CoChat
Sign Up
Cited by 947Distributed Control Multi-Agent SystemsStochastic Gradient Optimization TechniquesAdvanced Control Systems Optimization

Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

Open access
Duchi, J. C., Agarwal, A., Wainwright, M. J.·2012·IEEE Transactions on Automatic Control
DOI 10.1109/tac.2011.2161027
Open this paper in CoChat — free accountOpen PDF

Abstract

The goal of decentralized optimization over a network is to optimize a global objective formed by a sum of local (possibly nonsmooth) convex functions using only local computation and communication. It arises in various application domains, including distributed tracking and localization, multi-agent coordination, estimation in sensor networks, and large-scale machine learning. We develop and analyze distributed algorithms based on dual subgradient averaging, and we provide sharp bounds on their convergence rates as a function of the network size and topology. Our analysis allows us to clearly separate the convergence of the optimization algorithm itself and the effects of communication dependent on the network structure. We show that the number of iterations required by our algorithm scales inversely in the spectral gap of the network, and confirm this prediction's sharpness both by theoretical lower bounds and simulations for various networks. Our approach includes the cases of deterministic optimization and communication, as well as problems with stochastic optimization and/or communication.

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

Crossref · 10.1109/tac.2011.2161027

Cites

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

  • Previous research [18], [25], [5] studied the case when the matrices A(t) are doubly stochastic, which occurs when the directed graph sequence is regular; in this case, the paper's polynomial bounds match previously known results.

    “Finally, we note that previous research [18], [25], [5] has studied the case when the matrices A ( t ) in (3) are doubly stochastic, which occurs when the directed graph sequence { G ( t ) } is regular. In this case, our polynomial bounds match the previously known results.”

    From Distributed Optimization Over Time-Varying Directed Graphs (2015) · cites this paper as [5]

    Section 3.2 states that a degree-regular undirected graph yields a doubly stochastic communication matrix, and Theorem 3 studies time-varying doubly stochastic matrices. The source does not establish the stated relationship for a regular directed graph sequence. The comparison of polynomial bounds is the citing authors’ own conclusion, not a result attributed to this source. (LLM, conf=0.83)

    Experimental — accuracy not yet measured

  • It is standard for a distributed subgradient method to converge at the rate O(ln t/√t) with the constant depending on the subgradient-norm upper bounds L_i and the initial conditions x_i(0).

    “Specifically, it is standard for a distributed subgradient method to converge at the rate of O (ln t/ √ t ) with the constant depending on the subgradient-norm upper bounds L i and the initial conditions x i (0) [25], [5].”

    From Distributed Optimization Over Time-Varying Directed Graphs (2015) · cites this paper as [5]

    Theorem 2 (Section 3.2; page unavailable) gives an O(log(T√n)/√T) error bound for distributed dual averaging, with a constant depending on the common subgradient bound L and the network spectral gap. It does not state that the constant depends on individual bounds L_i or the initial conditions x_i(0); its bound instead uses the assumption ψ(x*) ≤ R². (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • The dual averaging method has a rate of O(ln k/√k) in the ergodic sense in terms of objective error.

    “[8] shows that the dual averaging method 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 [8]

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: 13

  1. F. Bénézit, A. Dimakis, P. Thiran, and M. Vetterli, Order-optimal consensus through randomized path averaging, IEEE Transactions on Information Theory 56 (2010), no. 10, 5150-5167.
  2. P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains, The Annals of Probability 1 (1991), no. 1, 36-61.
  3. A. G. Dimakis, A. Sarwate, and M. J. Wainwright, Geographic gossip: Efficient averag- ing for sensor networks, IEEE Transactions on Signal Processing 53 (2008), 1205-1216.
  4. G. B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations Research 8 (1960), 101-111.
  5. D. A. Freedman, On tail probabilities for martingales, The Annals of Probability 3 (1975), no. 1, 100-118.
  6. J. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I, Springer, 1996.
  7. Convex Analysis and Minimization Algorithms II, Springer, 1996.
  8. V. Lesser, C. Ortiz, and M. Tambe (eds.), Distributed Sensor Networks: A Multiagent Perspective, vol. 9, Kluwer Academic Publishers, 2003.
  9. R. McDonald, K. Hall, and G. Mann, Distributed training strategies for the structured perceptron, North American Chapter of the Association for Computational Linguistics (NAACL), 2010.
  10. A. Nedic and D. P. Bertsekas, Incremental subgradient methods for nondifferentiable optimization, SIAM Journal on Optimization 12 (2001), no. 1, 109-138.
  11. A. Nemirovski and D. Yudin, Problem complexity and method efficiency in optimization, Wiley, New York, 1983.
  12. M. Rabbat and R. Nowak, Distributed optimization in sensor networks, The 3rd Inter- national Symposium on Information Processing in Sensor Networks, 2004, pp. 20-27.
  13. J. Tsitsiklis, Problems in decentralized decision making and computation, Ph.D. thesis, Massachusetts Institute of Technology, 1984.

Cited by

Sorted by citations

Authors
Duchi, J. C., Agarwal, A., & Wainwright, M. J.
Affiliations
University of California, Berkeley (US)
ORCID
Wainwright, M. J.
Venue
IEEE Transactions on Automatic Control
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Published
2012-03
Volume
57
Issue
3
Pages
592-606
ISSN
  • 0018-9286 (ISSN-L)
  • 1558-2523
DOI
10.1109/tac.2011.2161027
OpenAlex
W2148087609
Cited by
947
References
22
Citations by year
2026: 45 · 2025: 62 · 2024: 53 · 2023: 73 · 2022: 83 · 2021: 79 · 2020: 118 · 2019: 89 · 2018: 79 · 2017: 76 · 2016: 70 · 2015: 44 · 2014: 38 · 2013: 18 · 2012: 17
FWCI
31.37
Type
journal article
Language
en
Open access
Licence
ieeexplore.ieee.org/Xplorehelp/downloads/license-information/IEEE.html (vor)
Locations
  • IEEE Transactions on Automatic Control (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (CAREER, 0545862)
  • Microsoft Research
  • National Defense Science and Engineering Graduate
  • Air Force Office of Scientific Research (09NL184)
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 › Engineering › Control and Systems Engineering › Advanced Control Systems Optimization
Keywords
distributed optimization, dual averaging, convergence rate, network scaling, spectral gap, nonsmooth convex optimization, stochastic optimization, communication effects, network topology, multi-agent coordination, sensor networks

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