A straightforward line search approach on the expected empirical loss for stochastic deep learning problems
Authors: Maximus Mutschler
Andreas Zell
Venue:  (2021)
Keywords: Empirical Optimization
Expected Loss
Line Search

Abstract:    A fundamental challenge in deep learning is that the optimal step sizes for update steps of stochastic gradient descent are unknown. In traditional optimization, line searches are used to determine good step sizes, however, in deep learning, it is too costly to search for good step sizes on the expected empirical loss due to noisy losses. This empirical work shows that it is possible to approximate the expected empirical loss on vertical cross sections for common deep learning tasks considerably cheaply. This is achieved by applying traditional one-dimensional function fitting to measured noisy losses of such cross sections. The step to a minimum of the resulting approximation is then used as step size for the optimization. This approach leads to a robust and straightforward optimization method which performs well across datasets and architectures without the need of hyperparameter tuning.


Under review conference paper ICLR 2021
A STRAIGHTFORWARD LINE SEARCH APPROACH ON THE EXPECTED EMPIRICAL LOSS FOR STOCHASTIC DEEP LEARNING PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
A fundamental challenge in deep learning is that the optimal step sizes for update steps of stochastic gradient descent unknown. In traditional optimization, line searches are used to determine good step sizes, however, in deep learning, it is too costly to search for good step sizes on the expected empirical loss due to noisy losses. This empirical work shows that it is possible to approximate the expected empirical loss on vertical cross sections for common deep learning tasks consid- erably cheaply. This is achieved by applying traditional one-dimensional function fitting measured noisy losses of such cross sections. The step minimum of the resulting approximation is then used as step size for the optimization. This ap- proach leads to a robust and straightforward optimization method which performs well across datasets and architectures without the need of hyperparameter tuning.
INTRODUCTION AND BACKGROUND
The automatic determination of an optimal learning rate schedule to train models with stochastic gradient descent or similar optimizers is still not solved satisfactorily for standard and especially new deep learning tasks. Frequently, optimization approaches utilize the information of the loss and gradient of single batch to perform an update step. However, those approaches focus on the batch loss, whereas the optimal step size should actually be determined for the empirical loss, which is the expected loss over all batches. In classical optimization line scarches commonly used to determine good step sizes. In deep learning. however, the noisy loss functions makes impractically costly to search for step sizes on the empirical loss. This work empirically revisits that the empirical loss has simple shape in the direction of noisy gradients. Based on this information, it is shown that the empirical loss can easily fitted with lower order polynomials in these directions. This is done by performing a straightforward, one-dimensional regression on batch losses sampled in such a direction. It then becomes simple to determine a suitable minimum and thus good step size from the approximated function. This results in a line search on the empirical loss. Compared to the direct measurement of the empirical loss on several locations, our approach is cost-efficient since it solely requires sample size of about 500 losses to approximate cross section of the loss. From a practical point of view this is still too expensive determine the step size for each step. Fortunately, it turns out to be sufficient to estimate a new step size only a few times during a training process, which, does not require any additional time due to more beneficial update steps. We show that this straightforward optimization approach called ELF (Empirical Loss Fitting optimizer), performs robustly across datasets and models without the need for hyperparameter tuning. This makes ELF a choice to be considered in order to achieve good results for new deep learning tasks out of the box.
In the following will revisit the fundamentals of optimization in deep learning make our approach easily understandahle. Following Goodfellow et al.) (2016), the aim of optimization deep learning generally means to find a glohal minimum of the true loss (risk) function Lirue which is the expected loss over all elements of the data generating distribution Pdota:
Lirue (0) = E(x.u) (xf(x; 0),
(1)
where L is the loss function for each sample (x, v). 0 are the parameters to optimize and f the model function. However, Pdato usually unknown and need use an empirical approximation Pdata-

---

Under review as conference paper ICLR 2021
which is usually indirectly given by a dataset Due to the central limit theorem we can assume Pdato to be Gaussian. In practice optimization is performed on the empirical loss Lemp:
Lempl (0) ((x.))- L(f(x:0).))
Σ (x.)lTT
0).
[T]
An unsolved task is to find a global minimum of Ltree by optimizing on Lemp if [T] is finite. Thus, we have to assume that small value of Lemp will also be small for Lerue- Estimating Lemp is impractical and expensive, therefore we approximate it with mini batches:
Chatch (8, B)
Σ
L(f(x;0):))
(X.))EBCT
where B denotes a batch. We call the dataset split in batches Thatch. We now can reinterpret Lemp, as the empirical mean value over a list of losses L which includes the output of Cantor (f, B) for each batch B:
Lemp (f) =
1
Σ
Lbatch (0,
(4)
[lL]
vertical cross section (s) of (0) in the direction through the parameter vector 0g is given by
temp(s: ; lg d) Lemp(0 + .d)
(5)
For simplification, we refer to as line function or cross section. The step size to the minimum of (emp(s) called Smin-
Many direct and indirect line search approaches for deep learning are often applied on Chatch (0, B) (Mutschler & Zell (2020). Berrada et al.] (2019). Rolinek & Martius) (2018), Baydin et al. ( al. (20T9)). Mutschler & Zell (2020) approximate an exact line search, which implies estimating the global minimum line function, by using one-dimensional parabolic ap- proximations. The other approaches, directly or indirectly, perform inexact line searches by estimat- ing positions of the line function, which fulfill specific conditions, such as the Goldberg, Armijo and Wolfe conditions (Jorge Nocedal (2006).. However, Mutscchlrr & Zell (2020) empirically suggests that line searches on Lhasch are not optimal since minima of line functions of Lhutch are not always good estimators for the minima of line functions of Cemp. Thus, it seems more promising to perform a line search on Lemp. This is cost intensive since we need to determine L fx 0n + s-). d)).) 3/ for all (x, y) E T for multiple of line function. Probabilistic Line Search (PLS) (Mahsereci & Hennig (2017) addresses this problem by performing Gaussian process regressions, which result in multiple one dimensional cubic splines. In addition, a probabilistic helief over the first (= Armija condition) and second Wolfe condition is introduced to find good update positions. The major drawhack of this conceptually appealing but complex method is, that for each batch the squared gradients of each input sample have to be computed. This is not supported by default by common deep learning li- braries and therefore has to be implemented manually for every layer in the model, which makes its application impractical. Gradient-only line search (GOLS1) (Kafka & Wilke (2019)) pointed out empirically that the noise directional derivatives in negative gradient direction is considerably smaller than the noise of the losses. They argue that they can approximate a line search on Lemp by considering consecutive noisy directional derivatives. Adaptive methods, such as Kingma & Ba (2014) Luo et al. (2019) Reddi et al. (2018) (0018)(Ln Liu al. (2019) Tieleman Hinton (2012) Zeiler(2012) Robbins & Monro (195T) concentrate more on finding good directions than on optimal step sizes. Thus, they could benetit from line search approaches applied on their estimated directions. Second order methods. such as Berahas et al.] (2019) Schraudolph et al. (2007) Martens & Grosse (2015) Ramamurthy & Duffy (2017) Botev et al. (2017) tend to find better directions but are generally too expensive for deep learning scenarios.
Our approach follows PLS and GOLSI by performing line search directly Lemp- We regression on multiple Lrotter(B (fg + s. d, B) values sampled with different step sizes s and different batches B, to estimate a minimum of a line function of Lemp in direction d. Consequently, this work further step towards efficient steepest descent line searches on Cemp. which show linear conver- gence on any deterministic function that is twice continuously diffcrentiable, has a relative minimum and only positive eigenvalues of the Hessian at the minimum (see Luenberger et al. (1984)). The details well the empirical foundation of approach are explained in the following.

---

Under review conference paper ICLR 2021
250 AM
Figure Distributions over all batch losses Leatch (blue) consecutive and representative sections during training process ResNet32 on CIFAR-IO. The empirical loss Lemps is given in red, the quartiles in black. The batch loss, whase negative gradient defines the search direction, is given in green. See Section 2.1 for interpretations.
2
OUR APPROACH
2.1 EMPIRICAL FOUNDATIONS
Xing al. (2018) Mutschler & Zell 2020); Mahsereci & Hennig (2017); Chac & Wilke (2019)
showed empirically that line functions Liatch in negative gradient directions tend to exhibit a simple shape for all analyzed deep learning problems. To get an intuition of how lines of the empirical loss in the direction of the negative gradient tend to behave,
tediously sampled Chuteh (0, + -----ee, Vo, Chatos B,)), B) for 50 equally distributed between -0.3 and 0.7 and ev- ery IB E 'T for a training process of a ResNet32 trained on CIFAR-I0 10 with a batch size of 100. The results are given in Figure
The results lead to the following characteristies:
Lemp has simple shape and can be approximated well by lower order polynomials, splines or fourier series. 2. kemp does not change much over con- secutive lines. 3. Minima of lines of Llateh be shifted from the minima of lemp lines and can even lead to update steps which increase Lemp. Characteristic 3 consolidates why line searches on Demp are to be favored over line searches on Lbatch- Although we derived these findings only from one training process, can assure, by analyzing the measured point clouds of our approach, that they seem be valid for all datasets, tasks, and models considered (see Appendix D).
2.2 OUR LINE SEARCH ON THE EXPECTED EMPIRICAL LOSS
There are two major challenges to be solved in order to perform line searches on Lemp:
1. To measure (smp(s; (s; 6 d) it is required to determine every L(f(xx; Og + d). v) for all line.
(x, y) T for all steps sized
For a good direction of the line function one has to know VoLemp = Σ V.hathh B).
BET
We solve the first challenge by fitting lemp with lower order polynomials, which can be achieved accurately by sampling a considcrably low number of batch loss values. We do have an efficient solution for the second challenge, thus we have to simplify the problem by taking the unit gradient the current batch IB,, which is V VoLoatch (0, Be), as direction of the line search. The line function we search on is thus given by:
(gLF(s; 0r, By) = Lemy + Vo, Chatch B.)) zs lower order polynomial
(6)
Note that 9r, B, are fixed during the line search.
'These results have already been published hy the authors of this paper another context [ref]

