# When, Why and How Much?
Adaptive Learning Rate Scheduling by Refinement

Aaron Defazio<EMAIL_ADDRESS>
FAIR, Meta Ashok Cutkosky<EMAIL_ADDRESS>
Boston University Harsh Mehta<EMAIL_ADDRESS>
Google Research Konstantin Mishchenko<EMAIL_ADDRESS>
Samsung AI Center

###### Abstract

Learning rate schedules used in practice bear little resemblance to those
recommended by theory. We close much of this theory/practice gap, and as a
consequence are able to derive new _problem-adaptive_ learning rate schedules.
Our key technical contribution is a refined analysis of learning rate
schedules for a wide class of optimization algorithms (including SGD). In
contrast to most prior works that study the convergence of the average
iterate, we study the last iterate, which is what most people use in practice.
When considering only worst-case analysis, our theory predicts that the best
choice is the “linear decay” schedule: a popular choice in practice that sets
the stepsize proportionally to $1-t/T$, where $t$ is the current iteration and
$T$ is the total number of steps. To go beyond this worst-case analysis, we
use the observed gradient norms to derive schedules _refined_ for any
particular task. These refined schedules exhibit learning rate warm-up and
rapid learning rate annealing near the end of training. Ours is the first
systematic approach to _automatically_ yield both of these properties. We
perform the most comprehensive evaluation of learning rate schedules to date,
evaluating across 10 diverse deep learning problems, a series of LLMs, and a
suite of logistic regression problems. We validate that overall, the linear-
decay schedule matches or outperforms all commonly used default schedules
including cosine annealing, and that our schedule refinement method gives
further improvements.

##  1 Introduction

For minimizing a function $f$, Stochastic Gradient Descent (SGD) updates the
iterate $x_{t}$ at step $t$ via:

$x_{t+1}=x_{t}-\eta_{t}g_{t},$

where $g_{t}$ is a (possibly stochastic) sub-gradient at $x_{t}$, and
$\eta_{t}$ is the learning rate (LR) at time $t$. Choosing a sequence of
$\eta_{t}$ for steps $t=1,\dots,T$ is a core problem in optimization.

The learning rate sequence for an optimizer is typically decomposed into two
parts: the baseline learning rate, indicating the maximum LR to use, and a
schedule, a sequence that multiplies the baseline LR to give the LR sequence.
In this work we focus exclusively on the problem of scheduling. Choosing the
right learning rate schedule for best performance is difficult; standard
practice is to perform a hyper-parameter sweep over a set of standardized
schedules (Wu et al., 2020).

Setting $\eta_{t}$ from theory is difficult due to a multitude of potential
problem assumptions and the wildly varying schedules that arise from these
assumptions. For instance, $\eta_{t}\propto 1/\sqrt{t}$, $\eta_{t}\propto 1/t$
and constant schedules $\eta_{t}=\eta$ are all dictated by three common but
different sets of assumptions. Unfortunately, all three work suboptimally in
practice for deep learning (Section 3.1), and are unpopular in the community
(Ge et al., 2019a). In this work we focus on two causes for this theory-
practice gap:

  1. 1.

Most theory analyzes the average iterate (Polyak, 1990; Ruppert, 1988)
$\hat{x}_{T}=\frac{1}{T}\sum_{t=1}^{T}x_{t}$ or a randomly sampled iterate.
However, in practice the last iterate $x_{T}$ is used.

  2. 2.

Existing theory for the last iterate often uses crude constant bounds on the
gradient norms or curvature. Our new tighter bound involves the entire
gradient norm sequence instead, allowing for problem-adaptive LR schedules.

1:Input: $G=\left\|g_{t}\right\|$ sequence of length $T$, smoothing hyper-
parameter $\tau>0$

2:$\hat{G}=\textrm{median\\_filter}(G,\textrm{filter\\_width}=\tau\,T,\textrm{padding}=(\textrm{nearest},\textrm{reflect}))$

3:Define $w_{t}=\hat{G}_{t}^{-2}$

4:for $t=1$ to $T$ do

5: $\eta_{t}=w_{t}\sum_{p=t+1}^{T}w_{p}$

6:end for

7:Return normalized schedule $\eta/\max(\eta)$

Algorithm 1 Schedule Refinement for SGD

Our method is a “refinement” method: it uses a prior training run to produce
an improved schedule to use in future runs. The practical variant of our
schedule refinement method for SGD is given in Algorithm 1. Given a sequence
of gradient norms produced by a prior run, it outputs a new schedule that is
adaptive to the structure of the problem. Mathematically, it is minimizing a
novel bound we derive on the function value $f(x_{T})$ of the final iterate
(Section 2.1). The learning rate at each time-step involves a sum of inverse-
squared gradient norms from _future_ time-steps, a major departure from
previous approaches to scheduling.

This approach is partially motivated by the remarkable work of Pan et al.
(2022), who show that for the last iterate of quadratic problems, minimizing
an upper bound can yield improved schedules. However their work requires
knowledge of the full Eigenspectrum of the Hessian, making it impractical to
use. Our theory relies on knowledge of the sequence of expected gradient
norms, a more tractable quantity.

Our analytical approach also departs from previous approaches by generalizing
beyond SGD. Prior analyses of learning rate schedules often rely on the
particular form of the SGD iterates to drive the calculations (Jain et al.,
2019; Zamani and Glineur, 2023). Our approach is instead a broad technique
that provides learning rate schedules for _any_ base optimization algorithm.
On a technical level, we design a step-size schedule that converts any
algorithm which obtains a vanishing regret into one that ensures a last-
iterate guarantee. This means that our refinement technique can provide
theoretically-motivated schedules for popular base optimization algorithms
like Adam.

Overall, we make three main contributions:

  1. 1.

Theory: We provide an general analysis of learning rate schedules for
arbitrary optimization algorithms. Our approach recovers the optimal
convergence rates for SGD, and can be used to produce refined schedules
customized for a particular task.

  2. 2.

Practice: Among non-adaptive schedules, we show that warm-up followed by
linear decay almost always matches or outperforms other schedules, including
cosine decay. Our refined schedules typically provide further improvements,
suggesting that our theory provides actionable guidance even for training non-
convex neural networks.

  3. 3.

Theory meets Practice: Our refined schedules exhibit both warmup and nearly-
linear decay (Figure 1). While Zamani and Glineur (2023) have very recently
shown that linear decay has favorable last-iterate guarantees, to our
knowledge this is the first time that warmup has arisen _directly from theory_
rather than as an empirical heuristic (Goya et al., 2017). That is, given
hindsight knowledge of all gradient statistics, our theoretically optimized
schedules usually include a warmup phase during which the learning rate
increases.

Figure 1: Example gradient norm sequences (top row) and the resulting refined
schedules given by Algorithm 1 (bottom row). Black dashed line at $y=1$ shown
for reference. Percentage of runtime on the x-axis.

###  1.1 Notation

$f\colon\mathbb{R}^{d}\to\mathbb{R}$ is a convex objective.
$x_{1},\dots,x_{T}$ and $z_{1},\dots,z_{T}$ are random vectors in
$\mathbb{R}^{d}$ with $x_{1}=z_{1}$, and $\Delta_{t}\triangleq z_{t+1}-z_{t}$.
$\Delta_{t}$ will indicate “baseline” updates before applying a schedule, and
$x_{t}$ will be iterates after applying the schedule. $g_{1},\dots,g_{T}$ are
random vectors in $\mathbb{R}^{d}$ satisfying
$\mathbb{E}[g_{t}|x_{1},\dots,x_{t}]\in\partial f(x_{t})$
($\mathbb{E}[g_{t}]=\nabla f(x_{t})$ when $f$ is differentiable). $G^{2}$ is a
bound on $\mathbb{E}[\max_{t}\|g_{t}\|^{2}]$. $w_{1},\dots,w_{T}$ indicate
non-negative random variables in $\mathbb{R}$ such that $g_{t}$ and $w_{t}$
are independent given $x_{1},\dots,x_{t}$. We define
$w_{a:b}\triangleq\sum_{t=a}^{b}w_{t}$. If $a>b$, then $w_{a:b}\triangleq 0$.
$u$ denotes an arbitrary element of $\mathbb{R}^{d}$; typically one should
consider the case $u\in\operatorname*{arg\,min}f$. $D\triangleq\|x_{1}-u\|$ is
the “distance-to-solution” term, and $f_{\star}\triangleq\inf_{u}f(u)$.

##  2 Main Analytical Result

Our general result is Theorem 1. This allows us to convert any sequence
$z_{1},\dots,z_{T}$ with bounded regret $\sum_{t=1}^{T}\langle
g_{t},z_{t}-u\rangle$ into a sequence of iterates $x_{1},\dots,x_{T}$ with a
bound on $f(x_{T})-f(u)$. Thus, Theorem 1 can be viewed as another addition to
the family of reductions from stochastic optimization to regret bounds (Cesa-
Bianchi et al., 2004; Cutkosky, 2019). The proof can be found in Appendix B.

###### Theorem 1

Suppose $z_{1},\dots,z_{T}$ is some arbitrary sequence of vectors. Let
$w_{1},\dots,w_{T}$ be an arbitrary sequence of non-negative numbers. Recall
that we define $\Delta_{t}=z_{t+1}-z_{t}$ and $x_{1}=z_{1}$. For $t\geq 1$,
suppose $x_{t+1}$ satisfies:

$\displaystyle x_{t+1}=x_{t}+\frac{w_{t+1:T}}{w_{1:T}}\Delta_{t},$

then for any $u$:

$\displaystyle\mathbb{E}[f(x_{T})-f(u)]\leq\mathbb{E}\left[\sum_{t=1}^{T}\frac{1}{w_{1:T}}\langle
w_{t}\cdot g_{t},z_{t}-u\rangle\right].$

Let us take a moment to consider the implications of this Theorem in the
simplest setting of $w_{t}=1$ for all $t$. In this case, it is well-known that
by setting $\Delta_{t}=-\eta g_{t}$ for $\eta=\frac{D}{G\sqrt{T}}$, one
guarantees $\sum_{t=1}^{T}\langle g_{t},z_{t}-u\rangle\leq DG\sqrt{T}$. Thus,
we immediately obtain the following important corollary:

###### Corollary 2

Set $x_{t+1}=x_{t}-\eta_{t}g_{t}$ with
$\eta_{t}=\frac{D}{G\sqrt{T}}\left(1-\frac{t}{T}\right)$. Then:

$\displaystyle\mathbb{E}[f(x_{T})-f(u)]$
$\displaystyle\leq\frac{DG}{\sqrt{T}}.$

Proof  With $w_{t}=1$ for all $t$ and $\Delta_{t}=-\frac{D}{G\sqrt{T}}g_{t}$,
classical online gradient descent analysis (Zinkevich (2003)) yields
$\sum_{t=1}^{T}\langle w_{t}g_{t},z_{t}-u\rangle\leq DG\sqrt{T}$. The result
now follows from Theorem 1.
The sequence $x_{t}$ suggested by Corollary 2 is simply stochastic gradient
descent ($x_{t+1}=x_{t}-\eta_{t}g_{t}$) equipped with a _linear decay learning
rate schedule_ :

$\eta_{t}=\frac{D}{G\sqrt{T}}\left(1-\frac{t}{T}\right).$ (1)

Linear decay emulates the effects of iterate averaging, as the contribution
from each gradient to the returned point is approximately the same as it would
be in an average: the gradient $g_{T/2}$ appears in half the points in the
average, and so its weight is halved, the gradient $g_{t}$ appears in $T-t$
out of $T$ points and so its weight is $1-t/T$.

This bound has a significantly better constant than previous schedules for
last-iterate convergence of SGD in this setting (Jain et al., 2019), and
matches recent work by Zamani and Glineur (2023), who were the first to show
that this schedule is actually optimal for gradient descent for the Convex
$G$-Lipschitz complexity class. Our regret analysis recovers their result when
specialized to SGD.

In practice, the linear decay schedule is employed not only with SGD but also
with a diverse panoply of other optimization algorithms. Our Theorem 1
suggests a theoretical basis for this approach: so long as the underlying
optimization method ensures a regret bound, the linear decay schedule will
provide a last-iterate guarantee. Note that we do not require the regret bound
to be analytically proven (as is the case for e.g. SGD (Zinkevich, 2003),
AdaGrad (Duchi et al., 2011; Streeter and McMahan, 2010) or AMSGrad (Reddi et
al., 2018)); it suffices for the regret bound to hold in practice (as may hold
for Adam (Kingma and Ba, 2015) or AdamW (Loshchilov and Hutter, 2017a)).

The key initial step in the proof of Theorem 1 is an identity we call the
“all-tail summation bound”. This is a refinement of a bound from Orabona
(2020) who attributes the approach originally to Lin et al. (2016). Using the
notation $q_{t}=f(x_{t})-f_{*}$, Lin et al. (2016) use the bound:

$w_{T}q_{T}\leq\frac{1}{T}\sum_{t=1}^{T}w_{t}q_{t}+\sum_{k=1}^{T-1}\frac{1}{k(k+1)}\sum_{t=k+1}^{T}w_{t}\left(q_{t}-q_{k}\right),$

whereas our refined approach uses an equality:

$q_{T}=\frac{1}{w_{1:T}}\sum_{t=1}^{T}w_{t}q_{t}+\sum_{k=1}^{T-1}\frac{\eta_{k}}{\sum_{t=k+1}^{T}\eta_{t}}\left(\frac{1}{\sum_{t=k}^{T}w_{t}}\sum_{t=k}^{T}w_{t}\left(q_{t}-q_{k}\right)\right).$

This identity is derived in Appendix A. All our results arise from careful
manipulation of this identity.

###  2.1 Optimizing the bound for data-dependent schedules

We have now seen that setting $w_{t}=1$ for all $t$ recovers the linear decay
schedule, and can obtain the worst-case optimal convergence rates. However,
optimizing for the worst case usually yields overly pessimistic behavior. In
this section, we build more adaptive schedules that obtain better results on
real data. To do this, we simply choose $w_{t}$ so as to optimize the bound in
Theorem 1.

