# No learning rates needed: Introducing SALSA
\- Stable Armijo Line Search Adaptation

1st Philip Kenneweg  AG Machine Learning
Bielefeld University
Bielefeld, Germany
0000-0002-7097-173X  2nd Tristan Kenneweg  AG Machine Learning
Bielefeld University
Bielefeld, Germany
0000-0001-8213-9396  3rd Fabian Fumagalli  AG Machine Learning
Bielefeld University
Bielefeld, Germany
0000-0002-0935-5591  AG Machine Learning
Bielefeld University
Bielefeld, Germany
0000-0003-3955-3510 and 4th Barbara Hammer

###### Abstract

In recent studies, line search methods have been demonstrated to significantly
enhance the performance of conventional stochastic gradient descent techniques
across various datasets and architectures, while making an otherwise critical
choice of learning rate schedule superfluous. In this paper, we identify
problems of current state-of-the-art of line search methods, propose
enhancements, and rigorously assess their effectiveness. Furthermore, we
evaluate these methods on orders of magnitude larger datasets and more complex
data domains than previously done.

More specifically, we enhance the Armijo line search method by speeding up its
computation and incorporating a momentum term into the Armijo criterion,
making it better suited for stochastic mini-batching. Our optimization
approach outperforms both the previous Armijo implementation and a tuned
learning rate schedule for the Adam and SGD optimizers. Our evaluation covers
a diverse range of architectures, such as Transformers, CNNs, and MLPs, as
well as data domains, including NLP and image data.

Our work is publicly available as a Python package, which provides a simple
Pytorch optimizer.

##  I Introduction

In the field of modern machine learning, there are numerous optimization
algorithms available [1]. However, determining the most suitable algorithm for
a specific problem and finding the appropriate learning rate or learning rate
schedule often requires extensive expertise and computational resources. In
particular, the prevailing approach involves treating the learning rate as a
hyperparameter and training the network repeatedly until the optimal value
that yields the best performance is discovered. To simplify and expedite this
process, recent research in deep learning [2, 3, 4, 5] has proposed the
reintroduction of line search methods as popular optimization technology,
which effectively identify an appropriate learning rate by calculating the
loss using different step sizes and comparing its reduction to the gradient of
the loss function, hereby they eliminate costly hyperparameter tuning.

Traditional line search methods necessitate several forward passes per
gradient update, making it imperative to explore more efficient alternatives.
In the work by Vaswani et al. [2], a Stochastic Line Search (SLS) is
integrated with an intelligent re-initialization of the step size, effectively
mitigating the requirement of multiple forward passes at each step. This
approach was shown in [2, 6] to improve a variety of optimization methods,
such as Stochastic Gradient Descent (SGD) on tasks such as matrix
factorization as well as image classification for small networks and datasets.
In [7] the authors adapt this line search to preconditioned optimizers like
Adam [8] further increasing its usability.

In this paper we extend upon this work, by introducing a momentum term to the
SLS, critically improving its performance and stability. Furthermore, we
introduce a limitation on the frequency with which a line search is performed,
greatly reducing the computation needed. Additionally, we conduct extensive
experiments to evaluate the performance of various optimization methods across
different datasets domains and architecture options. Our findings demonstrate
that, our improved Stable Armijo Line Search Adaptation algorithm, called
SaLSa, consistently outperforms the previously introduced SLS as well as tuned
optimizers, with very little computational overhead (about 3% compared to no
line search). We observe the SaLSa optimizers have on average an 1.5%
advantage on accuracy and a 50% lower average log loss at end of training.
Additionally, the stability of the training is improved compared to previously
introduced versions of SLS.

To make our work easy to reproduce and use, we implement all methods as
PyTorch optimizers. The source code is open-source and free software (MIT
licensed) and available on github.

##  II Background

The stochastic Armijo line search described in [2] and [6] is designed to set
a step size for all network parameters $w_{k}$ at iteration $k$. In this
section, we closely follow [6] to formalize a modification of the Armijo
criterion to handle the ADAM [8] direction. This is based originally upon [2,
7] More importantly, we introduce an improved Armijo criterion, which
mitigates the effect of noise in the mini-batch setting by calculating an
exponential moving average smoothing on both sides of the Armijo equation.

We adopt the following notation from [6]: The loss function is denoted by
$f(w)$. $||\cdot||$ denotes the Euclidean norm and $\nabla f$ denotes the
gradient of $f$. Given the iteration counter $k$, $f_{k}$ and $\nabla f_{k}$
denote the mini-batch loss and its mini-batch gradient.

###  II-A Armijo Line Search

The Armijo line search criterion is defined as:

$f_{k}(w_{k}+\eta_{k}d_{k})\leq f_{k}(w_{k})-c\cdot\eta_{k}||\nabla
f_{k}(w_{k})||^{2}$ (1)

