Résumé technique : Méthodes du premier ordre basées sur la pénalité pour l'optimisation bi-niveau avec des problèmes minimax et des niveaux inférieurs contraints

Formulation du problème

Ce papier traite d'une classe de problèmes d'optimisation bi-niveau où les problèmes de niveau supérieur et de niveau inférieur présentent tous deux des structures minimax. La formulation générale est définie comme suit :
$$\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\}$$
où $(y_1, y_2)$ représente un point selle de la fonction de niveau inférieur $\tilde{f}$. Les auteurs supposent des propriétés structurelles spécifiques : $f$ et $\tilde{f}$ peuvent être décomposés en composantes lisses et en fonctions convexes propres et fermées, avec des propriétés de convexité/concavité spécifiques concernant leurs variables respectives (par exemple, $\tilde{f}$ est convexe par rapport à $y_1$ et concave par rapport à $y_2$).

Un sous-ensemble significatif de ce travail se concentre sur les problèmes bi-niveau où le niveau inférieur est un problème de minimisation convexe avec des contraintes d'inégalité non linéaires convexes :
$$\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\}$$
Sous la condition de Slater, ce problème contraint est reformulé comme un cas particulier du cadre bi-niveau minimax général via la dualité lagrangienne.

La littérature existante se concentre largement sur l'optimisation bi-niveau où le niveau inférieur est une minimisation mono-objectif (souvent fortement convexe). Les méthodes reposant sur les hypergradients ou la différenciation implicite échouent souvent lorsque le niveau inférieur est simplement convexe, non convexe, ou possède une structure minimax. Ce travail vise à combler cette lacune en développant des méthodes du premier ordre pour le cadre de niveau inférieur minimax sans exiger de forte convexité.

Méthodologie

L'approche proposée utilise une reformulation par pénalité de la fonction de valeur. Le problème bi-niveau contraint est transformé en un problème minimax non contraint (ou plus simplement contraint) en introduisant un paramètre de pénalité $\rho$.

Cadre déterministe

1. Reformulation par pénalité : Le problème original est reformulé en un problème minimax à un seul niveau :
   $$\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)$$
   où $P_\rho$ intègre la fonction objectif et le terme de pénalité $\rho(p(x_1, y_1) - d(x_1, y_2))$, représentant l'écart de dualité du problème de niveau inférieur.
2. Algorithme : Les auteurs proposent une méthode de point proximal inexacte. La boucle externe met à jour les variables primales-duales en résolvant une séquence de sous-problèmes fortement convexes-fortement concaves (SCSC).
3. Résolveur de sous-problème : Chaque sous-problème est résolu à l'aide d'une méthode optimale du premier ordre (spécifiquement, une variante de la méthode de Lu et Mei [52] ou de Kovalev et Gasnikov [37]), notée OptFOM.
4. Complexité : La méthode trouve un point KKT $\epsilon$ avec une complexité d'oracle de $\tilde{O}(\epsilon^{-4})$.

Cadre stochastique

Lorsque seuls des oracles de gradient stochastique sont disponibles pour les composantes lisses :

1. Algorithme : La méthode de point proximal déterministe est adaptée pour utiliser une méthode Primal-Duale Accélérée Stochastique (SAPD) (spécifiquement SAPD+ de Zhang et al. [75]) pour résoudre les sous-problèmes internes.
2. Convergence : La méthode trouve un point KKT $\epsilon$ « presque » exact (où la solution est à une distance $\epsilon$ d'un point KKT $\epsilon$ exact) avec une complexité d'oracle stochastique de $\tilde{O}(\epsilon^{-9})$.

Application aux problèmes de niveau inférieur contraints

Pour le cas spécifique de l'optimisation bi-niveau avec un niveau inférieur convexe contraint (Problème 4), les auteurs montrent que sous la condition de Slater, les multiplicateurs de Lagrange sont bornés dans un hypercube $[0, B]^l$. Cela permet de reformuler le problème contraint comme le problème bi-niveau minimax général (Problème 1) en introduisant les variables duales comme variables d'optimisation explicites avec des contraintes de boîte. Cette reformulation évite le besoin d'un paramètre de pénalité interne, conduisant à des bornes de complexité améliorées par rapport aux travaux antérieurs.

Contributions clés

1. Premiers résultats de complexité pour le minimax bi-niveau : Le papier établit les premières bornes de complexité pour les méthodes du premier ordre déterministes et stochastiques pour l'optimisation bi-niveau où le niveau inférieur est un problème minimax.
   • Complexité déterministe : $\tilde{O}(\epsilon^{-4})$.
   • Complexité stochastique : $\tilde{O}(\epsilon^{-9})$.
2. Bornes améliorées pour les problèmes bi-niveau contraints : En reformulant les problèmes bi-niveau avec des niveaux inférieurs convexes contraints comme des instances du cadre minimax proposé, les auteurs atteignent une complexité de $\tilde{O}(\epsilon^{-4})$. Cela améliore les résultats existants pour les niveaux inférieurs simplement convexes ($\tilde{O}(\epsilon^{-7})$ dans [53]) et fortement convexes ($\tilde{O}(\epsilon^{-6})$ dans [51]). L'amélioration provient de l'évitement de l'utilisation d'un second paramètre de pénalité pour les contraintes internes, ce qui conduisait auparavant à des paramètres de régularité plus élevés.
3. Validation empirique :
   • Données synthétiques : Sur des problèmes bi-niveau linéaires contraints, la méthode proposée démontre des vitesses de convergence compétitives par rapport aux méthodes basées sur la pénalité existantes (FOP et SMO), en particulier lorsque la constante de Lipschitz est ajustée.
   • Application réelle : La méthode est appliquée au réglage d'hyperparamètres pour l'Optimisation Robuste Distributionnellement (DRO) en apprentissage profond. Sur les ensembles de données CelebA et Waterbirds, l'approche bi-niveau stochastique proposée surpasse les méthodes DRO standards en termes de précision du groupe le plus défavorisé tout en maintenant une précision moyenne comparable.

Résultats et signification

Le papier affirme que le cadre basé sur la pénalité proposé fournit une approche unifiée pour traiter les problèmes bi-niveau avec des structures minimax, un cadre précédemment inexploré dans la littérature concernant la complexité du premier ordre.

• Signification théorique : Le travail comble le fossé entre l'optimisation bi-niveau et l'optimisation minimax, fournissant des garanties de convergence rigoureuses sans s'appuyer sur des hypothèses de forte convexité pour le problème de niveau inférieur. La réduction de la complexité de $\tilde{O}(\epsilon^{-7})$ à $\tilde{O}(\epsilon^{-4})$ pour les niveaux inférieurs contraints est présentée comme une avancée théorique significative.
• Signification pratique : L'application à la DRO démontre l'utilité de la méthode dans des scénarios d'apprentissage machine impliquant des décalages de distribution et l'équité entre groupes. Les résultats sur les ensembles de données CelebA et Waterbirds montrent que la méthode peut efficacement gérer le défi de l'optimisation du « groupe le plus défavorisé », atteignant une précision supérieure pour ce groupe par rapport aux méthodes DRO de référence.

Les auteurs reconnaissent des limitations, notamment l'exigence de domaines réalisables compacts, l'utilisation d'un espace relevé pour les définitions KKT, et la complexité élevée du cas stochastique ($\tilde{O}(\epsilon^{-9})$), notant que les techniques de réduction de variance pourraient être une direction pour un travail futur.