Skip to Main content Skip to Navigation
Journal articles

Optimal Convergence Rates for Convex Distributed Optimization in Networks

Kevin Scaman 1 Francis Bach 2, 3 Sébastien Bubeck 4 Yin Lee 5 Laurent Massoulié 6, 7
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique - ENS Paris, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
7 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique - ENS Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : This work proposes a theoretical analysis of distributed optimization of convex functions using a network of computing units. We investigate this problem under two communication schemes (centralized and decentralized) and four classical regularity assumptions: Lipschitz continuity, strong convexity, smoothness, and a combination of strong convexity and smoothness. Under the decentralized communication scheme, we provide matching upper and lower bounds of complexity along with algorithms achieving this rate up to logarithmic constants. For non-smooth objective functions, while the dominant term of the error is in $O(1/\sqrt{t})$, the structure of the communication network only impacts a second-order term in $O(1/t)$, where $t$ is time. In other words, the error due to limits in communication resources decreases at a fast rate even in the case of non-strongly convex objective functions. Such a convergence rate is achieved by the novel multi-step primal-dual (MSPD) algorithm. Under the centralized communication scheme, we show that the naive distribution of standard optimization algorithms is optimal for smooth objective functions, and provide a simple yet efficient algorithm called distributed randomized smoothing (DRS) based on a local smoothing of the objective function for non-smooth functions. We then show that DRS is within a $d^{1/4}$ multiplicative factor of the optimal convergence rate, where $d$ is the underlying dimension.
Complete list of metadata

Cited literature [51 references]  Display  Hide  Download
Contributor : Kevin Scaman Connect in order to contact the contributor
Submitted on : Wednesday, January 15, 2020 - 11:14:48 AM
Last modification on : Tuesday, January 11, 2022 - 11:16:05 AM
Long-term archiving on: : Thursday, April 16, 2020 - 1:56:59 PM


Files produced by the author(s)


  • HAL Id : hal-02440504, version 1



Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Lee, Laurent Massoulié. Optimal Convergence Rates for Convex Distributed Optimization in Networks. Journal of Machine Learning Research, Microtome Publishing, 2019, 20, pp.1 - 31. ⟨hal-02440504⟩



Les métriques sont temporairement indisponibles