Convergence Rate in a Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence

Zixi Chen, Yumin Xu, Ruixun ZhangAAAI 2025 · DOI

TL;DR

This paper analyzes the convergence rates of a two-time-scale stochastic approximation (SA) algorithm, a crucial tool for complex systems. The authors introduce novel assumptions about state- and time-dependent noise, showing that these can lead to faster convergence, even exponential rates, compared to traditional SA methods with bounded noise. This work bridges the gap between theoretical SA and practical applications where noise characteristics are more nuanced.

What Problem Does This Paper Address?

Stochastic approximation (SA) is a fundamental technique for finding solutions to problems with noisy observations, widely used in optimization and machine learning. Traditional SA methods often assume bounded noise. However, many real-world scenarios involve noise that depends on the system's current state or time. The "two-time-scale" variant of SA is designed for systems with both fast and slow dynamics, but analyzing its convergence under more realistic, non-bounded noise conditions remains a challenge. This paper addresses this gap by investigating the convergence rates of a nonlinear two-time-scale SA when the noise is dependent on the state or time.

Methods

The core of this paper lies in its theoretical analysis of convergence rates. The authors extend the standard two-time-scale SA framework by introducing state-dependent noise variances (controlled by parameters $\delta_{ij}$) and time-dependent noise variances (controlled by parameters $\gamma_i$). They leverage Lyapunov functions to analyze the convergence of the system's errors. A key contribution is the development of a linear programming function, $m(x)$, which explicitly relates the noise parameters ($\delta_{ij}$) to the convergence rate. This allows them to derive conditions under which polynomial convergence rates can be accelerated, and even achieve exponential convergence. They also analyze the impact of learning rate schedules and provide specific conditions for different noise scenarios.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments using synthetic examples.

Key Insights and Ideas

  • Noise Matters: The paper strongly emphasizes that the nature of noise (state-dependent vs. time-dependent, and its decay rate) significantly impacts convergence speed.
  • Accelerated Convergence: By allowing noise variances to decrease with state or time, the authors demonstrate that convergence rates can be substantially improved beyond the standard $O(k^{-1})$ or $O(k^{-2/3})$.
  • Exponential Convergence is Achievable: Under specific conditions, particularly when state-dependent noise parameters approach 1 ($\delta_{ij} \to 1$), the Lyapunov function can exhibit exponential convergence, mirroring the behavior of deterministic systems.
  • Bridging Theory and Practice: The work provides a theoretical framework that better reflects real-world scenarios where noise is not always bounded, offering practical implications for algorithm design.
  • Unified Framework: The introduction of parameters $\delta_{ij}$ and $\gamma_i$ provides a unified way to analyze various noise assumptions, from bounded to state/time-dependent decaying noise.

Key Results

The paper establishes that for state-dependent noise, the convergence rate of the Lyapunov function is generally $O(k^{-t})$, where $t$ is determined by the noise parameters $\delta_{ij}$. As $\delta_{ij}$ approaches 1, $t$ increases, leading to faster polynomial convergence. Crucially, when $\delta_{ij} = 1$, an exponential convergence rate of $O(e^{-ck})$ is achieved. For time-dependent noise, the convergence rate is also polynomial, $O(k^{-t})$, where $t$ depends on $\gamma_i$. Numerical experiments with SGD and stochastic bilevel optimization validate these theoretical findings, showing that as $\delta$ increases (approaching 1) or $\gamma$ increases, the convergence rate indeed improves, and exponential convergence is observed when $\delta=1$.

Limitations and Future Work

The authors acknowledge that the assumptions made for achieving exponential convergence (e.g., $\delta_{ij}=1$) might be restrictive in some practical settings. Future work could explore convergence rates under more general noise assumptions, including correlated noise or noise with different decay patterns. Additionally, extending these results to more complex SA algorithms or different problem classes would be valuable. The paper also suggests investigating the impact of learning rate schedules beyond the specific forms considered.

Summary updated

BibTeX
@inproceedings{chen2025convergence,
  author = {Zixi Chen and Yumin Xu and Ruixun Zhang},
  title = {{Convergence Rate in a Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i15.33756},
}

Loading related content...

Figure