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

Grigory Malinovsky, Konstantin Mishchenko, Peter Richtárik

TL;DR

This paper provides the first rigorous theoretical proof that two common "tricks" in Federated Learning—server-side stepsizes and sampling without replacement (Random Reshuffling)—actually work together to speed up convergence. The authors introduce a new algorithm called Nastya, which achieves significantly better complexity rates (e.g., improving non-convex convergence from $O(\epsilon^{-3})$ to $O(\epsilon^{-2})$) while handling data heterogeneity and partial client participation without needing complex drift-reduction techniques.

What Problem Does This Paper Address?

Federated Learning (FL) is the practice of training machine learning models across many decentralized devices (clients) without their data ever leaving the device. While practitioners have long used heuristics like "server-side stepsizes" (scaling the global update) and "Random Reshuffling" (processing local data without replacement), the theoretical understanding of why these help has been lagging.

Specifically, most existing theories for Federated Averaging (FedAvg) assume that clients sample data with replacement (like standard SGD). However, in the real world, we almost always shuffle the local dataset and pass through it once. Furthermore, the interplay between local client steps and global server steps is poorly understood, especially when only a small fraction of clients participate in each round (partial participation) and when those clients have very different datasets (data heterogeneity).

Methods

The authors propose a new algorithm named Nastya (Algorithm 1). It incorporates four key ingredients:

  1. Partial Participation: In each round, the server selects a random cohort of $C$ clients out of a total $M$.
  2. Local Training: Each selected client performs a full pass over its local data.
  3. Random Reshuffling (RR): Instead of standard SGD, clients process their data in a random order without replacement.
  4. Server-side Stepsizes ($\eta$): After clients send their updates, the server doesn't just average them; it treats the average as a gradient-like direction and takes a step with its own stepsize $\eta$.

The paper provides a unified convergence analysis for Nastya across three regimes: strongly convex, convex, and non-convex objectives.

Datasets

The authors used two primary setups for evaluation:

  • Logistic Regression: Performed on the mushrooms dataset from LibSVM to test the theory in a controlled, convex environment.
  • Deep Learning: Training a LeNet architecture on the CIFAR-10 dataset to demonstrate the algorithm's effectiveness in a practical, non-convex setting.

Key Insights and Ideas

  • The "Small Client, Large Server" Sweet Spot: The theory reveals a fascinating synergy. By keeping the local client stepsize ($\gamma$) small, you minimize "client drift" (the tendency of local models to diverge due to data heterogeneity). You then compensate for this slow local progress by taking a "big leap" at the server level with a large server stepsize ($\eta$).
  • Shuffling is Superior: Using Random Reshuffling (RR) instead of SGD allows the algorithm to "see" every data point exactly once per pass. This reduces the variance of the gradient estimate, leading to faster convergence rates.
  • Drift Reduction for Free: Many FL algorithms (like SCAFFOLD) require extra communication or complex state-tracking to handle data heterogeneity. Nastya achieves competitive results without these extras, simply by leveraging the RR strategy and the dual-stepsize approach.
  • Quantifying the "Price" of Participation: The complexity bounds explicitly include a term for partial participation. When all clients participate ($C=M$), this term vanishes, providing a clear mathematical view of how limited client availability slows down training.

Key Results

  • Non-Convex Speedup: In the non-convex regime, Nastya improves the convergence rate from the standard $O(\epsilon^{-3})$ to $O(\epsilon^{-2})$. This is a significant jump, matching the best-known rates for centralized optimization.
  • Strongly Convex Efficiency: The algorithm achieves a complexity of $\tilde{O}(\frac{Ln}{\mu})$, showing that local steps provably help overcome the communication bottleneck.
  • Empirical Validation: In experiments, Nastya (RR with two stepsizes) consistently outperformed standard RR and adaptive gradient descent. On CIFAR-10, the authors showed that using an adaptive server-side optimizer (like Adam) on top of local updates significantly rescued performance when the base client stepsizes were poorly tuned.

Limitations and Future Work

  • Fixed vs. Adaptive Stepsizes: While the theory focuses on fixed server stepsizes, the experiments suggest that adaptive server stepsizes (like using Adam at the server level) are even more powerful. Extending the formal proofs to these adaptive cases is a natural next step.
  • Communication Compression: The current work does not incorporate communication compression (e.g., quantization or sparsification), which is another major pillar of efficient FL.
  • Scale of Experiments: The experiments are relatively small-scale ("toy" setups like LeNet). While they successfully validate the theoretical predictions, testing Nastya on massive-scale transformer models or cross-silo FL remains for future research.

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 <scr>O</scr> (ε−3) to <scr>O</scr> (ε−2). 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},
}

Loading related content...

Figure