acceptodds
Under review as a conference paper at ICLR 2027

DISTRIBUTED GRADIENT TRACKING ACHIEVING THE OPTIMAL WORST-CASE CONVERGENCE RATE OF CENTRALIZED GRADIENT DESCENT: NECESSARY AND SUFFICIENT CONDITIONS AND BEYOND

Abstract

This paper characterizes the optimal worst-case convergence rate of distributed gradient tracking, revealing its explicit dependence on both the objective functions and the communication network topology. We consider a modified version of the DIGing algorithm that incorporates the adapt-then-combine (ATC) strategy. In the algorithm, a parameter is set to tune the self-loop gain. For -strongly convex and -smooth objective functions, we show that is a threshold in the network topology that governs the worst-case convergence performance of the proposed DIGing-ATC algorithm, where . We prove that the algorithm can achieve the optimal worst-case convergence rate of centralized gradient descent (CGD) if and only if , where and are the smallest nonzero eigenvalue and the largest eigenvalue of the graph Laplacian matrix, respectively. We provide explicit formulas for the corresponding optimal parameters. For connected networks with , the optimal rate of CGD can never be reached. In this case, we further show that the achievable optimal worst-case convergence rate can be characterized as a root of a nonlinear equation depending only on and , which can be computed efficiently using a bisection method. Our derivations and proofs employ nontrivial techniques, including the small gain theorem, Routh stability criteria, and analytic solutions of inequality-constrained optimization. Simulation results are presented to validate the theoretical convergence rates and demonstrate the practical effectiveness of the proposed algorithm.

Primary area:
optimization
Keywords:
Distributed gradient tracking, Worst-case convergence rate, Small gain theorem, System stability, Distributed optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_L5WsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper examines the conditions under which DIGing-ATC can match the worst-case convergence rate of centralized gradient descent for strongly convex, smooth objectives over undirected, connected networks. The authors propose a threshold involving objective conditioning and Laplacian eigenvalues, together with choices of step size and communication weights. They also analyze achievable rates beyond this threshold.

Critical strengths

The paper identifies an explicit network-topology threshold for DIGing-ATC to match the optimal worst-case rate of centralized gradient descent.

Critical weaknesses
  1. On Page 5, Lines 268–269, the authors state that b1,b2,b3∈(0,1)b_1,b_2,b_3\in(0,1) for ρ,κ>1\rho,\kappa>1 and κ>T(ρ)\kappa>T(\rho). However, it is easy to choose ρ\rho and κ\kappa that satisfy these conditions but give b2>1b_2>1. This contradicts the stated range in Theorem 3.
  2. The manuscript contains several errors/typos, such as, in Appendix A.6 (Page 18, Lines 923–929), substituting γc=(ρ−1)/(ρ+1)\gamma_c=(\rho-1)/(\rho+1) into Eq. (39a) yields α≥2/(ρ+1)\alpha\geq 2/(\sqrt{\rho}+1), rather than α≥(ρ+1)/2\alpha\geq(\sqrt{\rho}+1)/2 as stated in the paper. The same error also appears in the statement of Theorem 4 (Page 6, Lines 285–288).
Questions for authors
  1. Could you clarify the valid range of b2b_2 and whether correcting it affects Theorem 3?
  2. Should the condition in Theorem 4 be α≥2/(ρ+1)\alpha\geq 2/(\sqrt{\rho}+1), and how would this correction affect the theorem?
  3. Could you check the manuscript for formatting issues and typos? The paper contains several minor presentation and formatting issues that should be addressed. In Algorithm 1 (Page 5, Lines 254–261), the end while and return statements are not properly separated. Additionally, several typographical errors appear throughout the manuscript, such as "We we show" (Page 2, Line 70), "opitmal step size" (Page 6, Line 290), and "experiemnt" (Page 8, Line 424).
2 comments
AuthorsOpenReview ↗

Responses to Questions 1-3