where $d_{k}$ is the direction (e.g., $d_{k}=-\nabla f_{k}(w_{k})$ in case of
SGD), $c\in(0,1)$ is a constant (commonly fixed to be $0.1$ [2]). The step
size $\eta_{k}$ which satisfies Condition 1 is practically obtained by
employing a backtracking procedure, see the pseudo-code in Algorithm 1:

Algorithm 1 Armijo Line Search

1: $\eta_{k}=\eta_{k-1}\cdot 2^{1/b}$

2: while not $f_{k}(w_{k}+\eta_{k}d_{k})\leq
f_{k}(w_{k})-c\cdot\eta_{k}||\nabla f_{k}(w_{k})||^{2}$ do

3: $\eta_{k}=\eta_{k}\cdot\delta$

4: end while

5: $w_{k+1}=w_{k}+d_{k}\cdot\eta_{k}$

To avoid a monotonically decreasing step size, $\eta_{k}$ is increased each
step as can be seen in line 1, ($b=500$ and $\delta=0.9$ in practice).

###  II-B Including preconditioned Optimizers (Adam)

Figure 1: The step size of ADAM + SLS as well as ADAM + SaLSa on ImageNet.
Colored areas indicate variance between runs. Notice the large variations for
ADAM + SLS compared to the consistent and stable behavior of ADAM + SaLSa.

In case of SGD, the direction $d_{k}$ is the negative mini-batch gradient.

$d_{k}=-\nabla f_{k}(w_{k})$

Adam’s direction defined in [8] can be written as:

$\begin{split}g_{k}&=\nabla f_{ik}(w_{k})\\\ m_{k}&=\beta_{1}\cdot
m_{k-1}+(1-\beta_{1})\cdot g_{k}\\\ v_{k}&=\beta_{2}\cdot
v_{k-1}+(1-\beta_{2})\cdot g_{k}^{2}\\\
\hat{m}_{k}&=m_{k-1}/(1-\beta^{k}_{1})\\\
\hat{v}_{k}&=v_{k-1}/(1-\beta^{k}_{2})\\\
d_{k}&=-\hat{m}_{k}/(\sqrt{\hat{v}_{k}}+\epsilon)\end{split}$ (2)

Adam integrates a momentum-based strategy along with a step-size correction
based on gradient variance. In the context of training Transformers, these
adjustments have proven to be significant improvements compared to the more
straightforward SGD algorithm [9].

The Armijo line search criterion from Eq. 1 must be adjusted for the Adam
optimizer. We perform this adjustment following [6] based on [2, 7]. To check
if the Armijo line search criterion is satisfied in the Adam case, we use the
direction $d_{k}$ defined in Eq. 2, with momentum $\beta_{1}=0$. Note that,
the Armijo criterion is only guaranteed to be satisfy-able by adjusting the
step size $\eta_{k}$, if the update direction and the gradient direction are
similar enough. However, this condition is not generally met when
$\beta_{1}\neq 0$ in Eq. 2. Additionally, we replace the gradient norm term
$||\nabla f_{k}(w_{k})||^{2}$ by the preconditioned gradient norm
$\frac{||\nabla f_{k}(w_{k})||^{2}}{\sqrt{\hat{v}_{k}}+\epsilon}$ as in [7]
resulting in Eq. 3.

$f_{k}(w_{k}+\eta_{k}d_{k})\leq f_{k}(w_{k})-c\cdot\eta_{k}\frac{||\nabla
f_{k}(w_{k})||^{2}}{\sqrt{\hat{v}_{k}}+\epsilon}$ (3)

Note that to perform final weight updates each step we use $\beta_{1}\neq 0$.

###  II-C SLS Failure Cases

Figure 2: The step size of ADAM + SLS (black) compared to ADAM + SaLSa (brown)
visualized during a training run of BERT on the MNLI dataset.

As shown in [2, 7] the previously described line search methods perform well
on smaller datasets and neural network architectures. However, here we show
that these methods have problems to consistently perform during larger scale
training.

The first of these problems we call ”mini-batch noise”: Eq. 1 and 3 describe
criterions which are checked for every mini-batch. This is problematic, since
the criteria will be violated subject to inherent noise in the mini-batch
data. The phenomenon is amplified by small mini-batch sizes. As can be seen in
Figure 2 in a typical training run the Armijo line search method leads to
frequent changes of the step size, see Figure 2.

Figure 3: The step size of ADAM + SLS (black) on the CIFAR10 dataset. We
sometimes observed drastic drops in step size due to computational precision
problems. When training with SaLSa (red) we do not observe any such drops.

Another frequently occurring problem is mini-batch gradient approximations
$\nabla f_{k}(w_{k})\approx 0$. These are due to computational precision
problems, even with float32 precision enabled. For an example see Figure 3. In
the original implementation by [7], whenever $\nabla f_{k}(w_{k})\leq 10^{-8}$
no line search was performed.

