TL;DR
Training federated learning models efficiently relies heavily on which clients are sampled each round. The authors propose K-Vib, a "free" adaptive client sampling algorithm that requires no extra communication or computation from edge devices. By pairing independent client sampling (independent coin flips) with an online convex optimization framework, K-Vib achieves lower gradient estimation variance and a communication-budget speedup on regret of $\tilde{\mathcal{O}}(N^{1/3} T^{2/3} / K^{4/3})$.
What Problem Does This Paper Address?
In cross-device Federated Learning (FL), a central server trains a shared model by coordinating thousands or millions of resource-constrained edge devices (like phones or IoT hardware). Because communicating with all devices simultaneously is impossible, the server samples a small subset of $K$ clients per round.
However, client data is non-IID and varies widely in quantity and quality. Standard uniform sampling leads to high-variance global model updates, slowing convergence. Existing importance sampling methods either:
- Require extra overhead: Demanding that clients compute and transmit gradient norms before sampling decisions are made.
- Introduce bias: Using heuristics (like prioritizing clients with the highest loss) that alter the global optimization objective and hurt consistency.
- Ignore batch-budget scaling: Existing unbiased online adaptive sampling schemes do not show theoretical performance improvements as the communication budget $K$ increases.
The paper addresses how a server can adaptively pick clients in an unbiased manner, using only the routinely uploaded model updates ("free" adaptivity), while minimizing gradient variance as the sampling budget $K$ scales.
Methods
The authors introduce K-Vib, an adaptive sampler rooted in two core techniques:
- Independent Sampling Procedure: Standard FL samplers select $K$ clients without replacement (random sampling). The authors prove that an independent sampling procedure—where each client $i$ is included via an independent Bernoulli trial with probability $p_i$ ($\sum_{i=1}^N p_i = K$)—yields strictly lower or equal variance in the global gradient estimator compared to random sampling without replacement.
- Online Convex Optimization (OCO) with Partial Feedback:
- Finding the variance-optimal probabilities depends on local update norms $\|g_i^t\|$, which are unknown prior to selection.
- The authors formulate this as an OCO problem using Follow-The-Regularized-Leader (FTRL).
- Because the server only observes updates from sampled clients (partial feedback), K-Vib forms unbiased importance-weighted estimates of update norms and employs an $\epsilon$-greedy-style mixing strategy: $$\tilde{p}_i^t = (1 - \theta) p_i^t + \theta \frac{K}{N}$$ This guarantees exploration and prevents unselected clients from having vanishingly small sampling probabilities.
Datasets
The authors evaluated K-Vib on:
- Synthetic Power-Law Dataset: 100 clients generated with Gaussian feature distributions for logistic regression, where local data volumes follow a power law.
- Federated EMNIST (FEMNIST): From the LEAF benchmark, tested with a Convolutional Neural Network (CNN) across three data-imbalance settings:
- v1: 10% of clients hold 82% of all training images.
- v2: 20% of clients hold 90% of training images.
- v3: 50% of clients hold 98% of training images.
No new datasets were introduced.
Key Insights and Ideas
- The Sampling Mechanism Itself Reduces Variance: Independent Bernoulli trials systematically outperform fixed-size subset sampling without replacement for importance-weighted gradient estimators, regardless of the sampling distribution chosen.
-
Budget-Aware Regret Speedup: By analyzing the independent sampling formulation, K-Vib improves the expected regret bound from prior bounds of $\tilde{\mathcal{O}}(N^{1/3}T^{2/3})$ (such as VRB or Avare) to: $$\tilde{\mathcal{O}}\left(\frac{N^{1/3} T^{2/3}}{K^{4/3}}\right)$$ This provides a near-linear speedup with respect to the expected sample size $K$.
-
Bridging OCO and FL Convergence: The authors connect the OCO regret directly to non-convex FedAvg convergence (Theorem 3.9), demonstrating that minimizing the online sampling regret directly improves the global gradient descent bound.
Key Results
- Regret & Variance Reduction: On the synthetic benchmark, K-Vib consistently maintained lower dynamic regret and lower gradient variance than baseline samplers (Uniform, Mabs, Vrb, and Avare). Unlike baselines whose regret degraded when increasing $K$ from 10 to 70, K-Vib's regret shrank significantly as predicted by theory.
- Faster Empirical Convergence: In FEMNIST experiments ($K \approx 5\%$ of total clients, $T = 500$ rounds), K-Vib reached higher test accuracy and lower training loss faster—particularly in the critical early rounds—across all three non-IID imbalance levels.
- Hyperparameter Robustness: Ablation studies showed K-Vib's variance reduction was robust across regularization parameters $\gamma \in [0.005, 1.0]$.
Limitations and Future Work
- Static Uniform Mixing: K-Vib currently uses a static uniform distribution for exploration mixing; optimizing this auxiliary distribution dynamically via online mirror descent could yield further gains.
- Client Availability & Stragglers: While a theoretical proof sketch for random client dropouts is provided (Appendix E.1), empirical evaluations assume sampled clients always respond.
- Integration with Advanced Optimizers: The current empirical and theoretical analyses focus on standard SGD-based FedAvg, leaving combinations with server-side momentum (e.g., FedAdam) or adaptive client learning rates for future work.
Summary updated