  As a novel distributed learning paradigm, federated learning (FL) faces
serious challenges in dealing with massive clients with heterogeneous data
distribution and computation and communication resources. Various
client-variance-reduction schemes and client sampling strategies have been
respectively introduced to improve the robustness of FL. Among others,
primal-dual algorithms such as the alternating direction of method multipliers
(ADMM) have been found being resilient to data distribution and outperform most
of the primal-only FL algorithms. However, the reason behind remains a mystery
still. In this paper, we firstly reveal the fact that the federated ADMM is
essentially a client-variance-reduced algorithm. While this explains the
inherent robustness of federated ADMM, the vanilla version of it lacks the
ability to be adaptive to the degree of client heterogeneity. Besides, the
global model at the server under client sampling is biased which slows down the
practical convergence. To go beyond ADMM, we propose a novel primal-dual FL
algorithm, termed FedVRA, that allows one to adaptively control the
variance-reduction level and biasness of the global model. In addition, FedVRA
unifies several representative FL algorithms in the sense that they are either
special instances of FedVRA or are close to it. Extensions of FedVRA to
semi/un-supervised learning are also presented. Experiments based on
(semi-)supervised image classification tasks demonstrate superiority of FedVRA
over the existing schemes in learning scenarios with massive heterogeneous
clients and client sampling.