Additionally, a problem which only occurs on large datasets, can be seen in
Figure 1. The step size and its variance over 5 different runs on ImageNet is
visualized. We observe that the step sizes of SLS are very sensitive to
initial conditions, the only difference between the runs is the random
parameter initialization of the network and the shuffled dataset. This problem
only seems to occur on larger datasets and is quite impactful, as some runs do
not converge properly, or take very long to even begin converging.

##  III Methods

To obtain a line search method with better properties in the mini-batch
scenario, we propose to extend the Armijo criterion with a momentum term.
Below we provide a detailed explanation of the modifications we made, the
theoretical basis behind them, and our reasoning. Furthermore, we introduce a
method to greatly reduce the computational overhead introduced by a line
search.

###  III-A Addressing Mini-batch Noise

As an extension to Eq. 1 we propose an exponential smoothing (also called
momentum term) of all factors which are dependent on the mini batch in this
equation. First we rewrite Eq. 1:

$f_{k}(w_{k})-f_{k}(w_{k}+\eta_{k}d_{k})\geq c\cdot\eta_{k}||\nabla
f_{k}(w_{k})||^{2}$ (4)

$f_{k}(w_{k})-f_{k}(w_{k}+\eta_{k}d_{k})$ denotes the decrease in loss and
$||\nabla f_{k}(w_{k})||^{2}$ denotes the gradient norm. In order to apply
exponential smoothing to both terms we define $h_{k}$ and $s_{k}$ as follows:

$\begin{split}h_{k}=h_{k-1}\cdot\beta_{3}+(f_{k}(w_{k})-f_{k}(w_{k}+\eta_{k}d_{k}))\cdot(1-\beta_{3})\\\
s_{k}=s_{k-1}\cdot\beta_{3}+||\nabla
f_{k}(w_{k})||^{2}\cdot(1-\beta_{3})\end{split}$ (5)

$h_{k}$ represents the smoothed decrease of the loss with the current step
size, $s_{k}$ the smoothed gradient norm and $\beta_{3}\in(0,1)$ the smoothing
factor used for the exponential moving average.

We introduce the Stable Armijo Line Search Adaptation (SaLSa) criterion as:

$h_{k}\geq c\cdot\eta_{k}\cdot s_{k}$ (6)

Combining SaLSa and the Adam optimizer is done by computing $s_{k}$ as
follows:

$\begin{split}s_{k}=s_{k-1}\cdot\beta_{3}+\frac{||\nabla
f_{k}(w_{k})||^{2}}{\sqrt{\hat{v}_{k}}+\epsilon}\cdot(1-\beta_{3})\end{split}$
(7)

and computing $d_{k}$ as described in Eq. 2, but with $\beta_{1}=0$. We keep
the calculation procedure for the step size $\eta_{k}$ the same as previously
described.

###  III-B Intuitive Motivation

As mentioned in Section III due to the inherent noise in mini-batches we
expect some of them to violate the original Armijo line search, even if the
step size $\eta_{k}$ is appropriate for the majority of mini-batches around
step $k$ in training.

Let us assume that all mini-batches are normally distributed with respect to
the Armijo criterion, e.g. some mini-batches fulfill the condition with a wide
margin, most fulfill it with a small margin and some rare exceptional batches
violate the criterion. In this scenario we do not want to decrease the step
size by a large amount each time we get an exceptionally bad mini-batch, since
the step size is still fitting for most batches and the step size is only
increased slowly. The stable Armijo line search adaptation in Equation 6 is
implementing exactly this behaviour. Note that the exact distribution is not
relevant in this thought experiment.

If we analyze Equation 6, we notice that the right hand side is affected by
the current step size $\eta_{k}$ to the same degree as in the original Armijo
line search Equation 1. However, the left hand side is substantially less
affected since $\eta_{k}$ is part of the exponential smoothing process. This
results in a slower reduction of the step size $\eta_{k}$ as the criterion is
fulfilled more easily than the original criterion by lowering $\eta_{k}$.

###  III-C Theoretical Analysis

We extend the convergence Theorem introduced in the original Armijo paper [10]
for the full batch setting and the SaLSa criterion with SGD from Eq. 6. We
additionally require that every found learning rate yields an improved loss
$f(w_{k})-f(w_{k}+\eta_{k}d_{k})\geq 0$. This condition ensures the
convergence for an infinite sequence, which may otherwise not be guaranteed
due to the exponential smoothing. In practice, enforcing this condition did
not yield a significant difference in the optimization process and is thus not
implemented in our experiments.

######  Theorem 1 (Convergence Theorem).

