acceptodds
Under review as a conference paper at ICLR 2027

TTA-GT: Time-to-Accuracy Oriented Adaptive First/Second-Order Gradient Tracking for Decentralized Training

Abstract

Decentralized training of deep neural networks has emerged as a promising paradigm for scalable AI development, offering the potential to overcome the scalability limitations of conventional centralized training infrastructures. Decentralized training efficiency is often measured in terms of iteration count. This metric can mis-represent wall-clock efficiency when first-order (FO) and second-order (SO) directions have different runtime costs. We study time-to-accuracy (TTA) oriented direction selection in decentralized gradient tracking (GT). Each node chooses between a low-cost FO direction and a damped SO direction. We propose TTA-GT, a node level selector that estimates a local TTA score for each candidate. The score is the product of predicted remaining iterations and per round time, which decides whether the expected future iteration saving of SO justifies its current runtime cost. Prediction affects efficiency but not correctness, with convergence guaranteed by explicit direction constraints. Under standard strongly convex and smooth assumptions, we prove linear convergence for adaptive FO/SO direction sequences whose applied directions satisfy explicit alignment and norm conditions. Experiments on synthetic quadratic problems and logistic regression on real datasets show that TTA-GT can reduce end-to-end TTA under heterogeneous environments, where nodes vary communication conditions, such as bandwidth and latency, as well as different computation capabilities. In a 300-dimensional quadratic setting, TTA-GT reduces TTA from 2.714 to 1.934, reaching a 28.7% improvement. TTA-GT can achieve significant TTA reduction when SO directions offer sufficient iteration savings, while their additional computation cost remains non-negligible.

Primary area:
optimization
Keywords:
Decentralized Training, Gradient Tracking, Time-to-Accuracy Optimization, Adaptive Direction Selection, Heterogeneous Systems

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_vLxvOpenReview ↗
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:

  1. 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.

  2. 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

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).

Thank you for your response. However, it does not change my mind, and I decide to keep the score.

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

This paper proposes TTA-GT, an adaptive framework for selecting first-order or second-order updates in decentralized gradient tracking. The selection criterion combines predicted remaining iterations with estimated execution time to reduce time to accuracy. The paper establishes linear convergence under strongly convex and smooth assumptions and evaluates the framework on synthetic optimization problems and logistic regression.

Critical strengths

The paper addresses a relevant tradeoff between optimization progress and execution cost. Evaluating time to accuracy rather than iteration count is well motivated when second-order updates offer faster convergence at a higher computational cost.

Critical weaknesses
  1. Limited experimental scope. Both the abstract and introduction motivate the work through decentralized training of deep neural networks. However, the evaluation is limited to small synthetic optimization problems and logistic regression on a single real dataset, with no neural network experiments. Consequently, the effectiveness and computational overhead of the proposed method remain unverified for deep neural network training.

  2. Insufficient comparison with existing methods. The experimental baselines primarily consist of fixed first-order, second-order, and AdamW update policies. Closely related hybrid optimization methods, such as DISH, are discussed but not included in the evaluation. The results therefore demonstrate benefits over fixed update strategies, but provide limited evidence of competitiveness against existing decentralized hybrid optimization methods.

Questions for authors

None

1 comment

Thank you for your positive feedback and constructive comments. We address each comment below.

W1+W2: We have added neural network experiments on Fashion-MNIST using Tanh LeNet-5 (61,706 parameters) under heterogeneous computation and communication conditions (Appendix I, Figure 8 and Table 7). TTA-GT achieves a TTA of 880.38 s, compared with 1,028.36 s for DSGT, yielding a 14.39% reduction. L-BFGS fails to reach the target accuracy within 2,000 iterations. These results demonstrate the effectiveness of TTA-GT on nonconvex neural network training tasks.