We sincerely thank the reviewer for the insightful and constructive comments.

  1. All errors and typos in Theorem 3 have been corrected. The revised version is as follows.
    Theorem,3.\mathbf{Theorem \\, 3.} Consider the DIGing-ATC algorithm (2) for $\boldsymbol{f}\in \mathcal{F} _{\mu ,L} $ over the network \mathcal{G} \in \left\\{ \mathcal{G} \right\\} _{\alpha ,\beta}. Suppose that κ>2ϱ(ϱ+1)3ϱ+1\kappa >\frac{2\varrho \left( \sqrt{\varrho}+1 \right)}{3\varrho +1}. Then, we have the following statements:
    i) Set $ \varepsilon _{1}^{*}=\frac{4\varrho }{\beta(3\varrho +1)} $, the worst-case convergence rate is $\gamma_1^*=\gamma _1\left( 1-\varepsilon_1^* \alpha \right) $ with η1∗=1−γ1∗μ\eta _{1}^{*}=\frac{1-\gamma _{1}^{*}}{\mu};
    ii) Set $\varepsilon _{2}^{*}=\min \left\{ \frac{2}{\alpha (\sqrt{\varrho}+1)},\frac{2}{\alpha +\beta} \right\} $, the worst-case convergence rate is $\gamma_2^*=\gamma _2\left( \varepsilon_2^* \beta -1 \right) $ with η2∗=1−γ2∗μ\eta _{2}^{*}=\frac{1-\gamma _{2}^{*}}{\mu};
    iii) Set $ \varepsilon _{3}^{*}=\frac{2}{\alpha+\beta}$, the worst-case convergence rate is $\gamma_3^*=\gamma _2\left( \varepsilon_3^* \beta-1 \right) $ with η3∗=1−γ3∗μ\eta _{3}^{*}=\frac{1-\gamma _{3}^{*}}{\mu}.

  2. Yes. Indeed, the condition should be α⩾2ϱ+1\alpha \geqslant \frac{2}{\sqrt{\varrho}+1}. Theorem 4 has been revised with modifications that accounts for the ranges of α\alpha and β\beta. The revised version is as follows.
    Theorem,4.\mathbf{Theorem \\, 4.} For the original DIGing-ATC, suppose that the adjacency matrix WW is a doubly stochastic matrix with 0<α<β<20<\alpha <\beta <2. Then the centralized rate γ∗=ϱ−1ϱ+1\gamma^*=\frac{\varrho -1}{\varrho +1} is achieved if and only if β⩽4ϱ3ϱ+1\beta \leqslant \frac{4\varrho}{3\varrho +1} and α⩾2ϱ+1\alpha \geqslant \frac{2}{\sqrt{\varrho}+1}, and the step size is set as η∗=2L+μ\eta^* =\frac{2}{L+\mu}. Otherwise, the optimal worst-case convergence rate is given by \gamma ^*=\begin{cases} \gamma _2\left( \beta -1 \right) ,& if\\,\\,\alpha \geqslant 1,\\\\ \max \left\\{ \gamma _1\left( 1-\alpha \right) ,\gamma _2\left( \beta -1 \right) \right\\} ,& if\\,\\,\alpha <1 \\,\\, and \\,\\,\beta >1,\\\\ \gamma _1\left( 1-\alpha \right) ,& if\\,\\,\beta \leqslant 1.\\ \end{cases} The optimal step size is set as η∗=1−γ∗μ\eta ^*=\frac{1-\gamma ^*}{\mu}, where $\gamma _1\left( \cdot \right) $ and $\gamma _2\left( \cdot \right) $ are defined as (7).

  3. We thank the reviewer for this suggestion and apologize for the typos and errors in the original manuscript. We have carefully checked the manuscript to eliminate typos and formatting issues.

AuthorsOpenReview ↗

Thanks for your comments

Dear Reviewer L5Ws,

Thank you for your professional and insightful comments, which have helped us significantly improve the quality of the revised manuscript. As the discussion period is nearing its end, with fewer than two days remaining, we wanted to confirm that we have satisfactorily addressed all of your concerns. If there are any additional points or feedback you'd like us to consider, please let us know. Your insights are invaluable to us, and we are eager to address any remaining issues to further improve our work.

Thank you again for your time and effort in reviewing our paper.

Best regards,
The Authors

Reviewer_DZWsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the optimal worst-case convergence rate of DIGing with ATC for smooth, strongly convex objectives over fixed undirected connected communication graphs. Its main result specifies a topology threshold for matching the optimal centralized gradient descent rate and characterizes the rate above that threshold through a scalar equation. It also provides parameter prescriptions and logistic regression experiments examining connectivity and parameter estimation.

Critical strengths

S1. Theorem 1 gives an explicit connection between topology and convergence, which identifies the threshold T(ϱ)=2ϱ(ϱ+1)/(3ϱ+1)T(\varrho)=2\varrho(\sqrt{\varrho}+1)/(3\varrho+1) using objective conditioning and the Laplacian eigenvalue ratio. This gives a concrete criterion for understanding when additional connectivity can improve the best guaranteed rate and when centralized gradient descent already determines that rate. S2. Theorem 2 and Algorithm 1 reduce parameter selection above the threshold to a monotone scalar equation solved by bisection, providing a simple parameter selection procedure. Together with the explicit parameters below the threshold, this offers a useful tuning procedure from μ,L,α,β\mu,L,\alpha,\beta without requiring numerical solutions of matrix inequalities. S3. The experiments validate the improvement in convergence performance. Section 5 examines logistic regression across several graph conditions, including conservative parameter estimates and an even cycle. Comparisons with accelerated methods using theoretical and tuned step sizes provide evidence that adjusting communication weights can improve convergence in practice.

