DIMENSION-REDUCED ADAPTIVE GRADIENT METHOD
Authors: Jingyang Li
Pan Zhou
Kuangyu Ding
Kim-Chuan Toh
Yinyu Ye
Venue: Submitted to ICLR 2023 (2023)
Keywords: Deep learning optimizer

Abstract: Adaptive gradient methods, such as Adam, have shown faster convergence speed than  SGD across various kinds of network models. However, adaptive algorithms often suffer from inferior generalization performance than SGD. Though much effort via combining Adam and SGD have been invested to solve this issue, adaptive methods still fail to attain as good generalization as SGD. In this work, we proposed a Dimension-Reduced Adaptive Gradient Method (DRAG) to eliminate the generalization gap. DRAG makes an elegant combination of SGD and Adam by adopting a trust-region like framework. We observe that 1) Adam adjusts stepsizes for each gradient coordinate according to some loss curvature, and indeed decomposes the $n$-dimensional gradient into $n$ independent directions to search, in which each direction inherits one coordinate element from the gradient and sets the remaining coordinate positions as zeros; 2) SGD uniformly scales gradient for all gradient coordinates and actually has only one descent direction to minimize. Accordingly, DRAG reduces the high degree of freedom of Adam and also improves the flexibility of SGD via optimizing the loss along $k\  (\ll \! n)$ descent directions, e.g. the gradient direction and momentum direction used in this work. Then per iteration, DRAG finds the best stepsizes for $k$ descent directions by solving a trust-region subproblem whose computational overhead is negligible since the trust-region subproblem is low-dimensional, e.g. $k=2$ in this work. DRAG is compatible with the common deep learning training pipeline without introducing extra hyper-parameters and with negligible extra computation. Moreover, we prove the convergence property of DRAG for non-convex stochastic problems that often occur in deep learning training. Experimental results on representative benchmarks testify the fast convergence speed and also superior generalization of DRAG.

Under review as a conference paper at ICLR 2023
DIMENSION-REDUCBI METHOD
ADAPTIVE
GRADIENT
Anonymous authors Paper under double-blind review
ABSTRACT
Adaptive gradient methods, such as Adam, have shown faster convergence speed than SGD across various kinds of network models. However, adaptive algorithms often suffer from inferior generalization performance than SGD. Though much ef- fort via combining Adam and SGD have been invested to solve this issue, adaptive methods still fail to attain as good generalization SGD. In this work, pro- posed a Dimension- Dimension-Reduced Adaptive Gradient Method (DRAG) to eliminate the generalization gap. DRAG makes elegant combination of SGD and Adam by adopting a trust-region like framework. We observe that 1) Adam adjusts stepsizes for each gradient coordinate, and indeed decomposes the n-dimensional gradient into n independent directions to search; 2) SGD uniformly scales gradient for all gradient coordinates and actually has only one descent direction to minimize. Ac- cordingly, DRAG reduces the high degree of freedom of Adam and also improves the flexibility of SGD via optimizing the loss along (< n)) descent directions, e.g. the gradient direction and momentum direction used in this work. Then per iteration, DRAG finds the best stepsizes for & descent directions by solving trust- region subproblem whose computational overhead is negligible since the trust- region subproblem low-dimensional, e.g. = 2 in this work. DRAG is com- patible with the common deep learning training pipeline without introducing extra and with negligible extra computation. Moreover, we prove the convergence property of DRAG for non-convex stochastic problems that often cur in deep learning training. Experimental results on representative benchmarks testify the fast convergence speed and also superior generalization of DRAG.
INTRODUCTION
SGD (Robbins & Monro, 1951) and its variant with momentum (Sutskever et al., 2013) are used widely in training deep neural networks. They perform well empirically and have theoretical guar- antee (Szegedy al., 2015; He et al., 2016; Lee al., 2016; Hardt al., 2016). However, SGD suffers from two issues. It often has slow convergence speed since it adopts a single learning rate for all the gradient coordinates. Moreover, it is also hard to tune the single learning rate (Wilson al., 2017), since not all gradient coordinates share the same optimization properties.
To resolve this problem, several adaptive gradient methods have been proposed to adopt different learning rate for different gradient coordinates. Typical examples of such methods include Adagrad (Duchi et al., 2011). RMSProp (Tieleman et al., 2012), and Adam (Kingma Ba, 2014). Emprically, these methods have shown faster convergence speed and eased the burden of carefully tuning the learning rate SGD across many kinds of networks. However, their generalization performance are often worse than SGD in many scenarios (Wilson et al., 2017; Zhou et al., 2020).
Some algorithms are proposed to combine the fast convergence speed of adaptive gradient methods and good generalization performance of SGD. Instances of this type of algorithms include SWATS (Keskar & Socher, 2017) which automatically switchs from Adam to SGD, ND-Adam (Zhang et al., 2017) which utilizes vector learning rate and normalization to control direction and stepsize, and AMSGrad (Reddi et al., 2018) which maintains a monotone increasing second moment. Unfortu- nately, these methods only slightly bridge the generalization gap between SGD and Adam, but does not attain as good generalization performance as SGD, needless to say the ofate-of-the perfor- mance test set. Accordingly, these algorithms are rarely used to train deep networks in practice.

---

Under review as a conference paper at ICLR 2023
To combine the merits of Adam and SGD, i.e fast convergence speed in Adam and excellent gener- alization in SGD, we proposed Dimension- Reciicdd Adaptive Gradient Method (DRAG for short) which minimizes the loss from several descent directions to trade-off the whole space search in Adam and the minimization along a single gradient direction in SGD. For Adam, adjusting stepsizes for each gradient coordinate actually transforms the n-dimensional gradient into independent di- rections to optimize, in which each direction inherits one coordinate element from the gradient and sets the remaining coordinate positions zeros, In contrast, SGD only uses a single learning rate for all gradient coordinates and minimizes the loss along one descent direction. Though the adaptive learning rate for each coordinate shows faster convergence speed than a single learning rate for all coordinates, shown in many works (Wilson et al., 2017; Zhou et al., 2018). it also leads to the inferior generalization in Adam, since minimizing n independent directions means searching the whole parameter space and could results in overfitting. So it is natural to trade-off the number of descent directions.
To this end, motivated by DRSOM (Zhang et al., 2022), we update the parameters along the gradient direction and momentum direction through a trust-region-like approach, which greatly reduces the high adaptivity of Adam while adding flexibility to SGD. At each iteration, DRAG searches for the optimal update along the gradient and the momentum which are widely used in accelerated algorithm (Polyak, 1964; Nesterov, 2003) by solving a two-dimensional trust-region subproblem to find the best stepsizes for these two directions. For the trust-region subproblem, we use a quadratic approximation to estimate the loss with the Hessian matrix estimated by the second moment in Adam which is diagonal matrix and can greatly reduce the computational cost. Moreover, we heuristically design simple and effective trust-region radius for the subproblem. Despite the delicate design of our algorithm, we also theoretically prove that on non-convex problems, our DRAG can converge and enjoys stochastic gradient complexity of Oc=")) to find an c-approximate first-order stationary point. To summarize, our contributions are as follows:
We proposed the DRAG algorithm to optimize the loss from several descent directions for balancing the whole space search in Adam and the optimization along a single gradient direction in SGD. Moreover, we formulate the optimum stepsize search for these descent directions into a low-dimensional trust region problem whose computational cost is negli- gible when compared with the vanilla cost in adaptive gradient algorithms.
We theoretically prove that to find an e-approximate stationary point on non-convex stochastic problems, DRAG has the stochastic gradient complexity of O(E=A) which matches the lower bound ((e=4) in (Arjevani et al., 2022) under the same non-convex optimization setting.
Experimental results show that on several representative benchmarks, our DRAG method can achieve faster convergence speed than SGD, and also state-of-the-art generalization performance.
2 RELATED WORK
Adaptive gradient methods, e.g. Adam (Kingma & Ba, 2014), Adagrad (Duchi et al., 2011), and R.Sprrpp (Tieleman et al., 2012), adopt different stepsizes for different gradient coordinates so as to boost training process. Although Adam and its variants are used widely for training deep neural networks, their poor generalization performance makes SGD still dominant in some areas, such as training CNNs (He et al., 2016). Many researchers tried to improve the generalization capacity of Adam, including SWATS (Keskar & Socher, 2017) which conducts automatic switch from Adam to SGD training strategy, ND-Adam (Zhang et al., 2017) which controls the stepsizes and update direction in more precise way, AMSGrad (Reddi al., 2019) which ensures monotone increasing second moment, and Padam (Chen et al., 2021) which introduces a partially adaptive parameter control the adaptivity of stepsizes. Our solution to improve the generalization performance is to confine the update of parameters to two- woo-dimensional subspace of the parameter space. Specifically, we solve trust-region subproblem determine the optimal stepsizes along the gradient direction and momentum direction at each iteration.
The idea of utilizing gradient and momentum direction to update the variable traces back to Polyak's heavy ball method (Polyak, 1964)
2t F4-1 0: (x;-1)) + a:24-11
2

