On the Outsized Importance of Learning Rates in Local Update Methods

By Zachary B. Charles, Jakub Konecný. 2020

60 citations recorded by the source corpus.

We study a family of algorithms, which we refer to as local update methods, that generalize many federated learning and meta-learning algorithms. We prove that for quadratic objectives, local update methods perform stochastic gradient descent on a surrogate loss function which we exactly characterize. We show that the choice of client learning rate controls the condition number of that surrogate loss, as well as the distance between the minimizers of the surrogate and true loss functions. We use this theory to derive novel convergence rates for federated averaging that showcase this trade-off between the condition number of the surrogate loss and its alignment with the true loss function. We validate our results empirically, showing that in communication-limited settings, proper learning rate tuning is often sufficient to reach near-optimal behavior. We also present a practical method for automatic learning rate decay in local update methods that helps reduce the need for learning rate tuning, and highlight its empirical performance on a variety of tasks and datasets.

Subfields: Artificial Intelligence, Optimization & Training

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 Optimization & Training

Citations in the corpus

Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms (2020, background): “[2020] reformulated FedAvg in a way that enabled adaptive optimization and derived corresponding convergence rates, noting that FedAvg requires careful tuning of learning rate schedules in order to converge to the desired optimum, which was further analyzed by Charles and Konečnỳ [2020]. To the best”
Effective Federated Adaptive Gradient Methods with Non-IID Decentralized Data (2020, background): “Our theoretical analysis from an angle shows the relationship between K and client drift for nonconvex function (it has only been shown for quadratic function (Charles and Konečnỳ (2020))).”