Sintesi Tecnica: Sulla dipendenza dal numero di condizionamento nella ottimizzazione bilevel

Definizione del Problema

Questo articolo investiga la complessità dell'oracolo per trovare un punto $\epsilon$-stazionario per problemi di ottimizzazione bilevel utilizzando metodi del primo ordine. Il setting specifico considerato è l'ottimizzazione bilevel nonconvessa-fortemente-convessa (NC-SC), definita come:
$$\min_{x \in \mathbb{R}^{d_x}} F(x) = f(x, y^*(x)), \quad \text{dove} \quad y^*(x) = \arg\min_{y \in \mathbb{R}^{d_y}} g(x, y).$$
In questo contesto, l'obiettivo del livello superiore $f$ è nonconvesso, mentre l'obiettivo del livello inferiore $g$ è fortemente convesso in $y$. La sfida principale risiede nella dipendenza del tasso di convergenza dal numero di condizionamento del problema di livello inferiore, indicato come $\kappa_y = L_1/\mu_y$ (dove $L_1$ è la costante di smoothness e $\mu_y$ è la costante di forte convessità), e dal numero di condizionamento globale $\bar{\kappa}_y$.

Sebbene lavori recenti abbiano stabilito upper bound di $\tilde{O}(\bar{\kappa}_y^4 \epsilon^{-2})$ o migliorati $\tilde{O}(\bar{\kappa}_y^{7/2} \epsilon^{-2})$ per problemi deterministici smooth, la dipendenza ottimale dal numero di condizionamento rimane ignota. Nello specifico, non è chiaro se i problemi bilevel siano provabilmente più difficili dei problemi minimax (dove $f = -g$) riguardo alla dipendenza dal numero di condizionamento, poiché i problemi minimax ammettono un lower bound di $\Omega(\sqrt{\kappa_y}\epsilon^{-2})$.

Metodologia

Gli autori stabiliscono nuovi lower bound costruendo "istanze difficili" basate su strutture a zero-chain, una tecnica ampiamente utilizzata nella letteratura sui lower bound dell'ottimizzazione.

1. Costruzione dell'Istanza Difficile:
   L'innovazione centrale è una modifica delle istanze tipo-catena utilizzate per i problemi minimax NC-SC. Gli autori introducono una costruzione che sfrutta l'asimmetria tra la funzione di livello superiore $f$ e la funzione di livello inferiore $g$.

   • Caratterizzazione a due sorgenti: La costruzione utilizza due variabili specifiche per amplificare la dipendenza dal numero di condizionamento:
     • Una variabile di accoppiamento $y$ (nel livello inferiore) per catturare la complessità del calcolo di $y^*(x)$.
     • Una variabile di riscalamento $z$ (spostata dal livello superiore al livello inferiore) per catturare la dipendenza nella smoothness dell'iper-obiettivo $F(x)$.
   • Meccanismo: Progettando attentamente le connessioni tra le variabili $x, z$ e $y$, e aggiungendo regolarizzazione nonconvessa su $z$ invece che su $x$, gli autori creano uno scenario in cui la lunghezza effettiva della catena nel livello superiore è scalata da un fattore correlato a $\kappa_y$. Nello specifico, l'iper-obiettivo diventa equivalente a una zero-chain nonconvessa valutata in $K^2 x$, dove $K = \Omega(\sqrt{\kappa_y})$.

2. Classi di Algoritmi:
   I lower bound sono dimostrati applicabili a:

   • Algoritmi Deterministici del Primo Ordine: Algoritmi che accedono ai gradienti $\nabla f$ e $\nabla g$.
   • Algoritmi basati su HVP: Algoritmi che accedono a Prodotti Vettore-Hessiano (HVP). Gli autori dimostrano che per funzioni di livello inferiore quadratiche, gli oracoli HVP sono equivalenti agli oracoli del primo ordine in termini di accesso alle informazioni, il che significa che i lower bound valgono per entrambe le classi.
   • Algoritmi Stocastici: Una costruzione separata è utilizzata per i setting stocastici, utilizzando zero-chain randomizzate per gestire rumore e varianza.

Contributi Chiave e Risultati

1. Lower Bound NC-SC Deterministici