Let $f\equiv f_{k}$. For $w_{0}\in\mathbb{R}^{d}$ let $S(w_{0}):=\\{w\mid
f(w)\leq f(w_{0})\\}$ and assume that
$f(w^{*}):=\inf_{w\in\mathbb{R}^{d}}f(w)$ exists for a unique point
$w^{*}\in\mathbb{R}^{d}$ with $\nabla f(w)=0$ for $w\in S(w_{0})$ if and only
if $w=w^{*}$. Any sequence $\\{w_{k}\\}_{k=1}^{\infty}$ found by the SaLSa
criterion with $f(w_{k})-f(w_{k}+\eta_{k}d_{k})\geq 0$ and $c<1$ converges to
$w^{*}$.

###### Proof.

The condition $f(w_{k})-f(w_{k}+\eta_{k}d_{k})\geq 0$ ensures that
$\\{f(w_{k})\\}_{k=1}^{K}$ is non-increasing and thus any infinite sequence
will converge to $f(w^{*})$, given the assumptions. It thus remains to show,
that in every step such a step size $\eta_{k}$ can be found. By definition, we
have that

$\displaystyle h_{k}$
$\displaystyle=\beta_{3}h_{k-1}+(1-\beta_{3})\left[f(w_{k})-f(w_{k}+\eta_{k}d_{k})\right]$
$\displaystyle\geq\beta_{3}c\eta_{k-1}s_{k-1}+(1-\beta_{3})\left[f(w_{k})-f(w_{k}+\eta_{k}d_{k})\right].$

If we assume, that there exists a learning rate $\eta_{k}\leq\eta_{k-1}$, such
that $f(w_{k})-f(w_{k}+\eta_{k}d_{k})\geq c\eta_{k}\|\nabla f(w_{k})\|^{2}$
(see proof of existence below), we can show that

$\displaystyle\beta_{3}c\eta_{k-1}s_{k-1}+(1-\beta_{3})\left[f(w_{k})-f(w_{k}+\eta_{k}d_{k})\right]$
$\displaystyle\geq$ $\displaystyle
c\eta_{k}\left[\beta_{3}s_{k-1}+(1-\beta_{3})\|\nabla f(w_{k})\|^{2}\right]$
$\displaystyle=c\eta_{k}s_{k},$

which finishes the proof, as we have found a learning rate $\eta_{k}$ that
fulfills the SaLSa criterion.

We now prove the existence of $\eta_{k}\leq\eta_{k-1}$ with
$f(w_{k})-f(w_{k}+\eta_{k}d_{k})\geq c\eta_{k}\|\nabla f(w_{k})\|^{2}$ by
contradiction, i.e. we assume that such a $\eta_{k}$ does not exist and thus
$f(w_{k})-f(w_{k}+\eta_{k}d_{k})<c\eta_{k}\|\nabla f(w_{k})\|^{2}$ for
$\eta_{k}\leq\eta_{k-1}$. Using the Taylor expansion for $f$ around $f(w_{k})$
yields

$\displaystyle f(w_{k})-f(w_{k}+\eta_{k}d_{k})=-\eta_{k}d_{k}\nabla
f(w_{k})-o(\eta_{k}).$

For $\eta_{k}\leq\eta_{k-1}$ it follows then

$\displaystyle c\eta_{k}\|\nabla f(w_{k})\|^{2}>-\eta_{k}d_{k}\nabla
f(w_{k})-o(\eta_{k}).$

Dividing both sides by $\eta_{k}$ and taking the limit for $\eta_{k}\to 0$
yields

$\displaystyle c\|\nabla f(w_{k})\|^{2}>-d_{k}\nabla f(w_{k}),$

and thus with $d_{k}=-\nabla f(w_{k})$ it follows $c>1$, which is a
contradiction. ∎

###  III-D Addressing Computational Costs

It is unnecessary and computationally expensive to perform a line search for
every step during training, as for most steps the step size does not need to
be changed. The overall training compute cost increases by roughly 30% when
performing a line search every step. To address this, we propose to perform a
line search more regularly when a high rate of change of the step size is
detected and less regularly otherwise. We realize this by keeping 2 different
exponential moving averages of the step size $\eta_{k}$ which we update after
every line search procedure:

$\bar{\eta}_{k}(\beta)=\beta\bar{\eta}_{k-1}+(1-\beta)\cdot\eta_{k-1}$ (8)

We calculate the average rate of change as follows:

$r_{k}=\frac{\bar{\eta}_{k}(0.9)}{\bar{\eta}_{k}(0.99)}$ (9)

and invert it if $r_{k}\leq 1$:

$\bar{r}_{k}=\begin{cases}r_{k}&\text{if }r_{k}\geq 1\\\
r_{k}^{-1}&\text{otherwise}\end{cases}$ (10)

we set the line search frequency $L_{k}$ to the closest integer of:

$L_{k}=\frac{1}{\bar{r}_{k}-1}$ (11)

and clamp it to the range $L_{k+1}\in[1,10]$. We perform the line search every
$L_{k+1}$ steps. This reduces the extra compute needed from roughly 30% to
approximately 3% for longer runs, see Figure 4. In practice, we did not notice
any performance degradation.

