Lower Bounds and Optimal Algorithms for Personalized Federated Learning

Abstract

In this work, we consider the optimization formulation of personalized federated learning recently introduced by Hanzely and Richtárik (2020) which was shown to give an alternative explanation to the workings of local {\tt SGD} methods. Our first contribution is establishing the first lower bounds for this formulation, for both the communication complexity and the local oracle complexity. Our second contribution is the design of several optimal methods matching these lower bounds in almost all regimes. These are the first provably optimal methods for personalized federated learning. Our optimal methods include an accelerated variant of {\tt FedProx}, and an accelerated variance-reduced version of {\tt FedAvg}/Local {\tt SGD}. We demonstrate the practical superiority of our methods through extensive numerical experiments.

NeurIPS 2020

References in corpus (25)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning with Non-IID Data
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Federated Learning for Mobile Keyboard Prediction
• Federated Optimization in Heterogeneous Networks
• Personalized Federated Learning: A Meta-Learning Approach
• Adaptive Personalized Federated Learning
• Three Approaches for Personalization with Applications to Federated Learning
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Federated Learning of a Mixture of Global and Local Models
• Variational Federated Multi-Task Learning
• FedSplit: An algorithmic framework for fast federated optimization
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• Private Federated Learning with Domain Adaptation
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• A Lower Bound for the Optimization of Finite Sums
• Direct Acceleration of SAGA using Sampled Negative Momentum
• Personalized Federated Learning for Intelligent IoT Applications: A Cloud-Edge based Framework
• Semi-Cyclic Stochastic Gradient Descent
• Distributed Stochastic Multi-Task Learning with Graph Regularization
• Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization
• L-SVRG and L-Katyusha with Arbitrary Sampling
• Lower Bounds for Parallel and Randomized Convex Optimization
• Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems

Cited by in corpus (24)

• A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection
• Ditto: Fair and Robust Federated Learning Through Personalization
• SecureBoost: A Lossless Federated Learning Framework
• Federated Multi-Task Learning under a Mixture of Distributions
• Federated Learning on Non-IID Data Silos: An Experimental Study
• Personalized and privacy-preserving federated heterogeneous medical image analysis with PPPML-HMI
• A Contribution-based Device Selection Scheme in Federated Learning
• FedCM: Federated Learning with Client-level Momentum
• Personalized Federated Learning through Local Memorization
• Model-Contrastive Federated Learning
• What Do We Mean by Generalization in Federated Learning?
• FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
• Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?
• Federated Composite Optimization
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• A Robust Federated Learning Approach for Combating Attacks Against IoT Systems Under non-IID Challenges
• Practical and Secure Federated Recommendation with Personalized Masks
• Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques
• Personalised Federated Learning On Heterogeneous Feature Spaces
• QuPeD: Quantized Personalization via Distillation with Applications to Federated Learning
• A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Private Multi-Task Learning: Formulation and Applications to Federated Learning
• Strategyproof Learning: Building Trustworthy User-Generated Datasets
• One-Point Feedback for Composite Optimization with Applications to Distributed and Federated Learning