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

arXiv: https://arxiv.org/abs/1905.02637 · HTML: https://mlsanity.com/paper/1905.02637/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2019.

## Built on by (most cited first, 4 of 4)

- [MDPGT: Momentum-based Decentralized Policy Gradient Tracking](https://mlsanity.com/paper/2112.02813/) (2021)
- [On Centralized and Distributed Mirror Descent: Convergence Analysis Using Quadratic Constraints](https://mlsanity.com/paper/2105.14385/) (2021)
- [Decentralized Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/2402.02356/) (2024)
- [Convergence Theory of Knowledge Distillation in Asynchronous P2P Gossip Learning Network](https://mlsanity.com/paper/2609.01952/) (2026)

## Abstract (arXiv)

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 ε>0 on the objective value in O(kappag log(1/ε)) gradient computations at each node and tildeObig(kappag (1-ρ)-1/2 log(1/ε)big) communication steps, where kappag is the condition number of F and ρ 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 kappag (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 ε>0 in Obig((β/μ) log(1/ε)big) iterations and tildeObig((β/μ) (1-ρ)-1/2 log(1/ε)big) communication steps, where β measures the degree of similarity of the agents' losses and μ is the strong convexity constant of F. Therefore, when β/μ < kappag, 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.