Distributed Optimization Based on Gradient-tracking Revisited: Enhancing Convergence Rate via Surrogation

DOI10.1137/19M1259973MaRDI QIDQ6318348arXivFDO

Authors Ying Sun, Gesualdo Scutari, Amir Daneshmand

Publication date 7 May 2019

Published in arXiv

Full work available at URL https://doi.org/10.1137/19M1259973

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

arXiv classification

cs.DCmath.OC

Abstract: We study distributed multiagent optimization over (directed, time-varying) 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 (going thus beyond linearization, such as proximal-gradient) coupled with a perturbed (push-sum) consensus mechanism that aims to track locally the gradient of $F$. SONATA achieves precision $epsilon>0$ on the objective value in $mathcalO(kapp{a}_{g}log(1/epsilon))$ gradient computations at each node and $$ communication steps, where $kapp{a}_g$ is the condition number of $F$ and $ho$ characterizes the connectivity of the network. This is the first linear rate result for distributed composite optimization; it also improves on existing (non-accelerated) schemes just minimizing $F$, whose rate depends on much larger quantities than $kapp{a}_g$ (e.g., the worst-case condition number among the agents). When considering in particular empirical risk minimization problems with statistically similar data across the agents, SONATA employing high-order surrogates achieves precision $epsilon>0$ in $$ iterations and $$ communication steps, where $$ measures the degree of similarity of the agents' losses and $mu$ is the strong convexity constant of $F$. Therefore, when $$, the use of high-order surrogates yields provably faster rates than what achievable by first-order models; this is without exchanging any Hessian matrix over the network.

This page was built for publication: Distributed Optimization Based on Gradient-tracking Revisited: Enhancing Convergence Rate via Surrogation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6318348)