Critical weaknesses

W1. The abundance of theory necessitates a clearer articulation of core technical insights. Section 3 places the exact rates, suboptimal parameter choices, and original algorithm analysis together in Theorems 1 to 4. Section 4 then moves through the Lur'e reformulation, Routh criteria, and small-gain argument with limited intuition for how ϵ\epsilon balances Equation (12) to yield the threshold. This makes the central technical insight difficult to identify. W2. Theorem 3(ii) permits divergence. For μ=1,L=4\mu=1,L=4, an unweighted star with five nodes has α=1,β=5\alpha=1,\beta=5, giving ϵ=2/3\epsilon=2/3 and b2=7/3b_2=7/3. With quadratic curvature q=4q=4, Equation (20) then has a pole near −4.682-4.682, although the claimed rate is 0.9550.955. Appendix A.5 overlooks the restriction needed for this prescription. W3. Theorem 4 contains a consequential threshold error. Setting ϵ=1\epsilon=1 in Theorem 1 requires α≥2/(ϱ+1)\alpha\geq2/(\sqrt{\varrho}+1), while Theorem 4 and Appendix A.6 state its reciprocal. For a valid stochastic matrix with α=0.9,β=1.1\alpha=0.9,\beta=1.1 and ϱ=4\varrho=4, this error selects the alternative formula and predicts γ≈0.291\gamma\approx0.291, violating the centralized lower bound of 0.60.6. W4. The experiments provide limited evidence for the exact rate. Figure 3 evaluates the theoretical formulas, while Figure 4(b) shows overlapping trajectories on one logistic regression problem. Appendix C adds robustness studies without comparing measured contraction factors with the predicted optimum on extremal quadratics. This leaves limited independent evidence for the exact threshold and the validity of the parameter prescriptions.

Questions for authors

Q1.Could you explain intuitively how tuning ϵ\epsilon balances Equations (12a) and (12b) to produce Theorem 1's threshold? Q2. What is the corrected validity range of Theorem 3(ii), and how should its parameters change for the five-node star with ϱ=4\varrho=4? Q3. Is Theorem 4's spectral threshold a reciprocal error, and what corrected rate formula resolves the contradiction at ϱ=4,α=0.9,β=1.1\varrho=4,\alpha=0.9,\beta=1.1? W4. Can you compare measured and predicted contraction factors on extremal quadratics immediately below and above T(ϱ)T(\varrho), using the state error in Definition 1?

2 comments
AuthorsOpenReview ↗

Responses to Questions Q1-Q4

  1. We thank the reviewer for this insightful and helpful question. In the proof of Theorem 1, we first solve the problem of minimizing γ\gamma subject to (11a)-(11b), whose optimal solution is $\gamma^* =\frac{\varrho-1}{\varrho+1} $, and $ \eta^*=\frac{2}{L+\mu} $, which correspond to the optimal rate and step size of CGD. We then determine whether there exists an ε\varepsilon satisfying inequalities (12a) and (12b), which is equivalent to determining whether the threshold condition holds.

    We have added the above explanation at the end of ''Key Step in the Proof of Theorem 1'' (Section 4, Page 8). We also added Remark 2 to clarify the meaning of the ε∗\varepsilon ^* interval (Section 3, page 5).

  2. Theorem 3(ii) has been corrected. Note that the condition −γ∗<ε∗α−1<ε∗β−1<γ∗-\gamma^*<\varepsilon^*\alpha-1<\varepsilon^*\beta-1<\gamma^* holds. For the five-node star graph with ϱ=4\varrho=4, we have γ2∗=0.9732,ε2∗=0.3333,η2∗=0.0268.\gamma_2^*=0.9732,\qquad \varepsilon_2^*=0.3333,\qquad \eta_2^*=0.0268.

    The updated version of Theorem 3 is as follows.
    Theorem,3.\mathbf{Theorem \\, 3.} Consider the DIGing-ATC algorithm (2) for $\boldsymbol{f}\in \mathcal{F} _{\mu ,L} $ over the network \mathcal{G} \in \left\\{ \mathcal{G} \right\\} _{\alpha ,\beta}. Suppose that κ>2ϱ(ϱ+1)3ϱ+1\kappa >\frac{2\varrho \left( \sqrt{\varrho}+1 \right)}{3\varrho +1}. Then, we have the following statements:
    i) Set $ \varepsilon _{1}^{*}=\frac{4\varrho }{\beta(3\varrho +1)} $, the worst-case convergence rate is $\gamma_1^*=\gamma _1\left( 1-\varepsilon_1^* \alpha \right) $ with η1∗=1−γ1∗μ\eta _{1}^{*}=\frac{1-\gamma _{1}^{*}}{\mu};
    ii) Set $\varepsilon _{2}^{*}=\min \left\{ \frac{2}{\alpha (\sqrt{\varrho}+1)},\frac{2}{\alpha +\beta} \right\} $, the worst-case convergence rate is $\gamma_2^*=\gamma _2\left( \varepsilon_2^* \beta -1 \right) $ with η2∗=1−γ2∗μ\eta _{2}^{*}=\frac{1-\gamma _{2}^{*}}{\mu};
    iii) Set $ \varepsilon _{3}^{*}=\frac{2}{\alpha+\beta}$, the worst-case convergence rate is $\gamma_3^*=\gamma _2\left( \varepsilon_3^* \beta-1 \right) $ with η3∗=1−γ3∗μ\eta _{3}^{*}=\frac{1-\gamma _{3}^{*}}{\mu}.

  3. Yes, there is a reciprocal error in the spectral threshold. It should be $ \alpha \geqslant \frac{2}{\sqrt{\varrho}+1}.$ For ϱ=4\varrho=4, α=0.9\alpha=0.9, β=1.1\beta=1.1, we have γ∗=0.6\gamma^*=0.6, and η∗=0.4\eta^*=0.4. (Assume μ=1\mu=1.)

  4. We thank the reviewer for the insightful and professional suggestion. We have added numerical examples with quadratic objective functions, for which the algorithm iteration reduces to an LTI dynamical system. By varying ϱ\varrho of the quadratic functions, we compare the state error with that predicted by Theorems 1 and 2. For the five-node star network, we select several quadratic objective functions near the threshold. The experiment results are added to Section 5 in the revised manuscript (page 9). Fig. 4b shows that when ϱ≥43.0088\varrho\ge 43.0088 (i.e., κ≤T(ϱ)\kappa\le\mathcal{T}(\varrho)), DIGing-ATC attains the optimal convergence rate of CGD. When ϱ<43.0088\varrho<43.0088 (i.e., κ>T(ϱ)\kappa>\mathcal{T}(\varrho)), DIGing-ATC converges more slowly than CGD and thus fails to attain the optimal CGD rate.