We focus on the particular case of SGD by setting
$x_{t+1}=x_{t}-\eta_{t}g_{t}$ with $\eta_{t}=\frac{w_{t}w_{t+1:T}}{w_{1:T}}$.
In the notation of Theorem 1, this corresponds to $\Delta_{t}=-w_{t}g_{t}$.
For this case, we have the following result, with proof in Appendix C.

###### Theorem 3

Suppose that $x_{t+1}=x_{t}-\eta_{t}g_{t}$ with
$\eta_{t}=\frac{w_{t}w_{t+1:T}}{w_{1:T}}$. Then we have:

$\displaystyle\mathbb{E}[f(x_{T})-f(u)]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{2\cdot
w_{1:T}}\left(D^{2}+\sum_{t=1}^{T}w_{t}^{2}\|g_{t}\|^{2}\right)\right].$ (2)

Moreover, for a fixed sequence $\|g_{1}\|^{2},\dots,\|g_{T}\|^{2}$, the value
of $\frac{1}{2\cdot w_{1:T}}(D^{2}+\sum_{t=1}^{T}w_{t}^{2}\|g_{t}\|^{2})$ is
minimized by setting:

$\displaystyle
w_{t}=\|g_{t}\|^{-2}\frac{D}{\sqrt{\sum_{p=1}^{T}\|g_{p}\|^{-2}}}.$

Theorem 3 suggests that if we knew the sequence of gradient norms ahead of
time, then we could optimize the weights $w_{t}$ (and therefore the learning
rate schedule $\eta_{t}$) by setting $w_{t}\propto\|g_{t}\|^{-2}$. This yields
a simple practical approach for _refining_ a learning rate schedule based on
empirical observations. First, perform one run using a baseline schedule to
observe the sequence of gradient norms. Then, use these norms to compute an
optimal schedule via Theorem 3. The constant factor $D=\|x_{1}-u\|$ appearing
in the value for $w_{t}$ plays the role of the “scale factor” typically
applied to learning rate schedules. A line of recent work has shown that this
quantity can be efficiently estimated online without significant downsides
(Mcmahan and Streeter, 2012; Orabona and Pál, 2016; Cutkosky and Orabona,
2018; Mhammedi and Koolen, 2020; Zhang et al., 2022; Carmon and Hinder, 2022;
Ivgi et al., 2023; Khaled et al., 2023; Cutkosky et al., 2023).

There are some subtleties here. Allowing $w_{t}$ to depend on random variable
$g_{t}$ breaks the independence between $w_{t}$ and $g_{t}$. Further, the act
of changing the schedule from a baseline to a refined data-dependent schedule
will change the gradient norm sequence, which may in turn indicate that a
substantially different schedule would have been optimal. Our approach relies
on the practical assumption that the gradient norm sequence does not change
significantly after refinement. To encourage this, Algorithm 1 applies a
median smoothing filter to the gradient norms before refining.

Finally, Theorem 3 provides an analysis that recovers schedules for SGD.
However, practitioners commonly use optimization methods with more complicated
_per-coordinate_ updates or other preconditioning schemes such as Adam. In
Appendix E we provide an alternative version of Theorem 3 that applies to such
algorithms (Theorem 8). This result enables us to develop schedules tailored
to any optimization algorithm. However, actually building this schedule in
practice may require inspecting the algorithm’s internal state, which may be
difficult or inefficient. For per-coordinate algorithms like Adam, we suggest
simply setting $w_{t}\propto 1/\|g_{t}\|_{1}$ as an approximation (see Section
3).

Figure 2 gives the Refined schedules on a set of standard benchmark machine
learning problems when initially trained using linear decay schedules to
provide the gradient norm sequences. Full details of the models and training
setup for each problem is provided in the Appendix. Gradient $\ell_{2}$ norms
are shown for SGD trained problems (ImageNet, RCNN) and $\ell_{1}$ norms for
the Adam trained problems, which also use inverse-$\ell_{1}$ norm weights for
refinement (see Section 3). Our single hyper-parameter $\tau=0.1$ was tuned so
that the resulting schedules obtained a balance between smoothness and
capturing structure. We recommend setting this parameter _by eye_ rather than
by grid search.

Figure 2: Gradient Norm sequences and the resulting Refined schedules,
generated using an initial linear decay schedule with warmup for the initial
run. Log scale views are inset for scale reference. Fitted polynomial decay
schedules are overlayed in blue.

##  3 Experiments

Table 1: Logistic Regression Experiments (Train Error Rate %). Problem | Stepwise | Cosine | Linear |  Refined $\left\|g\right\|_{2}^{2}$ |  Refined $\left\|g\right\|_{1}$ | Refined
---|---|---|---|---|---|---
Aloi |  $13.38$ $\pm 0.05$ |  $12.69$ $\pm 0.05$ |  $12.76$ $\pm 0.06$ |  $\mathbf{11.75}$ $\pm 0.01$ |  $12.24$ $\pm 0.04$ |  $12.30$ $\pm 0.05$
Glass |  $31.39$ $\pm 0.16$ |  $30.82$ $\pm 0.22$ |  $30.72$ $\pm 0.18$ |  $\mathbf{30.05}$ $\pm 0.44$ |  $\mathbf{29.62}$ $\pm 0.37$ |  $\mathbf{30}$ $\pm 0.41$
Iris |  $\mathbf{1.39}$ $\pm 0.000$ |  $\mathbf{1.39}$ $\pm 0.000$ |  $\mathbf{1.39}$ $\pm 0.000$ |  $\mathbf{1.46}$ $\pm 0.07$ |  $\mathbf{1.46}$ $\pm 0.07$ |  $\mathbf{1.46}$ $\pm 0.07$
Letter |  $22.24$ $\pm 0.008$ |  $\mathbf{22.24}$ $\pm 0.01$ |  $\mathbf{22.20}$ $\pm 0.02$ |  $\mathbf{22.23}$ $\pm 0.03$ |  $\mathbf{22.20}$ $\pm 0.03$ |  $\mathbf{22.20}$ $\pm 0.03$
Pendigits |  $4.70$ $\pm 0.02$ |  $4.67$ $\pm 0.01$ |  $\mathbf{4.62}$ $\pm 0.03$ |  $\mathbf{4.56}$ $\pm 0.02$ |  $\mathbf{4.58}$ $\pm 0.02$ |  $\mathbf{4.56}$ $\pm 0.04$
Sensorless |  $11.84$ $\pm 0.09$ |  $11.30$ $\pm 0.09$ |  $11.29$ $\pm 0.09$ |  $10.71$ $\pm 0.08$ |  $\mathbf{10.08}$ $\pm 0.05$ |  $\mathbf{10.11}$ $\pm 0.05$
Vehicle |  $18.83$ $\pm 0.09$ |  $18.49$ $\pm 0.05$ |  $18.55$ $\pm 0.06$ |  $\mathbf{18.21}$ $\pm 0.12$ |  $\mathbf{18.19}$ $\pm 0.08$ |  $\mathbf{18.21}$ $\pm 0.1$
Vowel |  $23.43$ $\pm 0.08$ |  $22.99$ $\pm 0.09$ |  $22.94$ $\pm 0.10$ |  $\mathbf{22.48}$ $\pm 0.12$ |  $\mathbf{22.44}$ $\pm 0.08$ |  $\mathbf{22.41}$ $\pm 0.08$

To validate the effectiveness of our method on convex problems, we performed a
comparison across 8 commonly used classification problems from the LIBSVM
repository, with separable problems excluded (see Section 3.5). We used a
logistic regression loss together with the Adam optimizer with
$\beta=(0.9,0.95)$, with batch size 16 and trained for 100 epochs. The Refined
schedules were calculated by using the linear decay schedule to generate the
initial gradient norm sequence. Table 1 demonstrates that both the linear
decay schedule and our refinement schedule consistently either match or out-
perform the cosine schedule. The linear decay schedule matches the cosine
schedule on every problem (up to statistical significance), and out-performs
it on two problems. The Refined schedule further out-performs the linear decay
schedule, either matching of exceeding it across the board.

Rather than using the Adam specific weighting for deriving the Refined
schedules, it is often convenient to use other norms, particularly if existing
logs are available using these other norms. In Table 1 we present results
using both the $\ell_{1}$ norm and $\ell_{2}$ norm-squared weighting. Both are
shown to maintain the advantages of the refinement technique, out-performing
the non-refined schedules consistently. Given the ease of logging $\ell_{1}$
norms compared to the internal Adam state, we advocate for weights to be the
inverse of the $\ell_{1}$ norm (no squaring) when using Adam.

###  3.1 Deep Learning experiments

Figure 3: Training curves on CIFAR-10 for a sweep over inverse-sqrt and
inverse-linear hyper-parameters. A linear-decay schedule baseline is shown in
orange. All combinations are out-performed by the linear-decay schedule.

Classical any-time learning rates schedules such as $1/\sqrt{t}$ and $1/t$ are
commonly used in theoretical analysis of optimization methods, yet they are
rarely used by practitioners. To illustrate why, in Figure 3, we sweep over
the learning rate $\eta$ and offset $\beta$ for schedules of the form:

$\eta\frac{\beta}{\beta+t}\quad\text{and}\quad\eta\frac{\sqrt{\beta}}{\sqrt{\beta+t}}.$

A 5% duration learning rate warmup was also included in each case. Even with
60 hyper-parameter combinations tried for each family, neither are able to
match the performance of the linear-decay schedule. For our deep learning
experiments we implemented two commonly used practical variants of these
schedules, since sweeping the $\beta$ hyper-parameter is computationally
impractical. The vanilla version uses $\beta=1$, and the _offset_ version uses
$\beta$ set to match the duration of the warmup period (a common setting due
to its implementation in FairSeq).

###  3.2 Large-scale schedule benchmark

We performed a large-scale comparison of schedules across common deep learning
benchmarks:

CIFAR10

For a small-scale image-classification problem, we chose CIFAR10 (Krizhevsky,
2009). A high-performance Wide ResNet architecture was used (Zagoruyko and
Komodakis, 2016). Test error percentage is reported.

CIFAR100

A more realistic yet still small scale benchmark. We used a compact DenseNet
architecture (Huang et al., 2017) to increase the diversity of model
architectures tested. Test error percentage is reported.

ImageNet

We used a ResNet-50 architecture (He et al., 2016) for the ImageNet
(Russakovsky et al., 2015) classification task. Note that we used a standard
(non-SOTA) data-augmentation pipeline following other recent comparisons in
the optimization literature. Test error percentage is reported.

IWSLT14

A small-scale German-English translation task (Cettolo et al., 2014) using a
LSTM model (Wiseman and Rush, 2016). Test Perplexity is reported.

GPT

A modern small (162M parameter) GPT-style auto-regressive transformer model
(Radford et al., 2019) trained on the large Book-Wiki corpus (Zhu et al.,
2015). Test Perplexity is reported.

RoBERTa

A masked autoencoder variant (Liu et al., 2019) also trained on the Book-Wiki
corpus. Test Perplexity is reported.

ViT

A high-performance ImageNet classifier using a Vision Transformer (Dosovitskiy
et al., 2021). In contrast to our ResNet-50 experiments, here we use modern
data-augmentation, following standard practice for ViT training. Test error
percentage is reported.

DLRM

A modern recommendation system engine (Naumov et al., 2019) trained on the
open Criteo Kaggle Display Advertising dataset. Test Accuracy is reported.

MRI

A large stacked U-Net architecture (Sriram et al., 2020) trained on the
fastMRI dataset (Zbontar et al., 2018), an image-to-image regression task from
the medical imaging domain. Test set metric $100\cdot(1-\text{SSIM})$ is
reported.

RCNN

The object detection method Faster-RCNN (Ren et al., 2015) trained on the COCO
2017 dataset, using a ResNet-50 ImageNet pretrained backbone. $100-\text{box
AP}$ is reported.

For each problem, we first performed a sweep of learning rates on a grid
[$10^{i}$, $2\times 10^{i}$, $5\times 10^{i}$] for varying $i$, separately for
each schedule. We then ran multiple seeds using the best learning-rate from
the grid search. Mean and standard error of the mean was tabulated for each
schedule. The best result for each method, up to a statistical significance
level of 0.05 using a paired two-sample t-test, is highlighted in bold.
Specific details of the hyper-parameters used for each problem are given in
Appendix G. All non-adaptive schedules included a fixed learning-rate warmup,
with length following standard practices for the problem. Our step-wise
schedule uses a 30-60-90 percent tenthing, following standard practices from
ImageNet training. As in the convex experiments, the Refined schedules were
calculated by using the linear schedule to generate the initial gradient norm
sequence.

Tables 2 & 3 show the results. We break the schedules into two categories,
classical and modern. The modern schedules consistently outperform the
classical schedules, often by large margins. Although this is common folk-law
in deep learning, we are not aware of any existing large-scale experiments
establishing this. Our comparison of modern schedules shows a clear hierarchy
among the schedules. The Stepwise schedule is dominated by the Cosine
schedule, and the Linear schedule matches or outperforms the Cosine schedule
on all problems except ViT. The refined schedule further outperforms the
Linear schedule on 5 of the 10 problems, but shows mixed results on ViT and
RCNN. The refinement process produced degenerate schedules that fail on the
CIFAR problems, we discuss this in Appendix 3.5.

