From Local SGD to Local Fixed Point Methods for Federated Learning

By Grigory Malinovsky, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, Peter Richtárik. 2020

139 citations recorded by the source corpus.

Most algorithms for solving optimization problems or finding saddle points of convex-concave functions are fixed-point algorithms. In this work we consider the generic problem of finding a fixed point of an average of operators, or an approximation thereof, in a distributed setting. Our work is motivated by the needs of federated learning. In this context, each local operator models the computations done locally on a mobile device. We investigate two strategies to achieve such a consensus: one based on a fixed number of local steps, and the other based on randomized computations. In both cases, the goal is to limit communication of the locally-computed variables, which is often the bottleneck in distributed frameworks. We perform convergence analysis of both methods and conduct a number of experiments highlighting the benefits of our approach.

Subfields: Artificial Intelligence, Computational Mechanics

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 Mechanics

Citations in the corpus

On the Outsized Importance of Learning Rates in Local Update Methods (2020, background): “(2020c), and later shown in (Malinovsky et al., 2020) and (Pathak and Wainwright, 2020).”
Towards Understanding Biased Client Selection in Federated Learning (2022, unknown): “…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 heterogeneity are proposed by Sahu…”
Distributed Proximal Splitting Algorithms with Rates and Acceleration (2020, background): “This is important for distributed or federated learning [16, 18].”
Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies (2020, background): “[18] Grigory Malinovsky, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik.”
Federated Learning Based on Dynamic Regularization (2021, background): “…training models on local data that minimize local empirical loss appears to be meaningful, but yet, doing so, ∗Boston University, Boston, MA †Arm ML Research Lab, Boston, MA is fundamentally inconsistent with minimizing the global empirical loss1 (Malinovsky et al., 2020; Khaled et al., 2020a) .”
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).”
A Comprehensive Survey of Privacy-preserving Federated Learning (2021, background): “The focuses of FL research can be roughly divided into three aspects: (1) improving the efficiency and effectiveness of FL [24, 68, 87, 100, 120, 211, 213], (2) improving the security of FL to attacks that aim to undermine the integrity of FL models and degrade the model performance [9, 13, 185, 198”