Additionally, we have added comparisons with two decentralized hybrid optimization baselines, DISH and DISH-Alt (Appendix H, Figure 7 and Table 6). On a 3,000-dimensional strongly convex problem with a 16-node ring topology, TTA-GT achieves a TTA of 30.35 s, compared with 342.29 s for DISH and 123.36 s for DISH-Alt, achieving 91.1% and 75.4% reductions, respectively. These results demonstrate the competitiveness of TTA-GT against existing decentralized hybrid optimization methods in terms of end-to-end training efficiency.

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

This paper proposes TTA-GT, an adaptive decentralized gradient-tracking algorithm that dynamically selects between first-order (FO) and second-order (SO) update directions. The selection is based on a KT-predictor that estimates the remaining number of iterations and the per-iteration execution time, aiming to minimize total time-to-accuracy (TTA). The authors establish linear convergence under strong convexity, smoothness, and bounded, sufficiently aligned update directions. Experiments on synthetic quadratic optimization, logistic regression, and a nonconvex FO/DAdamW variant demonstrate improvements in TTA under several heterogeneous computation and communication settings.

Critical strengths

Meaningful motivation. The paper highlights an important distinction between iteration complexity and wall-clock efficiency. An optimization method requiring fewer iterations may not achieve faster training when its per-iteration computational cost is higher.

Adaptive optimization framework. Allowing individual nodes to dynamically select different update directions according to local computation and communication conditions is an interesting approach to heterogeneous decentralized training.

Convergence analysis. The paper provides a theoretical framework establishing linear convergence for node-dependent, time-varying update directions under suitable alignment and bounded-norm conditions.

Critical weaknesses

Prohibitive computational and memory costs of Hessian-based updates. The proposed second-order direction requires computing local Hessians and performing Hessian-based linear solves. The storage and computational costs scale poorly with model dimension, making the method impractical for modern large-scale neural-network training. Moreover, the KT-predictor itself requires Hessian information to estimate residual contraction. The experiments are limited to low-dimensional quadratic problems (up to 300 dimensions) and logistic regression (124 dimensions). The nonconvex experiments replace SO with DAdamW rather than validating the original FO/SO method. Consequently, the practical scalability of the proposed algorithm remains unsubstantiated.

Limited theoretical novelty. The main theoretical contribution establishes linear convergence under strong convexity and smoothness, assuming bounded and sufficiently aligned update directions. However, conventional first-order decentralized gradient tracking already achieves linear convergence under similar assumptions. The analysis does not establish an improved convergence rate, better condition-number dependence, or acceleration attributable to SO updates. Furthermore, the KT-based selection mechanism does not enter the convergence-rate analysis, and no theoretical TTA improvement is established.

Potential inconsistency between the algorithm and convergence theorem. Theorem 1 requires every applied update direction to satisfy the alignment and bounded-norm conditions in Assumption 3. However, Appendix A, Algorithm 1 (lines 10–27), appears to allow an invalid SO direction to remain active during the cooldown period. Specifically, when the SO candidate fails the validity checks, the cooldown branch can retain the previous SO mode, potentially violating the assumptions required for convergence. The authors do not clearly establish that the actual algorithm always satisfies the theorem's premises.

Insufficient validation of the TTA predictor. The KT-predictor estimates the remaining iterations using a locally constructed residual and combines this estimate with local execution time. However, the paper does not establish how accurately these local predictions reflect global time-to-accuracy. In synchronized decentralized training, the overall iteration time depends on the joint execution schedule and potential stragglers. The absence of direct prediction-accuracy evaluations makes it difficult to assess whether the proposed selection mechanism reliably optimizes global wall-clock performance.

Questions for authors

Scalability: How can TTA-GT be applied to realistic neural-network models with millions or billions of parameters, given the computational and memory costs of the Hessian? Are Hessians or their factorizations cached in the quadratic experiments? Could the authors provide a detailed runtime breakdown and experiments on substantially higher-dimensional problems?

Theoretical advantage: Since standard first-order gradient tracking already achieves linear convergence, can the authors establish any stronger theoretical guarantee for the proposed adaptive FO/SO method, such as improved convergence-rate dependence on the condition number, local superlinear convergence, or a provable time-to-accuracy advantage?