Table 2: Classical Schedule Comparison Against the Linear Schedule (lower = better). Problem | Flat | 1/t | 1/sqrt | Offset 1/t | Offset 1/sqrt | Linear
---|---|---|---|---|---|---
CIFAR10 |  $8.04$ $\pm.13$ |  $5.42$ $\pm.28$ |  $6.37$ $\pm.41$ |  $9.23$ $\pm.08$ |  $6.58$ $\pm.06$ |  $\mathbf{4.35}$ $\pm.05$
CIFAR100 |  $30.43$ $\pm.20$ |  $26.58$ $\pm.11$ |  $29.09$ $\pm.16$ |  $32.80$ $\pm.07$ |  $27.62$ $\pm.13$ |  $\mathbf{22.11}$ $\pm.08$
ImageNet |  $33.00$ $\pm.14$ |  $26.48$ $\pm.06$ |  $28.35$ $\pm.05$ |  $47.94$ $\pm.08$ |  $27.34$ $\pm.06$ |  $\mathbf{23.11}$ $\pm.07$
IWSLT14 |  $8.07$ $\pm.02$ |  $7.62$ $\pm.01$ |  $7.52$ $\pm.01$ |  $12.89$ $\pm.06$ |  $8.48$ $\pm.01$ |  $\mathbf{7.10}$ $\pm.01$
GPT |  $20.20$ $\pm.000$ |  $18.99$ $\pm.04$ |  $19.48$ $\pm.02$ |  $27.85$ $\pm.05$ |  $22.88$ $\pm.006$ |  $\mathbf{18.60}$ $\pm.02$
RoBERTa |  $4.52$ $\pm.005$ |  $4.25$ $\pm.007$ |  $4.33$ $\pm.01$ |  $5.33$ $\pm.02$ |  $5.15$ $\pm.02$ |  $\mathbf{3.94}$ $\pm.007$
DLRM |  $\mathbf{20.95}$ $\pm.006$ |  $47.59$ $\pm 6.45$ |  $45.99$ $\pm 5.98$ |  $\mathbf{20.94}$ $\pm.007$ |  $20.99$ $\pm.009$ |  $\mathbf{20.94}$ $\pm.006$
MRI |  $\mathbf{9.00}$ $\pm.04$ |  $8.91$ $\pm.01$ |  $\mathbf{8.98}$ $\pm.04$ |  $9.53$ $\pm.08$ |  $9.16$ $\pm.05$ |  $\mathbf{8.88}$ $\pm.02$
ViT |  $30.11$ $\pm.27$ |  $28.36$ $\pm.40$ |  $28.53$ $\pm.15$ |  $73.84$ $\pm 6.08$ |  $50.36$ $\pm 12.39$ |  $\mathbf{24.82}$ $\pm.31$
RCNN |  $65.43$ $\pm.12$ |  $63.38$ $\pm.05$ |  $64.13$ $\pm.10$ |  $79.32$ $\pm.07$ |  $69.25$ $\pm.07$ |  $\mathbf{60.98}$ $\pm.02$
Table 3: Modern Schedule Comparison (lower = better). Problem | Stepwise | Cosine | Linear | Refinement
---|---|---|---|---
CIFAR10 |  $4.53$ $\pm.03$ |  $\mathbf{4.27}$ $\pm.04$ |  $\mathbf{4.35}$ $\pm.05$ | -
CIFAR100 |  $22.78$ $\pm.10$ |  $22.59$ $\pm.09$ |  $\mathbf{22.11}$ $\pm.08$ | -
ImageNet |  $23.51$ $\pm.07$ |  $\mathbf{23.10}$ $\pm.06$ |  $\mathbf{23.11}$ $\pm.07$ |  $\mathbf{23.12}$ $\pm 0.03$
IWSLT14 |  $7.43$ $\pm.01$ |  $7.17$ $\pm.009$ |  $7.10$ $\pm.01$ |  $\mathbf{6.92}$ $\pm.03$
GPT |  $19.70$ $\pm.03$ |  $18.65$ $\pm.02$ |  $18.60$ $\pm.02$ |  $\mathbf{18.29}$ $\pm.005$
RoBERTa |  $4.36$ $\pm.01$ |  $4.07$ $\pm.000$ |  $3.94$ $\pm.007$ |  $\mathbf{3.86}$ $\pm.005$
DLRM |  $20.95$ $\pm.008$ |  $\mathbf{20.94}$ $\pm.005$ |  $\mathbf{20.94}$ $\pm.006$ |  $\mathbf{20.94}$ $\pm.009$
MRI |  $8.97$ $\pm.02$ |  $8.90$ $\pm.03$ |  $8.88$ $\pm.02$ |  $\mathbf{8.85}$ $\pm.01$
ViT |  $26.27$ $\pm.33$ |  $\mathbf{24.56}$ $\pm.15$ |  $24.82$ $\pm.31$ |  $25.53$ $\pm.16$
RCNN |  $61.76$ $\pm.06$ |  $\mathbf{61.00}$ $\pm.04$ |  $\mathbf{60.98}$ $\pm.02$ |  $61.88$ $\pm.02$

###  3.3 Cosine schedule ablations

To further investigate the failure modes of the cosine schedule, we ran a
series of shorter duration training runs on CIFAR10. Our premise was that the
cosine schedule is heavily over-fit to long training duration computer vision
problems. As shown in Table 4, the cosine schedule begins to under-perform the
linear decay schedule and the refined schedules when training for less than 30
epochs. In contrast, while the refined schedule also under-performs for longer
duration training it has no statistically significant differences from the
linear decay schedule for shorter duration training, where they both perform
consistently better than the cosine schedule.

Table 4: CIFAR10 Training Time Ablations (Test Error %). Schedule | 1 Epoch | 5 Epochs | 15 Epochs | 30 Epochs
---|---|---|---|---
Cosine |  $35.80$ $\pm 0.27$ |  $15.07$ $\pm 0.11$ |  $7.99$ $\pm 0.06$ |  $\mathbf{6.08}$ $\pm 0.03$
Linear Decay |  $\mathbf{33.84}$ $\pm 0.17$ |  $\mathbf{14.36}$ $\pm 0.07$ |  $\mathbf{7.65}$ $\pm 0.07$ |  $\mathbf{6.12}$ $\pm 0.08$
Refined |  $\mathbf{34.04}$ $\pm 0.19$ |  $\mathbf{14.59}$ $\pm 0.08$ |  $7.88$ $\pm 0.04$ |  $6.24$ $\pm 0.06$
Figure 4:  Limitations of refinement: if model over-fits, our method produces
degenerate schedules.

###  3.4 Large Language Model size ablations

Figure 5:  Normalized learning rate schedules learned on vanilla Transformer-based LLM trained on C4 dataset. Left: schedules obtained when setting $w_{t}\propto\|g_{t}\|^{-2}$. Right: schedules when $w_{t}\propto 1/\|g_{t}\|_{1}$. We find that $\ell_{1}$ norm is much more consistent across model sizes and baseline schedules. Thus, we used $w_{t}\propto 1/\|g_{t}\|_{1}$ weighting from linear baselines to obtained Refined schedule mentioned in Table 5. The x axis is training steps. Table 5: LLM Ablations (C4 validation loss). Schedule | 117M | 284M | 1B | 3.5B
---|---|---|---|---
Cosine | $3.089$ | $2.891$ | $2.729$ | $2.631$
Linear Decay | $3.087$ | $2.888$ | $2.725$ | $\mathbf{2.625}$
Refined | $\mathbf{3.075}$ | $\mathbf{2.884}$ | $\mathbf{2.722}$ | $2.634$

In addition to the results above, we validate our insights on Language Models
by performing an additional set of experiments directly comparing to the
setting explored in Chinchilla (Hoffmann et al., 2022) where we train a
vanilla Transformer model on the C4 dataset (Raffel et al., 2020) for 10k
steps with a token batch size of around 524k ($2^{19}$). Starting with
Hoffmann et al. (2022), most recent LLMs employ the AdamW optimizer with
Linear Warmup and Cosine Decay. We perform a head-to-head comparison of Cosine
decay, Linear decay and Refined schedules (the latter is refined from Linear
decay). As shown in Table 5, contrary to popular wisdom, Linear decay performs
better than Cosine decay across all model sizes. The Refined schedule
outperforms Linear Decay for all but the 3.5B sized model.

###  3.5 Limitations

The cifar10 and cifar100 problems show potential pitfalls from using our
approach (Figure 4) when our assumptions break down. On these problems $100\%$
train accuracy is reached near the end, driving the gradient norm sequence to
zero. The resulting refined schedule rapidly increases the step size near the
end of optimization, which if used results in training divergence. We suggest
using a linear decay schedule instead on problems where the gradient norm
drops significantly at the end.

##  4 Discussion

Gradient sequences that slowly decrease or slowly increase after stabilizing
are often observed in practice (Figure 2), and the resulting schedules that
our framework produces show interesting behavior, resembling polynomial-decay
schedules with exponents $p$:

$\eta_{t}\propto\left(1-\frac{t}{T}\right)^{p}.$ (3)

Schedules of this form are already in use, with $p$ typically tuned as a
hyper-parameter. From Figure 1, we see that $p<1$ should be used when the
gradient norm is decreasing over time, $p>1$ when the gradient norm is
increasing, and $p=1$ when the gradient sequence is flat. We use the term
_polynomial decay_ for the schedule given in Equation 3, which its name in
both PyTorch and Tensorflow, although in the literature schedules of the form
$1/t^{\alpha}$ are also sometimes referred to as polynomial schedules. From
Figure 2, we can see that many of our test problems have refined schedules
that are well-approximated by a polynomial decay sequences, shown in blue.

##  5 Related work

The Robbins-Monro conditions are the foundation of early learning rate theory
(Robbins and Monro, 1951). They advocated for step size sequences where
$\sum_{t=1}^{\infty}\eta_{t}=\infty$ and
$\sum_{t=1}^{\infty}\eta_{t}^{2}<\infty$. Of the schedules satisfying these
conditions, they advocated for schedules with $1/t$ decay as they are
asymptotically optimal for twice continuously differentiable and strongly
convex functions. This schedule was later shown to be optimal (even non-
asymptotically) for strongly convex G-Lipschitz stochastic optimization when
appropriate averaging is used (Shamir and Zhang, 2013; Lacoste-Julien et al.,
2012; Rakhlin et al., 2012).

Nemirovski et al. (2009) point out that the performance of these step-sizes is
extremely poor when the base step size is miss-specified, and advocate
$1/\sqrt{t}$ step sizes, which have the advantage of performing asymptotically
optimally when strong convexity is not present. The use of $1/\sqrt{t}$ step
sizes in combination with averaging was originally developed by Polyak (1990)
and Ruppert (1988), and are optimal for the complexity class of G-Lipschitz
convex functions with or without stochasticity (Blair, 1985; Nesterov, 2018).

Scheduling for the stochastic quadratic setting has seen significant recent
interest. The seminal work of Bach and Moulines (2013) establish that a flat
$1/4R$ schedule (for a given problem dependent-constant $R$), independent of
the stopping time $T$, gives the optimal $\mathcal{O}(1/T)$ rate for the
average iterate. For the last iterate, Ge et al. (2019a) establish that the
step-decay schedule’s rate:

$\Theta\left(\frac{d\sigma^{2}}{T}\log T\right),$

Table 6: Polynomial Decay Schedules fit to refined schedules Problem | Warmup | Power
---|---|---
DLRM | 20% | 0.9
GPT | 28% | 1.0
RoBERTa | 45% | 0.8
MRI | 40% | 0.9
RCNN | 0% | 1.5
ImageNet | 1% | 3.0

is a multiplicative log factor worse than the mini-max optimal rate. Here $d$
is the dimensionality of the problem and $\sigma$ a bound on the noise. They
further show that the any-time last-iterate behavior of SGD is poor, visiting
highly sub-optimal function values infinitely often. Pan et al. (2022) study
the situation where the full Hessian spectrum is know in advance. In this
case, they are able to improve the rate to

$\mathcal{O}\left(\frac{d\sigma^{2}}{T}\log\kappa\right),$

or, under a skewed spectrum assumption, to

$\mathcal{O}\left(\frac{d\sigma^{2}}{T}\right).$

Ge et al. (2019b) show that commonly used schedules such as polynomial decay
schedules are sub-optimal in the quadratic setting.

###  5.1 Non-smooth last iterate convergence

For non-smooth stochastic optimization, Shamir and Zhang (2013) show that the
last iterate of SGD on non-smooth, convex problems with a $1/\sqrt{t}$ step
size is

$\mathcal{O}\left(\frac{\log(n)}{\sqrt{n}}\right).$

Harvey et al. (2019) show a corresponding lower bound, showing that the log
factor is unavoidable when using $1/\sqrt{t}$ step-sizes.

Jain et al. (2019) were the first to show that the log-factor can be removed
if the horizon is known in advance. Their approach uses a sequence of step
sizes:

$\gamma_{t}=\frac{D2^{-i}}{G\sqrt{T+1}},$

where $i$ is an epoch counter, for a sequence of epochs each half the length
of the preceding epoch. This step size sequence gives a convergence rate for
the last iterate of:

$E\left[f(x_{T})-f_{*}\right]\leq\frac{15GD}{\sqrt{T}}.$

For more general conversions from regret bounds to last iterate guarantees,
Cutkosky (2019) provides an alternative conversion based upon evaluating
gradients at running averages of iterates and achieves the same last-iterate
convergence rate as Theorem 1. However, our method is directly interpretable
in terms of learning rate schedules to yield immediate practical guidance
while the technique of Cutkosky (2019) is a more opaque transformation of the
base algorithm. Nevertheless, there are interesting contrasts: the result of
Cutkosky (2019) is ”anytime” in the sense that each individual iterate comes
with an optimal convergence guarantee. In our case, only the last iterate has
an optimal guarantee (in fact, Zamani and Glineur (2023) show that this
restriction is necessary for any scheme based on learning rate schedules).
Understanding the differences in these approaches is a valuable future
direction.

###  5.2 Schedules in Applications

Learning rate schedules used in applications usually fall within a few
standard classes supported by major frameworks. To survey the use of
schedulers in open source software, we performed a GitHub search on each of
the schedulers in the PyTorch Library. Table 7 shows that the polynomial decay
schedule that we advocate is currently the least popular scheduler in PyTorch.

PyTorch Scheduler | Github Files (in thousands)
---|---
ReduceLROnPlateau | 105
StepLR | 101
MultiStepLR | 37.9
CosineAnnealingLR | 37.1
ExponentialLR | 16
OneCycleLR | 14.9
CosineAnnealingWarmRestarts | 10.9
CyclicLR | 9.1
LinearLR | 5.9
ConstantLR | 3.6
MultiplicativeLR | 2.6
PolynomialLR | 1.3
Table 7: Popularity of standard learning rate schedules

The reduce-on-plateau, and its fixed length sister, the step-wise schedule,
popularized by Krizhevsky et al. (2012) for use in image classification, is
considered a benchmark method. They justify it heuristically (“The heuristic
which we followed was to divide the learning rate by 10 when the validation
error rate stopped improving with the current learning rate.”). Due to its use
in highly influential papers as well as its use in tutorials, it is by far the
most commonly used schedule (Table 7).