---

Under review conference paper ICLR 2021
Shanlo prit 201130
Steas art 20113
tarogere Koulo
04
14-
1.4
3.-
adviciat cagrint
14
-32
350
Figure An exemplar ELF routine testing for the best fitting polynomial. The empirical loss given in red, the distribution of batch losses in blue. The sampled losses are given in orange and green. The green losses are the test set of the current cross validation step. It can be seen, that the fifth-order polynomial (green) reaches the lowest test error.
Our straightforward concept is to sample losses Lhotch (00 + +; -V (6, Bo), B.), with ranging from to n and EB uniformly chosen from T and s; uniformly chosen from a reasonable interval, which we will focus later. Now, we follow a classical function fitting or machine learning routine. An ordinary least square regression (OLSR) for polynomials performed. Note, that our data is not homoscedastic, as required for OLSR This implies, that our resulting estimator is still unbiased, but we cannot perform an analysis of variances (see Goldberger et al. (1964)) However, the latter is not needed in our case. Those regressions are performed with increasing increasing. The test error is determined by a
degree until the test error of the fitted polynomial 5-fold validation. The second last polynomial degree is chosen and the polynomial is again fitted on all loss values get a more accurate fit. Consequently the closest minimum to the initial location is determined and additional losses are measured in a reasonable interval around it. This process is repeated four times. Finally, the step the closest minimum of the fitted polynomial is chosen as update step if, existing and value is positive. Otherwise, new line search is started. This routine is described in more detail in Algorithm I An empirical example of the search of the best fitting polynomial is given in Figure 2.2 The empirically found heuristic to determine reasonable measure intervals given in Algorithm This routine empirically ensures, that the point cloud losses is wider than high, so that a correctly oriented polynomial is fitted. To determine when to measure a new step size with a line search, we utilize that one can estimate the expected improvement by (0) IEL ((mmin)) )- If the real improvement of the training loss times faccorr is smaller than the expected improvement, both determined over a step window, a new step size is determined. The full ELF algorithm is given in Algorithm in Appendix A We note that all of the mentioned subroutines are easy implement with the Numpy Python library, which reduces the implementation effort significantly. The presented pscudo codes include the most important aspects for understanding our approach. For a more detailed description we refer to our implementation found in the supplementary material.
Based on our empirical experience with this approach we introduce the following additions: We measure 3 consecutive lines and take the average resulting step size to continue training with SGD. 2. We have experienced that ELF generalizes better if not performing step to the minimum, but perform a step that decreased the loss by a decrease factor of the overall improvement. In detail, we estimate Psarget > Tmin. which satisfies ((sarget) = (z() - Insa) - fzmmn) with 8 [0, 1) We use momentum term on the gradient, which can lead an improvement in generalization. To prevent over- wver-fitting, the batch losses required for fitting polynomials are sampled from the validation set. 5. At the beginning of the training short grid search is done to find the maximal step size that still supports training. This reduces the chances of getting stuck in local minima the beginning of optimization.
We indirectly use weighted OLSR by which softens the effect of heternscedastictty.
sampling more points in relevant intervals around the minimum.

