Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

Résumé Technique : Approximation Stochastique à Deux Échelles de Temps Non-Expansive

Énoncé du Problème
L'article étudie les taux de convergence de l'approximation stochastique à deux échelles de temps (TTSA) dans un régime où la carte rapide est contractive, mais où la carte lente réduite est seulement non-expansive. Ce cadre apparaît dans l'optimisation minimax, les inégalités variationnelles et l'approximation stochastique contrainte. Contrairement à la TTSA contractive, où la variable lente converge vers un équilibre unique, le cas non-expansif présente un ensemble de points fixes potentiellement non-singleton. Par conséquent, la métrique de performance naturelle est le résidu du point fixe $p(y) = h(y) - y$ plutôt que la distance par rapport à un point spécifique.

Des travaux antérieurs ont établi un taux de résidu de carré moyen du dernier itéré de $O(k^{-1/4+\epsilon})$ pour ce régime. L'article vise à expliquer l'origine théorique de cet exposant $1/4$ et à déterminer si des modifications algorithmiques peuvent l'améliorer.

Méthodologie et Cadre Théorique
Les auteurs décomposent la dynamique d'erreur en deux composantes distinctes : la convergence intrinsèque de la récursion lente non-expansive et la fuite des erreurs de suivi rapide dans l'oracle lent.

1. L'acuité de la barrière du calendrier KM (Krasnoselskii–Mann) :
   L'article établit d'abord que l'échelle de résidu classique de Krasnoselskii–Mann (KM), définie par l'inverse de la somme $\sum \beta_i(1-\beta_i)$, est aiguë pour tout calendrier de pas de la variable lente $(\beta_k)$ fixé. En utilisant un exemple de rotation planaire, les auteurs prouvent une borne inférieure d'horizon fini montrant qu'aucune mise à jour KM non régularisée ne peut atteindre un taux de décroissance du résidu pire cas plus rapide que cette échelle pour un calendrier donné. Cela implique que l'amélioration du taux nécessite de changer le régime algorithmique ou la structure de l'oracle, et non simplement d'affiner l'analyse de la mise à jour KM standard.

2. Diagnostic de l'exposant $1/4$ :
   L'article identifie la « fuite de premier ordre de la variété rapide » comme l'obstacle principal. Dans la TTSA brute, l'oracle lent évalue la carte à l'itération rapide actuelle $X_k$ plutôt qu'à l'équilibre véritable $x^*(Y_k)$. En raison de la continuité lipschitzienne de la carte lente dans la coordonnée rapide, l'erreur $g(X_k, Y_k) - h(Y_k)$ est du premier ordre par rapport à l'erreur de suivi $\|X_k - x^*(Y_k)\|$. L'erreur de suivi elle-même est gouvernée par un équilibre entre la variance stochastique rapide ($\alpha_k$) et le retard déterministe derrière la cible mobile ($(\beta_k/\alpha_k)^2$). Même sous la condition de séparation standard $\beta_k^2/\alpha_k^3 \lesssim 1$, la combinaison de l'échelle KM aiguë et de cette fuite de premier ordre produit un échantillonnage total de $T^{-1/4+o(1)}$. Violer la condition de séparation n'améliore pas le taux ; cela déplace simplement le goulot d'étranglement de la variance statistique vers le retard de la cible mobile, qui entre toujours comme une perturbation de premier ordre.

3. Correction de Biais par Préconditionnement du Résidu :
   Pour surmonter cette fuite de premier ordre, les auteurs introduisent un oracle lent préconditionné par le résidu. En utilisant les dérivées des cartes rapide et lente, ils construisent un terme de correction qui annule la dépendance linéaire vis-à-vis de l'erreur de suivi rapide.
   Spécifiquement, si $A(y) = I - \nabla_x f(x^*(y), y)$ et $C(y) = \nabla_x g(x^*(y), y)$, le préconditionneur est $P^*(y) = C(y)A(y)^{-1}$. L'oracle corrigé est défini par :
   $$H_{corr}(x, y) = g(x, y) + P^*(y)(f(x, y) - x)$$
   Le développement de Taylor montre que cette correction réduit le biais de l'oracle lent de premier ordre ($O(\|e\|$) à second ordre ($O(\|e\|^2)$), où $e$ est l'erreur de suivi rapide.

