mlsanityData to 7 Oct 2026

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

arXiv 2201.11066 ↗First posted 26 Jan 2022cs.LG math.OCcited by 23

Not on the map. Why?

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.

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

Builds on

19 of 32 references.

References · 19

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  4. 2020Adaptive Federated Optimizationcited by 1,036
  5. 2019Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classificationcited by 836
  6. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
  7. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  8. 2018The Convergence of Sparsified Gradient Methodscited by 228
  9. 2021On the Origin of Implicit Regularization in Stochastic Gradient Descentcited by 183
  10. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  11. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  12. 2020Optimal Client Sampling for Federated Learningcited by 123
7 more
  1. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  2. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  3. 2019Adaptive Gradient Descent without Descentcited by 79
  4. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
  5. 2021On Large-Cohort Training for Federated Learningcited by 73
  6. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  7. 2021Proximal and Federated Random Reshufflingcited by 33

Built on by

Cited by year

Citing papers per year: 2022: 4; 2023: 9; 2024: 7; 2025: 3.

23 papers.

Sort:

  1. 2023FedExP: Speeding Up Federated Averaging via Extrapolationcited by 68
  2. 2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 19
  3. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  4. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  5. 2023AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithmscited by 16
  6. 2023Federated Learning with Regularized Client Participationcited by 13
  7. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 12
  8. 2024Task Arithmetic Through The Lens Of One-Shot Federated Learningcited by 12
  9. 2023Coordinating Distributed Example Orders for Provably Accelerated Trainingcited by 7
  10. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  11. 2023Improving Accelerated Federated Learning with Compression and Importance Samplingcited by 7
  12. 2024Loss Landscape Characterization of Neural Networks without Over-Parametrizationcited by 7
11 more
  1. 2025Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Accelerationcited by 7
  2. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  3. 2023Distributed Stochastic Optimization under a General Variance Conditioncited by 4
  4. 2024FedECADO: A Dynamical System Model of Federated Learningcited by 2
  5. 2024Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learningcited by 1
  6. 2022Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothnesscited by 0
  7. 2023Improving Federated Aggregation with Deep Unfolding Networkscited by 0
  8. 2024Towards Fairness in Provably Communication-Efficient Federated Recommender Systemscited by 0
  9. 2024Painless Federated Learning: An Interplay of Line-Search and Extrapolationcited by 0
  10. 2025Adaptive Federated Learning via Dynamical System Modelcited by 0
  11. 2025First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptionscited by 0