- 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
- On Page 5, Lines 268–269, the authors state that for and . However, it is easy to choose and that satisfy these conditions but give . This contradicts the stated range in Theorem 3.
- The manuscript contains several errors/typos, such as, in Appendix A.6 (Page 18, Lines 923–929), substituting into Eq. (39a) yields , rather than as stated in the paper. The same error also appears in the statement of Theorem 4 (Page 6, Lines 285–288).
Questions for authors
- Could you clarify the valid range of and whether correcting it affects Theorem 3?
- Should the condition in Theorem 4 be , and how would this correction affect the theorem?
- 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 whileandreturnstatements 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
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
Responses to Questions 1-3
We sincerely thank the reviewer for the insightful and constructive comments.
All errors and typos in Theorem 3 have been corrected. The revised version is as follows.
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 κ>3ϱ+12ϱ(ϱ+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∗;
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∗;
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∗.
Yes. Indeed, the condition should be α⩾ϱ+12. Theorem 4 has been revised with modifications that accounts for the ranges of α and β. The revised version is as follows.
Theorem,4. For the original DIGing-ATC, suppose that the adjacency matrix W is a doubly stochastic matrix with 0<α<β<2. Then the centralized rate γ∗=ϱ+1ϱ−1 is achieved if and only if β⩽3ϱ+14ϱ and α⩾ϱ+12, and the step size is set as η∗=L+μ2. 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−γ∗, where $\gamma _1\left( \cdot \right) $ and $\gamma _2\left( \cdot \right) $ are defined as (7).
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.