SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning

By Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, Ananda Theertha Suresh. 2019

406 citations recorded by the source corpus.

Federated learning is a key scenario in modern large-scale machine learning. In that scenario, the training data remains distributed over a large number of clients, which may be phones, other mobile devices, or network sensors and a centralized model is learned without ever transmitting client data over the network. The standard optimization algorithm used in this scenario is Federated Averaging (FedAvg). However, when client data is heterogeneous, which is typical in applications, FedAvg does not admit a favorable convergence guarantee. This is because local updates on clients can drift apart, which also explains the slow convergence and hard-to-tune nature of FedAvg in practice. This paper presents a new Stochastic Controlled Averaging algorithm (SCAFFOLD) which uses control variates to reduce the drift between different clients. We prove that the algorithm requires significantly fewer rounds of communication and benefits from favorable convergence guarantees.

Subfields: Artificial Intelligence, Federated & Distributed Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Federated & Distributed Learning

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “Bounded gradient variance, which is a widely used assumption to analyze stochastic gradient methods, is often used when clients use stochastic local updates [266, 264, 265, 401, 227].”
Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, methodology): “This generalizes results of [15] from quadratics to all functions.”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “Besides, previous cross-client variance reduction methods such as variancereduced local SGD (VRLSGD) [21] and SCAFFOLD [20] are only designed for homogeneous local steps case.”
On the Outsized Importance of Learning Rates in Local Update Methods (2020, neutral): “We note that a form of this decoupling has previously been explored by Karimireddy et al. (2019) and Reddi et al.”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “In their recently updated parallel version, Karimireddy et al. (2019) improve upon these rates by removing σ from the second term.”
Adaptive Federated Optimization (2020, methodology): “SCAFFOLD has two variants described by Karimireddy et al. (2019). In Option I, the control variate of a client is updated using a full gradient computation.”
Personalized Federated Learning: A Meta-Learning Approach (2020, background): “[21] S.”
Is Local SGD Better than Minibatch SGD? (2020, background): “[12] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh.”
Distilled One-Shot Federated Learning (2020, methodology): “They include modifying the training loss [17], using lifelong learning to prevent forgetting [29], and correcting local updates using control variates [12].”
Adaptive Personalized Federated Learning (2020, methodology): “In this experiment it could be the global model of either FedAvg or SCAFFOLD (Karimireddy et al., 2019).”
Federated Visual Classification with Real-World Data Distribution (2020, methodology): “[14] propose to use control variates for correcting client updates drift.”
Federated Continual Learning with Weighted Inter-client Transfer (2020, positive): “5) Scaffold: FCL using Scaffold (Karimireddy et al., 2020) algorithm.”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, methodology): “…considered, for example with momentum (Yu et al., 2019a; Wang et al., 2019), with quantization (Reisizadeh et al., 2019; Basu et al., 2019), with adaptive stepsizes (Xie et al., 2019) and with various variance-reduction methods (Liang et al., 2019; Sharma et al., 2019; Karimireddy et al., 2019).”
On the Convergence of Local Descent Methods in Federated Learning (2019, methodology): “To reduce the drift among local workers, few studies attempt to either regularize updates such as proximal regularization [28] or utilize controlled averaging [15] (In Subsection 3.”
Federated Learning of a Mixture of Global and Local Models (2020, background): “Other variance reduced local SGD algorithms (Liang et al., 2019; Karimireddy et al., 2019; Wu et al., 2019) are not capable of achieving linear convergence.”