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

Technische Samenvatting: Niet-expansieve Two-Time-Scale Stochastische Approximatie

Probleemstelling
Het artikel onderzoekt de convergentiesnelheden van two-time-scale stochastische approximatie (TTSA) in een regime waarin de snelle kaart contractief is, maar de gereduceerde trage kaart slechts niet-expansief. Deze setting komt voor in minimax-optimalisatie, variatietische ongelijkheden en geconstrueerde stochastische approximatie. In tegen tegenstelling tot contractieve TTSA, waarbij de trage variabele convergeert naar een uniek evenwicht, kenmerkt het niet-expansieve geval zich door een potentieel niet-enkelvoudige vaste-puntverzameling. Bijgevolg is de natuurlijke prestatie-indicator de vaste-punt-residue $p(y) = h(y) - y$ in plaats van de afstand tot een specif specifieke punt.

Eerder werk heeft een last-iterate gemiddelde kwadratische residue-snelheid van $O(k^{-1/4+\epsilon})$ vastgesteld voor dit regime. Het artikel beoogt de theoretische oorsprong van deze $1/4$-exponent te verklaren en te bepalen of algoritmische modificaties dit kunnen verbeteren.

Methodologie en Theoretisch Kader
De auteurs ontleden de foutdynamica in twee afzonderlijke componenten: de intrinsieke convergentie van de niet-expansieve trage recursie en de lekkage van snelle tracking-fouten in de trage oracle.

1. Scherpte van de Fixed-Schedule KM-barrière:
   Het artikel stelt eerst vast dat de klassieke Krasnoselskii–Mann (KM) residue-schaal, gedefinieerd door de inverse van de som $\sum \beta_i(1-\beta_i)$, scherp is voor elke vaste trage stapgrootte-schema $(\beta_k)$. Met behulp van een planaire rotatie-voorbeeld bewijzen de auteurs een eindige-horizon ondergrens die aantoont dat geen enkele ongecorrigeerde KM-update een snellere worst-case residue-decay kan bereiken dan deze schaal voor een gegeven schema. Dit impliceert dat het verbeteren van de snelheid vereist dat men het algoritmische regime of de oracle-structuur verandert, en niet louter de analyse van de standaard KM-update verfijnt.

2. Diagnose van de $1/4$ Exponent:
   Het artikel identificeert "first-order fast-manifold leakage" als de primaire obstructie. In rauwe TTSA evalueert de trage oracle de kaart op de huidige snelle iteratie $X_k$ in plaats van op het ware evenwicht $x^*(Y_k)$. Vanwege de Lipschitz-continuïteit van de trage kaart in de snelle coördinaat, is de fout $g(X_k, Y_k) - h(Y_k)$ van de eerste orde in de tracking-fout $\|X_k - x^*(Y_k)\|$. De tracking-fout zelf wordt beheerst door een balans tussen de snelle stochastische variantie ($\alpha_k$) en de deterministische achterstand achter het bewegende doelwit ($(\beta_k/\alpha_k)^2$). Zelfs onder de standaard scheidingsvoorwaarde $\beta_k^2/\alpha_k^3 \lesssim 1$, levert de combinatie van de scherpe KM-schaal en deze first-order leakage een totale steekproefcomplexiteit van $T^{-1/4+o(1)}$. Het schenden van de scheidingsvoorwaarde verbetert de snelheid niet; het verschuift enkel de bottleneck van stochastische variantie naar de achterstand van het bewegende doelwit, die nog steeds als een first-order perturbatie optreedt.

3. Bias-correctie via Residue-Preconditionering:
   Om deze first-order leakage te overwinnen, introduceren de auteurs een residue-gepreconditioneerde trage oracle. Door gebruik te maken van de afgeleiden van de snelle en trage kaarten, construeren zij een correctieterm die de lineaire afhankelijkheid van de snelle tracking-fout wegcijfert.
   Specifiek, als $A(y) = I - \nabla_x f(x^*(y), y)$ en $C(y) = \nabla_x g(x^*(y), y)$, dan is de preconditioner $P^*(y) = C(y)A(y)^{-1}$. De gecorrigeerde oracle wordt gedefinieerd als:
   $$H_{corr}(x, y) = g(x, y) + P^*(y)(f(x, y) - x)$$
   Taylor-expansie toont aan dat deze correctie de bias van de trage oracle reduceert van first-order ($O(\|e\|)$) naar second-order ($O(\|e\|^2)$), waarbij $e$ de snelle tracking-fout is.

