Résumé Technique : Sur la dépendance au nombre de condition dans l'optimisation bi-niveau

Énoncé du Problème

Cet article étudie la complexité d'oracle pour trouver un point $\epsilon$-stationnaire pour des problèmes d'optimisation bi-niveau à l'aide de méthodes du premier ordre. Le cadre spécifique considéré est l'optimisation bi-niveau non-convexe-fortement-convexe (NC-SC), définie comme :
$$\min_{x \in \mathbb{R}^{d_x}} F(x) = f(x, y^*(x)), \quad \text{où} \quad y^*(x) = \arg\min_{y \in \mathbb{R}^{d_y}} g(x, y).$$
Ici, l'objectif du niveau supérieur $f$ est non-convexe, tandis que l'objectif du niveau inférieur $g$ est fortement convexe en $y$. Le défi principal réside dans la dépendance du taux de convergence vis-à-vis du nombre de condition du problème de niveau inférieur, noté $\kappa_y = L_1/\mu_y$ (où $L_1$ est la constante de lissage et $\mu_y$ la constante de forte convexité), ainsi que le nombre de condition global $\bar{\kappa}_y$.

Alors que des travaux récents ont établi des bornes supérieures de $\tilde{O}(\bar{\kappa}_y^4 \epsilon^{-2})$ ou améliorées de $\tilde{O}(\bar{\kappa}_y^{7/2} \epsilon^{-2})$ pour les problèmes déterministes lisses, la dépendance optimale vis-à-vis du nombre de condition reste inconnue. Plus précisément, il n'est pas clair si les problèmes bi-niveaux sont prouvablement plus difficiles que les problèmes minimax (où $f = -g$) concernant la dépendance au nombre de condition, car les problèmes minimax admettent une borne inférieure de $\Omega(\sqrt{\kappa_y}\epsilon^{-2})$.

Méthodologie

Les auteurs établissent de nouvelles bornes inférieures en construisant des « instances difficiles » basées sur des structures de chaîne de zéros (zero-chain), une technique largement utilisée dans la littérature des bornes inférieures d'optimisation.

1. Construction d'instances difficiles :
   L'innovation centrale est une modification des instances de type chaîne utilisées pour les problèmes minimax NC-SC. Les auteurs introduisent une construction qui exploite l'asymétrie entre la fonction de niveau supérieur $f$ et la fonction de niveau inférieur $g$.

   • Caractérisation à deux sources : La construction utilise deux variables spécifiques pour amplifier la dépendance au nombre de condition :
     • Une variable de couplage $y$ (dans le niveau inférieur) pour capturer la complexité du calcul de $y^*(x)$.
     • Une variable de remise à l'échelle $z$ (déplacée du niveau supérieur vers le niveau inférieur) pour capturer la dépendance dans le lissage de l'hyper-objectif $F(x)$.
   • Mécanisme : En concevant soigneusement les connexions entre les variables $x, z,$ et $y$, et en ajoutant une régularisation non-convexe sur $z$ plutôt que sur $x$, les auteurs créent un scénario où la longueur de la chaîne effective dans le niveau supérieur est mise à l'échelle par un facteur lié à $\kappa_y$. Spécifiquement, l'hyper-objectif devient équivalent à une chaîne de zéros non-convexe évaluée en $K^2 x$, où $K = \Omega(\sqrt{\kappa_y})$.

2. Classes d'algorithmes :
   Les bornes inférieures prouvées s'appliquent à :

   • Algorithmes déterministes du premier ordre : Algorithmes accédant aux gradients $\nabla f$ et $\nabla g$.
   • Algorithmes basés sur les HVP : Algorithmes accédant aux produits Hessien-Vecteur (HVP). Les auteurs prouvent que pour les fonctions de niveau inférieur quadratiques, les oracles HVP sont équivalents aux oracles du premier ordre en termes d'accès à l'information, ce qui signifie que les bornes inférieures s'appliquent aux deux classes.
   • Algorithmes stochastiques : Une construction distincte est utilisée pour les contextes stochastiques, utilisant des chaînes de zéros randomisées pour gérer le bruit et la variance.

Contributions Clés et Résultats

1. Bornes Inférieures Déterministes NC-SC

L'article établit le premier écart prouvable dans la dépendance au nombre de condition entre les problèmes bi-niveaux et les problèmes minimax.

