Geometrically convergent distributed optimization with uncoordinated step-sizes
Open accessAbstract
A recent algorithmic family for distributed optimization, DIGing's, have been shown to have geometric convergence over time-varying undirected/directed graphs [1]. Nevertheless, an identical step-size for all agents is needed. In this paper, we study the convergence rates of the Adapt-Then-Combine (ATC) variation of the DIGing algorithm under uncoordinated step-sizes. We show that the ATC variation of DIGing algorithm converges geometrically fast even if the step-sizes are different among the agents. In addition, our analysis implies that the ATC structure can accelerate convergence compared to the distributed gradient descent (DGD) structure which has been used in the original DIGing algorithm.
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.
Integrity signals
Registry
Cites
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.
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?
Allowing agents to use uncoordinated (different) step-sizes, all satisfying an upper bound, is possible.
“Allowing the agents to use uncoordinated (different) stepsizes (all satisfying an upper bound) is possible; see our very recent subsequent work [44] as well as the related papers [31,74].”
From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [44]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
The citation lists haven’t been fetched yet
References 26 · Cited by 145
Research works printed but not linked: 5
- W. Ren, "Consensus Based Formation Control Strategies for Multi-Vehicle Systems," in Proceedings of the American Control Conference, 2006, pp. 4237-4242.
- A. Nedić, A. Olshevsky, and C. Uribe, "Fast Convergence Rates for Distributed Non-Bayesian Learning," arXiv preprint arXiv:1508.05161, 2015. · arXiv
- A. Mokhtari, W. Shi, Q. Ling, and A. Ribeiro, "DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers," arXiv preprint arXiv:1508.02073, 2015. · arXiv
- J. Zeng and W. Yin, "ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks," arXiv preprint arXiv:1511.02942, 2015. · arXiv
- J. Xu, "Augmented Distributed Optimization for Networked Systems," Ph.D. dissertation, Nanyang Technological University, 2016.
- Authors
- Nedic, A., Olshevsky, A., Shi, W., & Uribe, C. A.
- Affiliations
- Boston University (US)
- Venue
- 2017 American Control Conference (ACC)
- Publisher
- IEEE
- Published
- 2017-05
- Pages
- 3950-3955
- ISSN
- 0743-1619 (ISSN-L)
- OpenAlex
- W2523259601
- Cited by
- 145
- References
- 26
- Citations by year
- 2026: 4 · 2025: 11 · 2024: 16 · 2023: 11 · 2022: 18 · 2021: 15 · 2020: 26 · 2019: 23 · 2018: 10 · 2017: 10 · 2016: 1
- FWCI
- 15.04
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Proceedings of the ... American Control Conference/Proceedings of the American Control Conference (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation
- University of Illinois at Urbana-Champaign
- Air Force Office of Scientific Research
- 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 › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- distributed optimization, geometric convergence, convergence rate, dynamic graphs, directed graphs, undirected graphs, distributed gradient descent, convergence acceleration
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
