# Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimization

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 32 references that are in the map.
- First posted on arXiv 26 Jan 2022.

## 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 Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [On the Origin of Implicit Regularization in Stochastic Gradient Descent](https://mlsanity.com/paper/2101.12176/) (2021)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Optimal Client Sampling for Federated Learning](https://mlsanity.com/paper/2010.13723/) (2020)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)

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

- [FedExP: Speeding Up Federated Averaging via Extrapolation](https://mlsanity.com/paper/2301.09604/) (2023)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox](https://mlsanity.com/paper/2207.03957/) (2022)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation](https://mlsanity.com/paper/2410.08305/) (2024)
- [Task Arithmetic Through The Lens Of One-Shot Federated Learning](https://mlsanity.com/paper/2411.18607/) (2024)
- [Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Acceleration](https://mlsanity.com/paper/2509.10439/) (2025)
- [Improving Accelerated Federated Learning with Compression and Importance Sampling](https://mlsanity.com/paper/2306.03240/) (2023)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [Coordinating Distributed Example Orders for Provably Accelerated Training](https://mlsanity.com/paper/2302.00845/) (2023)
- [On Convergence of Incremental Gradient for Non-Convex Smooth Functions](https://mlsanity.com/paper/2305.19259/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Distributed Stochastic Optimization under a General Variance Condition](https://mlsanity.com/paper/2301.12677/) (2023)
- [Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learning](https://mlsanity.com/paper/2406.01115/) (2024)
- [FedECADO: A Dynamical System Model of Federated Learning](https://mlsanity.com/paper/2410.09933/) (2024)
- [First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptions](https://mlsanity.com/paper/2512.21521/) (2025)
- [Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness](https://mlsanity.com/paper/2212.01848/) (2022)
- [Improving Federated Aggregation with Deep Unfolding Networks](https://mlsanity.com/paper/2306.17362/) (2023)
- [Towards Fairness in Provably Communication-Efficient Federated Recommender Systems](https://mlsanity.com/paper/2405.15788/) (2024)
- [Painless Federated Learning: An Interplay of Line-Search and Extrapolation](https://mlsanity.com/paper/2408.17145/) (2024)
- [Adaptive Federated Learning via Dynamical System Model](https://mlsanity.com/paper/2510.04203/) (2025)

## Abstract (arXiv)

We present a theoretical study of server-side optimization in federated learning. Our results are the first to show that the widely popular heuristic of scaling the client updates with an extra parameter is very useful in the context of Federated Averaging (FedAvg) with local passes over the client data. Each local pass is performed without replacement using Random Reshuffling, which is a key reason we can show improved complexities. In particular, we prove that whenever the local stepsizes are small, and the update direction is given by FedAvg in conjunction with Random Reshuffling over all clients, one can take a big leap in the obtained direction and improve rates for convex, strongly convex, and non-convex objectives. In particular, in non-convex regime we get an enhancement of the rate of convergence from Oleft(varepsilon-3right) to Oleft(varepsilon-2right). This result is new even for Random Reshuffling performed on a single node. In contrast, if the local stepsizes are large, we prove that the noise of client sampling can be controlled by using a small server-side stepsize. To the best of our knowledge, this is the first time that local steps provably help to overcome the communication bottleneck. Together, our results on the advantage of large and small server-side stepsizes give a formal justification for the practice of adaptive server-side optimization in federated learning. Moreover, we consider a variant of our algorithm that supports partial client participation, which makes the method more practical.