AuthorsOpenReview ↗

Thanks for your feedback

Dear Reviewer DZWs,

Thank you for your professional and insightful comments, which have helped us significantly improve the quality of the manuscript. As the discussion period is nearing its end, with fewer than two days remaining, I wanted to confirm that we have satisfactorily addressed all of your concerns. If there are any additional points or feedback you would like us to consider, please let us know. Your insights are invaluable to us, and we are eager to address any remaining issues to improve our work.

Thanks again for your time and effort in reviewing our paper.

Best regards,
The Authors

Reviewer_RkCuOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the optimal worst-case asymptotic convergence factor of a two-parameter DIGing-ATC gradient-tracking algorithm for distributed optimization over fixed, connected, undirected networks, with each local objective being μ\mu-strongly convex and LL-smooth. The parameters control the gradient step and the scaling of the graph Laplacian.

Writing ϱ=L/μ\varrho=L/\mu and κ=β/α\kappa=\beta/\alpha, the main result claims that the algorithm matches the optimal fixed-step centralized gradient descent factor (ϱ−1)/(ϱ+1)(\varrho-1)/(\varrho+1) if and only if κ≤2ϱ(ϱ+1)3ϱ+1.\kappa\leq \frac{2\varrho(\sqrt{\varrho}+1)}{3\varrho+1}. Above this threshold, the paper characterizes the claimed optimal factor through a scalar nonlinear equation that can be solved by bisection. It also gives explicit suboptimal parameter choices and a specialization to the original DIGing-ATC method.

The analysis combines a quadratic lower bound, spectral stability conditions, and a small-gain argument to establish attainability over the full class of smooth, strongly convex functions. Numerical results include plots of the theoretical characterization and distributed logistic regression on a9a, as well as additional experiments on parameter-estimation sensitivity and communication-weight adjustment.

Critical strengths
  1. An explicit and potentially consequential characterization of the network–objective trade-off. The paper addresses a clear question: when can a distributed gradient-tracking method match the optimal fixed-step factor of centralized gradient descent? A necessary-and-sufficient threshold expressed directly through ϱ=L/μ\varrho=L/\mu and κ=β/α\kappa=\beta/\alpha, together with corresponding parameter formulas, would be more informative than a conservative sufficient step-size bound. The characterization beyond the threshold is also valuable because it explains the network-limited regime rather than stopping at a condition under which centralized performance is possible. Subject to the correctness issues below, this is the main reason to consider acceptance.

  2. A useful analytical approach with constructive parameter selection. The proposed strategy combines a lower bound from common-curvature quadratics with an upper-bound argument intended to cover heterogeneous, nonlinear local objectives. Establishing that these bounds coincide would provide a strong explanation of worst-case behavior. The scalar bisection characterization also makes the theoretical result operational: users with bounds on the objective and Laplacian spectra can compute parameters without solving a semidefinite program or relying entirely on empirical tuning.