Many early works use step-sizes satisfying the Robbins-Monro conditions, such
as step sizes proportional to $1/(c+\alpha t)$, for some $c$ and $\alpha$, as
advocated in the influential work of Bottou (1991, 2012). These step sizes
produce large values for small $t$ and so are often clipped (using
$\min(\beta,\cdot)$ for some $\beta$).

Schedules involving restarting (also called cycling) are also widely used,
particularly on computer vision problems where overfitting can be an issue
(Smith and Topin, 2018). Loshchilov and Hutter (2017b) use restarting together
with the cosine annealing schedule:

$\eta_{t}=\eta_{\min}+\left(\eta_{\max}-\eta_{\min}\right)\left(1+\cos\left(\frac{t}{T}\pi\right)\right),$
(4)

This schedule is remarkably effective in practice for image classification
problems even without restarts; as far as the authors are aware, for ResNet-50
ImageNet training, no schedule has been demonstrated that out-performs it. It
is less commonly used in other problem domains. The motivation for the use of
cosine function is unstated, and there is no theory to support it. The reasons
for the success of the schedule are not currently understood.

The only large-scale comparison of schedulers for deep learning optimization
that we are aware of is the work of Schmidt et al. (2021). They compare on a
smaller set of problems than our comparison, although across a range of
optimizers, whereas we focus on just Adam & SGD.

###  5.3 Any-time Adaptive Schedules

There has been significant work on any-time learning rate adaptation that
makes use of gradient or loss information to adapt the learning rate.
Schedules in the AdaGradNorm class are backed by strong theory (Wu et al.,
2020; Streeter and McMahan, 2010; Duchi et al., 2011; Ward et al., 2019; Li
and Orabona, 2019). They use step sizes of the form:

$\eta_{t}\propto\frac{1}{\sqrt{\sum_{t=1}^{T}\left\|g_{t}\right\|^{2}}}$

They have not seen significant adoption in practice, likely due to the
intrinsic disadvantages of any-time $O(1/\sqrt{t})$-style schedules as already
discussed. It is also not clear how to apply this schedule on top of existing
high-performance optimizers such as Adam.

Methods based on hyper-gradients (i.e. gradients of the learning rate) are
another heavily studied class of any-time adaptive methods. They use recent
gradient evaluations and other local information to update the learning rate
at each step of training (Almeida et al., 1999; Franceschi et al., 2017;
Bengio, 2000; Domke, 2012; Pedregosa, 2016; Baydin et al., 2018; Feurer and
Hutter, 2019; Donini et al., 2020; Chandra et al., 2022). The hyper-gradient
can also be used in a more cautious manor to define conditions under which the
learning rate should be decreased (Pflug, 1983, 1988; Lang et al., 2019; Zhang
et al., 2020).

Methods based on loss minimization aim to choose a learning rate that greedily
minimize the loss, either at each step, or based on aggregate statistics that
are either produced in stages or by smoothing. They include methods that
target the train loss or loss on held out validation data (Xu et al., 2019;
Jin et al., 2021; Kim et al., 2021).

Methods that query additional points, such as line search methods, are not
scheduling methods _per se_ but can be used in place of scheduling (Mahsereci
and Hennig, 2017; Iyer et al., 2021). Due to the additional implementation
complexity and the cost of their use, they also have not seen widespread
adoption for deep learning.

### Conclusion

Our experimental results strongly support the use of the linear decay schedule
as a default baseline for deep learning optimization. Applying refinement on
top of an initial linear decay run gives a schedule showing improvements on 5
out of 10 deep learning problems and 5 of 8 convex problems. We develop
extensive theory supporting the linear decay schedule and our novel refinement
technique, establishing that their SOTA performance is well-supported both in
theory and practice.

## References

  * Almeida et al. (1999) Luís B. Almeida, Thibault Langlois, José D. Amaral, and Alexander Plakhov.  _Parameter Adaptation in Stochastic Optimization_ , page 111–134.  Cambridge University Press, USA, 1999.  ISBN 0521652634.
  * Bach and Moulines (2013) Francis Bach and Eric Moulines.  Non-strongly-convex smooth stochastic approimxation with convergence rate o(1/n).  _Neural Information Processing Systems (NeuRIPS)_ , 2013.
  * Baydin et al. (2018) Atılım Güneş Baydin, Robert Cornish, David Martínez Rubio, Mark Schmidt, and Frank Wood.  Online learning rate adaptation with hypergradient descent.  In _Sixth International Conference on Learning Representations (ICLR), Vancouver, Canada, April 30 – May 3, 2018_ , 2018.
  * Bengio (2000) Yoshua Bengio.  Gradient-based optimization of hyperparameters.  In _Neural Computation_ , 2000.
  * Blair (1985) Charles Blair.  Problem complexity and method efficiency in optimization (a. s. nemirovsky and d. b. yudin).  _SIAM Review_ , 27(2):264–265, 1985.
  * Bottou (1991) Leon Bottou.  Stochastic gradient learning in neural networks.  _Proceedings of Neuro-Nımes_ , 91(8):12, 1991\.
  * Bottou (2012) Léon Bottou.  _Stochastic Gradient Descent Tricks_ , pages 421–436.  Springer Berlin Heidelberg, 2012.
  * Carmon and Hinder (2022) Yair Carmon and Oliver Hinder.  Making sgd parameter-free.  In _Conference on Learning Theory_ , pages 2360–2389. PMLR, 2022\.
  * Cesa-Bianchi et al. (2004) Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile.  On the generalization ability of on-line learning algorithms.  _IEEE Transactions on Information Theory_ , 50(9):2050–2057, 2004.
  * Cettolo et al. (2014) Mauro Cettolo, Jan Niehues, Sebastian Stüker, Luisa Bentivogli, and Marcello Federico.  Report on the 11th IWSLT evaluation campaign.  In _IWSLT_ , 2014.
  * Chandra et al. (2022) Kartik Chandra, Audrey Xie, Jonathan Ragan-Kelley, and Erik Meijer.  Gradient descent: The ultimate optimizer.  In _36th Conference on Neural Information Processing Systems (NeurIPS)_ , 2022.
  * Cutkosky (2019) Ashok Cutkosky.  Anytime online-to-batch, optimism and acceleration.  In _International conference on machine learning_ , pages 1446–1454. PMLR, 2019.
  * Cutkosky and Orabona (2018) Ashok Cutkosky and Francesco Orabona.  Black-box reductions for parameter-free online learning in banach spaces.  In _Conference On Learning Theory_ , pages 1493–1529. PMLR, 2018\.
  * Cutkosky et al. (2023) Ashok Cutkosky, Aaron Defazio, and Harsh Mehta.  Mechanic: A learning rate tuner.  _arXiv preprint arXiv:2306.00144_ , 2023.
  * Domke (2012) Justin Domke.  Generic methods for optimization-based modeling.  In _Fifteenth International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2012.
  * Donini et al. (2020) Michele Donini, Luca Franceschi, Orchid Majumder, Massimiliano Pontil, and Paolo Frasconi.  Marthe: Scheduling the learning rate via online hypergradients.  In Christian Bessiere, editor, _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20_ , pages 2119–2125. International Joint Conferences on Artificial Intelligence Organization, 7 2020.
  * Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2021.
  * Duchi et al. (2011) John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12(61), 2011.
  * Feurer and Hutter (2019) Matthias Feurer and Frank Hutter.  _Automated Machine Learning_ , chapter Hyperparameter Optimization.  Springer International Publishing, 2019.
  * Franceschi et al. (2017) Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil.  Forward and reverse gradient-based hyperparameter optimization.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 1165–1173. PMLR, 2017.
  * Ge et al. (2019a) Rong Ge, Sham M. Kakade, Rahul Kidambi, and Praneeth Netrapalli.  The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares.  _Neural Information Processing Systems (NeuRIPS)_ , 2019a.
  * Ge et al. (2019b) Rong Ge, Sham M. Kakade, Rahul Kidambi, and Praneeth Netrapalli.  Rethinking learning rate schedules for stochastic optimization, 2019b.  URL https://openreview.net/forum?id=HJePy3RcF7.
  * Goya et al. (2017) Priya Goya, Piotr Dollar, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He.  Accurate, large minibatch SGD: Training ImageNet in 1 hour.  Technical report, Facebook, 2017.
  * Harvey et al. (2019) Nicholas J. A. Harvey, Christopher Liaw, and Yaniv Plan Sikander Randhawa.  Tight analyses for non-smooth stochastic gradient descent.  _Annual Conference on Learning Theory (COLT)_ , 2019.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016.
  * Hoffmann et al. (2022) Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katherine Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals, Jack William Rae, and Laurent Sifre.  An empirical analysis of compute-optimal large language model training.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=iBBcRUlOAPR.
  * Huang et al. (2017) Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q. Weinberger.  Densely connected convolutional networks.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 2261–2269, 2017.  doi: 10.1109/CVPR.2017.243.
  * Ivgi et al. (2023) Maor Ivgi, Oliver Hinder, and Yair Carmon.  DoG is SGD’s best friend: A parameter-free dynamic step size schedule.  _The 40th International Conference on Machine Learning (ICML 2023)_ , 2023.
  * Iyer et al. (2021) Nikhil Iyer, V. Thejas, Nipun Kwatra, Ramachandran Ramjee, and Muthian Sivathanu.  Lrtuner: A learning rate tuner for deep neural networks, 2021.
  * Jain et al. (2019) Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli.  Making the last iterate of SGD information theoretically optimal.  _Conference On Learning Theory (COLT)_ , 2019.
  * Jin et al. (2021) Yuchen Jin, Tianyi Zhou, Liangyu Zhao, Yibo Zhu, Chuanxiong Guo, Marco Canini, and Arvind Krishnamurthy.  Autolrs: Automatic learning-rate schedule by bayesian optimization on the fly.  In _Proceedings of the Ninth International Conference on Learning Representations (ICLR 2021)_ , 2021.
  * Khaled et al. (2023) Ahmed Khaled, Konstantin Mishchenko, and Chi Jin.  DoWG unleashed: An efficient universal parameter-free gradient descent method.  _arXiv preprint arXiv:2305.16284_ , 2023.
  * Kim et al. (2021) Chiheon Kim, Saehoon Kim, Jongmin Kim, Donghoon Lee, and Sungwoong Kim.  Automated learning rate scheduler for large-batch training.  _arXiv preprint arXiv:2107.05855_ , 2021.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Yoshua Bengio and Yann LeCun, editors, _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.  URL http://arxiv.org/abs/1412.6980.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, University of Toronto, 2009.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.
  * Lacoste-Julien et al. (2012) Simon Lacoste-Julien, Mark Schmidt, and Francis Bach.  A simpler approach to obtaining an $O(1/t)$ convergence rate for the projected stochastic subgradient method, 2012.
  * Lang et al. (2019) Hunter Lang, Lin Xiao, and Pengchuan Zhang.  Using statistics to automate stochastic optimization.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Li and Orabona (2019) Xiaoyu Li and Francesco Orabona.  On the convergence of stochastic gradient descent with adaptive stepsizes.  In _The 22nd international conference on artificial intelligence and statistics_ , pages 983–992. PMLR, 2019.
  * Lin et al. (2016) Junhong Lin, Lorenzo Rosasco, and Ding-Xuan Zhou.  Iterative regularization for learning with convex loss functions.  _Journal of Machine Learning Research_ , 17(77):1–38, 2016.  URL http://jmlr.org/papers/v17/15-115.html.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  RoBERTa: A robustly optimized BERT pretraining approach.  _arXiv preprint arXiv:1907.11692_ , 2019.
  * Loshchilov and Hutter (2017a) Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_ , 2017a.
  * Loshchilov and Hutter (2017b) Ilya Loshchilov and Frank Hutter.  SGDR: Stochastic gradient descent with warm restarts, 2017b.
  * Mahsereci and Hennig (2017) Maren Mahsereci and Philipp Hennig.  Probabilistic line searches for stochastic optimization.  _J. Mach. Learn. Res._ , 18(1):4262–4320, jan 2017.  ISSN 1532-4435.
  * Mcmahan and Streeter (2012) Brendan Mcmahan and Matthew Streeter.  No-regret algorithms for unconstrained online convex optimization.  _Advances in neural information processing systems_ , 25, 2012.
  * Mhammedi and Koolen (2020) Zakaria Mhammedi and Wouter M. Koolen.  Lipschitz and comparator-norm adaptivity in online learning.  In _Conference on Learning Theory_ , pages 2858–2887. PMLR, 2020\.
  * Naumov et al. (2019) Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang, Narayanan Sundaraman, Jongsoo Park, Xiaodong Wang, Udit Gupta, Carole-Jean Wu, Alisson G. Azzolini, Dmytro Dzhulgakov, Andrey Mallevich, Ilia Cherniavskii, Yinghai Lu, Raghuraman Krishnamoorthi, Ansha Yu, Volodymyr Kondratenko, Stephanie Pereira, Xianjie Chen, Wenlin Chen, Vijay Rao, Bill Jia, Liang Xiong, and Misha Smelyanskiy.  Deep learning recommendation model for personalization and recommendation systems.  _CoRR_ , 2019.
  * Nemirovski et al. (2009) A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on Optimization_ , 19(4):1574–1609, 2009.
  * Nesterov (2018) Yurii Nesterov.  _Lectures on Convex Optimization_.  Springer Nature, 2018.
  * Orabona (2020) Francesco Orabona.  Last iterate of SGD converges (even in unbounded domains), Aug 2020\.  URL https://parameterfree.com/2020/08/07/last-iterate-of-sgd-converges-even-in-unbounded-domains/.
  * Orabona and Pál (2016) Francesco Orabona and Dávid Pál.  Coin betting and parameter-free online learning.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Pan et al. (2022) Rui Pan, Haishan Ye, and Tong Zhang.  Eigencurve: Optimal learning rate schedule for SGD on quadratic objectives with skewed hessian spectrums.  _International Conference on Learning Representations (ICLR)_ , 2022\.
  * Pedregosa (2016) Fabian Pedregosa.  Hyperparameter optimization with approximate gradient.  In _International conference on machine learning_ , pages 737–746. PMLR, 2016.
  * Pflug (1983) Georg Ch. Pflug.  On the determination of the step size in stochastic quasigradient methods.  _International Institute for Applied Systems Analysis (IIASA), Laxenburg, Austria_ , 1983.
  * Pflug (1988) Georg Ch. Pflug.  Adaptive stepsize control in stochastic approximation algorithms.  In _Proceedings of 8th IFAC Symposium on Identification and System Parameter Estimation,_ , 1988.
  * Polyak (1990) Boris Polyak.  New stochastic approximation type procedures.  _Avtomatica i Telemekhanika_ , 7:98–107, 01 1990.
  * Radford et al. (2019) Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever.  Improving language understanding by generative pre-training.  Technical report, OpenAI, 2019.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67, 2020.  URL http://jmlr.org/papers/v21/20-074.html.
  * Rakhlin et al. (2012) Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan.  Making gradient descent optimal for strongly convex stochastic optimization.  In _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , ICML’12, 2012.
  * Reddi et al. (2018) Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar.  On the convergence of Adam and beyond.  In _Sixth International Conference on Learning Representations (ICLR), Vancouver, Canada, April 30 – May 3, 2018_ , 2018.
  * Ren et al. (2015) Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster R-CNN: Towards real-time object detection with region proposal networks.  In _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc., 2015.
  * Robbins and Monro (1951) Herbert Robbins and Sutton Monro.  A Stochastic Approximation Method.  _The Annals of Mathematical Statistics_ , 22(3):400 – 407, 1951.
  * Ruppert (1988) David Ruppert.  Efficient estimations from a slowly convergent robbins-monro process.  _Technical Report, Cornell University_ , 02 1988.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  _International Journal of Computer Vision (IJCV)_ , 115(3), 2015.
  * Schmidt et al. (2021) Robin M Schmidt, Frank Schneider, and Philipp Hennig.  Descending through a crowded valley - benchmarking deep learning optimizers.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 9367–9376. PMLR, 18–24 Jul 2021.
  * Shamir and Zhang (2013) Ohad Shamir and Tong Zhang.  Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes.  _International Conference on Machine Learning (ICML)_ , 2013.
  * Smith and Topin (2018) Leslie N. Smith and Nicholay Topin.  Super-convergence: Very fast training of residual networks using large learning rates, 2018.
  * Sriram et al. (2020) Anuroop Sriram, Jure Zbontar, Tullie Murrell, Aaron Defazio, C. Lawrence Zitnick, Nafissa Yakubova, Florian Knoll, and Patricia Johnson.  End-to-end variational networks for accelerated MRI reconstruction.  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_. Springer, 2020.
  * Streeter and McMahan (2010) Matthew Streeter and H. Brendan McMahan.  Less regret via online conditioning.  _arXiv preprint arXiv:1002.4862_ , 2010.
  * Ward et al. (2019) Rachel Ward, Xiaoxia Wu, and Leon Bottou.  Adagrad stepsizes: sharp convergence over nonconvex landscapes.  In _International Conference on Machine Learning_ , 2019.
  * Wiseman and Rush (2016) Sam Wiseman and Alexander M. Rush.  Sequence-to-sequence learning as beam-search optimization.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, 2016\.
  * Wu et al. (2020) Xiaoxia Wu, Rachel Ward, and Léon Bottou.  WNGrad: Learn the learning rate in gradient descent.  _arXiv preprint arXiv:1803.02865_ , 2020.
  * Xu et al. (2019) Zhen Xu, Andrew M. Dai, Jonas Kemp, and Luke Metz.  Learning an adaptive learning rate schedule.  _arXiv preprint arXiv:1909.09712_ , 2019.
  * Zagoruyko and Komodakis (2016) Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  In _Proceedings of the British Machine Vision Conference (BMVC)_ , 2016.
  * Zamani and Glineur (2023) Moslem Zamani and François Glineur.  Exact convergence rate of the last iterate in subgradient methods.  _arXiv preprint arXiv:2307.11134_ , 2023.
  * Zbontar et al. (2018) Jure Zbontar, Florian Knoll, Anuroop Sriram, Matthew J. Muckley, Mary Bruno, Aaron Defazio, Marc Parente, Krzysztof J. Geras, Joe Katsnelson, Hersh Chandarana, et al.  fastMRI: An open dataset and benchmarks for accelerated MRI.  _arXiv preprint arXiv:1811.08839_ , 2018.
  * Zhang et al. (2020) Pengchuan Zhang, Hunter Lang, Qiang Liu, and Lin Xiao.  Statistical adaptive stochastic gradient methods.  _arXiv preprint arXiv:2002.10597_ , 2020.
  * Zhang et al. (2022) Zhiyu Zhang, Ashok Cutkosky, and Ioannis Paschalidis.  PDE-based optimal strategy for unconstrained online learning.  In _International Conference on Machine Learning_ , pages 26085–26115. PMLR, 2022.
  * Zhu et al. (2015) Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler.  Aligning books and movies: Towards story-like visual explanations by watching movies and reading books.  In _Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV)_ , 2015.
  * Zinkevich (2003) Martin Zinkevich.  Online convex programming and generalized infinitesimal gradient ascent.  In _Proceedings of the Twentieth International Conference on International Conference on Machine Learning_ , pages 928–935, 2003.