---

Under review conference paper ICLR 2021
Algorithm Pseudo code of ELF's line search routine (see Algorithm
Input: direction (default: current unit gradient)
Input: 0g: initial parameter space position
Input: Lhatch (0c): batch loss function which randomly chooses batch
Input: k: sample interval adaptations (default: 5)
Input: re: losses to sample per adaptation (default: 100)
I: eeerval_widthe <- 1.0
2: sample-positions
3: lineLosses f- []
4: for from 0 to k do
!= 0 then
6: interval width <- chose sample intervalmmaaaaminnuu location, posittoo, line losses,
coefficents)
end if
8: new www.ssalppppstiiieeee <
witerval_width)
9: for in new cample_positionn do
10:
los_eessss.appeen wossses..peenndCCcc....... md))
11:
end for
12:
sample enetid sample positions) last_test_error 00
14:
for degree from to max mwx.polynonmeeeeee nax.ppoyynomill.om pedgne
15:
test enror <- 5-fold cross validation(degrree, sample positions, line losses)
last_rest_error test_error then
17:
best.degree + degree-1
18:
last test error +- test error break end if
20:
21:
if' degree = max polynomial degree then
22:
best_degree max www..ppoynoomil.dee .degee break end if end for
23:
24:
25:
26: coefficients + fitpolynoomalltess.deeee sample.positions, line_losses)
27: minimum position, improvement <- get minimum position nearest to O(coefficients)
28:
end for
29:
return minimum-position improvement, k
Algorithm Pseudo code of the chose www.ssammppette.. interval routine of Algorithm |
Input: minimum. minimum-posittin
Input: comple-positions
Input: line losses list of losses corresponding the sample.position
Input: coefficents coefficients of the polynomial of the current fit Input: min window size (default: 50)
I: window {m E sample positions and 0
minimum location)
2: wiindow] < mmin_windowwaa size then
3: window
ponittoo, minimum, )
4: end if
5: target_loss +
_quattilewwindow line_losses (eissos(inddw))
6: interval width < get nearest position where the absolut of polynomial-
takes valueecoofffieentstaage loss)
7: return interval