---

Under review as a conference paper at ICLR 2023
SGD (with momentum) (Sutskever et al., 2013) also be written in this form after replacing the gradient direction f with stochastic gradient direction 9t-1- Unlike SGD which adopts constant stepsizes, DRAG adopts the stepsizes as the solution of two-dimensional quadratic model with a spherical constraint, it adaptively learns the optimal stepsize for each direction.
Trust-region method has been widely used in optimization, and some works tries use it for ma- chine learning (Martens et al., 2010; Dudar et al., 2017: Erway et al., 2020). The closest related work the Dimension Reduced Second Order Method (DRSOM) proposed by Zhang et al. (2022). It uses a finite difference method to approximate the Hessian-vector product arisen in the trust-region sub- problem and achieves higher convergence rate than first order methods. However, difference method is inaccurate in high-dimensional problem, and it introduces huge extra computational overhead. Our method DRAG, on the other hand, approximates the Hessian directly by the second moment of stochastic gradient directly. It reduces extra product in DRSOM and captures curvature information more accurately. Moreover, DRAG adopts a heuristic trust-region radius, making the algorithm compatible with dominant deep learning training pipeline without introducing extra hyperparameters.
loops to calculate the Hessian-vecton
METHOD
Training neural networks can be seen as solving the following non-convex optimization problem
min f(x),
(I)
where is the loss function and R" the variable. Among all optimizers. Adam (Kingma & Ba, 2014) is one of the most popular algorithm to solve problem (1), At each training iteration, Adam maintains exponential moving average (EMA) of first and second moments of stochastic gradient Vs and as
=, + -1))9:11 U. -2 (1 111-8331 -2)
where 81 [o, 1] are constant and -t-1 (xx,-) is the stochastic gradient. It adaptively scales the learning rates for each gradient coordinate, and actually minimizes the loss function along descent directions
0: 32 -z- 1) Vūe + -
Cr
a
U + (o),)
7
where ú, ú, are bias-corrected vr, u4 e, is the standard basis vector with for dimension i and O for all other dimensions. Specifically, Adam adopts a stepsize of Ver,+tv
for the i-th gradient
descent direction ,,,
While adaptive stepsize boosts the convergence of Adam, it weakens the generalization performance due to noise and overfitting. In contrast, SGD generalizes well because uses a single stepsize for all gradient coordinates and indeed optimizes the loss function only along the gradient direction. One interpretation for their different generalization performance is that Adam's 's update direction no longer falls into the subspace spanned by all stochastic gradients span 2017; Zhang et al., 2017). while SGD do. Actually, Wilson et al. (2017) proved that on binary classification problem, SGD converges to the max-margin solution because its update each step is linear combination of stochastic gradients, while adaptive gradient methods converge to solutions that generalize poorly because adaptivity makes the algorithm susceptible noises and therefore causes overfitting.
. (Wilson al.,
To overcome the issue just mentioned, our DRAG algorithm optimizes the loss function (1) from the gradient direction and the momentum direction. It maintains flexibility in the update direction while inheriting the generalization capacity of SGD. At each step. it searches for the optimal step- sizes along these two directions by solving two-dimensional trust-region subproblem. Therefore, from the optimization perspective, it conducts the optimal update within the two-dimensional sub- space spanned by gradient direction and momentum direction. Moreover, while DRAG adopts the trust-region framework, it is compatible with the dominant deep learning training pipeline without introducing extra hyperparameters.
3

---

Under review as a conference paper at ICLR 2023
3.1 DETAILS OF THE ALGORITHM
Details of our algorithm are described in Algorithm 1. At each training epoch, DRAG first computes stochastic gradient Ir-1, and it to update the first moment o, and second moment u, of stochas- tic gradient like Adam. Then, we introduce the bias-corrected second moment de to approximate the Hessian. In this way, DRAG constructs the trust-region subproblem in line 9 of Algorithm 1. While solving this trust-region subproblem in nigh-dimensional parameter space is computational expensive, DRAG solves it in the two-dimensional subspace spanned by bias-corrected first moment direction é, and momentum direction 1 making the computational overhead negligible. Here we intuitively set the trust-region radius as 7 öell. and the benefits of this setting is described in Section 3.2. After calculating the solution 1z and 022 of the subproblem, we get an optimal update = ai + azy - in the wo--dimensional subspace. Finally, we follow (Loshchilov & Hutter, 2018) and conduct a decoupled weight decay step. This is the overall framework of our DRAG.
Algorithm Dimension Reducce Adaptive Gradient Method (DRAG)
1: Input: Total number training epoch m, learning rate y, exponential moving average coeffi- cients 31, B2, weight decay scale 7, margin coefficient v.
2: Initialize: Set æi Do = 0, uo = 0.
3: fo 1, m , do
4: Compute stochastic gradient -:1 (.)
5: Dt = 310-1 + - 31 111))1111 0; = 02/(1 (1- -
6:
u, 32 + (1 32)gr-11 Ur ue/(1 -1))
7:
H. diag( v Vü + 1/)
8:
d-1 -1-1 -t-2 if 2 else di O.
9:
(an:: 02)) = argmin, p (0., p) + 2 (p. H.P) ||ll| S m/l p -a00 a2d411)
10:
It It-1 a110; + d--
11:
It = x; -- (Conduct weight decay)
12: end for
13:
Output: 21, Im
The only extra computational overhead of DRAG compared with Adam is solving the two- dimensional trust-region subproblem in line 9 of Algorithm 1. The trust-region subproblem can be formally formulated as follows:
1 + (-a16;
min a1,0g
(6,, - a1 + +02d-111
+ 12d 0z + a2dh-1) 1))
2
b 0t 0, -1
1
6 H
of H,d-1
a1
= [ai 02l
+
[ai a2]
2
o7 Hid
di, H
02
s.t. || - 0: ú, + a2d1
S n//6,
where H, = diag(v ū. + v) as defined in Algorithm 1. This two-dimensional subproblem can be solved efficiently by using global minimal condition. In Appendix A, we transform this subprob- lem into a standard trust-region subproblem, and then an e-global primal-dual solution satisfying KKT condition can be found in Ollog log(?)) time (Luenberger et al., 1984). See more details in Appendix A.
we set p in line of Algorithm
p aaa 0, + Σ k-1
j=1 ajj1dh-j
our algorithm DRAG can be generalized to solve the subproblem with any A search directions. Al- though according to experimental results, one search direction or multiple search directions usually perform worse than two search directions (DRAG), they can give us some intuitions on the flexibility of our method and the optimality of its update in the subspace. We omit v in the discussions below for the simplicity of notation.
One-dimensional subspace spanned by gradient direction
Suppose we update the variable in the onc-dimensional subspace
c; Ft-1 Or11 St.
4