Figure 4: Wall clock run times on various datasets using the Speed-up
described in III-D

###  III-E Practical Considerations

In the original Armijo line search implementation a few outliers dominated the
determination of $\eta_{k}$ as shown in Figure 2. The hyperparameter $c$ was
set with this in mind. In our experiments we found good values for $c$ to be
in the range $c\in[0.3,0.5]$. For all our experiments we used $c=0.3$
(compared to $c=0.1$ for the original Armijo line search criterion).

Furthermore, we tuned the hyperparameter $\beta_{3}\in[0.9,0.999]$ from Eq. 5
on a variety of datasets. We found that although performance is robust to the
choice of $\beta_{3}$, a value of $\beta_{3}=0.99$ is the best general choice.
Larger $\beta_{3}$’s result in slower adaptation of the step size to the loss
landscape, but less susceptibility to noise.

We performed Ablation studies on the impact of different $\beta_{3}$ and $c$
values. While we found $\beta_{3}$ to have a minor impact on performance
different $c$ values do tend to have a more substantial impact. But in
contrast to the learning rate, the $c$ hyperparameter seems to have an
architecture and dataset independent optimum of $c=0.3$.

##  IV Experimental Approach

In this section, we detail our experimental design to investigate the
performance of our proposed optimization method. We utilize datasets, model
implementations and weights from the Huggingface library [11], the pytorch
datasets library and the nanoGPT [12] github repository.

###  IV-A Candidates

A quick overview of all candidates we are evaluating can be seen below:

  * •

SGD with tuned learning rate and learning rate schedule

  * •

ADAM with tuned learning rate and learning rate schedule

  * •

SGD + SLS, see Section II-A

  * •

ADAM + SLS, see Section II-B

  * •

SGD + SaLSa, see Section III

  * •

ADAM + SaLSa, see Section III

As a baseline comparison we evaluate the ADAM and SGD optimizers with a cosine
decay with warm starting for 10% of the total training time. For NLP tasks
this warm starting and cosine decay is common practice. For the image tasks we
compare to a flat learning rate as done in [2].

We take the peak learning rate for ADAM on natural language tasks $\eta=2\cdot
10^{-5}$ from the original Bert paper by [13], which presents a good value for
a variety of classification tasks, including the Glue [14] tasks upon which we
are evaluating. We found the value for the peak learning rate for SGD on the
NLP task $\eta=2\cdot 10^{-3}$ using a grid search.

We found the value $\eta=1\cdot 10^{-3}$ for image classification for ADAM
using a grid search. The same procedure resulted in $\eta=1\cdot 10^{-1}$ for
SGD.

###  IV-B Datasets and Models

To evaluate an optimization method it is necessary to perform large scale runs
of complex real world datasets and tasks. This is especially important as many
optimization methods perform well on small scale or clean theoretical tasks,
but fail to perform well on real world data.

_Natural Language Processing - Transformers_

We consider a common scenario in natural language processing, where a large
pre-trained language model (in our case Bert [13]) is fine-tuned on a small to
medium sized dataset, similar to previous papers [6]. The Glue dataset,
introduced by Wang et al. (2018) [14], comprises a diverse set of widely
recognized natural language processing (NLP) classification tasks. This
dataset serves as a benchmark for evaluating common NLP capabilities. The
versions of the datasets utilized in this study are sourced from tensorflow-
datasets 4.0.1.

To be specific, of the Glue collection [14], we use the datasets Stanford
Sentiment Treebank _SST2_ , Microsoft Research Paraphrase Corpus _MRPC_ ,
Stanford Question Answering Dataset _QNLI_ , and the Multi-Genre Natural
Language Inference Corpus _MNLI_. These datasets range from 500 - 400.000
training samples and represent a variety of fine-tuning tasks.

As a further evaluation metric for language models, we fine-tune GPT-2 [15] on
the Shakespeare dataset as described in [12] implementation.

_Image Classification - Convolutional Neural Networks_

In image classification common evaluation datasets are CIFAR10 and CIFAR100
[16], both being small scale (50.000 samples, 32x32 resolution). To obtain
more reliable results we also compare on ImageNet [17] which consists of
roughly $10^{6}$ samples. We use the ResNet34 [18] architecture without pre-
training for small datasets and ResNet50 for ImageNet.

###  IV-C Implementation Details

The following details are the same for all experiments: All models are trained
5 times and the averaged metrics are reported in Tables I and II. The learning
curves as well as standard errors are visualized in Figures 5 and 6.

A Bert [13] model was trained on the NLP dataset with the following
hyperparameter choices: Five epochs training time on each dataset. The pooling
operation used in the Glue experiments is [CLS]. The maximum sequence length
is set to 256 tokens. The batch size used during training is $32$.

