Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learning
This work provides theoretical insights for researchers in federated and meta-learning, though it is incremental as it builds on existing algorithms with new analysis.
The paper analyzes local update methods in federated and meta-learning, proving equivalence to first-order optimization on a surrogate loss for quadratic models and deriving convergence rates that reveal trade-offs between condition number and loss alignment, with applications to communication-limited settings.
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.