Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?
arXiv:2103.01901
Abstract
A widely recognized difficulty in federated learning arises from the statistical heterogeneity among clients: local datasets often originate from distinct yet not entirely unrelated probability distributions, and personalization is, therefore, necessary to achieve optimal results from each individual's perspective. In this paper, we show how the excess risks of personalized federated learning using a smooth, strongly convex loss depend on data heterogeneity from a minimax point of view, with a focus on the FedAvg algorithm (McMahan et al., 2017) and pure local training (i.e., clients solve empirical risk minimization problems on their local datasets without any communication). Our main result reveals an approximate alternative between these two baseline algorithms for federated learning: the former algorithm is minimax rate optimal over a collection of instances when data heterogeneity is small, whereas the latter is minimax rate optimal when data heterogeneity is large, and the threshold is sharp up to a constant. As an implication, our results show that from a worst-case point of view, a dichotomous strategy that makes a choice between the two baseline algorithms is rate-optimal. Another implication is that the popular FedAvg following by local fine tuning strategy is also minimax optimal under additional regularity conditions. Our analysis relies on a new notion of algorithmic stability that takes into account the nature of federated learning.
JMLR published version
References in corpus (32)
- Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- Federated Learning with Personalization Layers
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- FedMD: Heterogenous Federated Learning via Model Distillation
- Federated Optimization in Heterogeneous Networks
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Improving Federated Learning Personalization via Model Agnostic Meta Learning
- Personalized Federated Learning: A Meta-Learning Approach
- Adaptive Personalized Federated Learning
- Three Approaches for Personalization with Applications to Federated Learning
- Federated Learning of a Mixture of Global and Local Models
- Local SGD Converges Fast and Communicates Little
- On the Convergence of Local Descent Methods in Federated Learning
- The Benefit of Multitask Representation Learning
- Salvaging Federated Learning by Local Adaptation
- First Analysis of Local GD on Heterogeneous Data
- On the Theory of Transfer Learning: The Importance of Task Diversity
- Lower Bounds and Optimal Algorithms for Personalized Federated Learning
- Deep learning with Elastic Averaging SGD
- Few-Shot Learning via Learning the Representation, Provably
- Provable Meta-Learning of Linear Representations
- Minibatch vs Local SGD for Heterogeneous Distributed Learning
- Learning-to-Learn Stochastic Gradient Descent with Biased Regularization
- A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
- Transfer Learning for High-dimensional Linear Regression: Prediction, Estimation, and Minimax Optimality
- The Complexity of Making the Gradient Small in Stochastic Convex Optimization
- On the Value of Target Data in Transfer Learning
- Distributed Stochastic Multi-Task Learning with Graph Regularization
- Transfer Learning for Nonparametric Classification: Minimax Rate and Adaptive Classifier
- Minimax Lower Bounds for Transfer Learning with Linear and One-hidden Layer Neural Networks
- How Important is the Train-Validation Split in Meta-Learning?