##  Appendix A All-Tail Summation Bound

In this section we develop some key Lemmas that underlie our results. The
starting point of this development is the following result from Orabona
(2020); Lin et al. (2016). We present the result and proof below for
completeness, and then provide an improved version of the bound (Lemma 5) that
is used to derive our analytical results.

###  A.1 Existing bound

###### Lemma 4

Let $q_{t}\geq 0$, and let $\eta_{t}$ be a positive non-increasing sequence.
Then:

$\eta_{T}q_{T}\leq\frac{1}{T}\sum_{t=1}^{T}\eta_{t}q_{t}+\sum_{k=1}^{T-1}\frac{1}{k(k+1)}\sum_{t=k+1}^{T}\eta_{t}\left(q_{t}-q_{k}\right),$

Proof  We present below a version of the proof that’s written to move the
single inequality application in the whole proof to the last step. Define
$S_{k}=\frac{1}{k}\sum_{t=T-k+1}^{T}\eta_{t}q_{t}$.

Then

$\displaystyle kS_{k}$ $\displaystyle=(k+1)S_{k+1}-\eta_{T-k}q_{T-k}$
$\displaystyle=kS_{k+1}+S_{k+1}-\eta_{T-k}q_{T-k}$
$\displaystyle=kS_{k+1}+\frac{1}{k+1}\sum_{t=T-k}^{T}\left(\eta_{t}q_{t}-\eta_{T-k}q_{T-k}\right).$

Dividing through by $k$:

$S_{k}=S_{k+1}+\frac{1}{k(k+1)}\sum_{t=T-k}^{T}\left(\eta_{t}q_{t}-\eta_{T-k}q_{T-k}\right).$

Unrolling, we have:

$S_{1}=S_{T}+\sum_{k=1}^{T-1}\frac{1}{k(k+1)}\sum_{t=T-k}^{T}\left(\eta_{t}q_{t}-\eta_{T-k}q_{T-k}\right).$

Now we use $S_{1}=\eta_{T}q_{T}$. Note that the first entry in that sum is
zero so we may shift the indexing to start at $t=T-k+1$. Giving:

$\displaystyle\eta_{T}q_{T}$
$\displaystyle=S_{T}+\sum_{k=1}^{T-1}\frac{1}{k(k+1)}\sum_{t=T-k+1}^{T}\left(\eta_{t}q_{t}-\eta_{T-k}q_{T-k}\right)$
$\displaystyle\leq
S_{T}+\sum_{k=1}^{T-1}\frac{1}{k(k+1)}\sum_{t=T-k+1}^{T}\eta_{t}\left(q_{t}-q_{T-k}\right).$

Where the final step uses the fact that $\eta_{t}$ is decreasing. Plugging in
the definition of $S_{T}$, and substituting $k=T-k$ to simplify gives the
result.

###  A.2 Improved expression

###### Lemma 5

Let $q_{t}$ be any sequence, and let $w_{t}$ be a positive sequence. Then:

$\displaystyle q_{T}$
$\displaystyle=\frac{1}{\sum_{t=1}^{T}w_{t}}\sum_{t=1}^{T}w_{t}q_{t}+\sum_{k=1}^{T-1}\frac{w_{k}}{\sum_{t=k+1}^{T}w_{t}}\left(\frac{1}{\sum_{t=k}^{T}w_{t}}\sum_{t=k}^{T}w_{t}\left(q_{t}-q_{k}\right)\right)$
$\displaystyle=\frac{1}{w_{1:T}}\sum_{t=1}^{T}w_{t}q_{t}+\sum_{k=1}^{T-1}\left(\frac{1}{w_{k+1:T}}-\frac{1}{w_{k:T}}\right)\sum_{t=k}^{T}w_{t}\left(q_{t}-q_{k}\right).$

Proof  Define

$S_{k}=\frac{1}{\sum_{t=T-k+1}^{T}w_{t}}\sum_{t=T-k+1}^{T}w_{t}q_{t}.$

Note that with this definition:

$S_{1}=\frac{1}{\sum_{t=T}^{T}w_{t}}\sum_{t=T}^{T}w_{t}q_{t}=q_{T},$

and $S_{T}$ is the full sum:

$S_{T}=\frac{1}{\sum_{t=1}^{T}w_{t}}\sum_{t=1}^{T}w_{t}q_{t}.$

The difference from the weighting used in the the Lemma above: we normalized
by the sum of the step sizes rather than $k$. We get the following expansion:

$\displaystyle\left(\sum_{t=T-k+1}^{T}w_{t}\right)S_{k}$
$\displaystyle=\sum_{t=T-k+1}^{T}w_{t}q_{t}$
$\displaystyle=\sum_{t=T-k}^{T}w_{t}q_{t}-w_{T-k}q_{T-k}$
$\displaystyle=\left(\sum_{t=T-k}^{T}w_{t}\right)S_{k+1}-w_{T-k}q_{T-k}$
$\displaystyle=\left(\sum_{t=T-k+1}^{T}w_{t}\right)S_{k+1}+\left(w_{T-k}S_{k+1}-w_{T-k}q_{T-k}\right).$

So dividing through by $\sum_{t=T-k+1}^{T}w_{t}$:

$S_{k}=S_{k+1}+\frac{w_{T-k}}{\sum_{t=T-k+1}^{T}w_{t}}\left(S_{k+1}-q_{T-k}\right).$

Unrolling

$S_{1}=S_{T}+\sum_{k=1}^{T-1}\frac{w_{T-k}}{\sum_{t=T-k+1}^{T}w_{t}}\left(S_{k+1}-q_{T-k}\right).$

Note that, plugging in $S_{k+1}$:

$\displaystyle S_{k+1}-q_{T-k}$
$\displaystyle=\frac{1}{\sum_{t=T-k}^{T}w_{t}}\sum_{t=T-k}^{T}w_{t}q_{t}-q_{T-k}$
$\displaystyle=\frac{1}{\sum_{t=T-k}^{T}w_{t}}\sum_{t=T-k}^{T}w_{t}\left(q_{t}-q_{T-k}\right).$

So we have:

$q_{T}=\frac{1}{\sum_{t=1}^{T}w_{t}}\sum_{t=1}^{T}w_{t}q_{t}+\sum_{k=1}^{T-1}\frac{w_{T-k}}{\sum_{t=T-k+1}^{T}w_{t}}\left(\frac{1}{\sum_{t=T-k}^{T}w_{t}}\sum_{t=T-k}^{T}w_{t}\left(q_{t}-q_{T-k}\right)\right).$

Finally, we make the simple change of variables $k\to T-k$ to yield the
result.

###### Remark 6

We will typically use this result by setting $q_{t}=f(x_{t})-f_{*}$ in order
to bound $q_{T}=f(x_{T})-f_{*}$. By using a weighting sequence $w_{t}$
elsewhere, we are able to remove the $w_{T}$ weight from in front of the
$q_{T}$ term (in contrast to Lemma 4). This is crucial, as we want to be able
to analyze the situation in which $w_{t}$ drops extremely small near the end,
and yet still bound $q_{T}=f(x_{T})-f_{*}$, but if $q_{T}$ is weighted by
$w_{T}$ we will get very loose bounds when $w_{T}$ is small. Notice also that
we have an equality instead of an inequality, and we have not had to impose
the requirement that $w$ be a non-increasing sequence.

##  Appendix B Proof of Theorem 1

Before proving Theorem 1, we need the following important Lemma:

###### Lemma 7

Suppose $z_{1},\dots,z_{T}$ is an arbitrary sequence of vectors. Let
$w_{1},\dots,w_{T}$ be an arbitrary sequence of positive numbers. Define the
sequence $x_{1},\dots,x_{T}$ recursively by $x_{1}=z_{1}$ and:

$\displaystyle
x_{t}=w_{t:T}\left(\frac{z_{t}}{w_{1:T}}+\sum_{p=1}^{t-1}x_{p}\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)\right).$

Suppose $g_{t}$ are random variables. with
$\mathbb{E}[g_{t}|x_{1},\dots,x_{t}]\in\partial f(x_{t})$ for some convex $f$.
Then:

$\displaystyle\mathbb{E}[f(x_{T})-f(u)]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{w_{1:T}}\sum_{t=1}^{T}w_{t}\langle
g_{t},z_{t}-u\rangle\right].$

Proof  Let us set $q_{t}=f(x_{t})-f(u)$. Then we have
$\mathbb{E}[q_{t}]\leq\mathbb{E}[\langle g_{t},x_{t}-u\rangle]$ and
$\mathbb{E}[q_{t}-q_{k}]\leq\mathbb{E}[\langle g_{t},x_{t}-x_{k}\rangle]$.
Then, Lemma 5 implies:

$\displaystyle\mathbb{E}[q_{T}]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{w_{1:T}}\sum_{t=1}^{T}w_{t}\langle
g_{t},x_{t}-u\rangle+\sum_{k=1}^{T-1}\left(\frac{1}{w_{k+1:T}}-\frac{1}{w_{k:T}}\right)\sum_{t=k}^{T}w_{t}\langle
g_{t},x_{t}-x_{k}\rangle\right].$

