Technical Summary: Nonlinear Two-Time-Scale Stochastic Approximation

1. Problem Statement

Two-time-scale stochastic approximation (TTSA) involves coupled recursions where a "fast" iterate $x_k$ (stepsize $\alpha_k$) tracks a moving target determined by a "slow" iterate $y_k$ (stepsize $\beta_k$), with $\beta_k \ll \alpha_k$. While linear TTSA is known to achieve a decoupled mean-square convergence rate of $O(k^{-1})$ for the slow iterate even when the fast stepsize decays as $\alpha_k = \Theta(k^{-a})$ with $a < 1$, the behavior of nonlinear TTSA is less understood.

Recent literature suggests that for nonlinear contractive TTSA, the slow iterate may be limited to a slower rate of $O(k^{-a})$ unless strong local linearity assumptions hold. The central questions addressed are:

1. Structural: What specific feature of the slow drift determines whether the slow iterate converges at the optimal decoupled rate $O(k^{-1})$ or the slower fast-tracking rate $O(k^{-a})$?
2. Algorithmic: If the slow rate is limited by nonlinear bias, can the update rule be modified to remove this bias and recover the $O(k^{-1})$ rate without requiring simulator access or oracle debiasing?

2. Methodology and Model

The authors analyze the problem using a local normal-form model that isolates the rate-determining terms from the general TTSA mechanics. Let $X_k$ denote the fast tracking error and $Y_k$ the slow error. The model is defined as:
$$\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}$$
Here:

• $H X_k$ represents the locally linear leakage of fast error into the slow recursion.
• $R(X_k)$ is the genuinely nonlinear remainder, assumed to satisfy $\|R(x)\| \leq L_R \|x\|^{1+\rho}$ for $\rho \in [0, 1]$.
• $\rho$ measures local regularity: $\rho=0$ corresponds to a Lipschitz remainder, while $\rho=1$ corresponds to a second-order (Taylor) remainder.
• Stepsizes are $\alpha_k = \Theta(k^{-a})$ and $\beta_k = \Theta(k^{-1})$ with $a \in (1/2, 1)$.

The analysis relies on non-asymptotic finite-time bounds and utilizes Abel-transform cancellations (summation by parts) to handle the convolution of errors.

3. Key Contributions and Results

A. Sharp Phase Transition for Uncorrected Recursion

The paper establishes a sharp, regularity-dependent upper bound for the mean-square error of the uncorrected slow iterate:
$$\mathbb{E}\|Y_k\|^2 \leq C \left( k^{-1} + k^{-a(1+\rho)} \right).$$
This leads to a phase transition determined by the quantity $a(1+\rho)$:

• Case 1 ($a(1+\rho) \geq 1$): The nonlinear bias decays fast enough that the slow iterate achieves the decoupled rate $O(k^{-1})$. This includes cases where $\rho=1$ (second-order remainder) for any $a > 1/2$.
• Case 2 ($a(1+\rho) < 1$): The nonlinear bias dominates, and the rate is limited to $O(k^{-a(1+\rho)})$.

Lower Bound: The authors prove a matching lower bound in a scalar Gaussian subclass where $H=0$ (no linear leakage). They show that $\mathbb{E}[Y_k^2] \geq c_1 k^{-a(1+\rho)} + c_2 k^{-1}$. This confirms that the slower rate is unavoidable for the uncorrected recursion when $a(1+\rho) < 1$ and is caused solely by the non-zero mean of the nonlinear remainder, not by imperfect averaging of linear terms.

B. Mechanism of Convergence

• Linear Leakage ($HX_k$): Despite $X_k$ having magnitude $\Theta(k^{-a/2})$, the linear term $HX_k$ does not degrade the rate. Because $X_k$ satisfies a stable recursion, $HX_k$ can be rewritten using an identity involving the martingale difference $\xi_{k+1}$ and a telescoping term. Both components average down to the $O(k^{-1})$ noise floor via Abel-transform cancellation.
• Nonlinear Remainder ($R(X_k)$): In contrast, $R(X_k)$ acts as a predictable bias (not a martingale difference). Its magnitude scales as $\mathbb{E}\|R(X_k)\| \approx k^{-a(1+\rho)/2}$. Since it is not centered, it does not average down to $O(k^{-1})$; instead, it accumulates as a slowly varying drift, limiting the convergence rate.

C. Online Bias Tracking (Beating the Lower Bound)

The paper demonstrates that the lower bound is an obstruction of the update rule, not an information-theoretic limit. The authors propose an online bias-tracking algorithm that introduces an auxiliary variable $M_k$ on an intermediate time scale $\gamma_k$ (where $\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}$$
By subtracting the running estimate $M_k$ from the slow update, the predictable bias is removed. The residual $R(X_k) - M_k$ becomes a martingale-like difference that can be handled via a second Abel-transform cancellation.
Result: The corrected recursion achieves $\mathbb{E}\|\tilde{Y}_k\|^2 = O(k^{-1})$ for all $\rho \in [0, 1]$, including regimes where the uncorrected recursion fails.

D. Localized Transfer to General Nonlinear TTSA

The authors extend these results from the normal form to general nonlinear TTSA in fast-manifold coordinates ($X_k = x_k - \lambda(y_k)$). They prove that the same phase transition mechanism holds provided:

1. The fast equilibrium manifold $\lambda(y)$ is sufficiently smooth.
2. Local Taylor expansions of the drift functions hold.
3. Localized moment estimates are satisfied.
   The transfer theorem accounts for perturbations caused by the moving manifold and shows that the phase transition persists under these conditions.

4. Significance and Claims

The paper claims to resolve a structural ambiguity in the literature regarding nonlinear TTSA convergence:

1. Refinement of Prior Work: It corrects the binary view that "local linearity is necessary for $O(k^{-1})$." Instead, it shows that sufficient regularity ($a(1+\rho) \geq 1$) is sufficient, even without strict linearity.
2. Algorithmic Solution: It proves that the $O(k^{-1})$ rate is recoverable for general nonlinear remainders without oracle access, simply by tracking the predictable bias on an intermediate time scale.
3. Sharpness: The lower bound establishes that the derived rates are minimax optimal for the class of uncorrected recursions under the given assumptions.

The work relies on non-asymptotic proofs and specific technical tools (Abel-transform cancellations) to separate the effects of linear leakage (which averages out) from nonlinear bias (which accumulates). The paper does not claim to solve global stability issues but focuses strictly on the finite-time convergence rates of the local error dynamics.