Résumé technique : Méthodes de faisabilité aléatoires pour l'optimisation contrainte avec tailles de pas adaptatives

Formulation du problème

L'article traite le problème d'optimisation contrainte suivant :
$$\min_{x} f(x) \quad \text{sous la contrainte} \quad x \in X \cap Y$$
où $Y \subseteq \mathbb{R}^n$ est un ensemble convexe fermé qui est « facile à projeter sur » (par exemple, des boules ou des boîtes), et $X$ est défini comme l'intersection de $m$ ensembles de niveau inférieurs de fonctions convexes :
$$X := \bigcap_{i=1}^m \{x \in \mathbb{R}^n \mid g_i(x) \leq 0\}$$
Le défi principal survient lorsque $m$ est grand et que la projection sur l'intersection $X$ est numériquement intraitable. Les auteurs considèrent deux régimes distincts pour la fonction objectif $f$ :

1. Fortement convexe et Lipschitz-lisse : $f$ possède un minimiseur unique et des gradients lisses.
2. Convexe et potentiellement non lisse : $f$ peut manquer de lissage et de forte convexité.

L'objectif est de développer des algorithmes qui minimisent $f$ tout en garantissant la faisabilité par rapport à $X$ sans nécessiter une projection complète sur $X à chaque itération.

Méthodologie

L'approche proposée découple la minimisation de l'objectif de la satisfaction des contraintes à l'aide d'un cadre itératif en deux étapes :

1. Mises à jour de faisabilité aléatoires (Algorithme 1)

Pour gérer les contraintes complexes $X$, les auteurs emploient un algorithme de faisabilité aléatoire basé sur les étapes de Polyak. Au lieu de projeter sur l'ensemble complet $X$, l'algorithme :

• Échantillonne un indice de contrainte unique $\omega_k$ uniformément dans $\{1, \dots, m\}$.
• Calcule un sous-gradient de la fonction de violation de la contrainte échantillonnée $g^+_{\omega_k}(x) = \max\{0, g_{\omega_k}(x)\}$.
• Effectue une étape de sous-gradient avec une taille de pas de Polyak mise à l'échelle par un paramètre $\beta \in (0, 2)$.
• Projette le résultat sur l'ensemble « facile » $Y$.
• Répète ce processus $N_k$ fois par itération externe, où $N_k$ peut être déterministe ou aléatoire.

Le résultat de cette boucle interne, $x_k$, sert de mise à jour de faisabilité qui réduit la distance vers l'ensemble féasable $X \cap Y$ de manière géométrique.

2. Minimisation de l'objectif avec des étapes adaptatives

La boucle externe minimise $f(x)$ en utilisant les résultats des mises à jour de faisabilité. Le papier propose deux stratégies spécifiques basées sur les propriétés de $f$ :

• Cas (i) : Fortement convexe et lisse (Algorithme 2)
  La méthode combine des étapes de descente de gradient avec les mises à jour de faisabilité aléatoires. Les auteurs introduisent un schéma de taille de pas adaptative qui ne nécessite pas la connaissance préalable de la constante de forte convexité $\mu$ ou de la constante de Lipschitz $L$. La taille du pas est ajustée en fonction de la norme du gradient et d'une tolérance cible $\epsilon$.

• Cas (ii) : Convexe et potentiellement non lisse (Algorithmes 3 & 4)
  Pour les objectifs non lisses, le papier introduit un schéma adaptatif entièrement sans paramètres basé sur la Distance sur Sous-gradients Pondérés (DoWS), une variante de la méthode DoWG.

  • Algorithme 3 (DoWS) : Suppose que l'ensemble féasable $Y$ est borné. Il suit la distance maximale des itérés par rapport à un point initial et accumule les normes des sous-gradients pondérés pour déterminer la taille du pas.
  • Algorithme 4 (T-DoWS) : Une variante « tempérée » conçue pour les ensembles non bornés (par exemple, $Y = \mathbb{R}^n$). Elle modifie la mise à l'échelle de la taille du pas pour garantir que les itérés restent bornés sous une hypothèse de sous-niveau de $f$, supprimant ainsi la nécessité de la bornitude a priori de $Y$.

Contributions clés

1. Connexion théorique des bornes d'erreur et des multiplicateurs duaux :
   Les auteurs établissent une connexion entre les bornes d'erreur globales et les multiplicateurs duaux sous la condition de Slater forte. Ils prouvent qu'une borne supérieure uniforme sur les multiplicateurs duaux existe sans supposer la compacité de $Y$, un résultat dérivé de travaux antérieurs (Lewis & Pang, 1998 ; Bertsekas, 1999 ; Mangasarian, 1998) mais explicitement lié ici à la structure spécifique des contraintes.

