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

Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs

Open access
Nedic, Angelia, Olshevsky, Alex·2014·arXiv
DOI 10.48550/arxiv.1406.2075arXiv 1406.2075
Open this paper in CoChat — free accountOpen PDF

Abstract

We investigate the convergence rate of the recently proposed subgradient-push method for distributed optimization over time-varying directed graphs. The subgradient-push method can be implemented in a distributed way without requiring knowledge of either the number of agents or the graph sequence; each node is only required to know its out-degree at each time. Our main result is a convergence rate of $O \left((\ln t)/t \right)$ for strongly convex functions with Lipschitz gradients even if only stochastic gradient samples are available; this is asymptotically faster than the $O \left((\ln t)/\sqrt{t} \right)$ rate previously known for (general) convex functions.

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.1406.2075

Cites

40 of 40 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?

  • A better rate of O(ln k/k) is proved for the subgradient-push method under strong convexity and Lipschitz gradient assumptions, in terms of expected objective error plus squared consensus residual.

    “A better rate of O ( ln k k ) is proved for the (sub)gradient-push method in [24] under the strong convexity and Lipschitz gradient assumptions, in terms of expected objective error plus squared consensus residual.”

    From EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2015) · cites this paper as [24]

    The Conclusion reports an improved O(ln t/t) rate for stochastic (sub)gradient-push under strong convexity and Lipschitz-gradient assumptions. But the bound in III, Proof of Theorem 1, combines expected objective error with squared distances of node iterates from the optimizer, not squared consensus residuals; consensus deviations appear separately as unsquared terms. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • The subgradient-push method can be implemented in a dynamic digraph and, under the bounded subgradient assumption and diminishing step sizes α_k = O(1/√k), has a rate of O(ln k/√k) in the ergodic sense in terms of objective error.

    “The (sub)gradient-push method [23] can be implemented in a dynamic digraph and, under the bounded (sub)gradient assumption and diminishing step sizes α k = O ( 1 √ k ) , has a rate of O ( ln k √ k ) in the ergodic sense in terms of objective error.”

    From EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2015) · cites this paper as [23]

  • The subgradient-push algorithm suffers from a slow sublinear convergence rate even for strongly convex smooth functions due to its employment of diminishing step-size.

    “While the subgradient-push eliminates the requirement of graph balancing [22], it suffers from a slow sublinear 2 convergence rate even for strongly convex smooth functions due to its employment of diminishing step-size [41].”

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

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

1 of the 41 references couldn’t be matched to a known paper.

Research works printed but not linked: 4

  1. A. S. Nemirovski and D. B. Yudin. Problem complexity and method efficiency in optimization. John Wiley, 1983.
  2. A. Olshevsky. Efficient information aggregation for distributed control and signal processing. PhD thesis, MIT, 2010.
  3. K.I. Tsianos. The role of the Network in Distributed Optimization Algo- rithms: Convergence Rates, Scalability, Communication / Computation Tradeoffs and Communication Delays. PhD thesis, McGill University, Dept. of Electrical and Computer Engineering, 2013.
  4. K.I. Tsianos and M.G. Rabbat. Distributed strongly convex optimiza- tion. In Proc. of Allerton Conference on Communication, Control, and Computing, 2012.

Cited by

Sorted by citations

Related

Authors
Nedic, A., & Olshevsky, A.
Affiliations
University of Illinois Urbana-Champaign (US)
ORCID
Olshevsky, Alex
Venue
arXiv
Publisher
arXiv
Published
2014
Volume
61
Issue
12
Pages
3936-3947
ISSN
0018-9286 (ISSN-L)
DOI
10.48550/arxiv.1406.2075
arXiv
1406.2075
OpenAlex
W1588593629
Cited by
38
References
41
Citations by year
2025: 1 · 2023: 2 · 2021: 2 · 2020: 2 · 2019: 3 · 2018: 2 · 2017: 7 · 2016: 10 · 2015: 8 · 2014: 1
FWCI
6.92
Type
journal article
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • IEEE Transactions on Automatic Control (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
National Science Foundation (1111342)
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, time-varying directed graphs, strongly convex functions, stochastic gradient, convergence rate, out-degree, multi-agent systems

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