ACCELERATED G RADIENT D ESCENT FOR FASTER C ONVERGENCE WITH M INIMAL OVERHEAD Manuel Graca∗ IST, ULisboa Lisbon, Portugal
L. Miguel Silveira IST, ULisboa Lisbon, Portugal
Arlindo Oliveira IST, ULisboa Lisbon, Portugal
Frank Liu† † Old Dominion University Norfolk, VA USA
arXiv:2605.16017v1 [cs.LG] 15 May 2026
A BSTRACT In this paper, we present CT-AGD (Curvature-Tuned Accelerated Gradient Descent), an optimization method for non-convex optimization problems in deep learning training tasks. CT-AGD is a general boosting procedure that accelerates first-order methods by explicitly capturing the local curvature using finitedifference quotients, and the development of heuristics aimed at mitigating noise and bias introduced by stochastic mini-batch training. CT-AGD has a comparable storage and computational overhead as adaptive gradient methods such as Adam. Our extensive experiments demonstrate that CT-AGD achieves the same level of accuracy as the baseline first-order methods, yet reduces the required training epochs by 33% on average.
1
I NTRODUCTION
We investigate the optimization methods in the training of deep neural networks: θ⋆ = arg min L(θ) = arg min E(x,y)∼P ℓ(fθ (x), y) θ∈Rd
θ∈Rd
(1)
where fθ : X → Y represent the neural network, θ ∈ Rd are trainable parameters, ℓ(·) is the point-wise loss function, and P is the data distribution. The core of training tasks is essentially the optimization of a large-scale non-convex loss function, requiring substantial computational resources and energy (Strubell et al., 2019; Schwartz et al., 2020; Patterson et al., 2022). Despite significant progress in accelerator hardware (Sze et al., 2020; Jouppi et al., 2017; Hennessy & Patterson, 2019), the optimizers remain critical to reduce end-to-end training time while ensuring stable convergence (Bottou et al., 2018). Although higher-order, particularly second-order, optimization methods can achieve faster convergence under smoothness and convexity assumptions (Nesterov, 2004; Boyd & Vandenberghe, 2004; Bubeck, 2015), their theoretical advantages are often diminished in deep learning training due to the non-convexity of the loss function landscape, as well as stochastic noises from mini-batch sampling and data augmentation drift (Yao et al., 2021; Bollapragada et al., 2018). First-order methods (SGD and its variants) remain popular in deep learning training due to their robustness and relatively low computational cost (Goyal et al., 2017; Smith et al., 2018). Adaptive gradient methods using exponential moving averages have shown great success in addressing some key shortcomings of the first-order optimization methods, particularly poor convergence due to the noisy gradient from mini-batching sampling and the sensitivity of learning rates to different scales of widely different curvature. Among them, ADAM (Kingma & Ba, 2015), RMSProp (Tieleman & Hinton, 2012) and ADADelta (Zeiler, 2012) have been deployed in the successful training of many applications. However, as pointed out in Reddi et al. (2018b); Zaheer et al. (2018a), ADAM-family of adaptive gradient methods may fail to converge to the optimal solution in some relatively simple convex optimization problems when a constant mini-batch size is used. Improvements were also proposed in Zaheer et al. (2018a) to address the convergence issues with better adaptivity of the learning rate. Implicitly, the adaptive gradient methods can be considered as an approximation of the diagonal entries of the full Hessian matrix (or local curvature), and use the ∗
1
information to provide better learning rates for different dimensions, versus a global learning rate in the first-order methods. In this paper, we take a more direct approach by calculating approximations to the diagonal entries of the second-order derivatives (or quotients, or second differences) during the training steps. Our proposed method, Curvature-Tuned Accelerated Gradient Descent or CT-AGD, accumulates the second differences that are lightweight approximations of the local curvature. Within each epoch, CT-AGD behaves the same as a standard first-order optimizer. In parallel, CT-AGD accumulates per-coordinate quotients, which serve as approximations of local curvatures. Clamp functions are applied to guard the quotients into positive intervals, which suppress oversized steps, and to ensure optimization is stable. At the end of each epoch, CT-AGD performs one additional first-order update, using the quotient accumulation, which can be viewed as the approximation of the diagonal of the Hessian, and provides a direct measure of the local curvature. These direct estimates of the local curvature are also used in the subsequent epoch for faster convergence. Contributions The main contributions of this paper are as follows: 1. We introduce a simple, memory- and compute-efficient optimizer, CT-AGD, that can be deployed with existing first-order methods (e.g., SGD, ADAM, etc) with a once-per-epoch curvature estimation. By deploying CT-AGD the optimization method can capture the local curvature while preserving first-order scalability. 2. We conduct extensive numerical experiments on the effectiveness and efficiency of CT-AGD. We also provide an intuitive visualization and benchmarking testbed on DL-like objectives. We hope this testbed can be valuable in supporting transparent and reproducible evaluation of future research activities in this direction. R ELATED W ORK First-order methods. Stochastic gradient descent (SGD) remains the cornerstone of large-scale NN training because of its low per-iteration cost and strong anytime performance. Practical accelerations include momentum (Polyak, 1964) and Nesterov’s acceleration (Nesterov, 2004), as well as adaptive methods that maintain running statistics of gradients to adjust coordinate-wise step sizes (without modelling curvature explicitly). Representative examples are AdaGrad (Duchi et al., 2011), RMSProp (Tieleman & Hinton, 2012), AdaDelta (Zeiler, 2012), AdamW (Loshchilov & Hutter, 2019), NAdam (Dozat, 2016), Yogi (Zaheer et al., 2018b) and Adam (Kingma & Ba, 2015). Empirically, such methods are competitive across many workloads, but can be sensitive to hyperparameters, and they may converge to an approximate second-order critical point (Wilson et al., 2017; Ruder, 2016; Keskar et al., 2017; Reddi et al., 2018a; Levy, 2016; Jin et al., 2017; Ge et al., 2015). Nonetheless, rigorous nonconvex analyses have been done recently for many of these methods (Reddi et al., 2018b; Ward et al., 2019; Zaheer et al., 2018b). Our work follows this line but uses a quotient-based diagonal scaling tied explicitly to curvature proxies gathered during the preceding epoch. Second-order, natural-gradient, and quasi-Newton methods. Quasi-Newton methods approximate inverse curvature from observed changes during optimisation. The canonical example is limited-memory BFGS (L-BFGS), which stores a short history of curvature pairs (si , yi ) to build a low-rank inverse–Hessian and applies it with the two-loop recursion without forming matrices (Liu & Nocedal, 1989; Schraudolph et al., 2007; Wang et al., 2017). In deep learning, high dimensionality and mini-batch noise motivate stochastic variants that add damping to control indefiniteness, partition parameters into blocks to reduce memory, and refresh curvature only periodically. These variants can also use Hessian–vector products to apply curvature implicitly, preserving tractability while retaining curvature-informed directions (Pearlmutter, 1994; Byrd et al., 2016; Goldfarb et al., 2020; Anil et al., 2020; Gupta et al., 2018; Yao et al., 2021). A complementary line of work replaces the Hessian with statistical surrogates. Natural gradient uses the Fisher information as a metric and preconditions gradients by an estimate of F −1 , which improves conditioning and provides parameterisation invariance (Amari, 1998). Hessian-free and generalised Gauss–Newton methods construct a positive semidefinite curvature matrix such as the GGN or Fisher, and compute search directions with conjugate gradient using Hessian–vector products (Martens, 2010; Schraudolph, 2002). Kronecker-factored approximations such as K-FAC approximate layer-wise Fisher blocks with Kronecker products of small factors, yielding a tractable
2
block-diagonal preconditioner that lowers memory and compute cost and scales to large models (Martens & Grosse, 2015; Grosse & Martens, 2016).
2
L OSS O PTIMIZATION IN N EURAL N ETWORKS
P ROBLEM S TATEMENT Consider the training task of a deep learning network as described in Eqn. (1). Let the training set be {(xi , yi )}Ii=1 . Consider a depth-L feedforward network with parameters θ = {Wℓ , bℓ }L ℓ=1 ,
(2)
where each layer ℓ has a weight matrix Wℓ and a bias vector bℓ . In the forward pass step, given an input x, the activations are defined recursively: a0 = x,
hℓ = Wℓ aℓ−1 + bℓ ,
aℓ = ϕℓ (hℓ ),
ℓ = 1, . . . , L.
(3)
Here hℓ are the pre-activations (linear combinations of inputs plus bias), and ϕℓ (·) is a chosen nonlinear activation function. For a per-example loss ℓ(z, y) evaluated at the output z = aL , backpropagation computes derivatives backward as follows: DaL ←
∂ ℓ(z, y) , ∂z z=aL
(4)
and for ℓ = L, . . . , 1: gℓ = Daℓ ⊙ ϕ′ℓ (hℓ ),
∇Wℓ = gℓ a⊤ ℓ−1 ,
∇bℓ = gℓ ,
Daℓ−1 = Wℓ⊤ gℓ .
(5)
F IRST- VS S ECOND -O RDER O PTIMIZATION M ETHODS ( WITH A DAM /YOGI ) First-order algorithms such as SGD, and the variants with EMA enhancements such as RMSProp, and Adam update parameters using stochastic gradients, θt+1 = θt − η∇L(θt ),
(6)
with adaptivity and momentum altering the effective step sizes and directions. These methods are memory efficient and map well to accelerators and mini-batch pipelines, which is why they dominate large-scale training. Their main limitation is sensitivity to ill-conditioning and plateaus in the loss landscape (Ruder, 2016; Yao et al., 2021). By contrast, classical second-order methods like Newton and Levenberg–Marquardt incorporate curvature via (approximations to) the Hessian and can converge rapidly near minima (Hagan & Menhaj, 1994). In deep learning, however, forming or inverting dense curvature is prohibitive, and the stochasticity of mini-batches undermines accurate curvature estimation, which diminishes their practical effectiveness at scale (Ampazis & Perantonis, 2002). Structured approximations (e.g., block diagonal and Kronecker factorizations (Martens & Grosse, 2015)) and stochastic quasi-Newton variants narrow the gap but still face stability and overhead trade-offs in realistic DNN training tasks. L-BFGS in Brief Limited-memory BFGS (L-BFGS) maintains a short history of curvature pairs (sℓ , yℓ ) with sℓ = θℓ+1 − θℓ and yℓ = ∇L(θℓ+1 ) − ∇L(θℓ ), defining an implicit inverse-Hessian Ht−1 . The two-loop recursion computes the search direction, pt = − Ht−1 ∇L(θt ),
θt+1 = θt + αt pt = θt − αt Ht−1 ∇L(θt ).
(7)
The two-loop recursion applies Ht−1 to a vector in O(r d) time using r stored pairs and d parameters (with r typically 5–20 in deep nets). The step length αt is then chosen separately, usually by a linesearch which requires K − 1 extra forward–backward passes. Adam/Yogi in Brief Adam and Yogi maintain exponential moving averages of the gradient and its squared magnitude, with gt = ∇L(θt ),, mt = β1 mt−1 + (1 − β1 )gt , Adam: vt = β2 vt−1 + (1 − β2 )gt2 ,
(8) Yogi: vt = vt−1 − sign(vt−1 − gt2 )(1 − β2 )gt2 . 3
After bias correction (m̂t , v̂t ), the search direction and update are pt = √
m̂t , v̂t + ε
θt+1 = θt − η pt .
(9)
Per-step memory and compute are O(d). The step length η is set externally (often with a schedule), rather than via a line search. AdamW decouples weight decay from the adaptive update; Yogi’s variance rule caps unwarranted growth of vt under noisy gradients. 2.1
T HE CT-AGD M ETHOD
The rationale of CT-AGD is to provide more accurate estimates of local curvatures to the optimizers. It can be interpreted as a local-curvature-aware booster of first-order optimizers. Within each minib using finite-difference quotients. At the end of batch, it estimates the diagonal of the Hessian, H, each epoch, it uses this information to perform a more informed update. Conventions. Unless stated otherwise, absolute values, inequalities, divisions, and the clamp Π[λmin ,λmax ] (·) act element-wise; ⊘ denotes the element-wise division and ⊙ denotes the Hadamard product. K denotes the number of epochs with k as the epoch index. T denotes the number of minibatches in each epoch, with t as the index. Within each mini-batch, the training samples are drawn randomly without replacement with the batch size of B. Within-Epoch First-Order Steps In CT-AGD , the optimization within each epoch is almost identical to the classic first-order methods. Therefore, different first-order methods (e.g., SGD and Adam) can be used as the backbone. To simplify annotation, we use vanilla SGD as the example. Starting from xk,0 , the inner iterations for t = 0, . . . , T − 1 are done as follows: θk,t+1 = θk,t − µk,t gk,t ,
µk,t =
η1 , γk,t
(10)
with a scalar, iteration-varying curvature-aware divisor t γk,t = γk − γk − 1 , t = 0, . . . , T. (11) T With the divisor at the endpoints: γk,0 = γk , γk,T = 1. (See S.2 for a plot of γk,t over an epoch.) γk comes from the curvature estimation of the previous epoch. However, with every step, it loses fidelity as the inner steps move further away from the point of the curvature estimation, hence throughout the epoch: µk,t starts low and increases linearly to η1 , γ k > 1 : (12) 0 < γk < 1 : µk,t starts high and decreases linearly to η1 , γk = 1 : µk,t ≡ η1 . Interpretation: γk > 1 indicates high curvature; 0 < γk < 1 indicates low curvature. Direct Accumulation of Diagonals of Hessian Define first differences for t = 1, . . . , T − 1, ∆θk,t := θk,t − θk,t−1 ,
∆gk,t := gk,t − gk,t−1 .
To ensure the stability, we define a validity mask and the per-coordinate quotients, ∆gk,t 1 if |∆θk,t | > ε mk,t := hk,t := (element-wise). 0 if |∆θk,t | ≤ ε ∆θk,t
(13)
(14)
We use the following projection operator (or clamp function) to limit the range of computed quotients: Π[a,b] (x) = arg min |y − x| = min max(x, a), b . (15) y∈[a,b]
The clamped diagonal entries of Hessian are computed as: ! PT −1 t=1 t · (mk,t ⊙ hk,t ) b Hk := Π[λmin , λmax ] ∈ Rd (element-wise division). PT −1 ( t=1 t · mk,t ) + ε 4
(16)
where 0 < λmin ≤ λmax < ∞ and the division is element-wise. The t-weights prioritize later inner steps whose finite-difference quotients are closer to the current state. At the same time, the averaging reduces mini-batch noise (that typically corrupts curvature information) to yield a lower-variance (approximately unbiased) diagonal curvature estimate. This way, the diagonal entries provide direct information about local curvature. In CT-AGD they are applied at the end of each epoch as a correction step b k = 1/Hk,1 , . . . , 1/Hk,d ∈ Rd . Pk = 1 ⊘ H (17) Note on Memory and Compute: The approximations in Eqn. (16) can be calculated with rolling accumulators for the (weighted) numerator and denominator, as well as the most recent (θk,t , gk,t ) to form (∆θk,t , ∆gk,t ). Their computation only requires O(d) memory per tensor and avoids history buffers. One Step Update each Epoch At the end of each epoch, we have the most accurate estimate of diagonal of Hessian, which provide us the direct information on local curvature. CT-AGD performs one update: θk+1,0 = θk,T −1 − η2 Pk g̃k , (18) where the gradients g̃k are computed as the rolling accumulation by reusing the same rolling accumulators (weighted sum of gk,t and sum of t), keeping memory overhead minimal: PT −1 t · gk,t g̃k = Pt=0 (19) T −1 t=0 t + ε Alternatively, we can use the gradients from the last mini-batch: g̃k = gk,T −1 ,
(20)
The first method reuses the same rolling accumulators (weighted sum of gk,t and sum of t), keeping memory overhead minimal; while using the gradients in the last mini-batch requires less computing but higher-variance. Scaling Coefficient for the Next Epoch We calculate the scaling factor for the next epoch as: b k ), γk := Qω (H
(21)
b k ; i.e. we Here Qω (·) is computed over the entries of the per-tensor diagonal Hessian estimate H compute the low-tail ω-quantile across its coordinates (elements). Using a low-tail quantile biases γk toward small curvature directions (small diagonal entries), accelerates the effective learning rate when curvature is low, while remaining robust to outliers. In practice, γk is computed separately for b k is bounded by λmim each tensor/layer, using that tensor’s diagonal Hessian estimate, and since H and λmax so is γk ; if the quantile is numerically undefined, we set γk = 1. Overall Algorithm The overall algorithm of CT-AGD is summarized below: Updating Scheme when ADAM is used When the first-order method is ADAM, we replace the first-order step (Eqn. 10) with the bias-corrected ADAM update (Eqn. 9) while leaving the curb k (and maskvature tracking and quantile scaling unchanged. The diagonal curvature estimate H ing/clamping) is computed exactly as in the SGD case using {gt }, and the per-tensor scaling coeffib k ) (fallback 1). The epoch-level diagonal estimate is still P = 1 ⊘ H bk , cient remains γk := Qω (H and the outer update uses the stored gradients (not ADAM moments) for g̃: PT −1 t gt if avg, else g̃ := gT −1 , θ ← θ − η2 P g̃. g̃ := PTt=0 −1 t=0 t + ε In practice, all quantiles and hessian diagonal estimates are computed per tensor/layer. Hyperparameters A complete list of hyper-parameters and their default values can be find in Supplemental Section S.6. 2.2
C ONVERGENCE OF CT-AGD
We cast the convergence proof of CT-AGD as outlined in Eqn. (22). Note that we use x as the variable name instead of θ to avoid confusion. 5
Algorithm 1 CT-AGD Input: θ0 ∈ Rd , epochs K, inner steps T , batches Bt , steps η1 , η2 , clamp [λmin , λmax ], percentile ω, ε > 0, mode ∈ {avg, last}, First-order (FO) backbone method. 1: γ ← 1 2: for k = 0..K − 1 do 3: Snum , Sden ← 0; θ ← θ0 4: for t = 0..T − 1 do 5: sample Bt ; gt ← ∇fB(θ) 6: µt ← η1 / γ − γ − 1 Tt θ ← FOstep (θ, gt , µt ) 7: if t ≥ 1 then t −g− 8: m ← 1{|θ−θ− | > ε} ; ht ← m ⊙ gθ−θ − 9: Snum += t ht ; Sden += t m 10: end if 11: θ− ← θ; g− ← gt 12: end for b ← Π[λ ,λ ] Snum ; P ← 1 ⊘ H b 13: H min
max
Sden +ε
b (fallback 1) 14: γ ← Qω (H) PT −1 PT −1 15: g̃ ← ( t=0 t + ε) if avg else gT −1 t=0 t gt 16: θ ← θ − η2 P g̃ 17: end for n
f (x) =
1X fi (x), n i=1
x ∈ Rd ,
(22)
where each fi is convex and has Li -Lipschitz gradient (i.e., is Li -smooth). Let Lmax := maxi Li . Assume f attains a minimum and let x⋆ ∈ arg min f with f ⋆ := f (x⋆ ). At iteration t, SGD samples it ∈ {0, . . . , T } uniformly at random and performs xt+1 = xt − η1 ∇fit (xt ),
(23)
where (η1 )t≥0 are step sizes. We will also use the (at-optimum) gradient noise level σf⋆ := Var(∇fi (x⋆ )) = E ∥∇fi (x⋆ )∥2 − ∥E[∇fi (x⋆ )]∥2 = E ∥∇fi (x⋆ )∥2 , P since ∇f (x⋆ ) = n1 i ∇fi (x⋆ ) = 0 by optimality (convex and smooth).
(24)
CT-AGD introduces effective step sizes µk,t = η1 /γk,t . At the end of each epoch (k = 1, . . . , K) b k from a clamped diagonal secant proxy H b k ∈ [λmin , λmax ]d we form a diagonal Pk = 1 ⊘ H (element-wise), and take one stochastic step with a fresh sample: xk+1,0 = xk,T − η2 Pk g̃k , 2.3
g̃k := ∇fi (xk,T ).
(25)
S TORAGE AND C OMPUTATIONAL C OMPLEXITY
We summarize the storage and dominant per-iteration computational cost below. Note d represents the total number of trainable parameters. We use s = ∆θ and y = ∆g uniformly: s is the parameter change and y the corresponding gradient change. For L-BFGS, let r be the history size (number of stored (si , yi ) pairs, typically r ∈ [5, 20]).
3
A L IGHTWEIGHT V ISUALIZATION T ESTBED FOR O PTIMIZERS
We use a simple and self-contained testbed to illustrate the effectiveness of the CT-AGD. The testbed is a quadratic equation, added by a number of Gaussian kernels. To mimic the stochasticity and non-stationarity, at each step, additional random Gaussian noises are added to the quadratic equation itself, as well as the magnitude, mean, and standard deviation of the Gaussian kernel. The testbed mimics three key components of NN training: (i) dynamics of stochastic mini-batch, (ii) 6
Table 1: Per-step total complexity (including f–b passes). d = # parameters; r = L-BFGS history size; Kt = # closure (line-search) evaluations at step t. Algorithm
Total storage
Elem. ops / step
f–b passes / step
O(d) O(2 d) O(3 d) O(5 d) O(r d)
O(d) O(2 d) O(3 d) O(5 d) O(r d)
1 1 1 1 Kt
SGD SGD + momentum Adam CT-AGD† L-BFGS‡
Accounting / notes Parameters only; no optimizer state (≈ d). Parameters + one moment buffer (≈ 2d). Parameters + two moment buffers m, v (≈ 3d). Parameters + four d-vectors (prev. θ, prev. g, rolling means h, ḡ) (≈ 5d). Parameters + history of r pairs (si , yi ); two-loop recursion ≈ (2r+1)d .
†
P Extra per-epoch work: one low-tail quantile per tensor of size dℓ ; with linear-time selection this is O ℓ dℓ = O(d); with sorting it is P O ℓ dℓ log dℓ ≪ O(d log d) since no global sort over d is performed (both are outside per-step costs). ‡ With a (possibly inexact) line search evaluating Kt closures at step t, total f–b passes per step are Kt ; with a fixed step or no line search, Kt = 1.
non-stationarity across steps, and (iii) the generalization gap between train and test. The testbed, which will be publicly available after the paper is published, can be used to test various gradientbased optimizers. Its details are in Supplemental Section S.1.
Figure 1: LEFT: Illustration of convergence of CT-AGD, SGD, Adam, Newton and L-BFGS where each step is shown. RIGHT: test accuracy versus iterations. The advange of CT-AGD is clear.
The trajectories in Fig. 1 illustrate the convergence of all methods in one instance. As shown, CTAGD, SGD, Adam, and L-BFGS descend into the common basin where the minimum is located. The default CT-AGD (with SGD as the backbone, first-order method) requires the least number of steps to achieve so. CT-AGD with ADAM as the backbone is also faster than vanilla ADAM. The pure second-order method, Newton, failed to converge in this case due to its poor tolerance to noise. With Random Components Optimizer CT-AGD CT-AGD (Adam) SGD Adam L-BFGS
Stationary
Final value
# Steps
Gen. gap
Final value
# Steps
Time
−4.10 ± 1.29 −4.61 ± 1.13 −3.93 ± 1.10 −4.31 ± 1.30 −3.87 ± 1.41
117.47 ± 19.70 137.47 ± 27.96 138.73 ± 24.54 156.53 ± 24.35 278.93 ± 189.92
2.31 ± 0.91 1.66 ± 0.90 2.81 ± 0.55 2.08 ± 0.76 2.15 ± 0.97
−6.33 ± 1.61 −5.75 ± 2.15 −6.52 ± 1.56 −5.49 ± 2.33 −5.19 ± 2.48
144.93 ± 25.16 128.07 ± 49.40 150.73 ± 15.43 152.07 ± 33.91 51.07 ± 0.13
0.49 ± 0.08 0.43 ± 0.16 0.52 ± 0.06 0.54 ± 0.12 0.33 ± 0.14
Table 2: Average of 15 testbed runs with different parameters for five method listed. Note that L-BFGS failed to converge in 3 runs, hence the average of 12 is listed. On the right, each run is stationary because no random Gaussian noises are added.
More comprehensive results are shown in Tab. 2. We repeated 15 testbed runs, each with a different set of parameters/initial points, and recorded the optimization results as well as the number of steps required to converge. In addition, we evaluate the generalization gap, which is the difference between average of test loss and average of training loss. Observe that the first-order methods tend to achieve better answers (more negative) than L-BFGS, and in fewer steps. Not surprisingly, L-BFGS requires substantially more steps and appears less stable due to its poor tolerance to noise (failed to converge in 3 runs). As a control, the results with no Gaussian random components (hence each run becomes stationary) are listed on the right. As expected, L-BFGS takes advantage of the Hessian information and converges much quicker.
7
However, its final value remains less accurate than the first-order methods. CT-AGD with different backbones converges in the fewest number of steps.
4
E XPERIMENTAL R ESULTS
We compare CT-AGD with SGD and Adam on three datasets: CIFAR-10, CIFAR-100 and TinyImageNet. For each case, we use three architectures: ResNet (He et al., 2016) and Wide ResNet (Zagoruyko & Komodakis, 2016) on all datasets. Additionally, a transformer architecture, DeiT (Touvron et al., 2021), is used for the Tiny-ImageNet dataset. Due to memory and computational constraints, we only run L-BFGS on the CIFAR-10 dataset using ResNet. Each run is repeated at least five times. For each experiment, we report (i) the best test accuracy and (ii) the number of epochs to convergence, which is defined as the number of epochs to achieve within 5% of the final accuracy of that particular run. All methods share identical data pipelines and data augmentation methods. All experiments are conducted with identical hardware and software configurations, which are outlined in Supplemental Section S.5. The hyperparameters used are listed in Supplemental Section S.6. Finally, to demonstrate the method’s effectiveness beyond computer vision, we provide additional evaluations on GraphSAGE in Supplemental Section S.4. The results are summarized in Tab. 3. The accuracy versus epoch of three model-dataset pairs is also shown in Fig. 2. Our general observation is that CT-AGD achieves the same level of accuracy, but requires drastically fewer number of epochs. A few outliers include TinyImageNet with ResNet-20. It appears that Adam is slightly faster, however, the final testing accuracy is inferior (44.28% versus 46.24% of CT-AGD). To provide a more reliable comparison, we present a longitudinal comparison in Tab. 4. For each model-dataset pair, we set the cutoff test accuracy as 5% of the best accuracy among all optimization methods. The table reports the number of epochs for each optimization method to reach a given threshold. Note that some entries in Tab. 4 are different from the corresponding values in Tab. 3 because of different accuracy thresholds. CIFAR-10 Model
Optimizer
ResNet-20 ResNet-20 ResNet-20 ResNet-20 ResNet-20
CIFAR-100
Tiny-ImageNet
Acc (%)
# Epochs
Acc (%)
# Epochs
Acc (%)
# Epochs
CT-AGD SGD Adam CT-AGD (Adam) L - BFGS
90.05 ± 0.36 90.35 ± 0.14 89.20 ± 0.38 88.82 ± 0.09 82.79 ± 6.42
28.20 ± 2.22 44.00 ± 3.29 39.20 ± 3.09 31.40 ± 2.08 90.60 ± 29.50
64.70 ± 0.32 64.10 ± 0.53 61.86 ± 0.55 61.57 ± 0.39 -
48.00 ± 2.91 88.60 ± 7.43 75.20 ± 2.69 72.00 ± 6.74 -
46.24 ± 0.52 46.88 ± 0.49 44.28 ± 0.60 -
108.50 ± 7.50 120.00 ± 8.91 105.60 ± 7.78 -
WRN-28-4 WRN-28-4 WRN-28-4 WRN-28-4
CT-AGD SGD Adam CT-AGD (Adam)
93.68 ± 0.15 93.69 ± 0.19 93.35 ± 0.09 92.36 ± 0.23
23.00 ± 0.88 33.80 ± 4.25 40.00 ± 7.02 23.00 ± 1.24
73.84 ± 0.42 74.12 ± 0.44 74.05 ± 0.20 72.09 ± 0.24
37.80 ± 3.66 67.80 ± 1.62 100.40 ± 2.26 45.20 ± 5.51
58.69 ± 0.48 58.69 ± 0.50 57.11 ± 0.29 -
63.25 ± 5.42 96.40 ± 11.77 80.40 ± 5.99 -
DeiT-12 DeiT-12 DeiT-12
CT-AGD SGD Adam
-
-
-
-
31.87 ± 0.32 31.31 ± 0.35 32.61 ± 0.31
37.00 ± 2.32 47.00 ± 8.14 115.40 ± 14.76
Table 3: Test accuracy (%) and number of epochs to convergence on three datasets with three model architectures. Best results for a model-data combination are in bold. Fig. 2 shows the test accuracy versus epochs of shaded cells.
(a) CIFAR10 — ResNet-20
(b) CIFAR100 — WRN-28-4
(c) Tiny-ImageNet — DeiT-12
Figure 2: Test accuracy versus epochs of selected model-dataset pairs. See Tab. 3 for more details.
8
Model
Dataset
Acc. (%)
CT-AGD
SGD
Adam
CT-AGD (Adam)
Imp. 1
Imp. 2
ResNet-20 ResNet-20 ResNet-20
CIFAR-10 CIFAR-100 Tiny-ImageNet
85.7 61.2 44.3
24.0 ± 2.9 42.2 ± 1.4 116.5 ± 5.5
32.4 ± 3.4 85.0 ± 5.0 113.0 ± 6.4
39.8 ± 3.7 117.8 ± 31.2 145.2 ± 17.7
34.2 ± 3.4 121.4 ± 16.8 –
25.9% 50.4% -3.09%
14.1% -3.06% N/A
WRN-28-4 WRN-28-4 WRN-28-4
CIFAR-10 CIFAR-100 Tiny-ImageNet
88.9 70.2 55.5
18.8 ± 1.6 31.2 ± 6.0 54.5 ± 9.6
22.8 ± 5.2 62.0 ± 3.6 80.4 ± 13.8
28.8 ± 5.2 83.8 ± 9.8 87.8 ± 9.7
23.6 ± 1.4 57.8 ± 3.2 –
17.5% 49.7% 32.2%
18.1% 31.0% N/A
DeiT-12
Tiny-ImageNet
30.4
35.6 ± 3.7
91.2 ± 49.6
96.2 ± 8.4
–
Average
61.0%
N/A
33.4%
15.0%
Table 4: Number of epochs for a particular optimization method to reach a common cutoff threshold, which is shown in the third column. The best are shown in bold. The first improvement column represents the number of epochs improvement from SGD to CT-AGD with SGD as the backbone. The second improvement column compares CT-AGD with Adam as the backbone with Adam.
Overall we observe 33% cases of fewer number of epochs to achieve the same accuracy. Note that we used the same hyperparameters for all experiments. In two cases when ResNet-20 is used, CTAGD is slightly slower than the baseline methods. However the difference is within 5%. Fine-tuning of hyperparameters can be a solution to move forward. Also note the overfitting in DeiT, which is primarily driven by architectural/dataset. The issue is orthogonal to the optimizer, and should be addressed by other techniques such as data augmentation and regularization. Notice that CT-AGD delivered significant reduction in terms of number of epochs. As shown in Section. 2.3, CT-AGD requires slightly more computation per epoch. Our experiments show that per epoch runtime of CT-AGD is about 9% over its backbone method. However the overhead can be further reduced after code optimization. Overall CT-AGD still provides significant net saving while achieving the same accuracy. 4.1
A BLATION S TUDIES
We conduct ablation studies on CIFAR-10 (ResNet-20) using the default setup (same as in Tab. 3). We focus on the main heuristic components of the algorithm: (i) clamping of the diagonal curvature proxy, (ii) robustness to noisy curvature quotients, (iii) curvature averaging and decay, and (iv) the low-tail quantile ω. Effect of clamping interval. Tab. 5 reports a sweep of (λmin , λmax ) spanning three orders of magnitude around the default (10−2 , 102 ). Effect of computational noise on the curvature estimate. Tab. 5 also reports experiments where we inject unbiased Gaussian noise at every mini-batch step. Here what we do is replace Eqn. 14 with ∆gk,t hk,t := + N (0, σ 2 ) (26) ∆θk,t where σ 2 is varied between experiments. Setting
λmin
λmax
Noise σ 2
Top-1 (%)
Epochs to conv.
Interval sweep Interval sweep Interval sweep
10−1 10−2 10−3
101 102 103
0 0 0
90.13 ± 0.15 90.01 ± 0.22 90.23 ± 0.22
24.60 ± 2.86 26.20 ± 4.16 25.80 ± 1.25
Noise sweep Noise sweep Noise sweep
– – –
– – –
0 0.01 0.1
90.09 ± 0.16 90.07 ± 0.23 90.12 ± 0.14
23.67 ± 1.49 25.80 ± 2.39 24.80 ± 1.04
SGD baseline
–
–
0
90.35 ± 0.14
44.00 ± 3.29
Table 5: Ablations on the clamping interval (λmin , λmax ) and on injected curvature noise for CT-AGD on CIFAR-10 with ResNet-20. The SGD row is reported for reference.
The results show that both final accuracy and epochs to convergence remain essentially unchanged across a broad range of (λmin , λmax ), and are also stable under injected noise with variance up to 0.1 at the level of individual curvature quotients, which suggests that CT-AGD is robust.
9
Annealing schedule, curvature averaging, and low-tail quantile. We next ablate the annealing schedule used for propagating curvature information across iterations, the weighting scheme used to average curvature estimates within each epoch, and the low-tail quantile ω that defines the effective scaling. The first block of Tab. 6 compares: (i) removing annealing entirely by keeping µk,t = η1 /γk,t constant through each epoch, (ii) an exponential annealing of the curvature cue with factor α = 12 , (iii) the baseline linear annealing with weighted curvature estimation, and (iv) replacing the weighted curvature average by a non-weighted average. Setting
Top-1 (%)
Epochs to conv.
No annealing Exponential annealing (α = 0.5) Baseline Non-weighted curvature
50.96 ± 3.82 90.32 ± 0.35 90.01 ± 0.22 90.05 ± 0.29
2.20 ± 0.56 27.40 ± 5.31 26.20 ± 4.16 26.80 ± 1.62
ω = 0.1 ω = 0.2 ω = 0.5
90.23 ± 0.22 90.16 ± 0.26 90.18 ± 0.11
25.80 ± 1.25 23.80 ± 3.21 35.80 ± 3.87
SGD baseline
90.35 ± 0.14
44.00 ± 3.29
Table 6: Ablations of annealing schedule, curvature averaging, and ω on CIFAR-10 with ResNet-20. Removing annealing leads to severe degradation in accuracy and much higher variance, showing that some form of annealing of the inter-epoch curvature cue is essential. This is consistent with our intuition that outdated curvature cues can hinder optimization steps. Both exponential and linear annealing recover high accuracy and similar convergence speed, while the non-weighted curvature average performs almost identically to the weighted version. This indicates that CT-AGD is sensitive to the presence of annealing, but not to a precise functional form or a carefully engineered scheme. The second block of Tab. 6 sweeps the low-tail quantile ω used to define γk . Across a wide range of values (0.1 ≤ ω ≤ 0.5), the final accuracy remains essentially unchanged, whereas the number of epochs to convergence mainly reflects how aggressively the method exploits the curvature cue. Smaller values of ω favor more aggressive updates and faster convergence.
5
D ISCUSSION
The key insight of CT-AGD is that with careful range limiting and other heuristics, direct calculation of the diagonals of the Hessian can benefit large-scale non-convex optimization problems, which frequently occur in deep neural network training. When compared to adaptive gradient methods (e.g., ADAM), which rely on the moments of the gradients to capture the local curvature, the direct approach deployed in CT-AGD is more responsive to the change of the local curvature, thereby enabling convergence in a smaller number of epochs. Moreover, CT-AGD can be interpreted as a coordinate-wise curvature informed learning rate modulator approach, hence it can be deployed with other first-order optimization methods as its backbone. Our extensive experimental results show that on average CT-AGD achieves in average 33% fewer epochs for the same training task, with up to 61% savings in the best case. In certain extreme cases (especially with small models on challenging datasets), CT-AGD is slightly slower than the baseline method. ResNet-20 on Tiny-ImageNet is one such example. Nevertheless, CT-AGD still achieves comparable accuracy in this setting, in just 3% more epochs. This little overhead may be reduced with modest hyper-parameter tuning; in practice, adjusting λmin , λmax , and the quantile threshold ω can be explored. That said, our ablation studies confirm the method’s robustness to these hyperparameter choices, minimizing the need for extensive tuning.
10
R EFERENCES Shun-ichi Amari. Natural gradient works efficiently in learning. Neural Computation, 10:251–276, 1998. Nicholas Ampazis and Stavros J. Perantonis. Two highly efficient second-order algorithms for training feedforward networks. IEEE Transactions on Neural Networks, 13(5):1064–1074, 2002. Rohan Anil, Vineet Gupta, Tomer Koren, Kevin Regan, and Yoram Singer. Scalable second order optimization for deep learning. arXiv preprint arXiv:2002.09018, 2020. Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Peter Tang. A progressive batching l-BFGS method for machine learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 620–629. PMLR, 10–15 Jul 2018. Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3–4):231–357, 2015. Richard H. Byrd, Sherry Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi-newton method for large-scale optimization. SIAM Journal on Optimization, 26(3):1705–1727, 2016. Timothy Dozat. Incorporating nesterov momentum into adam. In International Conference on Learning Representations, Workshop Track, 2016. John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121–2159, 2011. Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points — online stochastic gradient for tensor decomposition. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 797–842, Paris, France, 03–06 Jul 2015. PMLR. Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-newton methods for training deep neural networks. In Advances in Neural Information Processing Systems, 2020. Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training ImageNet in 1 hour. arXiv preprint arXiv:1706.02677, 2017. Roger Grosse and James Martens. A kronecker-factored approximate fisher matrix for convolution layers. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 573–582, 2016. Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1842–1850, 2018. Martin T. Hagan and Mohammad B. Menhaj. Training feedforward networks with the marquardt algorithm. IEEE Transactions on Neural Networks, 5(6):989–993, 1994. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770–778. IEEE, 2016. John L. Hennessy and David A. Patterson. A new golden age for computer architecture. Communications of the ACM, 62(2):48–60, 2019.
11
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How to escape saddle points efficiently. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1724–1732. PMLR, 06–11 Aug 2017. Norman P. Jouppi, Cliff Young, Nishant Patil, David A. Patterson, et al. In-datacenter performance analysis of a tensor processing unit. In Proceedings of the 44th Annual International Symposium on Computer Architecture (ISCA), pp. 1–12, Toronto, ON, Canada, 2017. Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training and sharp minima: Understanding generalization in deep learning. In International Conference on Learning Representations, 2017. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. Kfir Y. Levy. The power of normalization: Faster evasion of saddle points. arXiv:1611.04831, 2016.
arXiv preprint
Dong C. Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45:503–528, 1989. Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. James Martens. Deep learning via hessian-free optimization. In International Conference on Machine Learning, 2010. James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature. In International Conference on Machine Learning, 2015. Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer, 2004. David A. Patterson, Joseph E. Gonzalez, Urs Hölzle, Quoc V. Le, Chen Liang, Lluis-Miquel Munguia, Daniel Rothchild, David R. So, Maud Texier, and Jeff Dean. The carbon footprint of machine learning training will plateau, then shrink. Computer, 55(7):18–28, 2022. Barak A. Pearlmutter. Fast exact multiplication by the hessian. Neural Computation, 6:147–160, 1994. Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964. Sashank Reddi, Manzil Zaheer, Suvrit Sra, Barnabas Poczos, Francis Bach, Ruslan Salakhutdinov, and Alex Smola. A generic approach for escaping saddle points. In Amos Storkey and Fernando Perez-Cruz (eds.), Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 1233–1242. PMLR, 09–11 Apr 2018a. Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018b. Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv:1609.04747, 2016.
arXiv preprint
Nicol N. Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural Computation, 14(7):1723–1738, 2002. Nicol N. Schraudolph, Jin Yu, and Simon Günter. A stochastic quasi-newton method for online convex optimization. In Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pp. 436–443, 2007. Roy Schwartz, Jesse Dodge, Noah A. Smith, and Oren Etzioni. Green ai. Communications of the ACM, 63(12):54–63, 2020. 12
Samuel L. Smith, Pieter-Jan Kindermans, Chris Ying, and Quoc V. Le. Don’t decay the learning rate, increase the batch size. In International Conference on Learning Representations, 2018. Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in NLP. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 3645–3650, Florence, Italy, 2019. Vivienne Sze, Yu-Hsin Chen, Tien-Ju Yang, and Joel S. Emer. Efficient Processing of Deep Neural Networks. Morgan & Claypool, 2020. Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5—rmsprop: Divide the gradient by a running average of its recent magnitude. Neural Networks for Machine Learning (Coursera) Lecture Notes, 2012. Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 10347–10357. PMLR, 2021. Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-newton methods for nonconvex stochastic optimization. SIAM Journal on Optimization, 27(2):927–956, 2017. Rachel Ward, Xiaoxia Wu, and Léon Bottou. AdaGrad stepsizes: Sharp convergence over nonconvex landscapes. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6677–6686. PMLR, 2019. Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, 2017. Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael W. Mahoney. Adahessian: An adaptive second order optimizer for machine learning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12):10665–10673, 2021. Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In Proceedings of the British Machine Vision Conference, pp. 87.1–87.12. BMVA Press, 2016. Manzil Zaheer, Sashank J. Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in Neural Information Processing Systems, volume 31, pp. 9793–9803. Curran Associates, Inc., 2018a. Manzil Zaheer, Sashank J. Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in Neural Information Processing Systems, volume 31, pp. 9793–9803. Curran Associates, Inc., 2018b. Matthew D. Zeiler. Adadelta: An adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012.
13
S
S UPPLEMENTAL M ATERIAL
S.1
DYNAMIC “G ENERALIZATION ” L ANDSCAPE
Snapshots and drift. The landscape is defined by a sequence of train snapshots and a shorter sequence of test snapshots, built sequentially to emulate nonstationarity. Each snapshot is a sum of a convex quadratic baseline and a set of drifting Gaussian “lumps” with random signs (to create both attractive and repulsive features). Let θ ∈ R2 , let c0 ∈ R2 be the target center, q > 0 the quadratic factor, and for j = 1, . . . , M let (cj , aj , sj , σj ) denote center, amplitude, scale, and sign (σj ∈ {−1, +1}). The value of a snapshot S at θ is V (θ; S) = q ∥θ − c0 ∥22 +
M X
∥θ−c ∥2 σj aj exp − 2s2j 2 .
(27)
j
j=1
Snapshots evolve by small stochastic drifts: cj
(t+1)
= cj + εc,j ,
(t+1)
= aj [1 + εa,j ],
(t+1)
= sj [1 + εs,j ],
aj sj
(t)
(t)
(t)
εc,j ∼ N (0, σc2 I2 ),
(t)
(t)
εa,j ∼ N (0, σa2 ),
(t)
(t)
(t)
εs,j ∼ N (0, σs2 ).
(t)
Calling the landscape once advances the train snapshot index (cyclically), so an optimiser observes a changing objective during a trajectory, akin to iterating over mini-batches and data augmentations. test train be the built sequences. For any point and {Sutest }Tu=1 Train, test, and the gap. Let {Sttrain }Tt=1 θ, we define
Lavg (θ) :=
1
TX train
Ttrain t=1
V
θ; Sttrain
Eavg (θ) :=
1
T test X
Ttest u=1
V θ; Sutest
(28)
Gap(θ) := Eavg (θ) − Lavg (θ) which play the role of train loss, test loss, and generalisation gap. In visualisations, we may draw either the instantaneous train surface V (·; Sttrain ) or the averaged test surface Eavg (·) as the background to contrast optimisation progress and generalisation. To visualise the animation of how the landscape works and how different optimisers behave (results from Figure 1), follow the link: https://osf.io/63zem?view only=b0f43a3664f44dba98cad7a1c4c33cc2 S.2
E VOLUTION OF THE CURVATURE - AWARE DIVISOR
Figure 3: Evolution of the curvature-aware divisor γk,t = γk − (γk − 1) Tt over one epoch (of 100 internal steps) for three initial values: γk > 1, 0 < γk < 1, and γk = 1. The schedule is linear from γk at t = 0 to 1 at t = T .
14
CIFAR-10 Model
Optimizer
ResNet-20 ResNet-20 ResNet-20 ResNet-20 ResNet-20
CIFAR-100
Tiny-ImageNet
Acc (%)
Time (s)
Acc (%)
Time (s)
Acc (%)
Time (s)
CT-AGD SGD Adam CT-AGD (Adam) L - BFGS
90.05 ± 0.36 90.35 ± 0.14 89.20 ± 0.38 88.82 ± 0.09 82.79 ± 6.42
255.13 ± 30.17 316.81 ± 28.85 388.12 ± 37.54 374.33 ± 36.40 16295.83 ± 3140.84
64.70 ± 0.32 64.10 ± 0.53 61.86 ± 0.55 61.57 ± 0.39 -
463.03 ± 15.86 857.62 ± 54.83 1179.86 ± 306.30 1335.25 ± 190.49 -
46.24 ± 0.52 46.88 ± 0.49 44.28 ± 0.60 -
4343.79 ± 207.09 3660.27 ± 202.14 4771.47 ± 660.88 -
Wide ResNet Wide ResNet Wide ResNet Wide ResNet
CT-AGD SGD Adam CT-AGD (Adam)
93.68 ± 0.15 93.69 ± 0.19 93.35 ± 0.09 92.36 ± 0.23
388.66 ± 33.75 416.61 ± 95.57 525.29 ± 93.24 524.07 ± 31.57
73.84 ± 0.42 74.12 ± 0.44 74.05 ± 0.20 72.09 ± 0.24
666.94 ± 132.49 1140.35 ± 66.81 1542.87 ± 185.55 1283.09 ± 72.73
58.69 ± 0.48 58.69 ± 0.50 57.11 ± 0.29 -
9382.40 ± 2322.14 11015.84 ± 1881.44 12000.42 ± 1317.28 -
DeiT DeiT DeiT
CT-AGD SGD Adam
-
-
-
-
31.87 ± 0.32 31.31 ± 0.35 32.61 ± 0.31
3785.37 ± 415.78 8598.44 ± 4677.69 9132.21 ± 799.30
Table 7: Test accuracy (%) and Time to convergence. Accuracies are the same as in Tab. 3, but convergence is defined as the first epoch at which a run reaches 5% of the best max test accuracy among optimizers for the same model–dataset pair. Best results for a model-data combination are in bold. Fig. 4 shows the test accuracy versus epochs of shaded cells.
(a) CIFAR-100 — ResNet
(b) Tiny-ImageNet — ResNet
(c) CIFAR-10 — WRN
(d) Tiny-ImageNet — WRN
Figure 4: Additional accuracy trajectories. Complements Fig. 2 by showing the non-diagonal tasks.
15
S.3
A DITIONAL RESULTS
S.4
A DDITIONAL E XPERIMENTS
We expanded our evaluation by testing CT-AGD on large-scale node classification on the Reddit benchmark. The Reddit graph contains ∼ 232k nodes and ∼ 11.6M edges with 602-dimensional input features and 41 target classes. We train a 2-layer GraphSAGE over 60 epochs. All optimizers share the same architecture and training protocol. Tab. 8 reports the final training accuracy and the number of epochs to convergence, averaged over 5 runs. Method
Train acc. (%)
Epochs to conv.
Adam CT-AGD (Adam) CT-AGD (SGD) SGD
97.60 ± 0.00 97.60 ± 0.00 93.30 ± 0.00 92.80 ± 0.00
23.4 ± 0.5 23.2 ± 0.4 18.8 ± 0.8 27.8 ± 0.4
Table 8: Reddit node classification with a 2-layer GraphSAGE encoder. CT-AGD (Adam) matches the strong training accuracy of Adam with essentially identical convergence, while CT-AGD (SGD) improves over plain SGD in both training accuracy and the number of epochs required to converge.
S.5
H ARDWARE AND S OFTWARE
Hardware and software configurations for the experimental results. Hardware CPU vCPU topology Memory GPU Driver
Intel Xeon Silver 4214R @ 2.40 GHz 8 vCPUs; 2 threads/core; NUMA nodes: 2 64 GiB RAM (swap: 0 B); HugePages: 0 NVIDIA Tesla V100S-PCIe-32GB (1×; 32 GB HBM2) NVIDIA 555.42.02
Software OS / Kernel Python PyTorch Torchvision CUDA
S.6
Ubuntu 20.04.4 LTS (Focal), Linux 5.4.0-120-generic 3.10.18 2.7.1 +cu126 0.22.1 12.6
H YPER - PARAMETERS
CT-AGD hyper-parameters and values used • Secondary learning rate: η2 = 0.5. • Clamp bounds: λmin = 10−2 , λmax = 102 . • Percentile statistic: ω = 0.1. • Numerical stabilizer: ε = 10−3 . • Gradient update mode: avg. CT-AGD inherits the hyperparameters of its backbone optimizer: CT-AGD (Adam) uses Adam’s defaults; CT-AGD uses SGD’s defaults. This means, they use the same values as the standalone optimizer.
16
Method Adam and CT-AGD (Adam) SGD and CT-AGD L-BFGS
Primary learning rate η1 and common defaults η1 = 10−3 ; (β1 , β2 ) = (0.9, 0.999) η1 = 10−2 ; momentum µ = 0.85 (no Nesterov) initial step size η1 = 1.0; history size r = 10; max inner iterations K = 20
All methods use weight decay λ = 5 × 10−4 .
17