Gradient descent with generalized Newton’s method
Authors: Zhiqi Bu
Shiyun Xu
Venue: ICLR 2025 Poster (2025)
Keywords: Optimization
Hessian matrix
Learning rate scheduler
Primary area: optimization
TL;DR: We verify the quadratic shape of loss function and propose a Hessian-informed learning rate schedule that generalizes the Newton's method.

Abstract: We propose the generalized Newton's method (GeN) --- a Hessian-informed approach that applies to any optimizer such as SGD and Adam, and covers the Newton-Raphson method as a sub-case. Our method automatically and dynamically selects the learning rate that accelerates the convergence, without the intensive tuning of the learning rate scheduler. In practice, our method is easily implementable, since it only requires additional forward passes with almost zero computational overhead (in terms of training time and memory cost), if the overhead is amortized over many iterations. We present extensive experiments on language and vision tasks (e.g. GPT and ResNet) to showcase that GeN optimizers match the state-of-the-art performance, which was achieved with carefully tuned learning rate schedulers.

Published as a conference paper at ICLR 2025
GRADIENT DESCENT WITH GENERALIZED NEWTON'S METHOD
Zhiqi Bu
Shiyun Xu
woodyx21 86 wma.l..mmmmmm...mmmm..m......... com
University of Pennsylvania shi yunxuêsas upenn, .ddu
ABSTRACT
We propose the generalized Newton's 's method (GeN) - Hessian-informed ap- proach that applies any optimizer such SGD and Adam, and covers the Newton- Raphson method as sub-case. Our method automatically and dynamically selects the learning rate that accelerates the convergence, without the intensive tuning of the learning rate scheduler. In practice, our method is easily implementable, since it only requires additional forward passes with almost zero computational overhead (in terms of training time and memory cost), if the overhead is amortized over many iterations. We present extensive experiments on language and vision tasks (e.g. GPT and ResNet) to showcase that GeN optimizers match the state-of-the-ar performance, which was achieved with carefully tuned learning rate schedulers.
INTRODUCTION
Deep learning models are trained via the gradient descent wW+1 = wi -,PP gt. where w, E Rd the model parameters. The model update w, W++1 consists of learning rate scheduler π) E RR that is controlled by several hyperparameters, a pre-condiei P, E Rdxd that can depend on the Hessian Fisher information, and the first-order gradient g: Rd of the loss function I(wx)..
Table 1: Summary optimizers with w = wt T/e P..PPta "g Fisher information, d is the number of model parameters. We highlight that GeN can take advantage of any pre-conditioner P.-
Pr. where H is the Hessian, F
Method
P.
dim (.))
Newton-
=1
H
d²
BFGS (Broyden 1970
need tune
R H
d2
LBFGS
Byrd ct al. 1995
GeN (this work)
G g/g Hg
Any
1 or
D D-adaptation (Defazio Mishchenko 2023
Prodigy (Mishchenko & Delazio
1100 w. mo.ll/ma
///xxx G
or v diag
1 1
DoG (Iver et al. (023
DoWG (Khaled ct at. 2023
AdaHessian Yao
2021
need tune
diag(H)
d
Sophia Liu et al.
Shampoo (uupta et al.
2018
K-FAC iMartens & Grosse
2015 5
need tune
d
Natural Gradient (Amari
1998
Adam (Kingma & Ba 2014
AdamW (Loshchilov & Hutter
2017
AdaGrad (Duchi al. 201
need tune
diag(F)
d
AdaDelta (Zeller 2012
RMMProp (Hinton cf al. 2012
SGD (Robbins & Monro, 1951
Heavyball (Polyak 1964
need tune
NAG (Nesterov
1983
Equal contribution. Code availahle

---

Published as a conference paper at ICLR 2025
For large-scale optimization problems with millions to billions of parameters, the training can be significantly costly. For example, large language models are trained with trillions of tokens, on
thousands of GPUs, costing millions of dollars (Sharir et al.] 2020
Biderman et al. [002). and at
high carbon footprint (Patterson et al. 2021: Luccioni et al. 2023 Dodge et al. 2022 Touvron
et al., 2023a): GPT-3 (175B, [Brown et al. 2020)). LLAMA (7~70B, [Touvron al. (2023a bj),
Chinchilla (70B, Hoffmann et al. (2022)) PaLM (540B, Chowdhery et al. (2023). ). and Falcon
(7~180B,, Almazrouei et al. (2023) models are trained on 2 IT tokens; state-of-the-art models require extremely long training time, measured in thousands of PetaFLOPS-dee days (Almazrouei
al., 2023 Figure 2) or millions of GPU hours (AI@ Meta (024). It is therefore computationally prohibitive to instantiate a dense P, or tune the hyperparameters of 7/:- However, the second-order pre-conditioner and the learning rate scheduler are critical to the fast convergence.
On one hand, Hessian-informeed pre-conditioner is necessary in large-scale model training, as SGD (using no pre-conditioning) empirically does not compete with adaptive optimizers like Adam. However, implementing or approximating the full Hessian matrix induces Odd²) or even (dd)) complexity, which infeasible for large models on current generation of computing devices. In order to compute the pre-conditioner P, efficiently, long list of adaptive optimizers (see Table [ with diagonal P2) have proposed to only leverage the diagonal of P. and/or to replace the Hessian with Fisher information, although some information in the full Hessian may be lost.
On the other hand, manually setting a learning rate scheduler requires a critical balance between the utility- more hyperparameters the better, and the tuning effort fewer hyperparameters the easier. The simplest approach is to set a constant learning rate T)t = r (only one hyperparameter) through grid search. However, the mini-batch gradient descent with a constant 7/: may not allow the model to converge even under the convex setting, which is easier to optimize than the non-convex setting in deep learning. Additionally, as we see in Figure [ small 17 converges slow but to better solution, and vice versa for large 17, which depicts the importance of setting the proper 7/; at each iteration. That is, tuning the learning rate scheduler is essentially selecting T (number of iterations) learning rates to maximize the convergence speed. To accommodate this challenge, a line of schedulers (including the linear decay, warm-up and cosine scheduler) has been proposed to control the learning rate during the training, with a number of hyperparameters. For instance, LLAMA 65B (Touvron et al. (223aa) uses a scheduler with 3 hyperparameters: warm-up s0eps=2000, maximum 7/t = 1.5c and final N 1.5c-5 Unfortunately, most schedulers are heuristic and have their limits: they do not guarantee fast convergence and become increasingly difficult to tune as the model and data sizes increase.
This work is closely related to previous literature in learning rate schedulers (including the heuristic and the parameter-free methods), optimization with Hessian information, and deep learning system design, which are discussed in Section 3.2 and Appendix D
Related works
Contribution We propose the generalized Newton's method (GeN) a Hessian- -iniiiin----omeddd approach which merges the information from the full Hessian into the learning rate, so to dynamically adapt to the loss landscape and accelerate the convergence. We examine GeN on 5 criteria: automaticity, applicability, scalability, computation efficiency, and convergence speed.
Overall, G is an automatic optimizer that is applicable to the general optimizers and work successfully in deep learning without adding much computations. Our efficiency analysis shows that GeN is perfectly scalable to large-scale training and as computationally efficient as existing optimizers. We empirically demonstrate that GeN is highly performant on image classification, text classification, natural language generation, object detection, instance segmentation, recommendation system, and marameter-efficiee training (PET).
MOTIVATION
2.1 NOTATIONS
We denote the model parameters as w, E Rd, where t < T is the index of iterations; {æ:} are
the samples, with or without labels. For any loss function, we denote L(w) == E2, Lww, x) as the
We use 'generalized' to mean that (1) Newton Raphson method can be viewed as sub-case of GeN and (2) we leverage the generalized inverse without inversing the Hessian matrix.
2

---

Published as a conference paper at ICLR 2025
atd
Figure Effects of various learning rate schedulers. Left two: ResNet18 on CIFARIOM dataset, compared with constant learning rates. Right two: GPT2 on E2E dataset, compared with heuristic learning rate schedulers.
generalization loss, and L(w) Σ L(w, w²)BB as the training loss. We denote the mini-batch stochastic gradient as optim (VL) = P, VL E Rd, where VL(w;) := T
Σ. aL(w...:: is the
vanilla gradient and optim the pre-conditioned gradient of any optimizer. For instance, SGD simply gives g (VL)
VL; SignSGD special case of Adam) post-processes the gradient as g gSignSSD (VL) sign LL); gradient clipping gives g (VL) min(C//|VZLll
and m V where is binary mask and @ is the element- wwie multiplication. We highlight that many optimization algorithms, including but not limited AdaGrad, Adam, Sophia, momentum, and weight decay, can also be summarized as the post-processing of V..
similarly for the projection; PET (e.g. LoRA) gives
2.2 SECOND-ORDER TAYLOR EXPANSION
In deep learning, the models are updated via the gradient descent by various optimizers:
W++1 = Wi Th optim (Wr))
(2.1)
Appyling the Taylor expansion on the loss and leveraging 2. at the current iteration.
we can derive the loss improvement
2
I(w,) L(w(+1) = L(w,)= - L(w; mug..lim)) 17: G2 g
optim
(g. optim
Hig
E.gopii
optim
+ O
2
(2.2)
where G.
OL and H, ow.
0² are the oracle gradient and Hessian, respectively. Ow?
In light of 2.2 claim that employing the second-order Taylor expansion is (1) necessary, since the first-order Taylor expansion only characterizes a linear approximation of the loss and thus fail characterize the loss curvature; and (2) sufficient, especially in the small learning rate regime where large models are universally trained and (17²²) is negligible In fact, (2.2) is also used in the analysis of neural scaling laws (Kaplan al. 2020 McCandlish et al. 2018).
theoretical
We visualize the loss function in Figure in which quadratic function with respect to is fitted by ignoring the higher order terms,
L(w,) L(w, n.g. optimn
Agggi m)) := n) G. gi
optim
" optim gg
H g:
optim
(2.3)
2
3 METHODOLOGY
3.1
GENERALIZED NEWTON'S METHOD
Our goal is to minimize the loss L(w:) over the domain of learning rate 1) E R, in particular the next-iteration loss in 2.3 fact, if we ming." AL(g. 77) over both learning rate and descent
The classical convergence analysis of gradient descent also leverages the second-order Taylor expansion T(w G) L(w) + G G Eg- G where C. is the Lipschitz smoothness of L. This quadratic function minimized 77 1/C.
3

---

Published as a conference paper at ICLR 2025
et Quetck plat.ng
g-
Figure Illustration of the second-order Taylor expansion 2.3). Left two: ResNet18 on CIFAR100 with SGD. Right two: GPT2 on E2E with Adam W.
direction, then the optimal solution is 7gg g H. and therefore w/+1 = w. - H, - This recovers the vanilla Newton's 's method conditioning that H, is invertible.
By working with the domain of 17, we effectively reduce the high(d+ 1)dmmensioon ming. (L ()) uni-variate problem min, (L 17). From (2.3). it is obvious that the optimal learning rate is optim optim) G, gr
VoaN (g: (gt
' optim
(3.1)
The closed form of (2.3) allows us to directly derive the optimal learning rate, without resorting to more complex methods such as back trackin or line searches.
Remark 3.1.
That is, given gi g (determined by the pre-conditioner P.) and that (g) method transforms any base optimizer to new optimizer by
Hig,
optim
optim
0, our
(g (
G optim
W++1 ut ,
optim
w.
(3.2)
(g.
optm
H optm
We term the family of optimizers in (3.2) the generalized Newton's method (GeN), because the vanilla Newton's method is a sub-case by Proposition 3.3 We highlight that gi gotiim can come from
any optimizer or even be random: e.g. equip (3.2) with gD to obtain GeN-SGD from SGD, or with g
Adam obtain GeN-Adam from Adam.
Remark 3.2. When the formulation of (3.2) is restricted to SGD without the pre-conditioning. this
equivalent form of GeN-SGD has also been presented in prior works like LQA (Zhu et al. (202)) and QLABGrad (Fu & Wu (024)) and ADLER (Balboni & Bacciu 2023). However, without the general optim through pre-conditioning, such formulation does not include the Newton's method as a sub-case. We dedicate Appendix t. highlight the similarities and differences between GeN and these works.
Proposition 3.3. if
H G 3.2 reduces to the Newton's 's method as ni g
optim
H, GG.
Another way understand (3.2) is via the generalized right inverse (see Definition A.1 For the simplicity of presentation, we drop the super-script of g:
opti from now on. We can write
(g. HH) g g; Hig = T/ g: (g. He) gi G.
(3.3)
which resembles the Newton's 's update H, G, but H. and G, are projected along the direction of g::
Wi+1 = w. HH,-H, H, - g. H,W++1 = g, H.W: - g, G; f- w = w. - (g. H.) g: G.
Remark 3.4. GeN-SGD is scale-invariant, as x. G.g. does not change g; is multiplied by a factor g, H.g.
of c E R, i.c. g: cg., This indicates that GeN-SGD (but not GeN-Adam) is stable w.r.t. the vanishing/cxploding gradient and does not need the gradient clipping.
FFor a row vector A E 1x its left inverse does not exist since rank (A) = 1: its right inverse is column vector =1 E R such that A -1 = 1.
4

---

Published as a conference paper at ICLR 2025
3.2 DERIVING 17" WITHOUT BACK- PROPAGATION
To compute 17" in 33.1 for GeN optimizers, or equivalently to compute G, gr and especially g, H.g the straight-forward but inefficient approach is to compute or approximate G2 and the full H,. For example, H, can be approximated iteratively by BFGS methods, although instantiating and inverting an Igdd matrix is prohibitively expensive for large models. More commonly, H2 is approximated by its low-rank representation (e.g. K-FAC) or its diagonal (e.g. AdaHessian, Sophia), which is usually combined with a replacement by the Fisher information (e.g. Adam, AdaGrad). However, these approximations incur at least (d) memory overhead, and may sub-optimal in performance due to the gap between the approximated Hessian and the full Hessian.
Alternatively, we can estimate g, Hgg: via the Hessian-vector product of H,g., without directly accessing Hy: firstly back propaaroggg on L gives gr and then back-proggg on gr (w.)² gives Hgg:- In fact, all Above-mentiones Hessian- vector product" which is not supported in large-scale distributed learning such as DeepSpeed (Rasley et al. 2020). Megatron (Shoeybi et al. 2019). and FSDP (FairScale authors) (021). because the computation graph is complicated and interferes with the communication orchestra. In summary, existing methods suffer from two constraints: they have to either approximate H, and sacrifice the performance, or to rely on the Hessian- vector product and sacrifice the efficiency and scalability.
methods (except BFGS and Fisher-related methods) need the
In stark contrast, we can overcome these constraints by using multiple additional forward passes to efficiently compute G, gr and g H,g: without accessing G, and H,, which is universally easy-to- implement because the forward pass is a fundamental operation in any deep learning system. To be specific, we apply gradient descent with different learning rates and derive the quadratic function in (2.3). Our approach can be viewed as extension of LQA (Zhu et al.) 2021). but allowing more flexibility while enhancing the stability and speed of convergence (see Algorithm| and Remark (355. As an extension, our method can use more forward passes to fit a higher-order polynomial than the second-order one in
3.3 ALGORITHM
We now present quadratic curve fitting approach estimate the optimal learning rate TdeN in (31)
L(w, - ng. mggi - L(w,) + by AA 7
17" (T) = /A" where A",b" b = argmin AER,bER EEN
2 (3.4)
in which I is set of learning rates, e.g. r {- T7 1, 0, m-1 } in Algorithm and the objective function leverages the Taylor expansion in (2.3) Therefore, we obtain
G optim ~ b² and (g. optim
Hig. opoim ~ A - 17" ~ NGaN-
optim
In fact, a mathematical equivalence can be established between this curve fitting and the finite difference (see Appendix A.3). Especially, for 3-point I' == {-1) 1. O, m-11. ). the finite difference
approach from Zhu al. 2021 gives estimate that is equal to (3.4):
T/- L L_
Mioa (T)
2 L4 2Lo + L where L == L(w, - 1 optim
(3.5)
However, on one hand, (35) is not generalizable it takes different forms whenever I' changes (see
an example of Vio (f0, 17, 2n1)) in Appendix ) On the other hand, the formulation is complicated when I' takes more than 3 points (see example of 5 points in (A.2) ). while (3.4) easily extends to any number of points as demonstrated in Figure
In practice, we leverage the curve fitting implement 3.2 via an efficient algorithm in Algorithm Remark 3.5. We discuss the flcxible designs of Algorithm and extend the discussion in Appendix
optim from any base optimizers such SGD, AdamW and PET. In line 3, GeN can operate g:
*Estimating the diagonal Hessian needs the Hutchinson method and Hessian-vector product, where R EEex Vs. 3 Hv + diag(H) as K - oo for vs (N I). Because the precision of these meth- ods relies on computing va @ Hv for K rounds, the training is very slow as the cost is K times that of standard proppaaapa,,,o,, say K 20 in Sophia and K 100 in PyHessian.
5

---

Published as a conference paper at ICLR 2025
Algorithm I Generalized Newton's optimizers (GeN), e.g. 7 0.9, Φ 8
1:
for E 1...... T do
2:
Compute loss Lo - L(wr) by standard forward pass optim (w,) by the hack-propagation on Zo
3:
Compute gradient gr
4:
it't mod 4 = 0: then
5:
Compute L+ L(w, + M optim g by two forward passes
6:
Fit the quadratic function via (.4): {- ) {L_, Lu, L+}
7:
Extract A b from the quadratic function and derive 17" = b" /A"
8:
A* > 0, b* 0, R2 score > 0.99 then
9:
Update the learning rate = 7 + - -7)n"
Update w1+1 W: 1e.i
In line setting large + significantly amortizes the computational overhead (see Section 4. where GeN optimizers are almost as fast as the base optimizers).
In line 5, the forward passes are cheaper than line 2, in that they do not store the activation tensors and save the memory which translates to faster training. addition, we can use more forward computation cost but reducing the variance in estimation of n
passes to fit 2.3), incurring Notice that the additional computation can be easily amortized through Φ.
In line 6, we highlight that {-/t-1 O, ft-1)} } is symmetric and auto-regressive, without introducing new hyperparameter. The choice is justified Appendix A.3]
In line we ensure the convexity (A* > 0), the positivity (b* 0) and the goodness of fit (R2 score > 0.99) for the update of learning rate.
Algorithm I is an approximation to the GeN method in (32)). since 3.4) approximates 7JGeN in
3.1.. We also give Algorithm 2 that implements GeN exactly as described in Section 3.2
3.4
ERROR ANALYSIS FOR OPTIMAL LEARNING RATE
We now analyze the estimation error of 17" 3 with batch size B and mini- mini-batch loss L(we). The estimation error consists of the sub-sampling error by using the mini-batch, and the precision error from fitting (.3) We note that the analysis based on the closed form of 17", which is available to us through MoA in b.5p.
Proposition 3.6. The estimation error of 1f" in 3.1 by mini-batch losses (Lo, -., Os O( where B is batch size and Tパ-1 is the learning rate from the previous iteration.
Empirically, the sub-sampling error Opl /BB dominant, compare to the precision error O As consequence, advocate apply GeN optimizers with large batch size for the best performance.
Figure 3: Convergence of ResNet18 on CIFARIO, optimized by GeN-SGD with various batch sizes.
4 EFFICIENCY AND SCALABILITY ANALYSIS
In this section, we show that GeN optimizers are as computationally efficient and scalable (in terms of the utility and the system design) their base optimizers. We train CIFAR10 (Krizhevsky et al. 2009)

---

Published as a conference paper at ICLR 2025
ResNet 18, 34, 50, 152 (He al., 2016) and ViT tiny, small, base and large (Dosovitskiy et al. 2020). For fine tuning, we use the pretrained models from the PyTorch Image Models framework (Wightman 2019).
For the utility,, we observe on CI that GeN optimizers work well with different model sizes across different architectures.
Tea
Vitumaal
Beredoou
Figure 4: Convergence of GeN-SGD (upper panel) and GeN-Adam W (lower panel) on CIFAR1O with various model architectures and sizes.
For efficiency and system-wise scalability, we focus on the additional forward passes in Algorithm I especially the scenarios such as parameter-efficien training (PET) and distributed learning. Our default setting is full-parameter training (including mixed precision training), t 1, and on single GPU (no communication cost among devices).
To set the stage, GeN optimizers have the same peak memory cost the base optimizers, all optimizers need forward passes and we adopt CPU off-loading. Hence it suffices to count the additional time complexity introduced by GeN. In the default setting, we can write
Base
1/(F + B+(F+++C)
F+B+C F+ ++++++2
absolute speed:
relative speed of GeN:
GeN
FF)
where F is the time complexity of the forward pass, in terms of float-point operations, B is that of the back propaapppa,,,onn and C' is other costs including the communication and the data loading, which minimal on single GPU. Given that in full-pate parameeert training, B 24 the GeN optimizers are roughly 60% as fast as the base optimizers.
4.1 LAZY LEARNING RATE UPDATE
One simple trick to make GeN almost fast base optimizers is to update the learning rate every > iterations, so the additional computation is amortized. For instance, GeN achieves 86% relative speed at @ = 4 and 92% relative speed at + 2 8.
Teiiie Beni
Figure 5: Convergence of ResNet18 on CIFAR10, optimized by GeN-SGI with various +
Forward pass takes unit of time. prok-pton consists of two sub- cub-processes-o output gradient and parameter gradient, each taking unit of time. See the complexity analysis in Table of al. 2202)
7

---

Published as a conference paper at ICLR 2025
In the PET setting, most parameters frozen whose gradients not computed. Hence B F and the relative speed of GeN becomes 1+1/$* e.g. 50% at d = and 89% at ① = Empirically, applying & has insignificant effect on the convergence.
4.2 COMMUNICATION IN DISTRIBUTED LEARNING
For lcage-scale optimization, the distributed learning with multiple devices necessary but chal- lenging, in that (1) the communication orchestra is complicated, and (2) the communication cost is significant (C > O). These two challenges determine if and how well an optimizer scales under distributed solution. For data-paralle solutions such as Distributed Data Parallel and ZERO1/2 (Rajb- handari et al. 2020), the communication orchestra is relatively simple that many Hessian-related optimizers are executable. For model-paralle, and hopeline-paralle solutions such ZERO3 and FSDP, each forward pass requires the communication of model parameters, and GeN indeed adds noticeable volume of communication. Nevertheless, applying the lazy learning rate can essentially reduce the communication overhead to a negligible level.
EXPERIMENTS ON SYNTHETIC DATA
To compare GeN and different optimizers deterministically in the synthetic setting, we experiment on 2-dimensional functions and carefully select an optimal learning rate for each optimizer (see the details in Appendix B.I.
+23 +15
Tarvicrs
45
Figure 6: Optimizing over the Rosenbrock (non-convex) function. Plots 1&3: losses over iterations optimized by different optimizers. Plots 2&4: 2D visualization of the optimization trajectories 40-th iteration (Plot 2) and the 180-th iteration (Plot 4).
In Figure test the Rosenbrock function, which is non-convex and has unique minimum at (1, 1) that lies in narrow valley. The left two plots show the trajectory of our GeN-SGD and its convergence speed, which significantly outperforms other optimizers. The right plots show the one-to-one comparison between the base optimizers (dashed curves) and their GeN variants (solid curves), from which the acceleration by GeN is observed universally.
In Figure 7
we test on the Beale function, which is convex and has a unique minimum at (3, 0.5).
and observe the same advantage of GeN.
40.0
Figure 7: Optimizing over the Beale (convex) function. Plots 1&3: losses over iterations optimized by different optimizers. Plots 2&4: 2D visualization of the optimization trajectories at 60-th iteration (Plot 2) and the 40-th iteration (Plot 4).
8

---

Published as a conference paper at ICLR 2025
EXPERIMENTS ON REAL DATA
In this section, we test GeN on real datasets across image classification, text classification, natural language generation, object detection and instance segmentation. We additionally experiment image generation and recommendation system in Appendix B] where all training details can found. Our experiments cover end-to-end training well as fine-tuning, and include PET methods such as LoRA (Hu et a and BitFit (aken et al. 2022).
6.1 IMAGE CLASSIFICATION
We apply variants of SGD ResNet50 and A ViT, by training computer vision datasets with various sizes (e.g. Places365 has 2 2 million images) and difficulty (ranging from 30% to 98% accuracy). In Table and Figure [ GeN optimizers consistently achieve high accuracy when compared with heuristic learning rate schedulers (i.e. constant, linear and cosine decay) as well as automatic optimizers like Prodigy and D-Adaptation
Table 2: Test accuracy of ResNet (optimized by SGD) and ViT (optimized by Adam W) on various image classification datasets.
CIRRRIO
CIAARIO
Feod10]
GTSRB
SVHIN
Places365
INa22021
reference
Kriztevsky
20133
2014
apoclis
GeN-SGD
44.57
SGDDccssstatt
95.91
$1.64
74.24
95.20
95.00
$1.09
33.5 33.80
ResNec50
SGDXlinear decay)
95.52
$1.67
30.95
30.69
SGDXcosine docay)
05.82
80.71
76.39
95.20
95.27
51.15
31.11 11.10
Prodigy
85.17
80:39
80.74
97.80
96.23
501.3
33.77
Deadepi SCDD
05
80.95
80 50
97:15
95.5 32
47. 23
38. 00
GEN AdamnW
95.68
91.82
90.48
99.06
97.14
$9.90
56.25
Adaas Wicntstant)
97.49
89.25
35.44
98.54
96.65
58 25
65 62
ViT-bose
Adum (liner decay)
98
92 92.60
54
07.08
58 555
65 43
Adam Winsine docay)
98.73
92.71
90:46
96.77
97.16
58
67.04
Prodigs D adapt AdumW
92.89
97.13
57.24
62.66
97.56
89.45
99.04
96.77
56.19
66.52
100 11 10lie
Sarcore
Prodayy
Figure 8: Convergence of ViT on INat2021 dataset, optimized by variants of AdamW.
6.2 NATURAL LANGUAGE PROCESSING
We compare GeN-Adam with a variety of learning rate schedulers on natural language generation (NLG) and natural language understanding (NLU).
For NLG experiments, we train GPT2 (Radford et al. 2019) model with LoRA on the E2E dataset (Novikova al.) 2017). We measure the quality the generated texts by the perplexity (the exponential of loss), BLEU (Papineni et al.] 2002). ROUGE-L (Lin) 2004), METEOR (Banerjee & Lavie 2005), NIST Doddington, 2002), and CIDEr (Vedantam et al. 2015). We use (Hu et al.) as the baseline, which trains for 5 epochs with linearly decaying learning rate. In Figure and Table 3] GeN consistently performant and outperforms the baseline over multiple metrics. Somewhat surprisingly, the learning rate of GeN continues to go up even if we extend the training to 20 epochs in Figure which is not captured by previous heuristic learning rate schedulers.
We have observed that D-Adaptation SGD diverges for all datascts when the weight decay of 5e-4 used.

---

Published as a conference paper at ICLR 2025
0.0038
Table 3: Test performance of GPT2 on E2E dataset (higher the better).
0.0030
Laaning rate
6.0034
BLEU
ROGUE
NIST
METEOR
CIDER
GeN
67.30
67.09
8,6508
0,4407
2.2810
lincar decay
66.85
67.78
8.4438
0.4375
2.2561
cosine decay
66.59
67.35
8.4511
0.4290
2,2553
Harr one
constant
65.95
66,69
8,3982
0.4462
2.1697
Figure 9: Loss and learning rate dur- ing GPT2 training.
inverse sqri(1 (v()
65.
66. 19
8.1274
0.4047
2.1001
inverse (1/()
64.43
65.95
8.0447
0,4010
2.0792
For NLU experiments, we evaluate RoBERTa- base Liu et al. 2019) on the GLUE (Wang al. 2019) benchmark with LoRA, BitFit and full-paraeeter training (FT).
Test performance of RoBERTa model with different methods on the GLUE benchmark (higher the better). Blue numbers are results in published papers, produced by heuristic learning rate schedulers in Hu al.] (linear warm-up and linear decay). Red numbers are results of GeN optimizers. We report the overall (matched and mismatched) accuracy for MNLI, Matthew's correlation for CoLA, Fl score for MRPC and QQP, and accuracy for other tasks.
Table 4:
Trainable param
MNLI
SST-2
MRPC
CoLA
QNLI
QQP
RTE
LoRA BitFit 0.IM 125.0M
0.3M
87.5186.7
95.1/94.3
90.8192.1
63.4163.7
93.3192.3
85.3186.9
86.6179.1
85.0185.1
93.7194.3
92.0192.3
61.8162.5
91.3191.5
84.2184.3
77.8/78.0
FT
86.7186.8
94.2194.7
92.5192.3
61.1164.8
92.3191.9
88.0188.4
77.4180.5
6.3
OBJECT DETECTION & INSTANCE SEGMENTATION
We train a Mask R-CNN (He et al. 2017) with SGD on the Penn-Fudan dataset (Wang et al. 2007). following the official Pytorch tutorial which uses linearly warm-up then constant learning rate. The loss L(w w) ) is the sum of losses from the classification and the localization in different model components. To be specific, the losses classifier loss, bounding box regression loss in object detection, mask loss, objectness loss, and Region Proposal Network (RPN) bounding box regression loss. The model is built on ResNet50 and pre-trained the COCO dataset (Lin al. 2014). We measure the precision Table 5),
based on the Intersection over Union (IoU).
7.0
Table 5: Average precision of Mask R-CNN (higher the better). AP P/m///l means amall/medium/larg instances, and AP the average over all instances.
0.010
25
0.008
Lewiing
2.004
manual
Object detection
0.002
AP
AP,
APm
AP
GeN manual
0.805 20000 038
20.022
0.6244a.088
0.81 18.3220022 0.002
0.0 0.0
0..02+00225
0.368 0.586+4.077
0.819~0.011
Instance segmentation
Figure 10: Loss and learning rate during Mask R-CNN training.
GeN
29.09
0.432 10.010
0.5181.. 104
0.781
manual
0. 0.768
0.388
0.455
0.783=p.020
7 DISCUSSION
In this work, we propose the GeN optimizers as a generally applicable and efficient approach towards the second-order optimization that is automatic and performant. Specifically, GeN is applicable to any future pre-conditioner that improves the convergence. However, additional work is needed to further our understanding of GeN. We remark that the learning rate in GeN is locally optimal but less is known about the global convergence speed. Looking forward, we expect further combination of more optimization algorithms and GeN, as well exploring GeN on various domains and problems.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Inaturalist 2021 competition. 2021. URL wttp:tttppss//ttoo..oco/////aa/p
Cree/master/2021
AI Al@Meta. Llama model card. httph//tss///ghhhh..ooooaaaaaaaa
b blob/ma
mdd
Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxandra Cojo- caru, Mérouane Debbah, Etienne Goffinet, Daniel Hesslow, Julien Launay, Quentin Malartic, et al. The falcon series of open language models. arXiv preprint arXiv:2311. 168667, 2023.
Scun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 1000::t:1n102:2251111::: 10(2)251-2776 1998.
Dario Balboni and Davide Bacciu, Adler-an efficient hessian-basee strategy for adaptive learning rate. arXiv preprint arXiv:2305. 2023.
Satanjeev Banerjee and Alon Lavie. Meteor:
An automatic metric for mt evaluation with improved correlation with human judgments. In Proceedings of the acl workshop on intrinsic and extrinsic evaluation measures for machine translation and/or summarization, pp. 65-72, 2005.
Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning, pp. 2397-2430. PMLR, 2023.
Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Food-101 1od-100--ining discriminative compo- nents with random forests. In Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part VI 13, pp. 446-461. Springer, 2014.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Charles George Broyden. The convergence of class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics, 6(1):76 1970.
Zhiqi Bu. Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. Advances in Neural Information Processing Systems, 35: 38305-3833 33318, 2022.
Richard H Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. limited memory algorithm for bound constrained optimization. SIAM Journal on scientific computing, 16(5):1190-1208, 1995.
Richard H Byrd, Samantha L. Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi-newton method for large-scale optimization. SIAM Journal on Optimization, 26(2):1008-1031, 2016.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 141240) 2023.
Aaron Defazio and Konstantin Mishchenko. Learning-rate-free learning by d-adaptation. In Interna- tional Conference on Machine Learning, pp. 7449-7479. PMLR, 2023.
George Doddington. Automatic evaluation of machine translation quality using n-gram co-occurrence statistics. In Proceedings of the second international conference on Human Language Technology Research, pp. 135-145,10 2002.
Jesse Dodge, Taylor Prewitt Remi Tachet des Combes, Erika Odmark, Roy Schwartz, Emma Strubell, Alexandra Sasha Luccioni, Noah A Smith, Nicole DeCario, and Will Buchanan. Measuring the carbon intensity of ai in cloud instances. In Proceedings of the 2022 ACM conference on fairness accountability, and transparency, pp. 1897-1894, 2022.

---

Published as a conference paper at ICLR 2025
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghami, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning reseurch, 12(7), 2011.
FairScale authors. Fairscale: A general purpose modular pytorch library for high performance and ht httpp:://gttub..c. wwtp::thhh...oooaaaeaeeeeeeaaaae http:///g..g..aoooco/c/co//oaaaa
large scale
2021.
Minghan Fu and
Wu. Qlabgrad: hyperparameterr-fre and convergence-guurantee
scheme for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38. pp. 12072-12081, 2024.
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 hour. arXiv preprint arXiv: (00.00/770.067.,, 2017.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimiza- tion. In International Conference on Machine Learning, pp. 1842-1850. PMLR, 2018
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In Proceedings of the IEEE international conference on computer vision, pp. 2961-2969, 2017.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. Cited on, 14(8):2, 2012.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. In Proceedings of the 36th International Conference on Neural Information Processing Systems, pp. 30016-30030, 2022.
Sebastian Houben, Johannes Stallkamp, Jan Salmen, Mare Schlipsing. and Christian Igel. Detection of traffic signs in real-world images: The German Traffic Sign Detection Benchmark. In International Joint Conference on Neural Networks, number 1288, 2013.
Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhi Yuanzhi Li, Shean Wang, Lu Wang. Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. In International Conference Learning Representations.
Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd's best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning, pp. 14465-14499. PMLR, 2023.
Paras Jain, Ajay Jain, Aniruddha Nrusimha, Amir Gholami, Pieter Abbeel, Joseph Gonzalez, Kurt Keutzer, and lon Stoica. Checkmate: Breaking the memory wall with optimal tensor rematerializa- tion. Proceedings of Machine Learning and Systems, 2:497-511, 2020.
Xiaomeng Jin, Zhiqi Bu, Bhanukiran Vinzamuri, Anil Ramakrishna, Kai-Wei Chang, Volkan Cevher, and Mingyi Hong. Unlearning as multi-task optimization: A normalized gradient difference approach with an adaptive learning rate. In Luis Chiruzzo, Alan Ritter, and Lu Wang (eds.), Proceedings the 2025 Conference of the Nations of the Americas Chupter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 11278- 11294, Albuquerque, New Mexico, April 2025, Association for Computational Linguistics. ISBN 8-888888-77-8888 URL https: a antho egy. or052025. naacl ong.ong......... 563/
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0888 2020.
12

---

Published as a conference paper at ICLR 2025
Jacob Devlin Ming- Wei Chang Kenton and Lee Kristina Toutanova. Bert:
Pre-training of deep bidirectional transformers for language understanding. In Proceedings of naacL-HLI, volume 1. Minneapolis, Minnesota, 2019.
Ahmed Khaled, Konstantin Mishchenko, and Chi Jin. Dowg unleashed: An efficient universal parameter-free gradient descent method. Advances in Neural Information Processing Systems, 36: 6748-6769, 2023.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Chin- Yew Lin. Rouge: A package for automatic evaluation of summaries. In Text summarization branches out, pp. 74 81, 2004.
Tsung-Yi Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In European Conference on Computer Vision, pp. 740-755. Springer, 2014.
Hong Liu, Zhiyuan Li, David Leo Wright Hall, Percy Liang, and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. In The Twelfth International Conference on Learning Representations.
Ruixuan Liu and Zhiqi Bu. Towards hyperparameter-free optimization with differential privacy. In The Thirteenth International Conference on Learming Representations.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 1rXiv:1907.11699 2019.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Ilya Loshchilov and Frank Hutter. Sgdr: tional Conference on Learning Representations, 2016.
Stochastic gradient descent with warm restarts. In Interna-
Nya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2017.
Aurelien Lucchi, Brian McWilliams, and Thomas Hofmann. A variance reduced stochastic newton method. arXiv preprint arXiv:1503.08314 2015.
Alexandra Sasha Luccioni, Sylvain Viguier, and Anne-Laure Ligozat. Estimating the carbon footprint of bloom, a 176b parameter language model. Journal of Machine Learning Research, 24(253): 1-15, 2023.
Haipeng Luo, Alekh Agarwal, Nicolo Cesa- Desa-Bianchi, and John Langford. Efficient second order online learning by sketching. Advances in Neural Information Processing Systems, 29, 2016.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 01553038-53073 2023.
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature. In International conference on machine learning, pp. 2408-2417. PMLR, 2015.
Sam McCandlish, Jared Kaplan, Dario Amodei, and OpenAl Dota Team. An empirical model of 2018
large-batch training. arXiv preprint 18Xiv:1812.0000
Konstantin Mishchenko and Aaron Defazio. Prodigy: An expeditiously adaptive parameter-free free learner. In Forty-forst International Conference on Machine Learning.
Yurii Nesterov. A method of solving a convex programming problem with convergence rate o o (1/k** 2). Doklady Akademii Nauk SSSR, 269(3):543, 1983.
13

---

Published as a conference paper at ICLR 2025
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Baolin Wu, Andrew Y Ng, al. Reading digits in natural images with unsupervised feature learning. In NIPS workshop on deep learning and unsupervised
learning, volume 2011, pp. 7. Granada, Spain, 2011.
Jekaterina Novikova, Ondrej Dusek, and Verena Rieser. The e2e dataset: New challenges for end-to- end generation. In Proceedings the 18th Annual SIGdial Meeting on Discourse and Dialogue, pp. 201-206, 2017.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 311-318, 2002.
David Patterson, Joseph Gonzalez, Quoe Le, Chen Liang, Lluis-Miquel Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean. Carbon emissions and large neural network training. arXiv preprint arXiv:2104. 10350, 2021.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- tional mathematics and mathematical physics, 4(5):1-17, 1964.
Alec Radford, Luke Metz. and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks, arXiv preprint arXiv:1511.0643: 2015.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. International conference on machine learning, pp. 8748 8763. PMLR, 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21(1):5485-555 2020.
Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. Zero: Memory optimizations toward training trillion parameter models. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-16. IEEE, 2020.
Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He. Deepspeed: System optimiza- tions enable training deep learning models with over 100 billion parameters. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp- #505-3506, 2020.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathmaticaal statistics, pp. 400-407, 1951.
Nicol Schraudolph, Jin Yu, and Simon Günter. A stochastic quasi-newton method for online convex optimization. In Artificial intelligence and statistics, pp. 436-444444 646.443. PMLR, 2007.
Or Sharir, Barak Peleg, and Yoav Shoham. The cost of training nlp models: concise overview. arXiv preprint 2tt.:::0000.890000 2020.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catan- zaro. Megatron-Img Im: Training multi-billion parameter language models using model parallelism. arXiv preprint 1909v 08053, 2019.
Leslie N Smith. No more pesky learning rate guessing games. CoRR,
5:575, 2015.
Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. Bert4rec: Sequential recommendation with bidirectional encoder representations from transformer. In Proceedings of the 28th ACM international conference on information and knowledge management, pp. 1441-1450, 2019.
14

---

Published as a conference paper at ICLR 2025
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXfv:2302.13971, 2023a
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.00 097.0288, 2023b.
Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh. Cider: Consensus-basd image description evaluation. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4566-4575, 2015.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding, In 7th International Conference on Learning Representations, ICLR 2019, 2019.
Liming Wang, Jianbo Shi, Gang Song, and I-fan Shen. Object detection combining recognition and segmentation. In Asian conference on computer vision, pp. 199. Springer, 2007.
Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-newton methods for nonconvex stochastic optimization. SIAM Journal Bttps://ggttub..com//vvvi//
Ross Wightman. Pytorch image models.
Pytorch-image-meen
2019.
Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael Mahoney, Adahessian: An adaptive second order optimizer for machine learning. proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 10665-10673 2021.
Rui Yuan, Alessandro Lazaric, and Robert M Gower. Sketched newton-raphson. SIAM Journal on Optimization, 3253):155--1558, 2022.
Elad Ben Zaken, Yoav Goldberg, and Shauli Ravfogel. Bitfit: Simple parameter-efficien fine-tuning for wansformer-basee masked language-model, In Proceedings of the 60th Anmual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 1-9, 2022.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.570. 2012.
Bolei Zhou, Agata Lapedriza, Jianxiong Xiao, Antonio Torralba, and Aude Oliva. Learning deep features for scene recognition using places database. Advances in neural information processing systems, 27, 2014.
Yingqiu Zhu, Danyang Huang, Yuan Gao, Rui Wu, Yu Chen, Bo Zhang, and Hansheng Wang. Auto- matic, dynamic, and nearly optimal learning rate specification via local quadratic approximation. Neural Networks, 141:11-29, 2021.
15

---

Published as a conference paper at ICLR 2025
A PRELIMINARIES AND PROOFS
A.1 FINITE DIFFERENCE METHOD
The finite difference method be used to approximate high-order derivatives of scalar f(w). We denote A as one unit difference.
We start with the first-order finite difference for df and two points. There are three popular methods: the forward, the backward, and the central difference:
Forward
((w+A))1 f(an)
1(w)- ((t))-
Backward
Central
I [w++ -
The precision of forward and backward difference is O(4), and that central difference is O(A
We approximate higher-order derivatives, such the second-order & dw three).
with more points (say
Forward [(++2A)- 2f(w- A) f(w))
Backward f(w) 2f(w f(m-
Central
f(++A)- 2 f(w
A²
The precision of forward and backward difference is O(A), and that of central difference is O( Generally speaking, we can use (I: + 1) points to approximate the k-th order derivatives at O(A)) with the central difference.
The precision can improved with more points for the same derivative, say for of dw
+2
Forward
fww)) ((w-)2))
Backward
/[ s( -000--))))-------------0------0-
Central
Compared with the two-point difference, using three points improves the precision of forward difference from O()) to O(A?); using four points improves the precision of central difference from O(A²) to O(A4).
A.2 GENERALIZED INVERSE
Definition A.1. Any matrix A Rm has at least one generalized inverse A E R= such that A A = A. The generalized right inverse and left inverse are sub-cases of the generalized inverses: if A -1
R satisfies AA R Imm and rank (A) = m. then A -1 is the right inverse of A; similarly, if A L A I, and rank A) = then A L is the left inverse of A.
A.3 EQUIVALENCE BETWEEN FINITE DIFFERENCE AND POLYNOMIAL FITTING
Proof. Consider fitting the quadratic function:
L4 = Lo + G g + "¹
Hg
2
n
L_ G T g g
Hg
Then T g central finite difference method for both terms.
L - 2n
Hg
L 2Lo which is the equivalent to applying the second-on recond-order
n/²
Hence, using the symmetric learning rates (0, -n) the optimal learning rate is estimated as I. I. 77" -- with O(1?²) error.
16

---

Published as a conference paper at ICLR 2025
If we instead fit another quadratic function using (0. 2n). then
L+2 Lo 21/ g + 21) 'g
"
:- Lo +o++1 G g -+- Hg
Then Gg
41.-41.+1 +3.a 2n
g Hg 1.42-2-2 -1 th which is the equivalent to applying the
second-order forward difference to
T g and the first-order forward difference to g Hg.
Hence, using the non-symmetric learning rates (0, 21)) the optimal learning rate is estimated as 444 11-4--2--0 2-30 with (1)) error.
L+2 2L Lo
A.4 ESTIMATION ERROR OF 17"
Proof of Proposition 3.6 We omit the subscript t for simplicity of presentation. Assume samples
are independently and identically distributed, then by central limit theorem,
1 L B L
L(w + ng, = L1 + Opl
VB
Hence the mini-batch approximation
71 L 17 - L_ +p(
11
- L
Opl
1
2 14 -L0 + +
2 2 -Lo + L. + Op((
2 L4 20g + L_
VB
VB
Next, the finite difference method has precision of (17²). Hence, the overall estimation error of y)*'
is Op 1 + O
A.5
DERIVATION OF 17*
We give the derivation of (3.4p given 1- 0,0,, and {L., Lo, L-}. We aim to minimize
2.3
ignoring the superscript in optim
min L(w, ng:) or equivalently min L(w, 178)) L(w,).
"
By second-order Taylor expansion, we get
min L(w, mg:)) I(w.) so min n²
2 ge H.g - n gr
which requires the knowledge of coefficients g, H.g. and G. gi.
Using curve fitting, we estimate the coefficients g, H,g. G. s A 6 by
(L(w: mg:) [(w))) ) (4 112
2
b" argmin A,b
Σ
bn)
(A.1)
The same result can be derived with finite difference as in 3.4) (though not through an optimization problem), through the numerical analysis demonstrated in Appendix A.3
Finally, we can write 17" = 6** /A x G, g:/g. Hgg. where the error is controlled to small values by Proposition 3.6
As an important extension, we can use more points (say 1-21-11, - 0, 7 2 to derive 17" This usually gives slightly more stable convergence, almost the same accuracy, but more computational overhead.
Using curve fitting, we easily extend
g, Hig, G. R argmin A.b
Σ
(T(wr 1/8.) I(w:)) (11 br)
2% 11 W
1.
17

---

Published as a conference paper at ICLR 2025
Using finite difference, the derivation is complicated than 3.4
12 + 12 L24 + / 3
/ +
L-
" R 1l
(A.2)
L2
where 4 = L(w, + 21p B:). We refer to http:p::/ee.....ppdaaaa.oo
wonn.wikine
Sifference_coeffiie.. for the table finite difference coefficients.
B
MORE ON EXPERIMENTS
B.1 SYNTHETIC DATA
In Section 5 we carefully select the best learning rate for each optimizer, through a exponential grid search from {10-5 - 2 10-* 10-*} for kt 4, ..., For each optimizer, we train with each learning rate for 1000 iterations and choose the one with smallest objective value.
The Rosenbrock function, also known to the Valley or Banana function a classic test problem. We take its two-dimensional case:
x2) = 100(22 - =x1) +
x1)²
The Beale is a convex function with the following expression:
f(11,32) = (1.5 21 + + + (2.25 - x + xイ (2.625 - #1 + x
B.2 IMAGE CLASSIFICATION
For image classification problems, use models that are pre-trained on ImageNet and can be loaded from torchvis ion and t iimm libraries. We resize all images to 224x224 and normalize the pixel values to [-1,1]. what follows, all ResNets are trained with SGD with 0.9 momentum and 5e-4 weight decay, and VIT is trained with Adam W using default hyperparameters in Pytorch.
B.2.1 CIFAR
1O and CIFARI00 are standard tiny image datasets that we have used as the test-bed. Our default hyperparameters for Figure !
Figure 2 Figure 3 Figure 4 Figure alae: 500, 4
SGD learning rate=le-2, AdamW learning rate=le-4, unless one of the hyperparameters are varied for the ablation study.
B.2.2 SECTION 6.1
We use 500. SGD learning rate=0.1 and AdamW learning rate=le-4 for all datasets. Notice that D-adapt SGD diverges on all datasets so we have to remove the 5c-4 weight decay for this optimizer only. For Places365 and INat2021, we use + 20; for other datasets, because they are much smaller in sample size, we use + 4.
B.3 NATURAL LANGUAGE PROCESSING
All transformers (RoBERTa, GPT2) are trained with AdamW using default hyperparameters in Pytorch.
B.3.1
NLG
In Figure I Figure 2 Figure 9aauee/ani and Table 3] we follow the codebase of al. and use B 256, sequence length 128, To le and 5 epochs. While applying, we set +b 4.
B.3.2 NLU
The results of full-parameter training and BitFit training are from Table of Zaken et al. (202)) and those of LoRA are from Table 2 of Hu al.) However, since LoRA didn't 't report the F1 score of
18

