Résumé Technique : Approximation Stochastique Non Linéaire à Deux Échelles de Temps

1. Énoncé du Problème

L'approximation stochastique à deux échelles de temps (TTSA pour Two-Time-Scale Stochastic Approximation) implique des récursions couplées où une itérée « rapide » $x_k$ (pas de $\alpha_k$) suit une cible mouvante déterminée par une itérée « lente » $y_k$ (pas de $\beta_k$), avec $\beta_k \ll \alpha_k$. Alors que la TTSA linéaire est connue pour atteindre un taux de convergence au sens de la moyenne quadratique décorrélé de $O(k^{-1})$ pour l'itérée lente, même lorsque le pas rapide décroît selon $\alpha_k = \Theta(k^{-a})$ avec $a < 1$, le comportement de la TTSA non linéaire est moins bien compris.

La littérature récente suggère que pour une TTSA contractive non linéaire, l'itérée lente peut être limitée à un taux plus lent de $O(k^{-a})$, à moins que des hypothèses de linéarité locale fortes ne soient satisfaites. Les questions centrales abordées sont :

1. Structurelle : Quelle caractéristique spécifique de la dérive lente détermine si l'itérée lente converge au taux décorrélé optimal $O(k^{-1})$ ou au taux plus lent de suivi rapide $O(k^{-a})$ ?
2. Algorithmique : Si le taux lent est limité par un biais non linéaire, la règle de mise à jour peut-elle être modifiée pour supprimer ce biais et récupérer le taux $O(k^{-1})$ sans nécessiter d'accès à un simulateur ou à un oracle de débaisage ?

2. Méthodologie et Modèle

Les auteurs analysent le problème en utilisant un modèle de forme normale locale qui isole les termes déterminants du taux des mécanismes généraux de la TTSA. Soient $X_k$ l'erreur de suivi rapide et $Y_k$ l'erreur lente. Le modèle est défini par :
$$\begin{aligned} X_{k+1} &= (I - \alpha_k A)X_k + \alpha_k \xi_{k+1}, \\ Y_{k+1} &= (I - \beta_k B)Y_k + \beta_k \left( H X_k + R(X_k) + \zeta_{k+1} \right). \end{aligned}$$
Où :

• $H X_k$ représente la fuite linéaire locale de l'erreur rapide dans la récursion lente.
• $R(X_k)$ est le reste véritablement non linéaire, supposé satisfaire $\|R(x)\| \leq L_R \|x\|^{1+\rho}$ pour $\rho \in [0, 1]$.
• $\rho$ mesure la régularité locale : $\rho=0$ correspond à un reste Lipschitz, tandis que $\rho=1$ correspond à un reste de second ordre (Taylor).
• Les pas de $\alpha_k = \Theta(k^{-a})$ et $\beta_k = \Theta(k^{-1})$ avec $a \in (1/2, 1)$.

L'analyse repose sur des bornes non asymptotiques en temps fini et utilise des annulations de transformées d'Abel (sommation par parties) pour traiter la convolution des erreurs.

3. Contributions Clés et Résultats

A. Transition de Phase Précise pour la Récursion Non Corrigée

L'article établit une borne supérieure précise, dépendante de la régularité, pour l'erreur de moyenne quadratique de l'itérée lente non corrigée :
$$\mathbb{E}\|Y_k\|^2 \leq C \left( k^{-1} + k^{-a(1+\rho)} \right).$$
Ceci conduit à une transition de phase déterminée par la quantité $a(1+\rho)$ :

• Cas 1 ($a(1+\rho) \geq 1$) : Le biais non linéaire décroît suffisamment vite pour que l'itérée lente atteigne le taux décorrélé $O(k^{-1})$. Cela inclut les cas où $\rho=1$ (reste de second ordre) pour tout $a > 1/2$.
• Cas 2 ($a(1+\rho) < 1$) : Le biais non linéaire domine, et le taux est limité à $O(k^{-a(1+\rho)})$.

Borne Inférieure : Les auteurs prouvent une borne inférieure correspondante dans une sous-classe gaussienne scalaire où $H=0$ (pas de fuite linéaire). Ils montrent que $\mathbb{E}[Y_k^2] \geq c_1 k^{-a(1+\rho)} + c_2 k^{-1}$. Cela confirme que le taux plus lent est inévitable pour la récursion non corrigée quand $a(1+\rho) < 1$ et qu'il est causé uniquement par la moyenne non nulle du reste non linéaire, et non par un moyennage imparfait des termes linéaires.

