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

Grigory Malinovsky, Konstantin Mishchenko, Peter Richtárik

Abstract

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 $\mathcal{O}\left(\varepsilon^{-3}\right)$ to $\mathcal{O}\left(\varepsilon^{-2}\right)$. 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. 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.

Introduction

Federated Learning (FL) enables training machine learning models across decentralized devices without data leaving the source. While practitioners frequently employ heuristics like server-side stepsizes (scaling global updates) and Random Reshuffling (processing local data without replacement), theoretical justification for their efficacy has been limited. Most existing theories for Federated Averaging (FedAvg) assume clients sample data with replacement, which contradicts the real-world practice of shuffling local datasets. Furthermore, the interaction between local client steps and global server steps—especially under data heterogeneity and partial client participation—remains poorly understood. This paper bridges this gap by providing a rigorous theoretical framework for these common practices.

The Nastya Algorithm

The authors introduce Nastya, a unified algorithm that integrates four critical components of modern FL:

  1. Partial Participation: The server selects a random cohort of $C$ clients from a total of $M$ in each round.
  2. Local Training: Selected clients perform a full pass over their local data.
  3. Random Reshuffling (RR): Clients process data in a random order without replacement, reducing gradient estimate variance compared to standard SGD.
  4. Server-side Stepsizes ($\eta$): The server treats the average of client updates as a gradient direction and applies a global stepsize $\eta$.
Nastya combines key features missing in previous theoretical works.

Theoretical Insights

The analysis reveals a powerful synergy between local and global optimization. By maintaining a small local client stepsize ($\gamma$), "client drift"—the divergence caused by heterogeneous data—is minimized. This slow local progress is then compensated for by a "big leap" at the server level using a large stepsize ($\eta$).

Crucially, the use of Random Reshuffling allows the algorithm to visit every data point once per pass, leading to faster convergence than with-replacement sampling. Nastya also handles data heterogeneity without the need for complex drift-reduction techniques like SCAFFOLD, effectively achieving "drift reduction for free" through its dual-stepsize strategy and RR.

Key Results

Nastya achieves state-of-the-art complexity rates across multiple optimization regimes:

  • Non-Convex Speedup: Convergence improves from the standard $O(\epsilon^{-3})$ to $O(\epsilon^{-2})$, matching the best rates for centralized optimization.
  • Strongly Convex Efficiency: Complexity is reduced to $\tilde{O}(\frac{Ln}{\mu})$, demonstrating that local steps can effectively overcome communication bottlenecks.
Comparison of convergence rates for Nastya against other federated optimization methods.

Empirical evaluations on Logistic Regression (mushrooms dataset) and Deep Learning (LeNet on CIFAR-10) validate these findings. On CIFAR-10, adaptive server-side optimizers (like Adam) were shown to significantly improve performance when base client stepsizes were suboptimal, justifying the use of adaptive server-side optimization in practice.

Conclusion

This work provides the first theoretical proof that server-side stepsizes and Random Reshuffling are not just heuristics but fundamental tools for accelerating Federated Learning. While the current theory focuses on fixed server stepsizes, experimental results suggest that adaptive variants are even more potent. Future research will explore extending these proofs to adaptive optimizers and integrating communication compression techniques.

Summary updated

Abstract

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 $\mathcal{O}\left(\varepsilon^{-3}\right)$ to $\mathcal{O}\left(\varepsilon^{-2}\right)$. 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.
BibTeX
@inproceedings{malinovsky2023server,
  author = {Grigory Malinovsky and Konstantin Mishchenko and Peter Richtárik},
  title = {{Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimization}},
  booktitle = {DistributedML@CoNEXT},
  year = {2023},
  url = {https://openreview.net/forum?id=YmcqPmlxes},
}
Figure