Critical weaknesses

1. Several stated parameter guarantees fail on admissible quadratic problems.

These are not only presentation issues.

For Theorem 3(ii), the assertion that b2=2κ/(ϱ+1)−1b_2=2\kappa/(\sqrt{\varrho}+1)-1 belongs to (0,1)(0,1) whenever κ>T(ϱ)\kappa > T(\varrho) is incorrect. Take μ=1\mu=1, L=4L=4, α=1\alpha=1, and β=10\beta=10. Then b2=17/3b_2=17/3, and the prescribed parameters are approximately

γ2⋆=0.907561,η2⋆=0.0924394,ε2⋆=23.\gamma_2^{\star}=0.907561,\qquad \eta_2^{\star}=0.0924394,\qquad \varepsilon_2^{\star}=\frac{2}{3}.

For the curvature-LL quadratic mode associated with Laplacian eigenvalue 1010, the characteristic polynomial is

(z−w)2+Lη2⋆w2(z−1),w=1−ε2⋆β=−173.(z-w)^2+L\eta_2^{\star}w^2(z-1),\qquad w=1-\varepsilon_2^{\star}\beta=-\frac{17}{3}.

Its roots are approximately −22.2991-22.2991 and −0.907561-0.907561. Thus, the prescribed iteration is unstable, including for initial conditions satisfying the required gradient-tracker initialization. The condition b2<1b_2 < 1 would require the additional restriction κ<ϱ+1\kappa < \sqrt{\varrho}+1, which is absent.

For Theorem 3(iii), the stated ε3⋆=(κ−1)/(κ+1)\varepsilon_3^{\star}=(\kappa-1)/(\kappa+1) appears to confuse the symmetric spectral deviation with the Laplacian scaling. The scaling that gives

1−εα=εβ−1=κ−1κ+11-\varepsilon\alpha=\varepsilon\beta-1=\frac{\kappa-1}{\kappa+1}

is ε=2/(α+β)\varepsilon=2/(\alpha+\beta).

Theorem 4 also fails as written. Consider the matrix WW whose three rows are (4,7,4)/15(4,7,4)/15, (7,4,4)/15(7,4,4)/15, and (4,4,7)/15(4,4,7)/15. This is a nonnegative, symmetric, doubly stochastic matrix, and I−WI-W has nonzero eigenvalues α=0.8\alpha=0.8 and β=1.2\beta=1.2. With μ=1\mu=1 and L=9L=9, the printed centralized-rate condition fails because it requires α≥2\alpha\geq 2. The "otherwise" formula then gives

γ⋆=max⁡γ1(0.2),γ2(0.2)≈0.653932,η⋆≈0.346068.\gamma^{\star}=\max\\{\gamma_1(0.2),\gamma_2(0.2)\\}\approx 0.653932,\qquad \eta^{\star}\approx 0.346068.

However, on a consensual curvature-LL quadratic mode, the update factor is

1−Lη⋆≈−2.11461,1-L\eta^{\star}\approx -2.11461,

so the method diverges. The printed condition on α\alpha is also inconsistent with Theorem 1 specialized to ε=1\varepsilon=1, which gives α≥2/(ϱ+1)\alpha\geq 2/(\sqrt{\varrho}+1).

These errors matter because explicit, reliable parameter selection is a central advertised benefit of the paper. These examples concern the auxiliary parameter prescriptions; they do not establish that the principal characterization in Theorems 1-2 is false.

2. The sufficiency argument for the main characterization needs completion.

Section 4 concludes stability from

∥H(γ⋆z)∥∞∥Δloop∥∞≤1.\lVert H(\gamma^{\star}z)\rVert_\infty\lVert\Delta_{\mathrm{loop}}\rVert_\infty\leq 1.

The standard small-gain theorem requires a strict gain inequality; equality alone does not justify the asserted stability. Definition 1 only requires convergence for every r>γ⋆r > \gamma^{\star}, with r≤1r\leq 1, so this may be repairable by establishing stability and a strict small-gain bound for H(rz)H(rz) at every such rr. That argument should be supplied rather than identifying the boundary inequality with stability.

Moreover, Appendix A.7 substitutes equalities at both spectral endpoints when proving Lemma 6. Those equalities correspond to the active constraints in the network-limited optimum, but they do not hold for every ε⋆\varepsilon^{\star} in the interval allowed by Theorem 1. A uniform inequality covering that entire interval is needed. I am not claiming that the full norm bound is false: the consensus transfer function may already attain the claimed norm. However, the supplied endpoint calculation does not establish the stated result in its full scope.