B. Mécanisme de Convergence

• Fuite Linéaire ($HX_k$) : Bien que $X_k$ ait une magnitude de $\Theta(k^{-a/2})$, le terme linéaire $HX_k$ ne dégrade pas le taux. Comme $X_k$ satisfait une récursion stable, $HX_k$ peut être réécrit en utilisant une identité impliquant la différence de martingale $\xi_{k+1}$ et un terme de télescopage. Les deux composantes se moyennent vers le plancher de bruit $O(k^{-1})$ via une annulation de transformée d'Abel.
• Reste Non Linéaire ($R(X_k)$) : En revanche, $R(X_k)$ agit comme un biais prévisible (et non une différence de martingale). Sa magnitude suit $\mathbb{E}\|R(X_k)\| \approx k^{-a(1+\rho)/2}$. Comme il n'est pas centré, il ne se moyenne pas vers $O(k^{-1})$; au contraire, il s'accumule comme une dérive variant lentement, limitant ainsi le taux de convergence.

C. Suivi de Biais en Ligne (Battre la Borne Inférieure)

L'article démontre que la borne inférieure est une obstruction de la règle de mise à jour, et non une limite d'information théorique. Les auteurs proposent un algorithme de suivi de biais en ligne qui introduit une variable auxiliaire $M_k$ sur une échelle de temps intermédiaire $\gamma_k$ (où $\beta_k \ll \gamma_k \ll \alpha_k$) :
$$\begin{aligned} M_{k+1} &= M_k + \gamma_k (R(X_k) - M_k), \\ \tilde{Y}_{k+1} &= (I - \beta_k B)\tilde{Y}_k + \beta_k (H X_k + R(X_k) - M_k + \zeta_{k+1}). \end{aligned}$$
En soustrayant l'estimation courante $M_k$ de la mise à jour lente, le biais prévisible est éliminé. Le résidu $R(X_k) - M_k$ devient une différence de type martingale qui peut être traitée via une seconde annulation de transformée d'Abel.
Résultat : La récursion corrigée atteint $\mathbb{E}\|\tilde{Y}_k\|^2 = O(k^{-1})$ pour tous $\rho \in [0, 1]$, y compris dans les régimes où la récursion non corrigée échoue.

D. Transfert Localisé vers la TTSA Non Linéaire Générale

Les auteurs étendent ces résultats de la forme normale à la TTSA non linéaire générale dans les coordonnées de la variété rapide ($X_k = x_k - \lambda(y_k)$). Ils prouvent que le même mécanisme de transition de phase s'applique, à condition que :

1. La variété d'équilibre rapide $\lambda(y)$ soit suffisamment lisse.
2. Des développements de Taylor locaux des fonctions de dérive tiennent.
3. Des estimations de moments localisées soient satisfaites.
   Le théorème de transfert prend en compte les perturbations causées par la variété mouvante et montre que la transition de phase persiste sous ces conditions.

4. Signification et Revendications

L'article prétend résoudre une ambiguïté structurelle dans la littérature concernant la convergence de la TTSA non linéaire :

1. Affinement des travaux antérieurs : Il corrige la vision binaire selon laquelle « la linéarité locale est nécessaire pour $O(k^{-1})$ ». Au lieu de cela, il montre que la régularité suffisante ($a(1+\rho) \geq 1$) est suffisante, même sans linéarité stricte.
2. Solution Algorithmique : Il prouve que le taux $O(k^{-1})$ est récupérable pour des restes non linéaires généraux sans accès à un oracle, simplement en suivant le biais prévisible sur une échelle de temps intermédiaire.
3. Précision (Sharpness) : La borne inférieure établit que les taux dérivés sont minimax optimaux pour la classe des récursions non corrigées sous les hypothèses données.

Le travail repose sur des preuves non asymptotiques et des outils techniques spécifiques (annulations de transformées d'Abel) pour séparer les effets de la fuite linéaire (qui se moyennent) de la dérive du biais non linéaire (qui s'accumule). L'article ne prétend pas résoudre les problèmes de stabilité globale mais se concentre strictement sur les taux de convergence en temps fini de la dynamique d'erreur locale.