Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods

Résumé technique : Bornes d'erreur, condition PL, croissance quadratique pour les fonctions faiblement convexes, et convergences linéaires des méthodes de point proximal

Énoncé du problème
De nombreux problèmes d'optimisation pratique, particulièrement en apprentissage automatique et en traitement du signal, manquent de convexité forte. Bien que les algorithmes du premier ordre soient connus pour atteindre une convergence linéaire sous convexité forte, des études récentes ont montré qu'une convergence linéaire peut également être garantie sous des conditions de régularité plus faibles (par exemple, l'inégalité de Polyak-Lojasiewicz, les bornes d'erreur, la croissance quadratique) pour les fonctions lisses et convexes. Cependant, les relations entre ces conditions n'étaient pas bien comprises dans le cadre des fonctions non lisses et non convexes. Plus précisément, la classe des fonctions faiblement convexes (fonctions $f$ telles que $f + \frac{\rho}{2}\|\cdot\|^2$ est convexe pour un certain $\rho \geq 0$) englobe de nombreux modèles modernes (par exemple, réseaux profonds non lisses, compositions de fonctions convexes et lisses) mais manquait d'un cadre unifié reliant ces conditions de régularité. De plus, les preuves existantes de la convergence linéaire de la Méthode du Point Proximal (PPM) reposaient souvent sur des hypothèses restrictives (par exemple, des minimiseurs uniques ou la continuité lipschitzienne locale de l'inverse du sous-différentiel) ou des arguments complexes.

Méthodologie
Le papier emploie des outils de l'analyse non lisse, spécifiquement la notion de pente, le principe de variation d'Ekeland et des lemmes d'estimation de distance, pour analyser les relations entre les conditions de régularité. Les auteurs définissent cinq conditions clés sur un ensemble de sous-niveau $[f \leq f^\star + \nu]$ :

1. Convexité Forte (SC)
2. Inégalité de Sécante Restreinte (RSI)
3. Borne d'Erreur du Sous-différentiel (EB)
4. Inégalité de Polyak-Lojasiewicz (PL)
5. Croissance Quadratique (QG)

Les auteurs utilisent la pente $|\nabla f|(x) = \text{dist}(0, \hat{\partial}f(x))$ (où $\hat{\partial}f$ est le sous-différentiel de Fréchet) pour combler l'écart entre les contextes lisses et non lisses. Ils établissent des implications logiques et des équivalences entre ces conditions, en se concentrant particulièrement sur le cas où la constante de croissance quadratique $\mu_q$ est supérieure au paramètre de faible convexité $\rho$.

S'appuyant sur ces équivalences, le papier analyse la Méthode du Point Proximal (PPM) :
$$x_{k+1} = \text{prox}_{c_k f}(x_k) = \arg\min_x \left( f(x) + \frac{1}{2c_k}\|x - x_k\|^2 \right)$$
Les auteurs fournissent une preuve modulaire de la convergence linéaire pour les contextes convexes et faiblement convexes. Ils étendent également l'analyse à la PPM inexacte (iPPM), où les sous-problèmes sont résolus approximativement, en traitant les subtilités concernant les critères d'arrêt et la faisabilité (garantir que les itérés restent dans le domaine de $f$).

Contributions clés

1. Unification des conditions de régularité pour les fonctions faiblement convexes :
   Le papier établit la hiérarchie et l'équivalence des conditions de régularité pour les fonctions $\rho$-faiblement convexes.

   • Chaîne d'implication générale : $(SC) \implies (RSI) \implies (EB) \iff (PL) \implies (QG)$.
   • Équivalence sous $\mu_q > \rho$ : Si une fonction $\rho$-faiblement convexe satisfait la Croissance Quadratique avec une constante $\mu_q > \rho$, alors les quatre conditions $(RSI), (EB), (PL)$ et $(QG)$ sont équivalentes.
   • Les auteurs dérivent des conversions explicites de coefficients entre ces conditions (résumées dans le Tableau 1 du papier), permettant aux praticiens de traduire les constantes d'une condition à une autre.

2. Simplification des preuves de convergence linéaire pour la PPM :
   Le papier présente une preuve simple et modulaire de la convergence linéaire de la PPM pour les fonctions convexes et faiblement convexes.

   • Cas convexe : Sous n'importe laquelle des conditions de régularité équivalentes (PL, EB, RSI, QG), la PPM atteint une convergence linéaire tant pour les valeurs de la fonction que pour la distance à l'ensemble des solutions. La preuve relaxe les hypothèses précédentes, supprimant l'exigence d'un minimiseur unique ou de la continuité lipschitzienne locale de l'inverse du sous-différentiel.
   • Cas faiblement convexe : Les résultats sont étendus aux fonctions $\rho$-faiblement convexes, à condition que l'initialisation soit dans un ensemble de sous-niveau satisfaisant la QG avec $\mu_q > \rho$ et que les tailles de pas satisfassent $1/c_k > \rho$.

3. Analyse de la PPM inexacte (iPPM) :
   Les auteurs clarifient les nuances de l'inexactitude et de la faisabilité dans l'iPPM. Ils établissent la convergence linéaire pour l'iPPM sous des critères d'arrêt standards (critères A et B de Rockafellar), à condition que la fonction satisfasse la QG dans un voisinage de l'ensemble des solutions. La preuve combine une inégalité clé de la littérature antérieure avec le cadre de régularité modulaire.

Résultats

• Théoriques : Le Théorème 3.1 confirme que pour les fonctions faiblement convexes, l'équivalence des conditions de régularité est vérifiée si $\mu_q > \rho$. Cela généralise les résultats précédents limités aux fonctions lisses ou convexes.
• Algorithmiques : Les Théorèmes 4.2 et 4.3 démontrent que la PPM converge linéairement avec des taux dépendant des constantes de régularité (par exemple, $\omega_k = \frac{1}{1+c_k\mu_p}$). Le Théorème 5.3 étend cela à la PPM inexacte, montrant que tant que l'inexactitude est contrôlée (la somme des erreurs est finie), le taux de convergence linéaire est préservé asymptotiquement.
• Numériques : Des expériences sur les problèmes de SVM Linéaire, Lasso et Elastic-Net confirment la convergence linéaire théorique de la PPM. Les expériences utilisent le package de modélisation YALMIP et le solveur MOSEK, montrant une convergence rapide tant dans les écarts de valeur de coût que dans la distance à l'ensemble des solutions.

Signification et affirmations
Le papier affirme généraliser la compréhension des conditions de régularité du cadre lisse/convexe vers la classe plus large des fonctions non lisses faiblement convexes. En clarifiant les connexions entre ces conditions, les auteurs fournissent un cadre unifié qui simplifie l'analyse des algorithmes itératifs.

Plus précisément, le papier soutient que :

• L'équivalence des conditions (RSI, EB, PL, QG) sous $\mu_q > \rho$ permet une analyse flexible ; une condition peut être établie pour déduire les résultats de convergence via les autres.
• Les preuves de convergence linéaire de la PPM sont plus simples et plus transparentes que la littérature existante, évitant des hypothèses restrictives comme les minimiseurs uniques.
• Les résultats facilitent le développement d'algorithmes pour l'optimisation non lisse, particulièrement pour les applications d'optimisation conique à grande échelle et d'apprentissage automatique où la faible convexité est prévalente.

Les auteurs notent que bien que l'équivalence de ces conditions ait été connue pour les fonctions lisses ou convexes, l'extension à la configuration faiblement convexe et la fourniture d'une preuve propre pour la PPM (incluant les versions inexactes) constitue la principale nouveauté. Le travail est présenté comme une version étendue d'un article de conférence, avec l'ajout de preuves détaillées, de conversions de coefficients et d'une analyse étendue de la PPM inexacte.