A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints

Résumé technique : Une méthode de descente de coordonnées par blocs pour l'optimisation composite non lisse sous contraintes d'orthogonalité

Énoncé du problème
L'article aborde le défi de l'optimisation composite non lisse sous contraintes d'orthogonalité, formulé comme suit :
$$\min_{X \in \mathbb{R}^{n \times r}} F(X) \triangleq f(X) + h(X), \quad \text{sous } X^T X = I_r$$
où $n \ge r$, $f(X)$ est une fonction lisse (potentiellement non convexe), et $h(X)$ est une fonction propre, semi-continue inférieurement, potentiellement non lisse et séparable par coordonnées. L'ensemble réalisable est la variété de Stiefel $\mathcal{M} = \text{St}(n, r)$. Ce cadre englobe des applications critiques en apprentissage statistique et en science des données, notamment l'analyse en composantes principales (ACP) parcimonieuse avec régularisation $\ell_0$ ou $\ell_1$, l'ACP non négative, l'entraînement de réseaux de neurones profonds avec contraintes d'orthogonalité, et l'apprentissage de dictionnaires.

Les méthodes existantes présentent des limitations significatives : beaucoup reposent sur des informations de gradient complet (coût computationnel élevé), échouent à traiter efficacement les objectifs non lisses par coordonnées, manquent de propriétés de descente véritables (atteignant souvent la faisabilité uniquement de manière asymptotique), ou offrent des garanties d'optimalité faibles (convergence uniquement vers des points critiques standards).

Méthodologie : L'algorithme OBCD
Les auteurs proposent OBCD (Descente de Coordonnées par Blocs Orthogonaux), une méthode réalisable qui met à jour simultanément $k$ lignes de la matrice solution $X$, où $k \ge 2$.

1. Schéma de mise à jour préservant les contraintes :
   Au lieu de projeter sur la variété ou d'utiliser des rétractions, OBCD emploie une règle de mise à jour spécifique qui maintient l'orthogonalité par construction. Pour un ensemble de travail d'indices de lignes $B$ (taille $k$), la mise à jour est définie comme suit :
   $$X^{t+1} = X^t + U_B (V - I_k) U_B^T X^t$$
   où $U_B$ sélectionne les lignes dans $B$, et $V \in \text{St}(k, k)$ est une matrice orthogonale résolvant un sous-problème. Le lemme 2.1 prouve que si $X^t$ est réalisable, $X^{t+1}$ reste réalisable pour tout $V \in \text{St}(k, k)$.

2. Formulation du sous-problème :
   À chaque itération, OBCD résout un sous-problème à petite échelle sur la variété de Stiefel de dimension $k \times k$. En utilisant une approche de Majorisation-Minimisation (MM), la partie lisse $f(X)$ est approximée par un surrogate quadratique, tandis que la partie non lisse $h(X)$ est conservée exacte. Le sous-problème résultant est :
   $$\bar{V}_t \in \arg\min_{V \in \text{St}(k, k)} \left( \frac{1}{2} \|V - I_k\|_{\tilde{Q}}^2 + \langle V, P \rangle + h(V Z) \right)$$
   où $Z = U_B^T X^t$, $P$ implique le gradient de $f$, et $\tilde{Q}$ est une matrice définie positive dérivée de l'Hessienne de $f$ ou d'un proxy scalaire.

3. Résolution des sous-problèmes :

   • Cas général $k$ : L'article suppose que le sous-problème peut être résolu exactement ou efficacement (par exemple, via des structures compatibles avec les proximaux).
   • Cas $k=2$ : Les auteurs introduisent une nouvelle Méthode de Recherche de Points de Rupture (BSM). En paramétrant les matrices orthogonales $2 \times 2$ à l'aide de rotations de Givens ($V^{rot}_\theta$) et de réflexions de Jacobi ($V^{ref}_\theta$), le sous-problème est réduit à une optimisation unidimensionnelle sur $\theta$. La BSM identifie tous les points de rupture (points critiques) de la fonction objectif (y compris ceux provenant du terme non lisse $h$) pour trouver le minimiseur global.

4. Sélection de l'ensemble de travail :
   L'algorithme prend en charge à la fois des stratégies aléatoires et cycliques pour sélectionner l'ensemble de travail $B$.

