  Federated Learning (FL) is a distributed learning paradigm to train a global
model across multiple devices without collecting local data. In FL, a server
typically selects a subset of clients for each training round to optimize
resource usage. Central to this process is the technique of unbiased client
sampling, which ensures a representative selection of clients. Current methods
primarily utilize a random sampling procedure which, despite its effectiveness,
achieves suboptimal efficiency owing to the loose upper bound caused by the
sampling variance. In this work, by adopting an independent sampling procedure,
we propose a federated optimization framework focused on adaptive unbiased
client sampling, improving the convergence rate via an online variance
reduction strategy. In particular, we present the first adaptive client
sampler, K-Vib, employing an independent sampling procedure. K-Vib achieves a
linear speed-up on the regret bound
$\tilde{\mathcal{O}}\big(N^{\frac{1}{3}}T^{\frac{2}{3}}/K^{\frac{4}{3}}\big)$
within a set communication budget $K$. Empirical studies indicate that K-Vib
doubles the speed compared to baseline algorithms, demonstrating significant
potential in federated optimization.
