Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization

Résumé Technique : Garanties KKT du second ordre pour l'ADMM de Bregman dans l'optimisation non convexe et non lipschitzienne

Formulation du Problème
Le papier traite de l'optimisation de problèmes non convexes à contraintes linéaires, où les fonctions objectifs peuvent manquer de continuité de gradient lipschitzienne globale. L'accent est mis sur la formulation à deux blocs :
$$\min_{x \in \mathbb{R}^n, y \in \mathbb{R}^m} f_1(x) + f_2(y) \quad \text{s.t.} \quad Ax + By = b,$$
où $f_1$ et $f_2$ peuvent être non convexes. Ce cadre est motivé par des objectifs polynomiaux issus de modèles de matrices et de tenseurs, où les hypothèses standards de lissage de Lipschitz échouent souvent car la norme du Hessien $\|\nabla^2 f\|$ peut être non bornée. Les auteurs étendent également l'analyse à une formulation de consensus global multi-blocs pertinente pour l'optimisation distribuée.

Méthodologie et Cadre
Les auteurs analysent l'ADMM de Bregman, une variante de l'algorithme de l'Alternating Direction Method of Multipliers qui remplace les termes proximaux euclidiens par des divergences de Bregman. Cela permet à l'algorithme d'opérer sous une condition de lissage relatif (et de bi-lissage relatif pour les cas multi-blocs) plutôt que sous un lissage lipschitzien global.

• Lissage Relatif : L'analyse repose sur une condition de comparaison de Hessien à deux côtés : $L_f \nabla^2 h(x) \pm \nabla^2 f(x) \succeq 0$, où $h$ est une fonction noyau fortement convexe. Ce cadre permet d'accommoder des objectifs polynomiaux en sélectionnant des noyaux polynomiaux appropriés.
• Structure Algorithmique : La méthode alterne entre des mises à jour de variables primales de type proximal de Bregman et une étape d'ascension duale. Les auteurs traitent une itération de l'algorithme comme une application de point fixe primal-duale lisse $g$ définie sur un domaine d'espace d'état ouvert invariant.
• Approche par Systèmes Dynamiques : Le mécanisme théorique central suit le point de vue des systèmes dynamiques. Les auteurs visent à démontrer que les points cols stricts (points KKT qui ne sont pas stationnaires du second ordre) correspondent à des points fixes instables de l'application $g$. En invoquant le Théorème de la Variété Stable, ils soutiennent que l'ensemble des initialisations convergeant vers de tels points instables a une mesure de Lebesgue nulle.

Contributions Clés

1. Évitement des Cols Stricts sans Gradient Lipschitzien : Le papier établit que pour l'ADMM de Bregman, sous lissage (bi-)relatif, les points KKT de type col strict sont des points fixes instables. Par conséquent, avec une initialisation aléatoire, les itérations convergent vers un col strict avec une probabilité nulle. Ce résultat est valable sans nécessiter de constante de lissage lipschitzienne globale, répondant ainsi à une limitation clé des analyses précédentes (ex. [5]) qui reposaient sur la géométrie euclidienne.
2. Nouveauté Technique des Arguments Spectraux : La preuve de l'instabilité nécessite des adaptations non triviales au cadre de Bregman :
   • Cas à deux blocs : Les auteurs développent une réduction de déterminant impliquant une étape de symétrisation et de mise à l'échelle spécifique à Bregman. Contrairement au cas euclidien, le problème spectral réduit n'est pas naturellement symétrique ; les auteurs introduisent une mise à l'échelle diagonale pour symétriser la matrice et identifier une direction de col strict.
   • Cas de Consensus Multi-blocs : Pour la formulation de consensus en étoile, la preuve utilise un argument d'annulation de l'espace nul. La structure spécifique du graphe en étoile (couplage entre un moyeu et une périphérie) permet à la pénalité de consensus de s'annuler le long de la direction de test d'égalité des $x$, isolant ainsi la courbure négative de l'objectif.
3. Stationnarité du Second Ordre des Points Limites : En combinant le résultat d'évitement des cols stricts avec les garanties de convergence du premier ordre existantes (qui assurent la convergence vers un point KKT sous des conditions telles que la bornitude et l'inégalité de Kurdyka-Łojasiewicz), les auteurs concluent que les points KKT limites sont presque sûrement stationnaires du second ordre.
4. Extension à l'Optimisation Distribuée : Le cadre est étendu à un problème de consensus multi-blocs, prouvant que les mêmes garanties d'évitement de col strict s'appliquent aux contextes distribués où les agents communiquent via une topologie en étoile.

Résultats et Expériences Numériques
Les conclusions théoriques sont validées par des expériences numériques sur deux modèles polynomiaux qui sortent du régime de lissage lipschitzien global :

• Factorisation de Matrice Distribuée : L'algorithme résout avec succès un problème de récupération de matrice de bas rang distribué. Les expériences démontrent une convergence rapide de l'objectif et des résidus de consensus vers la précision machine, confirmant la capacité de l'algorithme à gérer des objectifs polynomiaux non lipsitiens dans un contexte distribué.
• Factorisation de Tenseur Symétrique : Les auteurs appliquent l'idée de splitting proximal de Bregman à la factorisation de tenseur symétrique. Bien que la garantie théorique s'applique strictement à des objectifs séparables, cette expérience illustre l'utilité pratique de la régularisation de Bregman pour stabiliser les sous-problèmes pour des objectifs polynomiaux couplés. L'algorithme pousse les facteurs vers l'accord tout en minimant l'erreur de reconstruction.

Signification et Revendications
Le papier affirme que le mécanisme d'évitement des cols stricts, précédemment établi pour les méthodes proximales euclidiennes sous hypothèses de Lipschitz, survit à la transition vers l'ADMM de Bregman sous lissage relatif. La signification réside dans l'extension des garanties de convergence du second ordre à une classe plus large de problèmes non convexes (spécifiquement ceux avec des objectifs polynomiaux) où les constantes de lissage standards n'existent pas globalement.

Les auteurs soulignent que l'extension n'est pas une simple substitution triviale de termes proximaux ; elle nécessite de redériver la preuve d'instabilité au sein de la géométrie de Bregman, en gérant spécifiquement les blocs métriques introduits par les noyaux de Hessien. Ce travail comble le fossé entre les résultats de convergence du premier ordre pour les méthodes de Bregman non convexes et la propriété souhaitable d'éviter les cols stricts, assurant ainsi que les points limites sont probablement des minimiseurs locaux (et souvent globaux) dans des problèmes structurés comme la factorisation de matrices et de tenseurs.