Contributions Clés et Résultats

L'article présente trois résultats théoriques principaux, progressant d'un diagnostic de la méthode brute vers des algorithmes optimisés sous des hypothèses d'oracles structurés.

1. Borne Inférieure pour Calendrier Fixe :
   Les auteurs prouvent que pour tout calendrier de pas de la variable lente fixé, le carré moyen du résidu d'une itération KM non régularisée ne peut pas améliorer uniformément l'échelle $(\sum \beta_i(1-\beta_i))^{-1}$. Cela confirme que l'exposant $1/4$ dans les travaux antérieurs n'est pas un artefact d'une analyse lâche, mais une conséquence de l'échelle KM aiguë combinée à la fuite de premier ordre.

2. Algorithme à Emboîtement avec Correction de Biais ($T^{-1/3}$) :
   Dans un cadre Tikhonov-KM imbriqué, les auteurs appliquent le préconditionnement du résidu.

• Non corrigé : La méthode imbriquée avec un oracle brut atteint un taux d'échantillonnage total de $T^{-1/4+o(1)}$.
• Corrigé : En utilisant l'oracle préconditionné, le biais au carré de l'oracle lent devient $O(n^{-2})$ (où $n$ est le nombre d'échantillons internes) au lieu de $O(n^{-1})$. Ce changement structurel améliore la complexité totale de l'échantillonnage à $T^{-1/3+o(1)}$.
• Note : Ce résultat suppose l'accès au préconditionneur exact $P^*(y)$ ou à un estimateur satisfaisant des conditions de précision de produit spécifiques.

3. Préconditionneur Appris en Boucle Unique ($T^{-1/2}$) :
   Pour éviter le coût répété des résolutions de boucle interne de la méthode imbriquée, les auteurs proposent un algorithme à boucle unique qui suit l'équilibre rapide, la variable lente et la matrice de préconditionnement en ligne.

• Cette méthode maintient des estimations courantes de $X_k$, $Y_k$ et $P_k$ en utilisant des observations de dérivées stochastiques.
• Sous des hypothèses de régularité (dérivabilité des cartes et accès à des oracles de dérivées), cette approche atteint un taux d'échantillonnage total de $T^{-1/2+o(1)}$ avec $O(1)$ échantillons primitifs par itération.
• Cette amélioration repose sur la capacité à apprendre le préconditionneur de fuite en ligne, amortissant ainsi efficacement le coût de la résolution interne.

Signification et Revendications
L'article affirme fournir une explication théorique complète de l'exposant $1/4$ dans la TTSA non-expansive, l'attribuant à l'interaction entre l'échelle de résidu KM aiguë et la fuite de premier ordre de la variété rapide. La contribution principale est de démontrer que cette barrière n'est pas fondamentale à la classe de problèmes, mais spécifique à la structure de l'oracle « brut ».

En introduisant un oracle préconditionné par le résidu, les auteurs montrent que la fuite peut être réduite au second ordre, améliorant ainsi les taux de convergence. Le résultat en $T^{-1/3}$ sert de certificat de l'efficacité de la correction de biais, tandis que le résultat en $T^{-1/2}$ démontre que ces gains peuvent être réalisés dans un cadre à boucle unique si l'information de dérivée est disponible. Les auteurs présentent explicitement ces résultats comme des accomplissements de type « oracle structuré », notant qu'ils reposent sur la dérivabilité et l'accès à l'information de Jacobienne, ce qui les distingue des méthodes de point fixe non-expansif de type boîte noire. Le travail ne prétend pas résoudre le problème pour des oracles boîte noire généraux, mais identifie la modification structurelle spécifique (annulation du biais) requise pour accélérer la convergence en présence de régularité.