For the image datasets CIFAR10 and CIFAR100 [16] ResNet34 [18] was used. For
the ImageNet [17] dataset the ResNet50 [18] architecture was used, a larger
architecture was used due to the increased amount of complexity and size of
the dataset. The batch size used during training is set to 128 for Cifar10 and
Cifar100 and 256 for ImageNet. We applied pre-processing as described in the
ResNet paper by [18]. Models were trained on CIFAR10 and CIFAR100 for 100
epochs and on ImageNet for 12 epochs.

The computing time for all experiments was roughly 65 days on an A40 GPU.
Roughly 15 of these days were used for the NLP tasks and 50 for the image
datasets.

##  V Experimental Results

In this section, we will describe the results of our experiments. We compare
the 6 candidates as described in Section IV-A. All metrics reported are
average values obtained using 5 training runs. All accuracies presented below
are computed based on the validation sets. The losses presented are computed
on the training sets and are smoothed using an exponential moving average. The
shaded regions surrounding each line denote the standard error for each
experiment. Figures 5 and 6 showcase the accuracies and losses throughout the
training period. Tables I and II provide a representation of the peak
accuracies and final losses for each candidate. In summary, we observe the
SaLSa methods having on average an 1.5% advantage on accuracy and a 50% lower
average log loss at end of training.

###  V-A Natural Language Processing - Transformer Experiments

(a) MNLI

(b) MRPC

(c) QNLI

(d) MNLI

(e) MRPC

(f) QNLI

Figure 5: The top row depicts the loss curves, while the bottom row depicts
the accuracy curves from experiments conducted on the GLUE dataset. Standard
errors are represented around each curve with a shaded area. Accuracy
measurements are calculated on the validation data, loss calculations were
based on the training data.

(a) ImageNet

(b) Cifar 100

(c) Cifar 10

(d) ImageNet

(e) Cifar 100

(f) Cifar 10

Figure 6: The top row depicts the loss curves, while the bottom row depicts
the accuracy curves from experiments conducted on the image datasets. Standard
errors are represented around each curve with a shaded area. Accuracy
measurements are calculated on the validation data, loss calculations were
based on the training data.

In our NLP experiments, as shown in Figure 5 and in the Appendix for GPT-2 and
SST2, we have observed that, on average, ADAM + SaLSa achieves a lower final
loss compared to ADAM, ADAM + SLS, and SGD + SLS. However, this improvement in
loss does not always translate to a significant difference in the accuracy
metric. ADAM + SLS and ADAM + SaLSa perform similarly in terms of accuracy,
but both outperform ADAM and SGD + SLS on average. Note that for similar final
losses, the convergence rate of SaLSa is generally faster than that of ADAM,
as depicted in Figure 5.

TABLE I: Peak classification accuracies, averaged over 5 runs, for all datasets and optimization methods. Best performing optimization method is marked in bold.  | ADAM | SGD | ADAM | SGD | ADAM | SGD
---|---|---|---|---|---|---
| - | - | SLS | SLS | SaLSa | SaLSa
MNLI | 0.8340 | 0.8256 | 0.8446 | 0.8303 | 0.8409 | 0.8305
QNLI | 0.9090 | 0.8972 | 0.9044 | 0.8971 | 0.9090 | 0.9014
MRPC | 0.8279 | 0.8441 | 0.8667 | 0.8441 | 0.8745 | 0.8473
SST2 | 0.9271 | 0.9225 | 0.9261 | 0.9167 | 0.9216 | 0.9245
ResNet34 |  |  |  |  |  |
CIFAR10 | 0.9312 | 0.9229 | 0.9401 | 0.9453 | 0.9389 | 0.9384
CIFAR100 | 0.6733 | 0.7057 | 0.7128 | 0.6859 | 0.7114 | 0.7064
ResNet50 |  |  |  |  |  |
ImageNet | 0.6486 | 0.5633 | 0.4836 | 0.6234 | 0.6684 | 0.6594
average | 0.8215 | 0.8116 | 0.8111 | 0.8204 | 0.8378 | 0.8297
average rank | 3.57 | 4.86 | 2.42 | 4.43 | 2.14 | 3.28
TABLE II: Final losses, averaged over 5 runs, for all datasets and optimization methods. Best performing (minimal loss) optimization method is marked in bold. The logarithmic average is taken due to the logarithmic nature of the typical loss. | ADAM | SGD | ADAM | SGD | ADAM | SGD
---|---|---|---|---|---|---
| - | - | SLS | SLS | SaLSa | SaLSa
MNLI | 0.009567 | 0.08613 | 0.03713 | 0.06901 | 0.005867 | 0.02174
QNLI | 0.00258 | 0.02079 | 0.00504 | 0.03667 | 0.000628 | 0.0091627
MRPC | 0.01312 | 0.1978 | 0.007298 | 0.05262 | 0.003126 | 0.03862
SST2 | 0.005857 | 0.02561 | 0.009457 | 0.0412 | 0.006991 | 0.01837
GPT-2 | 2.86 | 3.572 | 2.917 | 3.566 | 2.772 | 3.559
ResNet34 |  |  |  |  |  |
CIFAR10 | 0.01394 | 0.00982 | 0.0009508 | 0.05646 | 0.003314 | 0.003773
CIFAR100 | 0.03739 | 0.01143 | 0.01337 | 0.08245 | 0.003774 | 0.01453
ResNet50 |  |  |  |  |  |
ImageNet | 0.9122 | 1.547 | 2.036 | 1.144 | 0.8339 | 0.9788
log average | 0.0355 | 0.0930 | 0.0315 | 0.134 | 0.0148 | 0.0477
average rank | 2.75 | 4.625 | 3.125 | 5.5 | 1.25 | 3.75

