MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes
Not on the map. Why?
Abstract (arXiv)
Non-smooth communication-efficient federated optimization is crucial for many machine learning applications, yet remains largely unexplored theoretically. Recent advancements have primarily focused on smooth convex and non-convex regimes, leaving a significant gap in understanding the non-smooth convex setting. Additionally, existing literature often overlooks efficient server-to-worker communication (downlink), focusing primarily on worker-to-server communication (uplink). We consider a setup where uplink costs are negligible and focus on optimizing downlink communication by improving state-of-the-art schemes like EF21-P (arXiv:2209.15218) and MARINA-P (arXiv:2402.06412) in the non-smooth convex setting. We extend the non-smooth convex theory of EF21-P [Anonymous, 2024], originally developed for single-node scenarios, to the distributed setting, and extend MARINA-P to the non-smooth convex setting. For both algorithms, we prove an optimal O(1/√T) convergence rate and establish communication complexity bounds matching classical subgradient methods. We provide theoretical guarantees under constant, decreasing, and adaptive (Polyak-type) stepsizes. Our experiments demonstrate that MARINA-P with correlated compressors outperforms other methods in both smooth non-convex and non-smooth convex settings. This work presents the first theoretical results for distributed non-smooth optimization with server-to-worker compression, along with comprehensive analysis for various stepsize schemes.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 75 of its 136 references that are in the map. First posted on arXiv 22 Dec 2024.
Builds on
75 of 136 references.
References · 75
- 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
- 2020Scaling Laws for Neural Language Modelscited by 6,411
- 2019Advances and Open Problems in Federated Learningcited by 3,021
- 2021Convex optimizationcited by 2,479
- 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
- 2019On the Convergence of Adam and Beyondcited by 834
- 2018Local SGD Converges Fast and Communicates Littlecited by 595
- 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
- 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 471
- 2018Sparsified SGD with Memorycited by 373
38 more
- 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
- 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 349
- 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
- 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
- 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
- 2017Sparse Communication for Distributed Gradient Descentcited by 243
- 2019PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimizationcited by 234
- 2018The Convergence of Sparsified Gradient Methodscited by 228
- 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 199
- 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 178
- 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 159
- 2024The Road Less Scheduledcited by 158
- 2020Is Local SGD Better than Minibatch SGD?cited by 151
- 2020On Biased Compression for Distributed Learningcited by 140
- 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
- 2018ATOMO: Communication-efficient Learning via Atomic Sparsificationcited by 135
- 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
- 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 129
- 2020Descending through a Crowded Valley - Benchmarking Deep Learning Optimizerscited by 118
- 2023Learning-Rate-Free Learning by D-Adaptationcited by 113
- 2019Distributed Learning with Compressed Gradient Differencescited by 110
- 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 98
- 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
- 2019Natural Compression for Distributed Deep Learningcited by 88
- 2019Communication-efficient distributed SGD with Sketchingcited by 81
- 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
- 2018Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimizationcited by 76
- 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
- 2020Linearly Converging Error Compensated SGDcited by 61
- 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
- 2019Revisiting the Polyak step sizecited by 55
- 2018Distributed learning with compressed gradientscited by 53
- 2021FedNL: Making Newton-Type Methods Applicable to Federated Learningcited by 50
- 2019Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedbackcited by 49
- 2020Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressorcited by 45
- 2015Network Lasso: Clustering and Optimization in Large Graphscited by 42
- 2016Randomized Distributed Mean Estimation: Accuracy vs Communicationcited by 39
- 2023A Guide Through the Zoo of Biased SGDcited by 39
50 most cited of 75 All 75 (JSON)
Built on by
Not cited yet.