FedSplit: An algorithmic framework for fast federated optimization

Abstract

Motivated by federated learning, we consider the hub-and-spoke model of distributed optimization in which a central authority coordinates the computation of a solution among many agents while limiting communication. We first study some past procedures for federated optimization, and show that their fixed points need not correspond to stationary points of the original optimization problem, even in simple convex settings with deterministic updates. In order to remedy these issues, we introduce FedSplit, a class of algorithms based on operator splitting procedures for solving distributed convex minimization with additive structure. We prove that these procedures have the correct fixed points, corresponding to optima of the original optimization problem, and we characterize their convergence rates under different settings. Our theory shows that these methods are provably robust to inexact computation of intermediate local quantities. We complement our theory with some simple experiments that demonstrate the benefits of our methods in practice.

27 pages, 4 figures

References in corpus (6)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Towards Federated Learning at Scale: System Design
• Optimal Distributed Online Prediction using Mini-Batches
• Protection Against Reconstruction and Its Applications in Private Federated Learning
• Distributed Coordinate Descent Method for Learning with Big Data
• Is Local SGD Better than Minibatch SGD?

Cited by in corpus (31)

• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
• Federated Learning Based on Dynamic Regularization
• Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
• Exploiting Shared Representations for Personalized Federated Learning
• Lower Bounds and Optimal Algorithms for Personalized Federated Learning
• Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning
• The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms
• Fed-ensemble: Improving Generalization through Model Ensembling in Federated Learning
• Federated Learning Meets Multi-objective Optimization
• FedCM: Federated Learning with Client-level Momentum
• Federated Accelerated Stochastic Gradient Descent
• Local Adaptivity in Federated Learning: Convergence and Consistency
• On the Outsized Importance of Learning Rates in Local Update Methods
• FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
• What Do We Mean by Generalization in Federated Learning?
• Federated Composite Optimization
• Local SGD: Unified Theory and New Efficient Methods
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learning
• Fast Convergence Algorithm for Analog Federated Learning
• On the Convergence of Nested Decentralized Gradient Methods with Multiple Consensus and Gradient Steps
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• An Operator Splitting View of Federated Learning
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• FLIX: A Simple and Communication-Efficient Alternative to Local Methods in Federated Learning
• Statistical Estimation and Inference via Local SGD in Federated Learning
• Iterated Vector Fields and Conservatism, with Applications to Federated Learning
• Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications