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

Yue Huang, Zhaoxian Wu, Shiqian Ma, Qing Ling

TL;DR

This paper provides a breakthrough in the analysis of Multi-Sequence Stochastic Approximation (MSSA), a framework used to solve complex coupled systems like bilevel optimization and distributed learning. By developing a new analytical approach, the authors prove that these systems can converge at optimal rates ($\tilde{O}(1/K)$) using a single-timescale update rule, entirely removing the restrictive and often unrealistic "fixed point smoothness" assumption required by previous theories.

What Problem Does This Paper Address?

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

Historically, analyzing MSSA faced a dilemma:

  1. Two-Timescale Analysis: One sequence is updated much slower than the other. This is easier to analyze but results in slow convergence rates.
  2. Single-Timescale Analysis: Both sequences move at the same rate. This is faster but previously required a "fixed point smoothness" assumption—essentially assuming the solution to an "inner" problem changes very smoothly as the "outer" variable changes. In many real-world problems (like those involving non-smooth loss functions), this assumption simply doesn't hold.

This paper tackles the challenge of proving fast, single-timescale convergence for MSSA without needing that smoothness assumption.

Methods

The authors establish a tighter convergence analysis for MSSA by shifting how they measure error. Instead of tracing the distance between a sequence and a time-varying fixed point (which is what necessitated the smoothness assumption), they characterize the convergence error based on an auxiliary sequence and direct characterization of the distance between sequences.

The paper analyzes two primary scenarios:

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

They apply these theoretical findings to two major applications:

  1. SOBA (Stochastic Bilevel Optimization Algorithm): They show SOBA converges without needing high-order Lipschitz continuity (smoothness).
  2. Distributed Learning: They propose a new algorithm that combines momentum acceleration with unbiased communication compression, providing the first finite-time convergence analysis for this specific combination.

Datasets

The authors validated their theories using several benchmarks:

  • MNIST: Used for a "data hyper-cleaning" task formulated as a bilevel optimization problem.
  • Fashion MNIST: Used to test a Convolutional Neural Network (CNN) in a communication-efficient distributed learning setting.
  • Synthetic Data: Used for evaluating a distributed $\ell_2$-Support Vector Machine (SVM) problem to test the algorithm's performance on strongly convex but non-smooth loss functions.

Key Insights and Ideas

  • Bypassing Smoothness: The "aha moment" is realizing that the smoothness of the fixed point is an analytical artifact, not a requirement for the algorithm to work. By changing the Lyapunov function used in the proof, the authors show that the sequences "self-correct" even if the target they are tracking moves abruptly.
  • Single-Timescale Optimality: The results show that MSSA can match the fundamental convergence rates of SSSA. This implies that coupling multiple sequences doesn't inherently slow down the system, provided the step sizes are tuned correctly.
  • Momentum + Compression: The paper provides a theoretical bridge for distributed systems that need to save bandwidth (via compression) while maintaining high speed (via momentum), showing these two techniques are mathematically compatible under the MSSA framework.

Key Results

  • Optimal Rates: For strongly monotone systems, the error scales with $1/K$ (ignoring log factors), which is the gold standard for stochastic first-order methods.
  • Bilevel Optimization: In the hyper-cleaning experiments, the single-timescale version (ST-SOBA) significantly outperformed the traditional two-timescale version (TT-SOBA) in both convergence speed and final accuracy.
  • Distributed Efficiency: The proposed momentum-compressed algorithm achieved a $O(K^{-1})$ convergence rate for the $\ell_2$-SVM task, matching the performance of much more complex distributed algorithms while requiring less memory.

Limitations and Future Work

  • Logarithmic Factors: The "tilde" in $\tilde{O}(K^{-1})$ indicates that there are still logarithmic factors ($\log K$) in the convergence rate. Future work could look at whether these can be eliminated to reach a pure $O(K^{-1})$ rate.
  • Unbiased Compression: The current analysis is limited to unbiased compressors (like random sparsification). Many popular compressors (like Top-K) are biased, and extending this smoothness-free analysis to biased/contractive compressors remains an open challenge.
  • Beyond First-Order: The paper focuses on gradient-like (first-order) updates. Exploring how these MSSA theories apply to second-order or adaptive methods (like Adam) in coupled systems is a promising next step.

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},
}

Loading related content...

Figure