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].”
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 801–900 of 1,070
A Linear Push-Pull Average Consensus Algorithm for Delay-Prone Networks
Makridis, E., & Charalambous, T. (2024) · European Control Conference (ECC) · doi:10.23919/ecc64448.2024.10591256 · Cited by 2
Ran, L., Li, H., Zheng, L., & Li, J. Q. (2024) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2024.3437249 · Cited by 4
“Utilizing the push-sum protocol, Push-DIGing [17] works with column stochastic matrices and fixed step-sizes.”
DISH: A Distributed Hybrid Optimization Method Leveraging System Heterogeneity
Niu, X., & Wei, E. (2024) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2024.3450351 · Cited by 1
“For consensus problems, DISH covers well-known primal-dual gradient-type methods such as EXTRA [7], DIGing [8], and [9], and primal-Newton-dual-gradient methods like ESOM-0 [16] as special cases.”
BackgroundMethodInfluentialTillmann, M. H. V., & Yukawa, M. (2024) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2024.3451992 · Cited by 1
Decentralized Optimization in Networks with Arbitrary Delays
Ortega, T., & Jafarkhani, H. (2024) · International Conference on Communications · doi:10.1109/icc51166.2024.10622164 · Cited by 4
“In the case where G is undirected, there are multiple efforts to solve this problem in various settings, like asynchronous communications [6], time-varying graphs [7], [8], or quantized communications [9], [10].”
BackgroundDistributed Least-Squares Optimization Solvers with Differential Privacy
Liu, W., Wang, L., Guo, F., Wu, Z., & Su, H. (2024) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc60939.2024.10644636
“Particularly, the gradient-tracking algorithm [13], [5] has gained increasing attention due to its fast convergence rate, yielding several variants such as [14], [15], [16], [17], [18].”
BackgroundLi, Y., Hou, J., Zeng, X., et al. (2024) · Chinese Control Conference (CCC) · doi:10.23919/ccc63176.2024.10661663 · Cited by 1
“(2)TheAggregating step: Each pursuer uses the gradient tracking technique [23] to approximate the partial gradient on its own mixed strategy and the aggregating gradient on the evader’s mixed strategy.”
MethodLinear Convergence of Asynchronous Gradient Push Algorithm for Distributed Optimization
Li, H., Cheng, H., Lü, Q., Wang, Z., & Huang, T. (2024) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2024.3516936 · Cited by 3
Distributed Optimization of Heterogeneous Linear Multi-Agent Systems with Unknown Disturbances
Duan, M., Zhu, S., Yang, Z., et al. (2024) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc56724.2024.10886146 · Cited by 1
“Considering agents modeled with first-order dynamics, many distributed controllers are designed to solve the distributed optimization problem, such as the distributed subgradient descent [3], EXTRA [4], DIGing [5], Aug-DGM [6], Asyn-DGM [7], distributed ADMM [8] and so on [9]-[10].”
A Single-Loop Algorithm for Decentralized Bilevel Optimization
Dong, Y., Ma, S., Yang, J., & Yin, C. (2025) · Mathematics of Operations Research · doi:10.1287/moor.2024.0488 · Cited by 16
Fully First-Order Methods for DecentralizedBilevel Optimization
Wang, X., Chen, X., Ma, S., & Zhang, T. (2025) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2025.3624427 · Cited by 7
“The gradient tracking (GT) technique was proposed to improve the convergence rates of decentralized optimization algorithms [48], [49], [60], [61].”
Decentralized optimization approach for power distribution network and microgrid controls
Liu, H. J. (2017) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 1
Distributed Fenchel Dual Gradient Methods Enabling a Smoothing Technique for Nonsmooth Optimization
Wu, X., Sou, K. C., & Lu, J. (2018) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.2018.8619031 · Cited by 1
“For strongly convex and smooth problems, an O(ln k/k) rate is proved for Gradient-Push [5] and linear rates O(q), q ∈ (0, 1) are derived for DIGing and Push-DIGing [8].”
MethodResultInfluentialLiang, S., Cheng, S., & Peng, K. (2019) · Chinese Control Conference (CCC) · doi:10.23919/chicc.2019.8866018 · Cited by 1
“This method has been further employed to develop subgradient-push method [20] and push-DIGing method [21].”
BackgroundMethodInfluentialPopSGD: Decentralized Stochastic Gradient Descent in the Population Model
Nadiradze, G., Sabour, A., Sharma, A. K., Markov, I., Aksenov, V., & Alistarh, D. (2019) · Cited by 1
Distributed Stochastic Algorithm for Convex optimization Problem Over Time-varying Directed Graphs
Cheng, S., Wang, Y., & Hong, Y. (2019) · International Conference on Control and Automation · doi:10.1109/icca.2019.8899958 · Cited by 1
“Another effective way of overcoming the unbalance of the directed topology is the push-sum based algorithm, which sent the weighted decision variables based on the out-degree of the counterpart agent [15-19].”
BackgroundPush-Pull Finite-Time Convergence Distributed Optimization Algorithm
Chen, X., Yan, K., Gao, Y. K., Xu, X., Yan, K., & Wang, J. (2020) · American Journal of Computational Mathematics · doi:10.4236/ajcm.2020.101008 · Cited by 1
“The original algorithm was actually calculated from [44], and it also gave us some inspiration.”
MethodOn the Comparison between Primal and Primal-dual Methods in Decentralized Dynamic Optimization
Xu, W., Yuan, K., Yin, W., & Ling, Q. H. (2019) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf44664.2019.9049028 · Cited by 1
Row-Stochastic Matrices Based Distributed Optimization Algorithm With Uncoordinated Step-Sizes
Li, H., Wang, J., & Wang, Z. (2019) · International Conference on Information, Cybernetics, and Computational Social Systems (ICCSS) · doi:10.1109/iccss48103.2019.9115478 · Cited by 4
“On the basis of [19], time-varying graphs were further considered in [20].”
BackgroundMethodLi, H., Lü, Q., Wang, Z., Liao, X., & Huang, T. (2020) · Springer eBooks · doi:10.1007/978-981-15-6109-2_2 · Cited by 1
Random Sleep Scheme-Based Distributed Optimization over Time-Varying Directed Networks
Li, H., Lü, Q., Wang, Z., Liao, X., & Huang, T. (2020) · Springer eBooks · doi:10.1007/978-981-15-6109-2_7 · Cited by 1
Distributed Stochastic Optimization: Variance Reduction and Edge-Based Method
Li, H., Lü, Q., Wang, Z., Liao, X., & Huang, T. (2020) · Springer eBooks · doi:10.1007/978-981-15-6109-2_8 · Cited by 1
Li, H., Lü, Q., Wang, Z., Liao, X., & Huang, T. (2020) · Springer eBooks · doi:10.1007/978-981-15-6109-2_3 · Cited by 1
Accelerated Row-stochastic Optimization over Directed Graphs with Uncoordinated Step Sizes
Zhou, K., Du, Z., & Li, H. (2020) · International Conference on Control and Automation · doi:10.1109/icca51439.2020.9264515 · Cited by 1
“The feature vectors c ij is generated Under the same condition setting, we compare the performance of The proposed algorithm with FROST [22], Push-DIGing [27] in Fig.2, where the choice of value does not affect the result of convergence.”
BackgroundMethodInfluentialOptimising Cost vs Accuracy of Decentralised Analytics in Fog Computing Environments
Valerio, L., Passarella, A., & Conti, M. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3101986 · Cited by 1
“of the high communication costs induced by decentralised optimisation algorithms [25], [26], the need to cope with timevarying graphs [27], [28], [29] and the problem of data heterogeneity among devices [16].”
BackgroundDecentralized Max-Min Resource Allocation for Monotonic Utility Functions
Wu, S., Xi, P., & Tian, G. (2021) · IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) · doi:10.1109/infocomwkshps51825.2021.9484502 · Cited by 5
Shi, X., Liu, H., Chen, J., et al. (2021) · Chinese Control and Decision Conference (CCDC) · doi:10.1109/ccdc52312.2021.9602039 · Cited by 1
Toghani, M. T., & Uribe, C. A. (2022) · European Journal of Control · doi:10.1016/j.ejcon.2022.100682 · Cited by 1
Decentralized Stochastic Optimization With Random Attendance
Phuong, T. T., & Phong, L. T. (2022) · IEEE Signal Processing Letters · doi:10.1109/lsp.2022.3179331 · Cited by 1
Distributed Convex Optimization on the Nonnegative Orthant
Jahvani, M., & Guay, M. (2022) · European Control Conference (ECC) · doi:10.23919/ecc55457.2022.9838106 · Cited by 1
Fang, R., Li, D., & Shen, X. (2022) · IET Control Theory and Applications · doi:10.1049/cth2.12349 · Cited by 1
Trust-Region Based Stochastic Variational Inference for Distributed and Asynchronous Networks
Fu, W., Qin, J., Ling, Q. H., Kang, Y., & Ye, B. (2022) · Journal of Systems Science and Complexity · doi:10.1007/s11424-022-2085-5 · Cited by 1
“2 Distributed Sampling and Diffusion To perform the uniform sampling in distributed networks, the token-passing-based asynchronous SVI algorithm([12]) is proposed according to the Metropolis Rule([20]).”
MethodNam, J., Heo, J., Kim, J. W., et al. (2022) · International Conference on Control, Automation and Systems (ICCAS) · doi:10.23919/iccas55662.2022.10003797 · Cited by 1
“In [10], it is utilized for tracking the average of the gradients dynamically.”
MethodInference Attack in Distributed Optimization via Interpolation and Manipulation
Xu, J., He, Z., Fang, C., et al. (2022) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc51059.2022.9993236 · Cited by 1
Marquis, D. J., Jaoude, D. A., Farhood, M., & Woolsey, C. A. (2023) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc55779.2023.10156353 · Cited by 1
“DIGing4 [5] uDIG5 [6] uEXTRA5 [6] A −μIN 0 0 A −IN 0 0 0 0”
MethodCommunication-Efficient Distributed Optimization with Adaptability to System Heterogeneity
Yu, Z., & Freris, N. M. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10383755 · Cited by 2
A Unified View of Decentralized Algorithms for Sparse Linear Regression
Maros, M., & Scutari, G. (2023) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camsap58249.2023.10403504 · Cited by 1
“DGD-like methods [3, 4, 5, 6], DIGing [10] (supplemented with a projection), and primal-dual methods [11, 12, 13, 14, 15, 16] serve as apt examples of such schemes.”
BackgroundMethodA non-cooperative game-based distributed optimization for chilled water pumps control
Li, S., Pan, Y., & Huang, Z. (2023) · Building Simulation Conference proceedings · doi:10.26868/25222708.2023.1164 · Cited by 1
“Regarding existing works of literature, as representative distributed decomposition algorithm, the First-Order Gradient Algorithm (Nedi’c et al, 2015; Nedi’c et al, 2018a; Nedi’c et al, 2018b), Augmented Lagrangian Method (ALM) (Dhingra et al., 2019), Alternating Direction Multiplier Method (ADMM) (Grübel et al., 2019…”
MethodDistributed Optimization on Riemannian Manifolds for multi-agent networksPreprint
Shah, S. M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.11196 · Cited by 23
“5 Gradient tracking In this section we use the concept of gradient tracking (see [24]) to replace the step (S2) of the algorithm.”
MethodConsensus over evolutionary graphsPreprint
Smyrnakis, M., Freris, N. M., & Tembiné, H. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.02564 · Cited by 1
“In this paper, we will study consensus over time-varying graphs as abstracted by a time-varying Laplacian Lt, dictated by agents’ randomized decisions; that is to say, Lt = L(xt, Et−) is a random matrix that depends on both the state at time t and the topology ‘right before’ time t; consequently, the analysis in exist…”
MethodDynamic Average Diffusion with randomized Coordinate UpdatesPreprint
Ying, B., Yuan, K., & Sayed, A. H. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.08901 · Cited by 1
“A variety of exact first-order distributed algorithms [2], [6], [8], [16], [24], [37] have also been researched in recent years.”
BackgroundMethodInfluentialDecentralized Approximate Newton Methods for In-Network OptimizationPreprint
Wei, H., Qu, Z., Wu, X., et al. (2019) · arXiv (Cornell University) · Cited by 1
Distributed Optimal Power Flow Algorithms Over Time-Varying Communication NetworksPreprint
Zholbaryssov, M., & Domínguez-García, A. D. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.11559 · Cited by 5
“We note that the idea of using the small-gain theorem in the convergence analysis of the distributed algorithms first appeared in [19] for solving an unconstrained optimization problem over time-varying graphs.”
BackgroundMethodVariance-Reduced Stochastic Learning by Networked Agents under Random ReshufflingPreprint
Yuan, K., Ying, B., Liu, J., et al. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1708.01384 · Cited by 1
On linear convergence of two decentralized algorithmsPreprint
Li, Y., & Yan, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.07225 · Cited by 1
“Another topic of interest is decentralized optimization over directed and dynamic graphs [14], [29]–[34].”
BackgroundMethodSystematic Design of Decentralized Algorithms for Consensus OptimizationPreprint
Han, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.01023 · Cited by 1
“This should not come as a surprise, because the DIGing algorithm is based on consensus tracking of the average gradient.”
BackgroundMethodInfluentialDecentralized Stochastic First-Order Methods for Large-scale Machine Learning.Preprint
Xin, R., Kar, S., & Khan, U. A. (2019) · arXiv (Cornell University) · Cited by 2
S-DIGing: A Stochastic Gradient Tracking Algorithm for Distributed OptimizationPreprint
Li, H., Zheng, L., Wang, Z., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.08704 · Cited by 1
“rder to get kxk −x∗k 2 ≤ ε, S-DIGing algorithm needs iterations number k ≥ 1 q log κ ε = 1+ 1 δ log κ ε > 1+ 1 Θ logκ+log ε where Θ is defined in Theorem 1. From the analysis of DIGing algorithm in [14], it can be concluded that the iteration number k ≥ 1+1 Ξ logκ+log 1 ε where Ξ = αµ 1.5−αµ is needed for kxk −x∗k 2…”
MethodInfluentialTime-varying constrained proximal type dynamics in multi-agent network gamesPreprint
Cenedese, C., Belgioioso, G., Grammatico, S., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.08443 · Cited by 1
“In the past years, several results were proposed for optimization problems subject to a time-varying communication network: in [11] the subgradients of the cost functions are bounded and the communication is described by a strongly connected sequence of directed graphs, while in [12] the cost functions are assumed to…”
BackgroundA Private and Finite-Time Algorithm for Solving a Distributed System of Linear EquationsPreprint
Gade, S., Liu, J., & Vaidya, N. H. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.04680 · Cited by 3
Byzantine-Robust Decentralized Stochastic Optimization over Static and Time-Varying NetworksPreprint
Peng, J., Li, W., & Ling, Q. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.06276 · Cited by 1
“ng, which finds applications in mobile computation systems and robotic swarms. Various decentralized stochastic optimization algorithms over time-varying networks have been developed, such as those in [20,21]. Some of the recent works further consider that the time-varying networks are directed such that the designed m…”
BackgroundDecentralized Learning with Lazy and Approximate Dual GradientsPreprint
Liu, Y., Sun, Y., & Yin, W. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.01748 · Cited by 1
“Several popular methods fall into this category, including distributed ADMM (D-ADMM) [6], [7], EXTRA [2], exact diffusion [8]], DIGing [9], COLA [10], and their extensions.”
MethodParallel and Distributed algorithms for ML problemsPreprint
Dvinskikh, D., Gasnikov, A. V., Rogozin, A., & Beznosikov, A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.09585 · Cited by 1
“Особенно отметим работы [4, 72, 56, 51, 65] с хорошим запасом оригинальных идей.”
Decentralized Approximate Newton Methods for Convex Optimization on Networked SystemsPreprint
Wei, H., Qu, Z., Wu, X., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.09481 · Cited by 1
“r methods NN-K, K = 0,1,2 [30] and DQN-K, K = 0,1,2 [32], the exact second-order methods DQM [26], ESOM-K, K = 0,1,2 [25], and NRC [33], as well as two recent first-order methods EXTRA [12] and DIGing [20] in the simulations. A. Globally strongly convex logistic regression We first set λ = 0.01 so that problem (34) is (…”
MethodInfluentialA Distributed Training Algorithm of Generative Adversarial Networks with Quantized GradientsPreprint
Chen, X., Yang, S. H., Shen, L., & Pang, X. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.13359 · Cited by 4
“Some method have been proposed for this kind of dynamic network topology [26, 27].”
BackgroundMethodDependable Distributed Nonconvex Optimization via Polynomial ApproximationPreprint
He, Z., He, J., Chen, C., & Guan, X. (2021) · arXiv (Cornell University) · Cited by 2
On the Convergence of NEAR-DGD for Nonconvex Optimization with Second Order GuaranteesPreprint
Iakovidou, C., & Wei, E. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.14233 · Cited by 1
“Other approaches include primal-dual algorithms [11], [12] (we note that primal-dual and gradient tracking algorithms are equivalent in some cases [3]), the perturbed push-sum method [13], zeroth order methods [14], [15], and stochastic gradient algorithms [16]–[19].”
MethodConvergence Properties of the Distributed Projected Subgradient Algorithm over General GraphsPreprint
Li, W., Chen, Z., Lou, Y., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.16993 · Cited by 1
“Following that, great efforts have been paid to explore distributed algorithms over weight-balanced graphs [13], [8], [25].”
BackgroundLi, W., Assaad, M., & Zheng, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.09387 · Cited by 1
“Sub-gradient based methods have been proposed to solve distributed optimization of the sum of several convex function, over time-varying [7], [8], [9] or asynchronous [10], [11] networks.”
MethodGarg, K., Baranwal, M., Hero, A. O., & Panagou, D. (2019) · arXiv (Cornell University) · Cited by 2
Optimal Gradient Tracking for Decentralized OptimizationPreprint
Song, Z., Shi, L., Pu, S., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.05282 · Cited by 1
“GT [9, 10, 32, 37, 59] O (( κ+ 1 θ2 ) log 1 ǫ ) O (( κ+ 1 θ2 ) log 1 ǫ ) !”
BackgroundMethodInfluentialFinite-Time Consensus Learning for Decentralized Optimization with Nonlinear GossipingPreprint
Chen, J., Wang, S., Carin, L., & Tao, C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.02949 · Cited by 3
“Concerning the graph topology (Nedic et al., 2017; Hale and Egerstedt, 2017), randomized gossiping has been investigated in (Hatano and Mesbahi, 2005; Boyd et al.”
MethodDistributed Sparse Regression via PenalizationPreprint
Yao, J., Scutari, G., Sun, Y., & Honnappa, H. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.06530 · Cited by 5
“…a constant stepsize can be used still preserving convergence to the exact solution; examples include: gradient tracking methods (Qu and Li, 2017, Nedić et al., 2016, Xu et al., 2018, Lorenzo and Scutari, 2016, Sun et al., 2019) and primal-dual schemes (Jakovetić et al., 2011, Shi et al., 2014,…”
BackgroundDistributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement LearningPreprint
Zhao, X., Lei, J., Li, L., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.12961 · Cited by 1
Decentralized convex optimization over time-varying graphs: a surveyPreprint
Rogozin, A., Gasnikov, A. V., Beznosikov, A., & Kovalev, D. A. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.09719 · Cited by 8
“A possible way to build mixing matrices satisfying Assump-tion 1 is to use Metropolis weights [43]:”
BackgroundMethodInfluentialBazizi, T., Maghenem, M. A., Frasca, P., Loría, A., & Panteley, E. V. (2025) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc57313.2025.11312883
Distributed convex optimization with a row-stochastic matrix over directed graphs
Zhang, Y., Lü, Q., Li, H., & Zhang, H. (2017) · International Workshop on Complex Systems and Networks (IWCSN) · doi:10.1109/iwcsn.2017.8276535 · Cited by 1
“In contrast to the column-stochastic matrix referred in [32, 34-37], a rowstochastic matrix is easier to achieve in a distributed fashion (because each agent can locally resolve the weights which are assigned to the incoming information).”
MethodResultFrank-Wolfe variants for minimization of a sum of functionsPreprint
Shah, S. M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.10200
“ere at each iteration an approximate average is obtained ) is studied in [21]. Furthermore, a much more communication efficient version is also proposed which utilizes the gradient tracking concept of [22]. The distributed version we study here is inspired from [5], which studies distributed dual averaging for proximal…”
BackgroundPang, C. H. J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.07734
Methods for Decentralized Signal Processing With Big Data
Wai, H.-T., Scaglione, A., & Moulines, É. (2018) · Elsevier eBooks · doi:10.1016/b978-0-12-813677-5.00015-8
A Proximal Gradient Algorithm for Composite Consensus Optimization over Directed Graphs
Zeng, J., He, T., Ouyang, S., Wang, M., & Chang, X. (2017) · IEEE International Conference on Cyber Technology in Automation, Control, and Intelligent Systems · doi:10.1109/cyber.2017.8446454
Kajiyama, Y., Hayashi, N., & Takai, S. (2019) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.e102.a.343
Accelerated Distributed Primal-Dual Dynamics using Adaptive SynchronizationPreprint
Bansode, P., Kosaraju, K. C., Wagh, S. R., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.00837
“Lately, the algorithms such as distributed gradient (sub-gradient) methods have been widely re-studied with the objective of improvement in the rate of convergence, see [10, 14, 23–25].”
MethodDistributed Optimization in Fixed-Time.Preprint
Baranwal, M., Garg, K., Hero, A. O., et al. (2019) · arXiv (Cornell University)
A Fast Proximal Gradient Algorithm for Decentralized Composite Optimization over Directed NetworksPreprint
Zeng, J., He, T., & Wang, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.03784
Distributed Training with Mobile Agents: Optimization Over Dynamic Directed Graphs
Saadatniaki, F., Xin, R., & Khan, U. A. (2019) · IEEE Data Science Workshop (DSW) · doi:10.1109/dsw.2019.8755589
“3 compares the performance of TV-AB with Push-DIGing [20] with Fig.”
MethodInfluentialLiang, S., Zeng, X., & Hong, Y. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.05542
Nested Distributed Gradient Methods with Stochastic Computation ErrorsPreprint
Iakovidou, C., & Wei, E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.13400
Corrected Gradient Methods for Distributed optimization
Qiu, Z., Xie, L., & You, K. (2019) · Chinese Control Conference (CCC) · doi:10.23919/chicc.2019.8866156
“This algorithm was firstly proposed in [24] and further analyzed in [25] and [26], and then extended to the case of time-varying networks for strongly convex functions [27].”
MethodAsynchronous Subgradient-push Algorithm for Distributed optimization over Directed Graphs
Zhang, J., & You, K. (2019) · Chinese Control Conference (CCC) · doi:10.23919/chicc.2019.8866497
“, [20].”
Primal-dual optimization methods for large-scale and distributed data analytics.Preprint
Jakovetić, D., Bajović, D., Xavier, J., & Moura, J. M. F. (2019) · arXiv (Cornell University)
Schnelle, verteilte Optimierungsmethoden und spieltheoretische Ansätze in vernetzten Systemen
Tatarenko, T. (2020) · at - Automatisierungstechnik · doi:10.1515/auto-2019-0080
“Um diese Beschränkungen zu beseitigen, erweiterten die Autoren von [16] die Ergebnisse der Arbeit [27] für gerichtete, zeitabhängige Kommunikationstopologien und schlugen den so genannten Algorithmus DIGing vor.”
BackgroundInfluentialAccelerated Distributed Optimization over Directed Graphs with Row and Column-Stochastic Matrices
Hu, J., Zhu, Y., Li, H., & Wang, Z. (2019) · IEEE Symposium Series on Computational Intelligence (SSCI) · doi:10.1109/ssci44817.2019.9002658
“( [21]) Given the sequence {bk}k=0, a constant δ ∈ (0, 1), and N ∈ N, define as follows:”
BackgroundMethodEvent-triggered Broadcasting for Distributed Smooth Optimization
Liu, C., Li, H., Shi, Y., & Xu, D. (2019) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc40024.2019.9029758 · Cited by 1
“However, it is shown in some works [5]–[10] that some properties of the objective function, e.g., smoothness and/or strong convexity, validate the use of large constant stepsizes, leading to faster convergence rate.”
BackgroundA Robust Gradient Tracking Method for Distributed Optimization over Directed NetworksPreprint
Pu, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.13980
“It is worth noting that the robust gradient tracking technique employed by R-Push-Pull, i.e., using sk and sk+1−sk to track the aggregated history gradients and the average gradient at step k respectively, can also be applied to other gradient tracking based methods such as Push-DIGing/ADDOPT [23], [45].”
MethodInfluentialOperator Sliding and Decentralized Optimization
Lan, G. (2020) · Springer series in the data sciences · doi:10.1007/978-3-030-39568-1_8
Malaspina, G., Jakovetić, D., & Krejić, N. (2020) · arXiv (Cornell University)
On Sensor Network Localization Exploiting Topological Constraints
Alberto Speranzon, B., Shivkumar, S., & Ghrist, R. (2020) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc45564.2020.9147982
“Typical problems of interest in the context of sensor networks, range from estimation [1], [2], [3] to optimization [4], [5], and localization [6], [7], [8], to name a few.”
BackgroundDistributed Economic Dispatch in Smart Grids: Event-Triggered Scheme
Li, H., Lü, Q., Wang, Z., Liao, X., & Huang, T. (2020) · Springer eBooks · doi:10.1007/978-981-15-6109-2_10
Double-Like Accelerated Distributed optimization Algorithm for Convex optimization Problem
Zhang, K., Xiong, J., & Dai, X. (2020) · International Conference on Information Science and Technology · doi:10.1109/icist49303.2020.9202354
“Then, quite a few new methods have been generated [14]– [16], [24], [25].”
BackgroundMethodInfluentialDistributed Subgradient Algorithm for Multi-agent Optimization with Uncoordinated Dynamic Stepsizes
Ren, X., Li, D., Xi, Y., & Shao, H. (2020) · International Conference on Control and Automation · doi:10.1109/icca51439.2020.9264511
A distributed methodology for approximate uniform global minimum sharing
Bin, M., & Parisini, T. (2021) · Automatica · doi:10.1016/j.automatica.2021.109777
“If the functions ψi in (2) are convex, indeed, different approaches can be used, such as consensus-based (sub)gradient methods [11–16], second-order methods [17, 18], projected [19] and primaldual [20, 21] methods with inequality constraints, methods based on the distributed Alternate Direction Method of Multipliers (…”
BackgroundMethodDistributed Nash Equilibrium Seeking in N-Cluster Games with Fully Uncoordinated Constant Step-SizesPreprint
Pang, Y., & Hu, G. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.11347
Accelerated Distributed Optimization over Digraphs with Stochastic Matrices
Wang, H., Li, H., & Zhou, B. (2021) · Springer eBooks · doi:10.1007/978-981-33-4528-7_4
Linear Convergence for Constrained Optimization Over Time-Varying Digraphs
Wang, H., Li, H., & Zhou, B. (2021) · Springer eBooks · doi:10.1007/978-981-33-4528-7_5
Newton Method over Networks is Fast up to the Statistical PrecisionPreprint
Daneshmand, A., Scutari, G., Dvurechensky, P. E., & Gasnikov, A. V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.06780 · Cited by 9
“The tuning of DiRegINA and DIGing is the same as in Fig.”
BackgroundMethodInfluentialCombining ADMM and tracking over networks for distributed constraint-coupled optimization
Falsone, A., Notarnicola, I., Notarstefano, G., & Prandini, M. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.380
Multi-agent network games with applications in smart electric mobility
Cenedese, C. (2021) · University of Groningen research database (University of Groningen / Centre for Information Technology) · doi:10.33612/diss.166885555
Liu, C., Zhou, Z., Pei, J., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.14075
“DIGing [28], Harnessing [35], and AugDGM [25] are based on similar strategies, for which the convergence rate is Θ((1− β)(2)/κ).”
BackgroundGradient-Consensus Method for Distributed Optimization in Directed NetworksPreprint
Khatana, V., Saraswat, G., Patel, S., & Salapaka, M. V. (2019) · arXiv (Cornell University) · Cited by 1
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.