# MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 75 of its 136 references that are in the map.
- First posted on arXiv 22 Dec 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization](https://mlsanity.com/paper/1909.13014/) (2019)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [Sparse Communication for Distributed Gradient Descent](https://mlsanity.com/paper/1704.05021/) (2017)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [FetchSGD: Communication-Efficient Federated Learning with Sketching](https://mlsanity.com/paper/2007.07682/) (2020)
- [The Road Less Scheduled](https://mlsanity.com/paper/2405.15682/) (2024)
- [Federated Learning with Compression: Unified Analysis and Sharp Guarantees](https://mlsanity.com/paper/2007.01154/) (2020)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [ATOMO: Communication-efficient Learning via Atomic Sparsification](https://mlsanity.com/paper/1806.04090/) (2018)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)

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

- [SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums](https://mlsanity.com/paper/2606.15832/) (2026)

## 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.