• Lisse de premier ordre ($p=1$) : $\Omega(\kappa_y^{5/2} \epsilon^{-2})$. Cela améliore la borne inférieure minimax de $\Omega(\sqrt{\kappa_y}\epsilon^{-2})$.
• Lisse de second ordre ($p=2$) : $\Omega(\kappa_y^{31/14} \epsilon^{-12/7})$.
• Arbitrairement lisse ($p \ge 3$) : $\Omega(\kappa_y^{21/10} \epsilon^{-8/5})$.

2. Contextes Convexe et Fortement Convexe

Les auteurs étendent leurs résultats aux contextes où l'hyper-objectif est convexe ou fortement convexe :

• Convexe-Fortement-Convexe (C-SC) : Améliore la borne inférieure précédente de $\tilde{\Omega}(\min\{\kappa_y, \epsilon^{-3/2}\}/\sqrt{\epsilon})$ à $\Omega(\kappa_y^{3/2}/\sqrt{\epsilon})$.
• Fortement-Convexe-Fortement-Convexe (SC-SC) : Améliore la borne de $\tilde{\Omega}(\kappa_y \sqrt{\kappa_x})$ à $\tilde{\Omega}(\kappa_y^{3/2} \sqrt{\kappa_x})$.

3. Bornes Inférieures Stochastiques NC-SC

Pour les problèmes stochastiques avec des gradients bruités :

• Borne Inférieure : $\Omega(\kappa_y^4 \epsilon^{-4})$ (dominée par le terme de variance).
• Intuition : Les auteurs soutiennent que dans les contextes stochastiques, la variance (amplifiée par la variable de remise à l'échelle) est le goulot d'étranglement fondamental, plutôt que le biais (capturé par la variable de couplage). Cela conduit à une borne inférieure nettement plus serrée par rapport aux travaux concomitants qui se concentraient sur le biais.

4. Bornes Supérieures Raffinées

Pour contextualiser les bornes inférieures, les auteurs affinent les bornes supérieures existantes en appliant l'accélération de Nesterov dans la boucle interne (solveur de niveau inférieur) :

• Pour les problèmes déterministes lisses de premier ordre, la borne supérieure est raffinée à $\tilde{O}(\bar{\kappa}_y^{7/2} \epsilon^{-2})$, et à $\tilde{O}(\kappa_y^{5/2} \epsilon^{-2})$ si la fonction de niveau inférieur est quadratique.
• Cela réduit l'écart entre les bornes supérieures et inférieures pour les problèmes de niveau inférieur quadratiques à un petit facteur polylogarithmique ou un petit facteur polynomial, suggérant une quasi-optimalité dans ces contextes spécifiques.

Signification et Revendications

L'article affirme fournir la première séparation prouvable de la complexité de l'optimisation bi-niveaux par rapport à l'optimisation minimax en termes de dépendance au nombre de condition.

• Difficulté Fondamentale : Les résultats démontrent que les problèmes bi-niveaux sont prouvablement plus difficiles que les problèmes minimax. L'augmentation de la dépendance à $\kappa_y$ (par exemple, $\kappa_y^{5/2}$ contre $\sqrt{\kappa_y}$) reflète une difficulté fondamentale découlant de la structure bi-niveaux elle-même, spécifiquement l'interaction entre le calcul de la solution de niveau inférieur et le lissage de l'objectif supérieur.
• Variance vs Biais : Dans le contexte stochastique, le travail identifie la variance comme le facteur limitant principal pour la vitesse de convergence, offrant une nouvelle perspective sur la raison pour laquelle l'optimisation bi-niveaux stochastique est difficile.
• Optimalité : Pour les problèmes de niveau inférieur quadratiques, les bornes inférieures établies sont montrées comme étant presque optimales, car les bornes supérieures raffinées correspondent aux bornes inférieures à de petits facteurs près.

Les auteurs notent que bien que leurs bornes soient serrées pour les fonctions de niveau inférieur quadratiques, établir des bornes plus serrées pour les fonctions générales non-quadratiques reste un problème ouvert. Ils laissent également ouvert l'extension de leurs bornes inférieures stochastiques aux algorithmes randomisés pour la lissité d'ordre supérieur et d'autres contextes tels que la lissité de type moyenne-au-carré.