- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper considers a hybrid decentralized gradient-tracking method with two candidate update directions: the typically used first-order direction and a second-order variant. They give a score to each update direction based on an estimated remaining iteration time using this update strategy, and choose the direction with the higher score to update.
Critical strengths
This paper has the following merits:
-
The idea is very reasonable -- they believe that the iteration number is not a good measure of algorithms, and we should focus on the wall-clock time required to achieve a given accuracy.
-
The presentation is very clear, and when I read equation (7), I understand the idea of this paper.
Critical weaknesses
From my perspective, this paper is not good enough for acceptance since 1) it lacks novelty since this idea is straightforward; 2) it is not mathematically elegant and includes many heuristic designs in the algorithm that may not be reasonable (see below); 3) it is not challenging since the analysis of gradient-tracking-type methods has already been studied in many papers.
I'm not convinced by several heuristic designs in the paper. It is reasonable to predict the wall-clock time required to achieve a given accuracy, but in the decentralized setting, the convergence is jointly determined by all nodes and each node individually estimates the required convergence time may not be that reasonable. Due to similar reasons, the estimate of per-iteration update time \hat{K}_{i,a} is not reasonable.
Minor comments: 1) \tilde{s}_i^t should be introduced after equation (4) since equation (4) has used it; 2) the problem dimension in the simulation is too small for learning tasks.
Questions for authors
Please clarify if some of my comments are incorrect.
2 comments
Thank you for your response. However, it does not change my mind, and I decide to keep the score.
We appreciate the reviewer's constructive feedback. We address the concern and question below.
W1. Thank you for your constructive comments. The novelty of TTA-GT lies in enabling decentralized, continuously online adaptive and lightweight FO/SO direction selection based on predicted time-to-accuracy, rather than simply introducing TTA as an optimization objective.
This simplicity is a deliberate design choice rather than a limitation. The proposed framework captures the key trade-off between optimization progress and execution cost while introducing minimal coordination overhead. It can be applied across different communication topologies (Appendix B) under standard gradient tracking assumptions and adapts to changing computation and communication conditions without requiring global optimization of the update policy. The key contribution is a simple, scalable, and theoretically grounded mechanism that makes decentralized training adaptive to system heterogeneity and runtime variations.
W2. Thank you for your question. We agree the decentralized convergence depends on the joint behavior of all nodes. But the theoretical convergence guarantee of TTA-GT is rigorous and does not rely on the accuracy of the heuristic predictors. The KT-predictor guide the selection between FO and SO directions, while the convergence analysis establishes linear convergence for any applied directions satisfying the alignment and norm conditions in Assumption 3. In particular, the proof does not require accurate predictions of global convergence or a specific switching schedule. We establish coupled recursions for optimization, consensus, and gradient tracking errors, and derive a uniform Lyapunov contraction to guarantee linear convergence under node-dependent, time-varying direction selection (Appendix G).
Although local estimates cannot fully capture global synchronization bottlenecks, they provide a practical decision signal without additional global coordination. Accurately predicting the remaining global training time introduce extra computation and global communication, which can be substantial and may offset the benefits of more accurate prediction. The K-predictor is designed as a local ranking signal rather than an exact prediction of global convergence. It incorporates both local optimization progress and consensus disagreement to account for decentralized interactions. The T-predictor estimates execution costs using measured local computation and communication times, rather than predicting global iteration time. Removing the consensus disagreement term and warm-up increases TTA by 24.3% and 14.1%, respectively (Appendix D), demonstrating the benefit of local surrogate and initializing these estimates.
W3. Thank you for raising this point. We acknowledge that standard gradient tracking already has linear convergence guarantees. While existing hybrid methods’ update policy is predefined, TTA-GT is the first work that allows each node to independently switch between FO and SO directions according to evolving optimization states and runtime conditions. Such time varying and heterogeneous updates make convergence analysis challenging, as the local direction changes are coupled with consensus and gradient tracking errors. Our analysis jointly controls optimization, consensus, and tracking errors through a Lyapunov contraction argument, establishing linear convergence for node level switching sequences satisfying the alignment and norm conditions in Assumption 3, without requiring accurate TTA predictions or a predetermined switching schedule (Appendix G).