Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learning

Abstract

We study a family of algorithms, which we refer to as local update methods, generalizing many federated and meta-learning algorithms. We prove that for quadratic models, local update methods are equivalent to first-order optimization on a surrogate loss we exactly characterize. Moreover, fundamental algorithmic choices (such as learning rates) explicitly govern a trade-off between the condition number of the surrogate loss and its alignment with the true loss. We derive novel convergence rates showcasing these trade-offs and highlight their importance in communication-limited settings. Using these insights, we are able to compare local update methods based on their convergence/accuracy trade-off, not just their convergence to critical points of the empirical loss. Our results shed new light on a broad range of phenomena, including the efficacy of server momentum in federated learning and the impact of proximal client updates.

References in corpus (12)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Federated Learning for Mobile Keyboard Prediction
• Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification
• On First-Order Meta-Learning Algorithms
• Applied Federated Learning: Improving Google Keyboard Query Suggestions
• Improving Federated Learning Personalization via Model Agnostic Meta Learning
• Personalized Federated Learning: A Meta-Learning Approach
• LEAF: A Benchmark for Federated Settings
• Adaptive Federated Optimization
• The Non-IID Data Quagmire of Decentralized Machine Learning
• FedSplit: An algorithmic framework for fast federated optimization
• Is Local SGD Better than Minibatch SGD?