# Read the Signs
Towards Invariance to Gradient Descent’s Hyperparameter Initialization

Davood Wadi  Marc Fredette  Sylvain Senecal

###### Abstract

We propose ActiveLR, an optimization meta algorithm that localizes the
learning rate, $\alpha$, and adapts them at each epoch according to whether
the gradient at each epoch changes sign or not. This sign-conscious algorithm
is aware of whether from the previous step to the current one the update of
each parameter has been too large or too small and adjusts the $\alpha$
accordingly. We implement the Active version (ours) of widely used and
recently published gradient descent optimizers, namely SGD with momentum,
AdamW, RAdam, and AdaBelief. Our experiments on ImageNet, CIFAR-10,
WikiText-103, WikiText-2, and PASCAL VOC using different model architectures,
such as ResNet and Transformers, show an increase in generalizability and
training set fit, and decrease in training time for the Active variants of the
tested optimizers. The results also show robustness of the Active variant of
these optimizers to different values of the initial learning rate.
Furthermore, the detrimental effects of using large mini-batch sizes are
mitigated. ActiveLR, thus, alleviates the need for hyper-parameter search for
two of the most commonly tuned hyper-parameters that require heavy time and
computational costs to pick. We encourage AI researchers and practitioners to
use the Active variant of their optimizer of choice for faster training,
better generalizability, and reducing carbon footprint of training deep neural
networks.

Machine Learning, Meta Optimization, Gradient Descent, Convex Optimization

##  1 Introduction

The current state-of-the-art optimization algorithms are mechanical in their
nature, in the sense that they passively average the gradients, based on a
predefined number of past steps, instead of actively adjusting the step size
at each epoch according to the change in the sign of the gradients. The
moving-average-based optimizers, such as SGD with momentum (Sutskever et al.,
2013), Adam (Kingma & Ba, 2014), RAdam (Liu et al., 2019), and RMSprop
(Tieleman & Hinton, 2012b), base their optimization calculations on a fixed
number of previous gradient values, regardless of what their sign is. If the
sign of the gradients changes after epoch $e$, we want the optimizer to
recognize this jump over the optimum immediately and decrease the step size
accordingly. Furthermore, current optimizers update all the weights by a
global scalar learning rate, $\alpha$ (referred to by most deep learning
frameworks as LR or learning rate).

We introduce ActiveLR, an optimization meta algorithm that can be implemented
on top of current optimizers to adjust the hyper-parameter $\alpha$ at each
epoch for each model parameter. We mathematically prove that ActiveLR variant
of a given optimizer has a lower objective function cost compared to the
vanilla implementation of that optimizer. One of the main objectives of
ActiveLR is to obviate the need for the tuning of the initial learning rate,
$\alpha$, and mini-batch size. For different datasets, architectures, and
tasks, the values of $\alpha^{*}$, the optimal initial learning rate, and the
optimal mini-batch size (Iiduka, 2021), which lead to optimal convergence, are
different. Although for well-known benchmark tasks, such as ImageNet with
ResNet18 for object recognition, the optimal values for different hyper-
parameters have been immensely studied and made publicly available, for new
tasks, researchers and practitioners must start anew and perform costly hyper-
parameters search to find the optimal values for the initial learning rate,
mini-batch size, what learning rate scheduler to use, and at which epochs they
should decay the learning rate by what amount.

Moreover, learning rate values higher than $\alpha^{*}$ lead to divergence of
the optimization, while values lower than $\alpha^{*}$ lead to significantly
slower rate of convergence and also increase the possibility of being stuck in
a local minimum. Also, large mini-batch sizes are necessary for fast training
of large-scale datasets and utilizing the full computational power of multiple
GPUs (You et al., 2017). Our tests show that vanilla implementations of SGD
with momentum, AdamW, RAdam, and Adabelief get stuck in local minima for
smaller learning rates and fail to achieve high performance on the test set.
Moreover, their performance has a negative correlation with mini-batch size.
As we increase the mini-batch size, the training becomes unstable and
generalizability suffers significantly. On the other hand, ActiveLR
implementations of these optimizers (i.e., ActiveSGD, ActiveAdamW,
ActiveRAdam, and ActiveBelief) outperform their original implementations, and
are also robust to the values of initial learning rate and mini-batch size.

This has major implication for research and practice. Not only is tuning the
learning rate and mini-batch size time consuming and costly, it causes severe
environmental impacts. For instance, the greenhouse gas emissions for training
a state-of-the-art transformers model is equivalent to 10 years of emissions
of a person in the U.S. (Lacoste et al., 2019; Strubell et al., 2019).
Furthermore, while researchers at large institutions have access to high
compute power and afford to perform intense hyper-parameter search on hundreds
of GPUs and TPUs, most AI researchers and practitioners have significantly
more limited access to computation power. Therefore, ActiveLR helps in
democratizing AI, saving time and cost to AI researchers, and also reducing
greenhouse emissions.

##  2 Problematization

SGD and adaptive optimizers have two shortcomings. First, when the optimizer
approaches the optimum, the accumulated momentum will cause it to oscillate
over the optimum. It is because when the gradient changes its sign, if the
exponential moving average has the opposite sign, the weight of the parameter
will be updated up the slope of the error curve, deviating the model from the
optimum. Therefore, it takes longer for such optimizers to stabilize around
the optimum compared to an optimizer that is aware of the gradients’ sign at
each step and adjusts the step size, $\alpha$, according to whether the
gradients have changed their sign or not.
Second, using a global learning rate, $\alpha$, to update all the parameters
does not account for the specific position of each neuron compared with its
optimum value. At each training epoch, some neurons are farther away from
their optimum—requiring a larger $\alpha$—while others are closer to their
optimum—requiring a smaller $\alpha$. In addition, for a deep neural network,
the gradient for middle layers are much smaller compared to the initial and
final layers (see 5.1), requiring a larger $\alpha$. Moreover, when we
simultaneously update the weights of a previous layer (e.g. $layer_{i-1}$) to
correct the same error function, this simultaneous change in the incoming
weights to the next layer ($layer_{i}$) causes an overshoot effect—determined
by the term “fan-in”—on the weights of $layer_{i}$. The size of fan-in
determines the amount of input a layer receives and varies from layer to layer
(Tieleman & Hinton, 2012a). Therefore, we need local $\alpha$’s for each
neuron to account for these disparities between different neurons.

##  3 Related work

Jacobs (1988) was the first to suggest that every weight of a neural network
be given its own $\alpha$, and each $\alpha$ be allowed to vary over time. He
states that when the sign of the derivative for a parameter is constant for
consecutive epochs, the $\alpha$ for that parameter should be increased. On
the other hand, when the sign of the derivative for a parameter changes for
consecutive epochs, the $\alpha$ for that parameter should be decreased
(Figure 1).

Efforts have been made to reduce the sensitivity of gradient descent
optimization to learning rate initialization (Baydin et al., 2017; Zhang et
al., 2019). However, previous work on reducing sensitivity to initial learning
rate has introduced additional hyper-parameters that need to be tuned, which
seems to defeat the purpose–removing a hyper-parameter and introducing others
to be tuned.

To best of our knowledge, there has not been an automatic algorithm that
reduces sensitivity to both initial learning rate and mini-batch size.