---

Under review conference paper ICLR 2021
Step
Validasion Accuracy
Training Loss
600
ELF
Figure 3: Comparison of ELF against PLS and GOLSI on a ResNet-32 trained on CIFAR-10. The corresponding test accuracies are: EFL: 0.900, PLS: 0.875, GOLSI: 0.872. ELF performs better this scenario and, intriguingly, PLS and ELF estimate similar step size schedules.
3 EMPIRICAL ANALASYS
To make our analysis comparable on steps and epochs, we define one step as loading of new input batch. Thus, the steps/batches needed of ELF to estimate a new line step are included.
3.1 COMPARISON TO OPTIMIZATION APPROACHES OPERATING ON Lemp
We compare against PLS (aahsereci & Hennig 2017) and GOLSI (Kafka & Wilke 2019). Both
approximate line searches on the empirical loss. Since PLS has to be adapted manually for each Model that introduces new layers. we restrict our comparison to a ResNet-32 (He et al. (2016) trained on CIFAR-IO (Krizhevsky & Hinton ).009)) ). In addition, we and the only available Tensorflow (Abadi et al. (2015)) implementation each optimizer we tested five appropriate hyperparameter combinations, which are likely to result good results (see Appendix [B. The best performing
empinially optimized PL. (Balles) (2017)). For
are given in 3. We can that ELF slightly surpasses GOLSS and PI.S on validation accuracy and training loss this scenario. Intriguingly, PLS and ELF estimate similar step size schedules, whereas, that of GOLS1 differs significantly.
3.2 ROBUSTNESS COMPARISON OF ELF, ADAM AND SGD
Since ELF, as long as loss lines are well approximate-able by polynomials, should adapt to differ- ent loss landscapes, is expected perform robustly across models and datasets. Therefore, we will concentrate on robustness this evaluation. For CIFAR-IO, CIFAR- 100, SVHN we will train on DenseNet-1211 MobileNetV2, ResNet-18 and ResNet-34. For Fashion-MNIST we consider a 3-layer fully connected network and 3-layer convolutional network. For ImageNet ResNet-18 MobileNetV2. We compare against the most widely used optimizer SGD, ADAM (widely considered to be robust (Schmidt et al. 2020 Kingma & Ba (014)) and PAL (Mutschler & Zell (2020)), line search approach on Lbatch- At first, perform an optimizer-hyperparamie hyperparameter grdd search over the models considered for CIFAR-I0. 10. Then, we choose the hyperparameter com- bination that achieves on average the best test accuracy for each optimizer. Consequently robust- each additional dataset and models. For ADAM and SGD we use a standard learning rate schedule, which divides initial learning rate by 10 after half and after three quarters of the training steps. For ADAM and SGD we considered 10-1, 10-1,10-2 1002, 2, 10-3,111000 11004 learning rates. ADAM's 's moving average factors set 0.9 and 0.999. For SGD, we used a momentum of 0.9. For ELF we used the default value each hyperparameter, except for the momentum factor, which was chosen as O or 0.4 and the decrease factor was chosen 0 or 0.2. For PAL mcasuring step size of 0.1 1 and step size adaptation of 1.66 and 1.0 was considered. Further details are given Appendix B
consider
ness is evaluated by reusing those hyperparameters
As shown in Figure 4 our experiments revealed that the most robust hyperparameter combination is momentum factor of 0.4 and a 5 of 0.2 for ELF. For SGD, the most robust learning rate is 0.01 and for ADAM 0.001. For PAL a measuring step size of 0.1 and a step size adaptation 1.0 perform most robustly.
For all optimizers the most robust hyperparameters found on CIFAR- 10 tend to perform also robustly other datasets and models. This is unexpected, since it is generally assumed that learning

---

Under review conference paper ICLR 2021
1.0
0.6
Tee
0.4
0..
012
DeaseNes-111
Mo
Rechee 18
3e
DesicNet22 121
MctikeNes. V2
Re-Net-88
ReaNes
CIFAR-10
CIFAR-1O
Tou A0000
0x8
0.6
0.0-
0.6
A00 Vm
ARART 1891
0.2
0.2
McMtNNN--
Redie-11
McNuNa--V
Ro
CIFAR-180
0.8
0.
0.4
02-
06-
DeasNNe-111
MiksteNes-22
Redicu11
3eaNei334
DeacNet.21 21
MctikcNs-V2 V2
RoNee-18
Be
MaNSI
ImageNer
Ted 500000
0.0-
0.4 MaayerCozz
0.38
Maaya-FC
Mantccha
RacNoo18
Figure 4: Robustness comparison of ELE, ADAM SGD and PAL. The most robust optimizer- hyperparameters across several models were determined CIFAR-IO. which then tested on further datasets and models. On those, the found hyperparameters of ELF, ADAM, SGD and PAI. behave robust. (8=momentum, x=learning rate, ô=decrease fuctar step adaptation, u--meaurinn step size). Plots of the training loss and validation accuracy given in Appendix C (Results for PAL on ImageNet will be included the final version.)
rate has to be searched for each new problem. In addition, we note that ELF tends to perform better on MobileNet-V V2 and the 3 3-Layer-FC network, however, is not that robust on SVHN. The most important insight, which has been obtained from our experiments, is that for all tested models and dataset ELF was able to fit lines by polynomials. Thus, we are able to directly measure step sizes on the empirical loss. Furthermore, we see that those step sizes are useful to guide optimization subsequent steps. To strengthen this statement, we plotted the sampled losses and the fitted polynomials for each approximated line. Representative examples are given Figure S and Appendix D
Figure 6 (left) shows that ELF uses depending the models between 1% to 75% of its training
Ayar
Figure 5: Representative polynomial line approximations (red) obtained by training ResNet-18 CIFAR-10. The samples losses are depicted in orange. The minimum the approximation represented by the green dot, whereas the update step adjusted by a decrease factor of 0.2 is depicted the red dot.

---

Under review conference paper ICLR 2021
training time on CIEAR- i0'nn min.
Friction training, steps ro- quited for line appros expottatioons
DDemeNeii-2 DommeNe--1LLMMoonneeee Mebbileett Ia ResNer-18 18 t ResNet-34
Ws-Layys-Conet is 3-Layos-RC
200
150
200
30
InsgeNNc CIFAR-10
DenseNee-12 121 MohieNNn-V
ReeNet-
RecNeet-S S4
Figure 6: Left: Fraction of training steps used for step size estimation and the total amount training steps. The amount of steps needed depends strongly on the model and dataset. Right: Training time comparison on CIFAR- 10. One can observe, that ELF performs slightly faster.
steps to approximate lines. This shows, that depending on the problem more or less step sizes have be determined. In addition, this indicates, that update steps become more efficient for models, for which many new step sizes had to determined. Figure 6 (left) shows that ELF faster than the other optimizers. This is consequence of sole forward passes required for measuring the losses on lines and since the operations required to fit polynomials cheap.
DISCUSSION & OUTLOOK
This work demonstrates that line searches on the true empirical loss can be done efficiently with the help of polynomial approximations. These approximations are valid for all investigated models and datasets. Although, from a practical point of view, measuring new step size is still expensive, it seems to be sufficient for successful training process to measure only a few exact step sizes during training. Our optimization approach ELF performs robustly over datasets and models without any hyperparameter tuning needed and competes against PAL, ADAM and SGD. The later 2 were run with good learning rate schedule. In experiments ELF showed better performance than Probabilistic Line Search and Gradient-only Line Search. Both also estimate their update steps from the expected empirical loss.
An open question is to what extent our approach leads to improvements in theory. It is known that exact steepest descent line searches deterministic problems (Luenberger et all (1984). p. 239)) exhibit linear convergence on any function, which is twice continuously differentiable and has a relative minimum at which the hessian is positive definite. The question to be considered is how the convergence behavior of exact line search behaves in noisy steepest directions. This, to the best our knowledge, has not yet been answered.

---

Under review conference paper ICLR 2021
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, lan Goodfellow, Andrew Harp, Geoffrey Irving. Michael Isard. Yangqing Jía, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg. Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Πly Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wat- tenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learn- ing on heterogeneous systems, 2015. URL https: h/tps://wwwww http://wwwttttcoceeto www.:.tessrf.... www.eeewwwww...ooooooooooo org/ Software available from tensorflow.org.
Lukas Balles.
https://qithube Probabilistic line search tensortlow implementation. 2017. line_
URL
seazch/conmit/aa/0
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. arXiv preprint arXiv: 1ee11703.0777 047822 2017.
Albert S. Berahas, Majid Jahani, and Martin Takác. Quasi-newton methods for deep learning: Forget the past, just sample. CoRR, abs/1901 01199009997,77 2019.
Leonard Berrada, Andrew Zisserman, and Pawan Kumar. Training neural networks for and by interpolation. arXiv preprint arXiv:1906.000 1eto:96060066,, 2019.
Aleksandar Botev, Hippolyt Ritter, and David Barber. Practical gauss newton optimisation for deep learning. arXiv preprint (tti::/706.06662. 2017.
Younghwan Chae and Daniel N Wilke. Empirical study towards understanding line search approxi- mations for training neural networks. arXiv preprint arXiv:1909.0689; 2019.
Arthur Stanley Goldberger al. Econometric theory. Econometric theory., 1964.
Tan Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1.
MIT press Cambridge, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Stephen Wright Jorge Nocedal. Numerical Optimization. Springer series in operations research. Springer, 2nd ed edition, 2006. ISBN 978088730301,008730000000
Dominic Kafka and Daniel Wilke. Gradient-only line searches: An alternative to probabilistic line searches. arXiv preprint arXiv: 9903.09933 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.6980,, 2014. URL http:://p////a/
orq/ http//bb/11110 6980
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Liyuan Liu, Haoming Jiang, Pengeheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond, 2019.
David G Luenberger, Yinyu Ye, et al. Linear and nonlinear programmingg volume 2. Springer, 1984.
Liangchen Luo, Yuanhao Xiong, and Yan Liu. Adaptive gradient methods with dynamic bound learning rate. In International Conference on Learning Representations, 2019. URI. https: / //opeeeeview. net. htt.://orummrraee/ ott.://foooouuutdddss333222
Maren Mahsereci and Philipp Hennig. Probabilistic line searches for stochastic optimization. Jour- nal of Machine Learning Research, 18, 2017.

---

Under review conference paper ICLR 2021
James Martens and Roger Grosse. Optimizing neural networks with kronecker- approximate curvature. In International conference on machine learning, pp. 2408-2411 2417, 2015.
Maximus Mutschler Andreas 7ell. Parabolic approximation line search dnns. arXiv preprint arXiv:1903. 11991, 2020.
Vivek Ramamurthy and Nigel Duffy. L-srl: a second order optimization method. 2017.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
net/ forcm? 1eee:dddddruuuue R-RZ
H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22:400-407, 1951.
Michal Rolinek and Georg Martius. L4: Practical loss-based stepsize adaptation for deep learning. In Advances in Neural Information Processing Systems, pp.
2018.
Robin M Schmidt, Frank Schneider, and Philipp Hennig. Descending through a crowded valley- benchmarking deep learning optimizers. arXiv preprint arXiv:2007.01547, 2020.
Nicol N. Schraudolph, Jin Yu, and Simon Gnter. A stochastic quasi-newton method for online convex optimization. In Marina Meila and Xiaotong Shen (eds.), Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, pp. 236-443, San Juan, Puerto Rico, 21-24 Mar 2007. PMLR.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop. coursera: Neural networks for machine learning. University of Toronto, Technical Report, 2012.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. arXiv preprint
0099779 2019.
Chen Xing, Devansh Arpit, Christos Tsirigotis, and Yoshua Bengio. A walk with sgd. arXiv preprint orXiv:1802.088 2018.
Matthew D. Zeiler. Adadelta: An adaptive learning method. CoRR, a2s/1212.5701, 2012.
10


Reviews:
[{"review_id": "b3PRx4GH8Ky", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis work proposes ELF, a newl method to do line search. The key idea is to fit a low order polynomial of the empirical loss (by sampling multiple batches) along the direction of a mini-batch gradient. The method stays computationally efficient by only computing the step size every so often. Experiments on a variety of image classification tasks show that ELF is competitive to GOLS1, PLS, PAL, SGD, and Adam, while taking less time to train.\n\nStrengths:\nThe fact that ELF can get competitive results compared to SGD with momentum, and Adam, while taking less time to train, is exciting.\n\nWeaknesses:\n- I find the contribution of this paper a bit weak. Reading a line search paper with mostly empirical justifications, I would like to see the method outperforming a strong baseline (a commonly used optimizer for that architecture, with default hyperparameters for example) where ELF uses a fixed set of hyperparameters. Such an experiment would justify the practical usefulness of ELF. As far as I can tell, this sort of experiment was not done. \n- The paper doesn’t clearly show the role fitting empirical instead of batch loss (which is written as the main contribution) compared to the introduction of beta and delta on performance. How does PAL perform with these additional settings (since they also seem equally applicable)? Similarly, for Figure 3: How much of this is due to the introduction of beta and delta compared to fitting method, or the fact that empirical loss is used rather than batch loss?\n- Using the validation set during training doesn’t really make sense. If the method overfits greatly by using just the training set, then that method is prone to overfitting; using the validation set can’t be the solution.\n- Currently, the paper’s presentation is lacking. Paragraphs are too long, the related work section feels unorganized, Figure 1 is taken from an already published paper, and the two huge algorithm boxes break the flow of the paper and is too much detail. \n\nDecision:\nReject. The idea shows promise but the current state of the paper should be improved before warranting acceptance, for the reasons listed above.\n\nComments and questions:\n- “Due to CLT we can assume p_data to be Gaussian” - not true.\n- Was there a reason why SLS (Vaswani et al. 2019) wasn't included in the comparisons? To my knowledge, SLS is the best performing line search method in deep learning.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ag0j1Q7XUU9", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a line-search for optimizing deep neural networks. The method is rather unprincipled and quite close to the approach proposed in (Vaswani et al, 2019). I do not think that the paper proposes new ideas that haven't been already explored in the deterministic optimization literature. All in all, the paper needs to better connect to the algorithmic ideas in the deterministic optimization literature, compare against the new optimization methods proposed recently and have more representative plots. Detailed review below. \n\n- The claim \"adaptive methods concentrate more on finding good directions than on optimal step sizes, and could benefit from line search approaches\" needs justification. At this point, there has been substantial work that shows that adaptive methods like Adam are quite robust to their step size and do in fact, work well across problems. \n\n- Please cite the literature relevant to SGD, for example, Robins-Munro and Bottou et al, 2016. In the deterministic optimization literature, using Polyak step size is an alternative to line-search approaches. Please also cite the recently proposed methods based on the Polyak step-size, Berrada, et al \"Training Neural Networks for and by Interpolation\" and Loizou et al \"Stochastic polyak step-size for SGD: An adaptive learning rate for fast convergence\" that have been used to train deep neural networks. \n\n- In Figure 1, it is not enough to show that the loss landscapes are similar in the batch gradient direction. they should also be the same in the stochastic gradient direction, which depending on the batch, can be very different from the batch gradient direction. A more convincing approach would be to choose random directions and compute a metric of similarity for all such directions. Moreover, please explain how is \"t\" chosen for this plot. We know that the loss landscape is different at the start vs the end of the optimization. Consequently, this is not enough evidence to show that line-search can be done on a stochastic batch. In this figure, the batch-size is another confounding factor. What is the effect of the batch-size? \n\n- \"lemp has a simple shape and can be approximated well by lower order polynomials, splines or fourier series.\" This is indeed the motivation behind line-search techniques for convex problems. Please cite Noecedal-Wright 2006 or the original line-search paper by Armijo. \n\n- In Section 2.2, backtracking line-search is used to overcome the first challenge, i.e. the algorithm picks the largest step-size that satisfies a sufficient decrease condition. The complexity of this is proportional to the number of backtracking iterations which is small. In the proposed approach, a number of points is sampled, meaning additional function evaluations. Please justify why the backtracking approach is not sufficient in this case, and explain why the proposed method would be better.  \n\n- Similarly, for the second challenge, it is doing exactly the thing you cautioned against earlier \"that the batch need not be representative of the full loss function\".  Doing a backtracking line-search on a batch is exactly the approach adopted by (Vaswani et al, 2019). Please clarify this and also explain why you do not experimentally compare against them. \n\n- The idea of building a model of the loss function by using additional points (from the past) is well known in the deterministic optimization literature in the form of line-search with quadratic/cubic interpolation. This approach does not use additional function evaluations. Please explicitly make this connection and again, justify your approach against this less expensive method. Moreover, the paper proposes to build a highly accurate model of a stochastic loss which need not be representative of the full loss in any case. \n\n- \"The test error is determined by a 5-fold cross-validation. The second last polynomial degree is chosen and the polynomial is again\nfitted on all loss values to get a more accurate fit. Consequently the closest minimum to the initial location is determined and additional losses are measured in a reasonable interval around it.\" This is clearly very computationally expensive for determining the step-size for one iteration. Please clearly state what is the computational complexity of determining the step-size in one iteration. \n\n- \"ELF generalizes better if not performing a step to the minimum, but to perform a step that decreased the loss by a decrease factor\" This is almost the same as checking the Armijo sufficient decrease condition with a factor of \\delta. Why not just do this and say it explicitly?\n\n- Experimentally, since the proposed approach is closest to the work of (Vaswani et al, 2019), please experimentally compare against their method. \n\n- In Figure 4, please plot the training/test loss vs the number of iterations. One point of information in the form of the test accuracy is not representative, especially since the metric being optimized is the training loss. And there are multiple confounding factors that influence the test error corresponding to any optimization method. Since this is more of an experimental paper, it would make sense to compare against the newer variants of Adam, such as RADAM and AdaBound that have found to work well.", "extra_scores": {}, "extra_text": {}}, {"review_id": "2FzkTxIoYer", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update: I thank the authors for the detailled response. Due to the number of required changes and the feedback of other reviewers, I believe the paper needs a major revision before publication and still recommend rejection.\n\n\n---\n\nThe submission introduces a heuristic to select the step-size for training deep learning models. Reducing the dependence on hyperparameters and improving the performance of optimization methods with out-of-the-box settings is an important problem and relevant to the ICLR community. The proposed approach is novel and well illustrated.\n\nHowever, as there are limited theoretical contributions or new insights, the submission has to be evaluated on the effectiveness of the method. The main weakness of the manuscript is a lack of motivation for the details of the proposed heuristics and insufficient experimental evaluation. \n\nDespite the method being described as simple and straightforward, I fail to see how the proposed approach is simpler than a backtracking line-search on the batch loss. A main argument for the proposed approach in constrast to previous work is that the minibatch loss is not sufficiently representative for a line-search. This contrasts with observations in previous work (e.g. Vaswani et al., 2019). While it makes intuitive sense that taking multiple batches into account is necessary in the presence of noise, there is limited evidence that the proposed method does so appropriately. The experimental evidence in section 3.1 is promising but is not broad enough to be informative. While the results of section 3.2 are nice to have, the improved robustness of the method against SGD and Adam is not surprising; the space would be better used comparing the performance of the method against the other cited works on batch line search.\n\nMy recommendation is towards a rejection. There is evidence the proposed method can work. But I doubt the submission will generate enthusiasm from the theory side of the community do to the limited new insights and the empirical evaluation is insufficient to convince me of the benefits of the method over previous work for its applications.\n\n\nAs additional feedback (there to help, not necessarily part of the decision), I advise the authors to pay a greater attention to presentation details when preparing their submissions. The writing and quality of the figures gets in the way of the message they are trying to communicate. For a few example, since the \"homoscedasticity\" is irrelevant for the current problem, I do not follow why it is mentioned so prominently in section 2. The use of \"vertical cross-section\" is also confusing; it is still unclear to me what is \nvertical.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0S1-PSG2-e", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper tackles an important issue, namely how to tune the step sizes in SGD during the training, trying to approximate step sizes which would be used in GD (even though the search direction is still noisy). Relevant prior work is cited. The method is simple and easy to understand. Step sizes are kept piecewise constant over updates. New batches are sampled, and the loss values along the search line are fitted with a low-order polynomial. There is some heuristic to choose the interval around 0 for the step. Importantly, these batches are sampled from the validation set. While this sounds very elaborate to find the minimum of the approximation, they later say they are just trying for sufficient descent along the line. Compared to previous work, the method is simple and seems quite robust. As drawbacks, the method seems pretty expensive, and it has a large number of free parameters that need to be chosen.\n\nA major weakness of the paper is the empirical evaluation. The comparison to related work in 3.1 is a bit meaningless, because they look at validation error. Now, their method uses the validation set extensively (to sample batches), while the others do not, so the comparison is flawed. One would have to evaluate on an independent test set. What is also really missing here are figures about the extra amount of time required. My suspicion is that PLS is quite a bit cheaper than what they do here, even though admittedly it needs specific implementations (which, for TensorFlow, are provided by the authors).\nThen, in 3.2, they do not compare against this related work anymore. Why not? Again, I am missing a proper quantification of extra cost. It is also unclear how the many free parameters of their heuristic are chosen. For Figure 6 left, it is hard to understand why there is this difference. The reason is buried in the text somewhere: \"To determine whether to measure a new step size...\". This describes a rule for how often to update step size, and it again has unspecified free parameters. For Figure 6 right: This comparison is meaningless unless the stopping criteria for all methods are clearly stated. If ELF is using *extra* batch evaluations to adjust learning rate, it must be slower than ADAM or SGD if the same number of epochs are done. What takes the extra time for ADAM and SGD? Do they run more epochs? If so, what is the stopping rule? If that rule depends on validation error, the comparison is flawed (see above), because ELF accesses the validation set a lot, while ADAM and SGD do not (except for initial HPO). Or do they all run the same number of epochs? If so, what takes the extra time for ADAM and SGD? If this is some initial HPO, it has to be clearly specified, as it could range from cheap to very expensive depending on what is done.\n\nGiven these issues, I feel the work cannot be properly evaluated. My recommendation is to (a) clearly quantify the extra cost for all methods compared, (b) to compare against PLS and GOLS1 everywhere, (c) to be very specific about how training is stopped when comparing training runtime, and (d) to evaluate metrics on a dataset that ELF has no access to.\n\nSince ELF seems quite expensive, it would be useful to try and see what can be done with batch losses evaluated along the training trajectory, instead of having to sample independent ones. They should also test how few batch losses are needed to still get good behaviour. In general, some ablation studies are needed that would drive down extra compute and check how fast this can be made.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an empirical method to automatically schedule the learning rate in stochastic optimization methods for deep learning, based on line-search over a locally fitted model. The idea looks interesting and promising, but the reviewers have serious concerns in the lack of principled support and insufficient empirical evidences. Therefore I recommend rejection of the paper and encourage the author(s) to strengthen the idea and contribution with further theoretical and empirical study.
Decision: Reject