Contributions théoriques
L'article fournit une analyse théorique rigoureuse concernant l'optimalité et la convergence :

• Complétude du schéma de mise à jour : Les auteurs prouvent que le schéma de mise à jour ligne par ligne proposé est complet. Plus précisément, n'importe quel point sur la variété de Stiefel peut être atteint à partir de n'importe quel autre point réalisable via une séquence de ces mises à jour de $k$ lignes (Théorème 3.1, Corollaire 3.2).
• Conditions d'optimalité plus fortes : L'article définit les Points Stationnaires Globaux par Blocs-$k$ (points BSk). Une solution est un point BSk si aucune amélioration ne peut être obtenue en optimisant n'importe quel bloc de $k$ lignes. Les auteurs établissent une hiérarchie d'optimalité :
  $$\{\text{Optima Globaux}\} \subseteq \{\text{Points BSk}\} \subseteq \{\text{Points BSk+1}\} \subseteq \{\text{Points Critiques}\}$$
  Cela implique que les points BSk (pour $k \ge 2$) satisfont une condition d'optimalité strictement plus forte que les points critiques standards, permettant théoriquement à l'algorithme d'échapper aux minima locaux pauvres qui piègent les méthodes standards.
• Complexité en itérations :
  • OBCD trouve un point stationnaire par blocs-$k$ de précision $\epsilon$ avec une complexité en itérations de $O(1/\epsilon)$.
  • Sous l'hypothèse de l'inégalité de Kurdyka–Łojasiewicz (KL), l'article établit des taux de convergence non ergodiques (convergence de la dernière itération). Selon l'exposant KL $\sigma$, la convergence est finie ($\sigma=0$), linéaire ($\sigma \in (0, 1/2]$), ou sous-linéaire ($\sigma \in (1/2, 1)$).

Résultats expérimentaux
Les auteurs évaluent OBCD sur l'ACP parcimonieuse régularisée L0, l'ACP parcimonieuse régularisée L1, et l'ACP non négative en utilisant des jeux de données réels (par exemple, MNIST, Gisette, 20News) et des données synthétiques.

• Performance : OBCD surpasse systématiquement les références de l'état de l'art, notamment ADMM linéarisé (LADMM), ADMM riemannien (RADMM), Méthode de séparation basée sur la pénalité (PSM), et Gradient Proximal sur Variété (ManPG).
• Valeurs de l'objectif : En termes de valeur finale de l'objectif, OBCD atteint des valeurs plus faibles que les méthodes concurrentes, échappant souvent aux minima locaux où les autres restent piégés.
• Efficacité : Bien que les méthodes de gradient complet puissent nécessiter moins d'itérations, le coût inférieur par itération d'OBCD (mises à jour de gradient partiel) se traduit par une performance supérieure lorsqu'elle est mesurée en temps CPU.
• Faisabilité : Contrairement à certaines méthodes non réalisables (par exemple, certaines méthodes de séparation) qui ne satisfont les contraintes qu'à la limite, OBCD maintient une orthogonalité stricte (et la non-négativité dans la variante ACP non négative) tout au long du processus d'optimisation.

Signification et affirmations
L'article affirme que OBCD représente une avancée significative en combinant l'efficacité computationnelle avec de fortes garanties théoriques. Sa signification principale réside dans :

1. Gestion de la non-lissité : Il traite efficacement les objectifs non lisses par coordonnées sous contraintes d'orthogonalité, un contexte où de nombreuses méthodes d'optimisation sur variété existantes peinent.
2. Optimalité renforcée : En utilisant des mises à jour par blocs ($k \ge 2$), la méthode cible les points BSk, qui sont théoriquement supérieurs aux points critiques standards, offrant un mécanisme pour éviter les minima locaux sous-optimaux.
3. Faisabilité : C'est une méthode strictement réalisable, assurant que les contraintes sont satisfaites à chaque itération, contrairement aux approches de séparation basées sur la pénalité ou non réalisables.
4. Efficacité pratique : L'algorithme est conçu pour des problèmes à grande échelle où les calculs de gradient complet sont prohibitifs, offrant une alternative évolutive avec des propriétés de convergence prouvées.