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] 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] 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].”
Background
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
Items 1,001–1,070 of 1,070
Distributed Feedback Optimization for Linear Uncertain Multiagent Systems with Unknown Exosystems
Liu, T., Liu, T., Hu, X., et al. (2025) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2025.11.019
Distributed Proximal Splitting Algorithm for Composite Constrained Convex Optimization
Li, H., Lü, Q., Xia, D., Wang, X., Wang, Z., Zheng, L., Li, J. Q., & Ran, L. (2025) · Computational intelligence methods and applications · doi:10.1007/978-981-95-0911-9_10
Distributed Dual Proximal Gradient Algorithms for Nonsmooth Constrained Composite Optimization
Li, H., Lü, Q., Xia, D., Wang, X., Wang, Z., Zheng, L., Li, J. Q., & Ran, L. (2025) · Computational intelligence methods and applications · doi:10.1007/978-981-95-0911-9_9
A Convergence-Motivated Learning-to-Optimize Framework for Decentralized Optimization
He, Y., Shang, Q., Huang, X., Liu, J., & Yuan, K. (2025) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2025.3644008 · Cited by 4
“Notable examples include primal algorithms such as DGD [2], [3] and Diffusion [4], [5], dual algorithms like dual averaging [6], and primal-dual algorithms such as decentralized ADMM [7], EXTRA [8], Exact-Diffusion [9] (also known as NIDS [10]), and Gradient-Tracking [11], [12], [13].”
Emirov, N., Song, G., & Sun, Q. (2025) · Expositiones Mathematicae · doi:10.1016/j.exmath.2025.125740
Cui, G., Jia, Q.-S., Guan, X., Zhai, Q., Guo, X., & Guo, Q. (2025) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2025.3638318
“Condition (2.3) holds if and only if the communication graph is connected [44].”
InfluentialA Unified Dual-Consensus Approach to Distributed Optimization With Globally Coupled Constraints
Liu, Z., Wu, X., Wang, D., & Lu, J. (2025) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2025.3649114
“It can be viewed as the proximal counterpart of DIGing [37] and is able to handle nonsmooth objectives.”
Multi-Agent Assignment over Stochastic Graphs via Learning Feasibility
Agorio, L., Alen, S. V., Paternain, S., et al. (2025) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc57313.2025.11312403
Lu, T. D., Zhao, J., Liu, H., et al. (2025) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc57313.2025.11312560
Makridis, E., Oliva, G., & Charalambous, T. (2025) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc57313.2025.11312648
“…∈ Z ≥ 0 : if v j ∈ J k +1 (arriving) Initialize: x j,k +1 , y j,k +1 , w j,k +1 , h j,k +1 via (10) ∈ R Assign weights: c lj,k via (12) Coordinate departure information: determine h j,k via (13), (14) Update: x j,k +1 , y j,k +1 , and w j,k +1 via (11) end if Output: z j,k +1 = x j,k +1 /y j,k +1 .”
Automated algorithm design for convex optimization problems with linear equality constraints
Ozaslan, I. K., Wu, W., Chen, J., et al. (2025) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc57313.2025.11312607
“In addition to the momentum-based accelerated methods, distributed algorithms such as EXTRA [24], DIGing [25], or ABN [26], can also be brought into the form given by (2); see [16] for additional details.”
Niu, Y., Xu, J., Sun, Y., et al. (2025) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc57313.2025.11312713
“Assumption 3 ( Penalty functions ): The penalty function Lastly, we make the following standard assumption regarding the network connectivity [18], [19].”
A novel distributed gradient algorithm for composite constrained optimization over directed network
Ou, M., Zhang, H., Yan, Z., Yang, Z., & Ran, H. (2026) · Scientific Reports · doi:10.1038/s41598-026-36058-4 · Cited by 1
Garmpis, S., & Bechlioulis, C. P. (2025) · International Conference on Systems and Control (ICSC) · doi:10.1109/icsc67755.2025.11335077
Distributed Nash Equilibrium Seeking for Aggregative Games With Linear Convergence Over Digraphs
Wu, Q. (2026) · IEEE Access · doi:10.1109/access.2026.3659251
“Although some distributed algorithms [19], [20] are applicable to directed graphs, they are only suitable for tracking the global gradient in distributed optimization problems, rather than for tracking the aggregation function in aggregative games.”
Decentralized Primal--Dual Optimization Without Global Lipschitz Continuity
Wang, L., Yang, S., & Zhang, M.-L. (2026) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2026.3656728
“When g i = 0 and f i is strongly convex, algorithms such as D-ADMM [12], DLM [13], EXTRA [14], DIGing [15], GT [16], and Exact Di ff usion [17] have been proposed, all of which are proved to exhibit linear convergence rates.”
Lu, T. D., Cheng, M., Liu, H., et al. (2026) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2026.3658066
“In fact, this issue is common and can be found in [25], [26], [27], [28], and [31].”
An improved convergence guarantee for the gradient-push algorithm with a constant stepsize
Choi, H., Choi, W., & Kim, G. (2026) · Computational Optimization and Applications · doi:10.1007/s10589-025-00763-z · Cited by 1
On the Convergence of Decentralized Stochastic Gradient-Tracking With Finite-Time Consensus
Fainman, A., & Vlaski, S. (2026) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2026.3667215 · Cited by 1
“Index Terms —Decentralized optimization, finite-time consensus, gradient-tracking, consensus optimization.”
Primal-Dual Strategy for Composite Optimization Over Directed Graphs
Zandi, S., Esfandiari, M., & Zhao, S. (2026) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2026.3667777
“Tosimplify theimplementationoftheconvergencerate,agradienttracking methodwasappliedin[15]and[16];then,dual-domainand accelerateddualgradientdescentwereutilizedin[17].”
Fan, P. Z., Wu, M., Liao, H., Jin, J., & Xiong, N. N. (2026) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2026.3665573 · Cited by 2
“Second, applying our method to specific network topologies (e.g., clustered or directed graphs [20], [53]) and systematically characterizing how graph structure influences algorithmic performance constitutes another meaningful direction.”
Chakrabarti, K., Mai, V. S., & Maity, D. (2026) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.70448
Variance-Reduced Decentralized Stochastic Optimization Algorithms With Communication Skip
Xu, W., li, R., & Yang, G. (2026) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2026.3669596
“In [30], the gradient tracking method [18], [19], [20], [21], [22], [23] was combined with SAGA and SVRG, respectively, i.e., gradient tracking-stochastic average gradient augmented (GT-SAGA) and gradient tracking-stochastic variance reduced gradient (GT-SVRG).”
A Hierarchical Gradient Tracking Algorithm for Mitigating Subnet-Drift in Fog Learning Networks
Chen, E., Wang, S., & Brinton, C. G. (2026) · IEEE Transactions on Networking · doi:10.1109/ton.2026.3673208
Liu, J., Liu, S., Wang, Y., et al. (2026) · IEEE Transactions on Artificial Intelligence · doi:10.1109/tai.2026.3675069
“Reasonable distributed optimization algorithms can make full use of computing resources in distributed environment, speed up the solving process, and have good performance in dealing with large-scale and complex optimization problems [8], [9], [10], [11], [12], [13], [14].”
How Physicality Enables Cy-Trust: A New Era of Trust-Centered Cyber–Physical Systems
Gil, S., Yemini, M., Chorti, A., Nedić, A., Poor, H. V., & Goldsmith, A. J. (2025) · Proceedings of the IEEE · doi:10.1109/jproc.2026.3660771 · Cited by 24
Self-citationGuo, L., Shi, X., Xu, W., & Cao, J. (2026) · Automatica · doi:10.1016/j.automatica.2026.112965 · Cited by 3
Chen, W., Wang, Z., Peng, J. C., et al. (2026) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2026.3675917
“Lemma 1 (Small-gain theorem [26]): Assume that sequences a 1 , a 2 , . . . , a s satisfy the following cyclic inequalities a i → a ( i mod s )+ 1 , ( i = 1 , 2 , . . . , s ) : with κ i being constants.”
Optimization methods over networks for popular content delivery and distributed machine learning
Costantini, M. (2023) · theses.fr (ABES) · doi:10.70675/1f27d904z6f26z4a9ez8b79z78214cb50b08
Decentralized Federated Learning With Period Gradient Tracking Over Time-Varying Networks
Shi, F., Chen, Y., Huang, Q., Huang, T., Liu, G., & Shen, L. (2026) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2026.3685244
“In comparison with [28], [29], we extend gradient tracking from a single-step local update to a multi-step local update.”
Decentralized Learning with Dynamically Refined Edge Weights: A Data-Dependent Framework
Du, R., & Wai, H.-T. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11463182
“Recent works have either extended the analysis of DGD with tighter bounds [8–11], or extended DGD to work under various settings, including gradient tracking [12, 13], directed graphs [14–18], time varying graphs [19,20], etc.”
Improved Analysis of Push-DIGing for Distributed Convex Optimization over Digraphs
Mo, M., Wang, J., Liu, B., 盛子晗, & Yuan, K. (2026) · International Symposium on Big Data and Applied Statistics (ISBDAS) · doi:10.1109/isbdas69350.2026.11484962
“Gradient-tracking methods (e.g., EXTRA, DIGing) eliminate this bias and achieve exact convergence with a constant step-size [1]–[3], [7], [9], [12], [16], but rely on an undirected graph and a doubly-stochastic mixing matrix, restricting use in inherently directed communication.”
Distributed Online Optimization with Switching Costs
Yang, Y., Li, X., Li, L., et al. (2026) · Journal of Systems Science and Complexity · doi:10.1007/s11424-026-5394-2
Balancing resilience and optimality in distributed optimization for cyber-physical systems
Molino, L., & Manfredi, S. (2026) · Expert Systems with Applications · doi:10.1016/j.eswa.2026.132676
A necessary and sufficient condition for discrete-time consensus on star boundaries
Sidorenko, G., & Thunberg, J. (2026) · Automatica · doi:10.1016/j.automatica.2026.113027
A Fast Differentially Private Distributed Algorithm Over Unbalanced Directed Networks
Ran, M., Wang, Z. X., Lei, Y., & Li, H. (2026) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2026.3691978
“For example, DIGing [23] employs fixed step sizes with doubly stochastic matrices, which achieve geometric convergence.”
Linear Convergence of Decentralized Gradient Tracking Under Generalized Smoothness
Bo, Y., & Wang, Y. (2026) · IEEE Control Systems Letters · doi:10.1109/lcsys.2026.3693322
“Specifically, we show a significant new finding that the standard gradient tracking method [28], [29] achieves linear convergence under strongly convex objectives, without any additional stabilization mechanisms, under a stepsize determined by the ( L 0 , L 1 ) smoothness parameters.”
Asheralieva, A., & Wei, X. (2026) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2026.3693874
“To evaluate node mobility and topology dynamics of the P2P graph 𝒢 , we use a standard time-varying random geometric graph model based on the random-waypoint mobility pattern [56], [62], commonly adopted in edge environments.”
Decentralized Inexact Cubic Newton Method With Consensus Procedure
Agafonov, A., Novitskii, A., Rogozin, A., et al. (2026) · IEEE Access · doi:10.1109/access.2026.3695635
“Here we also have τ = 1 , and the parameter is defined by the worst-case spectral gap: ) is connected [14].”
Liu, H., Cheng, M., Yu, W., & Zheng, W. X. (2026) · Science China Information Sciences · doi:10.1007/s11432-025-4887-6
“…left eigenvector with respect to eigenvalue 1 of a nonnegative stochastic matrix (see [21,22,31,37]) and Push-Pull or Push-DIGing framework (see [32,33,38]), the result in this work could be potentially extended to the cases with fixed unbalanced networks and uniformly-connected time-varying…”
Li, Z., Ran, L., Li, J., & Zheng, L. (2026) · Mathematical and Computational Applications · doi:10.3390/mca31030091
“In addition, there are several popular algorithms such as alternating direction method of multipliers (ADMM) [18,19], the decentralized adaptive diffusion [20], and various iterations of decentralized gradient-tracking techniques [21,22].”
Gradient tracking with distributed unified adaptive momentum for stochastic non-convex optimization
Cao, Z., He, S., Yan, D., Zhou, Y., Wang, X., & Li, C. (2026) · Communications in Nonlinear Science and Numerical Simulation · doi:10.1016/j.cnsns.2026.110279
Xiong, D. (2026) · Conference on Fully Actuated System Theory and Applications (FASTA) · doi:10.1109/fasta70174.2026.11548950
Zhu, Y., Zhang, G., Liu, H., & Li, T. (2026) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2026.108829
Accelerated Variance-Reduced Distributed Stochastic Optimization Over Time-Varying Directed Networks
Li, S.-Q., Liu, X., Xiao, J., Wang, Y., & Guo, K.-Y. (2026) · Chinese Control and Decision Conference (CCDC) · doi:10.1109/ccdc69976.2026.11560044
“…Assumption 2.3 is a more general assumption that merely requires the network to be periodically connected than ˜ B -bounded strong-connectivity assumption [5], [6], which requires the union network (cid:5) Algorithm 1 GT-ALSVRG at Each Node i 1: Initial: For each agent i , initialize variables:”
InfluentialClipped Stochastic Gradient Tracking For Locally Smooth Functions
Mei, L., & Zhang, J. (2026) · Journal of Scientific Computing · doi:10.1007/s10915-026-03357-x
“The gradient tracking method was originally proposed in [27] for convex problems, and has been extended to the nonconvex and stochastic setting in [51, 23, 16, 33], and they significantly outperform their DGD counterparts, whose convergence requires additional regularity condition such as uniformly…”
Dib, O. (2026) · Information Fusion · doi:10.1016/j.inffus.2026.104577 · Cited by 2
Zhang, S., Chen, G., & Ji, Y. (2026) · IEEE Control Systems Letters · doi:10.1109/lcsys.2026.3709160
“It can be seen from [17] that the states of agents will achieve consensus.”
Decentralized Gradient Descent with an Increasing Consensus Procedure Accuracy
Murzina, A., Kuruzov, I. A., & Gasnikov, A. V. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-31390-4_3
Garmpis, S., & Bechlioulis, C. P. (2026) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2026.3710316
“…tracking methods address this limitation by employing and communicating an additional auxiliary variable that tracks the global gradient, enabling exact convergence under constant step-sizes while substantially improving convergence speed compared to traditional subgradient methods [3], [4].”
Poisson subsampling for large-scale functional data analysis
Yan, X., & He, S. (2026) · Computational Statistics · doi:10.1007/s00180-026-01776-w
“The standard assumption is that W is symmetric and doubly stochastic, with nonzero entries only on the edges of the communication graph (Shi et al. 2015; Nedic et al. 2017 ): Such a matrix W has two key properties.”
Cheng, M., Liu, H., Tian, L., et al. (2026) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2026.3710315
“While push–pull algorithms are effective for unbalanced digraphs, they are not directly applicable to closed convex constraints [18], [19].”
Du, G., Zhang, B., Lian, Y., et al. (2026) · IEEE Internet of Things Journal · doi:10.1109/jiot.2026.3710534
“Unlike general distributed optimization [11], [12], [13], DOC for MASs must account for both objective functions and underlying system dynamics, posing significant theoretical challenges.”
Chaotic-AES Integration for Privacy-Preserving Distributed Personalized Optimization
Tang, Q., Zhou, X., Yuan, Y., Lü, Q., & Li, H. (2026) · IEEE Signal Processing Letters · doi:10.1109/lsp.2026.3711542
“…subgradient and gradient descent methods [10], [11], [12], [13], as well as more advanced schemes such as EXTRA [14], [15], [16], DIGing [17], [18], [19], push–pull methods [20], [21], [22], communication-efficientvariants[23],[24]andacceleratedNes-terovgradientmethodsoverarbitrarygraphs[25].”
Das, S., Schenato, L., & Dey, S. (2026) · European Journal of Control · doi:10.1016/j.ejcon.2026.101610
Meshcheryakov, V. N., Кондратьев, С. Е., & Kazyura, N. (2026) · Informatics and Automation · doi:10.15622/ia.25.4.8
“На основе метода интегратора из [21], разработанного для обеспечения условий консенсуса, в уравнение (9) с начальными условиями: В стационарном состоянии, когда lim s →∞ u ( · , s ) = u ∗ , имеем u s ( t, s ) = z s ( t, s ) = 0 для почти всех t ∈ [0 , T ] , что влечёт: Вспоминая определения J 2 , J…”
Privacy-preserving dynamic weighted average consensus based on agent decomposition
Gao, H. B., Cheng, X., Zhi, Y., et al. (2026) · Systems & Control Letters · doi:10.1016/j.sysconle.2026.106545
New Proof of the Decentralized BEER Optimization Algorithm Under the Polyak-Łojasiewicz Condition
Phuong, T. T., & Phong, L. T. (2026) · Lecture notes in electrical engineering · doi:10.1007/978-3-032-13917-7_8
Kővári, A. (2026) · Energy Conversion and Management X · doi:10.1016/j.ecmx.2026.102212
Decentralized low tubal rank tensor estimation via factorized gradient tracking
Song, Z., Peng, L., Zhao, W., & Lian, H. (2026) · Neurocomputing · doi:10.1016/j.neucom.2026.134884
Distributed pull-primal-dual stochastic gradient algorithm over directed networks with noisy links
Wu, J., Zhang, M., Zhang, S., & Zhou, Z. (2026) · Signal Processing · doi:10.1016/j.sigpro.2026.110885
Sahu, P. K., Baraha, S., Sahoo, U. K., et al. (2026) · Ad Hoc Networks · doi:10.1016/j.adhoc.2026.104404
Zha, L., Chen, W., & Zhang, X. (2026) · Symmetry · doi:10.3390/sym18091503
Decentralized Learning with Communication-Efficient Learned Gradient Sketches
Cheng, Z., Dai, W., & Sun, J. (2026) · Proceedings of the International Conference on Parallel Processing · doi:10.1145/3832810.3832830
“Gradient Tracking (GT) resolves this by maintaining an auxiliary variable that estimates the network-wide average gradient [6, 19, 22].”
AdGT: Decentralized Gradient Tracking With Adaptive Per-Agent Stepsizes
Ghaderyan, D., & Werner, S. (2026) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2026.3733814 · Cited by 5
“Remark 11: For comparison, representative sufficient fixed-stepsize bounds for the methods in [21], [22], expressed in our notation, are The sufficient AdGT condition in (25) has the same (1 − λ ) 2 dependence and scales as O ((1 − λ ) 2 / ( μκ 3 )) .”
InfluentialInfluence of Link Noise on Exact Diffusion Stochastic Optimization Over Distributed Networks
Han, H., Zhang, S., Chen, H., et al. (2026) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2026.3733659
“…methods have been proposed using gradient-tracking (GT), primal-dual, and alternating direction multiplier techniques to solve the problem (1); see, e.g., the presentation in [3] as well as DIGing [11], Aug-DGM [12], EXTRA [13], DLM [14], NIDS [15], and exact diffusion (ED) [16], [17] methods.”
Distributed Optimization Under Uncertainty: A Cross-Paradigm Review and Future Directions
Mugenga, I. R., Geletu, A., Mirau, S., & Li, P. (2026) · Mathematics · doi:10.3390/math14193489
A Two‐Average‐Tracking Scheme in Distributed Optimization With a Small‐Gain Convergence Analysis
Xiao, Y., & Ni, W. (2026) · Asian Journal of Control · doi:10.1002/asjc.70243
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.