CoChat
Sign Up
PreprintCited by 32Distributed Control Multi-Agent SystemsStochastic Gradient Optimization TechniquesOptimization and Variational Analysis

On the Linear Convergence of Distributed Optimization over Directed Graphs

Open access
Xi, Chenguang, Khan, Usman A.·2015·arXiv
DOI 10.48550/arxiv.1510.02149arXiv 1510.02149
Open this paper in CoChat — free accountOpen PDF

Abstract

This paper develops a fast distributed algorithm, termed \emph{DEXTRA}, to solve the optimization problem when~$n$ agents reach agreement and collaboratively minimize the sum of their local objective functions over the network, where the communication between the agents is described by a~\emph{directed} graph. Existing algorithms solve the problem restricted to directed graphs with convergence rates of $O(\ln k/\sqrt{k})$ for general convex objective functions and $O(\ln k/k)$ when the objective functions are strongly-convex, where~$k$ is the number of iterations. We show that, with the appropriate step-size, DEXTRA converges at a linear rate $O(τ^{k})$ for $0

Integrity signals

Registry

DataCite · 10.48550/arxiv.1510.02149

Cites

42 of 42 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • This step-size selection requirement compares favorably to existing literature [70,76], which require detailed spectral information about the network for step-size selection.

    “This compares favorably to some of the existing literature, e.g., [70,76], which require detailed spectral information about the network for step-size selection.”

    From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [70]

  • DEXTRA converges at an R-linear rate for a time-invariant strongly connected directed graph under strong convexity, but the step-size must be carefully chosen in some interval, and the feasible set of step-sizes can even be empty.

    “It turns out that for a time-invariant strongly connected directed graph, DEXTRA converges at an R-linear rate under strong convexity assumption but the step-size has to be carefully chosen in some interval. However, the feasible set of step-sizes for DEXTRA can even be empty in some situations [70].”

    From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [70]

Cites

Flagged first, then by citations

Cited by

Sorted by citations

Related

Authors
Xi, C., & Khan, U. A.
Affiliations
Tufts University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2015
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1510.02149
arXiv
1510.02149
OpenAlex
W2205030769
Cited by
29
References
41
Citations by year
2025: 1 · 2020: 3 · 2019: 4 · 2018: 5 · 2017: 9 · 2016: 7
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Computer Networks and Communications › Distributed Control Multi-Agent Systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
Keywords
distributed optimization, directed graphs, linear convergence, consensus, multi-agent systems, convex optimization, strongly convex functions, step size selection, convergence rate

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.

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