---

Under review as a conference paper at ICLR 2023
where are is calculated by solving the trust-region subproblem
1 min { (0t, ai + 2 2 diag(v (.)(-a)0)))))) lail - m)
In this case, the subproblem has an explicit solution air min (r..diag(/v.))::) As we can see from the solution, unlike SGD which adopts the learning rate set externally as the stepsize, our algorithm update the parameter with an adaptive stepsize within the learning rate. Furthermore, this adaptive stepsize is optimal according to the quadratic approximation of the loss function.
(#),
Full-dimensional parameter space whole parameter space
Suppose we update the variable along n directions in the
2t xz-1 +
Then trust-region subproblem becomes
min (.t, p) + (p, diag( v (:) IPell s mllldel
2
Under this scenario, the subproblem has solution
p v ús + X
Σ
Ur. + X (i),
1
where À 2 satisfies A(Ippl n/ (+ll = When By S dell x = 0 and the solution the same as Adam's update direction (2). From the form of solution, we can see all gradient coordinates have adaptive stepsizes. which means the method optimizes the loss function along directions in the whole parameter space. Also, this update is optimal with respect to the quadratic approximation of the loss function.
/u,
3.2 BENEFITS OUR ALGORITHM
Flexibility of update As in Algorithm 1, DRAG updates the variable æ along EMA of gradient direction ú, and momentum direction 1- This update direction choice acts trade-off between the whole space search of Adam and one direction search of SGD. Specifically, Adam adjusts step- tu, (bt, while SGD uniformly
sizes for each gradient coordinate as Ft = 2t-1 Σ
scales each coordinate of the gradient as -t-1 r/ū: DRAG, on the other hand, search along two important directions as e, Φt- Q, + dz This choice maintains the flexibility of update direction while alleviating overfitting and excessive noises.
Moreover, the update of DRAG lies in the subspace span d(-1) gp.. This means that the parameter update direction is always combination of stochastic gradients. Accord- ing to Wilson et al. (2017), this property makes DRAG always converge to the max-margin solution of the binary classification problem, which has the best generalization capacity. This helps to explain DRAG's excellent generalization performance in practice.
Optimal stepsizes DRAG solves the dimension-reduced subproblem at each training epoch and finds the best update along the gradient direction and momentum direction. This optimal update is evaluated by the quadratic approximation to the loss function, where the Hessian approximated by second moment Vū, and gradient is approximated by first moment ú, Since DRAG conducts optimal update along gradient and momentum direction within the learning rate we set, it converges faster than SGD training dataset and is comparable with adaptive gradient methods.
Heuristic trust-region radius We set the trust-region radius for the subproblem as v/]l,,]| |l. The intuition is that when gradient is large, we hope our algorithm can make a larger step minimize the loss function significantly. While when gradient is small, we hope our method to be stable and don't 't change the parameters too much. This heuristic design not only frees us from changing the radius at each step trust region method does, but also make our algorithm compatible well with dominant deep learning training pipeline without introducing extra hyperparameters. Other deep learning optimizers that adopt trust-region like framework, such as the Hessian-free optimization method (Martens et al., 2010), L-SSRI-TR (Erway et al., 2020), DRSOM (Zhang et al., 2022) introduced extra hyperparameters and may ineur high extra computational overhead. From our knowledge, this is the first time that a trust-region like method well-compatible with dominant deep learning training setting without extra hyperparameters.
5

---

Under review as a conference paper at ICLR 2023
4 CONVERGENCE ANALYSIS IN NON-CONVEX STOCHASTIC OPTIMIZATION
For the analysis of stochastic non-convex algorithm, we follow the works Zhuang et al. (2020); Guo et al. (2021) and make the following necessary definitions and also mild assumptions.
Definition 1. For differentiable function f, x: is said to be an e-approximate first-order stationary point if satisfies [[](( S c.
Definition 2. For differentiable funtion f(z). it is called L-Lipschitz smooth if it statisfies [VV(()) - V f(y)ll & L|| - yll for a constant >> and any x. y in domain of f-
Based on these definitions, we have the following assumption. Assumption 1. For non-convex problem minzeR= f() assume the loss ((x satisfies
f is L-Lipschitz smooth.
The gradient estimation g is unbiased, namely Elgd = f((z), and its variance can be bounded as Ellgg. V [(x+))] S o².
Then we can derive the convergence of our proposed algorithm and also provide its stochastic gra- dient complexity to find an e-approximate first-order stationary point.
Theorem 1. Suppose Assumption 1 holds. Let Bg = B and vi for all t. Assume there exist
constants a, G > 0, such that a I minn a: and O:1e I nG, lazd S nG.. In addition, n I
(1-8)8a)
min
2LG
8GL2
96G
48LGT
192
Then, if - B S 30 and 2
max
3G, (1-8)c2 j.
oc2
30g
DRAG can achieve
T-1
T-1 Se,
t E [[V[(<))))
Σ
Σ 1=
E be S SE?,
(3)
T
t=0
where C1 = 4 - f(x
C2= 4nG and C3 = 2n ((m)) (10 (1-8)))0111
Remark 1. Theorem / with its proof in Appendix C demonstrates that by properly selecting constant trust-region radius T) and constant momentum parameter Be (correspond to /1 in Algorithm 1), DRAG can converge to an c-approximate first-order stationary point of the non-convex stochastic problem with stochastic gradient complexity (ee Note that the assumptions for att and a22 are satisfied naturally with the design of DRAG, see details in Appendix B. The complexity of DRAG is of the same order the lower bound provided by Arjevani et al. (2022). A similar complexity has also been obtained in, for example, LAMB (You et al., 2019), Adam-family (Guo et al., 2021). In the analysis of DRAG, we only need unbiased and variance-bounded stochastic gradient, without any large mini-batch sizes requirement as in LARS (You et al., 2017) and LAMB (You et al., 2019). In addition, some previous works (Luo al., 2018; Zaheer et al., 2018; Liu et al., 2019; Shi al., 2020) require the momentum parameter 3e to be very close or decreasing to zero. In contrast, DRAG requires 3, to be close to one, which is more consistent with the practice.
Theorem 2. Suppose Assumption I holds. Assume there exist constants 6, G > O, such that 0 <
8
< G.
lagal W/
G. Set Th
Cq VIt2'
1- B
Cen for for any On and C satisfying C > LV
8G
1/2
Ve+1
8
1/2
and Oy /2LG
x2
8
Then there exist two constant C₁ and C2
96G
1BLG
1921.G0
which are independent with T, such that
T-1
Ci
C2 T
T-1
8C1 vT
8C2 log T
Σ [[]V](
E
11
+
VT
VT
vT
Given a tolerance e > 0, ifT > 0 ( we have
T-1
T
Σ
E| (1x) 11
2
1
E
1 8c..
T 1=0
T

---

Under review as a conference paper at ICLR 2023
Table Top-1 test accuracy (%) of VGGI6, ResNet34, DenseNet121 on CIFARIO and CIFAR100.
DRAG
SGD
Adam
AdamW
AdaBelief
VGGT6
94.0
92.7
92.2
92.4
93.6
CIFARIO
ResNet34
95.6
94.5
93.3
94.5
95.4
DenseNet121
96.1
94.5
93.3
94.6
95.5
VGG16
72.8
69.7
62.2
68.5
72.2
CI
ResNet34
77.6
75.6
73.0
70.9
76.1
DenseNet121
79.2
77.8
73.7
74.3
78.2
Remark 2. Theorem 2 with its proof in Appendix establishes an (logTT/v)) sub-linear con- vergence rate for DRAG by choosing a decreasing Tς and 1 3, with the order O(1/ /t). Similar sub-linear convergence rates are also established by Zou et al. (2019) for Adam and Guo et al. (2021) for Adam-rype optimizers. While Zou al. (2019) has restrictions on the second moment momentum parameter 32. In Theorem 2, we only need Be (corresponds 31 in Algorithm 1) to in- crease to one.
5 EXPERIMENTS
We conduct experiments on several representative benchmarks, including VGG (Simonyan & Zis- serman, 2014), ResNet (He et al., 2016), DenseNet (Huang et al., 2017) on CIFARIO, CIFARI00 dataset (Krizhevsky et al., 2009), ResNet18 ImageNet (Deng et al., 2009), and LSTM (Hochre- iter & Schmidhuber, 1997) on the Penn Treebank dataset (Marcinkiewiczz 1994). We compare our algorithm DRAG with some popular deep learning optimizers, including SGD (Robbins & Monro, 1951), Adam (Kingma & Ba, 2014), AdamW (Loshchilov & Hutter, 2018), AdaBound (Luo et al., 2018), AdaBelief (Zhuang et al., 2020), RAdam (Liu et al., 2019), Yogi (Zaheer al., 2018), and Padam (Chen et al., 2021). Experimental results show that DRAG has faster convergence speed compared with SGD and it achieves state-of-the-ard generalization performance. We also conduct ablation study to show 1) two search directions (DRAG) performs better than one direction and mul- tiple directions and 2) DRAG is robust different learning rate schedules. At the end of ablation study, we give some advice for practitioners to use DRAG.
5.1 CNNS ON IMAGE CLASSIFICATION
We conducted experiments for VGG16 with Batch Normalization, ResNet34, and DenseNet121 on CIFARIO an CIFAR100 dataset. The experimental setting is borrowed from AdaBelief (Zhuang al., 2020) and we also their default setting for all the hyperparameters. For DRAG, choose its learning rate to be the same as SGD, which 0.1, and weight decay factor is 0.0015 for CIFAR10 and 0.0025 for CIFAR100. Other hyperparameters of DRAG is the setting (31 = 0.9, B2 = 0.999, e = 10-8). As Figure shows, DRAG has convergence speed comparable with adaptive gradient methods and it attains the best generalization performance. To be specific, DRAG obtains more than 0.5% generalization accuracy gain over AdaBelief (Zhuang al., 2020) on most tasks. The detailed test accuracy summarized in Table 1.
the default
We also train R on ImageNet under the official training setting in He et al. (2016), and compare the top-1 test accuracy of DRAG with the best result of other optimizers in the literature. Experimental results show DRAG has the best generalization capacity. Details are in Table 2.
The possible reasons for this improvement on the convergence speed and generalization capacity is 1) DRAG searches for the optimal update along two directions and thus converges faster, 2) DRAG confines the search of update within the two-dimensional subspace spanned by gradient and momentum direction to avoid overfitting and alleviating the influence of noises, therefore it generalizes better.
5.2 LSTMS ON LANGUAGE MODELING
We experimented with LSTM on the Penn Treebank dataset and record the perplexity (lower is better). We follow the exact experimental setting in Adabelief (Zhuang et al., 2020) and use their

---

Under review as a conference paper at ICLR 2023
DRAG SCD
DR4G
DRAG
SGD
111
5CD
114 ACLEEO
AJam
Adam
Adam
Astmww
Admmi
Adamii
Azabl lcf
Adaiiiol
813
015
623
813
625
Triiin 8outh
ming Spach
Traiing Spsch
(a) VGG16 on CIFARIO.
(b) ResNet34 on CIFARIO.
(c) DenseNet121 on CIFARIO.
DRAG
DRAG
DRAG
SCD
SCD
SED
Azam
Adam
Adami
AJamm
Adamii
Adamiia
Adobelie
Singe
MiBell
Traniig Eoach
ming
Spach
Thaiing Spath
(a) VGGI6 on CIFARIO.
(b) ResNet34 on CIFARIO.
(c) DenseNet121 on CIFARIO.
Figure 1: Training and test accuracy of CNNs CIFARIO 10 dataset.
Table 2: Top-1 test accuracy (%) of ResNet18 on ImageNet. All results except DRAG are reported by Zhuang al. (2020) and Chen et al. (2021).
DRAG
SGD
Adam
AdamW
AdaBound
Padam
AdaBelief 70.08
70.41
70.23
63.79
67.93
68.13
70.07
default hyperparameters except for SGD. For SGD, we use the same hyperparameters as DRAG to make a fair comparison between the two. For SGD and DRAG, we set their learning rate as 25, 75, 75 for 1,2,3-layer LSTM and weight decay factor as 2.5 10-6, SGD's generalization performance in our setting is better than the results provided by Zhuang al. (2020). As show in Figure 2, for I-layer, 2-layer, and 3-layer LSTM, DRAG's convergence speed is faster than SGD and comparable to adaptive gradient methods. From Table 3, we can see that DRAG attains more than 0.5 less perplexity than other optimizers. The fast convergence speed may be attributed to the optimal update DRAG takes and the good generalization performance may be due to DRAG's s two- direction search. The gradient direction inherits SGD's good generalization property and the extra momentum direction further improves its performance.
5.3 ABLATION STUDY
Different search directions We compare the performance of algorithms that solve the trust-region subproblem in one-dimensional, two-dimensional (DRAG), and three-dimensional subspaces as de- scribed in Section 3.1. As show in Table 4 in Appendix E, DRAG generalizes better than its one search direction and three search direction counterparts. The reason is that DRAG updates in more directions than the one search direction counterpart while its subproblem can be solved more accu- rately than the three direction counterpart, since low-dimensional subproblem can be solved with less numerical errors in single precision arithmetic by GPU.
Robustness to learning rate schedule DRAG is robust to different choices of learning rate sched- ule. Except for letting the learning rate decay at epoch 150 as in Section 5.1, we also conduct ex- periments on decaying the learning rate at epoch 120 and adopting cosine annealing learning rate schedule. The only change of hyperparameter setting from Section 5. is we increase the learning rate of DRAG from 0.1 to 0.12 in cosine annealing schedule. The intuition is that when the trust- region radius is decreased during the training process, we need a larger initial radius to converge to better local minima. We compared DRAG's 's test performance with other optimizers with VGG16 on CIFARIO 10, details are presented in Table 5 in Appendix E, which shows that DRAG enjoys the best generalization performance for all the learning rate schedules.
8

---

Under review as a conference paper at ICLR 2023
159
110
10 10
10
10
(a) I-layer LSTM.
(b) 2-layer LSTM.
(c) 3-layer LSTM.
Azam
Adam
Azum
Adami AtoBeloo
Ad18ciel
baads
27a
US
Soach
Trann
30
(a) I-layer LSTM.
(b) 2-layer LSTM.
(c) Layer LSTM.
Figure 2: Training and test perplexity of 1,2,3-layer LSTM on Penn Treebank dataset.
Table 3:
Test perplexity (lower is better) of I-layer, 2-layer, and 3-layer LSTM PTB dataset. All results except DRAG, SGD, and Padam are reported by Adabelief (Zhuang et al., 2020).
DRAG
SGD
AdaBound
Adam
AdamW
AdaBelief
RAdam
Yogi
Padam
I-layer
82.5
83.0
84.3
85.1
87.7
84.8
86.5
86.5
84.0
2-layer
65.6
66.1
67.5
67.4
72.8
66.3
72.3
71.3
66.3
3-layer
61.0
61.8
63.6
64.3
69.9
61.8
70.0
67.5
62.8
For practitioners, any task that can use SGD can use DRAG to achieve faster convergence and comparable generalization performance with negligible extra computational overhead. The user only needs to set the learning rate the same as in SGD or slightly larger. For a new task, if one values good generalization performance, one can always use DRAG instead of SGD to enjoy easier hyperparameter tunning. DRAG is more robust than SGD when large learning rate is used. For instance, when training VGG16 on CIFARIO dataset, setting learning rate 0.5 still allows DRAG to attain over 90 percent test accuracy, but SGD diverge and fail in the training process.
CONCLUSION
In this paper we propose the DRAG algorithm, which finds the optimal update of the parameters along gradient and momentum directions at each iteration. Compared with Adam, DRAG reduces the flexibility of update direction from searching in the whole parameter space to updating in two-dimensional subspace: therefore is less susceptible to overfitting and has better generalization performance. Compared with SGD, DRAG inherits the gradient update direction and also update along an extra momentum direction, thus it has faster convergence speed and comparable gener- alization capacity. Theoretically complexity as the lower bound for non-convex stochastic optimization (Arjevani et al., 2022). Ex- perimentally we show that DRAG has faster convergence speed compared with SGD and it attains state-of-the-arr generalization performance. Our algorithm can be further generalized to any number of search directions and any choice of Hessian approximation.
prove that DRAG has the same order of stochastic gradient

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pp. 1-50, 2022.
Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 3267-3275, 2021.
Deng, W. Dong, R. Socher, L. Li, K. Li, and F. Li. Imagenet: A large-scale hierarchical image database. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 248 255, 2009.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
Viacheslav Dudar, Giovanni Chierchia, Emilie Chouzenoux, lean-Christopha Pesquet, and Vladimir Semenov. two-stage subspace trust region approach for deep neural network training. In 2017 25th European Signal Processing Conference (EUSIPCO), pp. 291-2995 IEEE, 2017.
Jennifer B Erway, Joshua Griffin, Roummel F Marcia, and Riadh Omheni. Trust-region algorithms for training responses: machine learning methods using indefinite Hessian approximations, Opti- mization Methods and Software, 35(3):460 487, 2020.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms the adam family, arXiv preprint arXiv:2112.03459, 2021.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234. PMLR, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp- 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8): 1735-1780, 1997.
G. Huang, Z. Liu, L. Van Der Maaten, and K. Weinberger. Densely connected convolutional net- works. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 4700-4708, 2017.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam to sgd. arXiv preprint arXiv: 2017.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXhv:1412.6980, 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Jason Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent converges to minimizers. arXiv preprint arXiv: 1602.04915. 2016.
Liyuan Liu, Haoming Jiang. Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In International Conference on Learning Representations, 2019.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2018.
David Luenberger, Yinyu Ye, et al. Linear and nonlinear programming, volume 2. Springer, 1984.
10

---

Under review as a conference paper at ICLR 2023
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. International Conference on Learning Representations, 2018.
Mary Ann Marcinkiewicz. Building large annotated corpus of english: The penn treebank. Using Large Corpora, 273, 1994.
James Martens et al. Deep learning via hessian- free optimization. In ICM,,, volume 27, pp. 735-742, 2010.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2003.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Com- putational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference Learning Representations, 2018
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint FrXXiv:99040092.. 2019.
H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statis- tics, 22(3)4400-477, 1951.
Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. Rmsprop converges with proper hyper- parameter. International Conference on Learning Representations, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International Conference on Machine Learning, pp- 1139-1147. PMLR, 2013.
C. Szegedy, W. Liu, Y. Jia, Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Ra- binovich. Going deeper with convolutions. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 1-9, 2015.
Tijmen Tieleman, Geoffrey Hinton, et al. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161 419-449, 2017.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. Advances in Neural Information Pro- cessing Systems, 30, 2017.
Stephen Wright, Jorge Nocedal, et al. Numerical optimization. Springer Science, 35(67-68):7, 1999.
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint
2017.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXiv: 1904.00999 2019.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive meth- ods for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.
Chuwen Zhang, Dongdong Ge, Bo Jiang, and Yinyu Ye. Drsom: A dimension reduced second-order method and preliminary analyses. arXiv preprint a208 00208, 2022.

---

Under review as a conference paper at ICLR 2023
Zijum Zhang, Lin Ma, Zongpeng Li, and Chuan Wu. Normalized direction preettrvingeeeiiigggg adam. arXiv preprint arXiv: 0700.04446, 2017.
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv: 2018.
Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Chu Hong Hoi, et al. Towards theoreti- cally understanding why sgd generalizes better than adam in deep learning. Advances Neural Information Processing Systems, 33:21285-21296, 2020.
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, Xenophon Pa- pademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in Neural Information Processing Systems, 18518895-18880 2020.
Fangyu Zou, Li Shen, Zequn Jic, Weizhong Zhang, and Wei Liu. sufficient condition for conver- gences of adam and rmsprop. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11127-11135, 2019.
12

---

Under review as a conference paper at ICLR 2023
A SOLVE THE TRUST-REGION SUBPROBLEM
Recall the trust region subproblem
1 - Qua)
min
(a, Ct)
s.t.
Vlu, G.a) S 1/1/x=l:
[1
oT Dz
67 H.
07 He
where a
C.
Qt
and G.
02
oy d
di Hrbr
df_1 H
of dr-1 de-1
H. diag(v ut + v).
In order to solve this trust region subproblem, we transform it into a standard trust region subproblem with L2- Lo-norm constraint.
When matrix G, is positive definite, we have
G. = L. (Cholesky Decomposition)
VaTG,a= ((TTa)"LTa = al z n/|/,]].
So we let y = Lf'a, then Li"y and the subproblem becomes
(Ca, I u) + 1 (1= y. Q.1.+
min
s.t. |llll S nl(
min (L, v) + (w. tv, Li Qi v)
s.t. lllll S n||61||-
In this way, the trust region subproblem is transformed to standard spherical constrained quadratic optimization problem and can be solved efficiently (Wright al., 1999).
When G. 0, this means é is linearly dependent with d.-1. In this case, we solve the one- dimensional subproblem described in Section 3.1.
B How O1 Ozzz. SATISFY THE ASSUMPTIONS NATURALLY
The trust-region subproblem be solved in Algorithm has global optimality condition (Luen- berger et al., 1984) given by
(Q: + AGI) + =0
Qi +G+ - 0
XG
Alllalla, - mll 0. A20
By its construction, we know that G. is positive semidefinite. In practice, numerical issues some- times make it indefinite, leaving the trust-region subproblem insoluble. Thus, make an adjust- ment to G,
{ Gt if Amin 2 |Grl 0
G,
o.W.
where Amii is the smallest eigenvalue of Gt. this way, when |Ga * O, we have
|
||||| < ||||all,,,, I 1/|
<
E
which means
0'
0:
E
13

---

Under review as a conference paper at ICLR 2023
With the common additional assumption that stochastic gradient 9r norm, i.e.I19el|so S Goo. then o as an moving average of 9i also has bounded norm |[ Therefore, are upper bounded by constant.
fxx)) has bounded Loc
can see that 2114
O. which means di- is parallel with ět. Then we only need to find the optimal update within the trust-region along gradient direction 8G In this case, we manually set 0:2 0 in our implementation of DRAG, and then (r satisfies |an S 17-
When [G,]
From discussions above, we can see the assumption that |0y |, " are upper bounded in Theorem
and Theorem 2 is satisfied given the common assumption that stochastic gradient 9: = V (xxe has bounded Log norm. For the simplicity of notations, we directly make assumptions for air and ag in Theorem and Theorem 2.
For the assumption that a is positive and Iي is lower bounded by a constant, we give an expla- ? nation here by intuition and empirical results. Gradient direction is what we considered the most important update direction locally, because by the training pipeline of neural networks, stochastic gradients of training parameters are the new information we gain at each iteration. Thus, we consider the update should at least move towards the gradient descent direction rather than move towards the gradient ascent direction. Moreover, from the observations of die under all the experimental set- tings, Orr is always positive and zu is always larger than 0.1. Therefore, this assumption or is y reasonable based on common sense and holds true in practice.
C PROOF OF THEOREM
One key ingredient in our analysis is an existing variance recursion of the stochastic estimator based on moving average, which is given by the following lemma.
Lemma 3 (Variance Recursion (Wang et al., 2017)). Suppose Assumption holds, then we huve
E (1lle - v=(()))] S Blle, f((==1))1 2(1 - 3) Vf(=)]11 + 1, 1.211 1- B
where [-] denotes the conditional expectation with respect to all randomness before gt-
Before proving Theorem 1, we need to prove the following auxiliary lemma.
Lemma 4. Suppose Assumption holds. Assume there exist ac, 77, 8, G > 0, such that a S min, a16 max; Th S n, and 0 < ō <
< <
< G, [oai
< G. (8, G) are constants independent with t.
Then there exist positive constants C₁ C2 and C3, which are all independent with T. such that the following estimation holds:
In addition, 1) S min+
2LG 2t
1-8
V 2G
406G'
(
* (192ं
T-1
Ci Ta
C3
[[VS(>))
<
+ C2((1 3002 + T(1 B)
T 0
(4)
8C1
1 + 8C2 (1- 3)0² + 8C3
E
[1
<
T 1=0
To
T(1 - 9))
Proof. Since F is L-smooth, we have
f(1411) S f(x)) + (z:), -1174+1 + azrde) + a1r1111 + 22
2
La
La
= f(xx) an V fZ)()) az (Vf(z)) de) +
|1442
112
||dell
(1411,
2
2
=((x) | V 12 ane(1 Lane)
|0141l12 ail
[f + az oz (V:))),
La
+
[ 2|2 (1 dj).
(5)
14

---

Under review as a conference paper at ICLR 2023
By Lemma 3, we can obtain
L E -)To² + (1 (1-13)2
Σ - ue
T E (1))) e +
1 1
Taking expectation for both sides of (5) and taking summation among 0,... T combining with (6), we have
E [f(TT) - f(xo)]
G
E V - 11
+ 2(1 - -)To² + (1 (3)2
I
T
E|I|de1?
T-1
0n
V (1x))1
2
1-3
2
1=1
1=
a1e(1 - -Laie)
La
Bla2 (V dell +
||de 1 (2
de'l
2
0=
By AM-GM inequality,
0u 02 (()
[
a2t Id:1l
4
all
01e(1 Law
L L2a ||del?.
S
|ee+1 1| +
4
- Lor
Combining all together, we have
011 E f(x))l
4
Sf(zo) - -f(x*) + G
(zoo) - -211 Σ n/I.2
T
E||
2(1 -B)2 -) Elldd
2(1-3)
1=1
T-1
2
Lad.
+ 12010032
T
ane(1 .aar))
+ + - 3yTo² +
Σ
+
El||d]
Σ
Ellee 11],
O11
2 1 Lors
4
t=0
t=
where x" is one of the global minimizer of F. Since a1 S n S
2L. we have
a1((1-bou)
>
4
8
n ?!?
gG aue
By the conditions for 7) and a, we have 22.44 ni..
2 2
21-37 2 21-0)
2
>
TO
16
96
2 2 Ln'C² >
Lad
1 2
and
2
a
2 23 >
1 22
a1.11 96
96
1-101.11
By [ddel| S ne
//el Since Up = O, we have
2
Laz
L'annaae
T
GLL
T-1 Σ
anr(1 - Lair)
||d,1 +
Σ
2(1 - 8)2 ||de|
|1++1
a1
2
I -
Lai1 )
4
1=1
1
T-1
T-1
azen 2
Lazghi
2
1 T2
LG || || 1|
a
|1e41 1|
+
+
+
|10
11 +
8
all
2
1 Lai
2(1 -))
1=
b=
1=0
||042a112.
(9)
Combining (8) and (9), we can obtain
1/G
f(xx)) ((o)
B|Il//( S s(xo) - 2(1 - 3)
E [[]]S((x)) - 1a 11 + 7/((1 - -YTo?
T-1
Ellle+11 1 11 s f(x)) - -f(x)) + GG
E| [)(0)) - 1 + - -ByTO?
E
32 0=
2(1 3)
15

---

Under review as a conference paper at ICLR 2023
Dividing the above two inequalities by of and al' 4 32
respectively, have
4 4(((z)) - f(x)))
2G1E||| (x))))) - 4G(1 3)0²
Ta
5(1 - -37
32 (f(zo) - f(x)))
16G V f(x))) - 11 171
32G 3)o²
B 041
+
T
Ta
8(1 - 611-B
which completes the proof by letting C1 = (f(xx) - f(x')) C2 = 4G 8 C3
f(xa)
Proof of Theorem
Proof. By the selections of and 7), in Theorem 1, let 8 a/n. By Lemma have
Ci Ta
C3
T E [[
s
C2(1 3)0²
T(1 (3)
The conditions 1- S 30 and T 2 max
30 ac (1-8)c2 } lead
3Ca
Ta S 3:
à
C2(1 B)0² s
This completes the proof.
D PROOF OF THEOREM
Proof. From (5) in Lemma 4, we have
f(141) S f1x)) [V 2241 ane(1 Lane)
|0141
ai (2)())))))
Love
[ 2 [o1102(M++1
(10)
By Lemma 3, we have
1.2 1.21
(1-8))lo = -llp:////lllolaaaa--aa -ttp:///-------//---------------
Be
Taking expectation and summation for = 1,..., T. we get
T
1.2 (1de11)
Σ t=
B(11-84)))V/(c)>>-ava E - ff(00)11
2(1 0(1-3:) (1)
+
1 - Be
(11)
Note that - B.+1 Cn. 2 < G & (1- B2+1). Taking expectation for both sides of (10) and taking summation among = 0 ..., T 1, combining with (1), we can obtain
E [ff(xr - fxoo)
G
Blllu vf(x0)]1
MMIMM I
2(1 2(1 (11-80 3.)0²
1.2 1.211
B, ]
T-1
Σ
01e1
.Lnd) E El
1
2C
T-1
au [[[I
(Vax(( +
La
||dl|
Li
(1141, di'l
2
(12)
16

---

Under review as a conference paper at ICLR 2023
From (7) and (12), we can get
a11 E V (==))
4
G
G
T
GL
<s(x)) - [(x))
R[ - -1 + Σ
-1- 3,)
(13)
20
C
2C 3)))
T
a
Lagu
+
L Laaa
Ellld, [7]
T-1
air(1 - Lane)
Ellle++1 11+]
2
1 Lan
4
1=
t=0
By the conditions for Cn and C, we have an 1 G
v
1 a1e(2-La11)
2 axc
By similar
21
4
8
arguments in the proof of Lemma 4, we have 2 bm 2 GL,
GL
5m >
2nc
B.+1
die 2 L0 and 2 ónc
2 21 G3 2
L' (1 112 By
01
1-
|dl] $ Th
nelloell.
Since to O, we can get
La
+ 1- 1-Lam
L2a
|d
+
Σ
T
GL2
|| 12
Σ
T-1
a1r(1 - La(1))
(1111)
||
ai
2C B,)
4
1=1
a11 ||
11
T-1
Σ
2
+
Lag.
L L' 2
||0/1|
GLL
||
8
a1
2
1 - Lax
2C(1
(3++1)
t=
t=0
t=0
0'1
|| 1|?
32
(14)
Combining (13) and (14), we can obtain
S
ai Bl
[( s f(x)) - -(x*) + GLElI| G f(0)) 81 11
Go²
C (1 - BB)2
2C
|
<
ai
| S f(xo) - f(x*) +
GE f( - 11
T
Go²
C (1 - BB)
32
32
2C
Then, the final assertion can be obtained by Σ #+1
(log T). This completes the proof.
E EXPERIMENTAL RESULTS FOR ABLATION STUDY
Table 4: Test accuracy of algorithms solving the trust-region subproblem with one, two, and three search directions CIFAR10.
VGG16
ResNet34
DenseNet121
direction
93.8
95.3
96.0)
DRAG
94.0
95.6
96.1
directions
93.8
95.4
95.7
Table 5: Test accuracy of VGG16 on CIFAR-10 with three different learning rate schedules.
DRAG
SGD
Adam
AdamW
Adahelief
Cosine Annealing
94.3
94.0
92.2
92.4
94.1
Decay at 120 epoch
93.8
92.5
91.8
92.6
93.6
Decay 150 epoch
94.0
92.7
92.2
92.4
93.6
17


Reviews:
[{"review_id": "t-4geqF6GQ", "reviewer": "Reviewer_kEoQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors proposed a Dimension-Reduced Adaptive Gradient Method (DRAG) to eliminate the generalization gap of adaptive gradient method. DRAG makes a combination of SGD and Adam by adopting a trust-region like framework. DRAG is compatible with the common deep learning training pipeline without introducing extra hyper-parameters and with negligible extra computation.  ", "summary_of_the_review": "1. The intuition for the proposed methods is not quite convincing. Why the two-dimensional search is better than a one-dimension or d-dimensional case? Seems a bit unnatural\n\n2. There are many approximations/vague parts in the process, e.g., the Hessian is approximated, and the trust-region is set without many justifications, why would such a trust-region solution give better estimates on the learning rate? \n\n3. Continue with point 2, I am concerned that the optimal lr may only give you better convergence rather than generalization. For example, running vanilla SGD/Adam with line searched lr may not give you better results. I would suggest the authors to compare the derived best lr at the beginning of Page 5 vs the vanilla SGD and the line searched SGD, as well as the Adam version.\n\n4. There are no major improvements shown in experiments. Currently the advantage of DRAG is quite marginal. Also the theoretical result only gives a convergence rate matching existing solutions, which does not give any new information on the generalization.\n\n5. The following method also attempts to combine SGD with Adam for better generalization. The authors may want to comment on/compare with it since the goal is the same.\n\n[1] \"Closing the generalization gap of adaptive gradient methods in training deep neural networks.\" IJCAI2020\n", "strength_and_weaknesses": "\nStrength: \n1. a new adaptive gradient method for better generalization performances\n2. no extra hyper-parameters\n\nWeakness\n1. improvement is not significant at all\n2. does not have very clear intuitions on why the strategy would help\n3. theoretical result does not reflect the improvement\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kGqRxwGiRy", "reviewer": "Reviewer_Guez", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes yet another variant of the Adam optimizer, by combining the idea of trust-region problem with adaptive optimization method. The authors provide some heuristics of creating this method and some theoretical analysis of the algorithm. Experimental results validate their claim that DRAG performs better than the other adaptive algorithms. ", "summary_of_the_review": "In summary, the paper is well-written and easy-to-understand. However, I don't think the contributions are enough to make the paper accepted. I would increase my score if the authors can\n\n1. Provide theoretical results showing that DRAG can converge faster than SGD/Adam in convex/nonconvex problems.\n\n2. Provide experimental results on large datasets/other datasets.", "strength_and_weaknesses": "Strength:\n  1. The proposed algorithm is easy to implement and understand.\n  2. The paper is well-written and easy-to-follow.\n  3. The experimental results show advantages over traditional methods.\n\nWeakness:\n  1. This algorithm seems to be just another variant of Adam in the vast number of similar works, where too many algorithms have been proposed and all claim to be better than Adam, with no theoretical gain and only experimental better performance on some datasets. The contribution of this paper seems insufficient to me.\n\n  2. My first question is, why is the algorithm designed in this particular way? I can kind of understand why and how the trust-region problem is formulated, but why is $H_t$ in line 7 of Algo 1 chosen to be the denominator of Adam? Is there a particular reason why the authors choose Adam? What if I replace it by the simple average of gradient squares (variant of AdaGrad) instead of the exponential moving average? In line 10 of Algo 1 and Sec 3.2, the update seems to be a linear combination of the past gradients $g_1, g_2, ..., g_t$, and $H_t$ is not involved expect for the computation of $\\alpha_1$ and $\\alpha_2$. If the authors only use $H_t$ to be an estimate of, say the Hessian matrix, then I think any similar estimate can be such matrix? Please correct me if I am wrong.\n\n  3. The theoretical results (Sec 4) do not show any advantage over SGD or Adam. It only proves that the algorithm converges in the nonconvex setting. Although this is appreciated, it does not show that the proposed algorithm can, at least have similar property as Adam in the convex case, i.e., in the convex problem, when the gradients are small or sparse, adaptive algorithms such as AdaGrad and Adam can converge faster than SGD, which is a major reason why people like John Duchi have proposed adaptive algorithms in the first place [1].\n\n  4. The experimental results look quite promising. However, they are all on small datasets with small neural networks. I would be much more convinced if the authors can provide results such as, on ImageNet with ResNet50, on One Billion Word with LSTMs, or similar large-scale experiments. Other kinds of experiments such as Image Generation (GAN), Image Segmentation would also be helpful.\n\n\n[1]. John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "f-ZdTguMTE", "reviewer": "Reviewer_LdvC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors observe that Adam has too much freedom in optimization, while SGD has one direction (too little freedom), hence the authors propose to propose an algorithm that has flexibility between SGD and Adam to achieve the benefits of both. Specifically, the authors proposed DRAG, which combines Adam with a trust-region like framework, and optimize the loss along $k$ descent directions, where $k$ is a pre-defined hyper-parameter ranging between 1 and $n$ ($n$ is the number of parameters).\n\nThe authors also proved the convergence of DRAG in the stochastic non-convex optimization setting, and validated DRAG with experiments for CNN and LSTM.", "summary_of_the_review": "The authors propose an interesting and novel idea, which controls the freedom of update to be between Adam and SGD. The analysis is in general complete and experiments are satisfactory. I'm concerned that Thm1 might be wrong, but honestly I think Thm1 is unnecessary and just Thm2 is sufficient. I'll adjust my rating according to the authors' response.", "strength_and_weaknesses": "Strength:\n1) The perspective of update freedom for comparing Adam vs SGD is novel to me. Furthermore, the authors formalize the trust-region idea, and limits the update direction to be a linear combination of first-order momentum and Nesterov-update, this limits the update at each step to be in the convex hull of all past gradients, which was shown to not hurt generalization performance as Adam.\n2) The authors conducted experiments on various architectures (CNN and LSTM) and compare with most of recently proposed optimizers, which is a more thorough comparison.\n\nWeakness:\n1) I'm not fully convinced by Thm1. Specifically, I checked the proof which should be correct up to Lemma 4. When deriving Thm1 from Lemma4, it does not look fully correct to me, because in Lemma4 RHS there's a term $C_2 (1-\\beta) \\sigma^2$, which does not goes to 0 as $T \\to \\infty$. This conclusion does not show that the risk $\\frac{1}{T} \\sum \\mathbb{E} ||\\nabla f(x_t)||^2 \\to 0 as T \\to \\infty$, which means Lemma4 does not fully prove the convergence of the algorithm. \n\nFor proof of Thm1, the condition that $C_2 (1-\\beta) \\sigma^2 \\leq \\epsilon^2 / 3$ is again pretty tricky, because $\\sigma^2$ is the noise of gradient which you can not control, $C_2$ is another constant that depends on $\\eta$, $C_2 = \\frac{4G}{\\delta} \\geq \\frac{\\eta}{\\alpha}$ without an upper bound, (I derive this based on Lemma4's assumption $0<\\delta<\\frac{\\alpha}{\\eta}$, which means this term in quite hard to bound unless you make an extra assumption on the lower-bound of $\\eta$.\n\n(I might be missing some point here, if the authors could correct me I would be happy to increase rating)\n\n2) The experiments are OK but not very complete. I would suggest the authors to test the proposed method on tasks where Adam typically outperforms SGD, for example transformers and reinforcement learning. For current experiments SGD almost always outperforms Adam.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7Y71F4Zooav", "reviewer": "Reviewer_Ymav", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes Dimension-Reduced Adaptive Gradient Method (DRAG), a combination of SGD and Adam by solving a trust-region sub problem. The method is inspired by DRSOM (Zhang et al., 2022) which uses Hessian-vector products in two directions. The authors show convergence theory and experiment results for DRAG. ", "summary_of_the_review": "This paper has some unclear points regarding the subproblem in the algorithm and the convergence analysis. I will be more open to accept this paper if the authors clarify these points. ", "strength_and_weaknesses": "The strengths are: \n- The proposed method has a nice connection with Adam and SGD, which helps further understanding of optimizations algorithms. This paper provided discussions on various approaches for search directions (one-dimension or full-dimension) and convergence theory for DRAG using standard assumptions. \n- Experiment results show encouraging performance compared to prior methods. \n\n\nThe weaknesses are \n- The subproblem is not motivated well enough. It is hard to find an explanation why the exact objective function of the subproblem should be minimized. Other details may explain that the algorithm are searching for the direction in a subspace of 2-dimension, but it does not explain their choice of objective function. The authors says \"update is optimal with respect to the quadratic approximation of the loss function\", however solving for that subproblem does not necessary guarantee a good descent direction. \n- Some details related to the algorithm and convergence theory is unclear, thus it is hard for the readers to fully understand this method. (Please see the comment below.)\n\nComments: \n- It is unclear when the authors state \"We omit $\\epsilon$ here and below for discussion simplicity.\", but mentioning $\\epsilon$ in the complexity later in the paragraph (Page 4). In my understanding, this epsilon maybe the accuracy in approximating the subproblem. If that is true, this complexity should be included in the consideration of total algorithm complexity. In addition, it is not clear if the algorithm use an exact solution of the subproblem or an approximation. Please consider this in the convergence results as well. \n- From the context of theorems I assume $\\alpha_{1t}$ and $\\alpha_{2t}$ should be non-negative. However, I cannot find any justification/explanation on this. Hence the questions: \n1. If true, can you provide a theoretical reason why $\\alpha_{1t}$ and $\\alpha_{2t}$ should be non-negative? \n2. The theorems assume that those solutions are lower bounded. Why this may hold true in practice? (if the assumption does not hold, there is no theoretical guarantee for this method.)\n\n- It is not really fair to say that the theory has the \"same assumptions\" as other methods because the assumptions on $\\alpha_{1t}$ and $\\alpha_{2t}$, $c\\eta$ and $C$ depends on the particular algorithm. \n- The abstract is too long. Please shorten it and put the motivation/explanation to the introduction. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject