Résumé Technique : Algorithmes Entièrement du Premier Ordre pour l'Optimisation Bilevel Non Convexe en Ligne

Formulation du Problème

Ce travail traite de l'Optimisation Bilevel Non Convexe en Ligne (OBO), un cadre où un agent doit générer une séquence de décisions $\{x_t\}_{t=1}^T$ pour suivre des solutions optimales variant dans le temps dans un environnement en flux continu. Le problème est formulé comme suit :
$$\min_{x \in \mathcal{X}} F_t(x) := f_t(x, y^*_t(x)) \quad \text{sous contrainte} \quad y^*_t(x) = \arg\min_{y \in \mathbb{R}^{d_2}} g_t(x, y)$$
où l'objectif de niveau supérieur $f_t$ est lisse mais potentiellement non convexe, et l'objectif de niveau inférieur $g_t$ est lisse et $\mu_g$-fortement convexe. Le défi réside dans la nature dynamique du problème, où $f_t$ et $g_t$ changent tous deux au cours du temps, et où la solution interne $y^*_t(x)$ dérive.

Les méthodes OBO existantes reposent généralement sur la descente de gradient hyper, qui nécessite le calcul d'informations du second ordre (produits vecteur-Hessien, HVP) via une différenciation implicite. Cela engendre des coûts de calcul élevés et limite l'applicabilité lorsque les HVP sont indisponibles ou coûteux. Cet article se concentre sur le développement d'algorithmes reposant exclusivement sur des gradients du premier ordre (oracles du premier ordre) pour les deux niveaux.

Méthodologie

La contribution méthodologique centrale est la reformulation du problème bilevel original en un problème d'optimisation en ligne à un seul niveau avec contraintes d'inégalité. En introduisant une fonction de Lagrange $L_t(x, y, \lambda_t) = f_t(x, y) + \lambda_t (g_t(x, y) - g_t(x, y^*_t(x)))$, les auteurs transforment le problème en une optimisation min-max sur le Lagrangien.

Crucialement, cette reformulation élimine le besoin du terme implicite $\nabla y^*_t(x)$ présent dans les calculs standards de gradient hyper. Le gradient de la fonction de valeur optimale du Lagrangien, $\nabla L^*_t(x)$, peut être approximé en utilisant uniquement les gradients du premier ordre de $f_t$ et $g_t$, à condition que le multiplicateur de Lagrange $\lambda_t$ soit suffisamment grand.

L'article propose trois algorithmes spécifiques :

1. F2OBO (Optimiseur Bilevel en Ligne Entièrement du Premier Ordre) :

   • Structure : Utilise une approche de boucle interne imbriquée pour résoudre simultanément la solution de niveau interne $y^*_t(x_t)$ et la solution du Lagrangien $y^*_{\lambda_t, t}(x_t)$ via une descente de gradient.
   • Mécanisme : Met à jour la variable de niveau supérieur $x_t$ en utilisant un gradient hyper approximé dérivé du Lagrangien. Le multiplicateur $\lambda_t$ suit un calendrier non décroissant $\Lambda(t, \lambda_t) = (1 + 1/t)^\tau \lambda_1$.
   • Complexité : Nécessite $O(T \log T)$ itérations au total.

2. F2OBO en Boucle Unique :

   • Structure : Restreint la boucle interne à une seule itération ($K_t = 1$) pour réduire la surcharge de calcul.
   • Mécanisme : Pour contrôler l'erreur provenant des solutions internes inexactes, cette variante introduit des termes de variation de gradient supplémentaires ($E_{f,y,T}$ et $E_{g,y,T}$) dans l'analyse du regret, mesurant le changement des gradients du premier ordre des objectifs internes au cours du temps.

3. AF2OBO (Optimiseur Bilevel en Ligne Entièrement du Premier Ordre Adaptatif) :

   • Structure : Une variante améliorée de F2OBO qui emploie un schéma d'itération interne adaptatif.
   • Mécanisme : Au lieu d'un nombre fixe d'itérations, les boucles internes s'exécutent jusqu'à ce que les normes de gradient tombent en dessous de seuils de tolérance spécifiques ($\delta_y, \delta_z$). Cet ajustement dynamique permet à l'algorithme d'éliminer la dépendance à la variation de dérive de la solution interne ($H_{2,T}$) dans la borne de regret, au prix d'un nombre d'itérations potentiellement plus élevé.

