Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis

1. Problem Statement

The paper addresses the finite-time convergence analysis of Two-Time-Scale Stochastic Approximation (SA) algorithms.

• Standard Setting: Traditional SA analysis assumes that both the faster and slower time-scale mappings are contractive (i.e., they shrink distances between points). Under these conditions, algorithms converge to a unique fixed point with established rates (e.g., $O(1/k)$).
• The Gap: Many critical applications (minimax optimization, Lagrangian optimization, generalized Nash equilibria) involve a slower time-scale where the mapping is non-expansive (distance-preserving or shrinking, but not strictly contracting) rather than contractive.
• The Challenge: Non-expansive mappings do not guarantee a unique fixed point (the solution set may be a manifold) and are more sensitive to noise and step-size choices. Existing finite-time bounds for contractive mappings do not apply directly, and the analysis for non-expansive settings in a two-time-scale stochastic environment was previously lacking rigorous finite-time guarantees.

The paper investigates the coupled iteration:
$$\begin{aligned} x_{k+1} &= x_k + \alpha_k (f(x_k, y_k) - x_k + M_{k+1}) \\ y_{k+1} &= y_k + \beta_k (g(x_k, y_k) - y_k + M'_{k+1}) \end{aligned}$$
Where:

• $x_k$ (fast) updates with step size $\alpha_k$ and follows a contractive mapping $f$.
• $y_k$ (slow) updates with step size $\beta_k$ and follows a non-expansive mapping $g$ (specifically $g(x^*(y), y)$).
• $M, M'$ are martingale difference noise sequences.

2. Methodology

The author develops a novel analytical framework combining techniques from contractive SA and Krasnoselskii-Mann (KM) iterations (used for non-expansive fixed points).

Key Assumptions

1. Contractivity (Fast Scale): $f(\cdot, y)$ is $\mu$-contractive. This ensures a unique fixed point $x^*(y)$ for any $y$.
2. Non-Expansiveness (Slow Scale): The mapping $h(y) = g(x^*(y), y)$ is non-expansive.
3. Lipschitz Continuity: Functions $f$ and $g$ are Lipschitz continuous.
4. Step Size Conditions:
   • $\alpha_k = O(k^{-a})$ and $\beta_k = O(k^{-b})$ with $0.5 < a < b < 1$.
   • Crucial Separation: $\beta_k / \alpha_k \to 0$ (standard two-time-scale).
   • Key Technical Constraint: $\beta_k^2 / \alpha_k^3 \leq 1$. This specific relationship is required to bound the error accumulation from the fast scale affecting the slow scale.

Analytical Techniques

• Lipschitz Tracking: Proving that the target $x^*(y_k)$ moves slowly as $y_k$ evolves, treating the movement as an additional error term for the fast scale.
• Averaged Error Sequence: To handle the martingale noise in the non-expansive slow scale, the author defines a modified iterate $z_k = y_k - U_k$, where $U_k$ is an averaged noise sequence. This allows the analysis to decouple the noise from the non-expansive operator's stability.
• Robbins-Siegmund Theorem: Used to establish almost sure boundedness of iterates.
• Recursive Bounds: Deriving recursive inequalities for the mean square error (MSE) of both scales, utilizing the specific step-size constraints to ensure summability of error terms.

3. Key Contributions

1. Finite-Time Bounds for Non-Expansive SA: The paper provides the first finite-time mean square error bounds for two-time-scale SA where the slow scale is non-expansive.
2. Convergence Rate: It establishes that the last-iterate mean square residual error for the slow scale decays at a rate of $O(k^{-1/4 + \epsilon})$, where $\epsilon > 0$ is arbitrarily small.
   • This is slower than the $O(1/k)$ rate seen in fully contractive settings, reflecting the inherent difficulty of non-expansive mappings.
3. Almost Sure Convergence: The iterates $y_k$ are proven to converge to the set of fixed points $Y^*$ with probability 1.
4. Projected Variant: The framework is extended to cases where the fast scale involves a projection onto a convex set ($P_X$). The paper shows that such projections can induce non-expansiveness in the slow scale even if the underlying map was contractive, and provides corresponding bounds.
5. Gradient Descent Extension: A variant is analyzed where the slow scale is a gradient descent operator for a smooth (potentially non-convex) function. The paper shows a bound of $O(\log(k)/k^{2/5})$ for the minimum gradient norm, matching the best-known results for non-convex settings.

4. Main Results

Theorem 2.6 (Main Result):
Under the stated assumptions, there exist constants $C_1, C_2$ such that:

• Fast Scale Error: $E[\|x_k - x^*(y_k)\|^2] \leq \frac{C_1}{(k+1)^a}$
• Slow Scale Residual: $E[\|g(x^*(y_k), y_k) - y_k\|^2] \leq \frac{C_2}{(k+1)^{1-b}}$

Optimal Rate:
By choosing $a = 0.5 + \frac{2}{3}\epsilon$ and $b = 0.75 + \epsilon$, the overall convergence rate for the slow scale residual is $O(k^{-0.25 + \epsilon})$.

• Note: Unlike contractive settings where $O(1/k)$ step sizes are optimal, non-expansive settings benefit from slower-decaying step sizes (smaller $b$), constrained by the $\beta_k^2 \leq \alpha_k^3$ requirement.

Comparison with Contractive SA:
The paper highlights that while contractive SA achieves $O(1/k)$, non-expansive SA is fundamentally limited to $O(k^{-1/4})$ under these specific step-size constraints, aligning with known lower bounds for single-time-scale non-expansive iterations.

5. Applications Demonstrated

The framework is applied to three major domains:

1. Minimax Optimization: Analysis of Two-Time-Scale Stochastic Gradient Descent Ascent (TTSGDA) for smooth strongly concave-convex problems. The slow scale (maximization) is non-expansive.
2. Linear Stochastic Approximation: Solving linear systems where the matrix governing the slow scale is negative semi-definite (non-expansive) rather than negative definite (contractive).
3. Constrained Optimization (Lagrangian): Solving constrained problems using Lagrange multipliers. The paper demonstrates that projecting the fast scale (primal variable) onto a convex set can cause the dual update (slow scale) to become non-expansive, even if the unconstrained version would be contractive.

6. Significance

• Theoretical Advancement: This work bridges a significant gap in stochastic approximation theory by providing rigorous finite-time guarantees for a class of algorithms (non-expansive two-time-scale) that are ubiquitous in modern machine learning (e.g., GANs, robust optimization) but previously lacked such analysis.
• Practical Guidance: It provides concrete step-size selection rules ($\alpha_k, \beta_k$) and convergence rates for practitioners working with minimax problems and constrained optimization, warning that standard contractive assumptions may not hold and that convergence will be slower.
• Robustness: The analysis of the projected variant is particularly valuable for distributed optimization and game theory, where constraints are inherent, and the interaction between projection and time-scales is non-trivial.

In summary, Chandak extends the theoretical toolkit for stochastic approximation to handle non-expansive mappings in a two-time-scale setting, proving that while convergence is slower than in contractive cases, it is still guaranteed with explicit, albeit conservative, finite-time bounds.