---

Published as a conference paper at ICLR 2025
Initial learning rate for FT
Batch size
# of epochs
Eval metries
MRPC
128
2e-5
10
F1
SST2
128
le-6
10
acc.
MNLI
128
le-6
(1 for FT) matched aecsmmiimtt acc.
CoLA
128
2e-5
10
Matthews corr.
QNLI
128
2c-5
10
acc.
QQP
256
2e-5
F1
RTE
128
2e-5
60
acc.
Table 6:
and evaluation metrics for training GLUE datasets with GeN,
MRPC and QQP, we run LoRA under settings (i.e., the same batch size and number of epochs) for fair comparison. The table below records our hyper-parameters for training with GeN.
While applying GeN, we set + 8 for all tasks. For hyperparameters that were not mentioned in T we followed Table 9 of Hu et al.
B.4 IMAGE GENERATION
We apply GeN-Adam to pre-train a deep convolutional generative adversarial network (DCGAN) Radford et al. 2213),, following the official Pytorch tutorial, which uses constant learning rate, with batch size 128 and training for epochs. The training uses CelebA [Lu al. (2015). real dataset of > 200000 face images. We qualitatively compare the fake generated images with the real ones,
04.000
Ypr ney
33
11 n me
009029
1000
2000
2508
Figure 11: Left: learning rate of GeN-Adam over the iterations. Right: losses of the components in DCGAN, where is the discriminator and the generator.
which demonstrates the effectiveness of our optimization that can be further improved with longer training. We believe this showcases the potential applicability of GeN to the vision generation, e.g. audio/music generation and diffusion models.
B.5 RECOMMENDATION SYSTEM
We apply GeN-Adam to BERT Kenton & Toutanova (0099) model for recommendation system, following the setting Sun et al. (2019), with a batch size 1024 and training for 100 epochs. We train on MovieLens- Im dataset, containing million user-rating pairs. The performance is measured by the recall and Normalized Discounted Cumulative Gain (NDCG, related the precision). The baseline is a constant learning rate given by the codebase. We observe that GeN outperforms the state-of-the-an setting (batch size 128) but needs a larger batch size to converge stably.
batch size
@ecall@
Rccall@5
Recall @ 10
Rocall 20
NDCG@1
NDCG@5 NDCG@ [0
NDCG@20
1024
0.720
0.821
0.900
0.575
0.607
0.627
Constant
1024
0.374
0.693
0.796
0.883
0.374
0,546
0.580
0.602
Constant
0.820
0.895
0.622
Table 7: Performance of top recommendations (Recall means the recall of 5).
19

---

Published as a conference paper at ICLR 2025
mages
Figure 12: Side-by-side comparison images, which is comparable to the quality here
NOCOOOO
Aacarigoo
5.50
9.00
6.30
CMr03-33--1 2030
49
25
169
Figure 13: Convergence of GeN-Adam and Adam with constant learning rates.
C MORE ON THE DESIGN OF ALGORITHM
C.1 TWO MODES OF FORWARD PASS
As we discussed in Section 3.3, there are two modes of forward pass: with or without the activation. the forward pass is followed by the back paok-propagation. then it must store activation each layer. The activation is R BTd where B is the batch size (say 256), T is the sequence length (say 2048 for LLAMA) or pixels (say 224 for ImageNet), and is the input dimension of one layer (say 768 for transformer block). In practice, the activation is very expensive to store and could take up 95% of the total memory cost (see Jain et al. (2020) Figure 3).
On the other hand, the forward pass be activation-free if we only do inference, not the training. In Pytorch, this is enabled by with torch. no_graddddddooooo (). We can leverage the saved memory to larger batch size and thus accelerate the computation, further reducing the GeN overhead.
C.2 CHOICE OF FINITE DIFFERENCE
We extend our discussion on fitting the quadratic function. In general, we can learn Hg and G by fitting any collection of finite differences, say { the corresponding losses [L(w, - {.g:)) For instance, we can use more than 3 points or use non-symmetric sequences like (0, 5. 2 (I(w.,) I(w;; {g:), L(ur. 2(g:)).
We recommend to use the symmetric sequences like (-2ç, 6, 2 for better precision (c.f. Appendix A.3).. Nevertheless, this introduces hyperparameter & and much churn to tune it, as is the case in zero-th order optimization Malladi et al. (2023). Therefore we use the symmetric and ruto-regressive sequences that employ the previous learning rates: (-21)- -,,-1, 0, 7)-11 21),-1), 1). Lastly, to reduce the computation overhead, use the fact that any quadratic function is uniquely determined by the three points. Therefore, we can use (-7)-1 , O, 7)-11 as the shortest sequence that both symmetric and auto-regressive.
20

---

Published as a conference paper at ICLR 2025
C.3 SMOOTHING
In Algorithm we propose to use the smoothing (e.g. setting 7 = 0.9) as a standard technique in the deep learning optimization. Note the smoothing is also known the momentum. For example, Nesterov accelerated gradient and SGD both use the smoothing on the gradients; Adam and Sophia additionally smoothing the pre-conditioner. We empirically confirm that the smoothing helps stabilize the training in all our experiments.
C.4 INITIAL LEARNING RATE
GeN optimizer and existing parameter-free methods such as D-adaptation Defiait Defazio & Mishchenko (2023) and DoG Ivgi et al. (023) still need someone hyperparameters. To be specific, D-adaptation needs an initial D estimate and growth rate = 1 the training is unstable; DoG needs to carefully select r, compute the initial distance: too large values could make DoG diverge, while small values cannot optimize the model. In our case, GeN only needs one hyperparameter - the initial learning rate y/o, which can be determined with nearly zero effort of manual tuning. We now introduce two methods to set 17o.
C.4.1 AUTOMATIC CORRECTION
Empirically, GeN optimizers have the capability to automatically correct the learning rate if ro is set large too small. We test a wide range learning rates, with the largest one being 1000 larger than the smallest, all resulting in similar final performance. This capability allows the practitioners to start the training with highly robust choice iju.
Intial nm
Leuning 1000
intial 25
inbal 2.1.1
intial 2.01
tu cw1.
iniiil 3.001
p-0
32.2
(w0
555
Far 61k77
IIEM g=1.
inbil pw5
Inti (005
inbil p.0.1
Inti (-03
Thsh
Hitil 1:00
Inti (-0.0)
HvEil (-0000)
Intl 2-0.001
Bax 21003
Figure 14: Convergence of ResNet18 on CIFAR10, optimized by GeN-SGD with B = 200.
In Figure 14 smaller Th (say < 0.1) quickly catches up at an exponential speed then stabilizes, whereas larger 7/ tends to decay from the beginning of training. We recommend setting no with small values, to avoid risking the possibility of loss divergence.
C.4.2 AUTOMATIC SEARCH
Alternatieely, we can search the fJu automatically at the first iteration. The computation overhead is negligible since it will be amortized over large number of iterations. In practice, observe that an exponential grid search ranging from 10 102 can quickly give an accurate estimate 1)-- Our experiment in the same setting Figure 14 selects no 0.008, close the red curve.
21

---

Published as a conference paper at ICLR 2025
C.5 EXACT ALGORITHM FOR GEN
We give algorithm that computes precisely using higher order differentiation. In contrast Algorithm| that approximately computes GeN, this algorithm uses the second-order back-prowe progattionnn which is generally inefficient and incompatible with large-scale distributed systems due lack of support.
Algorithm 2 Generalized Newton's optimizers with higher order differentiation (GeN-HOD)
1: for E 1...... T do
2:
Compute loss L(w,, by the standard forward pass
3:
Compute vanilla gradient by the first-order back-propagation from L(ws) E R
4:
Compute modified gradient g:
optim (w;)
5:
by the second-order back-propagation from Compute the Hessian-vector product H,g:
optim
optim
8:
6:
Derive G, optim and (g.
optim optim
Higi by multiplication
G.
7: Derive the optimal learning rate 1/t
by 3.1
(gt
H.g.
qum
8: Update w Wt 1/
C.6 PRELIMINARY RESULTS ON PRE-TRAINING
Following https: www..//uhhhcoccuuugg/g..oac hwwppttochhppccccooooooooo cwf.rriaaaoooeee git, we experimented on com CIFARIO 10 training from scratch on ResNet18. We replace SGD with Adam W at learning rate le-3 but the rest settings are the same as in the repository. We use = 4 for GeN. For D-adaptation, we their AdamW version for fair comparison.
80
60-
Prodlay
Prodigy
D adastation
D D-adaptation
Gell
Gell
20-
Berations
Figure 15: CIFARIO pre-training on ResNet18 for 15 epochs.
C.7 DEPENDENCE TOTAL STEPS
Total steps T is an important factor existing learning rate schedules (e.g. linear and consine decay in Table R): larger T' allows longer aagg--leamingg-rttt-triinnn while smaller T requires early learning rate decay. Our GeN in (3.1 is originally proposed as T-independent. Yet it may be slightly improved with dependence of T, especially if T is relatively small:
TG optimy
(ge optim)
t/T)
(C.I)
where the last term is hyperparameter-free free factor, decaying from to 0. The form of this factor is flexible, e.g. instead of linear decay,
also cosine decay like in D-adaptation Defazio & Mishchenko (2023) and Prodigy Mishchenko & Defazio which denote such factor as %k.
We have used this variant of GeN in the experiments of Places365, INat2021 and NLU.
22

---

Published as a conference paper at ICLR 2025
D RELATED WORKS
D.1 HEURISTIC LEARNING RATE SCHEDULER
proper learning rate important for fast convergence. There long line of work making efforts to search the best decay to 0 as the training iteration increases. This due to the mini-batch sampling which does not guarantee that SGD converges even in the convex setting. As consequence of this theoretical insight, different learning rate schedulers have been devised, albeit usually based on the empirical evidence.
especially the learning rate. In general, the learning rate should
type
scheduler
HP
reference
Constant
Raffel er ml 2020
Cusine decay
rall cos (Fa77 11/2
co
Losbchilav Hulter A0Tb Kadlord
Stepwise
i1 <1
16 Jeee
28 +1
Heuristic
Linear decay
%ell (77)
66
Smith
Polynomial decay
6u/f co/
Expomential decay
<g expl pt)
Co.P
WarmpUp
Cmin P
Goyal et al. 2017
Table 8: Learning rate schedulers for training with T iterations. HP means hyperparameter.
In deep learning, state-of-the-ar performance is usually obtained by multi- hillriityyprrmeter scheduler: for instance, LLAMA Touvron et al. (2023a) combines linear WarmUp and cosine decay (not decaying to O but minimum value); ResNet He et al. (2016) uses the stepwise scheduler (starting at 0.1 and decay by 10 times at 32k and 48k iterations) with 5 hyperparameters. While tuning multiple hyperparameters may be feasible for some models, is generally expensive for large models (say over 1B parameters).
D.2 AUTOMATIC LEARNING RATE
A number of automatic or parameter-free learning rate methods have attempted to dynamically adjust the learning rate throughout the training. D-adaptation Defazio & Mishchenko (2023) and Prodigy Mishchenko & Defazio both improve AdaGrad by characterizing ||wo w. where w. is the global minimum. However, this motivation is not well-defined in deep learning as the minimum not unique. In fact, for all computer vision experiments, D-adapt SGD with even small magnitude of weight decay diverges. Also Prodigy only implements to Adam, hence not future-proof for more advanced algorithms such as Sophia.
DoG Ivgi et al. (2023) and DoWG Khaled et al. 2023) are parameter-free free dynamic SGD scheduler with convergence guarantees for stochastic convex optimization. Additionally, these methods only work for SGD but not for the adaptive optimizers like Adam, and the algorithms requires to store the past iterates (because the output is the weighted E. C2 we in Equation 2 of Ivgi al. (2023) and Theorem 1 of Khaled et al.] (2023), instead of the last iterate Wy). As the authors admit in their Github) 'DoG must combined with iterate averaging' which adds to the memory cost that may be unacceptable for large models. In practice, we have observed these methods to be very unstable and inaccurate, e.g. on toy tasks like fine-tuning CIFARIO/100.
D.3 SECOND-ORDER METHODS
There is a long list of second-order or quasi-second-order methods in the optimization literature. including but not limited stochastic Newton methods Byrd et al. (2016); Wang et al. (2017); Lucchi
et al. (2015); Schraudolph et al. (2007), sketching methods Yuan et al. (2022); Luo et al. (2016) and diagonal Hessian methods in Section 3.2 We notice these methods are difficult implement in distributed learning at large scale, because the Hessian information (or Hessian veector product) is generally not supported by auto-differentiation or too expensive to store for large models.
D.4 PRIOR WORKS SIMILAR TO GEN
We elaborate multiple prior works that also present GeN-SGD in 3.1 and leverage the second- order Taylor approximation in (.3). However, these methods limited to goptim g SGD and
23

---

Published as a conference paper at ICLR 2025
not generalize to pre-conditioned gradients like in AdamW. As consequence, the role of pre- conditioning of gradient is under- investiavvt,,,,,dd,, and the connection to the generalized inverse (33) and to Newton's ' method in Proposition 3.3 is lacking.
Importantly, a missing piece in these works is to validate the second-order Taylor approximation of L(w 7g.). Our empirical visualization in Figure serves as necessary validation, without which the method and algorithms are not justified in the first place
Experiment-wise wise, prior works focused on computer vision and convolutional neural networks, whereas we have extensively tested various model architectures (transformers, GAN, recommendation systems) many tasks like language modeling.
LQA
The closest work to ours is LQA Zhu et al. 2021 which proposes 3.5
At the method level, this method (termed LQA-SGD) equivalent to GeN-SGD but it not extended to general optimizers: in their Figure 1-4, where the red curves in each figure are exactly the same, L.QA-SGD is compared SGD, SGD-momentum, and Adam; but there is no LQA-Adam. Additionally, the convergence speed of LQA-SGI (or GeN-SGD) is missing, whereas we provide an analysis under the convex Lipschitz regime in Appendix
At the algorithm level, LQA relies on estimating the losses at (L(w - -g), L(w), L(w mg))
" L(w + 7g) L(w 7/
ULoA 2 L(w + 7g) 2L(w) L(w 7/
This fixed choice of learning rates gives a closed form but could limit the general applicability when considers other learning rates (see our discussion below (3.5)). The estimation error of LQA was not analyzed. In contrast, our Proposition [36 indicates the benefit a large batch size which is empirically verified in Figure Additionally, like smoothing and lazy frequency, in order to stabilize the training and enhance the computational efficiency, which are not presented in LQA.
adopt critical techniques in Remark 3.5
While LQA and GeN requires 2 extra forward passes, QLABGrad Fu & Wu (024) only requires extra forward passes by restricting to SGD (hence incompatible to Adam W and other adaptive optimizers).
QLABGrad
of
|
IOLABGrad
2 L(w 7g) L(w) + " V
QLABGrad provides convergence analysis in terms of the gradient norm, i.e. ||VL||| + 0, whereas our convergence analysis in Appendix Elss in terms of L, O.
ADLER ADLER Balboni & Bacciu (2023) uses Hessian-vector product to compute H,g, (viewed as a sub-case of Algorithm 2). We note that Hessian-vector product not only slow, but also not
supported yet in distributed learning systems. Nevertheless, ADLER indeed implements (3.2) without approximating Moe, whereas the estimation eтror must be considered for other algorithms since
Tooa MoaN "QLABGrad
D.5 APPLYING GEN TO MORE PROBLEMS
We expect general applicability of GeN problems beyond the formulation of 2.1 Examples include differentially private optimization Liu & Bu, multi-task optimization Jin et al. (2055) gradient ascent, projected/proximal gradient descent, reinforcement learning, etc.
E CONVERGENCE ANALYSIS OF GEN
We provide the convergence analysis of GeN for multiple dimension, given that the 1-dimensional GeN is equivalent to the classic Newton-Raphe Raphson method. We work with the convex and Lipschitz
In fact, Figure 1 in Fu & Wu 2024) contradicts their own motivation in Equation (4), which is the Taylor expansion at since there quadratic curve hetween E [0. o).
24

---

Published as a conference paper at ICLR 2025
conditions, the same conditions which Prodigy and D D-adaptation proven to converge. We note that, similar to the proof of Newton's 's method, we also need to bound the third order derivative and GeN enjoy the quadratic convergence rate.
Theorem 1. For convex and G-Lipschitz loss L, assuming H(x) * Ova (i.e. no completely flat point), then GeN-GD 3.2 with g = G gives
W1++1 w+ll Mlww; - w.
and
L. S G w; - w. 1 GM2 - w.ll
where w. is the minimum of L, M = sup, ||{( sup, (x))l and k. the third order derivative of L. Furthermore, if Ml w.ll < 1, then we have the quadratic convergence w; - w, as + oC.
Proof. Denote e, wt w. then
GG
GG T
W++1 wt
ct+1 = C: HTGH. e.+-9
G HG
Taylor expansion on the gradient at w. leads to
G(w.) = G(w,) H(w,)e + K(Et)leree:
where G(w.) 0 e: Fd and k(&) ((E) VH(&:) dddddd is the third-order remainder. We have denoted the directional derivative k(x)(ee = lim h(r+ H(r) Rdxd
Left-multiplinng by G.T = G(w;) gives
G, H.e, G. G. G. n&))leeee
Multiplying the generalized inverse (G, H,) gives
G. G. G. G.G.T
c--1 e:
G H.G. H.G.
By the matrix norm inequality, we obtain
|e++ll S M|
Lec the quadratic convergence in the parameter space. Furthermore, the Lipschitz condition allows the quadratic convergence in the loss space.
25


Reviews:
[{"review_id": "TalLlPyHDQ", "reviewer": "Reviewer_sP3x", "summary": "This work proposes a robust optimizer for training deep neural networks on a diverse range of tasks, covering image classification, segmentation and detection, natural language generation, and natural language understanding. The proposed optimizer, Generalized Newton (GeN), is derived by taking a second order Taylor expansion of the loss function for a given search direction and analytically deriving the optimal learning rate given the quadratic approximation along this search direction. It generalizes the Newton method by allowing the search direction to be produced by any stochastic first-order optimization method (e.g., SGD or Adam). The derived learning rate requires the computation of Hessian-vector products and gradient-vector products. The proposed GeN implementation estimates these Hessian-vector products and gradient-vector products by using two additional forward passes, fitting a quadratic to the three points in the graph of the loss function, and then computing the learning rate analytically.", "questions": "Please see above.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Clarity: The proposed method is conceptually simple.\n2. Clarity: The paper is relatively clear and well written.\n3. Quality: Diverse range of experiments on relatively larger neural networks (e.g., RN-152 and ViT-L)\n4. Significance: Promising numerical results on the considered task suggest that the method may be of practical use.\n5. Significance: Good discussion of limitations and the added computational complexity, as well as strategies for mitigating these (e.g., infrequent computation of the learning rate, and tracking an exponential moving average of the computed values).", "weaknesses": "There are some weaknesses to be addressed in the experiments and the related work.\n\nExperiments:\n1. Why are the vision models on image classification tasks only trained for 5 or 10 epochs? It is common to use much longer training schedules for CIFAR10/100/iNat/ etc.\n2. The loss in Figure for the RN18 trained with GeN-SGD exhibits a step-wise learning rate decay, which is strange since the proposed method cannot produce step-wise decay due to the strong EMA smoothing of the learning-rate in Alg.1. Please fix this or clarify.\n3. The segmentation/detection experiments are not clear. Are you training on Penn-Fudan or COCO? What are you evaluating on? Are there pretrained components to your model or the neck/head? What are the 5 losses you're using?\n\nRelated work is relegated to a small discussion in the appendix and is lacking much many obvious references, including stochastic newton and other stochastic second-order or sketching methods. The comparison with D-Adaptation is also lacking in the main text and the experiments (except Figure 8, but here all models are only trained for 5 or 10 epochs as well).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HYtaFmXB2I", "reviewer": "Reviewer_EqmY", "summary": "This work proposes a new method of step size selection algorithm that is computationally efficient and can be combined with the descent direction provided by any off the shelf optimizer. The authors find a good step size by using gradient and Hessian information to find and fit a quaratic function of the step size that can be approximatly minimized analytiacally. They use a computationally efficient approach that does not require additional backward passes or Hessian vector products, as opposed to typical attempts that require relativly expensive power iteration or trace estimation. The authors then benchmark this method on several different tasks  ranging from large  language  models to convex functions. While the method is slightly more expensive than vanilla step size  schedules, it outperforms other methods on most benchmarks.", "questions": "- When you find the step size by minimizing the quadratic, do you ensure that the step  is actually a good one? Given the highly nonconvex and nonsmooth nature deep learning loss surfaces I would be concerned that you could get unlucky and the minimizing step size would actually significantly increase the loss (i.e. the interpolating points happen to have low loss values but any point on a convex combination between them has a high loss).\n- Given that the solution to the quadratic $\\eta^*$ should be optimal, what is the motivation for instead taking an exponential moving average of learning  rates? While  it is mentioned that it   helps in C.3, is the instability prohibitive  if you just use $\\eta^*$? If so is there a reason why?\n- Could the authors be more clear on the connections between minimizing a quadratic defined by $\\ge3$ points  and the finite differencing schemes discussed in appendix  A.1 and A.3?  It seems to me  that A.1 and A.3 are not actually  referenced in the  main text aside from a  justification for minimizing  error  in the step size chosen. The connections between these methods could be clarified, especially for an ML audience that is typically very averse  to anything involving  finite differences. It was  additionally  unclear  to me why the  scheme involving $L_-,L_0,L_+$ is equivalent  to minimizing equation 2.4 until reading A.3, so perhaps mentioning this earlier would be beneficial.\n- Is there any way to  measure  the estimation of   error that the proof in A.4 addresses? Central limit theorem  arguments can be very  loose at times  especially in situations without a large batch size (perhaps this is why some experiments required a larger than usual batch). Is it possible to show the error on models that are  small enough to actually compute $\\eta^*$? \n- Could the authors clarify how many  points they sample to form the quadratic? In Algorithm 1, three points are used, in appendix C.2 5 is reccomended, and in Figure 2 there  appear to be 11 and 10 for the ResNet and GPT2 respectivly. Given this is one of the more important and expensive hyperparaemters, I would be interested to know the sensitivity and if results would differ significantly for fewer/more  points. \n- When comparing to other algorithms, such as in Figure 8, are the hyperparemters for those algorithms/schedules tuned or taken from other  works using these configurations?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "I think this is an interesting approach that attempts to bridge older ideas in optimization (subspace optimization, quadratic interpolation) with the modern challenges of deep learning. The method is well motivated from an optimization  perspective and converges under the typical assumptions (smoothness, convexity). One of the key advantages  of this method is that it is more computationally efficient than other second order information type methods, which is paramount for adoption by those training big models (which is most people these days).  The authors are honest about what extra compute is required when and how the additional costs can be  minimized.\n\nThe presentation of this method has a few difficulties (addressed below) but overall is fairly clear, I particularly think Figure 2 summarizes the idea well. The resulting algorithm is also fairly simple and  would not be a challenge to implement or modify. I additionally like the experiments showing that the method is able to correct for poor initial guesses at a step size. To test the algorithm the authors use a very wide  array of tasks and models which is  helpful. I particularly like the choice of using test functions which offer more insights into the dynamics of various algorithms and step sizes prior to training large models, it’s a cheap experiment that can offer  more insight despite being less useful in practice than deep models. \n\nOverall I think this is an interesting idea that is mostly presented well and has a diverse set of experiments showing strong performance.", "weaknesses": "While minor I do feel some of the notation is confusion, for example using bold capitals for both vectors and matricies such as the gradient $\\mathbf{G}_t$ and Hessian $\\mathbf{H}_t$ in equation 2.2. Another example is in equation 3.2, which like the ratio of two quadratic forms when really its an inner product scaling the gradient in the numerator and a quadratic form in the denominator. It may be better to stick to typical notation for the gradeint like  $\\nabla L$ or at the very least use a lower case letter.\n\nMy concern regarding the algorithm itself is that I do not see a step to actually verify that the learning rate chosen in combination with the diretion ends up with a descent direction. This would be a simple thing to fix, but would require some (small) extra computation. More classical methods like Armijo line searches are guranteed to decrese the loss, where it appears here that the algorithm is very reliant on the loss being locally quadratic enough such that the loss between the samples points used to form the quadratic does not increase drastically then go back down. Given the empiracle performance of the algorithm it’s unlikely this actually happens, but I don’t see why it couldn’t. \n\nThe algorithm appears to perform well frequently, but is not always optimal. While I don’t think its reasonable to expect a new algorithm to  be universally best, it would be nice  to see some thoughts on why it underformed in the instances it did.\n\nTypos:\n\nOn line 208 should it be “we apply gradient descent” rather than “we apply the gradient descent”?\n\nline  842, the grid has $C10^{-k}$ followed by $k=-5,\\ldots,0$. I’ll assume this is a typo rather than having learning rates around $10^5$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5Zq0OS1NXw", "reviewer": "Reviewer_ACRL", "summary": "This paper proposes an adaptive learning-rate scheme based on a local quadratic approximation of the loss function during optimization. By approximating the loss as a locally quadratic function of the learning rate along some descent direction, the optimal learning rate can be easily computed. The authors show that this scheme is successful for a wide range of descent directions derived from other optimization algorithms.", "questions": "I cannot recommend that the paper be accepted in its current form. The proposed method is presented as a novel contribution despite it existing in the literature for at least four years --- and related methods have been used in adjacent fields for longer. The new experiments provide an updated evaluation of this technique that might spur the community to consider using it. However, the paper would require a significant rewrite to reposition itself.\n\nIt would be interesting to see how the approximation error compares to other approaches like QLAB [1] or ADLER [2] that utilize a first-order and second-order solution to the local quadratic approximation. Intuitively, these techniques should achieve a lower approximation error.\n\n\n[1]: \"QLABGrad: a Hyperparameter-Free and Convergence-Guaranteed Scheme for Deep Learning\", Fu & Wu. 2023\n\n[2]: \"ADLER - An efficient Hessian-based strategy for adaptive learning rate\", Balboni & Bacciu. 2023\n\n\n-----\n\n**Post-rebuttal** \n\nThe authors addressed my concerns regarding novelty and have provided a revised version that gives credit to the related work --- most prominently the LQA method of Zhu et al. that implements the same Algorithm 1 with SGD updates. The authors also provide greater emphasis on the curve-fitting approach they introduced that allows greater than 3 loss evaluations to be used in estimating the optimal learning rate.\n\nOverall, I feel that the curve-fitting approach is an interesting add-on but not a prominent part of this submission --- the authors primarily use Algorithm 1 which uses only three points as in LQA. And, I maintain that the LQA algorithm introduces most of the key methodological ideas from this work (quadratic interpolation for adaptive learning rate selection). However, this work includes some novel algorithmic components, a thorough empirical evaluation against modern deep learning benchmarks, and some novel theoretical analysis to help justify the method.\n\nOn balance, I have increased my score to reflect the improvements to the submission and recommend acceptance.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "To my knowledge, all derivations are correct for the proposed method.\n\nIncluding a discussion and short theoretical analysis of the approximation error is valuable too. This provides useful insight on when the method is most likely to be successful (at larger batch sizes).\n\nThe paper includes a diverse set of experiments using modern deep-learning architectures. The performance of the proposed method remains competitive with tuned learning rate schedules across all tasks. There is improved performance in settings where AdamW has likely been less aggressively tuned, but other methods do outperform the proposed techniques in some tasks --- I think this is quite reasonable given the ease of implementation and lack of tuning required for GeN.", "weaknesses": "The major weakness of this paper is that the proposed method is not novel. This technique has been used before within the optimization literature and has even been applied to deep-learning optimization problems. The clearest direct reference is [1], which uses this technique exactly. These techniques are also closely related to quadratic interpolation which has been studied within the optimization literature [2]. QLAB [3] is another method that applies the two-point quadratic interpolation approach (instead of the 3-point zeroth-order method).\n\nAnother missing related work is [4], which proposes a computationally efficient solution to Equation 2.3 directly using Hessian-vector products.   The authors should compare with this work to determine the relative change in wall-clock time to achieve a threshold loss.\n\nOverall, this constitutes a significant oversight in the placement of this work among the rest of the literature. Several claims made in the paper, e.g., \"To our best knowledge, GeN is the first automatic optimizer that is applicable to the general optimizers\" are overly strong even without the related work that I have introduced here --- adaptive learning rate methods are a well-studied area.\n\nAs a secondary point, I found it highly confusing to refer to this method as \"Generalized Newton's Method\" when there is no second-order computation. The proposed method applies a local quadratic approximation to choose a learning rate adaptively. It can be combined with a second-order preconditioner, but as it stands this technique is not related to Newton's method.\n\nThe paper can be difficult to follow at times. The derivation of the optimal learning rate should be laid out more clearly (as it is in the original works). For example, you could write down how the quadratic equations are combined to compute the coefficients. And then the form of the optimal learning rate in terms of these coefficients, before the final derivation shown in Eq. 3.3.\n\nI felt that the DCGAN experiments in the appendix added little to the paper. The final generation quality is quite poor, and it isn't clear that a quadratic approximation to the loss is suitable for this bilevel optimization problem. That said, it is interesting that it works somewhat.\n\n[1]: \"Automatic, Dynamic, and Nearly Optimal Learning Rate Specification by Local Quadratic Approximation\", Zhu et al. 2020\n\n[2]: https://people.math.sc.edu/kellerlv/Quadratic_Interpolation.pdf, Vandebogert. 2017\n\n[3]: \"QLABGrad: a Hyperparameter-Free and Convergence-Guaranteed Scheme for Deep Learning\", Fu & Wu. 2023\n\n[4]: \"ADLER - An efficient Hessian-based strategy for adaptive learning rate\", Balboni & Bacciu. 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Hz3isciX9V", "reviewer": "Reviewer_8bV8", "summary": "This paper introduces the Generalized Newton’s Method (GeN), a second-order optimization technique designed to dynamically adjust the learning rate for optimizers like SGD and Adam without manually tuning hyperparameters. The proposed method integrates Hessian information to select an optimal learning rate for each iteration, improving convergence speed with minimal computational overhead. Extensive experiments demonstrate that GeN achieves performance comparable to SOTA optimizers with carefully tuned learning rate schedules.", "questions": "1. **Figure 2:** The concept of $g_t^{\\text{optim}}$  in the illustration is unclear. It would be helpful to clarify which optimizer (SGD?) is used in this figure. Can you add a brief explanation of in the figure caption or main text, specifying which optimizer it refers to ?\n\n2. **Figure 4:** We can see training instability with sudden changes in curvature. Surprisingly (for me), ResNet-152 has a worse train accuracy than ResNet18 for GeN-SGD but not for GeN-AdamW. It would be better to run the same experiments with basic SGD and AdamW for comparison. The test loss for ResNet-152 appears quite unstable at the beginning of the training process.\n\n3. **Line 311:** For a more precise discussion about the forward/backward complexity  $B \\approx cF$ , consider referring to the paper “On the Complexity of Nonsmooth Automatic Differentiation” by Bolte et al. (2023). You also have \"Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation\" by Griewank et al. (2008), or the Bauer-Strassen theorem. The constant  $c$  is approximately 5 (in my knowledge), which might improve the relative speed estimation. A more detailed discussion on this point would be valuable. Moreover, could you give more insights into the sentence “GeN optimizers are roughly 60% as fast as the base optimizers”? Please, can you : \n- Incorporate the suggested references into their discussion of forward/backward complexity.\n- Clarify how they arrived at the 60% speed estimate and how it might change with the more precise constant c ≈ 5.\n- Provide a more detailed explanation or derivation of the relative speed calculation.\n\n4. **Figure 6:** Perhaps use 1000 iterations for Plot 3 to improve comparability? The same suggestion applies to Figure 7. Additionally, what happens if a different initialization for  $x_0$  and  $y_0 $ is used? Is it robust? Please, can you :\n\n- Update Figures 6 and 7 to use 1000 iterations for all plots for better comparability.\n- Conduct and report results from experiments with different initializations to demonstrate the robustness of their method.\n\n5. **Figure 8:** The number of iterations is unclear—10,000 iterations correspond to 5 epochs? From my experience, practitioners use 200 epochs to achieve over 95% test accuracy for Adam (or AdamW) with ResNet on CIFAR10. Did you use pre-trained models? In addition, was a learning rate of  $1e^{-4}$ used for AdamW on ResNet-CIFAR10? If so, I recommend a grid search for the learning rate, as the literature (e.g., Prodigy or D-Adaptation) often uses  $1e^{-3}$. It is also unclear whether Figure 8 shows training from scratch or fine-tuning. Finally, including results for ImageNet trained from scratch would be interesting.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. **Approach:** The paper presents a novel way to integrate second-order information into optimizers like SGD and Adam which is a significant improvement over traditional first-order methods. The method is generalizable to different optimizers and models, making it versatile and easy to adopt.\n\n2. **Computational efficiency:** GeN claims to achieve better convergence without more computational overhead, particularly useful for large-scale models. \n\n3. **Extensive experiments:** The empirical results on diverse datasets (ResNet, GPT, etc.) provide robust evidence that GeN performs well across various tasks. \n\n4. **Theoretical:** The paper gives a convergence analysis of GeN, including error analysis for optimal learning rate estimation and an in-depth explanation of the second-order Taylor expansion.", "weaknesses": "1. **No GitHub repository:** At this day, there is no open-source implementation provided. \n\n2. **Plots:** Several plots (such as Figures 1 and 8) could be improved. For example, in Figure 8, placing the legend below the figures would enhance clarity, especially since they share the same optimizer legend.\n\n3. **Computational overhead:** While the paper claims minimal overhead, the two extra forward passes in the training loop may introduce non-trivial complexities in practical implementations, especially on large distributed systems. A more detailed discussion or experiments about this could strengthen the paper. For example, replace the number of iterations by the training time.\n\n4. **Tuning hyperparameter:** It is unclear how authors chose hyperparameters for AdamW, SGD, etc… A grid search experiment or reference to the literature could strengthen the paper. Providing more details on the tuning process would enhance the reproducibility of the results.\n\nWhile this paper presents a highly interesting and innovative approach with GeN, its main weakness lies in the experimental section. The experimental results are promising but lack rigor in the precise description of the setup, particularly regarding training parameters and whether the models were pre-trained or not. Additionally, the paper would benefit from a more comprehensive discussion of related work, especially in the context of parameter-free methods (for e.g Francesco Orabona and Tatiana Tommasi. Training deep networks without learning rates through coin betting. 2017. and others papers…) would strengthen the theoretical and practical positioning of GeN. Addressing these gaps in the experimental setup and related work would significantly enhance the impact of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)