4. SF2OBO (Optimiseur Bilevel en Ligne Entièrement du Premier Ordre Stochastique) :

   • Structure : Étend F2OBO au cadre stochastique où les gradients sont bruités.
   • Mécanisme : Utilise des gradients stochastiques par lots pour les boucles interne et externe. Les tailles de lots augmentent au fil du temps pour contrôler la variance et le biais, évitant ainsi le besoin d'une analyse du regret moyennée sur une fenêtre utilisée dans les méthodes stochastiques antérieures.

Contributions Clés et Résultats Théoriques

L'article établit des garanties théoriques pour le regret local bilevel ($BLReg(T) = \sum_{t=1}^T \|G_\mathcal{X}(x_t, \nabla F_t(x_t), \gamma)\|^2$), défini comme la somme des carrés des applications de gradient.

• Bornes de Regret Déterministes :

  • F2OBO : Atteint une borne de regret de $O(1 + V_T + H_{2,T})$ avec $O(T \log T)$ itérations, où $V_T$ est la variation des valeurs de fonction et $H_{2,T}$ est la dérive de la solution optimale interne. Cela correspond aux performances des méthodes du second ordre sans nécessiter de HVP.
  • F2OBO en Boucle Unique : Atteint un regret sous-linéaire de $O(T^{1/3}(1 + V_T) + T^{2/3}P_T)$, où $P_T$ inclut les termes de variation de gradient. Cela démontre la faisabilité sous une structure en boucle unique, bien qu'avec une borne plus faible dépendante de la stabilité du gradient.
  • AF2OBO : Atteint un regret de $O(\log T + V_T)$, éliminant effectivement la dépendance à $H_{2,T}$. Ceci est significatif pour les scénarios où la solution interne dérive considérablement (par exemple, $H_{2,T} = O(T)$).

• Bornes de Regret Stochastiques :

  • SF2OBO : Établit une borne de regret de $O(T^{2/3}(1 + \sigma^2) + V_T + H_{2,T})$. Contrairement aux méthodes stochastiques antérieures (par exemple, SOBBO, SOGD) qui reposent sur un regret moyenné sur une fenêtre ou une variance de gradient du second ordre bornée, SF2OBO atteint cela sous des hypothèses plus faibles sur la variation environnementale et la variance standard du premier ordre.

Validation Expérimentale

Les auteurs valident leurs algorithmes sur deux tâches :

1. Réglage de Perte Paramétrique pour Données Déséquilibrées : Optimisation des poids de classe pour un CNN sur MNIST sous des distributions de classes changeantes. AF2OBO a obtenu la meilleure précision de test équilibrée.
2. Optimisation d'Hyperparamètres en Ligne : Optimisation des coefficients de régularisation L2 sur le jeu de données 20 Newsgroups sous bruit d'étiquettes et décalages de distribution. SF2OBO a démontré une précision de test supérieure et une efficacité compétitive par rapport à SOBBO et SOGD.

Importance et Revendications

L'article revendique que sa contribution principale est le développement d'algorithmes entièrement du premier ordre qui atteignent des bornes de regret comparables aux méthodes du second ordre existantes (qui nécessitent des HVP) tout en étant plus efficaces sur le plan computationnel et applicables à des cadres où l'information du second ordre est inaccessible.

• Élimination des HVP : En reformulant le problème via une relaxation de Lagrange, les auteurs contournent le besoin de différenciation implicite et de produits vecteur-Hessien.
• Robustesse à la Dérive : La variante adaptative (AF2OBO) offre une robustesse face aux dérives sévères de la solution de niveau interne, une limitation des méthodes à itérations statiques.
• Praticabilité : Les variantes en boucle unique et stochastiques démontrent que les approches entièrement du premier ordre peuvent être déployées dans des environnements pratiques, dynamiques et bruyants sans sacrifier les garanties théoriques de regret sous-linéaire.

Les auteurs reconnaissent que leur analyse théorique est actuellement restreinte aux problèmes avec des objectifs de niveau interne fortement convexes et suggèrent d'étendre ces résultats à des objectifs internes non convexes satisfaisant la condition de Polyak-Łojasiewicz (PL) comme une direction pour les travaux futurs.