Figure 1: Optimization of a parameter of a model using a sign-conscious
optimizer. When the sign of the gradient does not change (_left_), the Active
optimizer increases the step size $\alpha$, nudging the model weight to the
true value of the weight ($2.0$). When the sign of the gradient changes
(_right_), the weight has jumped over the optimum. Therefore, the Active
optimizer decreases the step size $\alpha$ for the next iteration. This not
only decreases convergence time, but also avoids constantly jumping over the
optimum value.

The latest mention of a sign-conscious optimization algorithm was in (Tieleman
& Hinton, 2012a). However, since previous implementations worked only on full-
batch training and researchers almost never want to train their neural
networks with full batches, the development of sign-conscious optimizers was
thwarted.

##  4 ActiveLR

We introduce a meta algorithm that utilizes a vanilla optimization algorithm,
such as Adam or SGD, in the inner-loop part, and in the outer-loop part of the
optimization, at every epoch, actively adjusts the local learning rate for
each parameter based on the change in the sign of the cumulative gradients.
Unlike previous implementations, ActiveLR works with mini-batch and stochastic
gradient descent. Almost always, mini-batch gradient descent is the optimal
way to train neural networks. Firstly, modern datasets (e.g., ImageNet) do not
fit into GPU memory, so full-batch gradient descent on such datasets is not
possible. Furthermore, researchers prefer to use mini-batches instead of full-
batches, as mini-batches provide faster convergence and better
generalizability (Qian & Klabjan, 2020; Wilson & Martinez, 2003).

###  4.1 The ActiveLR meta algorithm

Assuming we have $k$ mini-batches of data in our dataset, for each iteration t
in the dataset, given that each mini-batch of training data has a specific
gradient w.r.t. the parameter $\theta_{i}$, $\nabla f^{t}(\theta_{i}^{t-1})$,
that is calculated for that mini-batch, we define the cumulative gradient of
the model as the arithmetic summation of all mini-batch gradients. For epoch
$e$, the cumulative gradient, $\nabla f_{cu}^{e}$, with respect to the inner-
loop-updated parameter, $\theta_{i}$, can be derived from:

$\nabla f_{cu}^{e}(\theta_{i})=\sum_{t=1}^{k}\nabla f^{t}(\theta_{i}^{t-1})$

The cumulative gradient $\nabla f_{cu}^{e}(\theta_{i})$ is the gradient of the
objective function $f$ with respect to the parameter $\theta_{i}$ at epoch
$e$, as if the model has experienced the whole dataset (full-batch training).
Since after seeing each mini-batch the optimizer updates the parameters, the
calculated gradients for each mini-batch is different from the gradient of the
mini-batch if there was no update (this is what we are trying to approximate).
Consequently, we wish to prove that the sign of the gradient for the whole
dataset with respect to parameter $\theta_{i}$ when the parameter does not
change inside the loop is the same as that of the updated parameter within the
loop. Thus, we prove the Theorem 1 that enables us to use gradient-descent-
updated gradients instead of no-update gradients.

######  Theorem 4.1.

In the local convex regime of a non-convex objective function, the cumulative
gradient of parameter $\theta_{i}$ at epoch $e$ with no inner-loop updates,
$\overset{*}{cu}$, has the same sign as the cumulative gradient of parameter
$\theta_{i}$ at epoch $e$ with inner-loop updates, $\widehat{cu}$, if the
learning rate, $\alpha$, is smaller than $\alpha^{*}$ that causes the inner-
loop to diverge.

$\overset{*}{cu}\widehat{cu}\geq 0$

ActiveLR can now be implemented using mini-batches by comparing the sign of
the cumulative gradient at epoch $\mathit{e-1}$, $\nabla
f_{cu}^{e-1}(\theta_{i})$, with the sign of the cumulative gradient at epoch
$e$, $\nabla f_{cu}^{e}(\theta_{i})$ (Algorithm 1). It allows the optimizer to
update the parameters at each step of the mini-batch (Wilson & Martinez, 2003;
Qian & Klabjan, 2020), while adjusting the $\alpha$ at the end of each epoch
(Tieleman & Hinton, 2012a), enabling inner-loop learning through the backend
optimizer (e.g., Adam, SGD) and active learning rate adjustment together.

Algorithm 1 ActiveLR for SGD (ActiveSGD)

Inputs: $\alpha^{0}$ {initial learning rate}, $\theta_{i}^{0}$ {initial
parameter $i$}, $f(\theta)$ {stochastic objective function}, $\alpha_{high}$
{$\alpha$ growth constant}, $\alpha_{low}$ {$\alpha$ shrink constant}

Output: $\theta_{i}^{T}$ {the updated parameter $i$}

$e\leftarrow 0$, $g_{i,cu}^{0}\leftarrow 0$ {initialization}

repeat

$e\leftarrow e+1$ {next epoch}

$t\leftarrow 0$

$g_{i,cu}^{e}\leftarrow 0$ {set/reset the cumulative gradient to zero at each
epoch}

for mini-batches in dataset do

$t\leftarrow t+1$

$g_{i}^{t}\leftarrow\nabla_{\theta_{i}}f^{t}(\theta_{i}^{t-1})$ {calculate the
gradient of the objective w.r.t. the parameter at timestep $t$}

$g_{i,cu}^{e}\leftarrow g_{i,cu}^{e}+g_{i}^{t}$ {add mini-batch gradient to
cumulative gradient}

$\theta_{i}^{t}\leftarrow\theta_{i}^{t-1}-\alpha_{i}^{t}g_{i}^{t}$ {SGD
update}

end for

$\alpha_{i}^{e}\leftarrow\begin{cases}\alpha_{i}^{e-1}+\alpha_{high},&\text{\small$sign(g_{i,cu}^{e}\times
g_{i,cu}^{e-1})>0$}\\\
\alpha_{i}^{e-1}\times\alpha_{low},&\text{\small$sign(g_{i,cu}^{e}\times
g_{i,cu}^{e-1})\leq 0$}\end{cases}$ {adjust learning rate}

until $\theta_{i}^{t}$ converged

Return: $\theta_{i}^{T}$

###  4.2 Orthogonality of ActiveLR to other optimizers

A major advantage of ActiveLR is the orthogonality of the hyper-parameter that
it adjusts, $\alpha$, to the hyper-parameters that other well-known algorithms
adjust. To be more specific, we take a look at the generic parameter update
that is the backbone of SGD, Adam, RAdam, etc.

$\theta_{i}^{t}\leftarrow\theta_{i}^{t-1}-\alpha F(g_{i}^{t})$ (1)

The difference among these algorithms is the way they manipulate the
$F(g_{i}^{t})$ term through the $F$ function, while keeping $\alpha$ as is in
the original SGD algorithm. For instance, in the case of Adam, $F(g_{i}^{t})$
is
$\frac{\frac{\beta_{1}m_{i}^{t-1}+(1-\beta_{1})g_{i}^{t}}{1-\beta_{1}^{t}}}{\sqrt{\frac{\beta_{2}v_{i}^{t-1}+(1-\beta_{2}){g_{i}^{t}}^{2}}{1-\beta_{2}^{t}}}+\epsilon}$.
However, since ActiveLR modifies the $\alpha$ term in Equation 1, it can be
combined with other optimization algorithms. In fact, in our experiments we
report results on ActiveLR combined with SGD with momentum (ActiveSGD), AdamW
(ActiveAdamW), with RAdam (ActiveRAdam), and AdaBelief (ActiveBelief) and
compare the Active results with their original, vanilla variants.

