Step Size Optimization
Authors: Gyoung S. Na
Dongmin Hyeon
Hwanjo Yu
Venue:  (2020)
Keywords: Deep Learning
Step Size Adaptation
Nonconvex Optimization

Abstract: This paper proposes a new approach for step size adaptation in gradient methods. The proposed method called step size optimization (SSO) formulates the step size adaptation as an optimization problem which minimizes the loss function with respect to the step size for the given model parameters and gradients. Then, the step size is optimized based on alternating direction method of multipliers (ADMM). SSO does not require the second-order information or any probabilistic models for adapting the step size, so it is efficient and easy to implement. Furthermore, we also introduce stochastic SSO for stochastic learning environments. In the experiments, we integrated SSO to vanilla SGD and Adam, and they outperformed state-of-the-art adaptive gradient methods including RMSProp, Adam, L4-Adam, and AdaBound on extensive benchmark datasets.

Under review as a conference paper at ICLR 2020
STEP SIZE OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
This paper proposes a new approach for step size adaptation in gradient methods. The proposed method called step size optimization (SSO) formulates the step size adaptation as an optimization problem which minimizes the loss function with re- spect the step size for the given model parameters and gradients. Then, the step size is optimized based on alternating direction method of multipliers (ADMM). SSO does not require the second-order information or any probabilistic models for adapting the step size, so it is efficient and easy to implement. Furthermore, we also introduce stochastie SSO for stochastic learning environments. In the ex- periments, we integrated SSO to vanilla SGD and Adam, and they outperformed state-of-the-arr adaptive gradient methods including RMSProp, Adam, I---Adam, and AdaBound on extensive benchmark datasets.
INTRODUCTION
First-order gradient methods (simply gradient methods) have been widely used to fit model param- eters in machine learning and data mining, such training deep neural networks. In the gradient methods, step size (or learning rate) is one of the most important hyperparameters that determines the overall optimization performance. For this reason, step size adaptation has been extensively studied from various perspectives such as second-order information (Byrd et al. 20166] Schaul et al.) 2013), Bayesian approach (Mahsereci & Henning 2015). learning learn paradigm (Andrychow- icz et al. 2016). and reinforcement learning (Li & Malik 2017). However, they are hardly used in practice due lack of solid empirical evidence for the step size adaptation performance, hard im- plementation, or huge computation. For these reasons, some couristically-motivttee methods such as AdaGrad (Duchi al. (01T). RMSProp (Tieleman Hinton 2012). and Adam (Kingma & Bal 2013) are mainly used in practice to solve the large-scale optimization problems such as training deep neural networks.
Recently, two impressive methods, called L (Rolinek & Martius 2018 and AdaBdound (Luo et al, 2019). were proposed to efficiently adapt the step size in training of models, and showed some improvement over existing methods without huge computation. However, performance comparisons to them were conducted only on relatively simple datasets such as MNIST and CIFAR-10, 10, even though I.2 has several newly-introducee hyperparameters, and AdaBound needs manually-desgine bound functions. Moreover, L still requires about 30% more execution time, and AdaBound lacks the time complexity analysis or empirical results on training performance against actual execution time.
This paper proposes a new optimization-basee approach for the step size adaptation, called step size optimization (SSO). In SSO, the step size adaptation is formulated as sub-optimization problem of the gradient methods. Specifically, the step size is adapted to minimize linearized loss function for the current model parameter values and gradient. The motivation of SSO and the justification for the performance improvement by SSO is clear because directly optimizes the step size to minimize the loss function. We also present a simple and efficient algorithm to solve this step size optimiza- tion problem based on the alternating direction method of multipliers (ADMM) (Gabay & Mercier, 1976). Furthermore, provide a practical implementation of SSO the loss function with L2 regularization (Krogh & Hertz 1992) and stochastic SSO for the stochastic learning environments.
SSO does not require the second-order information (Byrd et al. 2016 Schaul et al. 2013) and any probabilistic models (Mahsereci & Henning 2015) to adapt the step size, so it is efficient and easy to implement. We analytically and empirically show that the additional time complexity of SSO in

---

Under review as a conference paper at ICLR 2020
the gradient methods is negligible in the training of the model. To validate the practical usefulness of SSO, we made two gradient methods, SSO-SGD and SSO-Adam, by integrating SSO to vanilla SGD and Adam. In the experiments, compared the training performance of SSO-SGD and SSO- Adam with two state-of-the-arr step size adaptation methods (I.2 and AdaBdound) as well as the most commonly used gradient methods (RMSProp and Adam) extensive benchmark datasets.
2 STEP SIZE OPTIMIZATION
2.1 PROBLEM FORMULATION
The goal of step size optimization (SSO) is to find the optimal step size that minimizes the loss function with respect to the step size 1) as:
= arg min J(0 - 1/v) + 02(0 -1/))
(1)
where T is the loss function; Ω is a regularization term; 0 is the model parameter; and v is the gradient for updating 0. Note that an optimizer-dependent gradient such as the moving average of the gradients in Adam. As gradient methods update the model by moving to the opposite direction of the gradient (0 0 7jv), the loss function [(0) and the regularization term (2))) can be expressed T r7v) and S2(0 ryv). respectively. In real-world problems, however, directly solving the optimization problem in Eq. (T) infeasible due to the severe nonlinearity of J. To handle this difficulty, first, we linearize T around 0 as:
J(e nT) = (()) + (VoJ)" - - (V--) = - -
(2)
where g- VoJ is the true gradient. Note that is the same g in vanilla gradient method.
However, in order for the linearization of Eq. 2 to be valid, should be sufficiently small. To this end, introduce incquality constraint for the upper bound of 7). Thus, the optimization problem of SSO is given by:
17 arg min [(0)- ng""' + 2(0 (v))
(3)
0SMSE
where e is a positive hyperparameter that defines the upper bound of the step size. That is, SSO adapts the step size by solving the constrained optimization problem in Eq.
2.2 AUGMENTED LAGRANGIAN FOR STEP SIZE OPTIMIZATION PROBLEM
The augmented Lagrangian a widely used optimization technique to handle constrained opti- mization problem by transforming it into unconstrained problem. The objective function in the augmented Lagrangian is defined based on equality constraints. For this reason, we need to trans- form the optimization problem with the inequality constraints in Eq. 33) the problem with the equality constraints by introducing slack variables 81 and 82 as:
1y arg min [(0) 1//g" 2(0 - 1/v)
(4)
7
8. L. 1 - 81 0, 11 82
0, 82 > 0.
Finally, the augmented Lagrangian for the problem of Eq. given by:
Cn A1, )2, 81, S2) J(0) ug" 22 vπv A1 $1) -2e(e -82)
/ (m 81)² 1/1 2
)
(5)
2
where A1 2 0 and Xg 2 are dual variables, and ب is a balancing parameter between the objective
function and the penalty term for the equality constraints. In general, is simply set to be gradually increased in optimization process to guarantee the feasibility for the equality constraints Gabay & Mercier 1976 Ouyan et al. 2013).
2