###  V-B Image - Convolutional Neural Networks Experiments

In our image experiments, we have observed that the combination of ADAM + SLS
or SGD + SLS yields good results for CIFAR10 and CIFAR100, but performs poorly
for ImageNet, as depicted in Figure 6. We attribute this outcome primarily to
stability issues. Specifically, ADAM + SLS occasionally produces excessively
large step sizes $\eta$, or it diminishes them to unreasonably small values
$\eta\leq 10^{-10}$. On the other hand, our enhanced approaches ADAM + SaLSa
and SGD + SaLSa, do not encounter these problems and on average deliver the
best performance among all methods.

##  VI Related Work

The refinement of deep neural network optimization has been a focal point of
investigation within the realm of machine learning. Various techniques and
optimizers have been proposed, including but not limited to SGD [19], Adagrad
[20], RADAM [21], ADAMW [22], RMSprop [23] and Adam [8]. However, selecting
the most suitable optimizer remains a challenge, and there is no clear
consensus on the best according to [1].

In a recent study by[1] on the topic of optimization methods, it was observed
that while there are various optimizers available, there is no definitive best
optimizer. The authors highlight that the introduction of more optimizers does
not necessarily lead to improved results, and therefore, alternative
approaches should be explored to enhance optimization techniques. One such
approach with great potential is automatic step size determination. One of the
most common approaches for this are line search methods, which hold promise
for enhancing optimization processes [24, 2, 5, 25].

In this work we particularly build upon [2]. The Armijo line search method
introduced there, offers several important advantages over other optimization
techniques: no hyperparameter tuning of the learning rate, faster convergence
rates and better generalization. A significant drawback of this method, along
with other line search approaches, is that it requires at least an additional
forward pass per update step. Consequently, this leads to an increase of
approximately 30% in computational resources required per training step.

Recent work has shown that Transformers are highly sensitive to the choice of
learning rate and learning rate schedule schedule during training [21, 26]. To
address this issue, various approaches have been proposed, such as RADAM [21]
and warm starting. We have showed previously that our methods are able to
train Transfomers despite these challenges. Other related work includes [27]
which studies the correlation between batch size and learning rate, [28] which
shows theoretical and practical results for training using higher order
gradients and [9] which investigates why Adam, upon which we focus, is so
effective at training the Transformer architecture.

The optimization of neural networks continues to be an important area of
research, to which, the development of effective and reliable line search
methods, which work on sensitive architectures such as transformers or large
scale convolutional neural networks, constitutes a significant contribution.

##  VII Conclusion

We have introduced SaLSa, an automatic step size selection method and built a
general purpose optimizer on top. We have compared its performance against
tuned learning rates for larger datasets and architectures than previously
done in optimizer evaluations for line search methods. The SaLSa optimizer
performance compares favorably in these cases, while requiring no tuning of
learning rates, or code overhead, as well as minimal compute overhead. We
recommend its use as a first choice for training deep neural networks in these
domains and publish the code as a Python package.

The source code is open-source and free (MIT licensed) software and available
on github

## Acknowledgment

We gratefully acknowledge funding and support by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation): TRR 318/1 2021 –
438445824 and by SAIL. SAIL is funded by the Ministry of Culture and Science
of the State of North Rhine-Westphalia under the grant no NW21-059A.