##  5 Convergence analysis

At any given epoch, $e$, we are faced with the choice between the ActiveLR
algorithm vs. its corresponding vanilla backbone. We prove that the value of
the objective function for ActiveSGD (ActiveLR combined with SGD) at epoch
$\mathit{e+1}$ is as good or better than the vanilla SGD (backbone) algorithm
at epoch $\mathit{e+1}$, and show the conditions where each inequality holds.
The proof is capable of any first-order backbone algorithm. For other
backbones, such as Adam, RMSProp, etc., their respective ActiveLR
implementation should have the same lines of proof, with some modifications
peculiar to the optimizer of interest.

######  Theorem 5.1.

Let us call the cost of vanilla SGD at epoch e, $f(\theta^{S}_{e})$, and the
cost of its corresponding ActiveLR implementation, $f(\theta^{A}_{e})$. We
define ActiveSGD’s gradient, $g_{e+1}^{A}$, as
$\frac{\partial{f(\theta_{e}^{A})}}{\partial{\theta_{e}^{A}}}$, and vanilla
SGD’s gradient, $g_{e+1}^{S}$, as
$\frac{\partial{f(\theta_{e}^{S})}}{\partial{\theta_{e}^{S}}}$. $\alpha$ is
the initial learning rate for ActiveSGD and also the constant learning rate
for SGD. $\alpha_{High}$ is the higher learning rate ($\alpha_{High}>\alpha$)
that ActiveLR uses when $g_{e}^{A}g_{e+1}^{A}>0$ and $\alpha_{Low}$ the lower
learning rate ($\alpha_{Low}<\alpha$) that ActiveLR uses when
$g_{e}^{A}g_{e+1}^{A}<0$. In the local convex regime of $f$, at any arbitrary
epoch, $\mathit{e}$, the difference between the cost of using vanilla SGD and
ActiveSGD at the next epoch, $\mathit{e+1}$, is

$\begin{cases}f(\theta^{S}_{e+1})-f(\theta^{A}_{e+1})\geq
g_{e+2}^{A}g_{e+1}^{A}(\alpha_{High}-\alpha),\\\ \text{if
}g_{e}^{A}g_{e+1}^{A}>0.\\\ f(\theta^{S}_{e+1})-f(\theta^{A}_{e+1})\geq
g_{e+2}^{A}g_{e+1}^{A}(\alpha_{Low}-\alpha),\\\ \text{if
}g_{e}^{A}g_{e+1}^{A}<0.\end{cases}$ (2)

where the right hand side for both cases is non-negative.

In other words, ActiveSGD is at least as good as vanilla SGD when gradients
are zero (equality in 2), and strictly better than vanilla SGD when gradients
are not zero (inequality in 2). The lower bound of the advantage is
$g_{e+2}^{A}g_{e+1}^{A}(\alpha_{High}-\alpha)$, when $g_{e}^{A}g_{e+1}^{A}>0$
and $g_{e+2}^{A}g_{e+1}^{A}(\alpha_{Low}-\alpha)$ when
$g_{e}^{A}g_{e+1}^{A}<0$.

(a) Adam, $\alpha=10^{-5}$

(b) Adam, $\alpha=10^{-3}$

(c) ActiveAdam, $\alpha=10^{-5}$

Figure 2: Gradient norms across layers for CIFAR-10 on ResNet-18. Vanilla Adam
when the $\alpha$ is too small ($\alpha=10^{-5}$) gets stuck in a local
minimum 2(a). Vanilla Adam when the learning rate is optimal
($\alpha=10^{-3}$) oscillates around the optimum 2(b). ActiveAdam with the
same low learning rate that gets vanilla Adam stuck ($\alpha=10^{-5}$)
achieves minimal loss and remains in the optimum 2(c).

#### The hyper-parameters of ActiveLR

To set the operations for $\alpha_{low}$ and $\alpha_{high}$, we follow
(Tieleman & Hinton, 2012a)–multiply by $\alpha_{low}$ and add $\alpha_{high}$.
We carry out an ablation analysis of the choice of operations (e.g., addition
or multiplication). For the results, please refer to A.3. To obtain the
default values of $\alpha_{low}$ and $\alpha_{high}$, we carry out a
preliminary experiment on CIFAR-10 and find that any combination of
$\alpha_{low}$ and $\alpha_{high}$ that satisfy the constraint
$\alpha_{low}+\alpha_{high}=1$ reduce sensitivity to initial learning rates
and mini-batch size, while increasing the overall accuracy. For all the
experiments that follow, we have kept $\alpha_{low}=0.9$ and
$\alpha_{high}=0.1$ constant. The results show the robustness of the default
values of $\alpha_{low}$ and $\alpha_{high}$ across datasets and tasks, which
suggests that ActiveLR’s hyper-parameters do not need to be tuned.

###  5.1 Distribution of gradient norms across layers