Now, let us find the coefficient of $\langle g_{t},x_{t}\rangle$ in the above
expression. This is:

$\displaystyle\frac{w_{t}}{w_{1:T}}+\left[\sum_{k=1}^{t}\left(\frac{1}{w_{k+1:T}}-\frac{1}{w_{k:T}}\right)w_{t}\right]-w_{t}\left(\frac{1}{w_{t+1:T}}-\frac{1}{w_{t:T}}\right)$
$\displaystyle=\frac{w_{t}}{w_{1:T}}+\sum_{k=1}^{t-1}\left(\frac{1}{w_{k+1:T}}-\frac{1}{w_{k:T}}\right)w_{t}$
$\displaystyle=\frac{w_{t}}{w_{t:T}}.$

Next, for $p<t$, the coefficient of $\langle g_{t},x_{p}\rangle$ is:

$\displaystyle-\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)w_{t}.$

And for $p>t$, the coefficient of $\langle g_{t},x_{p}\rangle$ is zero.
Finally the coefficient of $\langle g_{t},u\rangle$ is
$-\frac{w_{t}}{w_{1:T}}$.

Putting this all together, we can rearrange the expression as follows:

$\displaystyle\mathbb{E}[q_{T}]$
$\displaystyle\leq\mathbb{E}\left[\sum_{t=1}^{T}\left\langle
g_{t},\frac{w_{t}}{w_{t:T}}x_{t}-\left(\frac{w_{t}u}{w_{1:T}}+\sum_{p=1}^{t-1}w_{t}x_{t}\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)\right)\right\rangle\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}\left\langle\frac{w_{t}}{w_{t:T}}g_{t},x_{t}-w_{t:T}\left(\frac{u}{w_{1:T}}+\sum_{p=1}^{t-1}x_{p}\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)\right)\right\rangle\right].$

Now, given an arbitrary sequence $z_{1},\dots,z_{T}$, define $x_{t}$
recursively by:

$\displaystyle
x_{t}=w_{t:T}\left(\frac{z_{t}}{w_{1:T}}+\sum_{p=1}^{t-1}x_{p}\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)\right).$

Then we have:

$\displaystyle\mathbb{E}[q_{T}]$
$\displaystyle\leq\mathbb{E}\left[\sum_{t=1}^{T}\left\langle\frac{w_{t}}{w_{t:T}}g_{t},x_{t}-w_{t:T}\left(\frac{u}{w_{1:T}}+\sum_{p=1}^{t-1}x_{p}\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)\right)\right\rangle\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}\frac{w_{t}}{w_{1:T}}\langle
g_{t},z_{t}-u\rangle\right].$

Now, we are finally ready to prove Theorem 1:

See 1

Proof  Let’s define $\hat{x}_{1}=z_{t}$ and recursively set:

$\displaystyle\hat{x}_{t}=w_{t:T}\left(\frac{z_{t}}{w_{1:T}}+\sum_{p=1}^{t-1}\hat{x}_{p}\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)\right).$

Then, Lemma 7 shows that
$\mathbb{E}[f(\hat{x}_{T})-f(u)]\leq\mathbb{E}\left[\frac{1}{w_{1:T}}\sum_{t=1}^{T}w_{t}\langle
g_{t},z_{t}-u\rangle\right]$. So, it suffices to show that $x_{t}=\hat{x}_{t}$
for all $t$. In turn, since $\hat{x}_{1}=z_{1}=x_{1}$, it suffices to show
$\hat{x}_{t+1}-\hat{x}_{t}=\frac{w_{t+1:T}}{w_{1:T}}\Delta_{t}=x_{t+1}-x_{t}$
for all $t$.

To this end, let’s do some calculation. First:

$\displaystyle\hat{x}_{t}$
$\displaystyle=\frac{w_{t}}{w_{t:T}}\hat{x}_{t}+\frac{w_{t+1:T}}{w_{t:T}}\hat{x}_{t}$
$\displaystyle=\frac{w_{t}}{w_{t:T}}\hat{x}_{t}+w_{t+t:T}\left(\frac{z_{t}}{w_{1:T}}+\sum_{p=1}^{t-1}\hat{x}_{p}\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)\right).$

With this expression, we have:

$\displaystyle\hat{x}_{t+1}-\hat{x}_{t}$
$\displaystyle=\hat{x}_{t+1}-w_{t+1:T}\left(\frac{z_{t+1}}{w_{1:T}}+\sum_{p=1}^{t}x_{p}\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)\right)-\frac{w_{t}}{w_{t:T}}\hat{x}_{t}$
$\displaystyle=w_{t+1:T}\left(\frac{z_{t+1}}{w_{1:T}}+\sum_{p=1}^{t}\hat{x}_{p}\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)\right)$
$\displaystyle\qquad-
w_{t+1:T}\left(\frac{z_{t}}{w_{1:T}}+\sum_{p=1}^{t-1}x_{p}\left(\frac{1}{w_{p+1:T}}-\frac{1}{w_{p:T}}\right)\right)-\frac{w_{t}}{w_{t:T}}\hat{x}_{t}$
$\displaystyle=\frac{w_{t+1:T}(z_{t+1}-z_{t})}{w_{1:T}}+w_{t+1:T}\hat{x}_{t}\left(\frac{1}{w_{t+1:T}}-\frac{1}{w_{t:T}}\right)-\frac{w_{t}}{w_{t:T}}\hat{x}_{t}$
$\displaystyle=\frac{w_{t+1:T}}{w_{1:T}}\Delta_{t}+\hat{x}_{t}\left(1-\frac{w_{t+1:T}+w_{t}}{w_{t:T}}\right)$
$\displaystyle=\frac{w_{t+1:T}}{w_{1:T}}\Delta_{t}.$

##  Appendix C Proof of Theorem 3

See 3

Proof  First, observe that with $\Delta_{t}=-w_{t}\eta_{t}$, we have
$x_{t+1}=x_{t}+\frac{w_{t+1:T}}{w_{1:T}}\Delta_{t}$. Therefore with
$z_{1}=x_{1}$ and $z_{t+1}=z_{t}+\Delta_{t}$, Theorem 1 implies:

$\displaystyle\mathbb{E}[f(x_{T})-f(u)]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{w_{1:T}}\sum_{t=1}^{T}\langle
w_{t}g_{t},z_{t}-u\rangle\right].$

Next, observe that $z_{t}$ is simply online gradient descent with learning
rate 1 acting on the loss vectors $w_{t}z_{t}$. Standard analysis (Zinkevich,
2003) shows:

$\displaystyle\sum_{t=1}^{T}\langle w_{t}g_{t},z_{t}-u\rangle$
$\displaystyle=\frac{\|z_{1}-u\|^{2}}{2}-\frac{\|z_{T+1}-u\|^{2}}{2}+\sum_{t=1}^{T}\frac{w_{t}^{2}\|g_{t}\|^{2}}{2}.$

This immediately implies the first part of the Theorem. Next, we need to solve
for the minimizing values of $w_{t}$. To do this, we take the logarithm of the
expression
$\frac{1}{2w_{1:T}}\left(\|x_{1}-u\|^{2}+\sum_{t=1}^{T}w_{t}^{2}\|g_{t}\|^{2}\right)$
and differentiate:

$\displaystyle\frac{\partial}{\partial
w_{k}}\log\left[\frac{1}{2w_{1:T}}\left(\|x_{1}-u\|^{2}+\sum_{t=1}^{T}w_{t}^{2}\|g_{t}\|^{2}\right)\right]$
$\displaystyle=\frac{2w_{k}\|g_{k}\|^{2}}{\|x_{1}-u\|^{2}+\sum_{t=1}^{T}w_{t}^{2}\|g_{t}\|^{2}}-\frac{1}{w_{1:T}}.$

We set this equal to zero to solve for the optimal $w_{k}$:

$\displaystyle w_{k}$
$\displaystyle=\|g_{k}\|^{-2}\frac{\|x_{1}-u\|^{2}+\sum_{t=1}^{T}w_{t}^{2}\|g_{t}\|^{2}}{2w_{1:T}}\triangleq\lambda\|g_{k}\|^{-2},$

where we have defined
$\lambda=\frac{\|x_{1}-u\|^{2}+\sum_{t=1}^{T}w_{t}^{2}\|g_{t}\|^{2}}{2w_{1:T}}$,
which does not depend on $k$. That is, the optimal $w_{k}$ value is
proportional to $\|g_{k}\|^{-2}$. With this expression, we have:

$\displaystyle\sum_{t=1}^{T}w_{t}^{2}\|g_{t}\|^{2}$
$\displaystyle=\lambda^{2}\sum_{t=1}^{T}\|g_{t}\|^{-2}$ $\displaystyle
w_{1:T}$ $\displaystyle=\lambda\sum_{t=1}^{T}\|g_{t}\|^{-2}.$

So, let us now solve for $\lambda$ by plugging in these values:

$\displaystyle\lambda$
$\displaystyle=\frac{\|x_{1}-u\|^{2}+\sum_{t=1}^{T}w_{t}^{2}\|g_{t}\|^{2}}{2w_{1:T}}$
$\displaystyle\lambda$
$\displaystyle=\frac{\|x_{1}-u\|^{2}+\lambda^{2}\sum_{t=1}^{T}\|g_{t}\|^{-2}}{2\lambda\sum_{t=1}^{T}\|g_{t}\|^{-2}}$
$\displaystyle\lambda$
$\displaystyle=\frac{\|x_{1}-u\|^{2}}{2\lambda\sum_{t=1}^{T}\|g_{t}\|^{-2}}+\frac{\lambda}{2}$
$\displaystyle\lambda$
$\displaystyle=\frac{\|x_{1}-u\|}{\sqrt{\sum_{t=1}^{T}\|g_{t}\|^{-2}}}.$

This in turn implies the claimed optimal value for $w_{k}$.

##  Appendix D Proof of Theorem 9

Proof  First, observe that for any solution to the desired identity
$\eta_{t}=\frac{w_{t}w_{t:1:T}}{w_{1:T}}$, replacing $w$ with $c\cdot w$ for
some constant $c$ will yield a solution for $\eta$ replaced with $c\cdot\eta$.
Thus, it suffices to consider the possibility that $\max_{t}\eta_{t}=1$.

The intuition for the rest of the proof is the following: Given the value for
$w_{1}$, we can solve for $w_{2:T}$ using the equation
$\frac{w_{t}w_{2:T}}{w_{1}+w_{2:T}}=\eta_{1}$. This in turn provides us with
the value of $w_{1:T}$. Now, given $w_{k:T}$ for any $k$ we can solve for
$w_{k}$ using the equation
$\eta_{k}=\frac{w_{k}w_{k+1:T}}{w_{1:T}}=\frac{w_{k}(w_{k:T}-w_{k})}{w_{1:T}}$.
Thus we may recursively compute all the values of $w$. Each of these steps
requires solving a quadratic equation. We simply choose an initial $w_{1}$ so
as to ensure that all the following quadratic equations have non-negative real
roots.

Specifically, set $w_{1}=\frac{2^{2T}+\sqrt{2^{4T}-4\eta_{1}}}{2}$ and define
$s_{1}=2^{2T}$. Then, recursively define for $t=2,\dots,T-1$:

$\displaystyle s_{t}$ $\displaystyle=s_{t-1}-w_{t-1}$ $\displaystyle w_{t}$
$\displaystyle=\frac{s_{t}-\sqrt{s_{t}^{2}-4s_{1}\eta_{t}}}{2}$

and set $w_{T}=s_{T}=s_{T-1}-w_{T-1}$. Notice that these choices satisfy:

$\displaystyle w_{t}^{2}-s_{t}w_{t}+s_{1}\eta_{t}=0$

so that if we could establish (1) that all $w_{t}\geq 0$ and (2)
$s_{t}=w_{t:T}$, then we would have:

$\displaystyle\frac{w_{t}w_{t+1:T}}{w_{1:T}}$
$\displaystyle=\frac{w_{t}(w_{t:T}-w_{t})}{w_{1:T}}$
$\displaystyle=\frac{w_{t}(s_{t}-w_{t})}{s_{1}}$
$\displaystyle=\frac{s_{t}w_{t}-w_{t}^{2}}{s_{1}}$ $\displaystyle=\eta_{t}$

as desired.

Let us first prove (1): all $w_{t}\geq 0$. For $t\leq T-1$, this will hold if
$s_{t}^{2}-4s_{1}\eta_{t}>0$ . To establish this, we will first show that
$s_{t}\geq\frac{s_{1}}{2^{t-1}}$ for all $t\leq T-1$. If this holds, then we
have:

$\displaystyle
s_{t}^{2}\geq\frac{s_{1}^{2}}{2^{2t-2}}\geq\frac{s_{1}2^{2T}}{2^{2t-2}}\geq
4s_{1}\geq 4s_{1}\eta_{t}$

for $t\leq T-1$, where we have used our assumption $\eta_{t}\leq 1$.

So, we now establish $s_{t}\geq\frac{s_{1}}{2^{t-1}}$ by induction for $t\leq
T-1$. The statement is clear for $t=1$. Suppose it holds for for all $t\leq k$
for some $k\leq T-2$. Then we have:

$\displaystyle s_{k+1}$ $\displaystyle=s_{k}-w_{k}$
$\displaystyle=\frac{s_{k}+\sqrt{s_{k}^{2}-4s_{1}\eta_{k}}}{2}$
$\displaystyle\geq\frac{s_{k}}{2}$ $\displaystyle\geq\frac{s_{1}}{2^{k-1+1}},$

which establishes the claim. Therefore for $t\leq T-1$, $w_{t}$ are non-
negative real numbers. Finally, we have:

$\displaystyle w_{T-1}$
$\displaystyle=\frac{s_{T-1}+\sqrt{s_{T-1}^{2}-4s_{1}\eta_{t}}}{2}\leq
s_{T-1},$

so that $w_{T}=s_{T}=s_{T-1}-w_{T-1}\geq 0$. Thus $w_{t}\geq 0$ for all $t$.