This is consequential because the small-gain step is what upgrades the quadratic lower bound to an exact guarantee for the entire smooth strongly convex class.

Questions for authors

1. Corrected parameter statements.

Can you provide corrected versions of Theorems 3-4, including the admissible range of b2b_2, the intended scaling ε3⋆\varepsilon_3^{\star}, and the centralized-rate condition in Theorem 4?

Please also address the domains of the fallback expressions. For example, ϱ=9\varrho=9 and α=1.4\alpha=1.4 give γ1(1−α)=8\gamma_1(1-\alpha)=8 under the displayed formula. Which results require only a typographical correction, and which require additional restrictions or a revised case distinction?

2. Sufficiency for the full function class.

Can you establish the required convergence for every r∈(γ⋆,1]r\in(\gamma^{\star},1], as specified in Definition 1, including stability of H(rz)H(rz) and a strict small-gain bound?

Please also justify the norm estimate uniformly over the entire optimal ε⋆\varepsilon^{\star} interval in Theorem 1, without assuming that both endpoint constraints are equalities. This is a request to complete the proof of the current claim, not to extend the function class.

3. Are signed communication weights permitted?

Remark 3 calls I−ε⋆LI-\varepsilon^{\star}\mathcal{L} doubly stochastic, but the parameter formulas do not always ensure entrywise nonnegativity.

For example, an unweighted five-node star has α=1\alpha=1, β=5\beta=5, and maximum degree 44. With ϱ=44\varrho=44, Theorem 1 permits matching the centralized rate and prescribes

ε⋆∈[244+1,176665]≈[0.262012,0.264662].\varepsilon^{\star}\in\left[\frac{2}{\sqrt{44}+1},\frac{176}{665}\right]\approx[0.262012,0.264662].

Every value in this interval makes the central node's self-weight 1−4ε⋆1-4\varepsilon^{\star} negative. Is the intended algorithm allowed to use signed, sum-preserving weights? If nonnegative mixing weights are required, how does that additional constraint change the threshold and optimal parameters?

4. Direct validation of the rate characterization.

Can you include a controlled quadratic experiment comparing the predicted factors with the exact iteration spectral radius and measured asymptotic convergence, on both sides of the threshold? Such an experiment would directly test the parameter formulas and would have exposed the failures above.

For the logistic-regression comparisons, please distinguish evidence for the worst-case guarantee from empirical superiority over accelerated methods, and report comparable tuning effort and communication cost. Faster performance of an accelerated baseline on one instance does not itself contradict optimality within the DIGing-ATC family.

2 comments
AuthorsOpenReview ↗

Responses to Questions 1-2

