mlsanityData to 7 Oct 2026

MARINA: Faster Non-Convex Distributed Learning with Compression

arXiv 2102.07845 ↗First posted 15 Feb 2021cs.LG math.OCcited by 77

Not on the map. Why?

Abstract (arXiv)

We develop and analyze MARINA: a new communication efficient method for non-convex distributed learning over heterogeneous datasets. MARINA employs a novel communication compression strategy based on the compression of gradient differences that is reminiscent of but different from the strategy employed in the DIANA method of Mishchenko et al. (2019). Unlike virtually all competing distributed first-order methods, including DIANA, ours is based on a carefully designed biased gradient estimator, which is the key to its superior theoretical and practical performance. The communication complexity bounds we prove for MARINA are evidently better than those of all previous first-order methods. Further, we develop and analyze two variants of MARINA: VR-MARINA and PP-MARINA. The first method is designed for the case when the local loss functions owned by clients are either of a finite sum or of an expectation form, and the second method allows for a partial participation of clients -- a feature important in federated learning. All our methods are superior to previous state-of-the-art methods in terms of oracle/communication complexity. Finally, we provide a convergence analysis of all methods for problems satisfying the Polyak-Lojasiewicz condition.

Key facts. Cited by 77 papers in the map (data through 7 Oct 2026). Builds on 32 of its 46 references that are in the map. First posted on arXiv 15 Feb 2021.

Builds on

32 of 46 references.

References · 32

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  3. 2019Advances and Open Problems in Federated Learningcited by 3,021
  4. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  5. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  6. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 671
  7. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  8. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  9. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  10. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  11. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  12. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 179
20 more
  1. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 159
  2. 2020On Biased Compression for Distributed Learningcited by 140
  3. 2016Distributed Mean Estimation with Limited Communicationcited by 134
  4. 2017Lower Bounds for Finding Stationary Points Icited by 125
  5. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  6. 2019Decentralized Deep Learning with Arbitrary Communication Compressioncited by 109
  7. 2019Natural Compression for Distributed Deep Learningcited by 88
  8. 2019Optimization for deep learning: theory and algorithmscited by 70
  9. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
  10. 2020Linearly Converging Error Compensated SGDcited by 61
  11. 2020Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressorcited by 45
  12. 2020Error Compensated Distributed SGD Can Be Acceleratedcited by 45
  13. 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
  14. 2016Randomized Distributed Mean Estimation: Accuracy vs Communicationcited by 39
  15. 2020Recent Theoretical Advances in Non-Convex Optimizationcited by 30
  16. 2020A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimizationcited by 27
  17. 2019Communication-Efficient Local Decentralized SGD Methodscited by 21
  18. 2020Adaptivity of Stochastic Gradient Methods for Nonconvex Optimizationcited by 16
  19. 2019Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexitycited by 8
  20. 2020Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reductioncited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 25; 2023: 16; 2024: 12; 2025: 9; 2026: 3.

77 papers.

Sort:

  1. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  2. 2021Fast Federated Learning in the Presence of Arbitrary Device Unavailabilitycited by 72
  3. 2021EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learningcited by 53
  4. 2021FedNL: Making Newton-Type Methods Applicable to Federated Learningcited by 50
  5. 2022BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compressioncited by 41
  6. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  7. 2021Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devicescited by 36
  8. 2022SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compressioncited by 34
  9. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  10. 2023Momentum Provably Improves Error Feedback!cited by 31
  11. 2022Fine-tuning Language Models over Slow Networks using Activation Compression with Guaranteescited by 29
  12. 20223PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregationcited by 27
38 more
  1. 2023DoCoFL: Downlink Compression for Cross-Device Federated Learningcited by 27
  2. 2021CANITA: Faster Rates for Distributed Convex Optimization with Communication Compressioncited by 23
  3. 2022Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimizationcited by 23
  4. 2021FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learningcited by 19
  5. 2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 19
  6. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  7. 2022Privacy-Aware Compression for Federated Data Analysiscited by 17
  8. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
  9. 2022DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronizationcited by 15
  10. 2021Faster Rates for Compressed Federated Learning with Client-Variance Reductioncited by 14
  11. 2022Anchor Sampling for Federated Learning with Partial Client Participationcited by 14
  12. 2022Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clusteringcited by 14
  13. 2022Lottery Aware Sparsity Hunting: Enabling Federated Learning on Resource-Limited Edgecited by 12
  14. 2022Federated Learning with Flexible Controlcited by 12
  15. 2023Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Ratescited by 12
  16. 2021Secure Distributed Training at Scalecited by 11
  17. 2022Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregationcited by 11
  18. 2023Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compressioncited by 11
  19. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  20. 2022FL_PyTorch: optimization research simulator for federated learningcited by 10
  21. 2024DeMo: Decoupled Momentum Optimizationcited by 10
  22. 2021Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniquescited by 9
  23. 2022Communication-Efficient Federated Learning With Data and Client Heterogeneitycited by 9
  24. 2023Convergence and Privacy of Decentralized Nonconvex Optimization with Gradient Clipping and Communication Compressioncited by 9
  25. 2022Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalitiescited by 8
  26. 2022Fast Heterogeneous Federated Learning with Hybrid Client Selectioncited by 8
  27. 2023Federated Learning While Providing Model as a Service: Joint Training and Inference Optimizationcited by 8
  28. 2022QUIC-FL: Quick Unbiased Compression for Federated Learningcited by 7
  29. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  30. 2023AQUILA: Communication Efficient Federated Learning with Adaptive Quantization in Device Selection Strategycited by 7
  31. 2021EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedbackcited by 6
  32. 2023Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Featurescited by 6
  33. 2023Adaptive Compression in Federated Learning via Side Informationcited by 6
  34. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  35. 2024Activations and Gradients Compression for Model-Parallel Trainingcited by 6
  36. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  37. 2022Federated Learning with a Sampling Algorithm under Isoperimetrycited by 4
  38. 2023ELF: Federated Langevin Algorithms with Primal, Dual and Bidirectional Compressioncited by 4

50 most cited of 77 All 77 (JSON)