Next, to show (2): $s_{t}=w_{t:T}$. This is nearly immediate. By definition we
have $w_{T}=s_{T}$. Suppose $s_{k}=w_{t:T}$ for some $t\geq 2$. Then
$s_{t}=s_{t-1}-w_{t-1}$ so that $s_{t-1}=s_{t}+w_{t-1}=w_{t-1:T}$. Thus by
induction we have $s_{t}=w_{t:T}$ for all $t$, which is the last thing we
needed to show.

##  Appendix E Schedules for Per-Coordinate Updates

Many popular optimization algorithms in use today like Adam (Kingma and Ba,
2015) and its variants employ _per-coordinate_ updates: the update
$\Delta_{t}$ is not proportional to the gradient $g_{t}$ but instead scales
each coordinate of $g_{t}$ by an adaptively chosen value. In this section we
propose an approximately optimal schedule for such methods.

###### Theorem 8

Suppose $\Delta_{t}=z_{t+1}-z_{t}=-w_{t}\cdot(\eta_{t}\odot g_{t})$ where
$\eta_{t}\in\mathbb{R}^{d}$ is a vector of learning rates and $\odot$
indicates coordinate-wise product. Set
$x_{t+1}=x_{t}-\frac{w_{t+1:T}}{w_{1:T}}\Delta_{t}$. Define the quantity $R$
by:

$\displaystyle
R=\sqrt{\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{(z_{t,i}-u_{i})^{2}-(z_{t+1,i}-u_{i})^{2}}{\eta_{t,i}}}$

Then we have:

$\displaystyle\mathbb{E}[f(x_{T})-f(u)]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{w_{1:T}}\left(\frac{R^{2}}{2}+\sum_{t=1}^{T}w_{t}^{2}\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}\right)\right].$

Moreover, for any given fixed values for $R$ and $g_{t,i}^{2}$, the expression
$\frac{1}{w_{1:T}}\left(\frac{R^{2}}{2}+\sum_{t=1}^{T}w_{t}^{2}\sum_{i=1}^{d}\eta_{t,i}^{2}g_{t,i}^{2}\right)$
is minimized by setting $w_{t}$ as below:

$\displaystyle w_{t}$
$\displaystyle=\frac{R}{\sqrt{\sum_{t=1}^{T}\left(\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}\right)^{-1}}}\cdot\left(\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}\right)^{-1}.$

As an example of how to use this result, let us suppose we are employing the
Adam optimizer, and let us also also ignore the presence of momentum when
computing the weights (so really, these will be the weights for the RMSProp
optimizer). In this case, $\eta_{t,i}\propto\frac{1}{\sqrt{v_{t,i}}}$ where
$v_{t,i}$ is the exponential average of the squared gradients. Thus, we get:

$\displaystyle
w_{t}=\lambda\left(\sum_{i=1}^{d}\frac{g_{t,i}^{2}}{\sqrt{v_{t,i}}}\right)^{-1}$

for some $\lambda$. Then, we use a learning rate schedule of
$\frac{w_{t}w_{t+1:T}}{w_{1:T}}$.

That is, the corresponding procedure to Algorithm 1 is given by Algorithm 2:

1:Input:
$G=\left(G_{t}=\sum_{i=1}^{d}\frac{g_{t,i}^{2}}{\sqrt{v_{t,i}}}\right)$ length
$T$ sequence of weighted gradient norms from Adam optimizer, smoothing hyper-
parameter $\tau>0$

2:$\hat{G}=\textrm{median\\_filter}(G,\textrm{filter\\_width}=\tau\,T,\textrm{padding}=(\textrm{nearest},\textrm{reflect}))$

3:Define $w_{t}=\hat{G}_{t}^{-1}$

4:For each $t$, let:

5: $\eta_{t}=w_{t}\sum_{p=t+1}^{T}w_{p}$

6:Return normalized schedule $\eta/\max(\eta)$

Algorithm 2 Schedule Refinement for Adam

In practice, however, recording the value
$w_{t}\propto\left(\sum_{i=}^{d}\frac{g_{t,i}^{2}}{\sqrt{v_{t,i}}}\right)^{-1}$
may be difficult (for example, in Pytorch, the Adam implementation is
primarily C code rather than Python, which makes it substantially more
involved to modify). However, by inspecting the formula for $w_{t}$, we can
see that it is likely to be an interpolation between the $1/\|g_{t}\|_{2}^{2}$
and $1/\|g_{t}\|_{1}$ (the L1 norm is not squared). The intuition behind this
is that if $v_{t,i}$ has a minimum value of $|g_{t,i}|$. With this minimum
value, $w_{t}\propto 1/\|g_{t}\|_{1}$. On the other hand if all $v_{t,i}$ are
the same constant, then $w_{t}\propto 1/\|g_{t}\|_{2}^{2}$. In practice we
expect behavior closer to the first case and recommend using $w_{t}\propto
1/\|g_{t}\|_{1}$.

Proof [proof of Theorem 8] By standard online gradient descent analysis, we
have:

$\displaystyle\langle w_{t}\cdot g_{t},z_{t}-u\rangle$
$\displaystyle=\sum_{i=1}^{d}w_{t}g_{t,i}(z_{t,i}-u_{i})$
$\displaystyle=\sum_{i=1}^{d}\frac{(z_{t,i}-u_{i})^{2}}{2\eta_{t,i}}-\frac{(z_{t+1,i}-u_{i})^{2}}{2\eta_{t,i}}+\frac{\eta_{t,i}}{2}w_{t}^{2}g_{t,i}^{2}.$

Summing this over $t$ from $1$ to $T$, we get

$\displaystyle\sum_{t=1}^{T}\langle w_{t}\cdot g_{t},z_{t}-u\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{d}\frac{(z_{t,i}-u_{i})^{2}}{2\eta_{t,i}}-\frac{(z_{t+1,i}-u_{i})^{2}}{2\eta_{t,i}}+\sum_{t=1}^{T}w_{t}^{2}\sum_{i=1}^{d}\frac{\eta_{t,i}g_{t,i}^{2}}{2}$
$\displaystyle=\frac{R^{2}}{2}+\sum_{t=1}^{T}\frac{w_{t}^{2}}{2}\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}.$

The first part of the result now follows from Theorem 1.

Next, we again take the logarithm, differentiate and set equal to zero:

$\displaystyle 0$ $\displaystyle=\frac{\partial}{\partial
w_{k}}\log\left(\frac{1}{w_{1:T}}\left(\frac{R^{2}}{2}+\sum_{t=1}^{T}\frac{w_{t}^{2}}{2}\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}\right)\right)$
$\displaystyle=\frac{2w_{k}\sum_{i=1}^{d}\eta_{k,i}^{2}g_{k,i}^{2}}{R^{2}+\sum_{t=1}^{T}w_{t}^{2}\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}}-\frac{1}{w_{1:T}}.$

Rearranging, we obtain

$\displaystyle w_{k}$
$\displaystyle=\frac{\left(\sum_{i=1}^{d}\eta_{k,i}^{2}g_{k,i}^{2}\right)^{-1}\left(R^{2}+\sum_{t=1}^{T}w_{t}^{2}\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}\right)}{2w_{1:T}}$
$\displaystyle\triangleq\lambda\left(\sum_{i=1}^{d}\eta_{k,i}g_{k,i}^{2}\right)^{-1},$

where we have collected the non $k$-dependent terms into
$\lambda=\frac{R^{2}+\sum_{t=1}^{T}w_{t}^{2}\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}}{2w_{1:T}}$.
Now we solve for $\lambda$:

$\displaystyle\lambda$
$\displaystyle=\frac{R^{2}+\sum_{t=1}^{T}w_{t}^{2}\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}}{2w_{1:T}}$
$\displaystyle=\frac{R^{2}+\lambda^{2}\sum_{t=1}^{T}\left(\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}\right)^{-1}}{2\lambda\sum_{t=1}^{T}\left(\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}\right)^{-1}}$
$\displaystyle=\frac{R^{2}}{2\lambda\sum_{t=1}^{T}\left(\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}\right)^{-1}}+\frac{\lambda}{2}$
$\displaystyle=\frac{R}{\sqrt{\sum_{t=1}^{T}\left(\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}\right)^{-1}}}.$

Putting $w_{t}=\lambda\left(\sum_{i=1}^{d}\eta_{t,i}g_{t,i}^{2}\right)^{-1}$
completes the proof.

##  Appendix F Explicit bounds for arbitrary schedules

Section 2 develops a framework that suggests using learning rates of the form
$\eta_{t}=\frac{w_{t}w_{t+1:T}}{w_{1:T}}$ and in Theorem 3 we provided a
simple closed-form solution for the optimal values of $w_{t}$. Given this
apparently restricted form of $\eta_{t}$, it is natural to ask if this
restriction is real: that is, can _every_ schedule $\eta_{1},\dots,\eta_{T-1}$
be represented using some weights $w_{t}$? Theorem 9 shows that the answer is
“yes”:

###### Theorem 9

Let $\eta_{1},\dots,\eta_{T-1}$ be a sequence of non-negative numbers with
$\eta_{1}\geq 0$. Then there is a sequence of non-negative weights
$w_{1},\dots,w_{T}$ such that $\eta_{t}=\frac{w_{t}w_{t+1:T}}{w_{1:T}}$ for
all $t$.

This Theorem shows that by optimizing the weights $w_{t}$, we are in some
sense also solving for the optimal learning rate $\eta_{t}$. However, notice
that the reverse is not true: any given schedule $\eta_{t}$ can be represented
by a number of different weights $w_{t}$, and these weights give rise to
different bounds using Theorem 1. The proof of Theorem 9 works by constructing
a particular set of weights $w_{t}$, but these may not be the best weights in
terms of providing the tightest convergence bound for the given $\eta_{t}$.

Although Theorem 9 shows that the learning rate representation of Theorem 3
indeed covers all possible schedules, it does not provide a user-friendly way
to analyze the convergence of an arbitrary schedule. In this section, we
provide an alternative analysis that fills this gap.

This approach is closer to previous final-iterate analysis techniques: we
bound the final iterate in terms of the average iterate, plus an additional
_error_ term. This bound is strictly looser than those of Theorems 1 and 3 in
the constant factors, but provides a convenient way to analyze arbitrary
schedules. The bound is presented in Theorem 10 below.

###### Theorem 10

Suppose that $f$ is convex and let $x_{t}$ be given by SGD with learning rates
$\eta_{t}$: $x_{t+1}=x_{t}-\eta_{t}g_{t}$. Then for the last iterate $x_{T}$
we have:

$\displaystyle\mathbb{E}[f(x_{T})-f(u)]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{2\sum_{t=1}^{T}\eta_{t}}D^{2}+\frac{1}{2\sum_{t=1}^{T}\eta_{t}}\sum_{t=1}^{T}\eta_{t}^{2}\left\|g_{t}\right\|^{2}\right]$
$\displaystyle+\mathbb{E}\left[\frac{1}{2}\sum_{k=1}^{T-1}\frac{\eta_{k}}{\sum_{t=k+1}^{T}\eta_{t}}\left(\frac{1}{\sum_{t=k}^{T}\eta_{t}}\sum_{t=k}^{T}\eta_{t}^{2}\left\|g_{t}\right\|^{2}\right)\right].$
(5)

Optimizing this bound with respect to the step-size sequence produces
schedules that are visually indistinguishable from those of the regret based
approach described in Section 2.1 for large $T$.

To prove Theorem 10, we will need to control quantities like:

$\sum_{t=k}^{T}\eta_{t}\left(q_{t}-q_{k}\right)=f(x_{t})-f(x_{k}).$

This can be bounded by the usual suboptimality inequality for SGD/GD methods,
which holds for any $u$:

$\sum_{t=k}^{T}\eta_{t}\left[f(x_{t})-f(u)\right]\leq\frac{1}{2}\left\|x_{k}-u\right\|^{2}+\frac{1}{2}\sum_{t=k}^{T}\eta_{t}^{2}\left\|g_{t}\right\|^{2},$

Setting $u=x_{k}$ yields:

$\sum_{t=k}^{T}\eta_{t}\left[q_{t}-q_{k}\right]\leq\frac{1}{2}\sum_{t=k}^{T}\eta_{t}^{2}\left\|g_{t}\right\|^{2}.$

We can use this in our Lemma 5 to obtain the following result:

###### Corollary 11

$q_{T}=\frac{1}{\sum_{t=1}^{T}\eta_{t}}\sum_{t=1}^{T}\eta_{t}q_{t}+\frac{1}{2}\sum_{k=1}^{T-1}\frac{\eta_{k}}{\sum_{t=k+1}^{T}\eta_{t}}\left(\frac{1}{\sum_{t=k}^{T}\eta_{t}}\sum_{t=k}^{T}\eta_{t}^{2}\left\|g_{t}\right\|^{2}\right).$

Now, we are ready to prove Theorem 10. See 10

Proof  Following the standard convergence bound approach:

$\displaystyle\left\|x_{t+1}-u\right\|^{2}$
$\displaystyle=\left\|x_{t}-\eta_{t}g_{t}-u\right\|^{2}$
$\displaystyle=\left\|x_{t}-u\right\|^{2}-2\eta_{t}\left\langle
g_{t},x_{t}-u\right\rangle+\eta_{t}^{2}\left\|g_{t}\right\|^{2}$
$\displaystyle\leq\left\|x_{t}-u\right\|^{2}-2\eta_{t}\left[f(x_{t})-f(u)\right]+\eta_{t}^{2}\left\|g_{t}\right\|^{2}.$

Summing over $t$ and telescoping gives:

$\sum_{t=1}^{T}\eta_{t}\left[f(x_{t})-f(u)\right]\leq\frac{1}{2}D^{2}+\sum_{t=1}^{T}\eta_{t}^{2}\left\|g_{t}\right\|^{2}.$

Then divide through by $\sum_{t=1}^{T}\eta_{t}$:

$\frac{1}{\sum_{t=1}^{T}\eta_{t}}\sum_{t=1}^{T}\eta_{t}\left[f(x_{t})-f_{*}\right]\leq\frac{1}{2\sum_{t=1}^{T}\eta_{t}}D^{2}+\frac{1}{2\sum_{t=1}^{T}\eta_{t}}\sum_{t=1}^{T}\eta_{t}^{2}\left\|g_{t}\right\|^{2}.$