## References

  * [1] R. M. Schmidt, F. Schneider, and P. Hennig, “Descending through a crowded valley-benchmarking deep learning optimizers,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 9367–9376.
  * [2] S. Vaswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien, “Painless stochastic gradient: Interpolation, line-search, and convergence rates,” _NIPS’19: Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , 2019.
  * [3] M. Mahsereci and P. Hennig, “Probabilistic line searches for stochastic optimization,” _Advances in neural information processing systems_ , vol. 28, 2015.
  * [4] R. Bollapragada, J. Nocedal, D. Mudigere, H.-J. Shi, and P. T. P. Tang, “A progressive batching l-bfgs method for machine learning,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 620–629.
  * [5] C. Paquette and K. Scheinberg, “A stochastic line search method with expected complexity analysis,” _SIAM Journal on Optimization_ , vol. 30, no. 1, pp. 349–376, 2020.
  * [6] P. Kenneweg, L. Galli, T. Kenneweg, and B. Hammer, “Faster convergence for transformer fine-tuning with line search methods,” in _2023 International Joint Conference on Neural Networks (IJCNN)_ , 2023, pp. 1–8.
  * [7] S. Vaswani, I. H. Laradji, F. Kunstner, S. Y. Meng, M. Schmidt, and S. Lacoste-Julien, “Adaptive gradient methods converge faster with over-parameterization (and you can do a line-search),” 2021. [Online]. Available: https://openreview.net/forum?id=GSTrduvZSjT
  * [8] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , Y. Bengio and Y. LeCun, Eds., 2015. [Online]. Available: http://arxiv.org/abs/1412.6980
  * [9] F. Kunstner, J. Chen, J. W. Lavington, and M. Schmidt, “Noise is not the main factor behind the gap between sgd and adam on transformers, but sign descent might be,” in _The Eleventh International Conference on Learning Representations_ , 2023. [Online]. Available: https://openreview.net/forum?id=a65YK0cqH8g
  * [10] L. Armijo, “Minimization of functions having lipschitz continuous first partial derivatives,” _Pacific Journal of mathematics_ , vol. 16, no. 1, pp. 1–3, 1966.
  * [11] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, J. Davison, S. Shleifer, P. von Platen, C. Ma, Y. Jernite, J. Plu, C. Xu, T. L. Scao, S. Gugger, M. Drame, Q. Lhoest, and A. M. Rush, “Huggingface’s transformers: State-of-the-art natural language processing,” 2019. [Online]. Available: https://arxiv.org/abs/1910.03771
  * [12] A. Karpathy, “nanogpt,” https://github.com/karpathy/nanoGPT, 2023.
  * [13] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” 2019.
  * [14] A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. Bowman, “GLUE: A multi-task benchmark and analysis platform for natural language understanding,” in _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_. Brussels, Belgium: Association for Computational Linguistics, Nov. 2018, pp. 353–355. [Online]. Available: https://aclanthology.org/W18-5446
  * [15] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever _et al._ , “Language models are unsupervised multitask learners,” _OpenAI blog_ , vol. 1, no. 8, p. 9, 2019.
  * [16] A. Krizhevsky, “Learning multiple layers of features from tiny images,” pp. 32–33, 2009. [Online]. Available: https://www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf
  * [17] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , 2009, pp. 248–255.
  * [18] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016, pp. 770–778.
  * [19] H. Robbins and S. Monro, “A stochastic approximation method,” _The annals of mathematical statistics_ , pp. 400–407, 1951.
  * [20] J. Duchi, E. Hazan, and Y. Singer, “Adaptive subgradient methods for online learning and stochastic optimization,” _Journal of Machine Learning Research_ , vol. 12, no. 61, pp. 2121–2159, 2011. [Online]. Available: http://jmlr.org/papers/v12/duchi11a.html
  * [21] L. Liu, H. Jiang, P. He, W. Chen, X. Liu, J. Gao, and J. Han, “On the variance of the adaptive learning rate and beyond,” in _International Conference on Learning Representations_ , 2020. [Online]. Available: https://openreview.net/forum?id=rkgz2aEKDr
  * [22] I. Loshchilov and F. Hutter, “Decoupled weight decay regularization,” in _International Conference on Learning Representations_ , 2019. [Online]. Available: https://openreview.net/forum?id=Bkg6RiCqY7
  * [23] G. Hinton and N. S. K. Swersky, “Lecture notes neural networks for machine learning,” 2014. [Online]. Available: https://www.cs.toronto.edu/~tijmen/csc321/slides/lecture_slides_lec6.pdf
  * [24] K. Nar and S. Sastry, “Step size matters in deep learning,” _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [25] L. Galli, H. Rauhut, and M. Schmidt, “Don’t be so monotone: Relaxing stochastic line search in over-parameterized models,” 2023.
  * [26] P. Kenneweg, A. Schulz, S. Schröder, and B. Hammer, “Intelligent learning rate distribution to reduce catastrophic forgetting in transformers,” in _Intelligent Data Engineering and Automated Learning – IDEAL 2022_ , H. Yin, D. Camacho, and P. Tino, Eds. Cham: Springer International Publishing, 2022, pp. 252–261.
  * [27] D. Granziol, S. Zohren, and S. Roberts, “Learning rates as a function of batch size: A random matrix theory approach to neural network training,” _J. Mach. Learn. Res_ , vol. 23, pp. 1–65, 2022.
  * [28] M. J. Streeter and J. V. Dillon, “Automatically bounding the taylor remainder series: Tighter bounds and new applications,” _ArXiv_ , vol. abs/2212.11429, 2022.