Riepilogo Tecnico: Metodi del Primo Ordine Basati su Penalità per l'Ottimizzazione Bilevel con Strutture Minimax e Problemi di Livello Inferiore Vincolati

Formulazione del Problema

Questo articolo affronta una classe di problemi di ottimizzazione bilevel in cui sia il problema di livello superiore che quello di livello inferiore presentano strutture minimax. La formulazione generale è definita come:
$$\min_{x_1, y_1, y_2} \left\{ \max_{x_2} f(x_1, x_2, y_1, y_2) \mid (y_1, y_2) \in \arg\min_{z_1} \max_{z_2} \tilde{f}(x_1, z_1, z_2) \right\}$$
dove $(y_1, y_2)$ rappresenta un punto di sella della funzione di livello inferiore $\tilde{f}$. Gli autori assumono specifiche proprietà strutturali: $f$ e $\tilde{f}$ possono essere decomposti in componenti lisce e funzioni convesse proprie e chiuse, con specifiche proprietà di convessità/concavità riguardo alle rispettive variabili (ad esempio, $\tilde{f}$ è convesso in $y_1$ e concavo in $y_2$).

Un sottoinsieme significativo di questo lavoro si concentra su problemi bilevel in cui il livello inferiore è un problema di minimizzazione convesso con vincoli di disuguaglianza non lineari convessi:
$$\min_{x_1, y_1} \left\{ f(x_1, y_1) \mid y_1 \in \arg\min_{z_1} \{ \bar{f}(x_1, z_1) \mid \bar{g}(x_1, z_1) \leq 0 \} \right\}$$
Sotto la condizione di Slater, questo problema vincolato viene riformulato come un caso particolare del quadro generale bilevel minimax tramite la dualità lagrangiana.

La letteratura esistente si concentra largamente sull'ottimizzazione bilevel in cui il livello inferiore è una minimizzazione a obiettivo singolo (spesso fortemente convessa). Metodi basati su ipergradienti o differenziazione implicita spesso falliscono quando il livello inferiore è semplicemente convesso, non convesso o possiede una struttura minimax. Questo lavoro mira a colmare il vuoto sviluppando metodi del primo ordine per l'impostazione del livello inferiore minimax senza richiedere convessità forte.

Metodologia

L'approccio proposto utilizza una riformulazione a penalità della funzione valore. Il problema bilevel vincolato viene trasformato in un problema minimax non vincolato (o vincolato in modo più semplice) introducendo un parametro di penalità $\rho$.

Contesto Deterministico

1. Riformulazione a Penalità: Il problema originale viene riformulato in un problema minimax a singolo livello:
   $$\min_{x_1, y_1, y_2} \max_{x_2, z_1, z_2} P_\rho(x_1, x_2, y_1, y_2, z_1, z_2)$$
   dove $P_\rho$ incorpora la funzione obiettivo e il termine di penalità $\rho(p(x_1, y_1) - d(x_1, y_2))$, rappresentante il gap di dualità del problema di livello inferiore.
2. Algoritmo: Gli autori propongono un metodo del punto prossimale inesatto. Il ciclo esterno aggiorna le variabili primali-duali risolvendo una sequenza di sottoproblemi fortemente convessi-strongamente concavi (SCSC).
3. Risolvitore del Sottoproblema: Ogni sottoproblema viene risolto utilizzando un metodo ottimo del primo ordine (specificamente, una variante del metodo di Lu e Mei [52] o di Kovalev e Gasnikov [37]), denominato OptFOM.
4. Complessità: Il metodo trova un punto KKT-$\epsilon$ con una complessità di oracolo di $\tilde{O}(\epsilon^{-4})$.

Contesto Stocastico

Quando sono disponibili solo oracoli di gradiente stocastico per le componenti lisce:

1. Algoritmo: Il metodo del punto prossimale deterministico viene adattato per utilizzare un metodo Primal-Dual Accelerato Stocastico (SAPD) (specificamente SAPD+ di Zhang et al. [75]) per risolvere i sottoproblemi interni.
2. Convergenza: Il metodo trova un punto "quasi" KKT-$\epsilon$ (dove la soluzione è entro una distanza $\epsilon$ da un esatto punto KKT-$\epsilon$) con una complessità di oracolo stocastico di $\tilde{O}(\epsilon^{-9})$.

