Timezone: »

 
Poster
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
Sai Praneeth Reddy Karimireddy · Satyen Kale · Mehryar Mohri · Sashank Jakkam Reddi · Sebastian Stich · Ananda Theertha Suresh

Tue Jul 14 10:00 AM -- 10:45 AM & Tue Jul 14 09:00 PM -- 09:45 PM (PDT) @
in Poster Session 4 »

Federated learning is a key scenario in modern large-scale machine learning where the data remains distributed over a large number of clients and the task is to learn a centralized model without transmitting the client data. The standard optimization algorithm used in this setting is Federated Averaging (FedAvg) due to its low communication cost. We obtain a tight characterization of the convergence of FedAvg and prove that heterogeneity (non-iid-ness) in the client's data results in a `drift' in the local updates resulting in poor performance.

As a solution, we propose a new algorithm (SCAFFOLD) which uses control variates (variance reduction) to correct for the `client drift'. We prove that SCAFFOLD requires significantly fewer communication rounds and is not affected by data heterogeneity or client sampling. Further, we show that (for quadratics) SCAFFOLD can take advantage of similarity in the client's data yielding even faster convergence. The latter is the first result to quantify the usefulness of local-steps in distributed optimization.

Keywords: Convex Optimization · Non-convex Optimization · Parallel and Distributed Learning · Optimization - Convex

Author Information

Sai Praneeth Reddy Karimireddy (EPFL)
Satyen Kale (Google)
Mehryar Mohri (Google Research and Courant Institute of Mathematical Sciences)
Sashank Jakkam Reddi (Google)
Sebastian Stich (EPFL)
Ananda Theertha Suresh (Google Research)

More from the Same Authors