# Optimal Convergence Rates for Convex Distributed Optimization in Networks

2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
7 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, 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.
Keywords :
Document type :
Journal articles
Domain :

Cited literature [51 references]

https://hal.inria.fr/hal-02440504
Contributor : Kevin Scaman <>
Submitted on : Wednesday, January 15, 2020 - 11:14:48 AM
Last modification on : Saturday, January 18, 2020 - 1:20:18 AM
Document(s) archivé(s) le : Thursday, April 16, 2020 - 1:56:59 PM

### File

scaman_optimal_convergence.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-02440504, version 1

### Citation

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⟩

Record views