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

Technical Summary: Non-Expansive Two-Time-Scale Stochastic Approximation

Problem Statement
The paper investigates the convergence rates of two-time-scale stochastic approximation (TTSA) in a regime where the fast map is contractive, but the reduced slow map is only non-expansive. This setting arises in minimax optimization, variational inequalities, and constrained stochastic approximation. Unlike contractive TTSA, where the slow variable converges to a unique equilibrium, the non-expansive case features a potentially non-singleton fixed-point set. Consequently, the natural performance metric is the fixed-point residual $p(y) = h(y) - y$ rather than the distance to a specific point.

Prior work established a last-iterate mean-square residual rate of $O(k^{-1/4+\epsilon})$ for this regime. The paper aims to explain the theoretical origin of this $1/4$ exponent and to determine if algorithmic modifications can improve it.

Methodology and Theoretical Framework
The authors decompose the error dynamics into two distinct components: the intrinsic convergence of the non-expansive slow recursion and the leakage of fast-tracking errors into the slow oracle.

1. Sharpness of the Fixed-Schedule KM Barrier:
   The paper first establishes that the classical Krasnoselskii–Mann (KM) residual scale, defined by the inverse of the sum $\sum \beta_i(1-\beta_i)$, is sharp for any fixed slow stepsize schedule $(\beta_k)$. Using a planar rotation example, the authors prove a finite-horizon lower bound showing that no unregularized KM update can achieve a faster worst-case residual decay than this scale for a given schedule. This implies that improving the rate requires changing the algorithmic regime or oracle structure, not merely refining the analysis of the standard KM update.

2. Diagnosis of the $1/4$ Exponent:
   The paper identifies the "first-order fast-manifold leakage" as the primary obstruction. In raw TTSA, the slow oracle evaluates the map at the current fast iterate $X_k$ rather than the true equilibrium $x^*(Y_k)$. Due to the Lipschitz continuity of the slow map in the fast coordinate, the error $g(X_k, Y_k) - h(Y_k)$ is first-order in the tracking error $\|X_k - x^*(Y_k)\|$.
   The tracking error itself is governed by a balance between the fast stochastic variance ($\alpha_k$) and the deterministic lag behind the moving target ($(\beta_k/\alpha_k)^2$). Even under the standard separation condition $\beta_k^2/\alpha_k^3 \lesssim 1$, the combination of the sharp KM scale and this first-order leakage yields a total sample complexity of $T^{-1/4+o(1)}$. Violating the separation condition does not improve the rate; it merely shifts the bottleneck from statistical variance to the moving-target lag, which still enters as a first-order perturbation.

3. Bias Correction via Residual Preconditioning:
   To overcome the first-order leakage, the authors introduce a residual-preconditioned slow oracle. By utilizing the derivatives of the fast and slow maps, they construct a correction term that cancels the linear dependence on the fast tracking error.
   Specifically, if $A(y) = I - \nabla_x f(x^*(y), y)$ and $C(y) = \nabla_x g(x^*(y), y)$, the preconditioner is $P^*(y) = C(y)A(y)^{-1}$. The corrected oracle is defined as:
   $$H_{corr}(x, y) = g(x, y) + P^*(y)(f(x, y) - x)$$
   Taylor expansion shows that this correction reduces the slow oracle bias from first-order ($O(\|e\|)$) to second-order ($O(\|e\|^2)$), where $e$ is the fast tracking error.

Key Contributions and Results

The paper presents three main theoretical results, progressing from a diagnosis of the raw method to optimized algorithms under structured oracle assumptions.

1. Fixed-Schedule Lower Bound:
   The authors prove that for any fixed slow stepsize schedule, the mean-square residual of the unregularized KM iteration cannot uniformly improve upon the scale $(\sum \beta_i(1-\beta_i))^{-1}$. This confirms that the $1/4$ exponent in prior work is not an artifact of loose analysis but a consequence of the sharp KM scale combined with first-order leakage.

2. Nested Bias-Corrected Algorithm ($T^{-1/3}$):
   In a nested Tikhonov-KM framework, the authors apply the residual preconditioning.

   • Uncorrected: The nested method with a raw oracle achieves a total sample rate of $T^{-1/4+o(1)}$.
   • Corrected: By using the preconditioned oracle, the squared bias of the slow oracle becomes $O(n^{-2})$ (where $n$ is the number of inner samples) instead of $O(n^{-1})$. This structural change improves the total sample complexity to $T^{-1/3+o(1)}$.
   • Note: This result assumes access to the exact preconditioner $P^*(y)$ or an estimator satisfying specific product-accuracy conditions.

3. Single-Loop Learned Preconditioner ($T^{-1/2}$):
   To avoid the repeated cost of inner-loop solves in the nested method, the authors propose a single-loop algorithm that tracks the fast equilibrium, the slow variable, and the preconditioner matrix online.

   • This method maintains running estimates of $X_k$, $Y_k$, and $P_k$ using stochastic derivative observations.
   • Under smoothness assumptions (differentiability of maps and access to derivative oracles), this approach achieves a total sample rate of $T^{-1/2+o(1)}$ with $O(1)$ primitive samples per iteration.
   • This improvement relies on the ability to learn the leakage preconditioner online, effectively amortizing the cost of the inner solve.

Significance and Claims
The paper claims to provide a complete theoretical explanation for the $1/4$ exponent in non-expansive TTSA, attributing it to the interplay between the sharp KM residual scale and first-order fast-manifold leakage. The primary contribution is demonstrating that this barrier is not fundamental to the problem class but is specific to the "raw" oracle structure.

By introducing a residual-preconditioned oracle, the authors show that the leakage can be reduced to second order, thereby improving convergence rates. The $T^{-1/3}$ result serves as a certificate that bias correction is effective, while the $T^{-1/2}$ result demonstrates that these gains can be realized in a single-loop setting if derivative information is available. The authors explicitly frame these results as "structured-oracle" achievements, noting that they rely on differentiability and access to Jacobian-related information, distinguishing them from black-box non-expansive fixed-point methods. The work does not claim to solve the problem for general black-box oracles but rather identifies the specific structural modification (bias cancellation) required to accelerate convergence in the presence of smoothness.