Name
Abstract | ||
|---|---|---|
We study distributed, strongly convex and nonconvex, multiagent optimization over (directed, time-varying) graphs. We consider the minimization of the sum of a smooth (possibly nonconvex) function--the agent's sum-utility plus a nonsmooth convex one, subject to convex constraints. In a companion paper, we introduced SONATA, the first algorithmic framework applicable to such a general class of composite minimization, and we studied its convergence when the smooth part of the objective function is nonconvex. The algorithm combines successive convex approximation techniques with a perturbed push-sum consensus mechanism that aims to track locally the gradient of the (smooth part of the) sum-utility. This paper studies the convergence rate of SONATA. When the smooth part of the objective function is strongly convex, SONATA is proved to converge at a linear rate whereas sublinar rate is proved when the objective function is nonconvex. To our knowledge, this is the first work proving a convergence rate (in particular, linear rate) for distributed algorithms applicable to such a general class of composite, constrained optimization problems over graphs. |
Year | Venue | DocType |
|---|---|---|
2019 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1905.02637 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ying Sun | 1 | 41 | 13.51 |
| Amir Daneshmand | 2 | 10 | 1.81 |
| Gesualdo Scutari | 3 | 2397 | 140.91 |