Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications

Yue Huang, Zhaoxian Wu, Shiqian Ma, Qing Ling

Abstract

Stochastic approximation (SA) that involves multiple coupled sequences, known as multiple-sequence SA (MSSA), finds diverse applications in the fields of signal processing and machine learning. However, existing theoretical understandings of MSSA are limited: the multi-timescale analysis implies a slow convergence rate, whereas the single-timescale analysis relies on a stringent fixed point smoothness assumption. This paper establishes tighter single-timescale analysis for MSSA, without assuming smoothness of the fixed points. Our theoretical findings reveal that, when all involved operators are strongly monotone, MSSA converges at a rate of $\tilde{\mathcal{O}}(K^{-1})$, where $K$ denotes the total number of iterations. In addition, when all involved operators are strongly monotone except for the main one, MSSA converges at a rate of $\mathcal{O}(K^{-\frac{1}{2}})$. These theoretical findings align with those established for single-sequence SA. Applying these theoretical findings to bilevel optimization and communication-efficient distributed learning offers relaxed assumptions and/or simpler algorithms with performance guarantees, as validated by numerical experiments.

Introduction

Stochastic Approximation (SA) is a fundamental tool for finding the roots of operators when only noisy data—such as gradients in machine learning—is available. While Single-Sequence SA (SSSA) is well-understood, many modern applications involve Multi-Sequence SA (MSSA), where several sequences are updated simultaneously and depend on one another. Examples include bilevel optimization, reinforcement learning, and momentum-accelerated distributed learning.

Historically, analyzing MSSA faced a dilemma. Two-timescale analysis, where one sequence is updated much slower than the other, is easier to analyze but results in slow convergence rates. Conversely, single-timescale analysis, where sequences move at the same rate, is faster but previously required a "fixed point smoothness" assumption. This assumption requires the solution to an "inner" problem to change very smoothly as the "outer" variable changes, a condition that often fails in real-world problems involving non-smooth loss functions.

Theoretical Framework and Contributions

This paper establishes a tighter convergence analysis for MSSA by shifting the analytical focus. Instead of tracing the distance between a sequence and a time-varying fixed point (which necessitated the smoothness assumption), the authors characterize the convergence error based on an auxiliary sequence and a direct characterization of the distance between sequences. This allows the sequences to "self-correct" even if the target they are tracking moves abruptly.

Comparison of convergence rates and assumptions across different MSSA frameworks. The proposed method achieves near-optimal rates without requiring fixed point smoothness.

The paper analyzes two primary scenarios:

  • Strongly Monotone Operators: Where all coupled operators are well-behaved, achieving a rate of $\tilde{O}(K^{-1})$.
  • Non-Strongly Monotone Main Operator: A relaxed setting common in actor-critic methods, achieving a rate of $O(K^{-1/2})$.

These results show that MSSA can match the fundamental convergence rates of SSSA, implying that coupling multiple sequences does not inherently slow down the system if step sizes are tuned correctly.

Empirical Results and Applications

The theoretical findings were applied to two major domains: the Stochastic Bilevel Optimization Algorithm (SOBA) and communication-efficient distributed learning.

In hyper-cleaning experiments using the MNIST dataset, the single-timescale version (ST-SOBA) significantly outperformed the traditional two-timescale version (TT-SOBA) in both convergence speed and final accuracy. The empirical results validate that the single-timescale approach maintains high performance even without high-order Lipschitz continuity.

Validation loss over iterations for Linear Regression and Two-layer MLP tasks, comparing ST-SOBA against TT-SOBA and other baselines.

Additionally, the authors proposed a new algorithm for distributed learning that combines momentum acceleration with unbiased communication compression. This algorithm achieved a $O(K^{-1})$ convergence rate for $\ell_2$-SVM tasks on Fashion MNIST, providing the first finite-time convergence analysis for this specific combination and matching the performance of more complex algorithms with lower memory requirements.

Conclusion

By removing the restrictive fixed point smoothness assumption, this work provides a more realistic theoretical foundation for Multi-Sequence Stochastic Approximation. The results demonstrate that single-timescale updates can achieve optimal convergence rates in complex coupled systems. Future research will explore eliminating logarithmic factors from the $\tilde{O}(K^{-1})$ rate and extending this smoothness-free analysis to biased or contractive compressors commonly used in distributed systems.

Summary updated

Abstract

Stochastic approximation (SA) that involves multiple coupled sequences, known as multiple-sequence SA (MSSA), finds diverse applications in the fields of signal processing and machine learning. However, existing theoretical understandings {of} MSSA are limited: the multi-timescale analysis implies a slow convergence rate, whereas the single-timescale analysis relies on a stringent fixed point smoothness assumption. This paper establishes tighter single-timescale analysis for MSSA, without assuming smoothness of the fixed points. Our theoretical findings reveal that, when all involved operators are strongly monotone, MSSA converges at a rate of $\tilde{\mathcal{O}}(K^{-1})$, where $K$ denotes the total number of iterations. In addition, when all involved operators are strongly monotone except for the main one, MSSA converges at a rate of $\mathcal{O}(K^{-\frac{1}{2}})$. These theoretical findings align with those established for single-sequence SA. Applying these theoretical findings to bilevel optimization and communication-efficient distributed learning offers relaxed assumptions and/or simpler algorithms with performance guarantees, as validated by numerical experiments.
BibTeX
@article{huang2025single,
  author = {Yue Huang and Zhaoxian Wu and Shiqian Ma and Qing Ling},
  title = {{Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications}},
  journal = {IEEE Trans. Signal Process.},
  year = {2025},
  doi = {10.1109/tsp.2025.3569665},
}
Figure