Sincere thanks for the insightful and professional comments.

  1. Corrected Parameter Statements
    We apologize for the errors and typos in Theorems 3 and 4. The reviewer's insights are entirely correct. There should be a range constraint on b2b_2 in Theorem 3(ii). In addition, ε3∗=2β+α\varepsilon_3^*=\frac{2}{\beta+\alpha} in Theorem 3(iii), and α⩾2ρ+1\alpha\geqslant \frac{2}{\sqrt{\rho}+1} in Theorem 4. The revised theorems are as follows.
    Theorem,3.\mathbf{Theorem \\, 3.} Consider the DIGing-ATC algorithm (2) for $\boldsymbol{f}\in \mathcal{F} _{\mu ,L} $ over the network \mathcal{G} \in \left\\{ \mathcal{G} \right\\} _{\alpha ,\beta}. Suppose that κ>2ϱ(ϱ+1)3ϱ+1\kappa >\frac{2\varrho \left( \sqrt{\varrho}+1 \right)}{3\varrho +1}. Then, we have the following statements:
    i) Set $ \varepsilon _{1}^{*}=\frac{4\varrho }{\beta(3\varrho +1)} $, the worst-case convergence rate is $\gamma_1^*=\gamma _1\left( 1-\varepsilon_1^* \alpha \right) $ with η1∗=1−γ1∗μ\eta _{1}^{*}=\frac{1-\gamma _{1}^{*}}{\mu};
    ii) Set $\varepsilon _{2}^{*}=\min \left\{ \frac{2}{\alpha (\sqrt{\varrho}+1)},\frac{2}{\alpha +\beta} \right\} $, the worst-case convergence rate is $\gamma_2^*=\gamma _2\left( \varepsilon_2^* \beta -1 \right) $ with η2∗=1−γ2∗μ\eta _{2}^{*}=\frac{1-\gamma _{2}^{*}}{\mu};
    iii) Set $ \varepsilon _{3}^{*}=\frac{2}{\alpha+\beta}$, the worst-case convergence rate is $\gamma_3^*=\gamma _2\left( \varepsilon_3^* \beta-1 \right) $ with η3∗=1−γ3∗μ\eta _{3}^{*}=\frac{1-\gamma _{3}^{*}}{\mu}. \

     	$\mathbf{Theorem \\, 4.}$ 
     	For the original DIGing-ATC, suppose that the adjacency matrix $W$ is a doubly stochastic matrix with $0<\alpha <\beta <2$. Then the centralized rate $\gamma^*=\frac{\varrho -1}{\varrho +1}$ is achieved if and only if $\beta \leqslant \frac{4\varrho}{3\varrho +1}$ and $\alpha \geqslant \frac{2}{\sqrt{\varrho}+1}$, and the step size is set as $\eta^* =\frac{2}{L+\mu}$.	Otherwise, the optimal worst-case convergence rate   is given by
     	$$\gamma ^*=\begin{cases}
     			\gamma _2\left( \beta -1 \right) ,&		if\\,\\,\alpha \geqslant 1,\\\\
     			\max \left\\{ \gamma _1\left( 1-\alpha \right) ,\gamma _2\left( \beta -1 \right) \right\\} ,&		if\\,\\,\alpha <1 \\,\\, and \\,\\,\beta >1,\\\\
     			\gamma _1\left( 1-\alpha \right) ,&		if\\,\\,\beta \leqslant 1.\\
     		\end{cases}$$
     	The optimal step size is set as $\eta ^*=\frac{1-\gamma ^*}{\mu}$, where \$\gamma _1\left( \cdot \right) \$ and \$\gamma _2\left( \cdot \right) \$ are defined as (7).
    
  2. Sufficiency for the Full Function Class
    Thanks for the insightful comments.
    Response to the first comment:
    Since γ∗\gamma^* is the optimal solution of (P2) with parameters η∗\eta^* and ε∗\varepsilon^*, the poles of Φ(γ∗z)\varPhi \left( \gamma^* z \right) lie within the closed unit disc for all $q\in \left[ \mu ,L \right] $ and $ \lambda \in \left[ \alpha ,\beta \right]$. Then all poles of H(γ∗z)H\left( \gamma^* z \right) also lie within the closed unit disc, since H(⋅)H(\cdot) corresponds to the system with q=μ+L2q=\frac{\mu +L}{2}. Hence, H(z)H(z) is analytic in the region of the complex plane ∣z∣>γ∗|z|>\gamma^* (including the point at infinity). By the maximum modulus principle, for any γ>γ∗\gamma > \gamma^*, we have max⁡θ∥Hi(γejθ)∥<max⁡θ∥Hi(γ∗ejθ)∥⩽2L−μ.\underset{\theta}{\max}\left\| H_i\left( \gamma e^{j\theta} \right) \right\|<\underset{\theta}{\max}\left\| H_i\left( \gamma ^*e^{j\theta} \right) \right\|\leqslant \frac{2}{L-\mu}. Hence, ∥H(γz)∥∞<2L−μ\left\| H\left( \gamma z \right) \right\| _{\infty}<\frac{2}{L-\mu}, and $ \left| H\left( \gamma z \right) \right| _{\infty}\left| \varDelta _{loop} \right| _{\infty}<\frac{2}{L-\mu}\cdot \frac{L-\mu}{2}=1$. Then it follows from small gain theorem that the whole system is $\gamma $-stable for any γ>γ∗\gamma > \gamma^*.
    The above derivation has been added at the end of "Step 3. Verifying the attainability of the lower bound via small gain theorem" (Section 4, page 8).

    Response to the second comment:
    The key idea is that, throughout the entire optimal interval for ε∗\varepsilon^*, 0<1−ε∗α≤1−2ϱ+1=1−αβg1(γ∗),0<1-\varepsilon^*\alpha \le 1-\frac{2}{\sqrt{\varrho}+1}=1-\frac{\alpha}{\beta}g_1(\gamma^*), and 0<ε∗β−1≤4ϱ3ϱ+1−1=g2(γ∗)−1.0<\varepsilon^*\beta-1 \le \frac{4\varrho}{3\varrho+1}-1=g_2(\gamma^*)-1. Hence, for any λ∈[α,β]\lambda\in[\alpha,\beta], we have ε∗λ\varepsilon^*\lambda lies in the interval $ \left[\frac{2}{\sqrt{\varrho}+1},\frac{4\varrho}{3\varrho+1}\right].$ Therefore, the norm ∣h(⋅,⋅)∣\left|h(\cdot,\cdot)\right| is less than L−μL+μ\frac{L-\mu}{L+\mu}, provided that ε∗\varepsilon^* is not at the boundary of this interval.
    We have added Remark 2 to clarify the meaning of the optimal ε∗\varepsilon^* interval (Section 3, page 5). We have also added a detailed derivation to the proof of Lemma 6 (Appendix A.7, page 21).

