Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Open accessThe DOI matches its Crossref record; 89 of the 89 references it cites were found in a registry or an index; 10 of the 34 sources its claims cite were checked for support.
Abstract
This paper considers the problem of distributed optimization over time-varying graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, based on a combination of a distributed inexact gradient method and a gradient tracking technique. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all the agents' iterates to a global and consensual minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining the Push-DIGing algorithm. Push-DIGing uses column stochastic matrices and fixed step-sizes, but it still converges to a global and consensual minimizer. Under the strong convexity assumption, we prove that the algorithms converge at R-linear (geometric) rates as long as the step-sizes do not exceed some upper bounds. We establish explicit estimates for the convergence rates. When the graph is undirected it shows that DIGing scales polynomially in the number of agents. We also provide some numerical experiments to demonstrate the efficacy of the proposed algorithms and to validate our theoretical findings.
Overview
CoChat Summary
TL;DR
The paper introduces DIGing for distributed optimization over time-varying undirected graphs and Push-DIGing for time-varying directed graphs, both using fixed step-sizes and gradient tracking. Under strong convexity and smoothness, it proves global R-linear (geometric) convergence and gives explicit rate bounds.
Key findings
- DIGing uses doubly stochastic mixing matrices and fixed step-sizes; under Assumptions 1, 4, and 5, it converges to the unique optimum at a global R-linear rate \(O(\lambda^k)\) for step-sizes \(\alpha \in (0, 1.5(1-\delta)^2 \bar{\mu} J_1]\).
- Push-DIGing incorporates the push-sum protocol with column stochastic matrices and fixed step-sizes; under Assumptions 4–7, it also converges at a global R-linear rate \(O(\lambda^k)\) for \(\alpha \in (0, 1.5(1-\delta)^2 \bar{\mu} J_2]\).
- For undirected graphs, Corollary 11 gives iteration complexity \(O(\tau^{-2} B^3 n^{4.5} \bar{\kappa}^{1.5} \ln(1/\varepsilon))\), polynomial in the number of agents \(n\). For lazy Metropolis mixing on time-invariant connected undirected graphs, Corollary 12 gives rate \(\lambda = 1 - 1/(161312\, n^{4.5} \bar{\kappa}^{1.5})\) and iteration complexity \(O(n^{4.5} \bar{\kappa}^{1.5} \ln(1/\varepsilon))\).
- Numerical experiments with \(n=12\), \(m_i=1\), \(p=3\), and Huber loss show DIGing and variants have R-linear rates, while the push-gradient method has only sublinear rate; DIGing-ATC is faster in iterations than DIGing but has higher per-iteration communication cost, and Push-DIGing can be as fast as DIGing-ATC at half communication cost per iteration.
Methods
- The paper studies distributed convex optimization \(\min \sum_{i=1}^n f_i(x)\) over time-varying undirected and directed graphs, assuming smoothness with Lipschitz gradients and strong convexity of at least one local function.
- It proposes DIGing: \(x(k+1)=W(k)x(k)-\alpha y(k)\), \(y(k+1)=W(k)y(k)+\nabla f(x(k+1))-\nabla f(x(k))\), and Push-DIGing, which adds push-sum variables \(u,v,V\) and uses column stochastic matrices.
- Convergence analysis uses the small-gain theorem with an ergodic norm and a cycle of arrows \(q \to z \to \check{y} \to \check{x} \to q\); numerical experiments compare push-gradient, DIGing, DIGing-ATC, and Push-DIGing on time-invariant directed, time-varying undirected, and time-varying directed graphs.
Limitations
- The paper states an open question is obtaining improved estimates on convergence rates, especially scaling with the number of agents \(n\), and extensions to local constraints and couplings among agents.
- Step-size selection requires agents to agree on common upper bounds on \(n\) and \(B\), plus lower \(\bar{\mu}\) and upper \(L\); the paper assumes all agents use the same step-size, though it notes uncoordinated step-sizes are possible in subsequent work.
- The paper states its bounds on step-sizes are often conservative and uses hand-optimized step-sizes in experiments; the numerical experiments use a small network of \(n=12\), so the empirical validation is limited in scale.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
9 Valid · 0 Not valid · 10 Not checked · 37 Own results and interpretations
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“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.”
What the sources say
- Supportedcites [70] C. Xi and U. Khan, On the Linear Convergence of Distributed Optimization over Directed Graphs , preprint,arXiv:1510.02149, 2015. source
The part of the sentence this citation is offered for — that the cited work's step-size selection needs detailed spectral information about the network — is borne out by our copy: Theorem 1 (p. 13) sets α_min and α_max in terms of λ_min(M+M^⊤), d_- and d_∞, and the discussion after it (p. 14) states outright that 'the values of α and ᾱ need the knowledge of the network topology, which may not be available in a distributed manner,' flagging avoidance of that global knowledge as an open question. Section VI (p. 22) demonstrates the requirement in practice, computing λ_max/λ_min of H_i^⊤H_i, the degree constants and λ_min(M+M^⊤) to estimate the interval [9.6×10^-4, 0.26] before picking α = 0.1. The comparative framing ('compares favorably') is the citing authors' own conclusion and is not attributed to this source, so it is not judged here. (LLM, conf=0.85)
- Partly supportedcites [76] J. Zeng and W. Yin, ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks , preprint,arXiv:1511.02942, 2015. sourceExperimental — accuracy not yet measured
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)
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
Every source the paper cites for this claim was checked and supports it.
In the paper
“Proposition 1 ( [62]). Assume null { I -W } = span { 1 } where W ∈ R n × n . If x ∗ satisfies conditions: (i) x ∗ = Wx ∗ (consensus), (ii) 1 ⊤ ∇ f ( x ∗ ) = 0 (optimality), then the rows of x ∗ are the same as each other and the transpose of each row is an optimal solution of the problem (1) .”
What the sources say
- Supportedcites [62] matched to “EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization” (2015) source
The paper’s discussion of Proposition 2.1 (p. 6) says that, under null{I−W} = span{1}, a point satisfying its consensus and optimality conditions has identical rows that solve problem (1.1). Lemma 3.1’s proof (p. 9) identifies 1ᵀ∇f(x*) = 0 as the optimality condition. The citing proposition paraphrases those conditions and conclusion. (LLM, conf=0.92)
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
Every source the paper cites for this claim was checked and supports it.
In the paper
“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].”
What the sources say
- Supportedcites [41] A. Nedić and A. Olshevsky, Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs , preprint, arXiv:1406.2075, 2014. source
The paper reports an O((ln t)/t) rate for strongly convex functions with Lipschitz gradients using an appropriately chosen diminishing step-size (main-result passage; page unavailable). This is sublinear, although the Introduction and Conclusion emphasize that it improves on the earlier O((ln t)/√t) rate and is close to the best achievable rate in the noisy setting; “slow” is the citing authors’ characterization. (LLM, conf=0.85)
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
Every source the paper cites for this claim was checked and supports it.
In the paper
“Assumption 2 is typical for many results in multi-agent coordination and distributed optimization [42]. It is much weaker than the assumption of every G un ( k ) being connected.”
What the sources say
- Supportedcites [42] matched to “Distributed Optimization Over Time-Varying Directed Graphs” (2015) source
In II. Problem, Algorithm and Main Results (p. 2), the paper calls its connectivity assumption typical and says it is considerably weaker than requiring each graph to be connected, because the necessary edges can appear over time. (LLM, conf=0.91)
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“When the graph is undirected it shows that DIGing scales polynomially in the number of agents.”
- Also stated in: § ACHIEVING GEOMETRIC CONVERGENCE FOR DISTRIBUTED OPTIMIZATION OVER TIME-VARYING GRAPHS ∗ · p. 4 · plain
“Moreover, we show that the convergence rate of DIGing scales polynomially in the total number of agents in the network.”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on 2 assumptions not shown here.
- Also stated in: § ACHIEVING GEOMETRIC CONVERGENCE FOR DISTRIBUTED OPTIMIZATION OVER TIME-VARYING GRAPHS ∗ · p. 4 · plain
25 more claims
Create a free account to see all 56 claims and to verify the 2 references still open.
- It may state two separate claims as one. 13
- Probably not a substantial claim. 14
- The quote only partly states this claim. 1
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Algorithm 2: Push-DIGing · p. 21
“N out i ( k ) is the set of agents that can receive the information from agent i (in-neighbors of agent i ) at time k .”
§ Algorithm 2: Push-DIGing · p. 21
“N out i ( k ) = { j ∣ ∣ ( - → i, j ) ∈ A ( k ) }”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Algorithm 1: DIGing · p. 10
“the gradients are close to zero in the neighborhood of the optimal point”
§ ACHIEVING GEOMETRIC CONVERGENCE FOR DISTRIBUTED OPTIMIZATION OVER TIME-VARYING GRAPHS ∗ · p. 5
“not necessarily a point where ∇ f i ( x ) = 0 ∀ i”
Citations
Cites
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
Distributed Subgradient Methods for Multi-Agent Optimization
Nedic, A., & Ozdaglar, A. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.2009515 · Cited by 3,719 · cited 2×
“References [60–62] use a difference structure to cancel the steady state error in decentralized gradient descent [47, 75], thereby developing the algorithm EXTRA and its proximal-gradient variant.”
MethodFast linear iterations for distributed averaging
Xiao, L., & Boyd, S. (2004) · Systems & Control Letters · doi:10.1016/j.sysconle.2004.02.022 · Cited by 2,706
Markov Chains and Mixing Times
Levin, D., Peres, Y., & Wilmer, E. (2008) · doi:10.1090/mbk/058 · Cited by 2,241
Distributed asynchronous deterministic and stochastic gradient optimization algorithms
Tsitsiklis, J., Bertsekas, D., & Athans, M. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104412 · Cited by 1,967
Gossip-based computation of aggregate information
Kempe, D., Dobra, A., & Gehrke, J. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238221 · Cited by 1,480 · cited 4×
“Instead, if every agent knows its out-degree, it is possible for the agents to construct a column stochastic matrix C and perform the following recursions with initialization u(0) = x(0) and v(0) = 1 to achieve the average (push-sum protocol [27]):”
BackgroundMethodInfluentialEXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015) · SIAM Journal on Optimization · doi:10.1137/14096668x · Cited by 1,261
Self-citationDistributed Optimization Over Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2364096 · Cited by 1,187
Self-citationDistributed average consensus with least-mean-square deviation
Xiao, L., Boyd, S., & Kim, S.-J. (2007) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2006.08.010 · Cited by 1,107 · cited 1×
“Some examples include distributed averaging [7,50,72], distributed spectrum sensing [1], formation control [49, 58], power system control [21, 55], statistical inference and learning [20, 45, 53].”
BackgroundOptimal decentralized protocol for electric vehicle charging
Gan, L., Topcu, U., & Low, S. H. (2013) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2012.2210288 · Cited by 997
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2161027 · Cited by 947 · cited 1×
“Other works on distributed algorithms that also require the use of diminishing step-sizes include [19, 40, 78].”
BackgroundDistributed optimization in sensor networks
Rabbat, M., & Nowak, R. (2004) · Proceedings of the 3rd international symposium on Information processing in sensor networks · doi:10.1145/984622.984626 · Cited by 901 · cited 1×
“Some examples include distributed averaging [7,50,72], distributed spectrum sensing [1], formation control [49, 58], power system control [21, 55], statistical inference and learning [20, 45, 53].”
BackgroundGeometric Bounds for Eigenvalues of Markov Chains
Diaconis, P., & Stroock, D. (1991) · The Annals of Applied Probability · doi:10.1214/aoap/1177005980 · Cited by 882 · cited 1×
“Such bounds have been explored at great length within Markov chain literature, see e.g., the seminal paper [18] or the monograph [29], resulting in many different techniques, each giving accurate bounds on some graphs, and others.”
BackgroundOn the Linear Convergence of the ADMM in Decentralized Consensus Optimization
Shi, W., Ling, Q., Yuan, K., Wu, G., & Yin, W. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2304432 · Cited by 820 · cited 1×
“Under the strong convexity assumption, the decentralized ADMM has been shown to have linear convergence for time-invariant undirected graphs [63].”
BackgroundSelf-citationDistributed Stochastic Subgradient Projection Algorithms for Convex Optimization
Sundhar Ram, S., Nedić, A., & Veeravalli, V. V. (2010) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-010-9737-7 · Cited by 814 · cited 1×
“To handle a more general (possibly time-varying) networks, distributed subgradient algorithm was proposed in [47], while its stochastic variant was studied in [56] and its asynchronous variant in [36] with provable convergence rates.”
BackgroundSelf-citationOn Distributed Convex Optimization Under Inequality and Equality Constraints
Zhu, M., & Martinez, S. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2167817 · Cited by 759 · cited 1×
“Other works on distributed algorithms that also require the use of diminishing step-sizes include [19, 40, 78].”
BackgroundOn the Convergence of Decentralized Gradient Descent
Yuan, K., Ling, Q., & Yin, W. (2013) · arXiv · doi:10.48550/arxiv.1310.7063 · Cited by 635
Fast Distributed Gradient Methods
Jakovetic, D., Xavier, J., & Moura, J. M. F. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2298712 · Cited by 624 · cited 1×
“By utilizing multi-consensus inner loop, adapt-then-combine (ATC) strategy, and Nesterov’s acceleration, the algorithm proposed in [26] is shown to have O ( ln(k)/k(2) )”
MethodIncremental Subgradient Methods for Nondifferentiable Optimization
Nedic, A., & Bertsekas, D. P. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623499362111 · Cited by 589
Self-citationOn Distributed Averaging Algorithms and Quantization Effects
Nedic, A., Olshevsky, A., Ozdaglar, A., & Tsitsiklis, J. N. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2009.2031203 · Cited by 557
Self-citationDistributed Sparse Linear Regression
Mateos, G., Bazerque, J. A., & Giannakis, G. B. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2055862 · Cited by 550 · cited 1×
“The resulting algorithms include distributed dual decomposition [65] and decentralized alternating direction method of multipliers (ADMM) [5, 32].”
MethodProceedings of the 2005, American Control Conference, 2005.
(2005) · doi:10.1109/acc9914.2005 · Cited by 541
Distributed Spectrum Sensing for Cognitive Radio Networks by Exploiting Sparsity
Bazerque, J. A., & Giannakis, G. B. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2038417 · Cited by 510 · cited 1×
“Some examples include distributed averaging [7,50,72], distributed spectrum sensing [1], formation control [49, 58], power system control [21, 55], statistical inference and learning [20, 45, 53].”
BackgroundDiscrete-time dynamic average consensus
Zhu, M., & Martínez, S. (2010) · Automatica · doi:10.1016/j.automatica.2009.10.021 · Cited by 488 · cited 3×
“The proposed algorithm is based on the combination of Adapt-then-Combine (ATC) strategy of [59] and the dynamic average consensus for gradient tracking of [77].”
MethodNEXT: In-Network Nonconvex Optimization
Lorenzo, P. D., & Scutari, G. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2524588 · Cited by 473 · cited 2×
“The algorithm we will study in this paper crucially relies on tracking differences of gradients and is a minor variation of algorithms that have appeared in [73,74] and [15–17].”
MethodDiffusion Adaptation Over Networks
Sayed, A. H. (2014) · Academic Press Library in Signal Processing · doi:10.1016/b978-0-12-411597-2.00009-6 · Cited by 465
Multi-Agent Distributed Optimization via Inexact Consensus ADMM
Chang, T.-H., Hong, M., & Wang, X. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2367458 · Cited by 444 · cited 1×
“Building on (augmented) Lagrangian, a few improvements have been made via proximal-gradient [10], stochastic gradient [25], and second-order approximation [34, 35].”
Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing
Świętojański, P., & Renals, S. J. (2015) · Cited by 405
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers
Wei, E., & Ozdaglar, A. (2013) · 2013 IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2013.6736937 · Cited by 342 · cited 2×
“However, de-synchronization and extensions of these methods to time-varying undirected graphs are more involved [25, 69], while their extensions to directed graphs are non-existent in the current literature.”
BackgroundDistributed Algorithms for Aggregative Games on Graphs
Koshal, J., Nedić, A., & Shanbhag, U. V. (2016) · Operations Research · doi:10.1287/opre.2016.1501 · Cited by 341 · cited 1×
“A similar technique has been introduced in [77] for dynamically tracking the average state of a multi-agent system, and for tracking some network-wide aggregate quantities in [28,57].”
MethodSelf-citationXu, J., Zhu, S., Soh, Y. C., & Xie, L. (2015) · 2015 54th IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402509 · Cited by 332 · cited 5×
“The algorithm we will study in this paper crucially relies on tracking differences of gradients and is a minor variation of algorithms that have appeared in [73,74] and [15–17].”
MethodInfluentialThe electrical resistance of a graph captures its commute and cover times
Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R., & Tiwari, P. (1996) · Computational Complexity · doi:10.1007/bf01270385 · Cited by 328 · cited 2×
“Let us collect all the relations/arrows at hand [cf. Lemmata 5, 6, 7, and 9]: To apply the small gain theorem (Theorem 3) to get that q λ F is bounded, we need γ 1 γ 2 γ 3 γ 4 < 1, that is, (37) where β > 0 and η > 0 , along with other restrictions on parameters that appear in Lemmata 6, 7, and 9:…”
BackgroundMethodInfluentialAsynchronous Broadcast-Based Convex Optimization Over a Network
Nedic, A. (2011) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2079650 · Cited by 310
A Proximal Gradient Algorithm for Decentralized Composite Optimization
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2461520 · Cited by 307
Self-citationIncremental proximal methods for large scale convex optimization
Bertsekas, D. P. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0472-0 · Cited by 303
Cevher, V., Becker, S., & Schmidt, M. (2014) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2329397 · Cited by 300 · cited 1×
“The distributed algorithms designed over such special structure are usually fast in practice and mostly used in machine learning to handle big-data in a cluster of computers [6,8].”
BackgroundConsensus based formation control strategies for multi-vehicle systems
Ren, W. (2006) · 2006 American Control Conference · doi:10.1109/acc.2006.1657384 · Cited by 267
Feedback Systems: Input-Output Properties
Desoer, C. A., & Vidyasagar, M. (2009) · doi:10.1137/1.9780898719055 · Cited by 242
Incremental Stochastic Subgradient Algorithms for Convex Optimization
Ram, S. S., Nedić, A., & Veeravalli, V. V. (2009) · SIAM Journal on Optimization · doi:10.1137/080726380 · Cited by 239 · cited 1×
“Some earlier methods include distributed incremental (sub)gradient methods [37–39, 54 ] and incremental incremental proximal methods [ 3 , 68] , while a more recent Some distributed methods exist that do not (explicitly) use dual variables but can still converge to an exact consensual solution…”
MethodSelf-citationDistributed asynchronous computation of fixed points
Bertsekas, D. P. (1983) · Mathematical Programming · doi:10.1007/bf02591967 · Cited by 230 · cited 1×
“The research on distributed optimization dates back to 1980s [2,67].”
BackgroundFast linear iterations for distributed averaging
Xiao, L., & Boyd, S. (2004) · 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475) · doi:10.1109/cdc.2003.1272421 · Cited by 218
Convergence rate for consensus with delays
Nedić, A., & Ozdaglar, A. (2010) · Journal of Global Optimization · doi:10.1007/s10898-008-9370-2 · Cited by 198 · cited 3×
“≥ Based on those bounds on C ij ( k ), v j ( k ), and 1 /v i ( k + 1), we can have the following equivalent arc-utilization lower bound Thus, we have where the second inequality comes from Lemma 5 of reference [48].”
BackgroundMethodInfluentialSelf-citationConvergence Rate of Incremental Subgradient Algorithms
Nedić, A., & Bertsekas, D. (2001) · Applied Optimization · doi:10.1007/978-1-4757-6594-6_11 · Cited by 190
Self-citationDistributed Strategies for Generating Weight-Balanced and Doubly Stochastic Digraphs
Gharesifard, B., & Cortés, J. (2012) · European Journal of Control · doi:10.3166/ejc.18.539-557 · Cited by 171 · cited 2×
“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].”
Consensus-based distributed linear support vector machines
Forero, P. A., Cano, A., & Giannakis, G. B. (2010) · Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks · doi:10.1145/1791212.1791218 · Cited by 171
A fast distributed proximal-gradient method
Chen, A. I., & Ozdaglar, A. (2012) · 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2012.6483273 · Cited by 154
Decentralized Multi-Agent Optimization via Dual Decomposition
Terelius, H., Topcu, U., & Murray, R. M. (2011) · IFAC Proceedings Volumes · doi:10.3182/20110828-6-it-1002.01959 · Cited by 147 · cited 1×
“The resulting algorithms include distributed dual decomposition [65] and decentralized alternating direction method of multipliers (ADMM) [5, 32].”
MethodDistributed Asynchronous Incremental Subgradient Methods
Nedić, A., Bertsekas, D. P., & Borkar, V. S. (2001) · Studies in computational mathematics · doi:10.1016/s1570-579x(01)80023-9 · Cited by 146 · cited 1×
“Some earlier methods include distributed incremental (sub)gradient methods [37–39, 54 ] and incremental incremental proximal methods [ 3 , 68] , while a more recent Some distributed methods exist that do not (explicitly) use dual variables but can still converge to an exact consensual solution…”
MethodSelf-citationGeometrically convergent distributed optimization with uncoordinated step-sizes
Nedic, A., Olshevsky, A., Shi, W., & Uribe, C. A. (2017) · 2017 American Control Conference (ACC) · doi:10.23919/acc.2017.7963560 · Cited by 145
Self-citationA Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization
Mokhtari, A., Shi, W., Ling, Q. H., & Ribeiro, A. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2613678 · Cited by 132 · cited 2×
“Building on (augmented) Lagrangian, a few improvements have been made via proximal-gradient [10], stochastic gradient [25], and second-order approximation [34, 35].”
BackgroundMethodSelf-citationA new class of distributed optimization algorithms: Application to regression of distributed data
Sundhar Ram, S., Nedić, A., & Veeravalli, V. V. (2012) · Optimization Methods and Software · doi:10.1080/10556788.2010.511669 · Cited by 123 · cited 1×
“A similar technique has been introduced in [77] for dynamically tracking the average state of a multi-agent system, and for tracking some network-wide aggregate quantities in [28,57].”
MethodSelf-citationProduct of Random Stochastic Matrices
Touri, B., & Nedić, A. (2013) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2013.2283750 · Cited by 113
Self-citationAverage Consensus on Arbitrary Strongly Connected Digraphs With Time-Varying Topologies
Cai, K., & Ishii, H. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2305952 · Cited by 104 · cited 2×
“Some examples include distributed averaging [7,50,72], distributed spectrum sensing [1], formation control [49, 58], power system control [21, 55], statistical inference and learning [20, 45, 53].”
BackgroundMethodOn the Nonexistence of Quadratic Lyapunov Functions for Consensus Algorithms
Olshevsky, A., & Tsitsiklis, J. N. (2008) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.2007878 · Cited by 103 · cited 1×
“In consensus-based algorithms for optimization over directed graphs, it is difficult to construct monotonically decreasing Lyapunov functions for convergence analysis [51] due to the presence of asymmetric operators in the iterations (arising from the asymmetric weight matrices).”
Self-citationDistributed Non-Autonomous Power Control through Distributed Convex Optimization
Ram, S. S., Veeravalli, V. V., & Nedic, A. (2009) · IEEE INFOCOM 2009 · doi:10.1109/infcom.2009.5062275 · Cited by 99
Olshevsky, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.4186 · Cited by 92
Self-citationDistributed nonconvex multiagent optimization over time-varying networks
Sun, Y., Scutari, G., & Palomar, D. (2016) · 2016 50th Asilomar Conference on Signals, Systems and Computers · doi:10.1109/acssc.2016.7869154 · Cited by 86 · cited 1×
“Finally, the paper [64] proposed an algorithm with diminishing step-size for nonconvex optimization over directed graphs based on the push-sum method [27] and showed convergence to a stationary point.”
MethodProduct of Random Stochastic Matrices and Distributed Averaging
Touri, B. (2012) · Springer theses · doi:10.1007/978-3-642-28003-0 · Cited by 80 · cited 1×
“Also, to deal with time-varying graphs, one has to resort to time-varying or ergodic metrics [66] which are not easy to construct when the consensus protocol is combined with an optimization algorithm.”
BackgroundDistributed optimization over time-varying directed graphs
Nedic, A., & Olshevsky, A. (2013) · 52nd IEEE Conference on Decision and Control · doi:10.1109/cdc.2013.6760975 · Cited by 72 · cited 1×
“To overcome this issue, reference [40] is the first to propose a different distributed approach, namely a subgradient-push algorithm that combines the distributed subgradient method [47] with the push-sum protocol [27].”
MethodSelf-citationHarnessing smoothness to accelerate distributed optimization
Qu, G., & Li, N. (2016) · 2016 IEEE 55th Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798263 · Cited by 72 · cited 1×
“Finally, we note that reference [52], appearing simultaneously with this work, also proposed a method for distributed optimization based on gradient differences.”
MethodExtraPush for convex smooth decentralized optimization over directed networks
Zeng, J., & Yin, W. (2015) · arXiv · doi:10.48550/arxiv.1511.02942 · Cited by 65
Lü, Q., & Li, H. (2016) · arXiv · doi:10.48550/arxiv.1611.00990 · Cited by 54
Hong, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1604.00543 · Cited by 50
Random Walks on Regular and Irregular Graphs
Coppersmith, D., Feige, U., & Shearer, J. (1996) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480193260595 · Cited by 49 · cited 1×
“• On any regular graph, δ ≤ 1 − Ω(1 /n 2 ) as a consequence of the hitting time bounds of [12]. on the • On the star graph and two-star graph (defined to be two stars on n/ 2 nodes with a connection between the centers), δ ≤ 1 − Ω(1 /n 2 ) . strategy Remark 3 ( Adapt-then-Combine and acceleration ).”
BackgroundDistributed subgradient projection algorithm for convex optimization
Ram, S. S., Nedić, A., & Veeravalli, V. V. (2009) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2009.4960418 · Cited by 48
Self-citationStochastic First-Order Methods with Random Constraint Projection
Wang, M., & Bertsekas, D. P. (2016) · SIAM Journal on Optimization · doi:10.1137/130931278 · Cited by 47
On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of MultipliersPreprint
Wei, E., & Ozdaglar, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1307.8254 · Cited by 44
Incremental Aggregated Proximal and Augmented Lagrangian Algorithms
Bertsekas, D. (2015) · arXiv.org · doi:10.48550/arxiv.1509.09257 · Cited by 44
Distributed nonconvex optimization over networks
Lorenzo, P. D., & Scutari, G. (2015) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camsap.2015.7383778 · Cited by 40
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2014) · arXiv · doi:10.48550/arxiv.1406.2075 · Cited by 38
Self-citationOn the Linear Convergence of Distributed Optimization over Directed Graphs
Xi, C., & Khan, U. A. (2015) · arXiv · doi:10.48550/arxiv.1510.02149 · Cited by 29
Decentralized quadratically approximated alternating direction method of multipliers
Mokhtari, A., Shi, W., Ling, Q. H., & Ribeiro, A. (2015) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2015.7418306 · Cited by 26
Self-citationDistributed nonconvex optimization over time-varying networks
Lorenzo, P. D., & Scutari, G. (2016) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2016.7472453 · Cited by 23
Distributed Nonconvex Multiagent Optimization Over Time-Varying NetworksPreprint
Sun, Y., Scutari, G., & Palomar, D. P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1607.00249 · Cited by 17
Stochastic Proximal Gradient Consensus Over Random NetworksPreprint
Hong, M., & Chang, T. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.08905 · Cited by 14
Dual averaging for distributed optimization
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2012) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2012.6483406 · Cited by 13
Decentralized double stochastic averaging gradient
Mokhtari, A., & Ribeiro, A. (2015) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2015.7421158 · Cited by 12
A proximal gradient algorithm for decentralized nondifferentiable optimization
Shi, W., Ling, Q. H., Wu, G., & Yin, W. (2015) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2015.7178514 · Cited by 10
Self-citationStochastic proximal gradient consensus over time-varying networks
Hong, M., & Chang, T.-H. (2016) · 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp.2016.7472584 · Cited by 6
Augmented distributed optimization for networked systems
Xu, J. (2019) · doi:10.32657/10356/68805 · Cited by 5
On the Convergence Rate of Incremental Aggregated Gradient Algorithms
Gürbüzbalaban, M., Ozdaglar, A., & Parrilo, P. A. (2015) · DSpace@MIT (Massachusetts Institute of Technology) · doi:10.48550/arxiv.1506.02081
Distributed Algorithms for Aggregative Games on Graphs
Koshal, J., Nedić, A., & Shanbhag, U. V. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.00267
Self-citationMulti-Agent Distributed Optimization via Inexact Consensus ADMM
Chang, T.-H., Hong, M., & Wang, X. (2014) · arXiv · doi:10.48550/arxiv.1402.6065
DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
Mokhtari, A., Shi, W., Ling, Q., et al. (2015) · arXiv · doi:10.48550/arxiv.1508.02073
Self-citationA Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization
Mokhtari, A., Shi, W., Ling, Q., et al. (2016) · arXiv · doi:10.48550/arxiv.1602.00596
Self-citationGeometrically Convergent Distributed Optimization with Uncoordinated Step-Sizes
Nedić, A., Olshevsky, A., Shi, W., et al. (2016) · arXiv · doi:10.48550/arxiv.1609.05877
Self-citationFast Convergence Rates for Distributed Non-Bayesian Learning
Nedić, A., Olshevsky, A., & Uribe, C. A. (2015) · arXiv · doi:10.48550/arxiv.1508.05161
Self-citationHarnessing Smoothness to Accelerate Distributed Optimization
Qu, G., & Li, N. (2016) · arXiv · doi:10.48550/arxiv.1605.07112
Research works printed but not linked: 9
- Chen A., 2012, Allerton, 601
- Di Lorenzo P., 2015, Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 229
- Forero P., 2010, J. Mach. Learn. Res., 59, 1663
- Mokhtari A., 2016, J. Mach. Learn. Res., 17, 1
- Nedić A., 2008, UK, 3
- A. Olshevsky, Efficient Information Aggregation Strategies for Distributed Control and Signal Processing , Ph.D. thesis, Massachusetts Institute of Technology, 2010.
- Rabbat M., 2004, New York, 20
- Ram S., 2009, Proceedings of INFOCOM, 3001
- Sayed A., 2013, New York, 323
Cited by
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms
Zhang, K., Yang, Z., & Başar, T. (2021) · Studies in Systems, Decision and Control · doi:10.1007/978-3-030-60990-0_12 · Cited by 1,264
A survey of distributed optimization
Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., & Johansson, K. H. (2019) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2019.05.006 · Cited by 913
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization
Nedic, A., Olshevsky, A., & Rabbat, M. G. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2817461 · Cited by 534
Self-citationTutorial on dynamic average consensus: the problem, its applications,\n and the algorithms
Kia, S. S., Scoy, B. V., Cortés, J., Freeman, R. A., Lynch, K., & Martı́nez, S. (2018) · eScholarship (California Digital Library) · Cited by 404
Push–Pull Gradient Methods for Distributed Optimization in Networks
Pu, S., Shi, W., Xu, J., & Nedic, A. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2972824 · Cited by 376
“Unlike the push-sum type protocol used in the previous literature [9], [14], our algorithm uses a row stochastic matrix for the mixing of the decision variables, while it employs a column stochastic matrix for tracking the average gradients.”
BackgroundMethodInfluentialSelf-citation
Metadata
- Authors
- Nedić, A., Olshevsky, A., & Shi, W.
- Affiliations
- Boston University (US)
- Arizona State University (US)
- Venue
- SIAM Journal on Optimization
- Published
- 2017-01
- Volume
- 27
- Issue
- 4
- Pages
- 2597-2633
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2963649943
- Cited by
- 1,069
- References
- 38
- Citations by year
- 2026: 95 · 2025: 147 · 2024: 130 · 2023: 124 · 2022: 118 · 2021: 114 · 2020: 138 · 2019: 106 · 2018: 64 · 2017: 29
- FWCI
- 46.51
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- SIAM Journal on Optimization (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- U.S. Air Force (AF FA95501510394)
- Office of Naval Research (N00014-12-1-0998)
- National Science Foundation (CNS 15-44953)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Keywords
- distributed optimization, dynamic graphs, geometric convergence, R-linear convergence, gradient tracking, strong convexity, fixed step size, undirected graphs, directed graphs
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.
The claim verdicts this report counts are experimental: their accuracy is not yet measured.
A language model drew the claims from the paper on 2026-10-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-10 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Cited sources are checked with a language model’s help (qwen3.8-omni-flash and gpt-6-sol).
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.