Belangrijkste Bijdragen en Resultaten

Het artikel presenteert drie belangrijke theoretische resultaten, die progresseren van de diagnose van de ruwe methode naar geoptimaliseerde algoritmen onder gestructureerde oracle-aannames.

1. Fixed-Schedule Ondergrens:
   De auteurs bewijzen dat voor elk vast trage stapgrootte-schema, de gemiddelde kwadratische residue van de ongecorrigeerde KM-iteratie niet uniform kan verbeteren boven de schaal $(\sum \beta_i(1-\beta_i))^{-1}$. Dit bevestigt dat de $1/4$ exponent in eerder werk geen artefact is van een losse analyse, maar een gevolg is van de scherpe KM-schaal gecombineerd met first-order leakage.

2. Nested Bias-Corrected Algoritme ($T^{-1/3}$):
   In een geneste Tikhonov-KM framework passen de auteurs de residue-preconditionering toe.

• Ongecorrigeerd: De geneste methode met een rauwe oracle bereikt een totale steekproefsnelheid van $T^{-1/4+o(1)}$.
• Gecorrigeerd: Door de gepreconditioneerde oracle te gebruiken, wordt de gekwadrateerde bias van de trage oracle $O(n^{-2})$ (waarbij $n$ het aantal binnenste steekproeven is) in plaats van $O(n^{-1})$. Deze structurele verandering verbetert de totale steekproefcomplexiteit naar $T^{-1/3+o(1)}$.
• Noot: Dit resultaat gaat uit van toegang tot de exacte preconditioner $P^*(y)$ of een estimator die voldoet aan specifieke product-nauwkeurigheidscondities.

3. Single-Loop Learned Preconditioner ($T^{-1/2}$):
   Om de herhaalde kosten van binnenste loops te vermijden, stellen de auteurs een single-loop algoritme voor dat het snelle evenwicht, de trage variabele en de preconditioner-matrix online bijhoudt.

• Deze methode houdt lopende schattingen bij van $X_k$, $Y_k$, en $P_k$ met behulp van stochastische afgeleide-observaties.
• Onder aannames van gladheid (differentieerbaarheid van de kaarten en toegang tot afgeleide-oracles), bereikt deze aanpak een totale steekproefsnelheid van $T^{-1/2+o(1)}$ met $O(1)$ primitieve steekproeven per iteratie.
• Deze verbetering berust op het vermogen om de leakage-preconditioner online te leren, waardoor de kosten van de binnenste solve effectief worden geamortiseerd.

Betekenis en Claims
Het artikel claimt een volledige theoretische verklaring te bieden voor de $1/4$ exponent in niet-expansieve TTSA, door deze toe te schrijven aan de interactie tussen de scherpe KM-residue-schaal en first-order fast-manifold leakage. De primaire bijdrage is het aantonen dat deze barrière niet fundamenteel is voor de gehele probleemklasse, maar specifiek is voor de "rauwe" oracle-structuur.

Door een residue-gepreconditioneerde oracle te introduceren, tonen de auteurs aan dat de leakage kan worden gereduceerd tot tweede orde, wat de convergentiesnelheden versnelt. Het $T^{-1/3}$ resultaat dient als een certificaat dat bias-correctie effectief is, terwijl het $T^{-1/2}$ resultaat aantoont dat deze winsten gerealiseerd kunnen worden in een single-loop setting indien afgeleide-informatie beschikbaar is. De auteurs kaderen deze resultaten expliciet als "gestructureerde-oracle" prestaties, waarbij zij benadrukken dat zij rusten op differentieerbaarheid en toegang tot Jacobian-gerelateerde informatie, wat hen onderscheidt van black-box niet-expansieve vaste-punt methoden. Het werk claimt niet het probleem voor algemene black-box oracles op te lossen, maar identificeert de specifieke structurele modificatie (bias-annulatie) die vereist is om convergentie te versnellen in aanwezigheid van gladheid.