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

We study a family of algorithms, which we refer to as local update methods,\ngeneralizing many federated and meta-learning algorithms. We prove that for\nquadratic models, local update methods are equivalent to first-order\noptimization on a surrogate loss we exactly characterize. Moreover, fundamental\nalgorithmic choices (such as learning rates) explicitly govern a trade-off\nbetween the condition number of the surrogate loss and its alignment with the\ntrue loss. We derive novel convergence rates showcasing these trade-offs and\nhighlight their importance in communication-limited settings. Using these\ninsights, we are able to compare local update methods based on their\nconvergence/accuracy trade-off, not just their convergence to critical points\nof the empirical loss. Our results shed new light on a broad range of\nphenomena, including the efficacy of server momentum in federated learning and\nthe impact of proximal client updates.\n