Using a one dimensional parabolic model of the full-batch loss to estimate learning rates during training
Authors: Maximus Mutschler
Kevin Alexander Laube
Andreas Zell
Venue: ICLR 2022 Submitted (2022)
Keywords: Empirics based Optimization
Optimization
Line Search
SGD
Deep Learning

Abstract: A fundamental challenge in Deep Learning is to find optimal step sizes for stochastic gradient descent automatically. In traditional optimization, line searches are a commonly used method to determine step sizes. One problem in Deep Learning is that finding appropriate step sizes on the full-batch loss is unfeasibly expensive. Therefore, classical line search approaches, designed for losses without inherent noise, are usually not applicable. Recent empirical findings suggest that the full-batch loss behaves locally parabolically in the direction of noisy update step directions. Furthermore, the trend of the optimal update step size changes slowly. By exploiting these findings, this work introduces a line-search method that approximates the full-batch loss with a parabola estimated over several mini-batches. Learning rates are derived from such parabolas during training. In the experiments conducted, our approach mostly outperforms SGD tuned with a piece-wise constant learning rate schedule and other line search approaches for Deep Learning across models, datasets, and batch sizes on validation and test accuracy.

Under review conference paper ICLR 2022
USING A ONE DIMENSIONAL PARABOLIC MODEL OF THE FULL-BATCH LOSS TO ESTIMATE LEARNING RATES DURING TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
A fundamental challenge in Deep Learning is to find optimal step sizes for stochastic gradient descent automatically. In traditional optimization, line searches are a commonly used method to determine step sizes. One problem Deep Learning is that finding appropriate step sizes on the full-batch loss is unfea- sibly expensive. Therefore, classical line search approaches, designed for losses without inherent noise, are usually not applicable. Recent empirical findings sug- gest that the full-batch loss behaves locally paraholically in the direction of noisy update step directions. Furthermore, the trend of the optimal update step size changes slowly. By exploiting these findings, this work introduces a line-search method that approximates the full-batch loss with parabola estimated over sev- eral mini-batches. Learning rates derived from such parabolas during training. the experiments conducted, our approach mostly outperforms SGD tuned with a piece-wise constant learning rate schedule and other line search approaches for Deep Learning across models, datascts, and batch sizes on validation and test ac- curacy.
INTRODUCTION
Automatic determination of an appropriate and loss function-dependen learning rate schedule to train models with stochastic gradient descent (SGD) or similar optimizers still not solved satisfac- torily for Deep Learning tasks. The long-term goal is to design optimizers that work out-of-the-bee for wide range of Deep Learning problems without requiring hyper-paramedt tuning. Therefore, although well-working sand-designed schedules such as piece-wise constant learning rate or cosine decay exist (see (Loshchilov & Hutter 2017 Smith 2017)). it is desired to infer problem depended and better learning rate schedules automatically.
This work builds recent empirical findings; among those that the full-batch loss tends to have a simple parabolic shape SGD update step direction (Mutschler & Zell, 2021 2020) (see Figure T and that the trend of the optimal update step changes slowly (Mutschler & Zell 2021) (see Figure Figure 2. Exploiting these and more found observations. approximating the full-batch loss along lines SGD update step direction with parabolas. One parabola is sampled over several batches to obtain a more exact approximation of the full-batch loss. The learning rate is then derived from this parabola. As the trend of the optimal update step-size the full-batch loss changes slowly, the line search only needs to be performed occasionally; usually, every 1000th step. This results in low computational overhead.
introduce line search approach,
The major contribution of this work is the combination of recent empirical findings to derive line search method, which is built upon real-world observations and less theoretical assumptions. This method outperforms the most prominent line scarch approaches introduced for Deep Learning (Vaswani et al.] (2019); Mutschler & Zell (2020); Kafka & Wilke (2019): Mahsereci & Hennig (2017) across models, datasets usually considered in optimization for Deep Learning, in almost all experiments. In addition, it almost always outperforms SGD tuned with a piece-wise constant leamning rate schedule on validation and test accuracy. The second important contribution is that we are the first to analyze how the considered line searches perform under high gradient noise that originates from small batch sizes. While all considered line scarches perform poorly -mostly because they rely on mini-batch losses-, our approach adapts well to increasing gradient noise by approximating the full-hatch loss. However, a significant performance gap still exists between our

---

Under review conference paper ICLR 2022
line numbertt: 10
line aumbertt 4,000
line mumbert: S,0000
bewwen buca
35
qraticusd saile koon
Adiingg fusals
0.5-
6.55-
lend
10-
112
20-
CJ5
1.4
-0.1
Sap on (5)
stop (9)
line
Figure 1: Losses along the lines of the SGD training processes exhibit a parabolic shape. The loss of the direction defining mini-batch (green) is excluded from the distribution of mini-batch losses to show that it is significantly different. This makes line searches on it unfavorable. In addition, the parabolic property articulates stronger for the full-batch loss (red); thus, this work aims to approximate efficiently with parabola. The figure is created with code and data from Mutschler & Zell (202I).
line search and an optimally tuned SGD optimizer using momentum, weight decay, and a problem- specific hand-desipe dend-designed learning rate schedule.
The paper is organized as follows: Section [ provides an overview of related work. Section S derives our line search approach and introduces its mathematical and empirical foundations in detail.
Section 4 we analyze the performance of our approach across datasets, models, and gradient noise levels. Also, a comprehensive jyper-paramettr, runtime, and memory consumption analysis is performed. Finally, we end with discussion including limitations in Sections 5 &
RELATED WORK
Deterministic line searches:
33), line searches are consid- ered a solved problem, in the noise-free free case. However, such methods are not robust to gradient and loss noise and often fail in this scenario since they shrink the search space inadequately or use too inexact approximations of the loss. (Jorge & Stephen 2006 33.5) introduces a deterministic line search using parabolic and cubic approximations of the loss, which motivated our approach.
According to (Jorge & Stephen 2006,
Line searches mini-batch and full-batch losses and why to favor the latter. The following motivates the goal of our work introduce simple, reasonably fast, and well-performing line- search approach that approximates full-batch loss.
Many exact and inexact line search approaches for Deep Learning are applied on mini-batch losses (Mutschler & Zell 2020, [errada et 20200 Rolinek & Martius 2018 [aadinn al.) 2018, Vaswani et al. (201)). (Mutschler & Zell 2020) approximates an exact line search by estimating the minimum of the mini-batch loss along lines with one-dimensional parabolic approximation. The other approaches perform inexact line searches by estimating positions of the mini-batch loss along lines, which fulfill specific conditions. Such, inter alia, are the Goldberg, Armijo, and Wolfe conditions (seeJorge & Stephen (2006)). For these, convergence be assured under the interpolation condition (Vaswami al., (019)), which holds if the gradient with respect to each batch converges to zero at the optimum of the convex function. Under this condition, the convergence rates match those of gradient descent on the full-batch loss for convex functions (Vaswani al. 2019). However, relying on those assumptions and on mini-batch losses only does not lead to robust optimization, especially not the gradient noise is high, as will be shown in Sec- tion 4 MMutschler & Zell, [021] 2020) even showed that exact line searches on mini-bator losses not working all. Line searches the non-stochastic full-batch loss show linear convergence on any deterministic function that is twice continuously differentiable, has a relative minimum, and only positive eigenvalues of the Hessian at the minimum (see Luenberger et al. (1984)) In addition, they independent of gradient noise. Therefore, it reasonable consider line searches the full-batch loss. However, these are cost- intensieesive since a massive amount of mini-bateh losses for multiple positions along a line must be determined to measure the full-batch loss.
convex stochastic functions can
Probabilistic Line Search (PLS) (Mahsereci & Hennig, (017) addresses this problem by performing Gaussian Process Regressions, which result in muluple one-dimensional cubic splines. In addition, a probabilistic belief over the first (aka Armijo condition) and second Wolfe condition is introduced find appropriate update positions. The major drawback of this conceptually appealing method is

---

Under review conference paper ICLR 2022
axcumulaned loss impeovenent
ratoo of
to full baoch nin, and aocm of dir, grad.
11.33
Lou OQREEAD
Fall foll-bocch Inno inpRowentan
11.3
0.3
100
0.23
uptaee 41
0.25
Ioss deccuso centnnghas
100
112
02-
0.05
0.35
2,000
4,800
3,40
2,00
4.003
0,200
5,000
5,000
linc www.aaaanaaaaaa...... step
lise www.lerraaaaaa stop
lase sanderilggddee step
Figure 2: Several metrics to compare update step strategies on the full-batch losses along 10,000 lines measured by |Mutschler & 7ell (02T)): I. update step sizes, 2. accumulated loss improvement per step given as: I ((ppdd) where Supd is the update step of specific optimizer. This is the locally optimal improvement to the minimum of the full-batch loss along a line. The right plot shows almost proportional behavior between the optimal update step and the negative gradient norm of the direction defining mini-batch loss. The AABALL&SD version of our approach performs almost optimal on ground truth data. Results LABPAL&NSGD are almost identical and thus omitted. Plotting code based on Mutschler & Zell 2021 with addition of our proposed approach.
its high complexity and slow training speed. A different approach working on the full-batch loss is Gradient-only line search (GOLSI) (Kafka & Wilke [019]. It approximates a line search on the full-batch loss by considering consecutive noisy directional derivatives whose noise is considerably smaller than the noise of the mini-batch losses. practice, its performance is rather weak.
Empirical properties of the loss landscape: In Deep Learning, loss landscapes of the true loss (over the whole distribution), the full-batch loss, and the mini-batch loss can, in general, be highly non-convex. However, to efficiently perform line search, some properties of these losses have be apparent. Little is known about such properties from a theoretical perspective: however, several works suggest that loss landscapes tend to be simple and have some properties: Mutschler & Zell (2021): [L et al. (2018); Xing al. (2018); Mutschler Zell (2020); Chae & Wilke (2019); Mah- Sereci & Hennig (2017); Goodfellow et al. (2015) Fort & Jastrzebski 20 et al. (2018). (Mahsereci & Hennig] Xiigg et al. [2118] Mutschler & [cll][2021]] (2220 suggest that the full- batch loss C along lines in negative gradient directions tend exhibit simple shape for set of Deep Learning problems. This set includes at least classification tasks on CIFAR-I0 10, CIFAR-I00, and ImageNet. (Mutschler & 7ell] (02T) sampled the full-batch loss along the lines in SGD update step directions. This was done for 10, 000 consecutive SGD update steps of a ResNet18's training process on a subset of CIFAR-10. Representative plots of their 10, 000 measured full-batch losses along lines are presented in FigureD [ Relevant insights and found properties of these works will be introduced and exploited derive our algorithm in Section 3
Using the batch size to tackle gradient noise: Besides decreasing the learning rate, increasing the batch size remains important choice to tackle gradient noise. McCandlish et al. exploits empirical information to predict the largest piratical batch size over datasets and models. De al. adaptively increases the batch size over update steps to assure that the negative gradient is a descent direction. Smith & Le introduces the noise scale, which controls the magnitude of the random fluctuations of consecutive gradients interpreted as differential equation. The latter leads to the observation that increasing the batch size has a similar effect as decreasing the learning rate (Smith et al., 20018). which is exploited by our algorithm.
3 OUR APPROACH: BARGE-BATCH PARABOLIC APPROXIMATION LINE SEARCH (LABPAL)
3.1 MATHEMATICAL FOUNDATIONS
this subsection, we introduce the mathematical background relevant for line searches and chal- lenges that must be solved in order to perform line searches in Deep Learning. We consider the problem of minimizing the full-batch loss L, which is the mean over large amount of sample losses
C : R +
Σ La(0),
(1)
DD

---

Under review conference paper ICLR 2022
where a finite dataset and are n parameters to optimize, To increase training speed generally, a mini-batch loss Lg, which is a noisy estimate of L, is considered:
L3 R"
Σ
La(#),
dEBCD
with [B| DI/ We define the mini-batch gradient step as ga, E E Va,
For our approach, we need the full-batch loss along direction the negative normalized gradient of a specific mini-hatch loss. At optimization step & with current parameters O, and a direction defining batch B,, Lg along line with origin Og in the negative direction of the normalized batch gradient gs. //.//188.... |8/./l all is given as:
JR,
R R, 8 (0, + 8. gn..)),
(3)
where is the step size along the line. The corresponding full-batch loss along the same line is given by:
4. IR - R, 8 + [(2, + 8 - -B..))
(4)
Let the step size to the first encountered minimum of le be 8min.t.
Two major challenges have be solved in order to perform line searches on L:
1. To measure l exactly it is required to determine every (0: + -ge,a) for all and for all step sizes on line.
To assure convergence line searches have to performed a descent direction et al., 2016). The simplest form is the direction of steepest descent (Luenberger et al. 1984. Therefore, the full- batch gradient VoL
VL (,, has to be R" - R", 0 DED
approximated.
To be efficient, 4 has to be approximated sufficiently well with as little data points d and steps possible, and one has to use as little d as possible approximate VeL approximated sufficiently well. Such approximations are highly dependent on properties of Due to the complex structure Deep Neural Networks, little is known about such properties from a theoretical perspective. Thus, we fall back to empirical properties.
3.2 DERIVING THE ALGORITHM
In the following, we derive our line search approach on the full-batch loss by iteratively exploiting empirically found observations of (Mutschler & Zell, 2021) and solving the challenges for line search on the full-batch loss (see Section B.1). Given default values are inferred from detailed hyper parameter analysis (Section[4.4)
Observation 1: Minima of la.t can be significantly different points than minima of le and can even lead to update steps, which increase C (Figure center, green and red curve). Derivation Step 1: This consolidates that line searches on a too low mini- batch loss are unpromis- ing. Consequently, we concentrate on better way to approximate 4,-
Observation 2: 4 can be approximated with parabolas of positive curvature, whose fitring errors are of less than 0.6 10 mean absolute distance (exemplarily shown in Figure [}.
Derivation Step 2: We approximate 1 with a parabola ((ss), z a4s² bys + with o, > 0). A parabolic approximation needs three measurements of However, already computing I, for one s only is computationally unfeasible. Assuming i.i.d sample losses, the standard error of (s). de- creases with 1/ VBB. Thus. lB, -with a reasonable large batch size- is already a good estimator for the full-batch loss parabola. Consequently, we approximate l, with lp.., by averaging over multiple (s..: measured with multiple inferences. Thus, the approximation batch size B,, is significantly larger as the, by GPU memory limited, possible batch size B, In our experiments, B, is usually chosen to be 1280, which is 10 times larger as 18; In detail, measure (B., at the points 0.01, then we simply infer the parabola's parameters and the update step to the minimum. These values of s empirically lead to the best and numerically most stable approximations. Observation 3: The trend of smin. of consecutive 4, changes slowly and consecutive do not change locally significantly, (Figure[]ett red curve).
0.0001 and
Observation 4: Sminn and the direction defining batch's :|gs..ll are almost proportional during training. (Figure 2 right).

---

PERFROMJ.ARGR_ MAR.OOMJAARRR.ATALLL.. BATTOAAAOOOOOOAAAAAAAOO end if end while return 0 Under review conference paper ICLR 2022
Derivation Step Using measurements of fz..s to approximate 4 with a parabola by far to slow to compete against SGD if done for each weight update. By exploiting Observation we can ap- proximate 4, after constant amount of steps and reuse the measured learning rate À or update step size Suyd for subsequent steps. this case, is factor multiplied by g3,t. whereas Supd is factor multiplied by &8,(. Observation 4 allows us to reuse X. In our experiments, it is sufficient to measure new À or Supd every 1000 steps only.
Derivation Step 4: So far, we can approximate efficiently and, thus, overeome the first challenge (see Section [. Now, we will overcome the second challenge; approximating the full batch loss gradient for each weight update step:
For this, we revisit /Smith et al. (2018) who approximates the magnitude of random gradient fluctu- ations, that appear if training with a mini- batch gradient, by the noise scale v E IR:
(5) where À is the learning rate, [D} the dataset size and [B] the batch size. If the random gradient fluc- tuations are reduced, the approximation the gradient gets better. Since we want to estimate the learning rate automatically, the only tunable parameter to reduce the noise scale is the batch size. Observation 5: The variance of consecutive Smint is low, however, it increases continuously during training (Figure left red curve).
V/ = (ADI)/1B), [B),
Derivation Step 5: It stands to reason that the latter happens because the random gradient fluc- tuations increase. Consequently, during training. we increase the batch size for weight updates by iteratively sampling larger batch with multiple inferences. This reduces the variance of consecutive S and lets us reuse estimated the À or Supd for more steps. After experiencing unusable results with the approach of (De et al.] (016) to determine appropriate batch sizes, stick to a simple piece-wise constant batch size schedule doubling the batch size after two and after three-quarters of the training.
Observation 6: On global perspective Supd that overestimates Smin, optimizes and generalizes better.
Derivation Step 6: Thus, after estimating X (or Sapd) we multiply it with a factor a E|1,2|:
X = assmi.///lss
(6)
Note that under out parabolic property, the first wolfe condition wi, which is commonly used for line searches, simply relates to at wi a (see Appendix(F).
2
Algorithm 1 LABPAL&SGD. Simplified conceptional pseudo-code of our proposed algorithm, which estimates update steps on a parabolic approximation of the full-batch loss. See the published source code for technical details. Default values given in parenthesis. For LABPAL&NSON SGD is replaced with NSGD, and the update step is measured instead of the learning rate.
Input:
Hepoparaanctets:
18: procedure PERFORM WINERMLLIIIEEEE LINESEEEARRLLLEEE If samplooRuteeSSe < [Paa] then
initial parameters 9
upproximation butch size [B.]| (1280)
20:
update estimate C of C with over multiple inferences sampled Cag. with
inference batch size |B| (128)
5GD steps rscn (1000). or NSGD steps
[3,] = k(t) [3.l)
size adapiation a > (1.8)
compledBoicchiir [P+| and by k())
-training sepp fmax fmax (150000)
22:
ebse
ift S [fmux 0.5]
23:
Rete +- períomm parabolic approsimation with 3 values of é dallnn the search direction and estimate the
batch size schedule k(t)
2.
elift [fmax 0.75]
dhit [bmax 0.75]
leurning
24:
leorning +- learning Rote -o
1: # Variables have global soape
25:
sampledBarchSizz and perfomedSGDsitess
2: sampleddDttchSite 0
26:
stute 'SGDTraining"
3: performeSSGDnipp e-
27:
end if
4: learningRate 4-
end procedure
96
29:
6: state 4- 'Line search'
procedure PERFROM. LARGE BATCH_SGD_STEP)
direction
batch gradient
31:
if performedSGDDtees < Propp then
8: t 0
32:
0 perform SGD updale with leamingRate and multiple inferenees sampled Lay..
9: while
do
10: if Vtatte line search'' then
with [3,] = k(t) [B&])
11:
PERFORM LING SEARCH STIP))
increase by k(t)
if if state 'SGDTraining" then
34:
incresse PerformedSGG by
13:
else
14:
36:
direction é- current batch gradient
15:
37:
+- "inee search"
16:
17:
39:
end procedure

---

Under review conference paper ICLR 2022
Combining all derivations leads to our line search named large-batch parabolic appreximation line search (LABPAL), which is given in Algorithm [ It samples the desired batch size over multiple inferences to perform a close approximation of the full-batch loss and then reuses the estimated learning rate to train with SGD (LABPAL&SGD), or reuses the update step train with SGD with a normalized gradient (LABBAL&NSGDD) While LABPAL&SGD elaborates Observation 4, LABPAL&NSGD completely ignores information from lg)
4 EMPIRICAL ANALYSIS
Our two approaches are compared against other line search methods across several datasets and networks in the following. To reasonably compare different line search methods, define step as the sampling of a new input batch. Consequently, the steps/batches that LABPAL takes estimate a new learning rate/step size are considered, and optimization processes are compared on their data efficiency.
Since most line search approaches are introduced without a momentum term, no momentum terms are used. Note that the base ideas of the introduced line search approaches can be applied upon any direction giving technique such as Momentum, Adagrad (Duchi al. (011) Adam (Kingma & Ba 2015). Results are averaged over runs.
4.1 PERFORMANCE ANALYSIS ON GROUND TRUTH FULL-BATCH LOSS AND PROOF OF CONCEPT
To analyze how well our approach approximates the full-batch loss along lines, we extended the experiments of Mutschler & Zell 2021) by LABPAL. |Mutcchler & Zell (02I)) measured the full- batch loss along lines in SGD update step directions of training process; thus, this data provides ground truth to test how well the approach approximates the full-batch loss. In this scenario, LAB- PAL&SGD uses the full-batch size estimate the learning rate and reuses it for 100 steps. No update step adaptation applied. Figure 2
shows that LABPAL&SGD fits the update step sizes the minimum of the full-batch loss and performs near-optimal local improvement. The same holds for LABPAL&NSGD.
now lest how our approaches perform scenario for which we can assure that the used em- pirical observations hold. Therefore, we consider the optimization problem of (Mutschler & Zcll 202T) from which all empirical observations were inferred, which is training ResNet20 on 8% of CIFARI0. 1 of 1280 used for both approaches. Learning rates are reused for 100 steps, and a: = 1.8 is considered. The batch size is doubled after 5000 and 7500 steps. For SGD A is halved af- ter the same steps. grid search for the best À is performed. Figure (euuree]shore shows that LABPAL&NSGD with update step adaptation outperforms SGD, even though 9%
training steps are used to es- timate new update step sizes. This shows that using the estimated learning rates and step sizes leads better performance than keeping them constant decaying them with nicce-wise schedule. In-
0.75
1oes
10-1
val scomacy
0.7
0.65
SGD
SGD A D.2 decay
0.6
10
LABPAL&NSGD
LABPAL &SGD
10
0.5g
10
training stop -10*
training stop -10
10P
104
upslate stop
Jeaming
10P
10
10-1
Braining step -10
training step 102
Figure 3: Training process on the problem of which the empirical observations were inferred ( ResNet-20 trained on 8% of CIFAR-10 with SGD). LABPAL&NSGD and LABPAL&SGD outper- form SGD. Interestingly LABPAL&NSGD estimated huge Äs, whereas SupdS are decreasing

---

Under review conference paper ICLR 2022
terestingly huge As of up to 80, 000 are estimated, whereas SupdS are decreasing. LABPAL&SGD shows similar performance as SGD: however, it seems beneficial to ignore gradient size information as the better performance of LABPAL&NSGD shows.
4.2 PERFORMANCE COMPARISON TO SGD AND TO OTHER LINE SEARCH APPROACHES
We compare the SGD and NSGD variants of our approach against PLS (Mahsereci & Hennig 2017). GOLSI (Kafka & Wilke 2019), PAL (Mutschler & Zell (020), SLS (Vaswani et al. 2019) and SGD (Robbins & Monro 1951). I.. The latter is commonly used optimizer for Deep Learning problems can be reinterpreted as a parabolic approximation line search on mini-batch losses (Mutschler Zell 2021). PLS is of interest since it approximates the full-bated loss to perform line searches. PAL. GOLSI, SLS on the other hand are line searches optimizing mini-batch losses directly. For SGD, piece-wise constant learning rate schedule divides the learning rate after two and again after three-quarters of the training.
framing raie CHAAR- R0
lraming ratn CHRMR- 100 Mobile
leorning nin CIPAR-I00 DemeNrr-121
12
leantin 188e
leaiing rote
13:1
10
10
0.6
mmining RenNes-20
rusining lose MohiloNae-V
Iniinig CIFAR-ID
Taining lons
10
100
150
350
epocdhs
epocts
epochs
validutiion susuaaryy RccNoo-20
valichaton scsumay CIFAR-IOR MobilNNa-22
valicheion commany
07
wedditin acurccy
colatation
coltation
300
22.
900
.00
1.50
15:0
203
qpoches
Sposehs
CIEAR Reshier 20
CIEAR MobileNee
CIEAR DenseNet
4.7
103 ScAmnRy
rest RXCUrRAy
LABEAAL LIBEST JUGEEE TRRDUTT
spoch best
spoch with aoC.
spoch DEst val. aCC.
Figure 4: Performance comparison on CIFAR-100 of our approach LABPAL in the SGD and NSGD Optimal hyperparameters for CIFAR-10 10 found with
variants against several line searches and SGD.
a detailed grid search are reused (Appendix G.I Here, approaches surpass the other approaches
on training loss, validation, and test accuracy. Columns indicate different models. Rows indicate different metrics. Results for CIFAR-10, 10, ImageNet and SVHN are given in appendix Figures g and [0]
The hatch-size used is 128.

---

Under review as conference paper ICLR 2022
Comparison is done across several datasets and models. Specifically, we compare ResNet-22 (He)
et al. 2016). DenseNet-40 (Huang et al. (0017) and MobileNetV2 (Sandler et I 2018 trained on
CIFAR-I0 (Krizhevsky & Hinton]] 2009a), CIFAR- 100 (Krizhevsky & Hinton 2009b), and SVHN
NNetzer al. 2011). In addition, we compare MobileNetV3 (Howard al. 2019) trained on Im- ageNet (Deng et al. 2009). We concentrate on classification problems since the empirical obser- vations are inferred from a classification task and since those problems are usually considered to benchmark new optimization approaches.
For each optimizer, we perform a comprehensive syyper-parmmtee grid search over all models trained on CIFAR-10 10 (see Appendix G.I). The best performing hyper-parametery, on the validation set are then reused for all other experiments. The latter is done to check the robustness of the optimizer by handling all other datasets as if they were unknown, as is usually the case in practice. Our aim here is to show that satisfactory results can be achieved on new problems without any fine-tuning needed. Further experimental details are found in Appendix G
Figure as well as Appendix Figures I0 9 show that both LABPAL approaches outperform PLS, GOLSI and PAL considering training loss, validation accuracy, and test accuracy. LABPAL&NSGI tends to perform more robust and better than LABPAL&SGD. LABPAL&NSGD outperforms SGD tuned with a piece-wise constant schedule and challenges SLS on validation and test accuracy. On CIFAR-100, our approaches even perform better than all others. The important result is that hyper- parameter tuning for LABPAL is not needed to achieve good results across several models and datasets. However, this also is true for pure SGD, which suggests that the simple rule of performing a step size proportional to ||g| is sufficient to implement a well- performing line search. This also strengthens the observation of (Mutschler & Zell (02I), which states that SGD, with the correct leamingg rate, is already performing an almost optimal line search.
The derived learning rate schedules of the LABPAL approaches are significantly different from those of the other line search approaches (Figure 4, [ 10 first row). Interestingly they show a strong warm up phase at the beginning of the training followed rather constant phase which can show minor learning rate changes with an increasing trend. The warm up phase is often seen in sophisticated learning rate schedules for SGD; however, usually combined with a cool down phase. The latter is not apparent for LABPAL since we increase the batch size. LABPAL&NSGD indirectly uses learning rates of up to 10? but still trains robustly.
comparison of training speed and memory consumption is given in Appendix [ In short, LAB- PAL has identical GPU memory consumption as SGD and is on average only 19.6% slower. How- ever, for SGD usually a grid search is needed to find good X, which makes LABPAL considerably cheap.
4.3 ADAPTATION TO VARYING GRADIENT NOISE
Recent literature, w.g. (Mutschler & Zell 2020), (Vaswani et al., 2019). (Katka & Wilke 2019
show that line searches work with a relatively large batch size of 128 and training set size of approximately 40000 on CIFAR-10. However, a major, yet not deeply considered problem is that line searches operating on the mini-batch loss vary their behavior with another batch- and training set sizes leading to varying gradient noise. E.g.,
shoows that training with PAL and a batch size of 10 on CIFAR-I0 10 does not work at all. The reason is that the by mini-batches induced gradient noise, and with it the difference between the full-batch loss and the mini-batch loss, increases. However, we can adapt LABPAL work these scenarios by holding the noise scale is exposed to approximately constant. As the learning rate is inferred directly, the batch size has to be adapted. Based on the linear approximation of the noise scale (see Equation 5) adaptation factor
we directly estimate a noise
adapt LABPAL's hyperparameter:
Unese
p
Doeul
128
|1
Vort
Bnew
Dors
Brew
40, 000
The values the original batch size [Bori and the original dataset size [Dors] originate from our search for best-performing hyperparameters on CIFAR-10 with training set size of 40,000, a batch size of 128, and 150,000 training steps. We set the number of training steps to 150, 000c and multiply the batch sizes in the batch size schedule & by e. This rule makes the approach fully parameter less in practice.

---

Under review conference paper ICLR 2022
validacoon accunay CIFAR 10 DenseNet 121
valiiation accuracy CIEAR TO DenseNet 121
8:50
14.32
valdition J00un2y
30-
Volkdationn accuray
0.20
0.55
2.54
0.32
apodit
Figure 5: Performance comparison at batch size 10 on CIFAR-10. Left: reusing the same hyper- parameters as for batch size 128. Right: applying the directly estimable noise adaptation factor the LABPAL approaches and performing a grid search for optimal hyperparameters for the other approaches. On validation and test accuracy the LABPAL approaches outperform SGD, whereas on training loss they compete with it. (For more details see Appendix Figure 11 12. PLS curves are incomplete since training failed.
Figure shows
shows that LABPAL approaches fail when the gradient noise factor is not applied, but they improve their performance significantly if it is applied. Now, they even surpass SGD on validation For all other approaches, comprehensive hyperpa- Except for SGD, even the best-found hyperparameters
and test accuracy (Appendix Figure II & 12
rameter search is done (see Appendix G.1
could not handle the higher noise.
4.4 HYPERPARAMETER SENSITIVITY ANALYSIS
We performed a detailed hyperparameter sensitivity analysis for LABPAL&SGD and LAB- PAL&NSGD. To keep the calculation cost feasible, we investigated the influence of cach hyperpa- rameter, keeping all other hyperparameters fixed to the default values (see Algorithm D] Appendix Figure [ and and [ the following characteristics: Extimating new Supd À with TB, smaller than 640 decreases the performance since 4 is not fitted well enough (row 1). The performance also decreases if reusing the A (or supd) for more update steps (row 2), and if using a step size adaptation of less than 1.8 (row 3, except for ResNet). This shows that optimizing for the locally optimal minimum in line direction is not beneficial. From a global perspective, a slight decrease of the loss by performing steps to the other side of the parabola shows more promise. Interestingly, even using larger than two still leads good results. (Mutschler & Zell, 2021) showed that the loss valley in line direction becomes wider during training. This might be a reason why these update steps, which should actually increase the loss, work. Using a maximal step size of less than 1.5 (row 7) and increasing the noise adaptation factor (row 9) while keeping the batch size constant also decreases the performance. The latter indicates that the inherent noise of SGD is essential for optimization. addition, we considered a momentum factor and conclude that a value between 0.4 and 0.6 increases the performance for both LABPAL approaches (row 5).
5 LIMITATIONS
Our approach can only work if the empirically found properties we rely on are apparent are still a well enough approximation. In Section [4.2 we showed that this is valid for classification tasks. In additional sample experiments, we observed that our approach also works on regression tasks using the square loss. However, it tends fail if different kinds of losses from significantly different heads of a model are added, as it is often the case for object detection and object segmentation.
A theoretical analysis is lacking since the optimization field still does not know the reason for the local parabolic behavior of l, is, and consequently, what appropriate function space consider for convergence is.
DISCUSSION & OUTLOOK
This work introduces robust line search approach for Deep Learning problems based upon em- pirically found properties of the full-batch loss. Our approach estimates learning rates well across models, datasets, and batch sizes. It mostly surpasses other line search approaches and challenges SGD tuned with piece-wise constant learning rate schedule. We are the first line search work that analyses and adapts varying gradient noise. In addition, we show that mini-batch gradient norm information is not necessary for training. In future, we will analyze the causes for the local parabolic behavior of the full-batch loss along lines, to get a better understanding of DNN loss landscapes and especially of why and when specific optimization approaches work.

---

Under review conference paper ICLR 2022
REPRODUCIBILITY
Experimental details including all hyperparameters used for the experiments presented Section A are found in App. G.1 The source code to reproduce our experiments including our implementations of SLS. GOLSI, PLS, PAL and LABPAL is provided in the supplementary materials.
ETHICS STATEMENT
Since we understand our work as basic research, it is extremely error-prone to estimate its spe- cific ethical aspects and future positive or negative social consequences. As optimization research inftuences the whole field of deep learning, we refer to the following works, which discuss the ethical aspects and social consequences of Al and Deep Learning in a comprehensive and general way Yudkowsky al. (2008); Muchlhauser & Helm (2012) Bostrom Yudkowsky (2014).
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg Corrado, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawat, lan Goodfellow, Andrew Harp. Geoffrey Irving, Michael Isard, Yangging Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenherg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya 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: http://wwwweeesro..ooooooo org/ Software available from tensorflow.org.
Lukas Balles. Probabilistic line search tensorflow implementation, 2017. line_
URL
https: https://github. com http://///ooaaallee.eeeeeeeeeeea search/ faarch/coomit/a33d555
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. ICLR, 2018.
Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar. Training neural networks for and by interpolation. ICML, 2020.
Nick Bostrom and Elizzer Yudkowsky. The ethics of artificial intelligence. The Cambridge hand- book of artificial intelligence, 1:316-334, 2014.
Younghwan Chae and Daniel N. Wilke. Empirical study towards understanding line search approx- imations for training neural networks. arXiv, 2019.
Soham De, Abhay Kumar Yadav, David W. Jacobs, and Tom Goldstein. Big batch SGD: automated inference using adaptive batch sizes. arXiv, 2016.
J. Deng, W. Dong, Socher, L.-J. Li. Li, and L. Fei-Fei. ImageNet: Large-Scale Hierarchical Image Database. CVPR, 2009.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred A. Hamprecht. Essentially bar- riers in neural network energy landscape. ICML, 2018
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res., 12:2121 121-2199, 2011.
Stanislav Fort and Stanislaw Jastrzebski. Large scale structure of neural network loss landscapes. NeurlPS, 2019.
Tan J Goodfellow, Oriol Vinyals, and Andrew M Saxe. Qualitatively characterizing neural network optimization problems. ICLR, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CVPR, 2016.
10

---

Under review conference paper ICLR 2022
Andrew Howard, Ruoming Pang, Hartwig Adam, Quoc Le, Mark Sandler. Bo Chen, Weijun Wang, Liang-Chieh Chen, Mingxing Tan, Grace Chu, Vijay Vasudevan, and Yukun Zhu. Search- ing for mobilenetv3. ICCV, 2019.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. CVPR, 2017.
Nocedal Jorge and Wright Stephen. Numerical Optimization, Springer series in operations research. Springer, 2nd ed edition, 2006. ISBN 97800577000031103337000000
Dominic Kafka and Daniel Wilke. Gradient-only line searches: An alternative probabilistic line searches. arXiv, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. ICLR, 2015.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, 2009a.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers features from tiny images. Tech- nical report, 2009b.
Hao Li, Zheng Xu, Gavin Taylor, and Tom Goldstein. Visualizing the loss landscape of neural nets. NeurIPS, 2018.
Ilya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. ICLR, 2017.
David G Luenberger, Yinyu Ye, al. Linear and nonlinear programming, volume 2. Springer, 1984.
Maren Mahsereci and Philipp Hennig. Probabilistic line searches for stochastic optimization. Mach. Learn. Res., 18:119:1-119:59 2017.
Sam McCandlish, Jared Kaplan, Dario Amodei, and OpenAl Dota Team. empirical model large-batch training. arXiv, 2018.
Luke Muehlhauser and Louie Helm. The singularity and machine ethics. In Singularity Hypotheses, pp. 101-126. Springer, 2012.
Maximus Mutschler and Andreas Zell. Parabolic approximation line search for dnns. NewrIPS, 2020.
Maximus Mutschler and Andreas Zell. Empirically explaining sgd from line search perspective. ICANN, 2021.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. NewrIPS Workshop. 2011
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala, Pytorch: An imperative style, high-performance deep learning library. NeurlPS, 2019.
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. NeurlPS, 2018
Mark Sandler, Andrew G. Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chich Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. CVPR, 2018.
Leslie N. Smith. Cyclical learning rates for training neural networks. WACV, 2017.

---

Under review conference paper ICLR 2022
Samuel L Smith and Quoe Le. A bayesian perspective on generalization and stochastic gradient descent. ICLR, 2018.
Samuel I., Smith, Pieter-Jan Kindermans, Chris Ying, and Quoe V. Le. Don't decay the learning rate, increase the batch size. ICIR, 2018.
Sharan Vaswani, Aaron Mishkin, Issam Larudji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. NewrIPS, 2019.
Chen Xing, Devansh Arpit, Christos Tsirigotis, and Yoshua Bengio. A walk with sgd. arXiv, 2018.
Eliezer Yudkowsky et al. Artificial intelligence as a positive and negative factor in global risk. Global catastrophic risks, (303))1844 2008
12

---

Under review conference paper ICLR 2022
A HYPERPARAMTER SENSITIVITY ANALYSIS MobileNet-V2 V2
ResNet-20
DenseNet-128
90.
KD
Figure 6: Sensitivity analysis of parameters of LABPAL&SGD. The observations of LAB- PAL&NSGD described in Figure 7 are also valid for LABPAL&NSGD.
13

---

Under review conference paper ICLR 2022
ResNet-20
MobileNet-V?
DenseNet- 121
Cafll Tune
Boben Totee
Kiber Saroe
Figure 7: Sensitivity analysis of parameters of &NSGD.. The default parameters are: ap- proximation batch size B. 1280, SGD steps 1000, step size adaptation 1.8, batch size schedule = (0:1, 75000:2, 112500:4), momentum 3 = 0, maximal step size 1.0, noise-factor 1. For B, the factor 128 is multiplied with is given on the x axis.

---

Under review conference paper ICLR 2022
B FURTHER PERFORMANCE COMPARISONS
Toning an CRARIE Anho
TwAin OPAIAE Vinecle-72
2014
33
0.2
1.35
KXCaCCacC CEMAO EMD--ORAREINNN
CENAR D1D
025
0.52
1LS (c-0 30
FLS. (.00). 0000,
Figure 8: Performance comparison on CIFAR- R- of our approach LABPAL in the SGD and NSGD variants against several line searches and SGD. Optimal hyperparameters are found with elaborate grid search. Our approaches challenge and often outperform the other approaches on training loss, validation, and test accuracy. Columns indicate different models. Rows indicate different metrics.
15

---

Under review conference paper ICLR 2022
lesrning ImtageNet
Inining MohoicNas-V3
10a
10P
tmining
1094
10
10
20
30
stegs
spocts
validation accunccy LungeNNet MobileNet-V3
occuneey ImageNNe MobillNec--V3
0.54
0.58
acundy
0.62
0.54
LABPAL- NSGLD [B. 7. L8 1000
LARPAL-SOI:
0.51
S1S: P: O.1, 08 0.1
100
spoche
with hos val
-10-2
Figure 9: Performance comparison of top eπrо IMAGENET of approach LABPAL in the SGD and NSGD variants against elaborate grid search. Optimal hyperparameters found with detailed grid search for CIFAR-IO are reused. Our approaches challenge the other approaches training loss and test accuracy. SLS fails shortly after beginning the training due to too high estimated learning rates. For LABPAL the adaptation factor introduced in Section 4.3 is applied.
SGD. Optimal hyperparameters are found with an
16

---

Under review conference paper ICLR 2022
10'
13:5
1.00
1.0
3.0
120
200
250
3.90
3000
0.70
1/70-
T.TERAL Notth
LASTAL-SG D..)
SLS C...B.C
2/00
Figure 10: Performance comparison SVHN of our approach LABPAL in the SGD and NSGD variants against several line search and SGD. Optimal hyperparameters found with detailed grid search for CIFAR- 10 are reused. Our approaches challenge and often surpass the other approaches on training loss, validation, and test accuracy. Columns indicate different models. Rows indicate different metries.
17

---

Under review conference paper ICLR 2022
C
FURTHER RESULTS FOR BATCH SIZE 10
Compenne: CTAC 11NOMA
0.52
100
0.5
1.44
CIRA--12 XoNNeo2
0.50
0.02
3000
0.50
3.00
Figure 11: Performance comparison of several models on CIFAR-10 with batch size 10. The same hy perparameeeess used for batch size 128 (see Figure & PAL and PLS fail in this scenario. The LABPAL approaches work well the beginning but fail to estimate well learning rates later; this is solved in Figure 12] Interestingly, they still achieve competitive validation and test accuracies.
18

---

Under review conference paper ICLR 2022
(TTAL 11M
13.4
Lsakig
10
127
180
3.05
0.5
1.0
150
280
250
3/2
3.0
314
201
250
300
3.00
Figure 12: Performance comparison of several models on CIFAR-10 with batch size 10. For the LABPAL approaches only the noise f'ccorr adapted according equation 7 For all other ap- proaches, grid search is performed to find the best hyperparameters for this scenario. (see Ap- pendix G.1.. In comparison to Figure 11 now, the LABPAL approaches perform competitive on the training loss and surpass the other approaches validation and test accuracy. PLS plots are incomplete since the training failed after some steps.
19

---

Under review conference paper ICLR 2022
D WALL CLOCK TIME AND GPU MEMORY COMPARISON
PLLABPAL-SDDAR RABAL-SGDDLLAPPLLNNEE
speed compasison
max, GPU memory allocation
GPU memory on CIFAR 10 CD
14
CIFAR-100
e
10
DemscNes-121
MobileNes V2
BeaNes. 20
DonseNes122 121
MokileNes V2
ReaNies 20
Training time comparison on CIFAR-10. SGD, SLS, and PAL show similar training times. GOLSI, and both variants of LABPAL are slightly slower (up to 19.6%). However, a slightly longer training time acceptable if less time has to be spent in hyper-parameter tuning. PLS significantly slower. Note that in comparison to SGD, the implementations of the other optimizers are not optimized on CUDA level. Right: Maximum allocated memory comparison on CIFAR- 10. Except for PL.S all approaches need approximately the same amount of memory.
Figure Left:
E THEORETICAL CONSIDERATIONS
As the field does not know what the reason for the local parabolic behavior of the full-batch loss and, thus, what an appropriate function space to consider for convergence is, we refer to the theoretical analysis of (Mutschler & Zell 2020). They show convergence quadratic loss. This also valid for LABPAL, with the addition that each mini batch-loss can of any form as long the mean over these losses is quadratic function.
RELATION OF UPDATE STEP ADAPTATION AND THE FIRST WOLFE CONSTANT W1.
Let f : IR + IR be of form x - ay² + cc. condition, sufficient decrease condition):
We start with the first Wolfe condition (a.k.a. Armijo
fro + v) I f(za) yV (
in our case xo 0, wi wolfe constant
(8)
fly) _ f(0) + ybur
(9)
ay² + by + c < c ybw
use quadratic shape, fz(z)) =
(10)
ay² + by ybw 1 0
(11)
a 2 by ay
1 w1
(12)
by
-b
2 1 W1
set y
[1,2)
(13)
2a
-2w + 2 =
(14)
20

---

Under review conference paper ICLR 2022
G FURTHER EXPERIMENTAL DETAILS
Further experimental details for the optimizer comparison in Figure 8 10
of Sections 4.2
&
4.3
PLS: We adapted the only available and empirically improved TensorFlow (Abadi al. 2015)
implementation of PLS (Balles) 2017), which transferred PyTorch (Paszke et 2019) by
Vaaswan et al. 2019), to run on several state-of-the-an art models and datasets.
The training steps for the experiments in section Section 4
were 100,000 for DenseNet and 150,000
steps for MobileNetv2 and ResNet-22. Note that we define one training step processing one input batch to keep line search approaches comparable.
The batch size was 128 for all experiments. The validation/train set splits were: 5,000/45,000 for CIFAR-10 and CIFAR- 100 20,000/45,000 for SVHN.
All images were normalized with mean and standard deviation determined over the dataset. We used random horizontal flips and random cropping of size 32. The padding the random crop was 8 for CIFAR-100 and 4 for SVHN and CIFAR-10.
All trainings were performed on Nvidia Geforce 1080-TI GPUs.
Results were averaged over three runs initialized with three different seeds for each experiment.
For implementation details, refer to the source code provided in the supplementary materials.
G.1
HYPERPARAMETER GRID SEARCH CIFAR-10
For our evaluation, we used all combinations out of the following hyperparameters.
SGD:
hyperparameter learning rate
symbol
values
(0.1, 0.01, 0.001, 0.0001} {0.0)
momentum
a
PAL:
hyperparameter
symbol
values
measuring step size
[0.1,
direction adaptation factor 8
{0.0}
update step adaptation
1.66.
maximum step size
Smaz
[3.16
(== 1)
LABPAL (SGD and NSGD): hyperparameter
symbol
values
step size adaptation
(1.0, 1.25, 1.5, 1.8, 1.9)
SGD steps
(1000) keep speed comparable
initial measuring step size parabolic approximation sample step size approximation batch size
(0.01,0.1) (0.1,0.01) (5, 10, 20)
{(0 1,000 2, 112500 33, 1, 2, 112500 :4)
batch size schedule
bs
GOLSI:
hyperparameter initial step size
symbol
values
/
{0.1,1}
momentum
/
{0.0]
step size scaling parameter
7)
(0.2,2.0}
modified wolfe condition parameter
c2
(0.9.0.99]
21

---

Under review conference paper ICLR 2022
PLS:
hyperparameter
symbol
values
first wolfe condition parameter acceptance threshold for the wolfe probability initial step size
Ci
{0.005, 0.05, 0.5} {0.2,0.3, 0.4] {10
cW
ao
SLS:
hyperparameter
symbol
values
initial step size step size decay
(0.1,1)
0..9.
step size reset
Y
[2.0}
Armijo constant
0..10
maximum step size
Mmar
(10.0}
22


Reviews:
[{"review_id": "rJG0sPFHJZL", "reviewer": "Reviewer_w2rC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main drawback of this work is that LABPAL is compared to SGD and not to SGD with momentum, even though the fundamental idea behind them is very similar. I think what could make this work strong is showing a competitive result by comparing Momentum SGD with and without LABPAL step sizes. Without it the practical value of the proposed idea is quite limited even if it may outperform other line search methods or SGD tuned optimally.\n\nAnother concern I have is in the limited technical novelty and its implication when taking into account other scenarios where the assumptions/observations do not hold or generalize. LABPAL is essentially the backtracking line search with estimating full loss with multiple large mini-batches, and yet its reliance on empirical observations only pertaining to a certain task (image classification) make the scope of this method being applied to quite limited, not to mention that the arbitrarily chosen hyperparameters required to make LABPAL work may not generalize.\n\nThe Derivation step 4 seems really like a heuristics that may not hold depending on some data distributions/characteristics.\n\nIt's not obvious that why the step sizes have to increase after some period of time.", "summary_of_the_paper": "This work proposes a line search method LABPAL for first order methods to train neural networks with SGD. This work is motivated to address the issues in previous works that while the classical line search methods assume the exact descent direction, which is expensive to calculate for large data, the inexact methods based on mini-batches of examples are not robust. The idea is to leverage the two empirical observations on the loss landscape that the full-batch loss along lines in the SGD update direction is shaped parabolically and the optimal step size changes rather slowly. The authors provide extensive experimental results using various neural network models for image classification to compare LABPAL performed with either SGD or normalized SGD to other line search methods and show that LABPAL can perform better than SGD tuned optimally.", "summary_of_the_review": "While it is interesting to see a new line search method that is competitive to existing line search methods, the comparison doesn't seem entirely fair given that the proposed method shares essentially the same idea used in momentum. Maybe authors could give an estimate as to the required amount of total computations and compare it to that of momentum SGD.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dp1pXS7yyZM", "reviewer": "Reviewer_rHNN", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Adaptive learning rate methods for SGD are important and improvements over previous line search methods have the potential for significant impact.  However, the evaluation of different methods in the paper are either lacking or significantly suboptimal.\n\nFor the former, evaluated methods should be more extensive; SGD with a constant learning rate or piece-wise constant learning rate are not widely used (outside of ResNet architectures for the latter [1]).  At the very least, SGD with a decaying learning rate should be compared to.  Furthermore, the evaluation of other methods does not seem correct.  For instance, SLS uniformly performs terribly for CIFAR-100 ResNet and DenseNet, in stark contrast to the results in the original SLS NeurIPS 2019 paper.  Can the authors please comment on such a large discrepancy?  With regards to how the hyperparmaters for various methods are tuned, the grid search looks coarse and the search space very suboptimal, which is supported by ResNet-20 only achieving ~60% accuracy (for SGD) on CIFAR-100.  This is further supported by PLS only beginning with an initial step size of 10^{-4}; ResNet architectures for CIFAR-100 have displayed excellent performance using PLS with an initial learning rate of 0.1, which is then divided by 10 half-way through training and further divided by 10 three-fourths through training [1].  At the very least, the initial learning rate for this optimizer should always be the optimal learning rate for SGD output during hyperparameter optimization.\n\nOther comments:\n-\"Gradient-only line search (GOLSI)... its performance is rather weak.\"<- Please include citation for this claim\n\n-\"This was done for 10,000 consecutive SGD update steps of a ResNet18’s training process on a subset of CIFAR-10. Representative plots of their 10,000 measured full-batch losses along lines are presented in Figure 1. Relevant insights and found properties of these works will be introduced and exploited to derive our algorithm in Section 3.\" <- The problem with basing all presented work on this single study is that different learning schedules for SGD (and\nvariants) differ significantly for different datasets and problem domains.  See:\nSchmidt, Robin M., Frank Schneider, and Philipp\nHennig. \"Descending through a crowded valley-benchmarking deep\nlearning optimizers.\" International Conference on Machine\nLearning. PMLR, 2021.\n\n-\"Besides decreasing the learning rate, increasing the batch size remains an important choice to tackle gradient noise\" <- This is a point of contention in the literature; several studies report that increasing the batch size degrades performance [2,3].\n\n-The observation/derivation section in the paper is very difficult to read.\n\n-To clarify, the authors shrink the batch size from 128 to 10 in Figure 5, as a surrogate for increasing gradient noise.  Is that correct?  It would be interesting to see intermediate batch sizes from 128 decreasing to 10 to actually see how noise floor increases w.r.t. mini-batch size (a batch size of 10 is unreasonably small).\n\n\nReferences:\n[1] He, Kaiming, et al. \"Identity mappings in deep residual networks.\"\nEuropean conference on computer vision. Springer, Cham, 2016.\n[2] Keskar, Nitish Shirish, et al. \"On large-batch training for deep learning: Generalization gap and sharp minima.\" arXiv preprint arXiv:1609.04836 (2016).\n[3] Goodfellow, Ian, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.\n", "summary_of_the_paper": "The authors propose a parabolic line search for SGD to automatically adjust the learning rate during training.  The authors emphasize that their method is not motivated by theory, but on a previous empirical evaluation of ResNet-20 on CIFAR-10.  Their method is evaluated against several other recently proposed line search strategies for SGD (along with SGD using constant and piecewise learning rates) on CIFAR-100 for Resnet-20, MobileNet-V2, and DenseNet-121 (all using a mini-batch of 128).  The authors further show (in their method) how to overcome increasing noise levels in the gradient estimation of SGD by considering a mini-batch size of 10.", "summary_of_the_review": "Interesting take on a previously explored strategy for adaptable learning rates in SGD.  However, the results and (lack of) comparison to previous related methods does not look correct.", "strength_and_weaknesses": "", "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": "QoXqr29Ahsr", "reviewer": "Reviewer_mG5J", "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": "In this paper, the authors propose an algorithm for the automatic selection of the step size for SGD and apply this algorithm for DNN training. They suggest that full batch loss along the negative direction of the normalized batch gradient could be localy approximated with a parabola with high precision. So optimal step size could be also approximated as distance to minimum of that parabola. The authors notice that optimal step size changes slowly during SGD optimization process therefore one can reuse optimal step size for number of consequtive SGD updates and by doing that reduce algorithm complexity and made it applicable. \n\nWeak points:\n\n-W1. The overall novelty of paper is limited because propesed method LABPAL is straightforward modification of previously published PAL algorithm (https://arxiv.org/pdf/1903.11991.pdf). In LABPAL full batch loss is approximated via multiple  batches compared to single batch approximation in PAL. The difference in a way to perform parabolic approximation seems like a minor modification. Also, the experimental background for applicability of parabolic approximation (i.e. Observations 1, 2, 3, 4, 5, 6) is basically stated in the same way in https://arxiv.org/pdf/2103.17132.pdf as well as illustrations to these observations (figures 1, 2 matches figures 2, 6 from the latter paper). Other technical details like adaptation to varying gradient noise and relation with first Wolfe constant have marginal influence on the main point of the paper.\n-W2. The Observation 2 seems not well reasoned since the conclusion is made for only one choice of dataset and model and in other settings this observation may fail.\n\nStrong points:\n\n-S1. The experiments show that the proposed method outperforms other baseline methods on various datasets and that LABPAL produce stable results for a wide range of hyperparameters.\n", "summary_of_the_paper": "In this paper, the authors propose an algorithm for the automatic selection of the step size for SGD and apply this algorithm for DNN training. They suggest that full batch loss along the negative direction of the normalized batch gradient could be localy approximated with a parabola with high precision. So optimal step size could be also approximated as distance to minimum of that parabola. The authors notice that optimal step size changes slowly during SGD optimization process therefore one can reuse optimal step size for number of consequtive SGD updates and by doing that reduce algorithm complexity and made it applicable. ", "summary_of_the_review": "It seems that most part of the paper (including figures and statements) is taken from one of two previously published papers and hence the novelty contained in the paper itself is very limited.  This inclines me towards rejection of the paper in its current form. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "E_rfOA0e2u9", "reviewer": "Reviewer_kiNL", "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": "Strengths:\nTo the best of my knowledge, the exact idea proposed in this paper is novel.\n\nWeaknesses:\n- The algorithm is built on empirical observations of a specific image classification workload. The experiments only include image classification workloads, so whether this algorithm generalizes to other tasks (e.g. NLP tasks) is an open question.\n- Many of the design decisions made for the algorithm seem arbitrary, and there are many additional hyperparameters that seem important to tune. The method 1) approximates the full-batch loss using many mini-batch evaluations, 2) reuses the same step size for some consecutive steps, 3) increases the batch size with a piecewise constant schedule as training progress, and 4)uses a slightly larger step size value than the actual optimum given by the parabola by multiplying by a factor between 1 and 2. There are no ablation studies to understand which of these choices are important. Furthermore, they introduce many additional hyperparameters. In fact, looking at Section G.1 in the Appendix, it seems like LABPAL has the most number of hyperparameters.\n- There is no comparison to SGD with Momentum, which performs the best in the workloads considered in the experiments. Given that the method has so many additional hyperparameters, and the comparison with the best-performing optimizer is lacking, the practicality of the proposed method is questionable.\n- Section 4.3 (adaptation to varying gradient noise) doesn’t make much sense to me. It seems like all that is happening is the batch size is being increased. So then the comparison with other methods doesn’t seem fair, because the batch size is no longer the same.\n- Convergence analysis is missing.\n\nComments and questions:\n- The distinction between step size and learning rate is unclear. What exactly is the difference? Could you make things clearer in the paper? For example, it seems like in Equation 6, learning rate = \\lambda = alpha * s_{min,t}/||g_t||, but in the algorithm box, it seems like learning rate = learning rate * alpha.\n- In Section G.1, there are some parameters under LABPAL that I’m not sure were mentioned in the main paper: initial measuring step size, parabolic approximation sample step size, and approximation batch size.\n\n----\nUpdate:\nI have read the reviews from the other reviewers and the author responses. I agree with the authors that the paper's contributions are real and valid. However, as other reviewers also noted, I don't think the contributions are enough for acceptance, therefore, I am keeping my score. I would be excited to see a future version of the paper that has a wider range of experiments (maybe showing that the properties also hold for other deep learning tasks).", "summary_of_the_paper": "This paper uses empirical observations of Mutschler & Zell (2021) to come up with a line search algorithm called LABPAL, which is essentially fitting a 1-D parabola to the (approximate) full-batch loss in the direction of the mini-batch gradient, and using the minima of the parabola to obtain the step size. The authors include various tricks to make this approach work in practice. The show empirically on various image classification workloads that LABPAL is mostly better or on-par with SGD (with piecewise constant learning rate schedule) and other recent line-search methods.  \n", "summary_of_the_review": "The proposed method doesn’t seem practically useful. It introduces many additional hyperparameters, and it is unclear whether it performs better than SGD with Momentum, and in settings where it is not confirmed whether the empirical observations that justify the method hold. Therefore, I recommend rejection.", "strength_and_weaknesses": "", "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:

Meta-review: This work proposes a method for automatic adaptation of the learning rate via a estimating quadratic approximation of the full batch during training. The method motivated by two observed properties of the loss landscape, first the full batch loss along the gradient direction is well approximated by a quadratic polynomial, and second the optimal full batch step size does not change quickly during training. Two primary criticisms raised by reviewers is the weak experimental evidence provided to validate the method and similarities with other approaches for adapting the learning rate. Ultimately reviewers remain unconvinced by the rebuttal and maintained their scores. The AC further stresses the difficulty of properly (and fairly) comparing optimization methods in deep learning. As is consistently shown in the literature, optimizer performance is typically dominated by hyperparameter tuning, this is particularly problematic when submissions tune their own baselines as authors naturally are incentivized to tweak their own methods until the method looks favorable relative to others. Comparing directly against prior published results tuned by other researchers would help alleviate reviewer concerns regarding hyperparameter tuning.
Decision: Reject