Résumé Technique : RanSOM

1. Énoncé du Problème

L'article aborde une limitation fondamentale de l'optimisation stochastique pour l'apprentissage profond : le biais induit par la courbure dans les méthodes de momentum standards (par exemple, la Balle Lourde de Polyak) lorsqu'elles sont appliquées à des paysages non convexes.

Dans des contextes stochastiques, le vecteur de momentum $m_t$ agrège les gradients d'itérés précédents. Alors que l'optimiseur se déplace de $x_{t-1}$ vers $x_t$, la courbure du paysage de perte provoque un changement de direction du gradient. Par conséquent, $m_{t-1}$ devient un estimateur « obsolète » du gradient actuel $\nabla f(x_t)$. Ce biais, proportionnel à l'intégrale de l'Hessienne le long du chemin de mise à jour, empêche les méthodes de momentum standards d'atteindre la complexité d'échantillonnage optimale $O(\epsilon^{-3})$ requise pour l'optimisation non convexe, les limitant souvent à des taux sous-optimaux de $O(\epsilon^{-4})$.

Les stratégies de correction existantes font face à un « goulot d'étranglement biais-variance » :

• Estimateurs basés sur les différences (par exemple, STORM) : Nécessitent une régularité des échantillons individuels (souvent violée par les activations ReLU) ou souffrent d'une variance élevée.
• Momentum d'ordre deux déterministe (SOM) : Requiert de fortes hypothèses de Lipschitz globales sur l'Hessienne (dérivées troisièmes bornées).
• SOM stochastique (SOM-Unif) : Assouplit les hypothèses de régularité mais engendre des surcoûts computationnels prohibitifs en exigeant des requêtes auxiliaires « anticipées » (3 passages avant/arrière par itération).

2. Méthodologie : Le Cadre RanSOM

Les auteurs proposent RanSOM (Momentum d'Ordre Deux Randomisé), un cadre unifié qui élimine le biais de courbure sans hypothèses supplémentaires ni surcoût computationnel. L'innovation centrale consiste à remplacer les tailles de pas déterministes par des tailles de pas randomisées tirées de distributions spécifiques.

2.1 Intégration par Parties Randomisée

Au lieu d'un pas fixe $\eta_t$, la taille de pas $s_t$ est traitée comme une variable aléatoire de moyenne $\mathbb{E}[s_t] = \eta_t$. En exploitant des identités de type Stein (formules d'intégration par parties), la méthode relie la différence finie des gradients (le biais) à un seul Produit Hessien-Vecteur (HVP) évalué à l'extrémité aléatoire.

Le cadre utilise deux identités spécifiques :