AuthorsOpenReview ↗

Responses to Questions 3-4

  1. Are Signed Communication Weights Permitted?
    The doubly stochastic matrix I−ε∗LI-\varepsilon^*\mathcal{L} may have negative diagonal entries, whereas all off-diagonal entries are non-negative and are determined by the communication network satisfying Assumption 2. The interaction among neighbors is the same as in the case of positive self-loop gains. Thus, no additional implementation difficulty arises. Moreover, as shown by the theorems, negative self-loop gains may yield faster convergence.
    In the revised manuscript, we have added the above explanation to Remark 4 (Section 3, page 6).
    We conducted experiments on an unweighted 55-node star graph with controlled quadratic functions (Section 5, page 9 of the revised manuscript). We tested three points within the optimal ε∗\varepsilon^* interval and summarized the results in Table 1 of the appendix (page 23). The results confirm that negative self-loop gain is permissible and leads to a faster convergence rate.

  2. Direct Validation of the Rate Characterization
    We thank the reviewer for the helpful suggestion. In the revised manuscript, we have added experiments in Section 5 (page 9) with controlled quadratic objective functions, for which the algorithm iteration reduces to an LTI dynamical system. The convergence rate is exactly the second-largest eigenvalue modulus of the state transition matrix, which can be computed directly. We consider two graphs: an unweighted 5-node star graph (as suggested by the reviewer); and a 5-node cycle graph with all edge weights set to 0.5. The results are shown in Figure 4a (Section 5, page 9). The experiments show that the numerical convergence rate is consistent with the theoretical results.

    For the logistic-regression comparisons, we have added an explanation of the worst-case guarantee following the suggestion. No tuning is required to implement our algorithm. In contrast, accelerated algorithms must be tuned in practical implementations to achieve the expected faster convergence, since there is no clear rule on how to select proper parameters. In our experiments, the step size is tuned following the guidelines in Li & Lin (2024) and Qu & Li (2019). Moreover, the communication cost is lower than that of the accelerated method. We agree that the faster performance of an accelerated baseline on a single instance does not contradict the optimality of the DIGing-ATC algorithm. We have added the above explanation to the revised manuscript (Section 5, Page 10).

Comments on the paper

2 comments

Thank you for your appreciation. We are indebted to your insightful and professional comments, which improve the revised manuscript significantly. Thanks again.

AuthorsOpenReview ↗

Paper Summary and Main Contribution

Dear Conference Program Chairs, Senior Area Chairs, Area Chairs, Reviewer DZWs, and Reviewer L5Ws,

This paper addresses the following questions. Can we design a distributed gradient-tracking algorithm that achieves the optimal worst-case convergence rate of centralized fixed-step gradient descent (CGD)? If so, what are the necessary and sufficient conditions, and which parameter choices achieve this rate? The main contributions of this paper are as follows.

  • We characterize the optimal worst-case convergence rate of the proposed DIGing-ATC algorithm and show explicitly how it depends on both the objective condition number and the communication network topology.

  • We identify a threshold $ T(\varrho)=\frac{2\varrho(\sqrt{\varrho}+1)}{3\varrho+1}, $ where ϱ=L/μ\varrho=L/\mu is the objective condition number. We prove that DIGing-ATC achieves the optimal worst-case CGD rate $ \frac{\varrho-1}{\varrho+1} $ if and only if $ \kappa=\beta/\alpha\leq T(\varrho), $ where β\beta and α\alpha are the largest and smallest nonzero eigenvalues of the graph Laplacian, respectively. We provide explicit formulas for the corresponding optimal parameters.

  • For connected networks with κ>T(ϱ)\kappa>T(\varrho), the best achievable worst-case convergence rate of DIGing-ATC is strictly worse than the optimal CGD rate. We characterize this rate as a root of a scalar nonlinear equation that depends only on ϱ\varrho and κ\kappa. The root lies in a specified subinterval of (0,1)(0,1) and can be computed efficiently by bisection.

To the best of our knowledge, this is the first explicit necessary-and-sufficient condition for DIGing-ATC to match the optimal worst-case rate of CGD, together with explicit formulas for the parameters that attain it. We thank Reviewer RkCu for summarizing the paper and recognizing this contribution.

We are grateful to all three reviewers for pointing out errors and typos in Theorems 3 and 4, which we have corrected in the revised manuscript. We would also like to clarify that Theorems 3 and 4 are considerably less important than Theorems 1 and 2, for Theorems 1 and 2 contain all the main contributions described above. Although we received no further feedback from the other two reviewers, we appreciate their first-round comments and suggestions, which helped us improve the manuscript. We respectfully ask the Area Chairs and Senior Area Chairs to consider the revised manuscript for acceptance.

Yours sincerely,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.