Exploring Federated Optimization by Reducing Variance of Adaptive Unbiased Client Sampling

Dun Zeng, Zenglin Xu, Yu Pan, Qifan Wang, Xiaoying TangSubmission to ICLR 2024 · Withdrawn

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:

  1. Require extra overhead: Demanding that clients compute and transmit gradient norms before sampling decisions are made.
  2. Introduce bias: Using heuristics (like prioritizing clients with the highest loss) that alter the global optimization objective and hurt consistency.
  3. 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:

  1. 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.
  2. Online Convex Optimization (OCO) with Partial Feedback:
  3. Finding the variance-optimal probabilities depends on local update norms $\|g_i^t\|$, which are unknown prior to selection.
  4. The authors formulate this as an OCO problem using Follow-The-Regularized-Leader (FTRL).
  5. 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

Abstract

Federated Learning (FL) systems usually sample a fraction of clients to conduct a training process. Notably, the variance of global estimates for updating the global model built on information from sampled clients is highly related to federated optimization quality. This paper explores a line of "free" adaptive client sampling techniques in federated optimization, where the server builds promising sampling probability and reliable global estimates without requiring additional local communication and computation. We capture a minor variant in the sampling procedure and improve the global estimation accordingly. Based on that, we propose a novel sampler called K-Vib, which solves an online convex optimization respecting client sampling in federated optimization. It achieves improved a linear speed up on regret bound $\tilde{\mathcal{O}}\big(N^{\frac{1}{3}}T^{\frac{2}{3}}/K^{\frac{4}{3}}\big)$ with communication budget $K$. As a result, it significantly improves the performance of federated optimization. Theoretical improvements and intensive experiments on classic federated tasks demonstrate our findings.
BibTeX
@article{zeng2025exploring,
  author = {Dun Zeng and Zenglin Xu and Yu Pan and Qifan Wang and Xiaoying Tang},
  title = {{Exploring Federated Optimization by Reducing Variance of Adaptive Unbiased Client Sampling}},
  journal = {Trans. Mach. Learn. Res.},
  year = {2025},
  url = {https://openreview.net/forum?id=hxxzOYf4Zc},
}
Figure