CoChat

Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs

Open access
Nedić, Angelia, Olshevsky, Alex, Shi, Wei · 2017 · SIAM Journal on Optimization

The DOI matches its Crossref record; 89 of the 89 references it cites were found in a registry or an index; 10 of the 34 sources its claims cite were checked for support.

Abstract

This paper considers the problem of distributed optimization over time-varying graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, based on a combination of a distributed inexact gradient method and a gradient tracking technique. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all the agents' iterates to a global and consensual minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining the Push-DIGing algorithm. Push-DIGing uses column stochastic matrices and fixed step-sizes, but it still converges to a global and consensual minimizer. Under the strong convexity assumption, we prove that the algorithms converge at R-linear (geometric) rates as long as the step-sizes do not exceed some upper bounds. We establish explicit estimates for the convergence rates. When the graph is undirected it shows that DIGing scales polynomially in the number of agents. We also provide some numerical experiments to demonstrate the efficacy of the proposed algorithms and to validate our theoretical findings.

Overview

CoChat Summary

TL;DR

The paper introduces DIGing for distributed optimization over time-varying undirected graphs and Push-DIGing for time-varying directed graphs, both using fixed step-sizes and gradient tracking. Under strong convexity and smoothness, it proves global R-linear (geometric) convergence and gives explicit rate bounds.

Key findings

  • DIGing uses doubly stochastic mixing matrices and fixed step-sizes; under Assumptions 1, 4, and 5, it converges to the unique optimum at a global R-linear rate \(O(\lambda^k)\) for step-sizes \(\alpha \in (0, 1.5(1-\delta)^2 \bar{\mu} J_1]\).
  • Push-DIGing incorporates the push-sum protocol with column stochastic matrices and fixed step-sizes; under Assumptions 4–7, it also converges at a global R-linear rate \(O(\lambda^k)\) for \(\alpha \in (0, 1.5(1-\delta)^2 \bar{\mu} J_2]\).
  • For undirected graphs, Corollary 11 gives iteration complexity \(O(\tau^{-2} B^3 n^{4.5} \bar{\kappa}^{1.5} \ln(1/\varepsilon))\), polynomial in the number of agents \(n\). For lazy Metropolis mixing on time-invariant connected undirected graphs, Corollary 12 gives rate \(\lambda = 1 - 1/(161312\, n^{4.5} \bar{\kappa}^{1.5})\) and iteration complexity \(O(n^{4.5} \bar{\kappa}^{1.5} \ln(1/\varepsilon))\).
  • Numerical experiments with \(n=12\), \(m_i=1\), \(p=3\), and Huber loss show DIGing and variants have R-linear rates, while the push-gradient method has only sublinear rate; DIGing-ATC is faster in iterations than DIGing but has higher per-iteration communication cost, and Push-DIGing can be as fast as DIGing-ATC at half communication cost per iteration.

Methods

  • The paper studies distributed convex optimization \(\min \sum_{i=1}^n f_i(x)\) over time-varying undirected and directed graphs, assuming smoothness with Lipschitz gradients and strong convexity of at least one local function.
  • It proposes DIGing: \(x(k+1)=W(k)x(k)-\alpha y(k)\), \(y(k+1)=W(k)y(k)+\nabla f(x(k+1))-\nabla f(x(k))\), and Push-DIGing, which adds push-sum variables \(u,v,V\) and uses column stochastic matrices.
  • Convergence analysis uses the small-gain theorem with an ergodic norm and a cycle of arrows \(q \to z \to \check{y} \to \check{x} \to q\); numerical experiments compare push-gradient, DIGing, DIGing-ATC, and Push-DIGing on time-invariant directed, time-varying undirected, and time-varying directed graphs.

Limitations

  • The paper states an open question is obtaining improved estimates on convergence rates, especially scaling with the number of agents \(n\), and extensions to local constraints and couplings among agents.
  • Step-size selection requires agents to agree on common upper bounds on \(n\) and \(B\), plus lower \(\bar{\mu}\) and upper \(L\); the paper assumes all agents use the same step-size, though it notes uncoordinated step-sizes are possible in subsequent work.
  • The paper states its bounds on step-sizes are often conservative and uses hand-optimized step-sizes in experiments; the numerical experiments use a small network of \(n=12\), so the empirical validation is limited in scale.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1137/16m1084316

Cites

89 of 89 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

9 Valid · 0 Not valid · 10 Not checked · 37 Own results and interpretations

25 more claims

Create a free account to see all 56 claims and to verify the 2 references still open.

See all claims — free account
  • It may state two separate claims as one. 13
  • Probably not a substantial claim. 14
  • The quote only partly states this claim. 1

Create a free account to see these claims.

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

2 of 2

Citations

Cites

Show all 89 references

Research works printed but not linked: 9

  1. Chen A., 2012, Allerton, 601
  2. Di Lorenzo P., 2015, Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 229
  3. Forero P., 2010, J. Mach. Learn. Res., 59, 1663
  4. Mokhtari A., 2016, J. Mach. Learn. Res., 17, 1
  5. Nedić A., 2008, UK, 3
  6. A. Olshevsky, Efficient Information Aggregation Strategies for Distributed Control and Signal Processing , Ph.D. thesis, Massachusetts Institute of Technology, 2010.
  7. Rabbat M., 2004, New York, 20
  8. Ram S., 2009, Proceedings of INFOCOM, 3001
  9. Sayed A., 2013, New York, 323

Cited by

See all 1,070

Metadata

Authors
Nedić, A., Olshevsky, A., & Shi, W.
Affiliations
  • Boston University (US)
  • Arizona State University (US)
Venue
SIAM Journal on Optimization
Published
2017-01
Volume
27
Issue
4
Pages
2597-2633
ISSN
  • 1052-6234 (ISSN-L)
  • 1095-7189
OpenAlex
W2963649943
Cited by
1,069
References
38
Citations by year
2026: 95 · 2025: 147 · 2024: 130 · 2023: 124 · 2022: 118 · 2021: 114 · 2020: 138 · 2019: 106 · 2018: 64 · 2017: 29
FWCI
46.51
Type
journal article
Language
en
Open access
Locations
  • SIAM Journal on Optimization (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • U.S. Air Force (AF FA95501510394)
  • Office of Naval Research (N00014-12-1-0998)
  • National Science Foundation (CNS 15-44953)
Topics
  • Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
Keywords
distributed optimization, dynamic graphs, geometric convergence, R-linear convergence, gradient tracking, strong convexity, fixed step size, undirected graphs, directed graphs

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

The claim verdicts this report counts are experimental: their accuracy is not yet measured.

A language model drew the claims from the paper on 2026-10-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-10 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Cited sources are checked with a language model’s help (qwen3.8-omni-flash and gpt-6-sol).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs. https://app.cochat.ai/papers/10.1137/16m1084316
The paper
Nedić, A., Olshevsky, A., & Shi, W. (2017). Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs. SIAM Journal on Optimization. https://doi.org/10.1137/16m1084316

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.