PreprintCited by 66Distributed Control Multi-Agent SystemsStochastic Gradient Optimization TechniquesOptimization and Variational Analysis

ExtraPush for convex smooth decentralized optimization over directed networks

Open access
Zeng, Jinshan, Yin, Wotao·2015·arXiv

Abstract

In this note, we extend the algorithms Extra and subgradient-push to a new algorithm ExtraPush for consensus optimization with convex differentiable objective functions over a directed network. When the stationary distribution of the network can be computed in advance}, we propose a simplified algorithm called Normalized ExtraPush. Just like Extra, both ExtraPush and Normalized ExtraPush can iterate with a fixed step size. But unlike Extra, they can take a column-stochastic mixing matrix, which is not necessarily doubly stochastic. Therefore, they remove the undirected-network restriction of Extra. Subgradient-push, while also works for directed networks, is slower on the same type of problem because it must use a sequence of diminishing step sizes. We present preliminary analysis for ExtraPush under a bounded sequence assumption. For Normalized ExtraPush, we show that it naturally produces a bounded, linearly convergent sequence provided that the objective function is strongly convex. In our numerical experiments, ExtraPush and Normalized ExtraPush performed similarly well. They are significantly faster than subgradient-push, even when we hand-optimize the step sizes for the latter.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1511.02942

Cites

17 of 17 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

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 [76]

    Theorem 4 (p. 8) gives a condition on the step size, and the discussion on p. 9 relates the convergence bound to eigenvalues of network-derived matrices. But p. 9 calls the step-size condition sufficient, not necessary, and §6.1 (p. 12) selects step sizes by hand. The paper therefore supports a spectral dependence in its theoretical bound, not the categorical claim that step-size selection requires detailed spectral information. (LLM, conf=0.79)

    Experimental — accuracy not yet measured

Self-check

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

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 2

  1. [3][3] F. Chung, Laplancians and the cheeger inequality for directed graphs, Annals of Combinatorics , 2 (2005), 1-19. -
  2. [17][17] K. I. Tsianos, The role of the Network in Distributed Optimization Algorithms: Convergence Rates, Scalability, Communication/Computation Tradeoffs and Communication Delays, PhD thesis, Dept. Elect. Comp. Eng., McGill Univ., Montreal, QC, Canada, 2013. -

Cited by

Sorted by citations

Authors
Zeng, J., & Yin, W.
Affiliations
  • Jiangxi Normal University (CN)
  • University of California, Los Angeles (US)
Venue
arXiv
Publisher
arXiv
Published
2015
Volume
35
Issue
4
Pages
383-396
ISSN
0254-9409 (ISSN-L)
OpenAlex
W2223126829
Cited by
65
References
17
Citations by year
2026: 1 · 2025: 6 · 2024: 5 · 2023: 2 · 2022: 4 · 2021: 6 · 2020: 11 · 2019: 10 · 2018: 9 · 2017: 7 · 2016: 3 · 2015: 1
FWCI
6.73
Type
journal article
Language
en
Open access
Locations
  • Journal of Computational Mathematics (publishedVersion, cc-by)
  • 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, consensus optimization, directed graphs, stationary distribution, linear convergence, strongly convex functions, fixed step size

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