Il paper stabilisce il primo gap provabile nella dipendenza dal numero di condizionamento tra problemi bilevel e problemi minimax.

• Smooth del primo ordine ($p=1$): $\Omega(\kappa_y^{5/2} \epsilon^{-2})$. Questo migliora il lower bound minimax di $\Omega(\sqrt{\kappa_y}\epsilon^{-2})$.
• Smooth del secondo ordine ($p=2$): $\Omega(\kappa_y^{31/14} \epsilon^{-12/7})$.
• Arbitrariamente smooth ($p \ge 3$): $\Omega(\kappa_y^{21/10} \epsilon^{-8/5})$.

2. Setting Convesso e Fortemente Convesso

Gli autori estendono i loro risultati a setting in cui l'iper-obiettivo è convesso o fortemente convesso:

• Convesso-Fortemente-Convesso (C-SC): Migliora il precedente lower bound da $\tilde{\Omega}(\min\{\kappa_y, \epsilon^{-3/2}\}/\sqrt{\epsilon})$ a $\Omega(\kappa_y^{3/2}/\sqrt{\epsilon})$.
• Fortemente-Convesso-Fortemente-Convesso (SC-SC): Migliora il bound da $\tilde{\Omega}(\kappa_y \sqrt{\kappa_x})$ a $\tilde{\Omega}(\kappa_y^{3/2} \sqrt{\kappa_x})$.

3. Lower Bound NC-SC Stocastici

Per problemi stocastici con gradienti rumorosi:

• Lower Bound: $\Omega(\kappa_y^4 \epsilon^{-4})$ (dominato dal termine di varianza).
• Insight: Gli autori sostengono che nei setting stocastici, la varianza (amplificata dalla variabile di riscalamento) è il collo di bottiglia fondamentale, piuttosto che il bias (catturato dalla variabile di accoppiamento). Ciò porta a un lower bound significativamente più stretto rispetto al lavoro concorrente che si è concentrato sul bias.

4. Upper Bound Raffinati

Per contestualizzare i lower bound, gli autori raffinano gli esistenti upper bound applicando l'accelerazione di Nesterov nel loop interno (solver di livello inferiore):

• Per problemi deterministici smooth del primo ordine, l'upper bound è raffinato a $\tilde{O}(\bar{\kappa}_y^{7/2} \epsilon^{-2})$, e a $\tilde{O}(\kappa_y^{5/2} \epsilon^{-2})$ se la funzione di livello inferiore è quadratica.
• Ciò restringe il gap tra gli upper e i lower bound per problemi di livello inferiore quadratici a un piccolo fattore polilogaritmico o a un piccolo fattore polinomiale, suggerendo quasi l'ottimalità in questi specifici setting.

Significato e Rivendicazioni

Il paper rivendica di fornire la prima separazione provabile tra la complessità dell'ottimizzazione bilevel e quella dell'ottimizzazione minimax in termini di dipendenza dal numero di condizionamento.

• Difficoltà Fondamentale: I risultati dimostrano che i problemi bilevel sono provabilmente più difficili dei problemi minimax. L'aumentata dipendenza da $\kappa_y$ (ad esempio, $\kappa_y^{5/2}$ rispetto a $\sqrt{\kappa_y}$) riflette una difficoltà fondamentale derivante dalla struttura bilevel stessa, specificamente l'interazione tra il calcolo della soluzione di livello inferiore e la smoothness del livello superiore.
• Varianza vs Bias: Nel setting stocastico, il lavoro identifica la varianza come il fattore limitante primario per la velocità di convergenza, offrendo una nuova prospettiva sul perché l'ottimizzazione bilevel stocastica sia difficile.
• Strettezza (Tightness): Per funzioni di livello inferiore quadratiche, gli stabiliti lower bound sono mostrati essere quasi ottimali, poiché i raffinati upper bound corrispondono a essi salvo piccoli fattori.

Gli autori osservano che, sebbene i loro bound siano stretti per funzioni di livello inferiore quadratiche, stabilire bound più stretti per funzioni generalmente non quadratiche rimane un problema aperto. Lasciano inoltre aperto l'estensione dei loro lower bound stocastici ad algoritmi randomizzati per smoothness di ordine superiore e altri setting come la mean-squared smoothness.