We examine the L1-norm of the gradients across layers for the optimization of
the CIFAR-10 dataset on the ResNet-18 architecture, which has $21$
2D-convolution layers and $1$ final fully connected layer (Figure 2). The
gradient norm of the final dense layer (layer $\\#=22$) directly correlates
with the loss. In contrast, to achieve minimal loss, the gradient norm of the
convolutional layers (layer $\\#\in[1,21]$) increases to a maximum value (the
learning phase) and then decreases (the stabilizing phase around the optimum).
For vanilla Adam, when the $\alpha$ is too small ($\alpha=10^{-5}$), the
gradient norm for every convolutional layer increases monotonically with the
number of iterations and the loss reaches a plateau, indicating getting stuck
in a local minimum (2(a)). In other words, when the learning rate is lower
than an optimum value, the learning phase never ends. When the learning rate
is optimal ($\alpha=10^{-3}$), Adam increases the gradient norms to an optimal
level where it achieves the minimal loss (the end of the learning phase).
Afterwards, in the stabilizing phase, the gradients are decreased at a
relatively slow rate, which causes the loss to oscillate ($iteration>60$)
around the minimum value (2(b)). ActiveAdam, with the same low learning rate
that gets Adam stuck ($\alpha=10^{-5}$), is able to achieve what Adam with the
optimal learning rate does in the training phase (i.e., increase the gradient
norms to a maximum value). Additionally, after the minimal loss is achieved,
ActiveAdam sharply reduces the gradient norms, preventing fluctuations around
the optimum ($iteration>60$) (2(c)).

###  5.2 ActiveLR and non-convex functions

The Active implementation of a given algorithm such as Adam (ActiveAdam)
provides numerous advantages over the vanilla implementation in troublesome
non-convex optimization scenarios.

(a) $f(x)=x^{3}-6x^{2}+9x$ w.r.t. $x$

(b) $f(x,y)=-x^{3}-x^{2}y+y^{2}+4y+1680$ w.r.t. $x,y$

(c) $f(x,y)=y^{4}-2y^{2}+x^{2}$ w.r.t. $x,y$

Figure 3: (3(a)) univariate unimodal, (3(b)) bivariate multimodal, and (3(c))
saddle function optimization using vanilla Adam and ActiveAdam

#### ActiveLR and local minima

Local minima are a major plague in deep neural network optimization (Ding et
al., 2019; Yun et al., 2018). They are one of the main reasons that optimizers
do not generalize well and fail to fit the training data properly. This is
especially the case when the learning rate is smaller than an optimum value.
In Figure 3(a), the vanilla Adam quickly goes down the objective function at
the starting point $x=5$, but as soon as it reaches the local minimum, $x=3$,
the gradient becomes significantly small, causing vanilla Adam to oscillate
around the local minimum no matter how long we keep training. ActiveAdam, on
the other hand, quickly increases the learning rate, as soon as it realizes
that the gradient signs are not changing. It enables ActiveAdam to pass
through the local minimum and move towards the global minimum, $x\to-\infty$.
In Figure 3(b), the vanilla optimizer faces two challenges. This bivariate
function, $f(x,y)=-x^{3}-x^{2}y+y^{2}+4y+1680$, has three local minima and a
global minimum of $(+\infty,+\infty)$. The first local minimum, $(-4,6)$, the
starting point, has a higher function value than the other two, $(0,-2)$ and
$(1,-\frac{3}{2})$, which have the same lower value. The first challenge is
starting near a local minimum, where the gradients are too small. Adam
struggles to escape the starting point because of the small gradients. After a
large number of iterations, Adam eventually escapes the starting local optimum
but faces the second challenge. It gets trapped in another local minimum,
$(0,-2)$, and is unable to escape. ActiveAdam, on the other hand, quickly
escapes the initial local minimum since it increases its learning rate when
the gradients do not change. With the higher learning rate it has accumulated,
it is able to quickly escape the other two local minima and converge to the
global minimum, $(+\infty,+\infty)$.

#### ActiveLR and saddle points

Saddle points are another major pitfall in training neural networks
(Kawaguchi, 2016). For deep neural networks, large sets of strict and non-
strict saddle points have been shown to exist (Achour et al., 2021). Being
close to a saddle point equates very small gradient values in all directions.
As a result, non-Active optimizers will require significantly higher training
iterations to escape saddle points. In Figure 3(c), the saddle point lies at
$(0,0)$. After $12$ iterations, Adam is relatively where it was when the
training started. ActiveAdam, however, quickly increases its learning rate,
following iterations of no sign change, and reaches the global minimum at
$(0,1)$ in $12$ iterations.

Figure 4: Reduced sensitivity to mini-batch size on CIFAR-10 test accuracy
$([\mu\pm\sigma])$

##  6 Experiments

We perform our experiments on ImageNet (Deng et al., 2009) with ResNet-18 and
CIFAR-10 (Krizhevsky et al., 2009) with ResNet-34 for image classification,
WikiText-2 and WikiText-103 (Merity et al., 2016) with GPT-2 (Radford et al.,
2019) for language modelling, and PASCAL VOC (Everingham et al., 2010) dataset
on Faster-RCNN+FPN for object detection. Based on the literature, non-adaptive
optimizers (e.g. SGD) work with higher initial learning rates compared to
adaptive optimizers. Therefore, for all the experiments, we use $50$ times the
hyperparameter space for initial learning rates of SGD with momentum and
ActiveSGD compared to the adaptive optimizers. For each vanilla optimizer and
its Active variant, we test the performance across a range of initial learning
rates and, for other hyperparameters, we use the values suggested on the
optimizer’s official GitHub page for each task. We use a heterogeneous cluster
with each node comprised of 4 x NVIDIA P100 Pascal (12G or 16G HBM2 memory) or
4 x NVIDIA V100 Volta (32G HBM2 memory). To simulate common practitioners’
limited access to GPUs, we train the WikiText-2, WikiText-103, PASCAL VOC, and
CIFAR-10 experiments on 1 GPU and the ImageNet experiments on 4 GPUs.

Figure 5: Test accuracy $([\mu\pm\sigma])$ of SGD with momentum, AdaBelief,
RAdam, and AdamW compared with their Active variant on CIFAR-10. The red area
in-between lines indicates the sensitivity of the optimizer w.r.t. the value
of the initial learning rate. The horizontal lines indicate the highest mean
accuracy of each optimizer across learning rates.

###  6.1 Sensitivity to mini-batch size

ActiveLR alleviates the problem of large mini-batch sizes by its automatic
learning rate adaptation. In Figure 4, we can see that for the CIFAR-10
dataset, increasing the mini-batch size from the optimal value of $128$ to
larger values significantly decreases the test-set accuracy of vanilla SGD
with momentum. Larger mini-batch sizes also destabilize training as can be
seen by higher fluctuations in accuracy for vanilla SGD with momentum.
ActiveSGD, on the other hand, achieves a relatively high accuracy regardless
of the mini-batch size and also remains stable. ($\alpha={10}^{-4}$,
ResNet-18)

###  6.2 Sensitivity to learning rate

#### CIFAR-10

We train SGD with momentum, AdaBelief, RAdam, and AdamW along with their
Active variant (i.e., ActiveSGD, ActiveBelief, ActiveRAdam, ActiveAdamW) with
9 different initial learning rates $5\times 10^{n}$, $n\in[-7,-3]$, each ran
$3$ times. We test different values for weight decay in the range of
$[10^{3},10^{-8}]$ and found that the optimal weight decay, $wd^{*}$ depends
on the learning rate, $\alpha$. For CIFAR-10, ${wd}^{*}\times\alpha=10^{-4}$.
As seen in Figure 5, the Active variant of each optimizer achieves a higher
average accuracy compared with the vanilla variant. More importantly, the area
between the accuracy achieved by the worst-performing learning rate and the
best-performing learning rate is significantly smaller for the Active variants
compared to the vanilla variants. This indicates reduced sensitivity to the
selection of the initial learning rate that ActiveLR achieves.

(a) Test-set PPL (lower is better)

(b) Train-set PPL (lower is better).

Figure 6: WikiText-2 on GPT-2 with various initial learning rates

#### WikiText-2

We fine-tune GPT-2 with 124,439,808 parameters on WikiText-2 (vocabulary size
$50257$, maximum sequence length $1024$, dimensionality of the embeddings and
hidden states $768$, number of hidden layers in the Transformer encoder $12$,
number of attention heads for each attention layer $12$, activation function
$gelu$, dropout probability $0.1$). Initial learning rates in the range of
$[10^{-8},10^{-4}]$ for adaptive optimizers and $[5\times 10^{-7},5\times
10^{-3}]$ for non-adaptive optimizers are tested. For each initial learning
rate, we calculate the test-set PPL for the epoch that gives the highest
validation-set PPL. In Figure 6, we can see that ActiveLR gives better test-
set PPL compared to vanilla optimizers on average, while producing lower
train-set errors. Furthermore, vanilla optimizers have a significant degree of
variation in their test-set and train-set PPLs, indicating their sensitivity
to the initial learning rate, while ActiveLR shows relative insensitivity to
the initial learning rate. A surprising finding is the generalizability of
ActiveSGD. Although in the literature the performance of SGD with momentum for
transformers models has been shown to be inferior to adaptive methods–and our
results confirm it–the ActiveLR variant of SGD with momentum shows better
generalizability than the adaptive methods. In fact, ActiveSGD gives the best
test PPL among all optimizers tested.

(a) ImageNet top 1 accuracy
$([\mu\pm\sigma])$

(b) ImageNet top 5 accuracy
$([\mu\pm\sigma])$

(c) ImageNet training loss
$([\mu\pm\sigma])$

Figure 7: The mean/std test accuracy $([\mu\pm\sigma])$ of ActiveAdam,
AdaBelief, RAdam, and Adam on ImageNet with three initial learning rates
($[10^{-5},10^{-4},10^{-3}]$). The shaded area around each line is the
standard deviation of the means for each optimizer across different values of
the initial learning rate. (Adam and RAdam plots are _visually identical_)

#### ImageNet

For ImageNet, we train ActiveAdam, AdaBelief, RAdam, and Adam for $110$
epochs, after which the accuracies do not improve. Figure 7 shows the average
and standard deviation of each metric across initial learning rates of
${10}^{n},n\in\\{-3,-4,-5\\}$. ActiveAdam achieves the highest mean top-1 and
top-5 accuracy and the lowest training error (the green line) compared to the
other vanilla optimizers (the plots for Adam and RAdam are _visually
identical_). It also has the lowest amount of variance among the optimizers,
showing reduced sensitivity to the initial learning rate.

#### WikiText-103 and PASCAL VOC

Please refer to Appendix A.2.

##  7 Social impact

ActiveLR makes contributions to several social causes. First, given the growth
of the size of datasets and deep learning models, it has become increasingly
more difficult for average AI practitioners and researchers to train state-of-
the-art models. By reducing sensitivity to hyperparameter initialization,
ActiveLR helps in democratizing AI. Second, carbon emissions from training
deep neural networks have reached alarming levels. Consider training a new
dataset with the size of the ImageNet on a relatively small model, such as
ResNet-18. Let us assume the goal is to achieve top-1 accuracy of 55% or
higher. Since we a priori do not know what the optimal initial learning rate
is, we need to test various initial learning rates. Testing 9 initial learning
rates starting from $10^{-4}$ up to ${10^{0}}$, we find that, with SGD with
momentum, 7 out of 9 initial learning rates achieve our desired accuracy in
$100$ epochs, while, with ActiveSGD, 8 out of 9 values reach our desired
accuracy (Figure 8). Considering the worst-case, where the suboptimal learning
rates are selected first, SGD with momentum, compared with ActiveSGD, requires
13,816,000 TFLOPS extra computation (2200 seconds per epoch, 61.11 hours
total). With an average carbon efficiency of 0.432 kgCO2eq/kWh, using 4 x
Tesla V100-SXM2-32GB (TDP of 300W) GPUs (same as our experiments), the
excessive $CO_{2}$ emissions are estimated to be 7.92 kgCO2eq. This is
equivalent to 3.96 Kgs of extra coal burned. On the other hand, ActiveSGD not
only prevents such extra carbon emissions, but also gives higher average
accuracy and fit (estimations were conducted using the MachineLearning Impact
calculator presented in Lacoste et al. (2019).) As a result, we believe that
ActiveLR is a step towards eliminating the need for hyperparameter search,
which helps democratize AI and reduce carbon emissions.

##  8 Limitations

While we try to include as many experiments on various tasks to show the
robustness of the results of ActiveLR, due to time and computational limits,
we could not test all benchmark datasets. We are working on releasing test
results for COCO dataset (Lin et al., 2014) for object segmentation, and
IWSLT14 DE-EN for neural machine translation on transformers, among others,
for ActiveLR. With Active LR, we demonstrated the capability to reduce
sensitivity to initial learning rate and mini-batch size. We encourage future
research to identify and tackle optimization sensitivity to _other_ hyper-
parameters, such as weight decay, in an attempt to streamline neural network
optimization, reduce carbon emissions, and training time.

##  9 Conclusion

In this paper, we show that for all the learning rates tested, the Active
variant of SGD with momentum, AdamW, AdaBelief, and RAdam achieves the best
fit and highest accuracy. Our tests show robust results for different datasets
and model architectures. It did so in a lower number of epochs, which
translates to faster training. Moreover, we show that ActiveLR remains stable
and does not suffer from loss in generalizability when trained with large
mini-batch sizes. As a result, multi-GPU training of large datasets can be
sped up with ActiveLR using large mini-batch sizes. The orthogonality of
ActiveLR to other optimizers allows it to be implemented on top of them. We
also show relative insensitivity of ActiveLR to the values of initial learning
rate and mini-batch size. We encourage practitioners to use ActiveLR for their
model training to achieve better training/test-set performance in a shorter
amount of time, remove the need for tuning the initial learning rate and mini-
batch size, and reduce their carbon footprint.

## Acknowledgements

The authors would like to thank Compute Canada for its provision of
computational resources that made the experimentations possible.

## References

  * Achour et al. (2021) Achour, E. M., Malgouyres, F., and Gerchinovitz, S.  Global minimizers, strict and non-strict saddle points, and implicit regularization for deep linear neural networks.  _arXiv preprint arXiv:2107.13289_ , 2021.
  * Baydin et al. (2017) Baydin, A. G., Cornish, R., Rubio, D. M., Schmidt, M., and Wood, F.  Online learning rate adaptation with hypergradient descent.  _arXiv preprint arXiv:1703.04782_ , 2017.
  * Chen et al. (2019) Chen, K., Wang, J., Pang, J., Cao, Y., Xiong, Y., Li, X., Sun, S., Feng, W., Liu, Z., Xu, J., Zhang, Z., Cheng, D., Zhu, C., Cheng, T., Zhao, Q., Li, B., Lu, X., Zhu, R., Wu, Y., Dai, J., Wang, J., Shi, J., Ouyang, W., Loy, C. C., and Lin, D.  Mmdetection: Open mmlab detection toolbox and benchmark, 2019.  URL https://arxiv.org/abs/1906.07155.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pp. 248–255. Ieee, 2009.
  * Ding et al. (2019) Ding, T., Li, D., and Sun, R.  Spurious local minima exist for almost all over-parameterized neural networks.  _Optimization online_ , 2019.
  * Everingham et al. (2010) Everingham, M., Van Gool, L., Williams, C. K. I., Winn, J., and Zisserman, A.  The pascal visual object classes (voc) challenge.  _International Journal of Computer Vision_ , 88(2):303–338, June 2010.
  * Iiduka (2021) Iiduka, H.  The number of steps needed for nonconvex optimization of a deep learning optimizer is a rational function of batch size.  _ArXiv_ , abs/2108.11713, 2021.
  * Jacobs (1988) Jacobs, R. A.  Increased rates of convergence through learning rate adaptation.  _Neural networks_ , 1(4):295–307, 1988.
  * Kawaguchi (2016) Kawaguchi, K.  Deep learning without poor local minima.  _arXiv preprint arXiv:1605.07110_ , 2016.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Krizhevsky et al. (2009) Krizhevsky, A., Hinton, G., et al.  Learning multiple layers of features from tiny images.  2009\.
  * Lacoste et al. (2019) Lacoste, A., Luccioni, A., Schmidt, V., and Dandres, T.  Quantifying the carbon emissions of machine learning.  _arXiv preprint arXiv:1910.09700_ , 2019.
  * Lin et al. (2014) Lin, T.-Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P., and Zitnick, C. L.  Microsoft coco: Common objects in context.  In _European conference on computer vision_ , pp. 740–755. Springer, 2014.
  * Liu et al. (2019) Liu, L., Jiang, H., He, P., Chen, W., Liu, X., Gao, J., and Han, J.  On the variance of the adaptive learning rate and beyond.  _arXiv preprint arXiv:1908.03265_ , 2019.
  * Merity et al. (2016) Merity, S., Xiong, C., Bradbury, J., and Socher, R.  Pointer sentinel mixture models.  _arXiv preprint arXiv:1609.07843_ , 2016.
  * Qian & Klabjan (2020) Qian, X. and Klabjan, D.  The impact of the mini-batch size on the variance of gradients in stochastic gradient descent.  _arXiv preprint arXiv:2004.13146_ , 2020.
  * Radford et al. (2019) Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Ren et al. (2015) Ren, S., He, K., Girshick, R., and Sun, J.  Faster r-cnn: Towards real-time object detection with region proposal networks.  _Advances in neural information processing systems_ , 28, 2015.
  * Strubell et al. (2019) Strubell, E., Ganesh, A., and McCallum, A.  Energy and policy considerations for deep learning in nlp.  _arXiv preprint arXiv:1906.02243_ , 2019.
  * Sutskever et al. (2013) Sutskever, I., Martens, J., Dahl, G., and Hinton, G.  On the importance of initialization and momentum in deep learning.  In _International conference on machine learning_ , pp. 1139–1147, 2013.
  * Tieleman & Hinton (2012a) Tieleman, T. and Hinton, G.  Lecture 6.4 - a separate, adaptive learning rate for each connection.  _COURSERA: Neural networks for machine learning_ , 4(2):22–25, 2012a.
  * Tieleman & Hinton (2012b) Tieleman, T. and Hinton, G.  Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude.  _COURSERA: Neural networks for machine learning_ , 4(2):26–31, 2012b.
  * Wilson & Martinez (2003) Wilson, D. R. and Martinez, T. R.  The general inefficiency of batch training for gradient descent learning.  _Neural networks_ , 16(10):1429–1451, 2003.
  * You et al. (2017) You, Y., Gitman, I., and Ginsburg, B.  Scaling sgd batch size to 32k for imagenet training.  _ArXiv_ , abs/1708.03888, 2017.
  * Yun et al. (2018) Yun, C., Sra, S., and Jadbabaie, A.  Small nonlinearities in activation functions create bad local minima in neural networks.  _arXiv preprint arXiv:1802.03487_ , 2018.
  * Zhang et al. (2019) Zhang, M., Lucas, J., Ba, J., and Hinton, G. E.  Lookahead optimizer: k steps forward, 1 step back.  _Advances in neural information processing systems_ , 32, 2019.
  * Zhuang et al. (2020) Zhuang, J., Tang, T., Ding, Y., Tatikonda, S., Dvornek, N., Papademetris, X., and Duncan, J. S.  Adabelief optimizer: Adapting stepsizes by the belief in observed gradients.  _arXiv preprint arXiv:2010.07468_ , 2020.

##  Appendix A Appendix

###  A.1 Additional plots

SGD with momentum vs. ActiveSGD for Image-Net on ResNet-18 (Figure 8).

(a) ImageNet top-1 accuracy

(b) ImageNet top-5 accuracy

(c) ImageNet training loss

Figure 8: The top-1, top-5, and training loss of SGD with momentum and
ActiveSGD on ImageNet with 9 initial learning rates $[10^{-4},10^{0}]$. The
shaded area shows the performance gap between the best initial learning rate
and the worst one (sensitivity to the value of initial learning rate.)

CIFAR-10 training loss on ResNet-34 (Figure 9).

Figure 9: Training loss $([\mu\pm\sigma])$ of SGD with momentum, AdaBelief,
RAdam, and AdamW compared with their Active variant on CIFAR-10. The red area
in-between lines indicates the sensitivity of the optimizer w.r.t. the value
of the initial learning rate. The horizontal lines indicate the lowest loss of
each optimizer across learning rates.

###  A.2 Extra experiments

#### WikiText-103 on mini-GPT2

We train WikiText-103 on a small variant of GPT-2–mini-GPT-2 1 from scratch.

Figure 10 shows the test and training PPLs for SGD with momentum, AdamW,
ActiveSGD and ActiveAdamW. They show that compared with the vanilla variants,
the ActiveLR variants achieve better training fit and test-set PPL. Moreover,
lower variance of ActiveSGD and ActiveAdamW PPLs show the reduced sensitivity
of the ActiveLR variants to the value of the initial learning rate compared
with the vanilla variants.

(a) Test-set PPL (lower is better)

(b) Train-set PPL (lower is better)

Figure 10: WikiText-103 on mini-GPT-2 with various initial learning rates
Table 1: mini-GPT-2 specifications
Hyperparameter | Value
---|---
Vocabulary Size | $10,000$
Block Size | $200$
Number of Layers | 2
Number of Attention Heads | 2

The training hyperparameters are in Table 2.

Table 2: WikiText-103 on mini-GPT-2 hyperparameters
Hyperparameter | Value
---|---
Mini-batch Size | $128$
Maximum Number of Epochs | $200$
Weight Decay | $0.0$
Non-Adaptive Optimizers’ Learning Rates | $[5\times 10^{-6},10^{-1}]$
Adaptive Optimizers’ Learning Rates | $[10^{-7},10^{-2}]$

(a) Test-set PPL (lower is better)

(b) Test-set PPL (lower is better).

(c) Train-set PPL (lower is better)

(d) Train-set PPL (lower is better).

Figure 11: WikiText-103 on mini-GPT-2 with various initial learning rates

#### PASCAL VOC on Faster-RCNN

We train PASCAL VOC on Faster-RCNN (Ren et al., 2015) with pretrained
ResNet-50 backbone, following (Zhuang et al., 2020).

(a) Test-set mAP (higher is better) Figure 12: PASCAL VOC on Faster-RCNN with
various initial learning rates

The results are shown in Figure 12. Note that we could not replicate the mAP
from (Zhuang et al., 2020); we suspect the reason is their use of the
MMDetection (Chen et al., 2019) framework, which does various extra image
augmentation transforms.

###  A.3 The choice of $\alpha_{low}$ and $\alpha_{high}$

We run a simulation to see the range of the learning rate after going through
a series of $\alpha_{low}$ and $\alpha_{high}$ updates. We simulate a setting
where the learning rate, $\alpha$, with 0.5 probability, is decreased by
$\alpha_{low}$, otherwise, it is increased by $\alpha_{high}$. The simulation
is run for $10^{4}$ epochs.

In Figure 13 we see that, consistent with (Tieleman & Hinton, 2012a), only
multiplying by $\alpha_{low}$ and adding to $\alpha_{high}$ maintain a stable
and positive learning rate ($\mu_{\alpha}=1.0$, $\sigma_{\alpha}=0.3$). Other
combinations lead to a negative learning rate (subtract-add and subtract-
multiply) or shrink the learning rate to $0$ (multiply-multiply).

Figure 13: learning rate (y-axis) plotted against training epochs (x-axis)

###  A.4 Proofs

#### Theorem 4.1

In the local convex regime of a non-convex objective function, the cumulative
gradient of parameter $\theta_{i}$ at epoch $e$ with no inner-loop updates,
$\overset{*}{cu}$, has the same sign as the cumulative gradient of parameter
$\theta_{i}$ at epoch $e$ with inner-loop updates, $\widehat{cu}$, if the
learning rate, $\alpha$, is smaller than $\alpha^{*}$ that causes the inner-
loop to diverge.

$\overset{*}{cu}\widehat{cu}\geq 0$ (3)

###### Proof.

We prove this for the general case of the cost function $f$ for inner-loop
updates of SGD. We wish to show that at time $K$, for a dataset of $K$ mini-
batches, the cumulative gradient when there is no inner-loop updates to the
parameters, $\overset{*}{cu}$, has the same sign as the cumulative gradient
when there is SGD updates at each iteration to the parameters, $\widehat{cu}$.
Suppose we are optimizing parameters $\theta$ using a convex objective
function $f(\theta_{t},batch_{t})$, where $\theta_{t}$ and $batch_{t}$ are the
parameter and the mini-batch at time-step $t$. For ease of notation, we will
refer to the objective function evaluated for $batch_{t}$ as $f_{t}$. We will
also refer to the gradients of the objective function w.r.t. the parameter
$\theta_{t}$ for mini-batch $t$, as $g_{t}(\theta_{t})$. When there are no
inner-loop updates, we will refer to the parameter as $\theta_{t}^{*}$, which
will equal the initial $\theta$, i.e., $\theta_{0}$, regardless of the value
of $t$. When there are SGD updates in the inner-loop, we will refer to the
parameter as $\widehat{\theta_{t}}$, which will be determined by the SGD
algorithm 5. Formally,

$\begin{split}\theta_{t}^{*}&=\theta_{0}\end{split}$ (4)

$\begin{split}\widehat{\theta_{t}}&=\widehat{\theta_{t-1}}-\alpha
g_{t}(\widehat{\theta_{t-1}}),\end{split}$ (5)

where $\alpha$ is the constant, positive learning rate and

$\begin{split}g_{t}(\theta)=\frac{\partial{f_{t}(\theta)}}{\partial{\theta}}\end{split}$
(6)

The no-update and SGD-updated cumulative gradients are defined as follows:

$\begin{split}\overset{*}{cu}&=\sum_{t=1}^{K}g_{t}(\theta_{t-1}^{*})\\\
\widehat{cu}&=\sum_{t=1}^{K}g_{t}(\widehat{\theta_{t-1}})\end{split}$ (7)

Since 5 is recursive, we can unroll it from $\widehat{\theta_{t-1}}$ through
$\widehat{\theta_{0}}$:

$\begin{split}\widehat{\theta_{t}}=\theta_{0}-\alpha\sum_{i=1}^{t}g_{i}(\widehat{\theta_{i-1}})\end{split}$
(8)

In order to prove the theorem, we will use the following property of convex
functions:

Supposing that f is a convex function, $a$ and $b$ two points in the domain of
f, and $\frac{\partial{f(b)}}{\partial{b}}$ the derivative of f at point b, we
have:

$f(a)-f(b)\geq\frac{\partial{f(b)}}{\partial{b}}(a-b)$ (9)

We use 9 on $\widehat{\theta_{K}}$, i.e., the final parameter after the
updates, and $\theta_{0}$, the initial parameter, for the objective function
evaluated on batch $t$:

$\begin{split}f_{t}(\widehat{\theta_{K}})-f_{t}(\theta_{0})\geq\frac{\partial{f_{t}(\theta_{0})}}{\partial{\theta_{0}}}(\widehat{\theta_{K}}-\theta_{0})\end{split}$
(10)

Replacing $\frac{\partial{f_{t}(\theta_{0})}}{\partial{\theta_{0}}}$ with
$g_{t}(\theta_{0})$ according to 6:

$\begin{split}f_{t}(\widehat{\theta_{K}})-f_{t}(\theta_{0})\geq
g_{t}(\theta_{0})(\widehat{\theta_{K}}-\theta_{0})\end{split}$ (11)

Replacing $\widehat{\theta_{K}}-\theta_{0}$ with the unrolled version from 8:

$\begin{split}f_{t}(\widehat{\theta_{K}})-f_{t}(\theta_{0})\geq-\alpha
g_{t}(\theta_{0})\sum_{i=1}^{K}g_{i}(\widehat{\theta_{i-1}})\end{split}$ (12)

From the theorem’s assumption that the optimization does not diverge, it
follows that the objective function for the final parameter $\theta_{k}$
should have a lower value than the initial parameter $\theta_{0}$:

$\begin{split}f_{t}(\widehat{\theta_{K}})-f_{t}(\theta_{0})\leq 0\end{split}$
(13)

Combining 12 and 13, we have:

$\begin{split}0\geq f_{t}(\widehat{\theta_{K}})-f_{t}(\theta_{0})\geq-\alpha
g_{t}(\theta_{0})\sum_{i=1}^{K}g_{i}(\widehat{\theta_{i-1}})\\\ 0\leq
f_{t}(\theta_{0})-f_{t}(\widehat{\theta_{K}})\leq\alpha
g_{t}(\theta_{0})\sum_{i=1}^{K}g_{i}(\widehat{\theta_{i-1}})\end{split}$ (14)

From 7, we replace $\sum_{i=1}^{K}g_{i}(\widehat{\theta_{i-1}})$ with
$\widehat{cu}$:

$\begin{split}0\leq f_{t}(\theta_{0})-f_{t}(\theta_{K})\leq\alpha
g_{t}(\theta_{0})\widehat{cu}\end{split}$ (15)

Finally, we sum over all the mini-batches in the dataset, t=1…K:

$\begin{split}&0\leq\sum_{t=1}^{K}[f_{t}(\theta_{0})-f_{t}(\widehat{\theta_{K}})]\leq\sum_{t=1}^{K}[\alpha
g_{t}(\theta_{0})\widehat{cu}]\\\
&0\leq\sum_{t=1}^{K}[f_{t}(\theta_{0})-f_{t}(\widehat{\theta_{K}})]\leq\alpha\widehat{cu}\sum_{t=1}^{K}g_{t}(\theta_{0})\end{split}$
(16)

From 4 and 7, $\sum_{t=1}^{K}g_{t}(\theta_{0})=\overset{*}{cu}$:

$\begin{split}0\leq\sum_{t=1}^{K}[f_{t}(\theta_{0})-f_{t}(\widehat{\theta_{K}})]\leq\alpha\widehat{cu}\overset{*}{cu}\end{split}$
(17)

Since $\alpha$ is positive:

$\begin{split}0\leq\frac{\sum_{t=1}^{K}[f_{t}(\theta_{0})-f_{t}(\widehat{\theta_{K}})]}{\alpha}\leq\widehat{cu}\overset{*}{cu}\qed\end{split}$
(18)

We see that $\widehat{cu}\overset{*}{cu}$ is non-negative and found a lower
bound
$\frac{\sum_{t=1}^{K}[f_{t}(\theta_{0})-f_{t}(\widehat{\theta_{K}})]}{\alpha}$
for it. ∎

#### Theorem 5.1

Let us call the cost of vanilla SGD at epoch e, $f(\theta^{S}_{e})$, and the
cost of its corresponding ActiveLR implementation, $f(\theta^{A}_{e})$. We
define ActiveSGD’s gradient, $g_{e+1}^{A}$, as
$\frac{\partial{f(\theta_{e}^{A})}}{\partial{\theta_{e}^{A}}}$, and vanilla
SGD’s gradient, $g_{e+1}^{S}$, as
$\frac{\partial{f(\theta_{e}^{S})}}{\partial{\theta_{e}^{S}}}$. $\alpha$ is
the initial learning rate for ActiveLR SGD and also the constant learning rate
for SGD. $\alpha_{High}$ is the higher learning rate ($\alpha_{High}>\alpha$)
that ActiveLR uses when $g_{e}^{A}g_{e+1}^{A}>0$ and $\alpha_{Low}$ the lower
learning rate ($\alpha_{Low}<\alpha$) that ActiveLR uses when
$g_{e}^{A}g_{e+1}^{A}<0$. In the local convex regime of $f$, at any arbitrary
epoch, $\mathit{e}$, the difference between the cost of using vanilla SGD and
ActiveLR SGD at the next epoch, $\mathit{e+1}$, is

$\begin{cases}f(\theta^{S}_{e+1})-f(\theta^{A}_{e+1})\geq
g_{e+2}^{A}g_{e+1}^{A}(\alpha_{High}-\alpha),\\\ \text{if
}g_{e}^{A}g_{e+1}^{A}>0.\\\ f(\theta^{S}_{e+1})-f(\theta^{A}_{e+1})\geq
g_{e+2}^{A}g_{e+1}^{A}(\alpha_{Low}-\alpha),\\\ \text{if
}g_{e}^{A}g_{e+1}^{A}<0.\end{cases}$ (19)

where the right hand side for both cases is non-negative.

###### Proof.

At the start, the parameters and gradients are equal for ActiveLR and vanilla
SGD:

$\begin{split}\theta_{e}^{A}&=\theta_{e}^{S}\\\
g_{e+1}^{A}&=g_{e+1}^{S}\end{split}$ (20)

$\theta_{e+1}^{A}$ and $\theta_{e+1}^{S}$ are as follows:

$\theta_{e+1}^{S}=\theta_{e}^{S}-\alpha g_{e+1}^{S}\\\ $ (21)

Replacing $\theta_{e}^{S}$ with $\theta_{e}^{A}$ and $g_{e+1}^{S}$ with
$g_{e+1}^{A}$,

$\theta_{e+1}^{S}=\theta_{e}^{A}-\alpha g_{e+1}^{A}$ (22)

For ActiveLR,

$\begin{split}\begin{cases}&\theta_{e+1}^{A}=\theta_{e}^{A}-\alpha_{High}g_{e+1}^{A},\\\
&\text{if }g_{e}^{A}g_{e+1}^{A}>0.\\\
&\theta_{e+1}^{A}=\theta_{e}^{A}-\alpha_{Low}g_{e+1}^{A},\\\ &\text{if
}g_{e}^{A}g_{e+1}^{A}<0.\end{cases}\end{split}$ (23)

For a differentiable convex function, f, at two points a and b in its domain,
we have

$f(a)\geq f(b)+\frac{\partial{f(b)}}{\partial{b}}(a-b).$ (24)

From 24, for $\theta_{e+1}^{A}$ and $\theta_{e+1}^{S}$ we have

$f(\theta_{e+1}^{S})\geq
f(\theta_{e+1}^{A})+\frac{\partial{f(\theta_{e+1}^{A})}}{\partial{\theta_{e+1}^{A}}}(\theta_{e+1}^{S}-\theta_{e+1}^{A})$
(25)

Replacing $\frac{\partial{f(\theta_{e+1}^{A})}}{\partial{\theta_{e+1}^{A}}}$
with $g_{e+2}^{A}$

$f(\theta_{e+1}^{S})-f(\theta_{e+1}^{A})\geq
g_{e+2}^{A}(\theta_{e+1}^{S}-\theta_{e+1}^{A})$ (26)

Replacing from 22 and 23 into 26:

$\begin{split}\begin{cases}&f(\theta_{e+1}^{S})-f(\theta_{e+1}^{A})\geq
g_{e+2}^{A}g_{e+1}^{A}(\alpha_{High}-\alpha),\\\ &\text{if
}g_{e}^{A}g_{e+1}^{A}>0.\\\ &f(\theta_{e+1}^{S})-f(\theta_{e+1}^{A})\geq
g_{e+2}^{A}g_{e+1}^{A}(\alpha_{Low}-\alpha),\\\ &\text{if
}g_{e}^{A}g_{e+1}^{A}<0.\end{cases}\end{split}$ (27)

We can divide the training process into two segments, $e_{0}$ to $e_{switch}$
when the gradients change after each epoch, and $e_{switch+1}$ to the end of
training, $e_{T}$, when the gradients do not change. Note that the opposite
can be also be true, i.e., $e_{0}$ to $e_{switch}$ is when the gradients do
not change after each epoch, and $e_{switch+1}$ to the end of training,
$e_{T}$, when the gradients change after each epoch. Here we treat the former.
After the proof of the former, the latter can be proved trivially.

While we are in the segment $e_{0}$ to $e_{switch}$, since the gradients
change sign after each epoch, $g_{e+2}^{A}g_{e+1}^{A}<0$ and
$g_{e}^{A}g_{e+1}^{A}<0$. Therefore, the second inequality of 27 holds. On the
right hand side, we have $\alpha_{Low}-\alpha<0$ from the theorem’s
assumption. As a result, the right hand side is non-negative, and
$f(\theta_{e+1}^{S})-f(\theta_{e+1}^{A})$ is greater than or equal to a non-
negative number.

When we are in the segment $e_{switch+1}$ to $e_{T}$, since the gradients do
not change sign after each epoch, $g_{e+2}^{A}g_{e+1}^{A}>0$ and
$g_{e}^{A}g_{e+1}^{A}>0$. Therefore, the first inequality of 27 holds. On the
right hand side, we have $\alpha_{High}-\alpha>0$ from the theorem’s
assumption. As a result, the right hand side is non-negative, and
$f(\theta_{e+1}^{S})-f(\theta_{e+1}^{A})$ is greater than or equal to a non-
negative number. ∎

###  A.5 Interactive webapp

We created an interactive webapp where the readers can compare the performance
of ActiveAdam and Adam in minimizing a saddle and an MSE loss function, with
the ability to change hyper-parameter values, such as initial learning rate,
initial weight, and number of epochs. The webapp can be accessed through the
link below:
https://active-lr.herokuapp.com

##  Appendix B Notes on the appended codes

The training scripts are written for SLURM workload manager since our
experiments were run on HPCs with SLURM.

###  B.1 License

The licenses for the assets used in this paper are the following:

  * •

AdamW: This work is licensed under a BSD 3-Clause ”New” or ”Revised” License

  * •

RAdam: This work is licensed under a Apache License 2.0

  * •

AdaBelief: This work is licensed under a BSD 2-Clause ”Simplified” License

  * •

CIFAR-10 and -100: This work is licensed under a New BSD License

  * •

WikiText-2 and -103: This work is licensed under a Creative Commons
Attribution-ShareAlike License

  * •

ImageNet: This work is licensed under a custom (research, non-commercial)
license

  * •

GPT-2: This work is licensed under a Modified MIT License