---

Under review as a conference paper at ICLR 2020
2.3 OPTIMIZATION
In this section, we describe the optimization algorithm to find the optimal step size that minimizes the augmented Lagrangian in Eq. (5) using ADMM. In mathematical optimization and machine
learning, ADMM has been widely used to solve the optimization problem containing different types of primal variables x, with the equality constraints such as:
x, z arg min f(x) g(z)
(6)
S. Ax + Bz c.
where A and are coefficient matrices of the equality constraints, and e is a constant. ADMM iteratively finds the optimal variables by minimizing the augmented Lagrangian for the problem in Eq. (6). denoted by L,((x, z, A), because directly solving the problem can be nontrivial. Specifically, optimizes primal and dual variables in one-sweep Gauss-Seidel manner: C (x, z, X) is minimized with respect to the primal variables x and z alternatively for the fixed dual variable A. Then, Cy (x, z, A) is minimized over the dual variable À for the fixed primal variables
ADMM (Algorithm
and z.
Algorithm 1: ADMM
Output: Optimized primal variables x and z
1 1= 0, A = 0, fM
repeat
x((+1) +- arg min (x, ((1))
((++1) t arg min, L (x(t+1), (())
( + ( ((A((t+1) (+((++)
Increase f I t ++1
until x, z, À converged;
The step size optimization problem of Eq. 4 is equality constrained problem, and also has two kinds of primal variables, the step size 7 and the slack variables $1, That is, for the primal variables 17 and 81, S2, the step size optimization problem of Eq. (4) has the same structure as
the problem in Eq. 6 where f(n) = [()) ng"v v Si 7yv, g(S1, 82) = 0, and the equality constraints are 1 81 and 6-17-50 $2 Thus, the primal variables of the step size optimization problem v), 81, 82, and the dual variables X1, A2 can be optimized by ADMM as:
n (++1) t arg min Cn (0) 82
(t)
(() (0)).
(7)
31
((+1) + max
0, arg min C. (1+1)
81, A {(01
(0)
(8)
(t+1)
0, arg min C, (1) (++1) (1+1)
82, (0) 110)
82
mar
#2
X ((+1) = maa {0, 11 - ((1 - -8 ((+1))]
(10)
X (1+1) max f0, 11 ule (1+1) 82 (t1))}
(11)
Note that the max operation with zero is applied to Eq. constrains of the slack and the dual variables.
for satisfying the nonnegative
Algorithm 2 shows the overall process of the gradient descent method with SSO to optimize 0. In line 3, the true gradient g and the adaptive gradient are computed, and the augmented Lagrangian C (7, $1, $2, A1, A2) for optimizing the step size is determined based on the current gradients. Then, the step size is optimized for currently given model parameters and gradients by iteratively mini- mizing C, (17 $1, $2, '₁ A2) in line 533 Finally, 0 is updated with the optimized step size and the adaptive gradient in line 14.
3

---

Under review as a conference paper at ICLR 2020
Algorithm 2: Gradient descent method with SSO
Input : Upper bound of the step size: é E (0, 1]
Output: 0
=0 repeat
Compute g g= VeJ and v to determine Ln 81, 82, 21)
t= s- - 0, $2 0, A1 0, 11
repeat
rf(++1 arg min, (n 81 (1) 11) 1100 ,1())
8) c((+1) mar
arg min, (1 81, (1)
82 (1+1) f max
0. arg min, (n [1+1] (1) (++1) 92: 21 (1) (oss
1 ((+1) + max
0, \ (1 - 81 ((+11)}
A2 ((+1) f max
0, 1 ule - -1((+1) - (1+1) {
10
11
Increment μ 6- 1+1
12
until converged;
@(++1) ((k)
14
15
k + k +1
16
until converged;
2.4 UPPER BOUND DECAY
In this section, we additionally introduce the upper bound decay for SSO. Since the shape of the augmented Lagrangian for SSO can be changed by the regularization term Ω2 the convergence prop- erty of the gradient methods with SSO may be different for each different regularization term. To overcome this problem, we devise the upper bound decay method and integrate it into SSO. One possible implementation of the upper bound decay is
the exponential decay follows.
(k+1) + (k)
(12)
where 7 E (0, 1) is decay factor. That is, is exponentially decreased over the training.
similar to the step size decay, but there a big difference. The upper bound decay indirectly reduces the step size by decreasing the upper bound of the step size instead of reducing it directly. That is. SSO with the upper bound decay automatically provides an optimal step size that will be gradually reduced guarantees that the step size converges to zero regardless of the shape of the augmented Lagrangian for the valid decay factors such 7 1) Eq (2). Thus, the upper bound decay is more flexible than the step size decay and can be regarded as a generalized method of the step size decay. One main advantage of SSO over the existing methods is that can exploit such upper bound decay. In SSO with the upper bound decay, the initial upper bound (0)) is hyperparameter.
the training. Furthermore, SSO with the upper bound decay always
2.5 PRACTICAL IMPLEMENTATION SSO WITH L2 REGULARIZATION
In this section, we derive SSO with the T-2 regularization that is the most widely used regularization technique and also provide practical implementation of the gradient method with SSO.
2.5.1
UPDATE RULE
With the L2 regularization term, the augmented Lagrangian of the step size optimization problem is given by:
8
Cn A2, = -(()) 'g''v
110
nvll - 10--v|13
>1 $1) dolc 52)
2
+ 1/ (m
81 )1
+
2 =2)²
(13)
4

---

Under review as a conference paper at ICLR 2020
where 3 is positive hyperparameter of the L2 regularization for balancing the loss function and the we can optimize the step size using the
regularization term. By applying ADMM in Algorithm following update rules:
g'v + Br 0 11
( + u[s
(1) 82 + +e)
((+1)
(14)
Br 24
x(1)
81
(1+1)
max
0, 11 ((++1)
(15)
1
(()
52
(t-1) max 0, rf(+1)
2
(16)
p
Note that the update rule for the dual variables x and X2 are the same as Eq. 10 and because the update rules of the dual variables are independent of the loss function and the regularization in SSO. More precisely, the update rules of the dual variables depend only on the equality constraints for the step size.
2.5.2 CONVERGENCE
If the optimal step size exists within an range e0, the slack variables converge s1 + 7 and 82 - c- when ADMM SSO sufficiently iterated (f + oo). Thus, the step size vj converges
to some value as:
(++)) g g 8 ( 2 (p
2pm
17 (t)
(17)
3y v + 2p
2μ
In contrast, if the optimal step size exists over the upper bound, the step size may converge near the upper bound (17 c) in ADMM. Thus, the slack variables converge as $1 + and 82 + 0, and the step size consequently converge the upper bound as follows.
g" 3 0 (4) X +uEE
2pe
(++1
C.
(18)
T v + 2/1
211
Thus, the step size always converges ADMM of SSO.
Unfortunately, the second case (1) + e) is not the desired result in which the model is sufficiently trained because a relatively small step size required in this situation make the gradient methods converge. However, it is not problem in SSO with the upper bound decay because the upper bound e must be reduced by the decay method over the training.
STOCHASTIC SSO
In this section, we describe SSO for the stochastic learning environments and also provide stochas- tie SSO with L2 regularization. The optimization problem in the stochastic environments can be formulated on mini-batch with respect to the step size as follows.
N
(k+1) arg min uSnse N
Σ J,(000) - ())()) + (2((()) - (A)))))
(19)
where J, is the loss function for the 7th sample in the mini-batch. This problem can be rewritten as an optimization problem with a conservative penalty term as (Ouyan et al. 2013 Li et al. 2014):
(k)
(k+1) arg min
N Σ T,(0(() ())) (A()()) ())()))
(20)
OS
Note that the conservative penalty term introduced to prevent undesired large change in the model parameters as mini-batch changes. The conservative penalty term can be rewritten with respect to the step size as:
1 (k)
( D
[|0(s)
(0()) ny (k)(k)
(k)) TT(k).
(21)
"
5

---

Under review as a conference paper at ICLR 2020
Thus, derive the optimization algorithm for n ( in stochastic environments by applying the linearization and ADMM to the problem in Eq. 22 as described in Section 2.1 2.3
In addition, provide the update rule of stochastic SSO with L2 regularization for the practical implementation of Similar to the update rule the deterministic SSO with L2 regularization in Section 2.5.1I the update rule for r of stochastic SSO with L2 regularization is given by:
(k+1) N Ei=18 Bi v(k) v(8)² (()) + (p(K)) O + 1
1 + m()
+
(22)
By(k)² (k)) 2/u
Note that the update rule of the slack variables are the same as Eq. depend only on the constraints of the problem.
15 and 16
because they
TIME COMPLEXITY ANALYSIS
Due to the sub-optimization process for the step size adaptation of SSO, a gradient method with SSO inevitably requires additional complexity. In this section, we analyze the time complexity of the gradient method with SSO and show that the additional time complexity of the gradient method with SSO is almost the same as the vanilla gradient method in large-scale optimization problems such as training deep neural networks. The empirical time complexity analysis over the actual execution time will be conducted in the experiment section.
The time complexity of a gradient method with SSO is O(TV+Td-TT) where T is the number of epochs in the gradient method: v the total computation for model updates such as the forward and the backward steps in neural networks; d is the number of model parameters; and I is the number of iterations for updating 7 (line 5~~33 Algorithm Z The additional time complexity from SSO is O(Td + TT). The time complexity ( comes from the dot product operations to compute g" v, vT 0, and vTv. Another time complexity O(T1) comes from the iterative optimization process of ADMM for adapting 7). Practically, however, O(T'b - Td + TI) ((Tτ)) because the dot product operation can be accelerated significantly by GPU, and O(Td+TI) is negligible compared to (T when we sophisticated model for high representation ability, such as deep neural network. Thus, in real-world applications, the time complexity of the gradient method with SSO is approximately the same ()T)), which is the time complexity of the vanilla gradient method. In the experiment section, this time complexity analysis for SSO will be also demonstrated empirically on several real-world datasets.
EXPERIMENTS
In the experiments, we validated the effectiveness of SSO gradient-based optimization. To this end, we generated two gradient methods with stochastic SSO using the upper bound decay (1) vanilla SGD with SSO (SSO-SGD) and (2) Adam with SSO (SSO-Adam), and then their optimiza- tion performance was compared with the state-of-the-art gradient methods: RMSProp: Adam; 3) L Addam;; 4) AdaBound. We specified the optimization problem as training deep neural net- works because is the most appealing and challenging problem using gradient methods. To train deep neural networks, cross-entropy loss with L2 regularization is used as a loss function.
We conducted the experiments on four well-known benchmark datasets: MNIST, SVHN, CIFAR- 10, and CIFAR- 100 datasets. For MNIST dataset, convolutional neural network (CNN) was used. For CIFAR and SVHN datasets, ResNet (He al.) (016) was used. For all datasets, we measured the training loss and the highest test accuracy during the training. We reported the mean and the standard deviation of the highest accuracies by repeating the training several times. Specifically, repeated the training 10 times for MNIST dataset and 5 times for the other datasets. Table summarizes the experiment results, and detailed explanations of the results for each dataset will be provided in the following sections.
For each gradient method, we selected the best initial learning rate using a grid search in a set of (0.1, 0.05, 0.01. 0.005, 0.001} for all datasets. For the other hyperparameters of Adam, such as the exponential decay rate Adam, we followed the settings of the original paper of Adam (Kingma & Ba 2015). To set the additional hyperpameters of 1-1-ddam and the bound functions of AdaBound,

---

Under review as a conference paper at ICLR 2020
Table 1:
Test accuracy in percent of the neural networks trained by each gradient method. The highest test accuracy measured during the training is reported.
Gradient method
MNIST
SVHN
CIFAR-10
CIFAR-100
RMSProp
98.82 0.04
94.51 0.14
89.13 0.17
64.61 0.09
Adam
98.89 + 0.04
94.96 + 0.13
89.95 + 0.34
67.35 + 0.18
-
99.31 0.05
95.68 0.09
0.21
66.79 = 0.81
AdaBound
99.28 + 0.03
95.48 + 0.12
91.46 0.21
69.71 0.16
SSO-SGD
99.29 + 0.05
96.41 + 0.08
94.43 0.15
74.96 0.36
SSO-Adam
99.33 + 0.04
95.75 + 0.06
92.53 + 0.12
70.82 = 0.41
we used the recommended setting in their original papers (Rolinek & Martius 2018 Luo et al., 2019). For MNIST dataset, the initial upper bound of SSO, c!0), was set to 0.5. For the other datasets, c(0) was fixed to The decay factor the upper bound decay, 7 was fixed to 0.95 for all datasets. The number of iterations for optimizing the step size in SSO was fixed to 20 (I 20). We selected the best regularization coefficient (3) using a grid search for each gradient method on for all datasets. The batch size was fixed to 128 for all datasets. For MNIST dataset, exploited a commonly used architecture of CNN with two convolution layer and one fully-connected output layer. For SVHN and CIFAR datasets. we used the ResNet with three residual blocks and one fully-connected output layer (ResNet-18). All experiments were conducted on NVIDIA GeForce RTX 2080 Ti. We used PyTTrch to implement SSO and the author's source code for L--Adam and AdaBound The source code of SSO and the experiment scripts are available at GitHubURL Open after the review).
5.1 DIGIT RECOGNITION
MNIST dataset is widely used benchmark dataset for digit recognition. It contains 60,000 training instances 10,000 test instances of 28x28x size from 10 classes. As shown Fig. (a), I. Adam, AdaBound, SSO-SGD, and SSO-Adam rapidly reduced the training loss to zero on MNIST dataset. Although SSO-Adam showed the highest test accuracy, other gradient methods also showed similar accuracies because MNIST dataset is too simple and easy to fit the model (easy to achieve 99% test accuracy). For this reason, to accurately evaluate the effectiveness each method, we compared the performance SVHN dataset, which is also widely used benchmark dataset for digit recognition and more realistic.
100
0.200
0.175
99
0.150
AdsBound 250 303
Test accuracy
S50 Adam
0.125
98
Training
0.100
0.075
Adam
0.050
96
Li-Adbm
AdaBound
0.025
0.000
95
10
20
30
40
50
10
20
30
40
50
Epoch
Epoch
(a) Training loss over epoch
(b) Test accuracy over epoch
Figure
Training progress of CNNs on MNIST dataset.
thups://gttuh..cmm// www.///aa//dddddddddaad

---

Under review as a conference paper at ICLR 2020
0.6
masppmp Adam 14-aders
100.0
0.5
97.5
Test accuracy
95.0
0.4
502-Adarm
Test accuracy
92.5
90.0
0.2
87.5
85.0
L4-Aca
Adattound
82.5
560-63D
300 A3am
0.0
80.0
20
40
60
80
100
20
40
60
80
100
Epcch
Epoch
(a) Training loss over epoch
(b) Test accuracy over epoch
Figure 2: Training progress of ResNets SVHN dataset.
SVHN dataset contains 73,257 training instances and 26,032 test instances of x2x32x3 size from 10 classes. As shown in Fig. (a)), I.'-Adam, SSO-SGD, and SSO-Adam rapidly reduced the training loss to zero on SVHN dataset. Furthermore, both SSO-SGD and SSO-Adam outperformed all state-of-the -trt-art competitors in the test accuracy. In the experiments, although L -ddAda, SSO- SGD, and 3SO-Adam all rapidly reduced the training loss, SSO-SGD and SSO-Adam showed better generalization performance than L*-Adam.
5.2 OBJECT CLASSIFICATION
CIFAR datasets contain 50,000 training instances and 10,000 test instances 32x32x3 size. CIFAR-10 and CIFAR-100 100 contain 10 and 100 categories (classes), respectively. We also used ResNet with three residual blocks and one fully-connected layer for CIFAR datasets.
1.0
95
90
Lt-Adars
0.8
AdoBound
Test accuracy
accuracy
85
0.6
80
75
0.4
RAtSirop
70
Adam
0.2
65
550 5GD
AS0m
60
20
80
60
100
Epoch
Epoch
(a) Training loss epach
(b) Test accuracy over epoch
Figure 3: Training progress of ResNets on CIFAR-10 10 dataset.
On CIFAR-10 10 dataset, Lt, SSO-SGD, and SSO-Adam also rapidly reduced the training loss to zero (Fig. a). Furthermore, SSO-SGD and SSO-Adam outperformed all competitors the test
accuracy (Fig. a). Especially, SSO-SGD achieved about 3% improvement the test accuracy compared to Bound that showed the highest test accuracy among the competitors.
As shown in Fig. (b), both SSO-SGD and SSO-Adam outperformed all ofate-of-the-tar com- petitors the test accuracy again. In particular, SSO-SGD achieved 5% improved test accuracy compared to I. A.mm that showed the highest test accuracy among the competitors. In this experi-
8

---

Under review as a conference paper at ICLR 2020
3.0
80
masProp
75
2.5
Ldsiders
Adiellondd
70
accuracy
2.0
accuracy
65
1.5
60
55
10to/rap
50
Acam
0.5
AcoBourd
45
550-50D
500-/cam
40
50
100
150
200
150
200
Epech
Epoch
(a) Training loss epoch
Test accuracy over epoch
Figure 4: Training progress of ResNets on CIFAR- 100 dataset.
ment, SSO-SGD and SSO-Adam showed better generalization performance than I'-Adam because stochastic SSO is designed to the stochastic learning environments.
5.3 TRAINING PERFORMANCE OVER EXECUTION TIME
In this experiment, we measured the test accuracy over actual execution time to evaluate the useful- ness of each method. Fig. 5 shows the results of the experiment on SVHN and CIFAR 100 datasets.
100
80
75
70
Test accuracy
Test accuracy
90
65
My
bo 1
85
60
55
RMSPPoo
50
Adam
Ad-Adam
75
acasound
SSC 590
45
350-300
S50 Adtam
70
40
1000
2000
3000
4000
5000
2000
4000
6000
Execution time (sec)
Execution time (sec)
(a) Test accuracy on SVHN dataset
(b) Test accuracy on CIFAR100 dataset
Figure 5: Test accuracy the execution time.
The experiment results are similar to the results in Fig. (b) and 4 It shows that SSO is as efficient existing step size adaptation methods. Furthermore, quantitatively. SSO-SGD and SSO-Adam required about 5,500 seconds execution time for 100 epochs like RMSProp and Adam, but L Adam required about 9,000 seconds execution time that is 30% higher than the execution time of SSO-SGD and SSO-Adam. On CIFAR- 100 dataset, SSO-SGD and SSO-Adam also required about 8,500 seconds execution time for 200 epochs like RMSProp and Adam, but I. Addm spent about 13,000 seconds.
5.4 INITIAL UPPER BOUNDS AND TRAINING PERFORMANCE
We checked the training performance on MNIST dataset by change the initial upper bound ( to measure the sensitivity of SSO for the hyperparameter. Fig. shows the experiment results.

---

Under review as a conference paper at ICLR 2020
99.4
99.2
99.0
accuracy
98.8
96.6
98.4
96.2
98.0
10
20
30
40
50
Epoch
Figure 6: Changes on the test accuracy with the different initial upper bounds on MNIST dataset.
As shown in the result, SSO-Adam showed consistent test accuracy in 99.2%~~99.35%% for all initial upper bounds in {0.5, 0.6, 0.7, 0.8, 0.9, 1.0).
REFERENCES
Marcin Andrychowicz, Misha Denil, Sergio Gomez Colmenarejo, Mathew W. Hoffmman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando de Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems (NIPS), 2016.
R. H. Byrd, L. Hansen, Jorge Nocedal, and Singer. stochastic quasi-newton method for large-scale optimization. SIAM Journal on Optimization, 26:1008- 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research (JMLR), 12:2121-2159, 2011.
Daniel Gabay and Bertrand Mercier. dual algorithm the solution of nonlinear variational problems via finite element approximation. Computes and Mathematics with Applications, 2: 17-40, 1976.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2015.
Anders Krogh and John A. Hertz. A simple weight decay can improve generalization. Conference on Neural Information Processing Systems (NIPS), 1992.
Ke Li and Jitendra Malik. Learning to optimize. International Conference on Learning Representa- tions (ICLR)), 2017.
Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J. Smola. Efficient mini-batch training for stochastic optimization. ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2014.
Liangehen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. International Conference on Learning Representations (ICLR), 2019.
Maren Mahsereci and Philipp Henning. Probabilistic line searches for stochastic optimization. In Advances in Neural Information Processing Systems (NIPS), 2015.
Hua Ouyan, Niao He, Long Q Tran, and Alexander Gray. Stochastic alternating direction method of multipliers. International Conference on Machine Learning, 2013.
Michal Rolinek and Georg Martius. L4:
Practical loss-based stepsize adaptation for deep learning. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
10

---

Under review as a conference paper at ICLR 2020
Tom Schaul, Sixin Zhang, and Yann LeCun. No more pesky learning rates. Proceedings of Machine Learning Research (PMLR), 28:343-351, 2013.
T. Tieleman and G. Hinton. Rmsprop: Divide the gradient by running average of its recent magni- tude. Coursera: Neural Networks for Machine Learning, 2012.
A APPENDIX: OPTIMIZED STEP SIZE ON MNIST DATASET.
In this experiment, we measured the optimized step size of SSO rate for each epoch. We used SSO- Adam with the upper bound decay. Since the step size adaptation executed by the number of mini-batches for each epoch, we presented maximum, mean, and minimum of the optimized step size for each epoch. Fig. shows the optimized step sizes for each epoch. As shown the result, the learning rate is strictly optimized within [0, e] and gradually reduced over the epochs. Note that the current upper bounds are not shown because the maximums of the optimized step sizes overlap them in Fig. 7 (a).
upper bound
upper
Optimized step size
0.4
Optimized step size
0.4
0.2
0.2
0.0
10
20
30
40
50
10
20
30
40
50
Epoch
Epoch
(a) Optimized step size over the epochs
(b) Optimized step size over the epochs without presenting the maximum
Figure 7: Maximum, mean, and minimum of the optimized step sizes for each epoch MNIST dataset.
11


Reviews:
[{"review_id": "HkxuABPC5S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new step size adaptation in first-order gradient methods. The proposed method establishes a new optimization problem with the first-order expansion of loss function and the regularization, where the step size is treated as a variable.  ADMM is adopted to solve the optimization problem.\n\nThis paper should be rejected because (1) the proposed method does not show the convergence rate improvement of the gradient method with other step sizes adaptation methods. (2) the linearization of the objective function leads the step size to be small ($0<\\eta<\\epsilon$), which could slow down the convergence in some cases. (3) the experiments generally do not support a significant contribution. In table 1, the results of the competitor are not with the optimal step sizes. The limit grid search range could not verify the empirical superiority of the proposed method.\n\n\nMinor comments:\nThe y-axis label of (a) panel in each figure is wrong. I guess it should be \"Training loss \".", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Bkecwky9KH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "First, I would like to point out that there has not been a conclusion or discussion section included, therefore the paper appears to be incomplete.\nAside from this the main contribution of the paper is a study on optimising the step size in gradient methods. They achieve this through the use of alternating direction method of multipliers. Given all the formulations provided, it appears as if this method does not rely on second order information or any probabilistic method.\nAn extension of the proposed method covers stochastic environments.\nThe results demonstrate some promising properties, including convergence and improvements on MNIST, SVHN, Cifar-10 and Cifar-100, albeit marginal improvements.\nAlthough the results appear to be promising the overall structure of the paper and the method presented are based upon established techniques, therefore the technical contribution is rather limited.\nI have read the rebuttal and answered to some of the concerns of the authors.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is rejected based on unanimous reviews.
Decision: Reject