Improved Gradient Descent Optimization Algorithm based on Inverse Model-Parameter Difference
Authors: Ayushya Pare
Zhichun Lei
Venue: Submitted to ICLR 2023 (2023)
Keywords: Deep learning
Neural Networks
Optimization algorithm
Adaptive learning-rate
Stochastic Gradient Descent

Abstract: A majority of deep learning models implement first-order optimization algorithms like the stochastic gradient descent (SGD) or its adaptive variants for training large neural networks. However, slow convergence due to complicated geometry of the loss function is one of the major challenges faced by the SGD. The currently popular optimization algorithms incorporate an accumulation of past gradients to improve the gradient descent convergence via either the accelerated gradient scheme (including Momentum, NAG, etc.) or the adaptive learning-rate scheme (including Adam, AdaGrad, etc.). Despite their general popularity, these algorithms often display suboptimal convergence owing to extreme scaling of the learning-rate due to the accumulation of past gradients. In this paper, a novel approach to gradient descent optimization is proposed which utilizes the difference in the model-parameter values from the preceding iterations to adjust the learning-rate of the algorithm. More specifically, the learning-rate for each model-parameter is adapted inversely proportional to the displacement of the model-parameter from the previous iterations. As the algorithm utilizes the displacement of model-parameters, poor convergence caused due to the accumulation of past gradients is avoided. A convergence analysis based on the regret bound approach is performed and the theoretical bounds for a stable convergence are determined. An Empirical analysis evaluates the proposed algorithm applied on the CIFAR 10/100 and the ImageNet datasets and compares it with the currently popular optimizers. The experimental results demonstrate that the proposed algorithm shows better performance than the popular optimization algorithms.

Under review as a conference paper at ICLR 2023
IMPROVED GRADIENT DESCENT OPTIMIZATION AL- GORITHM BASED ON INVERSE MODEL-PARAMETER DIFFERENCE
Anonymous authors Paper under double-blind review
ABSTRACT
A majority of deep learning models implement first-order optimization algorithms like the stochastic gradient descent (SGD) its adaptive variants for training large neural networks. However, slow convergence due to complicated geometry of the loss function one of the major challenges faced by the SGD. The currently pop- ular optimization algorithms incorporate an accumulation of past gradients to im- prove the gradient descent convergence via either the accelerated gradient scheme (including Momentum, NAG, etc.) or the adaptive learning-rate scheme (includ- ing Adam, AdaGrad, etc.). Despite their general popularity, these algorithms often display suboptimal convergence owing to extreme scaling of the learning- due to the accumulation past gradients. In this paper, a novel approach to gradi- ent descent optimization is proposed which utilizes the difference in the model- parameter values from the preceding iterations to adjust the learning-rate of the al- gorithm. More specifically, the learning-rate for each model-parameter is adapted inversely proportional to the displacement of the model-parameter from the pre- vious iterations. As the algorithm utilizes the displacement of model paraameers.ssssss. poor convergence caused due to the accumulation of past gradients is avoided. A convergence analysis based on regret bound approach is performed and the theoretical bounds for stable convergence are determined. An Empirical analysis evaluates the proposed algorithm applied on the CIFAR 10/100 and the ImageNet datasets and compares it with the currently popular optimizers. The experimental results demonstrate that the proposed algorithm shows significant improvement over the popular optimization algorithms.
INTRODUCTION
Machine learning essentially involves implementing an optimization algorithm to train the model- parameters by minimizing an objective function, and has gained tremendous popularity in fields like computer vision, image processing, and many other areas of artificial intelligence Dong et al. (006)): Simonyan & Zisserman (2015): Dong et al. (2014).
Fundamentally, optimization algorithms are categorized into first-order Robbins & Monro [195] Jain et al.] (2018). higher-order Dennis & Moré (1977); Martens (2010) and derivative free algo- rithms Rios Sahinidis (2013); Berahas et al. (2019) based on the use of the gradient of the objec- tive function. First order algorithms use the first derivative to locate the optimum of the objective function through gradient descent. The second-order algorithms, on the other hand, use the second- order derivative information to approximate the gradient direction as well as the step-size to attain the optimum. Major disadvantage of these methods is the large computations required deter- mine the inverse of the inverse Hessian matrix. The quasi-newton algorithms like the L-BFGS solve this problem by approximating the Hessian matrix, and have gained significant popularity in many optimization problems Kochenderfer & Wheeler (2019).
Over the years, first-order optimization algorithms have become the primary choice for training deep neural network models. One of the widely popular first-order optimization algorithms is the stochastic gradient descent (SGD) which is (a) easy to implement and (b) is known to perform well across many applications Agarwal et al. 2012 Nemirovski al. 2009). However, despite the ease

---

