mlsanityData to 7 Oct 2026

DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization

arXiv 2202.01268 ↗First posted 2 Feb 2022cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

We develop and analyze DASHA: a new family of methods for nonconvex distributed optimization problems. When the local functions at the nodes have a finite-sum or an expectation form, our new methods, DASHA-PAGE and DASHA-SYNC-MVR, improve the theoretical oracle and communication complexity of the previous state-of-the-art method MARINA by Gorbunov et al. (2020). In particular, to achieve an epsilon-stationary point, and considering the random sparsifier RandK as an example, our methods compute the optimal number of gradients Oleft(frac√mvarepsilon√nright) and Oleft(fracσvarepsilon3/2nright) in finite-sum and expectation form cases, respectively, while maintaining the SOTA communication complexity Oleft(fracdvarepsilon √nright). Furthermore, unlike MARINA, the new methods DASHA, DASHA-PAGE and DASHA-MVR send compressed vectors only and never synchronize the nodes, which makes them more practical for federated learning. We extend our results to the case when the functions satisfy the Polyak-Lojasiewicz condition. Finally, our theory is corroborated in practice: we see a significant improvement in experiments with nonconvex classification and training of deep learning models.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 33 of its 40 references that are in the map. First posted on arXiv 2 Feb 2022.

Builds on

33 of 40 references.

References · 33

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  4. 2021Zero-Shot Text-to-Image Generationcited by 4,276
  5. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  6. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  7. 2017Deep Learning Scaling is Predictable, Empiricallycited by 556
  8. 2021A Field Guide to Federated Optimizationcited by 312
  9. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  10. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  11. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  12. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 159
21 more
  1. 2021A Universal Law of Robustness via Isoperimetrycited by 150
  2. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  3. 2020On Biased Compression for Distributed Learningcited by 140
  4. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  5. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  6. 2019Distributed Learning with Compressed Gradient Differencescited by 110
  7. 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
  8. 2019Natural Compression for Distributed Deep Learningcited by 88
  9. 2013Distributed optimization over time-varying directed graphscited by 77
  10. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
  11. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
  12. 2021STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learningcited by 43
  13. 2021RelaySum for Decentralized Deep Learning on Heterogeneous Datacited by 39
  14. 2021Permutation Compressors for Provably Faster Distributed Nonconvex Optimizationcited by 32
  15. 2020Recent Theoretical Advances in Non-Convex Optimizationcited by 30
  16. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 30
  17. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 28
  18. 2019A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimizationcited by 27
  19. 2020An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimizationcited by 9
  20. 2019Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexitycited by 8
  21. 2020Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reductioncited by 3

Built on by

Cited by year

Citing papers per year: 2022: 5; 2023: 5; 2024: 3; 2025: 2.

15 papers.

Sort:

  1. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  2. 2023Momentum Provably Improves Error Feedback!cited by 31
  3. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  4. 2022Anchor Sampling for Federated Learning with Partial Client Participationcited by 14
  5. 2023Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Ratescited by 12
  6. 2022Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregationcited by 11
  7. 2023Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compressioncited by 11
  8. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  9. 2022Communication-Efficient Federated Learning With Data and Client Heterogeneitycited by 9
  10. 2024Queuing dynamics of asynchronous Federated Learningcited by 6
  11. 2025Optimizing Asynchronous Federated Learning: A Delicate Trade-Off Between Model-Parameter Staleness and Update Frequencycited by 2
  12. 2023FAVANO: Federated AVeraging with Asynchronous NOdescited by 1
3 more
  1. 2023CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexitycited by 1
  2. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 1
  3. 2025Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Constructioncited by 0