A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization

Sintesi Tecnica: Una Storia di Due Problemi: Apprendimento Bilevel Multi-Task incontra l'Ottimizzazione Multi-Obiettivo con Vincoli di Uguaglianza

Enunciato del Problema
Il documento affronta la sfida dell'Apprendimento Bilevel Multi-Task (MTBL) in condizioni di Convessità Generale al Livello Inferiore (LLGC). Sebbene l'ottimizzazione bilevel (BLO) sia ampiamente utilizzata nell'apprendimento automatico (ad esempio, per la regolazione degli iperparametri, l'apprendimento meta e l'allineamento dei LLM), i quadri teorici e gli algoritmi esistenti si basano prevalentemente sull'assunzione di Convessità Forte al Livello Inferiore (LLSC). Tale assunzione garantisce una soluzione unica al livello inferiore e un iper-gradiente ben definito, ma è spesso violata in problemi moderni e complessi di apprendimento automatico dove l'obiettivo al livello inferiore è meramente convesso.

Inoltre, i lavori esistenti su MTBL sono largamente confinati a contesti a singolo compito o si basano sulla LLSC. Quando si estende MTBL al contesto LLGC, sorgono due questioni critiche:

1. L'iper-gradiente diventa mal definito a causa della mancanza di convessità forte.
2. La presenza di molteplici obiettivi al livello superiore, potenzialmente conflittuali, richiede un'interpretazione di equilibrio di Pareto, complicando i criteri di ottimalità.

Metodologia
Gli autori propongono un nuovo quadro che riformula il problema LLGC-MTBL in un problema di Ottimizzazione Multi-Obiettivo con Vincoli di Uguaglianza (ECMO). I passaggi metodologici fondamentali sono:

1. Riformulazione in ECMO:
   Invece di risolvere direttamente il problema bilevel annidato, gli autori osservano che per una funzione convessa al livello inferiore $g(x, y)$, la condizione di ottimalità $\nabla_y g(x, y) = 0$ è sia necessaria che sufficiente. Riformulano il problema MTBL come:
   $$\min_{z} F(z) = [f_1(z), \dots, f_S(z)]^\top \quad \text{s.t.} \quad h_i(z) = 0, \forall i \in [q]$$
   dove $z = [x^\top, y^\top]^\top$ e $h_i(z)$ rappresenta la $i$-esima componente del gradiente al livello inferiore $\nabla_y g(x, y)$.

2. Caratterizzazione della Stazionarietà di Pareto per ECMO:
   Il documento identifica che le definizioni standard di stazionarietà di Pareto per l'ottimizzazione multi-obiettivo (MOO) non vincolata sono insufficienti per ECMO a causa dei vincoli di fattibilità. Gli autori stabiliscono un nuovo criterio di stazionarietà di Pareto basato sulle condizioni KKT. Sfruttano la scalarizzazione Weighted-Chebyshev (WC) per creare una corrispondenza biunivoca tra il fronte di Pareto del problema ECMO e le soluzioni di un problema scalarizzato. Analizzando le condizioni Karush-Kuhn-Tucker (KKT) del problema scalarizzato WC, definiscono una metrica di convergenza rigorosa basata sulla norma del sistema di residui KKT.

3. Progettazione dell'Algoritmo (WC-Penalty):
   Per risolvere il problema ECMO, gli autori propongono l'algoritmo WC-Penalty. Questo metodo:

   • Riformula il problema scalarizzato WC introducendo variabili di slack per gestire la minimizzazione della norma $\ell_\infty$.
   • Converte i vincoli di uguaglianza (sia i vincoli originali che quelli delle variabili di slack) in termini di penalità all'interno della funzione obiettivo.
   • Risolve il problema risultante a singolo livello, vincolato e a obiettivo singolo, utilizzando la Discesa del Gradiente Proiettata (GD).
   • Opera sia in contesti deterministici che stocastici.

Contributi Chiave

• Estensione Teorica: Questo lavoro è il primo a estendere l'ottimizzazione bilevel al contesto multi-task sotto l'assunzione rilassata di LLGC.
• Nuova Formulazione del Problema: Introduce il problema ECMO come una formulazione distinta che non era stata studiata teoricamente prima di questo lavoro, affrontando specificamente la mancanza di garanzie di convergenza in tempo finito nella letteratura esistente.
• Nuova Metrica di Convergenza: Gli autori definiscono una nuova metrica di stazionarietà di Pareto basata su KKT per ECMO, risolvendo l'ambiguità delle condizioni di ottimalità in contesti multi-obiettivo vincolati.
• Algoritmo e Tasso di Convergenza: Propongono l'algoritmo WC-Penalty e dimostrano un tasso di convergenza in tempo finito di $O(S T^{-1/2})$ verso la stazionarietà di Pareto basata su KKT, dove $S$ è il numero di obiettivi e $T$ è il numero totale di iterazioni. Questa è la prima garanzia di questo tipo per problemi ECMO.
• Esplorazione del Fronte di Pareto: Variando il vettore di preferenze sul simpleisso, il metodo esplora sistematicamente l'intero fronte di Pareto.

Risultati Sperimentali
Gli autori validano il loro approccio su due attività di ponderazione dei dati multi-obiettivo:

1. Addestramento del Modello di Ricompensa RLHF: Utilizzando il dataset HelpSteer, l'algoritmo ottimizza i pesi dei dati per bilanciare molteplici metriche allineate all'uomo (utilità, correttezza, ecc.). I risultati mostrano che l'algoritmo WC-Penalty copre una porzione significativamente maggiore del fronte di Pareto rispetto a baseline come MOML, MoCo e FORUM.
2. Allineamento Multi-Obiettivo dei LLM: Il metodo viene applicato al fine-tuning di Llama-3.2-1B-Instruct (e scalato a modelli da 3B e 8B) per minimizzare molteplici perdite di validazione. L'algoritmo dimostra prestazioni superiori nelle comparazioni di volume ipervolume e metrica $\epsilon$ rispetto alle esistenti baseline MTBL e bilevel.
3. Esempi Sintetici: Ulteriori esperimenti sintetici confermano la capacità dell'algoritmo di recuperare l'intero fronte di Pareto sia nei contesti ECMO che LLGC-MTBL.

Significato e Affermazioni
Il documento afferma di chiudere il cerchio tra i quadri fondamentali di ottimizzazione traducendo le soluzioni dal problema ECMO direttamente al problema MTBL originale. Gli autori sottolineano che il loro lavoro fornisce la prima garanzia di convergenza in tempo finito per problemi ECMO, un vuoto precedentemente non affrontato nella letteratura. Rilassando l'assunzione di LLSC, il quadro proposto estende l'applicabilità dell'apprendimento bilevel a scenari di apprendimento automatico più complessi e reali, dove non è possibile assumere la convessità forte. I risultati suggeriscono che il metodo WC-Penalty offre sia rigore teorico che efficienza pratica nell'esplorare soluzioni ottimali di Pareto per l'apprendimento bilevel multi-task.