Under review as a conference paper at ICLR 2023
of implementation and generalization, the SGD often shows slow convergence due to the fact that SGD scales the gradient uniformly in all dimensions for updating the model--aaameters. This is disadvant,geouss, particularly in case of loss functions with uneven geometry, ie.. having regions of steep and shallow slope in different dimensions simultaneously, and often leads to slow convergence Sutton (1966).
There have been a number of optimization algorithms developed over the years which attempt to improve the convergence speed of the gradient descent in general. There are algorithms that ex- pedite the convergence in the direction of the gradient descent, which include the Momentum and the Nesterov's Accelerated Gradient (NAG) algorithms Qian [1999]; [Botev et al.) (2017). Then there are algorithms that dynamically adapt the learning- rate of the algorithm based on an exponen- tially decaying average of the past gradients, and include the AdaGrad, RMSProp, and the Adadelta algorithms Duchi et al. (201T); Tieleman & Hinton (2012); Zeiler (2012). This category of algo- rithms implements the learning-rate as a vector, each element of whose corresponds to one model- parameter, and is dynamically adapted based on the gradient of the loss function relative to the corresponding model-parann paramee.. Further, there are the adaptive gradient algorithms like the Adam algorithm and its variants like the Adamax, RAdam, Nadam, etc., which simultaneously incorporate the expedition of the gradient direction and the adaption of learning-rate based on the past gradients Kingma & Ba (2015); Dozat (2016); Reddi al. (2018). Apart from that, some recent advances in the other first-order gradient descent methods include the signnGGDDBernstein
|Brnsttein et al. (2018). variance
reduction methods like the SAGA Roux et al. (2012). SVRG Johnson Zhang (2013) and their improved variants Allen-Zhu & Hazan (0166); Reddi et al. (2016); Defazio et al. (2014).
The above-mentioned adaptive learning-rate methods, are amongst the most widely implemented optimizers for machine learning. However, despite increasing popularity and relevance, these meth- ods have their limitations. Willson et al. (2017) in their study showed that the non-uniform scaling of the past gradients, in some cases, leads to unstable and extreme values of the learning-rate, causing suboptimal convergence of the algorithms. A variety of algorithms have been developed over the last few years which improve the Adam-type algorithms further, like the AdaBound, which employ dynamic bounds on the learning-rate, Luo et al. (2019;; AdaBelief, which incorporates the variance of the gradient to adjust the learning-rate Zhuang et al. (2020); LookAhead, which considers the tra- jectories of the fast and the slow model-pane parameters /hang et al. (0199); Radam, through rectifying the variance Liu et al. (2020); and AdamW, by decoupling the model- podeel-arrameter decay Loshchilov & Hutter (2019).
In this paper, new approach for the gradient descent optimization is proposed, where the learning- rate is dynamically adapted according to the change in the model-parameter values from the pre- ceding iterations. The algorithm updates the learning-rate individually for each model-parameter, inversely proportional to the difference in model-parameter value from the past iterations. This speeds up the convergence of the algorithm, especially in case of loss function regions shaped like ravine, as the pardmm-a converging with small steps on gentle slope is updated with larger learning-rate according to the inverse proportionality, thereby speeding up the overall convergence towards the optimum. Further in the paper, a theoretical analysis to determine the lower and upper bounds on the adaptive learning-rate and a convergence analysis using the regret bound approach is performed. Additionally, an empirical analysis of the proposed algorithm is carried out through implementation of the proposed algorithm for training standard datasets like the CIFAR-100 10010000000 and the ImageNet datasets on different CNN models.
The major contributions of the paper are as follows:
A new approach to gradient descent optimization, which updates the learning-rate dynam- ically, inversely proportional to the difference in the model pardm--arrrettr values from the pre- ceding iterations is presented. The novelty of the algorithm lies in the fact that it does not employ an accumulation of past gradients and thus the suboptimal convergence, due to very large or very small scaling of the learning-rate, is avoided.
A theoretical analysis determining the bounds the adapting of the learning is pre- sented and a convergence analysis based on the regret bound approach is derived.
An empirical analysis implementing the proposed algorithm the benchmark classifica- tion tasks and its comparison with the currently popular optimization algorithms is per- formed.
2

---

Under review as a conference paper at ICLR 2023
The remainder of the paper is organized as follows: Section 2 gives short background and for- mulates the problem at hand. In Section 3, the proposed algorithm is introduced and described in detail and the theoretical bounds on the adaptive leamning-rate for stable convergence are deter- mined. In Section 4, the proposed algorithm implemented on benchmark neural networks and its performance is evaluated in comparison with the currently popular optimization algorithms, like the SGD, Adam, AdaBelief, LookAhead, RAdam, AdamW, etc., which is followed by conclusion and a brief outlook on the future aspects of the work in Section 5.
PROBLEM FORMULATION
2.1 NOTATIONS
Given a vector R. Pk is used to denote the hth element of the vector at the 1th time instance, ||l|| denotes the L2- norm of the vector and | gives the absolute value the vector. Given two vectors p, Q E IR, then p- q denotes the dot product, p O denotes the element-wise product and p/q denotes the element-wise wise division the two vectors.
2.2 BACKGROUND
Supervised learning involves training neural network, initially modelled with parameters 0 E R, that maps the input dataset æ E R to predict an output ý = f(0, æ), and compute the gradient of given loss function with respect to the model-parameters, and solve optimization problem adapt the parameters 0 such that the loss function is minimized. The optimization (minimization) problem is represented as
min N Σ (V.
where J is the loss function, is the number of training examples, x(()) is the 5th training example, and σd) is the corresponding labelled output. The SGD optimization recursively updates the model- parameters 9 by subtracting the gradient of the loss function scaled by certain factor (learning-ratee via the following update rule
0 0 = 02 p.
(Ok)
(2)
where O% represents the model-parameters at instance k, V is the unbiased estimate of the exact gradient of the loss function and (4 is the learning-rate which is also generally adapted at every iteration Zinkevich 2003); Haykin (2014).
Slow convergence one of the major challenges faced by the SGD optimization. SGD convergence can be particularly slow due the complex geometry of the loss function. A variety of optimization algorithms, which dynamically adjust the learning-rate of the algorithm by considering an accumu- lation of the past gradients for adapting the learning-rate. have been developed and gained popularity in the past years Soydaner (2020); Dogo et al. (2018). The adaptive gradient algorithms, like Adam and its variants (as listed in section 1), despite their widespread popularity, display suboptimal con- vergence in many scenarios. This results from the non- uniform scaling of the learning- -aating-ttteaa rate accumu- lation of the past gradients Wilson al. (2077); Chen et al. (2019).Th Therefore, novel approach to SGD optimization, which adjusts the learning-rate of the algorithm considering the difference in the model-paranen values instead an accumulation of past gradients, proposed in this paper.
PROPOSED ALGORITHM
The proposed algorithm is based on dynamic adjustment the beanning-rate according to the change in the values of the the learning-rate for each moral-parameter dynamically adjusted by scaling it inversely propor- tional to the difference in the values of that model-parameter from the immediate preceding iter- ations. The proposed algorithm follows the norm that the model-paramesn slope should be adapted with larger learning- rate compared to the parameters converging quickly over regions of steeper slope, thereby boosting the overall convergence the algorithm towards the optimum.
between the preceding consecutive iterations. More precisely,
in regions of a gentle
3

---

Under review as a conference paper at ICLR 2023
The difference coefficient, denoted by D is function of the absolute difference between the values of the 7th model-parameter from the immediate preceding iterations, and is given by
D 1
K
(3)
abs )
where ( is the difference coefficient of the jth 0( ( gives the difference between the values of the ith model-parameter between the 1oth and the (k 1)th iterations. The term 1 + abs( (0) limits the range of the denominator to o0) so that extreme scaling of μ& in case of very small A&, is avoided. The learning-rate P4 for the ith model-parameter thus updated according to the following relation.
at the hth iteration and A0g
K
Pk
pr D = =40 (1+ abb(
(4)
The characteristic of the ( determines the behavior of the dynamic learning-rate. Note that for K = 1, D E (0,1), A (0). It can be observed that large difference in the model- parameter values results in a smaller Dj and thus smaller adaptive learning-rate, while smaller difference results in larger Da. i.e., larger adaptive learning-rate.
The dynamic geamning-rate, in this algorithm, is represented by vector M E R. every element of whose gives the learning-rad -aat corresponding to each model-parameter
(I) (2) P Pk .... U (T)
M
(5)
where (+) = μo D and is the number of model-parameters. Thus, at 4 iteration, the update of the model--parametee is given by
0x+1= M O (0x)
(6)
The algorithm defined by the Eq. 6 above adjusts the learning-rate for each model-parane parametter as an inverse function change in the model-parameter values. The Algorithm depicts the generic framework of the proposed algorithm.
Algorithm 1: Proposed algorithm
Input: R
Parameters:
initial paramepassseters On initial learning-rate po
Iterate:
for k 1,2,3, until convergence
compute gradient
V (J(0))/00
2. compute displacement coefficient
D (1)
(+a
3. compute adaptive learning-rate
Pk Mu (1)
M
(1)
1
(2)
(L)
update maram--parameters
o 0 Mc ((x)))
end for
The idea of utilizing the difference in the modell-arameter is also used in the L-BFGS algorithm, which belongs the category of quasi-Newton methods, and uses the history of past m parameter
4

---

Under review as a conference paper at ICLR 2023
updates and their gradients, to estimate the Hessian of the objective function H (8x) V J (0x) Liu & Nocedal] (1989): Kochenderfer & Wheeler (2019). In comparison, the proposed algorithm update the learning- rate of the gradient descent. Also, the BFGS algorithm requires computation costs and storage capacity the order ((n²), whereas the proposed algorithm requires both computation well as storage of the order ((n) Mokhtari & Ribeiro 20155.
utilizes the difference mooel--parameeer
3.1 CONVERGENCE ANALYSTS
In this section, convergence analysis the proposed algorithm based on the regret bound ap- proach is performed, and the conditions for guaranteed convergence based the bounds the adaptive learning-rate and the range of the parameter K are determined. Considering {J(0)) {J(O)), (0,), (02), .... [0x)] as the sequence of the loss function values, the regret bound (T)) is the sum of the difference between the optimum value of the loss function, i.e. J(0)) and the series of function values from (6o) to J (0x), and is given by
T (T( = Σ [J(0k) - -(()))
(7)
where J(0") arg (0). For convex and twice differentiable loss function (0) v0 E I, FER
whose gradient is 3-Lipschitz continuous i.e., V 10,,00 02 the regret bound for the proposed algorithm (proof in Appendix A given by
&. (02) - (01) ll2 < B || 02 01112-
RT(T) S 2M
|| 1100-00 - 0.
(8)
(2) where M = [m() . ..... U (L) Further, the algorithm converges with a rate O (1/pgk), which
means the rate of convergence is inversely dependent the number of iterations well as the instantaneous learning-rate /4g, which in turn is determined from the change in the marameer values A02. This implies that, the model parameters on flatter trajectory will converge at faster rate.
3.1.1 CONVERGENCE BOUNDS AND RANGE OF PARAMETER K
In this section, the lower and upper bounds for the adaptive learning-rate in case of a very small or very large change in model-paran paddmeparameters are determined. The algorithm will converge with a rate (L/kk), if the adaptive learning-rate is bounded by
0 < p*
<
(9)
3
where & the number of iterations and the maximum eigenvalue of the input correlation matrix Raa. determined from the classical theoretical analysis of the SGD convergence Boyd & Vandenberghe (2004).
Case I: For the model-parameter converging over a very steep slope, i.e., where the value of Ae(")
very large (A - oo), the lower bound on the adaptive learning rate is given by
(8)
lim
K
(10)
A6
400000
(1+ abs (AD
The minimum adaptive learning-rate M4 Maainn for convergence with rate ((1kk), must be bound (4) by j0mmn
(8)
0. Thus, the lower bound of the parameter K given by K 0.
'The maximum eigenvalue of the matrix Run determined from the trace of the matrix E [a= 2x] and under practical considerations, the trace (F. To [T===) ) is computed from the average power of the input signal Haykin (2014).
5

---

Under review as a conference paper at ICLR 2023
Case II: For the morel-parameter following very slow convergence long, gradual slope
( sa 0), the theoretical maximum of the learning-rate maating-rateea given by
K
Jlmma
lim 20
Po
K μi
(11)
[ + abs A
and for the gradient descent have global convergence, the upper bound must be limited to (1) Jommax S 2/3. Thus, the range of the parameters K, computed by substituting the minimum and the maximum values respectively, is given by K (0. Mo.
In this section, the proposed algorithm was described and the bounds on the adaptive learning rate for a guaranteed convergence were determined. The proposed algorithm provides a novel approach to improve the convergence speed of the gradient descent algorithm, simultaneously guaranteeing stable convergence.
EXPERIMENTS
In this section, an extensive experimental analysis was carried out to evaluate the efficacy and perfor- mance of the proposed algorithm. The performance of the proposed algorithm was compared with a number of state of the art optimizers like the SGDM, Adam, AdaBelief, LookAhead, RAdam, and AdamW. The first part of the experiments involved implementing the proposed algorithm a standard two-pares wwo-parameter loss-function, i.e., Rosenbrock function, and visualise and compare its convergence with SGDM and Adam. In the next part, further experiments were carried out im- plementing the above-mentionel optimizer for training of two benchmark datasets, and comparing their performance based on the training loss and accuracy. The experiments involved training of (i) CIFAR 10 and CIFAR 100 datasets on the ResNet 8 architecture, and (ii) Tiny-ImageNet dataset on the EfficientNet architecture
4.1 PERFORMANCE ASSESSMENT ON ROSENBROCK FUNCTION
For the experiments in this section, the above-mentioned algorithms were implemented on a two- dimensional optimization function and their convergence characteristics were compared. The Rosenbrock function is known to be used as performance evaluation benchmark for different op- timization algorithms Emiola & Adem (202I). The Rosenbrock function for two-twwomma poopparmetter setup implemented in the experiments is given by
(Wi, W2) K (wf w2)² + (wi - 1)²
(12)
where w1, wy E IK and ff (W1, wyy is strictly convex and differentiable, and the constant determines the steepness of the valley of the Rosenbrock function. The minimum of the function lies at (1, 1).
and is inside long, parabolic shaped flat valley, and achieving fast convergence the minimum becomes difficult in some cases. The Fig. I aa) shows the Rosenbrock function with a k = 100.
The experiment was set up as follows: The porame-passeseess wj and W2 were initialized to (0, 5) and the initial learning-rate for all the algorithms was set to μ4 0.001. The hyperparameters 31 and B2 for the Adam optimizer were to 31 0.9 and 3,2 0.999 respectively. The performance of the mhove-mentionee algorithms was analyzed and compared based on the speed of convergence, the accuracy and the run time of the algorithm.
The Figure I shows the convergence comparison of the proposed algorithm with the SGD and the Adam optimizers. The Plor Ttd show the 3D surface plot and the contour plot of the conver- gence of the above-mentioned algorithms, while the clo shows the convergence of the function against the number of iterations. can be seen from the plot [[c] that the proposed algorithm con- verges to the minimum in about 25 iterations. In comparison, the SGD algorithm converged in about 40 iterations, while the Adam algorithm showed the slowest convergence for this experiment and re- quired about 160 iterations to converge minimum. It can be observed that the proposed algorithm outperforms the SGD and the Adam algorithms terms of the convergence speed, i.c., number of iterations for convergence.

---

Under review as a conference paper at ICLR 2023
AnD
Acamm
Adam
Proposed algorfhm
Propased
400
algontti
200
12
2.9
2
-.5
-25
83
15
300
250
Proposed
200
algonihym
60
0
150
200
Ieeratoons
Figure 1: (a) 3D Surface plot of the convergence. (b) 2D contour plot of the convergence. (c) Convergence of the function w.r.t. number of iterations.
4.2
PERFORMANCE ASSESSMENT ON NEURAL NETWORKS
4.2.1
CIFAR- AND CIFAR-100
For the experiments in this section, image classification the standard CIFAR-10 and CIFAR- 100 datasets was performed using the ResNet-18 architecture He et al. (2015). The CIFAR-IO and CIFAR- 100 datasets consist of 32 x 32 colour images belonging 10 and 100 classes respectively. The dataset is split into 50000 images for training and 10000 images for test Krizhevsky et al. (2099) The SGDM optimizer was implemented with step-decay scheduler with initial learning- rate of 0.1 and decreased by a factor of 10 after every 20 epochs. For the Adam and AdaBelief optimizers. the initial learning rate chosen 0.001 with hyperparameters B1 0.9, 0.999. The Look optimizer was implemented with a learning-rate of 0.001 and the hyperparameters 5 and a 0.5. The RAdam and the Adam W optimizers were applied with learning-rate of 0,001, hypeparameterss 31 = 0.9, B2 = 0.999 and weight decay of 0.0001 in case of AdamW. For the proposed algorithm, the initial learning-rate was set at 0.001 and the parameter K was chosen to be K = 10. This value was chosen after extensive simulations with different parameter values (refer section 4.2.3) The CNN models were coded on the Google Colaboratory environment and trained on 25 GB RAM GPU and run for 100 epochs for each optimization algorithm with a batch-size of 128.
Table Comparison of the training loss and accuracy for the CIFAR Datasets
Dataset
Optimizer
CIFAR 10
CIFAR 100
Loss
Accuracy
Loss
Accuracy
SGDM
0.06139
0,98886
0.28875
0,93812
Adam
0.00936
0.99713
0.14823
0.96270
AdaBelief
0.04569
0.99080
0.26306
0,94918
LookAhead
0.37017
0.87695
0.01018
0.99905
RAdam
0.01806
0.99617
0.16338
0.96631
Adam W
0.01783
0,99422
0.02219
0,99320
Proposed
algorithm
0.00012
1.0
0.00571
0.99914

---

Under review as a conference paper at ICLR 2023
The figure shows the training results for the classification task the CIFAR-10 10 dataset, and the figure b) for the CIFAR-I0U 100 dataset. It can be observed that for all algorithms can achieve an accuracy approaching almost 99%. The proposed algorithm performs slightly better in case of both the CIFAR-10 10 and the CIFAR-100 datasets. The performance evaluation hased on the training accuracy and loss for each optimizer is compiled in the table T
1.0
10
SCDN (step, decay)
Adam
Training accuracy
Adadlelled
0.8
Training loss
0.8
Lookthhodd
Räddam
0.6
decay)
0.6
proposed algerithin
0.4
LookAbead
0.4
Mkdam
Adamm
0.2
preposed algorkhm
0.2
20
40
60
100
40
60
80
100
Epochs
Epochs
(a)
1.0
1.0
S0ON decay))
Training accuracy
0.8
Training loss
0.8
LooliAhosd
RAddam
Adarmw proposed algonithmm
0.6
500M istep_dacm docay?
Adam
Adasclief
0.4
0.4
0.2
proposed algorithm
0.2
20
40
60
80
100
0
20
40
60
80
100
Epochs
Epochs
(b)
Figure 2: (a) Convergence comparison on the CIFAR-10 dataset (b) Convergence comparison on the CIFAR-100 dataset
4.2.2 TINY-IMAGENET
For the next experiments, the Tiny-ImageNet dataset was implemented Le & Yang (2015) and the training was carried out using the EfficientNe:B3 architecture Tan & Le (2019). This dataset consists of 100,000 training images, 10,000 validation images, and 10,000 testing images and are divided into 200 classes. The images are extracted from the ImageNet dataset, cropped and resized to be 64 x 64. Due to the heavy computational burden, the simulation comparisons SGDM and the Adam algorithm. The hyperparameters for the SGDM (with step-decay), Adam optimizer and the proposed algorithm the learning curves for each optimization method for both the training accuracy and training loss on the Tiny-ImageNet dataset. can be observed that both the Adam and the proposed algorithm perform better than the SGDM and the proposed algorithm shows slightly better performance than the Adam algorithm. The Table 2 summarizes the training and test accuracy and loss for the above mentioned model in case of each optimizer.
carried out only with
the same in the above experiments. Figure shows
4.2.3 EXPERIMENTS WITH DIFFERENT HYPERPARAMETERS
In this section, the performance of the proposed algorithm was evaluated for different hyperparam- eters applied on the CIFAR-10 dataset. The proposed algorithm was implemented for training the dataset for different values of the parameter K, i.e. 0. 1. 5, 10, and 20. It can observed that for smaller values of the parameter K, the algorithms shows slower convergence and results in lower curacy. However, convergence of the algorithm is aggressive for larger values of K and for = 20 shows large oscillations at the middle stage of training. Training with parameter K 10 shows the best overall performance. The f the comparisons of the training curves for the different hyperparameters and the table lists the training accuracy and training loss for the same.
8

---

Under review as a conference paper at ICLR 2023
Table 3: Training and Test Loss and accuracy for different values of parameter K
Table 2: Training and Test Loss and accuracy on the Tiny-Imagell dataset
CIFAR-100
Tiny-Inn ImageNet
Parameter
Loss
Accuracy
Optimizer SGDM Adam 0.71841
Loss
Accuracy
K = 0.1
0.71115
0.75323
1.21919
0.69322
K
0.21901
0.92940
0.79568
0.0010
1.0
Proposed algorithm
0.69584
0.80373
K 10
0.00012
1.0
K 20
4.35486
1.0
SGDM siop_deccy)
3.5
Adam
Training accuracy
Training accuracy
proposed algorithm
3.0
0.5
2.5
0.4
2.0
(step, decay)
0.3
1.5
proposed algorithm
0.2
1.0
20
40
60
100
0
20
60
80
100
Epochs
Epochs
Figure 3: Convergence comparison on the Tiny-ImageNe dataset
1.0
K=0.1
Training accuracy
2.0
0.8
Training loss
10
1.5
0.6
1.0
- 0.1
K=
0.5
0.2
K 10
K 20
0.0
20
40
60
80
100
0
20
40
60
80
100
Epochs
Epochs
Figure 4: Convergence comparison for different hyperparameters K
CONCLUSION
In this paper, new approach to gradient descent optimization is presented, which updates the learning-rate of the algorithm for each paraee-arrameter inversely proportional to the change in marameer values from the preceding iteration. The algorithm adapts the morelepas on gentle slope with larger learning-rate relative to proving the overall convergence speed. The efficacy of the proposed algorithm was proven based on the training of standard datasets like the CIFAR- R-/000000 and the Tiny-ImageNet datasets, and it was noted that the proposed algorithm surpasses the currently popular algorithms. Future work involves deeper analysis of the proposed algorithm complex non-convex loss functions and implementing on other benchmark datasets and models.
on steep slope, thereby im-
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alckh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, and Martin J. Wainwright. Information- Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization. IEEE Transactions on Information Theory, 58(5):323533244 May 2012. ISSN 1557-9654, doi: 10.
1109/TT:2001.2182277. Conference Name: IEEE Transactions on Information Theory.
Zevuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In
33rd International Conference Machine Learning. ICML 2016, pp. 1093-1101. International Machine Learning Society (IMLS), 2016.
Albert S. Berahas, Richard H. Byrd, and Jorge Nocedal. Derivative- optimization of noisy functions via quasi-Newton methods. SIAM Journal on Optimization, 29(2):965-993, 2019, ISSN 1052-6234. doi: 1
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed Optimisation for Non-Convex Problems. In Proceedings of the 35th Inter- national Conference on Machine Learning, pp. 560-569. PMLR, July 2018. ISSN: 2640-3498.
Alcksandar Botev, Guy Lever, and David Barber. Nesterov's accelerated gradient and momentum as approximations to regularised update descent. In 2017 International Joint Conference on Neural Networks (IJCNN), pp. 1899-1903, May 2017. doi: 10. 109/1ICNN.001..966660 ISSN: 2161- 4407.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization, March 2004. 978051180444 Publisher: Cambridge University Press.
ISBN:
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of Adam-type algorithms for non-convex optimization. International Conference on Learning Representations, May 2019.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: a fast incremental gradient method with support for non-strongly convex composite objectives. In Proceedings of the 27th Interna- tional Conference on Neural Information Processing Systems Volume 1, NIPS' 14, pp. 1646- 1654, Cambridge, MA, USA, December 2014. MIT Press.
J. Dennis, Jr. and Jorge Moré. Quasi-Newton Methods. Motivation and Theory. SIAM Review, 19( 19(1):6689, January 1977. ISSN 0036-1445, doi: 10.1 107/10//019005
E. M. Dogo, O. J. Afolabi, N. I. Nwulu, B. Twala, and C. O. Aigbavboa. A Comparative Analy- sis Gradient Descent- Based Optimization Algorithms on Convolutional Neural Networks. In 2018 International Conference Computational Techniques, Electronics and Mechanical Sys- tems (CTEMS), pp. 92-99, Belgaum, India, December 2018. IEEE. ISBN 978-1-5388-7700944 doi: 10.1109/CTEMS. 2018.8769211.
Chao Dong, Chen Change Loy, Kaiming He, and Xiaoou Tang. Learning a Deep Convolutional Net- work for Image Super-Resolution. In Computer Vision ECCV 20/4, Lecture Notes in Computer Science, pp. 184-199, Cham, 2014. Springer International Publishing. ISBN 978-3-319-10593-2 doi: 1-110079777-3--11--009-----
Chao Dong, Chen Change Loy, Kaiming He, and Xiaoou Tang. Image Super- Resol-Resoottion Using Deep Convolutional Networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016. doi: 10.1109/PAM..2215.222222.
Timothy Dozat. Incorporating Nesterov Momentum into Adam. International Conference on Learn- ing Representations workshop, February 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12(61):2121) 12111):21 2011. ISSN 1533-7928.
Iyanuoluwa Emiola and Robson Adem. Comparison of Minimization Methods for Rosenbrock Functions. June 2021. doi: 10.1 00.1109/MED1144002000 000.EEDDDS5444022299400000000
Pages: 842.
10

---

Under review as a conference paper at ICLR 2023
Simon S. Haykin. Adaptive filter theory. Pearson, Upper Saddle River, New Jersey, fifth edition edition, 2014. ISBN 978-0-13-266145-3.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CoRR, 122.0335,, 2015. URL
03385
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Paralleliz- ing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification. Journal of Machine Learning Research, 18(223):1-42 2018.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Proceedings of the 26th International Conference Neural Information Process- ing Systems Volume 1, NIPS' 13, pp. 315-323, Red Hook, NY, USA, December 2013. Curran Associates Inc.
D. Kingma and J. J. Ba. Adam: A Method for Stochastic Optimization. International Conference on Learning Representations (ICLR), 2015. Publisher: Ithaca, NYarXiv.org.
Mykel J. Kochenderfer and Tim A. Wheeler. Algorithms for Optimization. The MIT Press, 2019. ISBN 0262039427.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny im- (209,, 2009.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 23/N, 7(7):3, 2015.
Dong Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming, 45(1):503-5235 1989.
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, 2020.
I. Loshchilov and F. Hutter. Decoupled Weight Decay Regularization. International Conference Learming Representations, 2019.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive Gradient Methods with Dynamic Bound of Learning Rate. International Conference on Learning Representations, 2019.
James Martens. Deep learning via Hessian-free optimization. In Proceedings of the 27th Interna- tional Conference on International Conference on Machine Learning, ICML' 10, pp. 735-742, Madison, WI, USA, June 2010. Omnipress. ISBN 978- 978-1-60555-90777.
Aryan Mokhtari and Alejandro Ribeiro. Global convergence of online limited memory bfgs. The Journal of Machine Learning Research, 16(1):31513181,, 2015.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust Stochastic Approximation Ap- proach Stochastic Programming. SIAM Journal on Optimization, January 2009. doi: 10.1137/070704277. Publisher: Society for Industrial and Applied Mathematics.
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural Networks, 12 (1):145-151, Jamuary 1999. ISSN 0893-6080. doi: 10.1016/08992-60009930000 16-6.
Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabás P6czós, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML 16, pp. 314-323, New York, NY, USA, June 2016. JMLR.org.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the Convergence of Adam and Beyond. In International Conference Learning Representations, February 2018.
Luis Miguel Rios and Nikolaos V. Sahinidis. Derivative-free optimization: review of algorithms and comparison of software implementations. Journal of Global Optimization, 56(3):1247-1293; July 2013. ISSN 1573-2916 doi: 10. 00.1007711898--12--995111

---

Under review as a conference paper at ICLR 2023
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. Mathematical Statistics, 22(3):400 407, September 1951. ISSN 0003-4851, 2168-8998 doi:
The Annals of
Publisher: Institute of Mathematical Statistics.
Nicolas Le Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponen- tial convergence rate for finite training sets. In Proceedings of the 25th International Conference on Neural Information Processing Systems Volume 2, NIPS' 12, pp. 2663-2677 Red Hook, NY, USA, December 2012. Curran Associates Inc.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition, In International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Derya Soydaner. A Comparison of Optimization Algorithms for Deep Learning. International Jour- nal of Pattern Recognition and Artificial Intelligence, 34(13):2052013, December 2020. ISSN 0218-0014. doi: 10.1 422/00228004220200
Publisher: World Scientific Publishing Co.
Richard S. Sutton. Two problems with backpropagation and other steepest-descent learning proce- dures for networks. In Proceedings of the Eighth Annual Conference of the Cognitive Science Society. Hillsdale, NJ: Erlbaum, 1986.
Mingxing Tan and Quoc Le. EfficientNet: Rethinking model scaling for convolutional neural net- works. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th In- ternational Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6105-6114, PMLR, 09-15 Jun 2019. URL /ttp:ss//pprceeeddng...oot
press/v97/tan html
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):66 31, 2012.
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS 17, pp. 4151-4161, Red Hook, NY, USA, December 2017. Curran Associates Inc. ISBN 978-1-5 188-1-5108-60966
Matthew D. Zeiler. ADADELTA: An Adaptive Learning Rate Method. arXiv:1212.5701 [cs],
December 2012. arXiv: 1212.5701.
Michael Zhang, James Lucas, Geoffrey Hinton, and Jimmy Ba. Lookahead optimizer: steps forward, step back. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, number 861, pp. 9597-9608. Curran Associates Inc., Red Hook, NY, USA, December 2019.
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvorek, Xenophon Pa- pademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in neural information processing systems, 33:18795-18806, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-936, 2003.
12

---

Under review as a conference paper at ICLR 2023
A APPENDIX
The proof of convergence of the algorithm carried out considering the regret bound of the algorithm. Consider J(0) the objective function to be optimized and consider {J(0)] {J6)), ((0)),
} } as the sequence of the loss function values. Regret bound, given
by (T", the sum of the difference between the optimum value of the loss function, i.e. J(0)) and the series of function values from [(bu to J(Ox). The regret bound is given by
R₂(T) - Σ -
(13)
where J(0") = arg (0) sERO
Notations: [( gives the value of the loss function at instance with respect to the model-
parameter i. V.(((() gives the gradient of the loss function instance with respect to the model- parameter i.
Assumptions: For the convergence analysis, the following assumptions made:
Assumption 1: The function ((f) is convex, i.e.,
J(x2) 2 ((x) + (VJ(z1). - =1)) VI1, E R"
(14)
Assumption 2: VJ(0) is L- Lipschitz continuous, i.e.,
VJ(x2)
L. 12 x V01 IR""
(15)
and
L 2
J(x2) s ((1) + (VJ(z)), (x2 21)) +
21
12
VI1, R.
(16)
Proof:
The convergence analysis attempts to prove that the upper bound of the regret function (T) is bounded by the inverse of the number of iterations.
Considering the Lipschitz continuity, we have
L
((02) < ((0)) + (VJ(0)), - (0)-
|| 02
- 02
11
v0,, 02 E R
(17)
for the ith model-parameeer, the above equation can be written as
( ((( + (V.(O (0f) 0( +
L
0+1
g 1
(18)
J(O(1 s ((0ai + (ajela)) - 60 v)((("))
+ - ||
- ( VJ(((")) 112
(19)
s (1 + (' - 10 (
1
16 ((( 1
-
(20)
2
(n (
S <'(1 a4i (3) || ()(O 11 +
vJ(0(()) 12
(21)
2
< (() - -1b (1- 11-4 -
II VJ(O 12
(22)
2
13

---

Under review as a conference paper at ICLR 2023
using the condition Pkc (9 S and plugging in 22
J( - J(
(23)
2
It can be observed from the above Eq. 23 that since
V 11 is always positíve, the value of the loss function (( always decreases after every iteration untill reaches the minimum (( )
where the gradient of the loss function v.(((()) = 0.
Now considering the convexity of the loss function V (0) again (Assumption 1), the following can be written
)( 2 -((( (VJ(O(()) (0!) - o(0))
(24)
+ J( - )(05))+ (V.( (0 -0())
(25)
Plugging the above in Eq. 23 gives
(1)
J( 1 S J(O + VJ(O || 00 - o000
1|2
Mk
VJ(O 12
(26)
2
(6)
J(B(1) x(++)) s ((O(()) + VJ((()) || 0 o!0) 1|2
Ui
2
(1l 0 95"
12 - 0% 005) 11 (27)
2
Rearranging the above equation gives
- <
1
2
(8)
(J(
1 - _000 1|2 (uk
(3) ) || (O( 11
2
( ( 12 0 o59)
11
(28)
which on simplification gives.
1 - -((!!) <
0000
o.5)
11
(o 0000 us
(1) (
(29)
2
(8)
+ =((0())) J(B!
(
13
( E+1
g.99
(30)
2p
The above inequality hold for every iteration of the sequence. Thus, summing over all the iterations. gives
K-1 Σ J0 - i=0
<
o09 11
(
0 12
(31)
214 ==
(3)
The sum element on the right-hand side of the equation is telescopic sum, and hence all the intermediate terms disappear, resulting in the following
14

---

Under review as a conference paper at ICLR 2023
Σ JO J(
1
1000
0.0) 11
0
0.²)
11
(32)
2
(8)
The second term in the right-hand side, i.c.. inequality holds true as well
-00²)
112 is always positive and hence the following
k-1 -
1
0
0.00
12
(33)
(1)
2
==
This relation shows that for step-size uk algorithm is bounded by
(1)
S
t. the regret of the bound of the gradient descent
00
000 12
(34)
2
(3)
It was established in the above section that the upper bound of the variable learning-rate at any (0, po) and be inferred that the regret bound of the algorithm is
instance is bounded by pi (4) given by
R
(T) S
00
12
000
12
(35)
2/4
(1)
2,50
And the regret bound of the complete loss function can be computed by aggregating the above relation across all dimensions, for all the moral-parameters.
[|| 0 0. 11
(T
(36)
2M
(1)
(L) T
where M =
1/ : 1k ..... Hx
where M = |/ 14 ...... 14 "01 Further, the algorithm converges with a rate O (1/pgk), which means the rate of convergence is inversely dependent the number of iterations well as the instantaneous learning-rate μ4x, which in turn is determined from the change in the model-parameter values Ad,. This implies that, nearing convergence, when the change model- pardem-pr values is very small, the algorithm converges faster than vanilla-GD (or vanilla-GGD).
Since is assumed that the loss function (0) is convex and the function (0) is reducing every iteration for each paremeear i.e., ((x++1) < J(Ox) < J(Ax-1) <
J(0++1) S [J(0a)
= J(0k+1) - - S - -(O.))
Thus, it can be concluded that the algorithm converges with a rate O (+), given by
= J(0 J(O.) < 1: 2M
0p 0, 11
(37)
15


Reviews:
[{"review_id": "uOJW2U24gn", "reviewer": "Reviewer_D864", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 2, "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 a new adaptive learning rate first-order optimizer, where the learning rate is scaled by the inverse parameter difference between two recent iterations. Theoretical analysis based on regret bound is presented, and experimental results on image dataset / CNN models are conducted.", "summary_of_the_review": "I have low confidence of this review, and happy to take advices from other reviewers, and AC.\n\nUpdate: after carefully reading other reviews, I generally agree reviewer xzMY's comment, and appreciate his/her efforts on checking the correctness of proof. I lower down my score to clear reject.", "strength_and_weaknesses": "Pros:\nThe idea is easy to understand.\n\nCons:\n1. The notation is not presented very clearly. For example, the explaination of $K$ in eqn.(3) appears very lately.\n2. The idea is a little strange to me. In my understanding, the adaptive learning methods (including Nestrov accelerated momentum) should aim for estimate the Hessian to obtain an approximation of the best step-size in comparision with second-order methods. For example, the momentum term of NAG could be reformulated to the difference of gradients between two recent iterations, where is a reasonable approximation for the second-order information. However, it makes no sense to me that the difference of model parameters could do the similar thing, therefore I doubt the theoritical correctness of the proposed method.\n3. It's quite strange that only evaluating the training accuracy but not validation / test accuracy on real datasets, especially for stochastic optimization methods. If we only aim for training, then gradient decent should be the best method. Also, the training stability of the proposed method seems very badly, therefore I doubt the practical usage of the proposed method.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "i132ukhWaS", "reviewer": "Reviewer_LcE9", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\nThis paper proposes an adaptive learning rate method to improved the stochastic gradient descent algorithm by leveraging the difference of two consecutive iterations. More concretely, the authors proposes that the learning rate of each parameter should be inversely proportional to the difference between the current and the previous iteration of the this parameter. The authors claim the such an updating scheme, when combined with SGD, can converge under mild assumptions. Empirical studies also show that it can achieve lower training loss and better accuracy on CIFAR-10/100 and Tiny-ImageNet.", "summary_of_the_review": "The paper is not well written that it is hard to tell if the proof is correct. Besides, the idea is not very novel and the empirical study is not comprehensive either, making it less convincing that the proposed algorithm is effective.", "strength_and_weaknesses": "Strength:\n\n1. The idea is simple and easy to understand. It is also easy to implement.\n\nWeaknesses:\n\n1. There are a bunch of notation errors/overloading in the paper that make it hard to follow. Examples:\n    \n    1.1. Vectors should be in $\\mathbb{R}^L$ rather than $\\mathbb{R}$, e.g.,  $p, q \\in \\mathbb{R}$, $\\theta \\in \\mathbb{R}$, etc.\n    \n    1.2. The equation immediately after eqn (7) should be $J(\\theta^*)= \\arg\\min_\\theta J(\\theta)$. \n    \n    1.3. While eqn (8) uses $M_k$, the following sentence uses $M$. And there is no definition about $\\mu_k$ in the next sentence. \n    \n    1.4. \\beta is used for the Lipschitz constant above eqn (8), and then overloaded as the maximum eigenvalue of the input correlation matrix in eqn(9).\n\n2. Given the the notation systems are so messy, it is hard to believe the proof is correct.\n\n3. The algorithm involves parameters $K$ and $\\mu_0$, but there is no guidance on how to choose them.\n\n4. The empirical studies are not convincing either.\n\n    4.1. In Figure 2, the proposed algorithm converges obviously slower than quite a few other algorithms. Although it seems to converge to a point with lower loss, it is unclear why it is the case. Also, the proposed algorithm is unstable compared to others, as its curve is bumpy.\n    \n    4.2. The algorithm is only evaluated on three small image datasets. It is unclear if the conclusion can generalize to other domains/networks. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "XhKtehsHxJ", "reviewer": "Reviewer_xzMY", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "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 paper proposes an adaptive stochastic gradient method, which scales element-wise step sizes inversely proportional to the update magnitude in the previous step. A regret bound is provided and the method is evaluated on a number of neural network training tasks.", "summary_of_the_review": "In light of the weaknesses discussed above, I recommend rejecting this paper. The mathematical sections contain multiple severe errors (weakness 3-4) and the experimental comparison is not up to the standards that are expected of empirical work on optimization methods (weakness 6). I would also question the basic motivation for the proposed methods (weakness 1), but of course it is perfectly justifiable to just \"try out\" something.\n\nTo the authors, I want to say that my negative review is not meant to diminish your work or to discourage you from pursuing it further. The mathematical errors might be fixable and the experimental comparison can be improved (clear tuning protocol, multiple random seeds, report test performance).", "strength_and_weaknesses": "### Strenghts\n\n1) The paper follows a clear structure and is generally well-written. \n\n2) I like the illustration of the proposed method on the Rosenbrock function.\n\n### Weaknesses\n\n1) Generally, I find the motivation offered for the method unsatisfying. Some of the reasons used to motivate the method are not really substantiated. For example, on page 2, the paper states that the proposed algorithm avoids\n\"the suboptimal convergence due to very large or very small scaling of the learning rate.\"\nWhile this might have been some intuition guiding the authors, the do not offer any reason as to why very large or very small scaling is inherently bad. In fact, the literature on\nadaptive gradient methods probably argues that drastic step size differences in different coordinates are a _feature_ not a bug.\n\n2) The parametrization of the proposed algorithm is redundant. In Eq. (4), the hyperparameter\n$K$ could simply be subsumed into the \"global\" learning rate $\\mu_0$. (This also has some implications for the experimental comparison, see point 6.)\nOn the other hand,\none could imagine having an additional hyperparameter in the denominator.\nIf I were to experiment with an update of the proposed form, I would want to parametrize\nit as $a / (1 + b \\Delta)$.\n\n3) Neither the regret bound in in Eq. (8)\nnor its proof (Appendix A) make mathematical sense. The cumulative regret on the left-hand\nside of Eq. (8) is a scalar quantity. The right-hand side seems to be $k$-dimensional vector.\nIn the proof, Eq. (18) does not have any well-defined mathematical meaning.\n$J$ is a function of _all_ model parameters\n$\\theta\\in \\mathbb{R}^d$, so it is mathematically meaningless to plug in only the $i$-th model\nparameter $\\theta^{(i)}$.\nIt seems the authors want to assume some sort of decomposition across individual coordinates,\nbut this would certainly require additional assumptions beyond smoothness and convexity.\nEven assuming that some such decomposition exists, there are a more errors in the\nremainder of the proof.\nI'm not going to list all of them, but for example going from Eq. (25)-(26) is not\npossible and using Cauchy-Schwarz would introduce a norm around the gradient term.\n\n4) In Section 3.1.1, the paper states that the algorithm will converge if $\\mu_k< 1 / (2 \\beta)$\nwhere $\\beta$ is \"the maximum eigenvalue of the input correlation matrix\".\nThis statement is not applicable to the setting the paper is assuming (smoothness + convexity). It might hold for\nlinear least-squares regression, but if that is what the authors are referring to here,\nit should be stated very clearly.\n\n5) In the beginning of of Section 4.1, it is falsely stated that the Rosenbrock function is strictly convex.\n\n6) The experimental comparison has several shortcomings in my opinion. The base learning rate is\nset to the same value for _all_ methods. For the proposed method, the hyperparameter $K$\nis tuned (the tuning protocol employed is unclear). Since $K$ is simply a multiplier for the\nlearning rate (see comment 2) this amounts\nto an unfair comparison.\nFurthermore, the experiments seem to have been conducted with a single random seed.\nMultiple seeds should be used to gauge the variabilty of the performance.\nFinally, the paper compares _training_ loss and accuracy. While this is adequate from an\noptimization perspective, the potential users of the method will be more interested in the\nperformance on the test set.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "MwCFW5Nkca_", "reviewer": "Reviewer_Pa1W", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 proposed a new optimizer, which adapts the stepsize by $K/(1+abs(\\Delta \\theta))$ where $\\Delta \\theta$ is the update of the parameters. The authors proved the convergence of the proposed algorithm and conducted experimental validations.", "summary_of_the_review": "The proposed method is counter-intuitive, and the proof of convergence is only limited to deterministic convex objective functions, and the experimental validations are pretty naive.", "strength_and_weaknesses": "Strength:\nThe paper is overall easy to follow and well presented. The authors conducted analysis in both theory and validation on toy and real-world datasets.\n\nWeakness:\n1. The proposed method is actually counter-intuitive. If $abs(\\Delta \\theta)$ is large in dimension $I$, for SGD it means the gradient amplitude in dimension $i$ is large. I don't see why the update stepsize should be small in the $i-th$ dimension. \n2. The proof of convergence is restricted to convex objective functions, instead of the more general stochastic non-convex optimization setting. Therefore the results in pretty limited.\n3. Experimental validation on Cifar datasets is far from satisfactory. The authors should validate the proposed method in various tasks with different model architectures and datasets.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}]

Author rebuttal:

Decision: Reject