2. Convergence linéaire pour les problèmes fortement convexes :
   Pour les objectifs fortement convexes et lisses, le papier prouve une convergence linéaire en espérance des valeurs de la fonction objectif vers toute tolérance $\epsilon$ prescrite. Ceci est réalisé grâce à des tailles de pas adaptatives et une condition spécifique sur le nombre d'échantillons de faisabilité $N_k$. Contrairement aux travaux précédents, ce résultat ne suppose pas a priori des sous-gradients bornés des fonctions de contrainte mais prouve qu'ils sont bornés presque sûrement.

3. Méthodes entièrement sans paramètres pour les problèmes non lisses :
   Le papier présente la première méthode entièrement sans paramètres pour résoudre le problème (P) sans projections, combinant DoWS avec des mises à jour de faisabilité aléatoires.

   • Elle atteint un taux de pire cas de $O(1/\sqrt{T})$ en espérance pour les objectifs convexes, potentiellement non lisses.
   • Elle introduit T-DoWS (Algorithme 4), qui garantit des itérés bornés et des taux de convergence optimaux même lorsque l'ensemble des contraintes $Y$ est non borné, à condition que les ensembles de sous-niveau de $f$ soient bornés.

4. Analyse des stratégies d'échantillonnage aléatoire :
   Les auteurs analysent l'impact du nombre d'échantillons de faisabilité $N_k$ par itération. Ils montrent que l'infaisabilité des itérés diminue géométriquement presque sûrement. Ils fournissent des orientations théoriques pour choisir la distribution de $N_k$ (par exemple, Poisson, Binomiale ou croissance déterministe) afin d'atteindre des taux de convergence optimaux, démontrant que des taux optimaux peuvent être obtenus avec des programmes de croissance de la taille de l'échantillon spécifiques.

Résultats et évaluation empirique

Garanties théoriques

• Cas fortement convexe : L'algorithme atteint une précision $\epsilon$ en $O(\ln(1/\epsilon))$ itérations. L'écart d'infaisabilité décroît géométriquement avec le nombre d'échantillons $N_k$.
• Cas convexe non lisse : Les itérés moyennés atteignent une borne d'erreur attendue de $O(1/\sqrt{T})$ (à un facteur logarithmique près selon le ratio du diamètre de l'ensemble par rapport à l'estimation initiale). La borne d'infaisabilité dépend de la distribution d'échantillonnage et diminue à un taux de $O(1/T)$ sous certaines conditions d'échantillonnage.

Simulations

Les auteurs valident leurs méthodes sur trois types de problèmes :

1. Programmation quadratique avec contraintes quadratiques (QCQP) : Démontre une convergence linéaire pour le cas fortement convexe et des performances compétitives pour le cas non lisse par rapport à Arrow-Hurwicz, Alt-GDA et ACVI.
2. Machines à vecteurs de support (SVM) : Montre que les méthodes proposées sans paramètres convergent sans nécessiter de validation croisée pour le réglage de la taille du pas, contrairement aux méthodes primal-dual qui souffrent d'un coût de calcul élevé dans les contextes en ligne.
3. Régression logistique avec contraintes d'équité de groupe : Illustre la capacité à gérer des contraintes d'équité complexes (modélisées comme des intersections d'ensembles de niveau inférieur) tout en atteignant une violation de faisabilité nulle et en convergeant vers la valeur optimale de l'objectif.

Dans toutes les simulations, les algorithmes proposés (Algorithmes 2, 3 et 4) démontrent une efficacité de calcul, particulièrement dans les scénarios avec un grand nombre de contraintes où la projection complète est infaisable. Les méthodes surpassent ou égalent les bases de référence de l'état de l'art (ACVI, Arrow-Hurwicz) tout en évitant le besoin de réglage d'hyperparamètres ou de résolution de sous-problèmes à chaque itération.

Signification et revendications

Le papier affirme faire progresser le domaine de l'optimisation contrainte en fournissant des algorithmes efficaces sur le plan computationnel, théoriquement fondés et entièrement sans paramètres pour des problèmes comportant un grand nombre de contraintes.

• Nouveauté : Les auteurs affirment qu'il s'agit de la première fois qu'une combinaison de DoWG (ou de sa variante tempérée) avec des mises à jour de faisabilité aléatoires est étudiée pour l'optimisation contrainte sans projections.
• Robustesse : Les méthodes ne nécessitent pas la connaissance des paramètres spécifiques au problème (constantes de forte convexité, constantes de Lipschitz ou valeurs optimales), ce qui les rend adaptées aux applications pratiques où ces informations sont indisponibles.
• Scalabilité : En utilisant des mises à jour de faisabilité aléatoires, les algorithmes évitent le goulot d'étranglement computationnel de la projection sur l'intersection de nombreuses contraintes, se adaptant efficacement aux problèmes de haute dimension comportant des milliers de contraintes.

Le travail fait le pont entre les méthodes de faisabilité aléatoires et les méthodes de gradient adaptatives, offrant un cadre unifié qui s'adapte à la fois aux objectifs lisses et non lisses tout en garantissant une faisabilité à décroissance géométrique.