On the Outsized Importance of Learning Rates in Local Update Methods

Abstract

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.

References in corpus (27)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Federated Learning for Mobile Keyboard Prediction
• One weird trick for parallelizing convolutional neural networks
• How To Backdoor Federated Learning
• Learning Differentially Private Recurrent Language Models
• Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• On First-Order Meta-Learning Algorithms
• Applied Federated Learning: Improving Google Keyboard Query Suggestions
• Can You Really Backdoor Federated Learning?
• Improving Federated Learning Personalization via Model Agnostic Meta Learning
• Personalized Federated Learning: A Meta-Learning Approach
• LEAF: A Benchmark for Federated Settings
• Meta-Learning with Implicit Gradients
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Robust Federated Learning in a Heterogeneous Environment
• Adaptive Federated Optimization
• The Non-IID Data Quagmire of Decentralized Machine Learning
• FedSplit: An algorithmic framework for fast federated optimization
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Is Local SGD Better than Minibatch SGD?
• On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms
• Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates
• Federated Learning of N-gram Language Models

Cited by in corpus (9)

• A Field Guide to Federated Optimization
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms
• Effective Federated Adaptive Gradient Methods with Non-IID Decentralized Data
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• How Does the Task Landscape Affect MAML Performance?
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• On Data Efficiency of Meta-learning