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:
- Partial Participation: In each round, the server selects a random cohort of $C$ clients out of a total $M$.
- Local Training: Each selected client performs a full pass over its local data.
- Random Reshuffling (RR): Instead of standard SGD, clients process their data in a random order without replacement.
- 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
mushroomsdataset 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