Validity of the convergence guarantee: In Appendix A, Algorithm 1, can the cooldown mechanism retain an SO direction even when it fails the validity constraints? If so, how is Assumption 3 guaranteed for every applied update? Do safety checks override cooldown in the actual implementation?

TTA prediction quality: How accurately do the predicted remaining iterations and per-round execution times correspond to realized global training time? Could the authors evaluate the predictor's ranking accuracy and compare its performance against simpler adaptive selection policies?

1 comment

We thank reviewer for careful reading and constructive comment. We address each comment and question below.

W1 + Q1. Scalability and additional experiments.

We thank reviewer for this question. We agree that dense Hessian computation and linear solves are costly. But our method does not compute Hessian at every iteration. TTA-GT only computes the Hessians during the warm-up, periodic probes, and when there is indeed a benefit from Hessian information. In the quadratic experiments, Hessians are not cached. We have added d = 3,000 quadratic experiment (Appendix H, Table 6), comprising 16 nodes and 633 iterations, executing a total of 10,128 node updates. The SO was constructed 450 times, of which 390 were adopted, accounting for only 3.85%, and the Hessian computation time accounted for approximately 25.24%. In the new d = 3,000 quadratic experiment, TTA-GT reaches the target in 30.35 s, versus 33.29 s for GT-FO and 92.79 s for GT-SO (8.8% and 67.3% reduction). We have added neural network experiment. On Fashion-MNIST with a 61,706-parameter Tanh LeNet-5 (Appendix I), TTA-GT takes 880.38 s versus 1,028.36 s for DSGT (14.39% reduction).

W2+Q2. Theoretical scope.

We thank reviewer for this question. We do not claim a faster asymptotic rate than standard gradient tracking or provably optimal TTA. The main theoretical challenge is guaranteeing convergence under dynamic, node level update direction selection throughout training. Unlike existing methods with predefined hybrid update patterns, 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. We establish coupled error recursions and construct a weighted Lyapunov function to prove a uniform linear convergence rate for all admissible switching sequences satisfying Assumption 3, regardless of their specific switching patterns or prediction accuracy (Appendix G). With this guarantee, switching of node directions guided by the KT-predictor can proceed without compromising convergence.

W3+Q3. Validity versus cooldown.

Thank you for correctly identifying an ambiguity in Appendix A. If the cooldown mechanism retains an SO direction, it will break the convergence. Safety checks override cooldown in the actual implementation. Every applied SO step must satisfy Eqs. (14)–(16), otherwise the node immediately applies a FO step, even during cooldown. Cooldown only limits FO to SO mode changes. We have stated this precedence explicitly in Algorithm 1 so that every applied direction satisfies Assumption 3 under the conditions.

W4+Q4. Predictor quality.

We thank reviewer for your comment. The predicted remaining iterations and per-round execution times provide approximate estimates of the realized global training time, rather than precise numerical predictions. Our primary goal is to provide a reasonable reference for online direction selection, not to accurately forecast the exact time remaining until global convergence. The actual global training progress is jointly determined by all participating nodes, including their local optimization progress, direction selection decisions, and heterogeneous computation and communication conditions. Consequently, accurately predicting the remaining global training time would require additional coordination and information exchange among nodes to obtain and aggregate their global states. Such operations introduce extra computation and communication overhead, which can be substantial and may offset the benefits of more accurate prediction. We therefore adopt a trade-off between prediction accuracy and estimation overhead, using locally available information to provide each node with a lightweight reference for comparing candidate update directions. The experimental results support the practical effectiveness and robustness of these local estimates. In Appendix D, removing the consensus disagreement term increases the realized TTA by 24.3%, while removing the warm-up phase increases TTA by 14.1%, demonstrating the importance of local progress information and initial runtime measurements. These results suggest that the proposed predictors provide useful decision signals. The existing hybrid methods employ predefined update policies rather than prediction-based selection mechanisms. Therefore, they do not produce predicted rankings, making a direct comparison of adaptive selection policies and predictor ranking accuracy inapplicable.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.