mlsanityData to 14 Oct 2026

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

arXiv 2410.13743 ↗First posted 17 Oct 2024cs.LGcited by 4

Not on the map. Why?

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.

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

49 of 70 references.

References · 49

  1. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
  2. 2017Mixed Precision Trainingcited by 1,156
  3. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  5. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  6. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 405
  7. 2018Sparsified SGD with Memorycited by 376
  8. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  9. 2018Approximation Methods for Bilevel Programmingcited by 236
  10. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 234
  11. 2016Hyperparameter optimization with approximate gradientcited by 233
  12. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
37 more
  1. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 222
  2. 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 201
  3. 2018Truncated Back-propagation for Bilevel Optimizationcited by 190
  4. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 180
  5. 2020On the Iteration Complexity of Hypergradient Computationcited by 155
  6. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  7. 2019SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentumcited by 121
  8. 2019Distributed Learning with Compressed Gradient Differencescited by 112
  9. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  10. 2019Accelerating Federated Learning via Momentum Gradient Descentcited by 76
  11. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 53
  12. 2021A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inversecited by 53
  13. 2020Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimizationcited by 51
  14. 2019Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedbackcited by 50
  15. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
  16. 2020Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressorcited by 45
  17. 2020Error Compensated Distributed SGD Can Be Acceleratedcited by 45
  18. 2022Towards understanding how momentum improves generalization in deep learningcited by 40
  19. 2023Momentum Benefits Non-IID Federated Learning Simply and Provablycited by 38
  20. 2020Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performancecited by 35
  21. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  22. 2018Multi-Level Stochastic Gradient Methods for Nested Composition Optimizationcited by 24
  23. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 24
  24. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 22
  25. 2020On Communication Compression for Distributed Optimization on Heterogeneous Datacited by 19
  26. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  27. 2019On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communicationcited by 16
  28. 2020Semi-supervised Batch Active Learning via Bilevel Optimizationcited by 16
  29. 2023Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?cited by 14
  30. 2021A Gradient Method for Multilevel Optimizationcited by 12
  31. 2023Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compressioncited by 11
  32. 2023Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learningcited by 10
  33. 2024Finite-Time Decoupled Convergence in Nonlinear Two-Time-Scale Stochastic Approximationcited by 10
  34. 2021Projection-Free Algorithm for Stochastic Bi-level Optimizationcited by 8
  35. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  36. 2021Multi Timescale Stochastic Approximation: Stability and Convergencecited by 5
  37. 2024Accelerated Multi-Time-Scale Stochastic Approximation: Optimal Complexity and Applications in Reinforcement Learning and Multi-Agent Gamescited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximationcited by 5
  2. 2025Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimizationcited by 3
  3. 2025In-memory Training on Analog Devices with Limited Conductance States via Multi-tile Residual Learningcited by 3
  4. 2026Rethinking Neural Network Learning Rates: A Stackelberg Perspectivecited by 1