FedSplit: An algorithmic framework for fast federated optimization

By Reese Pathak, Martin J. Wainwright. 2020

214 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, neutral): “[29] Reese Pathak and Martin J Wainwright.”
On the Outsized Importance of Learning Rates in Local Update Methods (2020, background): “, 2019), proximal updates (Li et al., 2020a; Pathak and Wainwright, 2020) and control variates (Karimireddy et al.”
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications (2021, methodology): “To address this problem, an operator splitting method was proposed to avoid the local models drifting apart from the global model [141].”
On Large-Cohort Training for Federated Learning (2021, background): “For special cases of Algorithm 1 where clients perform multiple local training steps, ∆ is not an unbiased estimator of ∇ f (Malinovskiy et al., 2020; Pathak and Wainwright, 2020; Charles and Konečný, 2021).”
Exploiting Shared Representations for Personalized Federated Learning (2021, background): “…line of work has studied federated learning in heterogeneous settings [Haddadpour et al., 2020, Karimireddy et al., 2020, Mitra et al., 2021, Pathak and Wainwright, 2020, Reddi et al., 2020, Reisizadeh et al., 2020, Wang et al., 2020], and the optimization-based insights from these works…”
Towards Understanding Biased Client Selection in Federated Learning (2022, methodology): “…2019; Khaled et al., 2020; Stich and Karimireddy, 2020; Woodworth et al., 2020; Koloskova et al., 2020; Huo et al., 2020; Zhang et al., 2020; Pathak and Wainwright, 2020; Malinovsky et al., 2020; Sahu et al., 2020) and methods to overcome the adverse eﬀects of data and computational…”
Federated Learning Based on Dynamic Regularization (2021, methodology): “Figure 2a and 2b show comparison between FedSplit and FedDyn for 100% and 10% participation levels respectively.”
Lower Bounds and Optimal Algorithms for Personalized Federated Learning (2020, background): “Such an approach was already considered in [28, 40] for the standard FL formulation (1).”
Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies (2020, unknown): “[17] Reese Pathak and Martin J Wainwright.”
Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms (2020, background): “Using stateful clients [Karimireddy et al., 2019, Pathak and Wainwright, 2020] can help to remedy the convergence issues in the cross-silo setting, where relatively few clients are queried repeatedly, but is not practical in the cross-device setting ( i.e. , when clients are mobile devices) for…”