Now we apply Corollary 11 to get:

$\displaystyle f(x_{T})-f_{*}$
$\displaystyle\leq\frac{1}{2\sum_{t=1}^{T}\eta_{t}}D^{2}+\frac{1}{2\sum_{t=1}^{T}\eta_{t}}\sum_{t=1}^{T}\eta_{t}^{2}\left\|g_{t}\right\|^{2}$
$\displaystyle+\frac{1}{2}\sum_{k=1}^{T-1}\frac{\eta_{k}}{\sum_{t=k+1}^{T}\eta_{t}}\left(\frac{1}{\sum_{t=k}^{T}\eta_{t}}\sum_{t=k}^{T}\eta_{t}^{2}\left\|g_{t}\right\|^{2}\right).$

By using a worst-case bound of $\|g_{t}\|^{2}\leq G^{2}$, we obtain:

###### Corollary 12

If $f$ is $G$-Lipschitz, then

$\displaystyle f(x_{T})-f_{*}$
$\displaystyle\leq\frac{1}{2\sum_{t=1}^{T}\eta_{t}}D^{2}+\frac{G^{2}}{2\sum_{t=1}^{T}\eta_{t}}\sum_{t=1}^{T}\eta_{t}^{2}$
$\displaystyle\quad+\frac{G^{2}}{2}\sum_{k=1}^{T-1}\frac{\eta_{k}}{\sum_{t=k+1}^{T}\eta_{t}}\left(\frac{1}{\sum_{t=k}^{T}\eta_{t}}\sum_{t=k}^{T}\eta_{t}^{2}\right).$

###  F.1 Linear schedule analysis with Theorem 10

In this section, we use Theorem 10 to re-analyze the the linear decay
schedule:

$\eta_{t}=\frac{D}{G\sqrt{T}}\left(1-\frac{t}{T+1}\right).$ (6)

The resulting convergence rate is asymptotically correct, but does not achieve
the optimal constant obtained by Theorem 3.

###### Theorem 13

Schedule 6 gives the following bound on the last iterate:

$f(x_{T})-f_{*}\leq\left(2+\frac{1}{4}\right)\frac{DG}{\sqrt{T}},$

or more precisely:

$f(x_{T})-f_{*}\leq\left(2+\frac{H\left(T-1\right)-2/3}{T+1}\right)\frac{DG}{\sqrt{T}},$

where H(T) is the Tth harmonic sum.

Proof  We start with the above bound:

$\displaystyle f(x_{T})-f_{*}$
$\displaystyle\leq\frac{1}{2\sum_{t=1}^{T}\eta_{t}}D^{2}+\frac{G^{2}}{2\sum_{t=1}^{T}\eta_{t}}\sum_{t=1}^{T}\eta_{t}^{2}$
$\displaystyle+\frac{G^{2}}{2}\sum_{k=1}^{T-1}\frac{\eta_{k}}{\sum_{t=k+1}^{T}\eta_{t}}\left(\frac{1}{\sum_{t=k}^{T}\eta_{t}}\sum_{t=k}^{T}\eta_{t}^{2}\right).$

Since the $\frac{D}{G\sqrt{T}}$ part of the step size is constant, it can be
pulled outside the summations, so we just need to focus on summations
involving $\left(1-\frac{t}{T+1}\right)$. For the first two terms we have in
the bound, they simplify

$\displaystyle\sum_{t=1}^{T}\eta_{t}$
$\displaystyle\propto\sum_{t=1}^{T}\left(1-\frac{t}{T+1}\right)$
$\displaystyle=\left(T-\frac{1}{T+1}\sum_{t=1}^{T}t\right)$
$\displaystyle=\left(T-\frac{1}{2}\frac{T(T+1)}{T+1}\right)$
$\displaystyle=\frac{T}{2}.$

Similarly,

$\displaystyle\sum_{t=1}^{T}\eta_{t}^{2}$
$\displaystyle\propto\sum_{t=1}^{T}\left(1-\frac{t}{T+1}\right)^{2}$
$\displaystyle=\sum_{t=1}^{T}\left(1-\frac{2t}{T+1}+\frac{t^{2}}{T+1^{2}}\right)$
$\displaystyle=\left(T-T+\sum_{t=1}^{T}\frac{t^{2}}{T^{2}}\right)$
$\displaystyle=\left(\frac{T(T+1)(2T+1)}{6(T+1)^{2}}\right)$
$\displaystyle=\left(\frac{T(T+1)(T+1/2)}{3(T+1)^{2}}\right)$
$\displaystyle\leq\frac{T}{3}.$

So we have the following bound on the last iterate:

$\displaystyle f(x_{T})-f_{*}$
$\displaystyle\leq\frac{DG}{\sqrt{T}}+\frac{DG}{3\sqrt{T}}$
$\displaystyle+\frac{G^{2}}{2}\sum_{k=1}^{T-1}\frac{\eta_{k}}{\sum_{t=k+1}^{T}\eta_{t}}\left(\frac{1}{\sum_{t=k}^{T}\eta_{t}}\sum_{t=k+1}^{T}\eta_{t}^{2}\right).$

To simplify the remaining term we rely on computer algebra software. SymPy
gives:

$\sum_{k=1}^{T-1}\frac{\eta_{k}}{\sum_{t=k+1}^{T}\eta_{t}}\left(\frac{1}{\sum_{t=k}^{T}\eta_{t}}\sum_{t=k+1}^{T}\eta_{t}^{2}\right)=\left(\frac{D}{G\sqrt{T}}\right)\frac{4T+6H\left(T-1\right)-4}{3(T+1)}.$

Where $H(T)=\sum_{t=1}^{T}1/t$ is the harmonic sum. So:

$\displaystyle f(x_{T})-f_{*}$
$\displaystyle\leq\frac{DG}{\sqrt{T}}+\frac{DG}{3\sqrt{T}}+\frac{2DG\sqrt{T}}{3T}+\frac{DG\left(3H\left(T-1\right)-2\right)}{3\left(T+1\right)\sqrt{T}}$
$\displaystyle\leq\frac{2DG}{\sqrt{T}}+\frac{DG}{3\sqrt{T}}+\frac{DG\left(3H\left(T-1\right)-2\right)}{3(T+1)\sqrt{T}}.$

Note that the term $\left(3H\left(T-1\right)-2\right)/3\left(T+1\right)\leq
1/4$ for all $T$, so:

$\displaystyle\frac{DG\left(3H\left(T-1\right)-2\right)}{3(T+1)\sqrt{T}}$
$\displaystyle=\frac{DG}{4\sqrt{T}},$

So combining with the $\frac{DG}{\sqrt{T}}+\frac{DG}{3\sqrt{T}}$ terms, we
have:

$f(x_{T})-f_{*}\leq\left(2+\frac{1}{4}\right)\frac{DG}{\sqrt{T}}.$

bounding the harmonic function with a log gives instead:

$f(x_{T})-f_{*}\leq\frac{2DG}{\sqrt{T}}+O\left(\frac{DG\log(T)}{T^{3/2}}\right).$

##  Appendix G Experimental Setup

Our experiments on CIFAR-10, CIFAR-100, ImageNet and RCNN use SGD, and the
remaining problems use Adam. We used decoupled weight decay with Adam in each
case following standard practice for each problem.

###  G.1 Convex Experiments

Each dataset is obtained from the LIBSVM repository with used without
modifications.

Hyper-parameter | Value
---|---
GPUs | 1$\times$V100
Batch size | 16
Epochs | 100
Seeds | 10

Hyper-parameter | Value
---|---
Decay | 0.0
Optimizer | Adam
$\beta_{1}$ | 0.9
$\beta_{2}$ | 0.95

Figure 6: Logistic regression schedules, generated using a linear decay
schedule with warmup for the initial run.

###  G.2 CIFAR-10

We used custom training code based on the PyTorch tutorial code for this
problem. Following standard data-augmentation practises, we appliyed random
horizontal flips and random offset cropping down to 32x32, using reflection
padding of 4 pixels. Input pixel dataD was normalized by centering around 0.5.

Hyper-parameter | Value
---|---
Architecture | Wide ResNet 16-8
Epochs | 300
GPUs | 1$\times$V100
Batch size per GPU | 128
Hyper-parameter | Value
---|---
Seeds | 10
decay | 0.0001
Momentum | 0.9

###  G.3 CIFAR-100

We used the same codebase as for our CIFAR-10 experiments, with the same data
augmentation.

We normalized each input image using fixed mean and standard error values
derived from pre-processing the data.

Hyper-parameter | Value
---|---
Architecture |  | DenseNet [6,12,24,16],
---
growth rate 12
Epochs | 300
GPUs | 1$\times$V100
Hyper-parameter | Value
---|---
Batch size per GPU | 64
Seeds | 10
Decay | 0.0002
Momentum | 0.9

###  G.4 ImageNet

We used the same code-base as for our CIFAR-10 experiments, and applied the
same preprocessing procedure. The data-augmentations consisted of PyTorch’s
RandomResizedCrop, cropping to 224x224 followed by random horizontal flips.
Test images used a fixed resize to 256x256 followed by a center crop to
224x224.

Hyper-parameter | Value
---|---
Architecture | ResNet50
Epochs | 100
GPUs | 8$\times$V100
Batch size per GPU | 32
Hyper-parameter | Value
---|---
Seeds | 5
Decay | 0.0001
Momentum | 0.9

###  G.5 IWSLT14

We used the FairSeq framework 111https://github.com/facebookresearch/fairseq
for our experiments here, as well as for our GPT and RoBERTa experiments.
Rather than a vanilla LSTM we use the variant from (Wiseman and Rush, 2016)
provided in the FairSeq codebase.

Hyper-parameter | Value
---|---
Architecture | lstm_wiseman_iwslt_de_en
Max Epoch | 55
GPUs | 1$\times$V100
Tokens per batch | 4096
Warmup steps | 4000
Dropout | 0.3
Label smoothing | 0.1
Hyper-parameter | Value
---|---
| Share decoder, input,
---
output embed
True
Float16 | True
Update Frequency | 1
Seeds | 10
Decay | 0.05
$\beta_{1},\beta_{2}$ | 0.9, 0.98

###  G.6 RoBERTa

The RoBERTa implementation in FairSeq is the canonical one. We differ from the
paper’s results by training for a shorter duration, which is necessary to keep
our experiments computationally tractable. Our BookWiki dataset matches the
original paper.

Hyper-parameter | Value
---|---
Architecture | roberta_base
Task | masked_lm
Max updates | 23,000
GPUs | 8$\times$V100
Max tokens per sample | 512
Dropout | 0.1
Attention Dropout | 0.1
Max sentences | 16
Hyper-parameter | Value
---|---
Warmup | 10,000
Sample Break Mode | Complete
Float16 | True
Update Frequency | 16
Seeds | 5
Decay | 0.0
$\beta_{1},\beta_{2}$ | 0.9, 0.98

###  G.7 GPT

Since the training dataset for GPT models are not availiable, we use the
BookWiki dataset as used for RoBERTa training. Our model here is small, using
12 decoding layers and a decoder embedding dim of 768, giving 162 million
parameters.

Hyper-parameter | Value
---|---
Architecture | transformer_lm_gpt
Task | language_modeling
Max updates | 65,000
GPUs | 8$\times$V100
Tokens per sample | 512
Dropout | 0.1
Attention Dropout | 0.1
Max sentences | 1
Warmup | 10,000
Hyper-parameter | Value
---|---
Sample Break Mode | Complete
| Share decoder, input,
---
output embed
True
Float16 | True
Update Frequency | 16
Seeds | 5
Decay | 0.005
$\beta_{1},\beta_{2}$ | 0.9, 0.98

###  G.8 ViT

Our implementation uses the PyTorch Image Models library
222https://github.com/rwightman/pytorch-image-models, with hyper-parameters
following examples given in the repository.

Hyper-parameter | Value
---|---
Model | vit_tiny_patch16_224
GPUs | 8$\times$V100
Epochs | 300
Batch Size | 512
Warmup epochs | 5
Hflip | 0.5
aa | rand-m6-mstd0.5
mixup | 0.1
Hyper-parameter | Value
---|---
mixup | 0.1
cutmix | 1.0
Crop Pct | 0.9
BCE Loss | True
Seeds | 5
Decay | 0.1
$\beta_{1},\beta_{2}$ | 0.9, 0.999

###  G.9 DLRM

We used a custom implementation of the DLRM model based on the publicly
available code. Our optimizer uses dense gradients for implementation
simplicity, although sparse-gradients using AdaGrad is a more common baseline
on this problem, we consider AdaGrad variants of our scheduling approach as
future work.

Hyper-parameter | Value
---|---
Iterations | 300 000
Batch Size | 128
Emb Dimension | 16
GPUs | 8$\times$V100
Hyper-parameter | Value
---|---
Seeds | 5
Decay | 0.0
$\beta_{1},\beta_{2}$ | 0.9, 0.999

###  G.10 MRI

We used the version of the the fastMRI code base at
https://github.com/facebookresearch/fastMRI/tree/main/banding_removal. Note
that we found that training failed using PyTorch 2 or newer, and so we ran
these experiments using PyTorch 1.9.

Hyper-parameter | Value
---|---
Architecture | 12 layer VarNet 2.0
Epochs | 50
GPUs | 8$\times$V100
Batch size per GPU | 1
Acceleration factor | 4
Hyper-parameter | Value
---|---
Low frequency lines | 16
Mask type | Offset-1
Seeds | 5
Decay | 0.0
$\beta_{1},\beta_{2}$ | 0.9, 0.999

###  G.11 RCNN

Our RCNN experiments use
Detectron2333https://github.com/facebookresearch/detectron2, and we use a
pretrained ResNet backbone444 detectron2://ImageNetPretrained/MSRA/R-50.pkl.

Hyper-parameter | Value
---|---
Backbone | ResNet-50
Max Iter | 200000
IMS Per Batch | 16
Hyper-parameter | Value
---|---
GPUs | 8$\times$V100
Momentum | 0.9
Decay | 1.5e-4