DISTRIBUTED OPTIMIZATION BASED ON GRADIENT TRACKING REVISITED: ENHANCING CONVERGENCE RATE VIA SURROGATION

Ying Sun, Gesualdo Scutari, Amir Daneshmand

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

We study distributed multiagent optimization over graphs. We consider the minimization of F + G subject to convex constraints, where F is the smooth strongly convex sum of the agent's losses and G is a nonsmooth convex function. We build on the SONATA algorithm: the algorithm employs the use of surrogate objective functions in the agents' subproblems (thus going beyond linearization, such as proximal-gradient) coupled with a perturbed consensus mechanism that aims to locally track the gradient of F. SONATA achieves precision \epsilon > 0 on the objective value in \scrO (\kappa g log(1/\epsilon )) gradient computations at each node and \scrO \~\bigl(\kappa g(1 - \rho ) -1/2 log(1/\epsilon )\bigr) communication steps, where \kappa g is the condition number of F and \rho characterizes the connectivity of the network. This is the first linear rate result for distributed composite optimization; it also improves on existing (nonaccelerated) schemes just minimizing F, whose rate depends on much larger quantities than \kappa g. When the loss functions of the agents are similar, due to statistical data similarity or otherwise, SONATA employing high-order surrogates achieves precision \epsilon > 0 in \scrO \bigl((\beta /\mu ) log(1/\epsilon )\bigr) iterations and \scrO \~\bigl((\beta /\mu )(1 - \rho ) -1/2 log(1/\epsilon )\bigr) communication steps, where \beta measures the degree of similarity of agents' losses and \mu is the strong convexity constant of F. Therefore, when \beta /\mu < \kappa g, the use of high-order surrogates yields provably faster rates than those achievable by first-order models; this is without exchanging any Hessian matrix over the network.

Original languageEnglish (US)
Pages (from-to)354-385
Number of pages32
JournalSIAM Journal on Optimization
Volume32
Issue number2
DOIs
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'DISTRIBUTED OPTIMIZATION BASED ON GRADIENT TRACKING REVISITED: ENHANCING CONVERGENCE RATE VIA SURROGATION'. Together they form a unique fingerprint.

Cite this