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

arXiv: https://arxiv.org/abs/2410.13743 · HTML: https://mlsanity.com/paper/2410.13743/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 70 references that are in the map.
- First posted on arXiv 17 Oct 2024.

## Builds on (most cited first, 30 of 49)

- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Mixed Precision Training](https://mlsanity.com/paper/1710.03740/) (2017)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum](https://mlsanity.com/paper/1910.00643/) (2019)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [Accelerating Federated Learning via Momentum Gradient Descent](https://mlsanity.com/paper/1910.03197/) (2019)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse](https://mlsanity.com/paper/2112.04660/) (2021)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback](https://mlsanity.com/paper/1905.10936/) (2019)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor](https://mlsanity.com/paper/2002.08958/) (2020)
- [Error Compensated Distributed SGD Can Be Accelerated](https://mlsanity.com/paper/2010.00091/) (2020)
- [Towards understanding how momentum improves generalization in deep learning](https://mlsanity.com/paper/2207.05931/) (2022)

## Built on by (most cited first, 4 of 4)

- [O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2504.19375/) (2025)
- [Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization](https://mlsanity.com/paper/2505.02101/) (2025)
- [In-memory Training on Analog Devices with Limited Conductance States via Multi-tile Residual Learning](https://mlsanity.com/paper/2510.02516/) (2025)
- [Rethinking Neural Network Learning Rates: A Stackelberg Perspective](https://mlsanity.com/paper/2605.15530/) (2026)

## Abstract (arXiv)

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 tildeO(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 O(K^-frac12). 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.