1. Identité Exponentielle (Sans contrainte) : Si $s \sim \text{Exp}(\lambda)$, alors :
   $$\mathbb{E}[g(s) - g(0)] = \frac{1}{\lambda} \mathbb{E}[g'(s)]$$
   Cela permet d'estimer le biais $\nabla f(x_{t+1}) - \nabla f(x_t)$ en mettant à l'échelle le HVP en $x_{t+1}$ par $\eta_t$.
2. Identité Bêta (Contrainte) : Si $s \sim \text{Beta}(1, K)$, alors :
   $$\mathbb{E}[g(s) - g(0)] = \mathbb{E}\left[ \frac{1-s}{K} g'(s) \right]$$
   Cela prend en compte le support compact de la distribution Bêta, assurant la faisabilité dans l'optimisation contrainte.

2.2 Instantiations Algorithmiques

Le cadre est instancié dans deux algorithmes :

• RanSOM-E (Sans contrainte) : Utilise des pas distribués exponentiellement. Il s'intègre avec un Oracle de Minimisation Linéaire (LMO) pour unifier diverses mises à jour géométriques, retrouvant le SGD Normalisé (boule $L_2$), le SignSGD (boule $L_\infty$) et les mises à jour spectrales de style Muon.
• RanSOM-B (Contraint) : Utilise des pas distribués selon une loi Bêta sur $[0, 1]$. Cela garantit que la mise à jour $x_{t+1} = (1-s_t)x_t + s_t v_t$ (où $v_t$ est la direction LMO) reste strictement à l'intérieur de l'ensemble réalisable convexe $C$, évitant les opérations de projection.

2.3 Efficacité Computationnelle

Un avantage critique de RanSOM est son coût computationnel. Le terme de correction nécessite un HVP en $x_{t+1}$. Dans les cadres modernes de différenciation automatique (par exemple, PyTorch, JAX), ce HVP peut être calculé via l'astuce de Pearlmutter en un seul passage arrière combiné parallèlement au calcul standard du gradient.

• Coût : $2(F_c + B_c)$ (équivalent à deux passages avant/arrière).
• Comparaison : Cela correspond au coût des méthodes standards de réduction de variance comme STORM et est nettement moins cher que SOM-Unif, qui nécessite une requête auxiliaire dédiée ($3(F_c + B_c)$).

3. Contributions Clés

1. Cadre Unifié : Une méthode qui élimine le biais induit par la courbure en utilisant des tailles de pas randomisées et des identités de Stein, applicable à la fois à l'optimisation sans contrainte et contrainte.
2. Taux de Convergence Optimaux : L'analyse théorique prouve que RanSOM atteint la complexité d'échantillonnage optimale $O(\epsilon^{-3})$ sous des hypothèses standards de bruit borné.
3. Robustesse aux Queues Lourdes : La méthode s'étend à des contextes difficiles avec un bruit de gradient à queues lourdes ($p \in (1, 2]$) et une régularité $(L_0, L_1)$ généralisée (où la norme de l'Hessienne croît avec la norme du gradient), sans exiger que l'Hessienne soit lipschitzienne.
4. Sans Surcoût Auxiliaire : Contrairement aux corrections d'ordre deux antérieures, RanSOM ne nécessite aucun point « anticipé » auxiliaire, maintenant la complexité de requête standard de $2(F_c + B_c)$.
5. Sans Recalage (Clipping-Free) : La méthode atteint des taux optimaux sans recalage explicite des gradients, s'appuyant plutôt sur la normalisation intrinsèque fournie par les mises à jour LMO et les propriétés statistiques des pas randomisés.

4. Résultats Théoriques

L'article établit la convergence pour l'optimisation non convexe sous les conditions suivantes :

• Hypothèses : L'objectif est borné inférieurement et satisfait une régularité $(L_0, L_1)$ ponctuelle. Les gradients stochastiques et les HVP sont non biaisés avec un bruit à queues lourdes affine (moments $p, q \in (1, 2]$).
• Sans contrainte (RanSOM-E) : Convergence vers un point stationnaire avec un taux :
  $$\frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}[\|\nabla f(x_t)\|_*] \leq O\left( T^{-\frac{q(p-1)}{2q(p-1)+p}} \right)$$
  Pour le cas standard ($p=q=2$), cela retrouve le taux optimal $O(T^{-1/3})$.
• Contraint (RanSOM-B) : Convergence en termes de l'écart de Frank-Wolfe $G(x)$ avec le même taux optimal $O(T^{-1/3})$ pour $p=q=2$.

L'analyse met en évidence une mise à l'échelle asymétrique du paramètre de momentum $\beta$ : un $\beta$ plus petit aide à lisser les gradients à forte variance, tandis qu'un $\beta$ plus grand rend la correction de courbure plus impactante. Le $\beta$ optimal équilibre ces effets.

5. Résultats Expérimentaux

Les auteurs évaluent RanSOM sur trois tâches non convexes :

1. Classification Binaire (SPLICE) : RanSOM-E (variante Muon) a atteint la précision de test la plus élevée (84,90 %) avec une variance significativement plus faible par rapport à STORM (73,35 % ± 10,77 %).
2. Classification de Séquences (MNIST1D) : RanSOM-E (Muon) a atteint 91,90 % de précision, surpassant STORM (88,83 %) et le SOM classique, tout en maintenant une stabilité élevée (écart-type ±0,36 contre ±1,38 pour STORM).
3. Complétion de Matrice Contrainte (MovieLens) : RanSOM-B a convergé vers un RMSE final plus faible que les bases de Frank-Wolfe stochastiques (SFW-Polyak, SFW-SOM), démontrant son efficacité pour naviguer dans des géométries de contraintes complexes.

6. Importance et Revendications

L'article revendique que RanSOM résout le « dilemme » des corrections de momentum d'ordre deux : il atteint le taux de convergence optimal de $O(\epsilon^{-3})$ sans les hypothèses restrictives d'Hessiennes lipschitziennes ou de régularité des échantillons individuels, et sans le surcoût computationnel de l'échantillonnage auxiliaire.

En traitant les tailles de pas comme des variables aléatoires, RanSOM permet une correction de biais d'ordre deux robuste qui est :

• Légère en hypothèses : Gère les pertes individuelles non régulières (par exemple, réseaux avec ReLU) et le bruit à queues lourdes.
• Efficace computationnellement : Correspond au coût du SGD standard avec momentum.
• Géométriquement flexible : Se généralise naturellement aux optimiseurs normalisés et aux contextes contraints via les LMO.

Les auteurs positionnent RanSOM comme une solution unifiée pour l'optimisation non convexe moderne, en particulier dans les architectures d'apprentissage profond où les hypothèses de régularité standards échouent et où l'efficacité computationnelle est primordiale.