From Local SGD to Local Fixed-Point Methods for Federated Learning

Grigory Malinovskiy, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, Peter Richtarik
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:6692-6701, 2020.

Abstract

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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v119-malinovskiy20a, title = {From Local {SGD} to Local Fixed-Point Methods for Federated Learning}, author = {Malinovskiy, Grigory and Kovalev, Dmitry and Gasanov, Elnur and Condat, Laurent and Richtarik, Peter}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {6692--6701}, year = {2020}, editor = {Hal Daumé III and Aarti Singh}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/malinovskiy20a/malinovskiy20a.pdf}, url = { http://proceedings.mlr.press/v119/malinovskiy20a.html }, abstract = {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.} }
Endnote
%0 Conference Paper %T From Local SGD to Local Fixed-Point Methods for Federated Learning %A Grigory Malinovskiy %A Dmitry Kovalev %A Elnur Gasanov %A Laurent Condat %A Peter Richtarik %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-malinovskiy20a %I PMLR %P 6692--6701 %U http://proceedings.mlr.press/v119/malinovskiy20a.html %V 119 %X 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.
APA
Malinovskiy, G., Kovalev, D., Gasanov, E., Condat, L. & Richtarik, P.. (2020). From Local SGD to Local Fixed-Point Methods for Federated Learning. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:6692-6701 Available from http://proceedings.mlr.press/v119/malinovskiy20a.html .

Related Material