Applicazione ai Problemi di Livello Inferiore Vincolati

Per il caso specifico di ottimizzazione bilevel con un livello inferiore convesso vincolato (Problema 4), gli autori dimostrano che, sotto la condizione di Slater, i moltiplicatori di Lagrange sono limitati all'interno di un box $[0, B]^l$. Ciò permette di riformulare il problema vincolato come il problema bilevel minimax generale (Problema 1) introducendo le variabili duali come variabili di ottimizzazione esplicite con vincoli a box. Questa riformulazione evita la necessità di un parametro di penalità interno, portando a limiti di complessità migliorati rispetto ai lavori precedenti.

Contributi Chiave

1. Primi Risultati di Complessità per Minimax Bilevel: L'articolo stabilisce i primi limiti di complessità per metodi del primo ordine deterministici e stocastici per l'ottimizzazione bilevel in cui il livello inferiore è un problema minimax.
   • Complessità deterministica: $\tilde{O}(\epsilon^{-4})$.
   • Complessità stocastica: $\tilde{O}(\epsilon^{-9})$.
2. Limiti Migliorati per Problemi Bilevel Vincolati: Riformulando i problemi bilevel con livelli inferiori vincolati convessi come istanze del quadro minimax proposto, gli autori raggiungono una complessità di $\tilde{O}(\epsilon^{-4})$. Questo migliora i risultati esistenti per livelli inferiori semplicemente convessi ($\tilde{O}(\epsilon^{-7})$ in [53]) e fortemente convessi ($\tilde{O}(\epsilon^{-6})$ in [51]). Il miglioramento deriva dall'evitare l'uso di un secondo parametro di penalità per i vincoli interni, che in precedenza portava a parametri di regolarità più elevati.
3. Validazione Empirica:
   • Dati Sintetici: Su problemi bilevel lineari vincolati, il metodo proposto dimostra velocità di convergenza competitive rispetto ai metodi basati su penalità esistenti (FOP e SMO), in particolare quando la costante di Lipschitz viene tarata.
   • Applicazione Reale: Il metodo è applicato al tuning degli iperparametri per l'Ottimizzazione Robusta Distribuzionalmente (DRO) nell'apprendimento profondo. Sui dataset CelebA e Waterbirds, l'approccio bilevel stocastico proposto supera i metodi DRO standard in termini di accuratezza del gruppo peggiore, mantenendo un'accuratezza media comparabile.

Risultati e Significato

L'articolo afferma che il quadro proposto basato su penalità fornisce un approccio unificato per gestire problemi bilevel con strutture minimax, un contesto precedentemente inesplorato nella letteratura riguardo alla complessità del primo ordine.

• Significato Teorico: Il lavoro colma il divario tra ottimizzazione bilevel e ottimizzazione minimax, fornendo garanzie di convergenza rigorose senza fare affidamento su assunzioni di convessità forte per il problema di livello inferiore. La riduzione della complessità da $\tilde{O}(\epsilon^{-7})$ a $\tilde{O}(\epsilon^{-4})$ per livelli inferiori vincolati è presentata come un significativo avanzamento teorico.
• Significato Pratico: L'applicazione alla DRO dimostra l'utilità del metodo in scenari di apprendimento automatico che coinvolgono spostamenti distribuzionali e equità di gruppo. I risultati sui dataset CelebA e Waterbirds mostrano che il metodo può gestire efficacemente la sfida dell'ottimizzazione del "gruppo peggiore", raggiungendo un'accuratezza del gruppo peggiore superiore rispetto ai metodi DRO di base.

Gli autori riconoscono le limitazioni, inclusa la necessità di domini fattibili compatti, l'uso di uno spazio sollevato per le definizioni KKT e l'alta complessità del caso stocastico ($\tilde{O}(\epsilon^{-9})$), notando che le tecniche di riduzione della varianza potrebbero essere una direzione per lavori futuri.