# Provable Reduction in Communication Rounds for Non-Smooth Convex Federated Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 26 references that are in the map.
- First posted on arXiv 27 Mar 2025.

## Builds on (most cited first, 19 of 19)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (2018)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [On the Convergence of Local Descent Methods in Federated Learning](https://mlsanity.com/paper/1910.14425/) (2019)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [First Analysis of Local GD on Heterogeneous Data](https://mlsanity.com/paper/1909.04715/) (2019)
- [Communication Efficiency in Federated Learning: Achievements and Challenges](https://mlsanity.com/paper/2107.10996/) (2021)
- [Towards Efficient Communications in Federated Learning: A Contemporary Survey](https://mlsanity.com/paper/2208.01200/) (2022)
- [GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity](https://mlsanity.com/paper/2210.16402/) (2022)
- [Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method](https://mlsanity.com/paper/2010.01848/) (2020)
- [LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression](https://mlsanity.com/paper/2403.04348/) (2024)
- [FedComLoc: Communication-Efficient Distributed Training of Sparse and Quantized Models](https://mlsanity.com/paper/2403.09904/) (2024)

## Abstract (arXiv)

Multiple local steps are key to communication-efficient federated learning. However, theoretical guarantees for such algorithms, without data heterogeneity-bounding assumptions, have been lacking in general non-smooth convex problems. Leveraging projection-efficient optimization methods, we propose FedMLS, a federated learning algorithm with provable improvements from multiple local steps. FedMLS attains an ε-suboptimal solution in O(1/ε) communication rounds, requiring a total of O(1/ε2) stochastic subgradient oracle calls.