Optimal Convergence Rates for Convex Distributed Optimization in Networks - Archive ouverte HAL Access content directly
Journal Articles Journal of Machine Learning Research Year : 2019

## Optimal Convergence Rates for Convex Distributed Optimization in Networks

(1) , (2, 3) , (4) , (5) , (6, 7)
1
2
3
4
5
6
7
Kevin Scaman
• Function : Author
• PersonId : 1062981
Francis Bach
• Function : Author
• PersonId : 863086
Sébastien Bubeck
• Function : Author
Yin Tat Lee
• Function : Author
Laurent Massoulié
• Function : Author
• PersonId : 933636

#### 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.

### Dates and versions

hal-02440504 , version 1 (15-01-2020)

### Identifiers

• HAL Id : hal-02440504 , version 1

### Cite

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

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

108 View