A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization

Résumé Technique : Une Histoire de Deux Problèmes : l'Apprentissage Bilevel Multi-Tâche Rencontre l'Optimisation Multi-Objectif avec Contraintes d'Égalité

Énoncé du Problème
L'article aborde le défi de l'Apprentissage Bilevel Multi-Tâche (MTBL) dans le cadre de la Convexité Générale au Niveau Inférieur (LLGC). Bien que l'optimisation bilevel (BLO) soit largement utilisée en apprentissage automatique (par exemple, pour le réglage des hyperparamètres, l'apprentissage par méta et l'alignement des LLM), les cadres théoriques et les algorithmes existants reposent principalement sur l'hypothèse de la Convexité Forte au Niveau Inférieur (LLSC). Cette hypothèse garantit une solution unique au niveau inférieur et un hyper-gradient bien défini, mais elle est souvent violée dans les problèmes d'apprentissage automatique modernes et complexes où l'objectif au niveau inférieur est simplement convexe.

De plus, les travaux existants sur le MTBL sont largement confinés à des scénarios à tâche unique ou reposent sur la LLSC. Lors de l'extension du MTBL au cadre LLGC, deux problèmes critiques émergent :

1. L'hyper-gradient devient mal défini en raison de l'absence de convexité forte.
2. La présence de multiples objectifs au niveau supérieur, potentiellement conflictuels, nécessite une interprétation d'équilibre de Pareto, ce qui complique les critères d'optimalité.

Méthodologie
Les auteurs proposent un cadre novateur qui reformule le problème LLGC-MTBL en un problème d'Optimisation Multi-Objectif avec Contraintes d'Égalité (ECMO). Les étapes méthodologiques centrales sont :

1. Reformulation en ECMO :
   Au lieu de résoudre directement le problème bilevel imbriqué, les auteurs observent que pour une fonction convexe au niveau inférieur $g(x, y)$, la condition d'optimalité $\nabla_y g(x, y) = 0$ est à la fois nécessaire et suffisante. Ils reformulent le problème MTBL comme suit :
   $$\min_{z} F(z) = [f_1(z), \dots, f_S(z)]^\top \quad \text{sous } \quad h_i(z) = 0, \forall i \in [q]$$
   où $z = [x^\top, y^\top]^\top$ et $h_i(z)$ représente la $i$-ème composante du gradient au niveau inférieur $\nabla_y g(x, y)$.

2. Caractérisation de la Stationnarité de Pareto pour l'ECMO :
   L'article identifie que les définitions standard de stationnarité de Pareto pour l'optimisation multi-objectif (MOO) non contrainte sont insuffisantes pour l'ECMO en raison des contraintes de faisabilité. Les auteurs établissent un nouveau critère de stationnarité de Pareto basé sur les conditions KKT. Ils exploitent la scalarisation de Tchebycheff pondérée (WC) pour créer une correspondance biunivoque entre le front de Pareto du problème ECMO et les solutions d'un problème scalarisé. En analysant les conditions Karush-Kuhn-Tucker (KKT) du problème scalarisé par WC, ils définissent une métrique de convergence rigoureuse basée sur la norme du système résiduel KKT.

3. Conception de l'Algorithme (WC-Penalty) :
   Pour résoudre le problème ECMO, les auteurs proposent l'algorithme WC-Penalty. Cette méthode :

   • Reformule le problème scalarisé par WC en introduisant des variables d'écart pour gérer la minimisation de la norme $\ell_\infty$.
   • Convertit les contraintes d'égalité (à la fois les contraintes originales et les contraintes liées aux variables d'écart) en termes de pénalité au sein de la fonction objectif.
   • Résout le problème résultant, à un seul niveau et à objectif unique contraint, en utilisant la Descente de Gradient Projeté (GD).
   • Opère dans des contextes déterministes et stochastiques.

Contributions Clés

• Extension Théorique : Ce travail est le premier à étendre l'optimisation bilevel au cadre multi-tâche sous l'hypothèse relâchée de LLGC.
• Nouvelle Formulation de Problème : Il introduit le problème ECMO comme une formulation distincte qui n'avait pas été étudiée théoriquement avant ce travail, traitant spécifiquement de l'absence de garanties de convergence en temps fini dans la littérature existante.
• Nouvelle Métrique de Convergence : Les auteurs définissent une nouvelle métrique de stationnarité de Pareto basée sur les KKT pour l'ECMO, résolvant l'ambiguïté des conditions d'optimalité dans les contextes multi-objectifs contraints.
• Algorithme et Taux de Convergence : Ils proposent l'algorithme WC-Penalty et prouvent un taux de convergence en temps fini de $O(S T^{-1/2})$ vers la stationnarité de Pareto basée sur les KKT, où $S$ est le nombre d'objectifs et $T$ le nombre total d'itérations. Il s'agit de la première garantie de ce type pour les problèmes ECMO.
• Exploration du Front de Pareto : En faisant varier le vecteur de préférence sur le simplexe, la méthode explore systématiquement l'ensemble du front de Pareto.

Résultats Expérimentaux
Les auteurs valident leur approche sur deux tâches de pondération de données multi-objectifs :

1. Entraînement de Modèle de Récompense RLHF : En utilisant le jeu de données HelpSteer, l'algorithme optimise les poids des données pour équilibrer plusieurs métriques alignées avec l'humain (utilité, exactitude, etc.). Les résultats montrent que l'algorithme WC-Penalty couvre une portion significativement plus large du front de Pareto par rapport aux bases de référence telles que MOML, MoCo et FORUM.
2. Alignement Multi-Objectif de LLM : La méthode est appliquée au fine-tuning de Llama-3.2-1B-Instruct (et étendue aux modèles 3B et 8B) pour minimiser plusieurs pertes de validation. L'algorithme démontre des performances supérieures dans les comparaisons d'hypervolume et de métrique $\epsilon$ par rapport aux bases de référence MTBL et bilevel existantes.
3. Exemples Synthétiques : Des expériences synthétiques supplémentaires confirment la capacité de l'algorithme à retrouver l'intégralité du front de Pareto dans les contextes ECMO et LLGC-MTBL.

Signification et Revendications
L'article revendique la fermeture de la boucle entre les cadres d'optimisation fondamentaux en traduisant directement les solutions du problème ECMO vers le problème MTBL original. Les auteurs soulignent que leur travail fournit la première garantie de convergence en temps fini pour les problèmes ECMO, un vide laissé par la littérature précédente. En assouplissant l'hypothèse LLSC, le cadre proposé étend l'applicabilité de l'apprentissage bilevel à des scénarios d'apprentissage automatique plus complexes et réels où la convexité forte ne peut être supposée. Les résultats suggèrent que la méthode WC-Penalty offre à la fois une rigueur théorique et une efficacité pratique dans l'exploration de solutions optimales de Pareto pour l'apprentissage bilevel multi-tâche.