Abstract
Federated Learning (FL) relies on client sampling to manage communication with vast numbers of edge devices. However, traditional Random Sampling Procedures (RSP) introduce significant sampling variance, which acts as noise and slows model convergence. This paper introduces K-Vib, an adaptive unbiased client sampler that leverages an Independent Sampling Procedure (ISP). By transitioning from fixed-size sampling to independent Bernoulli trials for each client, K-Vib achieves tighter variance bounds. Combined with an online variance reduction strategy using Follow-the-Regularized-Leader (FTRL), K-Vib demonstrates a near-linear speed-up relative to the communication budget, often doubling training efficiency across diverse image and text classification tasks.
Introduction
In large-scale Federated Learning, communicating with every client in every round is computationally and logistically prohibitive. Consequently, a central server typically selects a small subset of clients for updates. The standard approach, Random Sampling Procedure (RSP), picks a fixed number of clients $K$ uniformly. While unbiased, RSP suffers from high sampling variance, forcing the global model to follow a noisy optimization path. Previous attempts to mitigate this through biased sampling often lead to model drift toward specific data distributions. The central challenge addressed here is reducing this variance adaptively without introducing bias.
The Independent Sampling Procedure (ISP)
The core innovation of this work is the shift from RSP to the Independent Sampling Procedure (ISP). In RSP, the constraint of selecting exactly $K$ clients creates a dependency that inflates variance. In contrast, ISP allows the server to decide participation for each client independently via a "dice roll." While the actual number of participating clients may fluctuate slightly around the target $K$, the authors prove that this stochasticity unlocks a significantly tighter bound on sampling variance.
As shown in the sampling statistics, ISP consistently maintains a lower L2-norm of estimate error compared to both uniform sampling and standard RSP, particularly as the sampling budget $K$ increases. This reduction in "noise" allows the optimization process to proceed more directly toward the global minimum.
The K-Vib Sampler: Adaptive Variance Reduction
Building upon ISP, the authors developed K-Vib, which treats client selection as an Online Convex Optimization problem. K-Vib utilizes a "Follow-the-Regularized-Leader" (FTRL) strategy to adaptively adjust sampling probabilities based on historical feedback—specifically, the norms of local updates. Clients that consistently provide more informative updates (higher norms) are assigned higher sampling probabilities.
To ensure the system does not permanently ignore certain clients (which would introduce bias), K-Vib employs a mixing strategy. This ensures every client maintains a non-zero probability of being sampled, allowing the server to periodically refresh its "feedback" for all participants.
Experimental Evaluation
The researchers evaluated K-Vib across several benchmarks, including FEMNIST (image classification with high heterogeneity) and large-scale language tasks like AGNews and CCNews using DistillBert and Pythia-70M models.
Key Results
- 2x Training Speedup: K-Vib reached target accuracy levels approximately twice as fast as baseline algorithms like FedAvg.
- Linear Scaling: The theoretical regret bound of $\tilde{O}(N^{1/3} T^{2/3} / K^{4/3})$ indicates a near-linear speed-up relative to the communication budget $K$, outperforming previous state-of-the-art bounds.
- Robustness to Heterogeneity: K-Vib proved particularly effective in highly heterogeneous environments, where its adaptive nature allowed it to navigate data imbalances far more effectively than uniform sampling.
Conclusion and Future Work
K-Vib represents a significant step forward in federated optimization by demonstrating that the "fixed-K" constraint of traditional sampling is a bottleneck. By adopting independent sampling and adaptive feedback, K-Vib substantially reduces variance and accelerates training. Future research will focus on stabilizing the adaptive strategy in environments with extreme data volatility and optimizing the server-side overhead for cross-device settings involving millions of clients.
Summary updated