Research map / Optimization / Nonconvex and smooth optimization
Convergence Rate in a Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes nonlinear two-time-scale stochastic approximation with state- or time-dependent noise variances, proving polynomial Lyapunov convergence rates that become exponential when the state-noise parameter reaches 1.
Problem
Convergence rates of nonlinear two-time-scale stochastic approximation when martingale noise variance depends on the current state residuals or on iteration time, rather than being bounded.
Approach
Allows noise variance to decay with state residuals (parameters delta_ij) or with time (parameters gamma_i), introduces a Lyapunov function V_k = c(beta/alpha)||x_hat||^2 + ||y_hat||^2, and derives a linear-programming function m(x) that links noise parameters to the polynomial rate exponent; with delta=1 the rate becomes exponential.
Key results
- Theory gives polynomial Lyapunov rate O(k^{-t}) for state-dependent noise with delta_ij in [0,1), where t is set by the linear programming function m(x); the rate is at least O(k^{-2/3}) at delta=0 and increases toward k^{-infinity} as delta approaches 1.
- With delta_ij equal to 1 and constant step sizes, E[V_k] <= e^{-eps k} V_0 (exponential convergence), verified numerically on SGD with Polyak-Ruppert averaging and stochastic bilevel optimization.
- Under time-dependent noise, the exponent t = (2+2gamma_1+gamma_2)/3 grows linearly with gamma, but exponential rate is not obtained.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use state-dependent noise with δij > 0 instead of δij = 0 | Two-time-scale SA · State-dependent noise | Lyapunov convergence rate: O(k^{-2/3}) -> O(k^{-t}) | Helped |
| Set the state-noise parameters to δij = 1 | Two-time-scale SA · State-dependent noise | Lyapunov convergence rate: O(k^{-t}) -> O(e^{-ε k}) | Helped |
| Increase the state-noise parameter δ toward 1 | SGD with Polyak-Ruppert averaging · SGD with Polyak-Ruppert averaging | Convergence rate: δ = 0.0, 0.2, 0.4, 0.6, 0.8 | Helped |
| Set the state-noise parameter to δ = 1 | SGD with Polyak-Ruppert averaging · SGD with Polyak-Ruppert averaging | Convergence rate: O(e^{-ε k}) | Helped |
| Increase the state-noise parameter δ toward 1 | Stochastic bilevel optimization · Stochastic bilevel optimization | Convergence rate: δ ∈ [0, 1) | Helped |
| Set the state-noise parameter to δ = 1 | Stochastic bilevel optimization · Stochastic bilevel optimization | Convergence rate: O(e^{-ε k}) | Helped |
| Increase the time-noise decay parameters γi | Two-time-scale SA · Time-dependent noise | Lyapunov convergence rate: t = (2+2γ1+γ2)/3 | Helped |
| Increase the time-noise parameter γ | SGD with Polyak-Ruppert averaging and stochastic bilevel optimization · Time-dependent noise | Convergence rate: γ = 0, 1, 2, 3, 4 | Helped |
| Use time-dependent noise with increasing γi | Two-time-scale SA · Time-dependent noise | Convergence rate: t → +∞; O(e^{-ε k}) | Mixed |
Surprising findings
- Under time-dependent noise the exponent grows linearly with gamma, so exponential convergence is not reached even as gamma grows, unlike the state-dependent case with delta=1.
Limitations
- Assumptions are restrictive (strong monotonicity, Lipschitz operators, overparametrized-type noise), and exponential rate requires delta_ij = 1.
- Experiments are small synthetic examples (5-dimensional SGD and a scalar-style bilevel toy problem) with Gaussian noise only.
- Step sizes require k0 and alpha, beta chosen large, with the ratio alpha/beta sufficiently large.
Experimental setup
Metrics: Lyapunov function V_k decay rate (log-log slope)
Builds on: two-time-scale stochastic approximation state-dependent noise assumptions Polyak-Ruppert averaging
Closest papers by meaning
- Continuous-time Models for Stochastic Optimization Algorithms (NeurIPS 2019 · similarity 0.90)
- Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance (NeurIPS 2021 · similarity 0.88)
- Steady-State Behavior of Constant-Stepsize Stochastic Approximation: Gaussian Approximation and Tail Bounds (ICML 2026 · similarity 0.88)
- The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations (ICML 2025 · similarity 0.88)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.