Critical Bach Size Minimizes Stochastic First-Order Oracle Complexity of Deep
Learning Optimizer using Hyperparameters Close to One
This work was supported by JSPS KAKENHI Grant Number 21K11773.

Hideaki Iiduka
Department of Computer Science, Meiji University, 1-1-1 Higashimita, Tama-ku,
Kawasaki-shi, Kanagawa 214-8571 Japan<EMAIL_ADDRESS>
Abstract: Practical results have shown that deep learning optimizers using
small constant learning rates, hyperparameters close to one, and large batch
sizes can find the model parameters of deep neural networks that minimize the
loss functions. We first show theoretical evidence that the momentum method
(Momentum) and adaptive moment estimation (Adam) perform well in the sense
that the upper bound of the theoretical performance measure is small with a
small constant learning rate, hyperparameters close to one, and a large batch
size. Next, we show that there exists a batch size called the critical batch
size minimizing the stochastic first-order oracle (SFO) complexity, which is
the stochastic gradient computation cost, and that SFO complexity increases
once the batch size exceeds the critical batch size. Finally, we provide
numerical results that support our theoretical results. That is, the numerical
results indicate that Adam using a small constant learning rate,
hyperparameters close to one, and the critical batch size minimizing SFO
complexity has faster convergence than Momentum and stochastic gradient
descent (SGD).

Keywords: Adam, adaptive method, batch size, critical batch size,
hyperparameters, learning rate, nonconvex optimization

##  1 Introduction

###  1.1 Background

Useful deep learning optimizers have been proposed to find the model
parameters of the deep neural networks that minimize loss functions called the
expected risk and empirical risk, such as stochastic gradient descent (SGD)
[17, 27, 13, 6, 7], momentum methods [15, 14], and adaptive methods. The
various adaptive methods include Adaptive Gradient (AdaGrad) [4], Root Mean
Square Propagation (RMSProp) [21], Adaptive Moment Estimation (Adam) [10],
Adaptive Mean Square Gradient (AMSGrad) [16], Yogi [23], Adam with decoupled
weight decay (AdamW) [12], and AdaBelief (named for adapting stepsizes by the
belief in observed gradients) [26].

Theoretical analyses of adaptive methods for nonconvex optimization were
presented in [23, 28, 3, 25, 26, 2, 9] (see [5, 1, 18, 11] for convergence
analyses of SGD for nonconvex optimization). A particularly interesting
feature of adaptive methods is the use of hyperparameters, denoted by
$\beta_{1}$ and $\beta_{2}$, that can be set to influence the method
performance. Almost all of the previous results for convergence analyses of
adaptive methods showed that using $\beta_{1}$ and $\beta_{2}$ close to $0$
makes the upper bound of the performance measure
$(1/K)\sum_{k=1}^{K}\mathbb{E}[\|\nabla f(\bm{\theta}_{k})\|^{2}]$ small,
where $\nabla f$ is the gradient of a loss function
$f\colon\mathbb{R}^{d}\to\mathbb{R}$, $(\bm{\theta}_{k})_{k=1}^{K}$ is the
sequence generated by an optimizer, and $K$ is the number of steps.

Meanwhile, practical results for adaptive methods were presented in [10, 16,
23, 28, 3, 26, 2]. These studies have shown that using, for example,
$\beta_{1}\in\\{0.9,0.99\\}$ and $\beta_{2}\in\\{0.99,0.999\\}$ provides
superior performance for training deep neural networks. The practically useful
$\beta_{1}$ and $\beta_{2}$ are each close to $1$, whereas in contrast, the
theoretical results (the above paragraph) show that using $\beta_{1}$ and
$\beta_{2}$ close to $0$ makes the upper bounds of the performance measures
small.

The practical performance of a deep learning optimizer strongly depends on the
batch size. In [20], it was numerically shown that using an enormous batch
size leads to a reduction in the number of parameter updates and model
training time. The theoretical results in [23] showed that using large batch
sizes makes the upper bound of $\mathbb{E}[\|\nabla f(\bm{\theta}_{k})\|^{2}]$
of an adaptive method small. Convergence analyses of SGD in [1] indicated that
running SGD with a decaying learning rate and large batch size for
sufficiently many steps leads to convergence to a local minimizer of a loss
function. Accordingly, the practical results for large batch sizes match the
theoretical ones.

In [19, 24], it was studied how increasing the batch size affects the
performances of deep learning optimizers. In both studies, it was numerically
shown that increasing batch size tends to decrease the number of steps $K$
needed for training deep neural networks, but with diminishing returns.
Moreover, it was shown that momentum methods can exploit larger batches than
SGD [19], and that K-FAC and Adam can exploit larger batches than momentum
methods [24]. Thus, it was shown that momentum and adaptive methods can
significantly reduce the number of steps $K$ needed for training deep neural
networks [19, Figure 4], [24, Figure 5].

###  1.2 Motivation

####  1.2.1 Hyperparameters close to one and constant learning rate

As described in Section 1.1, the practically useful $\beta_{1}$ and
$\beta_{2}$ are each close to $1$, whereas in contrast, the theoretical
results show that using $\beta_{1}$ and $\beta_{2}$ close to $0$ makes the
upper bounds of the performance measures small. Hence, there is a gap between
theory ($\beta_{1},\beta_{2}\approx 0$) and practice
($\beta_{1},\beta_{2}\approx 1$) for adaptive methods. As a consequence, the
first motivation of this paper is to bridge this gap.

Since using small constant learning rates (e.g., $10^{-2}$, $10^{-3}$, and
$10^{-4}$) is robust for training deep neural networks [10, 16, 23, 28, 3, 26,
2], we focus on using a small constant learning rate $\alpha$. Here, we note
that using a learning rate depending on the Lipschitz constant $L$ of the
gradient of a loss function $f$ would be unrealistic. This is because
computing the Lipschitz constant $L$ is NP-hard [22, Theorem 2].

####  1.2.2 Critical batch size

The second motivation of this paper is to clarify theoretically the
relationship between the diminishing returns reported in [19, 24] and batch
size. Numerical evaluations in [19, 24] have definitively shown that, for deep
learning optimizers, the number of steps $K$ needed to train a deep neural
network halves for each doubling of the batch size $b$ and that there is a
region of diminishing returns beyond the critical batch size $b^{\star}$. This
implies that there is a positive number $C$ such that

$\displaystyle Kb\approx 2^{C}\text{ for }b\leq b^{\star}\text{ and }Kb\geq
2^{C}\text{ for }b\geq b^{\star},$ (1.1)

where $K$ and $b$ are defined for $i,j\in\mathbb{N}$ by $K=2^{i}$ and
$b=2^{j}$ (For example, Figure 2 in Section 4 shows $C\approx 20$ and
$b^{\star}\approx 2^{11}$ for Adam used to train ResNet-20 on the CIFAR-10
dataset). We define the stochastic first-order oracle (SFO) complexity of a
deep learning optimizer as $Kb$ on the basis of the number of steps $K$ needed
for training the deep neural network and the batch size $b$ used in the
optimizer. Let $b^{\star}$ be a critical batch size such that there are
diminishing returns for all batch sizes beyond $b^{\star}$, as asserted in
[19, 24]. This fact, expressed in (1.1), implies that, while SFO complexity
$Kb$ initially almost does not change (i.e., $K$ halves for each doubling of
$b$), $Kb$ is minimized at critical batch size $b^{\star}$, and there are
diminishing returns once the batch size exceeds $b^{\star}$.

###  1.3 Contribution

Our results are summarized in Table 1. Our goal is to find a local minimizer
of a loss function $f$ over $\mathbb{R}^{d}$, i.e., a stationary point
$\bm{\theta}^{\star}\in\mathbb{R}^{d}$ satisfying $\nabla
f(\bm{\theta}^{\star})=\bm{0}$, which is equivalent to the variational
inequality (VI) defined for all $\bm{\theta}\in\mathbb{R}^{d}$ by $\nabla
f(\bm{\theta}^{\star})^{\top}(\bm{\theta}^{\star}-\bm{\theta})\leq 0$. Hence,
we use an $\epsilon$-approximation $\mathrm{VI}(K,\bm{\theta})\leq\epsilon$
(Table 1) as the performance measure of the sequence
$(\bm{\theta}_{k})_{k\in\mathbb{N}}$ generated by a deep learning optimizer,
where $\epsilon>0$ is the precision.

Table 1: Relationship between batch size $b$ and the number of steps $K$ to achieve an $\epsilon$-approximation of an optimizer using a constant learning rate $\alpha$ and hyperparameters $\beta_{1},\beta_{2}$. The critical batch size $b^{\star}$ minimizes SFO complexity $Kb$ ($G$, $\sigma^{2}$, $M$, and $v_{*}$ are positive constants, $D(\bm{\theta})$ is a positive real number depending on $\bm{\theta}\in\mathbb{R}^{d}$, and $h$ defined by (3.5) is monotone decreasing for $\beta_{1}$) Optimizer | SGD | Momentum | Adam
---|---|---|---
$C_{1}$ | $\displaystyle{\frac{\mathbb{E}[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}]}{2\alpha}}$ | $\displaystyle{\frac{\mathbb{E}[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}]}{2\alpha\beta_{1}}}$ | $\displaystyle{\frac{d{D}(\bm{\theta})\sqrt{M}}{2\alpha\beta_{1}\sqrt{1-\beta_{2}}}}$
$C_{2}$ | $\displaystyle{\frac{\sigma^{2}\alpha}{2}}$ | $\displaystyle{\frac{\sigma^{2}\alpha}{2\beta_{1}}}$ | $\displaystyle{\frac{\sigma^{2}\alpha}{2\sqrt{v_{*}}\beta_{1}(1-\beta_{1})}}$
$C_{3}$ | $\displaystyle{\frac{G^{2}\alpha}{2}}$ | $\displaystyle{\frac{G^{2}\alpha}{2\beta_{1}}}+h(\beta_{1})$ | $\displaystyle{\frac{G^{2}\alpha}{2\sqrt{v_{*}}\beta_{1}(1-\beta_{1})}}+h(\beta_{1})$
Upper Bound of VI | $\displaystyle{\mathrm{VI}(K,\bm{\theta}):=\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[\nabla f(\bm{\theta}_{k})^{\top}(\bm{\theta}_{k}-\bm{\theta})\right]\leq\frac{C_{1}}{K}+\frac{C_{2}}{b}+C_{3}=\epsilon}$
Steps $K$ and SFO $Kb$ |  $\displaystyle{K=\frac{C_{1}b}{(\epsilon-C_{3})b-C_{2}}}$ $\displaystyle{Kb=\frac{C_{1}b^{2}}{(\epsilon-C_{3})b-C_{2}}}$
Critical Batch | $\displaystyle{b^{\star}=\frac{2C_{2}}{\epsilon-C_{3}}}$

####  1.3.1 Advantage of setting a small constant learning rate and
hyperparameters close to one

We can show that the upper bound $C_{1}/K+C_{2}/b+C_{3}$ of
$\mathrm{VI}(K,\bm{\theta})$ becomes small when $\alpha$ is small, $\beta_{1}$
and $\beta_{2}$ are close to $1$, and $K$ is large. This implies that Momentum
and Adam perform well when $\alpha$ is small and $\beta_{1}$ and $\beta_{2}$
are each set close to $1$. Section 3.1 shows this result in detail.

####  1.3.2 Critical batch size

We can check that the upper bound $C_{1}/K+C_{2}/b+C_{3}$ of
$\mathrm{VI}(K,\bm{\theta})$ becomes small when a batch size $b$ is large.
Motivated by the results in [19, 24] and Section 1.2.2, we use SFO complexity
$Kb$ as the performance measure of a deep learning optimizer. We first show
that the number of steps $K$ to satisfy
$\mathrm{VI}(K,\bm{\theta})\leq\epsilon$ can be defined as in Table 1. As a
function, $K$ is convex and monotone decreasing with respect to batch size
$b$. Next, we show that SFO complexity $Kb$ defined as in Table 1 is convex
with respect to batch size $b$. This result agrees with the fact of (1.1).
Moreover, SFO complexity $Kb$ is minimized at

$\displaystyle b^{\star}=\frac{2C_{2}}{\epsilon-C_{3}}.$ (1.2)

Section 3.2 shows the above results in detail. From the above discussion, we
conclude that a deep learning optimizer should use the following parameters:

  * •

a small constant learning rate $\alpha$ (e.g., $\alpha=10^{-3}$) and
hyperparameters $\beta_{1}$ and $\beta_{2}$ close to $1$ (e.g.,
$\beta_{1},\beta_{2}\in\\{0.9,0.99,0.999\\}$)

  * •

the critical batch size $b^{\star}$ defined by (1.2)

The accurate setting of the critical batch size $b^{\star}$ defined by (1.2)
would be difficult since $b^{\star}$ in (1.2) involves unknown parameters,
such as $G$ and $\sigma$ (see (2.4) and (A1)). Hence, we would like to
estimate appropriate batch sizes using the formula (1.2) for $b^{\star}$
before implementing deep learning optimizers. Section 4 will discuss
estimation of appropriate batch sizes in detail.

##  2 Nonconvex Optimization and Deep Learning Optimizers

This section gives a nonconvex optimization problem in deep neural networks
and optimizers for solving the problem under standard assumptions.

###  2.1 Nonconvex optimization in deep learning

Let $\mathbb{R}^{d}$ be a $d$-dimensional Euclidean space with inner product
$\langle\bm{x},\bm{y}\rangle:=\bm{x}^{\top}\bm{y}$ inducing the norm
$\|\bm{x}\|$ and $\mathbb{N}$ be the set of nonnegative integers. Define
$[n]:=\\{1,2,\ldots,n\\}$ for $n\geq 1$. Given a parameter
$\bm{\theta}\in\mathbb{R}^{d}$ and a data point $z$ in a data domain $Z$, a
machine learning model provides a prediction whose quality is measured by a
differentiable nonconvex loss function $\ell(\bm{\theta};z)$. We aim to
minimize the expected loss defined for all $\bm{\theta}\in\mathbb{R}^{d}$ by

$\displaystyle
f(\bm{\theta})=\mathbb{E}_{z\sim\mathcal{D}}[\ell(\bm{\theta};z)]=\mathbb{E}[\ell_{\xi}(\bm{\theta})],$
(2.1)

where $\mathcal{D}$ is a probability distribution over $Z$, $\xi$ denotes a
random variable with distribution function $P$, and $\mathbb{E}[\cdot]$
denotes the expectation taken with respect to $\xi$. A particularly
interesting example of (2.1) is the empirical average loss defined for all
$\bm{\theta}\in\mathbb{R}^{d}$ by

$\displaystyle
f(\bm{\theta};S)=\frac{1}{n}\sum_{i\in[n]}\ell(\bm{\theta};z_{i})=\frac{1}{n}\sum_{i\in[n]}\ell_{i}(\bm{\theta}),$
(2.2)

where $S=(z_{1},z_{2},\ldots,z_{n})$ denotes the training set and
$\ell_{i}(\cdot):=\ell(\cdot;z_{i})$ denotes the loss function corresponding
to the $i$-th training data $z_{i}$.

We would like to find a stationary point
$\bm{\theta}^{\star}\in\mathbb{R}^{d}$ of $f$ defined by (2.1). A point
$\bm{\theta}^{\star}\in\mathbb{R}^{d}$ is a stationary point of $f$ if and
only if $\bm{\theta}^{\star}\in\mathbb{R}^{d}$ satisfies the following
variational inequality (VI): for all $\bm{\theta}\in\mathbb{R}^{d}$, $\nabla
f(\bm{\theta}^{\star})^{\top}(\bm{\theta}^{\star}-\bm{\theta})\leq 0$. Hence,
we use

$\displaystyle\mathrm{VI}(K,\bm{\theta}):=\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[\nabla
f(\bm{\theta}_{k})^{\top}(\bm{\theta}_{k}-\bm{\theta})\right]\leq\epsilon$

as the performance measure of the sequence
$(\bm{\theta}_{k})_{k\in\mathbb{N}}$ generated by a deep learning optimizer,
where $\epsilon>0$ is the precision and $K$ denotes the number of steps of the
optimizer (see also Table 1).

###  2.2 Deep learning optimizers

####  2.2.1 Conditions

We assume that a stochastic first-order oracle (SFO) exists such that, for a
given $\bm{\theta}\in\mathbb{R}^{d}$, it returns a stochastic gradient
$\mathsf{G}_{\xi}(\bm{\theta})$ of the function $f$ defined by (2.1), where a
random variable $\xi$ is supported on $\Xi$ independently of $\bm{\theta}$.
The following are standard conditions when considering a deep learning
optimizer.

  1. (C1)

$f\colon\mathbb{R}^{d}\to\mathbb{R}$ defined by (2.1) is continuously
differentiable.

  2. (C2)

Let $(\bm{\theta}_{k})_{k\in\mathbb{N}}\subset\mathbb{R}^{d}$ be the sequence
generated by a deep learning optimizer. For each iteration $k$,

$\displaystyle\mathbb{E}_{\xi_{k}}[\mathsf{G}_{\xi_{k}}(\bm{\theta}_{k})]=\nabla
f(\bm{\theta}_{k}),$ (2.3)

where $\xi_{0},\xi_{1},\ldots$ are independent samples and the random variable
$\xi_{k}$ is independent of $(\bm{\theta}_{l})_{l=0}^{k}$. There exists a
nonnegative constant $\sigma^{2}$ such that

$\displaystyle\mathbb{E}_{\xi_{k}}\left[\left\|\mathsf{G}_{\xi_{k}}(\bm{\theta}_{k})-\nabla
f(\bm{\theta}_{k})\right\|^{2}\right]\leq\sigma^{2}.$ (2.4)

  3. (C3)

For each iteration $k$, the optimizer samples a batch $B_{k}$ of size $b$
independently of $k$ and estimates the full gradient $\nabla f$ as

$\displaystyle\nabla
f_{B_{k}}(\bm{\theta}_{k}):=\frac{1}{b}\sum_{i\in[b]}\mathsf{G}_{\xi_{k,i}}(\bm{\theta}_{k}),$

where $\xi_{k,i}$ is a random variable generated by the $i$-th sampling in the
$k$-th iteration.

In the case that $f$ is defined by (2.2), we have that, for each $k$,
$B_{k}\subset[n]$ and

$\displaystyle\nabla
f_{B_{k}}(\bm{\theta}_{k})=\frac{1}{b}\sum_{i\in[b]}\nabla\ell_{\xi_{k,i}}(\bm{\theta}_{k}).$

####  2.2.2 Adam

Algorithm 1 is the Adam optimizer [10] under (C1)–(C3). The symbol $\odot$ in
step 6 is defined for all $\bm{x}=(x_{i})_{i=1}^{d}\in\mathbb{R}^{d}$,
$\bm{x}\odot\bm{x}:=(x_{i}^{2})_{i=1}^{d}\in\mathbb{R}^{d}$, and
$\mathsf{diag}(x_{i})$ in step 8 is a diagonal matrix with diagonal components
$x_{1},x_{2},\ldots,x_{d}$.

Algorithm 1 Adam [10]

0: $\alpha\in(0,+\infty)$, $b\in(0,+\infty)$, $\beta_{1}\in(0,1)$,
$\beta_{2}\in[0,1)$

1: $k\leftarrow 0$, $\bm{\theta}_{0}\in\mathbb{R}^{d}$, $\bm{m}_{-1}:=\bm{0}$,
$\bm{v}_{-1}:=\bm{0}$

2: loop

3: $\nabla
f_{B_{k}}(\bm{\theta}_{k}):=b^{-1}\sum_{i\in[b]}\mathsf{G}_{\xi_{k,i}}(\bm{\theta}_{k})$

4: $\bm{m}_{k}:=\beta_{1}\bm{m}_{k-1}+(1-\beta_{1})\nabla
f_{B_{k}}(\bm{\theta}_{k})$

5: $\displaystyle{\hat{\bm{m}}_{k}:=(1-\beta_{1}^{k+1})^{-1}\bm{m}_{k}}$

6: $\bm{v}_{k}:=\beta_{2}\bm{v}_{k-1}+(1-\beta_{2})\nabla
f_{B_{k}}(\bm{\theta}_{k})\odot\nabla f_{B_{k}}(\bm{\theta}_{k})$

7: $\displaystyle{\hat{\bm{v}}_{k}:=(1-\beta_{2}^{k+1})^{-1}\bm{v}_{k}}$

8: $\mathsf{H}_{k}:=\mathsf{diag}(\sqrt{\hat{v}_{k,i}})$

9:
$\bm{\theta}_{k+1}:=\bm{\theta}_{k}-\alpha_{k}\mathsf{H}_{k}^{-1}\hat{\bm{m}}_{k}$

10: $k\leftarrow k+1$

11: end loop

The SGD optimizer under (C1)–(C3) is Algorithm 1 when $\beta_{1}=0$ and
$\mathsf{H}_{k}$ is the identity matrix. The Momentum optimizer under
(C1)–(C3) is Algorithm 1 when $\mathsf{H}_{k}$ is the identity matrix.

####  2.2.3 Assumptions

We assume the following conditions that were used in [10, Theorem 4.1]:

  1. (A1)

There exist positive numbers $G$ and $B$ such that, for all $k\in\mathbb{N}$,
$\|\nabla f(\bm{\theta}_{k})\|\leq G$ and $\|\nabla
f_{B_{k}}(\bm{\theta}_{k})\|\leq B$.

  2. (A2)

For all $\bm{\theta}\in\mathbb{R}^{d}$, there exists a positive number
$\mathrm{Dist}(\bm{\theta})$ such that, for all $k\in\mathbb{N}$,
$\|\bm{\theta}_{k}-\bm{\theta}\|\leq\mathrm{Dist}(\bm{\theta})$.

Let $(g_{k,i}^{2})_{i=1}^{d}:=\nabla f_{B_{k}}(\bm{\theta}_{k})\odot\nabla
f_{B_{k}}(\bm{\theta}_{k})$ $(k\in\mathbb{N})$. Assumption (A1) implies that
$M:=\sup\\{\max_{i\in[d]}g_{k,i}^{2}\colon k\in\mathbb{N}\\}<+\infty$.
Assumption (A2) implies that
$D(\bm{\theta}):=\sup\\{\max_{i\in[d]}(\theta_{k,i}-\theta_{i})^{2}\colon
k\in\mathbb{N}\\}<+\infty$. We define
$v_{*}:=\inf\\{\min_{i\in[d]}v_{k,i}\colon k\in\mathbb{N}\\}$. Theorem 3 in
[16] shows that there exists a stochastic convex optimization problem such
that Adam using $\beta_{1}<\sqrt{\beta_{2}}$ (e.g., $\beta_{1}=0.9$ and
$\beta_{2}=0.999$) does not converge to the optimal solution. If for all
$k\in\mathbb{N}$ and all $i\in[d]$, $v_{k,i}$ in Adam satisfies

$\displaystyle\hat{v}_{k+1,i}\geq\hat{v}_{k,i},$ (2.5)

then Adam (AMSGrad) with a decaying learning rate
$\alpha_{k}=\mathcal{O}(1/\sqrt{k})$ and $\beta_{1}$ and $\beta_{2}$
satisfying $\beta_{1}<\sqrt{\beta_{2}}$ can solve the stochastic convex
optimization problem [16, (2), Theorem 4]. We thus assume condition (2.5) for
Adam to guarantee the convergence of Adam.

##  3 Our Results

This section states our theoretical results (Theorem 3.1) in Table 1 and our
contribution (Sections 3.1 and 3.2) in detail. The proof of Theorem 3.1 is
given in Appendix A.

######  Theorem 3.1.

The sequence $(\bm{\theta}_{k})_{k\in\mathbb{N}}$ generated by each of SGD,
Momentum, and Adam with (2.5) under (C1)–(C3) and (A1) and (A2) satisfies the
following:

(i) [Upper bound of $\mathrm{VI}(K,\bm{\theta})$] For all $K\geq 1$ and all
$\bm{\theta}\in\mathbb{R}^{d}$,

$\displaystyle\mathrm{VI}(K,\bm{\theta}):=\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[\nabla
f(\bm{\theta}_{k})^{\top}(\bm{\theta}_{k}-\bm{\theta})\right]\leq\frac{C_{1}}{K}+\frac{C_{2}}{b}+C_{3},$

where $C_{i}$ $(i=1,2,3)$ for SGD are

$\displaystyle
C_{1}:=\frac{\mathbb{E}[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}]}{2\alpha},\text{
}C_{2}:=\frac{\sigma^{2}\alpha}{2},\text{ }C_{3}:=\frac{G^{2}\alpha}{2},$

$C_{i}$ $(i=1,2,3)$ for Momentum are

$\displaystyle
C_{1}:=\frac{\mathbb{E}[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}]}{2\alpha\beta_{1}},\text{
}C_{2}:=\frac{\sigma^{2}\alpha}{2\beta_{1}},$ $\displaystyle
C_{3}:=\frac{G^{2}\alpha}{2\beta_{1}}+\mathrm{Dist}(\bm{\theta})\left\\{\frac{G(1-\beta_{1})}{\beta_{1}}+2\sqrt{\sigma^{2}+G^{2}}\left(\frac{1}{\beta_{1}}+2(1-\beta_{1})\right)\right\\},$

$C_{i}$ $(i=1,2,3)$ for Adam with (2.5) are

$\displaystyle
C_{1}:=\frac{dD(\bm{\theta})\sqrt{M}}{2\alpha\beta_{1}\sqrt{1-\beta_{2}}},\text{
}C_{2}:=\frac{\sigma^{2}\alpha}{2\sqrt{v_{*}}\beta_{1}(1-\beta_{1})},$
$\displaystyle
C_{3}:=\frac{G^{2}\alpha}{2\sqrt{v_{*}}\beta_{1}(1-\beta_{1})}+\mathrm{Dist}(\bm{\theta})\left\\{\frac{G(1-\beta_{1})}{\beta_{1}}+2\sqrt{\sigma^{2}+G^{2}}\left(\frac{1}{\beta_{1}}+2(1-\beta_{1})\right)\right\\},$

and the parameters are defined as in Section 2.2.

(ii) [Steps to satisfy $\mathrm{VI}(K,\bm{\theta})\leq\epsilon$] The number of
steps $K$ defined by

$\displaystyle K(b)=\frac{C_{1}b}{(\epsilon-C_{3})b-C_{2}}$ (3.1)

satisfies $\mathrm{VI}(K,\bm{\theta})\leq\epsilon$ and the function $K(b)$
defined by (3.1) is convex and monotone decreasing with respect to batch size
$b$ $(>C_{2}/(\epsilon-C_{3})>0)$.

(iii) [Minimization of SFO complexity] The SFO complexity defined by

$\displaystyle K(b)b=\frac{C_{1}b^{2}}{(\epsilon-C_{3})b-C_{2}}$ (3.2)

is convex with respect to batch size $b$ $(>C_{2}/(\epsilon-C_{3})>0)$. The
batch size

$\displaystyle b^{\star}:=\frac{2C_{2}}{\epsilon-C_{3}}$ (3.3)

attains the minimum value

$\displaystyle K(b^{\star})b^{\star}=\frac{2C_{1}C_{2}}{(\epsilon-
C_{3})^{2}}\quad\text{of }K(b)b.$

###  3.1 Advantage of setting a small constant learning rate and
hyperparameters close to one

We first show theoretical evidence that Momentum and Adam using a small
constant learning rate $\alpha$, $\beta_{1}$ and $\beta_{2}$ close to $1$, and
a large number of steps $K$ perform well. Theorem 3.1(i) indicates that the
upper bound of $\mathrm{VI}(K,\bm{\theta})$ for Momentum is

$\displaystyle\mathrm{VI}(K,\bm{\theta})\leq\frac{\mathbb{E}[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}]}{2\alpha\beta_{1}K}+\frac{\sigma^{2}\alpha}{2\beta_{1}b}+\frac{G^{2}\alpha}{2\beta_{1}}+h(\beta_{1}),$
(3.4)

where $\beta_{1}\in(0,1)$ and

$\displaystyle
h(\beta_{1}):=\mathrm{Dist}(\bm{\theta})\left\\{\frac{G(1-\beta_{1})}{\beta_{1}}+2\sqrt{\sigma^{2}+G^{2}}\left(\frac{1}{\beta_{1}}+2(1-\beta_{1})\right)\right\\}.$
(3.5)

Since the function $h(\beta_{1})$ defined by (3.5) is monotone decreasing,
using $\beta_{1}$ close to $1$ makes $h(\beta_{1})$ small. Hence, using
$\beta_{1}$ close to $1$ makes the upper bound in (3.4) small. Moreover, using
a small learning rate $\alpha$ makes
$\sigma^{2}\alpha/(2\beta_{1}b)+G^{2}\alpha/(2\beta_{1})$ in (3.4) small.
Meanwhile, using a small learning rate $\alpha$ makes
$\mathbb{E}[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}]/(2\alpha\beta_{1}K)$ in (3.4)
large. Hence, we need to use a large $K$ to make
$\mathbb{E}[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}]/(2\alpha\beta_{1}K)$ in (3.4)
small. Theorem 3.1(i) indicates that the upper bound of
$\mathrm{VI}(K,\bm{\theta})$ for Adam is

$\displaystyle\mathrm{VI}(K,\bm{\theta})$
$\displaystyle\leq\frac{d{D}(\bm{\theta})\sqrt{M}}{2\alpha\beta_{1}\sqrt{1-\beta_{2}}K}+\frac{\alpha(\sigma^{2}b^{-1}+G^{2})}{2\sqrt{v_{*}}\beta_{1}(1-\beta_{1})K}\sum_{k=1}^{K}\sqrt{1-\beta_{2}^{k+1}}+h(\beta_{1})$
(3.6)
$\displaystyle\leq\frac{d{D}(\bm{\theta})\sqrt{M}}{2\alpha\beta_{1}\sqrt{1-\beta_{2}}K}+\frac{\sigma^{2}\alpha}{2\sqrt{v_{*}}\beta_{1}(1-\beta_{1})b}+\frac{G^{2}\alpha}{2\sqrt{v_{*}}\beta_{1}(1-\beta_{1})}+h(\beta_{1}),$
(3.7)

where $\beta_{1}\in(0,1)$ and $\beta_{2}\in[0,1)$ (while Theorem 3.1(i) shows
(3.7), the strict evaluation (3.6) comes from (A.18) in Appendix A). Using
$\beta_{1}$ close to $1$ makes $h(\beta_{1})$ small. Since
$1/(\beta_{1}(1-\beta_{1}))$ is monotone increasing for $\beta_{1}\geq 1/2$,
using $\beta_{1}$ close to $1$ makes $1/(\beta_{1}(1-\beta_{1}))$ large.
Hence, we need to set a small $\alpha$ to make
$\alpha(\sigma^{2}/b+G^{2})/(2\sqrt{v_{*}}\beta_{1}(1-\beta_{1}))$ small. The
function $\sqrt{1-\beta_{2}^{k+1}}$ is monotone decreasing with respect to
$\beta_{2}$, while using $\beta_{2}$ close to $1$ makes $1/\sqrt{1-\beta_{2}}$
large. When $\beta_{2}$ close to $1$ is used, we need to use a large $K$ to
make $d{D}(\bm{\theta})\sqrt{M}/(2\alpha\beta_{1}\sqrt{1-\beta_{2}}K)$ small.

###  3.2 Critical batch size

Here, we can see that the upper bound of $\mathrm{VI}(K,\bm{\theta})$ for SGD
is

$\displaystyle\mathrm{VI}(K,\bm{\theta})\leq\frac{\mathbb{E}[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}]}{2\alpha
K}+\frac{\sigma^{2}\alpha}{2b}+\frac{G^{2}\alpha}{2}.$ (3.8)

Compared with (3.4) and (3.7), it seems that, for a fixed small constant
learning rate $\alpha$ (e.g., $\alpha=10^{-3}$), SGD performs better than
Momentum and Adam in terms of the upper bound of $\mathrm{VI}(K,\bm{\theta})$.
Meanwhile, we can check that the upper bounds of $\mathrm{VI}(K,\bm{\theta})$
in (3.4), (3.7), and (3.8) are small when batch size $b$ is large.
Accordingly, we need to check carefully how to set batch sizes to improve
theoretical and practical performances of deep learning optimizers. Motivated
by the results in [19, 24] and Section 1.2.2, we use SFO complexity $Kb$ as
the performance measure of a deep learning optimizer.

Theorem 3.1(ii) indicates that the number of steps $K$ to satisfy
$\mathrm{VI}(K,\bm{\theta})\leq\epsilon$ can be expressed as (3.1). The
function $K(b)$ defined by (3.1) is convex and monotone decreasing. Hence, the
form of $K$ defined by (3.1) supports theoretically the relationship between
$K$ and $b$ shown in [19, 24] (see also Figures 2 and 4 in this paper).
Theorem 3.1(iii) indicates that SFO complexity defined by (3.2) is convex with
respect to batch size $b$. This result agrees with the fact of (1.1) (see also
Figures 2 and 4 in this paper). Moreover, SFO complexity $Kb$ is minimized at
$b^{\star}$ defined by (3.3); e.g., $b_{\mathrm{S}}^{\star}$ for SGD,
$b_{\mathrm{M}}^{\star}$ for Momentum, and $b_{\mathrm{A}}^{\star}$ for Adam
are respectively

$\displaystyle
b_{\mathrm{S}}^{\star}=\frac{\sigma_{\mathrm{S}}^{2}\alpha}{\epsilon-
C_{3,\mathrm{S}}},\text{
}b_{\mathrm{M}}^{\star}=\frac{\sigma_{\mathrm{M}}^{2}\alpha}{\beta_{1}(\epsilon-
C_{3,\mathrm{M}})},\text{
}b_{\mathrm{A}}^{\star}=\frac{\sigma_{\mathrm{A}}^{2}\alpha}{\sqrt{v_{*}}\beta_{1}(1-\beta_{1})(\epsilon-
C_{3,\mathrm{A}})},$ (3.9)

where $\sigma_{\mathrm{S}}$, $\sigma_{\mathrm{M}}$, and $\sigma_{\mathrm{A}}$
are positive constants depending on SGD, Momentum, and Adam and
$C_{3}=C_{3,\mathrm{S}},C_{3,\mathrm{M}},C_{3,\mathrm{A}}$ are positive
constants defined as in Theorem 3.1. From (3.9), the lower bounds $b^{*}$ of
$b_{\mathrm{S}}^{\star}$, $b_{\mathrm{M}}^{\star}$, and
$b_{\mathrm{A}}^{\star}$ are respectively

$\displaystyle
b_{\mathrm{S}}^{\star}>b_{\mathrm{S}}^{*}:=\frac{\sigma_{\mathrm{S}}^{2}\alpha}{\epsilon},\text{
}b_{\mathrm{M}}^{\star}>b_{\mathrm{M}}^{*}:=\frac{\sigma_{\mathrm{M}}^{2}\alpha}{\beta_{1}\epsilon},\text{
}b_{\mathrm{A}}^{\star}>b_{\mathrm{A}}^{*}:=\frac{\sigma_{\mathrm{A}}^{2}\alpha}{\sqrt{v_{*}}\beta_{1}(1-\beta_{1})\epsilon}.$

If $\sigma_{\mathrm{S}}=\sigma_{\mathrm{M}}=\sigma_{\mathrm{A}}$, $\alpha$ and
$\beta_{1}$ are fixed (e.g., $\alpha=10^{-3}$ and $\beta_{1}=0.9$), and
$\sqrt{v_{*}}(1-\beta_{1})<1$ (e.g., $0.1\sqrt{v_{*}}<1$ when
$\beta_{1}=0.9$), then

$\displaystyle
b_{\mathrm{S}}^{*}:=\frac{\sigma_{\mathrm{S}}^{2}\alpha}{\epsilon}<b_{\mathrm{M}}^{*}:=\frac{\sigma_{\mathrm{M}}^{2}\alpha}{\beta_{1}\epsilon}<b_{\mathrm{A}}^{*}:=\frac{\sigma_{\mathrm{A}}^{2}\alpha}{\sqrt{v_{*}}\beta_{1}(1-\beta_{1})\epsilon}.$
(3.10)

Hence, $b_{\mathrm{A}}^{*}$ is larger than $b_{\mathrm{S}}^{*}$ and
$b_{\mathrm{M}}^{*}$. Section 4 discusses estimation of appropriate batch
sizes in detail.

##  4 Numerical Results

We evaluated the performances of SGD, Momentum, and Adam with different batch
sizes. The metrics were the number of steps $K$ and the SFO complexity $Kb$
satisfying $f(\bm{\theta}_{K})\leq 10^{-1}$, where $\bm{\theta}_{K}$ is
generated for each of SGD, Momentum, and Adam using batch size $b$. The
stopping condition was $200$ epochs. The experimental environment consisted of
two Intel(R) Xeon(R) Gold 6148 2.4-GHz CPUs with 20 cores each, a 16-GB NVIDIA
Tesla V100 900-Gbps GPU, and the Red Hat Enterprise Linux 7.6 OS. The code was
written in Python 3.8.2 using the NumPy 1.17.3 and PyTorch 1.3.0 packages. A
constant learning rate $\alpha=10^{-3}$ was commonly used. Momentum used
$\beta_{1}=0.9$. Adam used $\beta_{1}=0.9$ and $\beta_{2}=0.999$ [10].

Here, we use (3.10) and estimate appropriate batch sizes in the sense that SFO
complexity is minimized. The definitions of $v_{*}$ and $v_{k,i}$ (see also
(A.13) in Appendix A) imply that, for $k\in[K]$ and all $i\in[d]$, $v_{*}\leq
v_{k,i}\leq\max_{k\in[K]}\max_{i\in[d]}g_{k,i}^{2}=:g_{k^{*},i^{*}}^{2}\leq\sum_{i=1}^{d}g_{k^{*},i}^{2}=\|\nabla
f_{B_{k^{*}}}(\bm{\theta}_{k^{*}})\|^{2}$. Condition (C2)(2.3) implies that
$\mathbb{E}[\|\nabla
f_{B_{k}}(\bm{\theta}_{k})\|^{2}]\leq\sigma^{2}/b+\mathbb{E}[\|\nabla
f(\bm{\theta}_{k})\|^{2}]$ (see also (A.2) in Appendix A). Conditions
(C2)(2.4) and (C3) imply that, if $b$ is large, then $\sigma$ is small. Hence,
assuming that $\sigma^{2}/b\approx 0$ implies that $v_{*}\leq\|\nabla
f(\bm{\theta}_{k^{*}})\|^{2}=\|(1/n)\sum_{i\in[n]}\nabla\ell_{i}(\bm{\theta}_{k^{*}})\|^{2}=(1/n^{2})\|\sum_{i\in[n]}\nabla\ell_{i}(\bm{\theta}_{k^{*}})\|^{2}=:(1/n^{2})\|\bm{G}_{k^{*}}\|^{2}=(1/n^{2})\sum_{i\in[d]}G_{k^{*},i}^{2}\leq(d/n^{2})\max_{i\in[d]}G_{k^{*},i}^{2}$.
Since deep learning optimizers can approximate stationary points of $f$, we
assume that, for example, $G_{k^{*},i}\approx\epsilon$. Then, (3.10) implies
that

$\displaystyle
b_{\mathrm{S}}^{*}:=\frac{\sigma_{\mathrm{S}}^{2}}{10^{3}\epsilon},\text{
}b_{\mathrm{M}}^{*}:=\frac{\sigma_{\mathrm{M}}^{2}}{9\cdot
10^{2}\epsilon},\text{
}b_{\mathrm{A}}^{*}:=\frac{\sigma_{\mathrm{A}}^{2}}{9\cdot
10\sqrt{v_{*}}\epsilon}>\frac{\sigma_{\mathrm{A}}^{2}n}{9\cdot
10\sqrt{d}\epsilon^{2}}.$ (4.1)

Conditions (C2)(2.4) and (C3) imply that, if $b$ is large, then $\sigma$ is
small. If SGD and Momentum can exploit large batch sizes, then
$\sigma_{\mathrm{S}}$ and $\sigma_{\mathrm{M}}$ are small. However, (4.1)
implies that $b_{\mathrm{S}}^{*}$ and $b_{\mathrm{M}}^{*}$ must be small when
$\sigma_{\mathrm{S}}$ and $\sigma_{\mathrm{M}}$ are small. Accordingly, SGD
and Momentum would not be able to use large batch sizes. Meanwhile, from
(4.1), we expect that Adam can exploit a large batch size
$b_{\mathrm{A}}^{\star}>b_{\mathrm{A}}^{*}$, for example, when
$b_{\mathrm{A}}^{*}<2^{10}$ (CIFAR-10; $b_{\mathrm{A}}^{*}\approx 1010$,
$d=3072$, $n=50000$) and $2^{11}<b_{\mathrm{A}}^{*}<2^{12}$ (MNIST;
$b_{\mathrm{A}}^{*}\approx 2380$, $d=784$, $n=60000$), where
$\sigma_{\mathrm{A}}^{2}\approx 10^{-2}$ and $\epsilon\approx 10^{-2}$ are
used.

###  4.1 ResNet-20 on the CIFAR-10 dataset

Figure 1: Number of steps for SGD, Momentum, and Adam versus batch size needed to train ResNet-20 on CIFAR-10. There is an initial period of perfect scaling (indicated by dashed line) such that the number of steps $K$ for Adam is inversely proportional to batch size $b$. Adam has critical batch size $b^{\star}=2^{11}$. |  Figure 2: SFO complexities for SGD, Momentum, and Adam versus batch size needed to train ResNet-20 on CIFAR-10. SFO complexity of Adam (resp. Momentum) is minimized at critical batch size $b^{\star}=2^{11}$ (resp. $b^{\star}=2^{3}$), whereas SFO complexity for SGD tends to increase with batch size.
---|---

Let us consider training ResNet-20 on the CIFAR-10 dataset with $n=50000$.
Figure 2 shows the number of steps for SGD, Momentum, and Adam versus batch
size. For SGD and Momentum, the number of steps $K$ needed for
$f(\bm{\theta}_{K})\leq 10^{-1}$ initially decreased. However, SGD with $b\geq
2^{6}$ and Momentum with $b\geq 2^{10}$ did not satisfy
$f(\bm{\theta}_{K})\leq 10^{-1}$ before the stopping condition was reached.
Adam had an initial period of perfect scaling (indicated by dashed line) such
that the number of steps $K$ needed for $f(\bm{\theta}_{K})\leq 10^{-1}$ was
inversely proportional to batch size $b$, and critical batch size
$b^{\star}=2^{11}$ such that $K$ was not inversely proportional to the batch
size beyond $b^{\star}$; i.e., there were diminishing returns.

Figure 2 plots the SFO complexities for SGD, Momentum, and Adam versus batch
size. For SGD, SFO complexity was minimum at $b^{\star}=2^{2}$; for Momentum,
it was minimum at $b^{\star}=2^{3}$. This implies that SGD and Momentum could
not use large batch sizes, as shown in (4.1). For Adam, SFO complexity was
minimum at the critical batch size $b^{\star}=2^{11}$ that was close to
estimation of critical batch $b_{\mathrm{A}}^{\star}>b_{\mathrm{A}}^{*}$ with
$b_{\mathrm{A}}^{*}<2^{10}$, as shown in (4.1). We also checked that the
elapsed time for Adam monotonically decreased for $b\leq 2^{11}$ and that the
elapsed time for critical batch size $b^{\star}=2^{11}$ was the shortest. The
elapsed time for $b\geq 2^{12}$ increased with the SFO complexity, as shown in
Figure 2 (see Tables 2, 3, 4, and 5 in Appendix A).

###  4.2 ResNet-18 on the MNIST dataset

Figure 3: Number of steps for SGD, Momentum, and Adam versus batch size needed to train ResNet-18 on MNIST. There is an initial period of perfect scaling (indicated by dashed line) such that the number of steps $K$ for Adam is inversely proportional to batch size $b$. Adam has critical batch size $b^{\star}=2^{10}$. |  Figure 4: SFO complexities for SGD, Momentum, and Adam versus batch size needed to train ResNet-18 on MNIST. SFO complexity of Adam (resp. Momentum) is minimized at critical batch size $b^{\star}=2^{10}$ (resp. $b^{\star}=2^{3}$), whereas SFO complexity for SGD tends to increase with batch size.
---|---

Let us consider training ResNet-18 on the MNIST dataset with $n=60000$.
Figures 4 and 4 indicate that Adam could exploit larger batch sizes than SGD
and Momentum. Moreover, these figures indicate that Momentum minimized SFO
complexity at the critical batch size $b^{\star}=2^{3}$ and Adam minimized SFO
complexity at the critical batch size $b^{\star}=2^{10}$ that was close to
estimation of critical batch $b_{\mathrm{A}}^{\star}>b_{\mathrm{A}}^{*}$ with
$2^{11}<b_{\mathrm{A}}^{*}<2^{12}$, as shown in (4.1). We can also check that
the elapsed time for critical batch size $b^{\star}=2^{10}$ was the shortest
(see Tables 6, 7, 8, and 9 in Appendix A).

##  5 Conclusion and Future Work

This paper showed the relationship between batch size $b$ and the number of
steps $K$ to achieve an $\epsilon$-approximation of deep learning optimizers
using a small constant learning rate $\alpha$ and hyperparameters $\beta_{1}$
and $\beta_{2}$ close to $1$. From the convexity of SFO complexity $Kb$, there
exists a global minimizer $b^{\star}$ of $Kb$ that is the critical batch size.
We also gave numerical results indicating that Adam using a small constant
learning rate, hyperparameters close to one, and the critical batch size
minimizing SFO complexity has faster convergence than Momentum and SGD.
Moreover, we estimated appropriate batch sizes from our formula for
$b^{\star}$ and showed that actual critical batch sizes are close to estimated
batch sizes.

This paper focused on the theoretical analyses of SGD, Momentum, and Adam. In
the future, we should consider developing theoretical analyses of Adam’s
variants, such as Yogi, AMSGrad, AdaBelief, and AdamW.

## References

  * [1] Chen, H., Zheng, L., AL Kontar, R., Raskutti, G.: Stochastic gradient descent in correlated settings: A study on Gaussian processes.  In: Advances in Neural Information Processing Systems, vol. 33 (2020)
  * [2] Chen, J., Zhou, D., Tang, Y., Yang, Z., Cao, Y., Gu, Q.: Closing the generalization gap of adaptive gradient methods in training deep neural network.  In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, vol. 452, pp. 3267–3275 (2021)
  * [3] Chen, X., Liu, S., Sun, R., Hong, M.: On the convergence of a class of Adam-type algorithms for non-convex optimization.  In: Proceedings of The International Conference on Learning Representations (2019)
  * [4] Duchi, J., Hazan, E., Singer, Y.: Adaptive subgradient methods for online learning and stochastic optimization.  Journal of Machine Learning Research 12, 2121–2159 (2011)
  * [5] Fehrman, B., Gess, B., Jentzen, A.: Convergence rates for the stochastic gradient descent method for non-convex objective functions.  Journal of Machine Learning Research 21, 1–48 (2020)
  * [6] Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: A generic algorithmic framework.  SIAM Journal on Optimization 22, 1469–1492 (2012)
  * [7] Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization II: Shrinking procedures and optimal algorithms.  SIAM Journal on Optimization 23, 2061–2089 (2013)
  * [8] Horn, R.A., Johnson, C.R.: Matrix Analysis.  Cambridge University Press, Cambridge (1985)
  * [9] Iiduka, H.: Appropriate learning rates of adaptive learning rate optimization algorithms for training deep neural networks.  IEEE Transactions on Cybernetics DOI: 10.1109/TCYB.2021.3107415 (2021)
  * [10] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization.  In: Proceedings of The International Conference on Learning Representations (2015)
  * [11] Loizou, N., Vaswani, S., Laradji, I., Lacoste-Julien, S.: Stochastic polyak step-size for SGD: An adaptive learning rate for fast convergence.  In: Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, vol. 130 (2021)
  * [12] Loshchilov, I., Hutter, F.: Decoupled weight decay regularization.  In: International Conference on Learning Representations (2019)
  * [13] Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming.  SIAM Journal on Optimization 19, 1574–1609 (2009)
  * [14] Nesterov, Y.: A method for unconstrained convex minimization problem with the rate of convergence ${O}(1/k^{2})$.  Doklady AN USSR 269, 543–547 (1983)
  * [15] Polyak, B.T.: Some methods of speeding up the convergence of iteration methods.  USSR Computational Mathematics and Mathematical Physics 4, 1–17 (1964)
  * [16] Reddi, S.J., Kale, S., Kumar, S.: On the convergence of Adam and beyond.  In: Proceedings of The International Conference on Learning Representations (2018)
  * [17] Robbins, H., Monro, H.: A stochastic approximation method.  The Annals of Mathematical Statistics 22, 400–407 (1951)
  * [18] Scaman, K., Malherbe, C.: Robustness analysis of non-convex stochastic gradient descent using biased expectations.  In: Advances in Neural Information Processing Systems, vol. 33 (2020)
  * [19] Shallue, C.J., Lee, J., Antognini, J., Sohl-Dickstein, J., Frostig, R., Dahl, G.E.: Measuring the effects of data parallelism on neural network training.  Journal of Machine Learning Research 20, 1–49 (2019)
  * [20] Smith, S.L., Kindermans, P.J., Le, Q.V.: Don’t decay the learning rate, increase the batch size.  In: Proceedings of The International Conference on Learning Representations (2018)
  * [21] Tieleman, T., Hinton, G.: RMSProp: Divide the gradient by a running average of its recent magnitude.  COURSERA: Neural networks for machine learning 4, 26–31 (2012)
  * [22] Virmaux, A., Scaman, K.: Lipschitz regularity of deep neural networks: analysis and efficient estimation.  In: Advances in Neural Information Processing Systems, vol. 31 (2018)
  * [23] Zaheer, M., Reddi, S., Sachan, D., Kale, S., Kumar, S.: Adaptive methods for nonconvex optimization.  In: S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett (eds.) Advances in Neural Information Processing Systems, vol. 31. Curran Associates, Inc. (2018)
  * [24] Zhang, G., Li, L., Nado, Z., Martens, J., Sachdeva, S., Dahl, G.E., Shallue, C.J., Grosse, R.: Which algorithmic choices matter at which batch sizes? Insights from a noisy quadratic model.  In: Advances in Neural Information Processing Systems, vol. 32 (2019)
  * [25] Zhou, D., Chen, J., Cao, Y., Tang, Y., Yang, Z., Gu, Q.: On the convergence of adaptive gradient methods for nonconvex optimization.  In: 12th Annual Workshop on Optimization for Machine Learning (2020)
  * [26] Zhuang, J., Tang, T., Ding, Y., Tatikonda, S., Dvornek, N., Papademetris, X., Duncan, J.S.: AdaBelief optimizer: Adapting stepsizes by the belief in observed gradients.  In: Advances in Neural Information Processing Systems, vol. 33 (2020)
  * [27] Zinkevich, M.: Online convex programming and generalized infinitesimal gradient ascent.  In: Proceedings of the 20th International Conference on Machine Learning, pp. 928–936 (2003)
  * [28] Zou, F., Shen, L., Jie, Z., Zhang Weizhong, W.L.: A sufficient condition for convergences of Adam and RMSProp.  In: Computer Vision and Pattern Recognition Conference, pp. 11,127–11,135 (2019)

##  Appendix A Appendix

Unless stated otherwise, all relationships between random variables are
supposed to hold almost surely. Let $S$ be a positive definite matrix, which
is denoted by $S\in\mathbb{S}_{++}^{d}$. The $S$-inner product of
$\mathbb{R}^{d}$ is defined for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$ by
$\langle\bm{x},\bm{y}\rangle_{S}:=\langle\bm{x},S\bm{y}\rangle=\bm{x}^{\top}(S\bm{y})$,
and the $S$-norm is defined by
$\|\bm{x}\|_{S}:=\sqrt{\langle\bm{x},S\bm{x}\rangle}$.

###  A.1 Lemmas

######  Lemma A.1.

Suppose that (C1), (C2)(2.3), and (C3) hold. Then, Adam satisfies the
following: for all $k\in\mathbb{N}$ and all $\bm{\theta}\in\mathbb{R}^{d}$,

$\displaystyle\mathbb{E}\left[\left\|\bm{\theta}_{k+1}-\bm{\theta}\right\|_{\mathsf{H}_{k}}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|\bm{\theta}_{k}-\bm{\theta}\right\|_{\mathsf{H}_{k}}^{2}\right]+\alpha^{2}\mathbb{E}\left[\left\|\bm{\mathsf{d}}_{k}\right\|_{\mathsf{H}_{k}}^{2}\right]$
$\displaystyle\quad+2\alpha\left\\{\frac{\beta_{1}}{\tilde{\beta}_{1k}}\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\bm{m}_{k-1}\right]+\frac{\hat{\beta}_{1}}{\tilde{\beta}_{1k}}\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\nabla
f(\bm{\theta}_{k})\right]\right\\},$

where $\bm{\mathsf{d}}_{k}:=-\mathsf{H}_{k}^{-1}\hat{\bm{m}}_{k}$,
$\hat{\beta}_{1}:=1-\beta_{1}$, and $\tilde{\beta}_{1k}:=1-\beta_{1}^{k+1}$.

###### Proof.

Let $\bm{\theta}\in\mathbb{R}^{d}$ and $k\in\mathbb{N}$. The definition
$\bm{\theta}_{k+1}:=\bm{\theta}_{k}+\alpha\bm{\mathsf{d}}_{k}$ implies that

$\displaystyle\|\bm{\theta}_{k+1}-\bm{\theta}\|_{\mathsf{H}_{k}}^{2}=\|\bm{\theta}_{k}-\bm{\theta}\|_{\mathsf{H}_{k}}^{2}+2\alpha\langle\bm{\theta}_{k}-\bm{\theta},\bm{\mathsf{d}}_{k}\rangle_{\mathsf{H}_{k}}+\alpha^{2}\|\bm{\mathsf{d}}_{k}\|_{\mathsf{H}_{k}}^{2}.$

Moreover, the definitions of $\bm{\mathsf{d}}_{k}$, $\bm{m}_{k}$, and
$\hat{\bm{m}}_{k}$ ensure that

$\displaystyle\left\langle\bm{\theta}_{k}-\bm{\theta},\bm{\mathsf{d}}_{k}\right\rangle_{\mathsf{H}_{k}}$
$\displaystyle=\left\langle\bm{\theta}_{k}-\bm{\theta},\mathsf{H}_{k}\bm{\mathsf{d}}_{k}\right\rangle=\left\langle\bm{\theta}-\bm{\theta}_{k},\hat{\bm{m}}_{k}\right\rangle=\frac{1}{\tilde{\beta}_{1k}}(\bm{\theta}-\bm{\theta}_{k})^{\top}{\bm{m}}_{k}$
$\displaystyle=\frac{\beta_{1}}{\tilde{\beta}_{1k}}(\bm{\theta}-\bm{\theta}_{k})^{\top}\bm{m}_{k-1}+\frac{\hat{\beta}_{1}}{\tilde{\beta}_{1k}}(\bm{\theta}-\bm{\theta}_{k})^{\top}\nabla
f_{B_{k}}(\bm{\theta}_{k}).$

Hence,

$\displaystyle\begin{split}\left\|\bm{\theta}_{k+1}-\bm{\theta}\right\|_{\mathsf{H}_{k}}^{2}&=\left\|\bm{\theta}_{k}-\bm{\theta}\right\|_{\mathsf{H}_{k}}^{2}+\alpha^{2}\left\|\bm{\mathsf{d}}_{k}\right\|_{\mathsf{H}_{k}}^{2}\\\
&\quad+2\alpha\left\\{\frac{\beta_{1}}{\tilde{\beta}_{1k}}(\bm{\theta}-\bm{\theta}_{k})^{\top}\bm{m}_{k-1}+\frac{\hat{\beta}_{1}}{\tilde{\beta}_{1k}}(\bm{\theta}-\bm{\theta}_{k})^{\top}\nabla
f_{B_{k}}(\bm{\theta}_{k})\right\\}.\end{split}$ (A.1)

Conditions (2.3) and (C3) guarantee that

$\displaystyle\mathbb{E}\left[\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\nabla
f_{B_{k}}(\bm{\theta}_{k})\Big{|}\bm{\theta}_{k}\right]\right]=\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\mathbb{E}\left[\nabla
f_{B_{k}}(\bm{\theta}_{k})\Big{|}\bm{\theta}_{k}\right]\right]=\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\nabla
f(\bm{\theta}_{k})\right].$

Therefore, the lemma follows from taking the expectation on both sides of
(A.1). This completes the proof. ∎

The discussion in the proof of Lemma A.1 also gives the following lemma.

######  Lemma A.2.

Suppose that (C1), (C2)(2.3), and (C3) hold. Then, SGD satisfies the
following: for all $k\in\mathbb{N}$ and all $\bm{\theta}\in\mathbb{R}^{d}$,

$\displaystyle\mathbb{E}\left[\left\|\bm{\theta}_{k+1}-\bm{\theta}\right\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|\bm{\theta}_{k}-\bm{\theta}\right\|^{2}\right]+\alpha^{2}\mathbb{E}\left[\left\|\nabla
f_{B_{k}}(\bm{\theta}_{k})\right\|^{2}\right]+2\alpha\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\nabla
f(\bm{\theta}_{k})\right].$

Moreover, Momentum satisfies the following: for all $k\in\mathbb{N}$ and all
$\bm{\theta}\in\mathbb{R}^{d}$,

$\displaystyle\mathbb{E}\left[\left\|\bm{\theta}_{k+1}-\bm{\theta}\right\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|\bm{\theta}_{k}-\bm{\theta}\right\|^{2}\right]+\alpha^{2}\mathbb{E}\left[\left\|\bm{m}_{k}\right\|^{2}\right]$
$\displaystyle\quad+2\alpha\left\\{\beta_{1}\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\bm{m}_{k-1}\right]+\hat{\beta}_{1}\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\nabla
f(\bm{\theta}_{k})\right]\right\\},$

where $\hat{\beta}_{1}:=1-\beta_{1}$.

The following lemma indicates the bounds on
$(\mathbb{E}[\|\bm{m}_{k}\|^{2}])_{k\in\mathbb{N}}$ and
$(\mathbb{E}[\|\bm{\mathsf{d}}_{k}\|_{\mathsf{H}_{k}}^{2}])_{k\in\mathbb{N}}$.

######  Lemma A.3.

Adam under (C2)(2.3), (2.4), and (A1), for all $k\in\mathbb{N}$ satisfies

$\displaystyle\mathbb{E}\left[\left\|\bm{m}_{k}\right\|^{2}\right]\leq\frac{\sigma^{2}}{b}+G^{2},\quad\mathbb{E}\left[\left\|\bm{\mathsf{d}}_{k}\right\|_{\mathsf{H}_{k}}^{2}\right]\leq\frac{\sqrt{\tilde{\beta}_{2k}}}{\tilde{\beta}_{1k}^{2}\sqrt{{v}_{*}}}\left(\frac{\sigma^{2}}{b}+G^{2}\right),$

where ${v}_{*}:=\inf\\{\min_{i\in[d]}{v}_{k,i}\colon k\in\mathbb{N}\\}$,
$\tilde{\beta}_{1k}:=1-\beta_{1k}^{k+1}$, and
$\tilde{\beta}_{2k}:=1-\beta_{2k}^{k+1}$.

###### Proof.

Condition (C2)(2.3) implies that

$\displaystyle\begin{split}\mathbb{E}\left[\left\|\nabla
f_{B_{k}}(\bm{\theta}_{k})\right\|^{2}\Big{|}\bm{\theta}_{k}\right]&=\mathbb{E}\left[\left\|\nabla
f_{B_{k}}(\bm{\theta}_{k})-\nabla f(\bm{\theta}_{k})+\nabla
f(\bm{\theta}_{k})\right\|^{2}\Big{|}\bm{\theta}_{k}\right]\\\
&=\mathbb{E}\left[\left\|\nabla f_{B_{k}}(\bm{\theta}_{k})-\nabla
f(\bm{\theta}_{k})\right\|^{2}\Big{|}\bm{\theta}_{k}\right]+\mathbb{E}\left[\left\|\nabla
f(\bm{\theta}_{k})\right\|^{2}\Big{|}\bm{\theta}_{k}\right]\\\
&\quad+2\mathbb{E}\left[(\nabla f_{B_{k}}(\bm{\theta}_{k})-\nabla
f(\bm{\theta}_{k}))^{\top}\nabla
f(\bm{\theta}_{k})\Big{|}\bm{\theta}_{k}\right]\\\
&=\mathbb{E}\left[\left\|\nabla f_{B_{k}}(\bm{\theta}_{k})-\nabla
f(\bm{\theta}_{k})\right\|^{2}\Big{|}\bm{\theta}_{k}\right]+\|\nabla
f(\bm{\theta}_{k})\|^{2},\end{split}$ (A.2)

which, together with (C2)(2.4) and (A1), in turn implies that

$\displaystyle\mathbb{E}\left[\left\|\nabla
f_{B_{k}}(\bm{\theta}_{k})\right\|^{2}\right]\leq\frac{\sigma^{2}}{b}+G^{2}.$
(A.3)

The convexity of $\|\cdot\|^{2}$, together with the definition of $\bm{m}_{k}$
and (A.3), guarantees that, for all $k\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\left\|\bm{m}_{k}\right\|^{2}\right]$
$\displaystyle\leq\beta_{1}\mathbb{E}\left[\left\|\bm{m}_{k-1}\right\|^{2}\right]+\hat{\beta}_{1}\mathbb{E}\left[\left\|\nabla
f_{B_{k}}(\bm{\theta}_{k})\right\|^{2}\right]$
$\displaystyle\leq\beta_{1}\mathbb{E}\left[\left\|\bm{m}_{k-1}\right\|^{2}\right]+\hat{\beta}_{1}\left(\frac{\sigma^{2}}{b}+G^{2}\right).$

Induction thus ensures that, for all $k\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\left\|\bm{m}_{k}\right\|^{2}\right]\leq\max\left\\{\|\bm{m}_{-1}\|^{2},\frac{\sigma^{2}}{b}+G^{2}\right\\}=\frac{\sigma^{2}}{b}+G^{2},$
(A.4)

where $\bm{m}_{-1}=\bm{0}$. For $k\in\mathbb{N}$,
$\mathsf{H}_{k}\in\mathbb{S}_{++}^{d}$ guarantees the existence of a unique
matrix $\overline{\mathsf{H}}_{k}\in\mathbb{S}_{++}^{d}$ such that
$\mathsf{H}_{k}=\overline{\mathsf{H}}_{k}^{2}$ [8, Theorem 7.2.6]. We have
that, for all $\bm{x}\in\mathbb{R}^{d}$,
$\|\bm{x}\|_{\mathsf{H}_{k}}^{2}=\|\overline{\mathsf{H}}_{k}\bm{x}\|^{2}$.
Accordingly, the definitions of $\bm{\mathsf{d}}_{k}$ and $\hat{\bm{m}}_{k}$
imply that, for all $k\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\left\|\bm{\mathsf{d}}_{k}\right\|_{\mathsf{H}_{k}}^{2}\right]=\mathbb{E}\left[\left\|\overline{\mathsf{H}}_{k}^{-1}\mathsf{H}_{k}\bm{\mathsf{d}}_{k}\right\|^{2}\right]\leq\frac{1}{\tilde{\beta}_{1k}^{2}}\mathbb{E}\left[\left\|\overline{\mathsf{H}}_{k}^{-1}\right\|^{2}\|\bm{m}_{k}\|^{2}\right],$

where

$\displaystyle\left\|\overline{\mathsf{H}}_{k}^{-1}\right\|=\left\|\mathsf{diag}\left(\hat{v}_{k,i}^{-\frac{1}{4}}\right)\right\|=\max_{i\in[d]}\hat{v}_{k,i}^{-\frac{1}{4}}=\max_{i\in[d]}\left(\frac{v_{k,i}}{\tilde{\beta}_{2k}}\right)^{-\frac{1}{4}}=:\left(\frac{v_{k,i^{*}}}{\tilde{\beta}_{2k}}\right)^{-\frac{1}{4}}.$

Moreover, the definition of

$\displaystyle{v}_{*}:=\inf\left\\{{v}_{k,i^{*}}\colon
k\in\mathbb{N}\right\\}$

and (A.4) imply that, for all $k\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\left\|\bm{\mathsf{d}}_{k}\right\|_{\mathsf{H}_{k}}^{2}\right]\leq\frac{\tilde{\beta}_{2k}^{\frac{1}{2}}}{\tilde{\beta}_{1k}^{2}{v}_{*}^{\frac{1}{2}}}\left(\frac{\sigma^{2}}{b}+G^{2}\right),$

completing the proof. ∎

###  A.2 SGD

We show Theorem 3.1 for SGD.

###### Proof.

(i) Lemma A.2 and (A.3) imply that, for all $k\in\mathbb{N}$ and all
$\bm{\theta}\in\mathbb{R}^{d}$,

$\displaystyle
2\alpha\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\nabla
f(\bm{\theta}_{k})\right]$
$\displaystyle=\mathbb{E}\left[\left\|\bm{\theta}_{k}-\bm{\theta}\right\|^{2}\right]-\mathbb{E}\left[\left\|\bm{\theta}_{k+1}-\bm{\theta}\right\|^{2}\right]+\alpha^{2}\mathbb{E}\left[\left\|\nabla
f_{B_{k}}(\bm{\theta}_{k})\right\|^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\left\|\bm{\theta}_{k}-\bm{\theta}\right\|^{2}\right]-\mathbb{E}\left[\left\|\bm{\theta}_{k+1}-\bm{\theta}\right\|^{2}\right]+\alpha^{2}\left(\frac{\sigma^{2}}{b}+G^{2}\right).$

Summing the above inequality from $k=1$ to $k=K$ leads to the finding that,
for all $K\geq 1$,

$\displaystyle
2\alpha\sum_{k=1}^{K}\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\nabla
f(\bm{\theta}_{k})\right]\leq\mathbb{E}\left[\left\|\bm{\theta}_{1}-\bm{\theta}\right\|^{2}\right]-\mathbb{E}\left[\left\|\bm{\theta}_{K+1}-\bm{\theta}\right\|^{2}\right]+\alpha^{2}\left(\frac{\sigma^{2}}{b}+G^{2}\right)K,$

which implies that, for all $K\geq 1$ and all $\bm{\theta}\in\mathbb{R}^{d}$,

$\displaystyle\begin{split}\mathrm{VI}(K,\bm{\theta})&:=\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\nabla
f(\bm{\theta}_{k})\right]\leq\frac{\mathbb{E}\left[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}\right]}{2\alpha
K}+\frac{\alpha}{2}\left(\frac{\sigma^{2}}{b}+G^{2}\right)\\\
&=\underbrace{\frac{\mathbb{E}\left[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}\right]}{2\alpha}}_{C_{1}}\frac{1}{K}+\underbrace{\frac{\sigma^{2}\alpha}{2}}_{C_{2}}\frac{1}{b}+\underbrace{\frac{G^{2}\alpha}{2}}_{C_{3}}.\end{split}$
(A.5)

(ii) Let $\bm{\theta}\in\mathbb{R}^{d}$ and $\epsilon>0$. Condition
$C_{1}/K+C_{2}/b+C_{3}=\epsilon$ is equivalent to

$\displaystyle K=K(b)=\frac{C_{1}b}{(\epsilon-C_{3})b-C_{2}}.$ (A.6)

Since $\epsilon=C_{1}/K+C_{2}/b+C_{3}>C_{3}$, we consider the case
$b>C_{2}/(\epsilon-C_{3})>0$ to guarantee that $K>0$. From (A.5), the function
$K$ defined by (A.6) satisfies $\mathrm{VI}(K,\bm{\theta})\leq
C_{1}/K+C_{2}/b+C_{3}=\epsilon$. Moreover, from (A.6),

$\displaystyle\frac{\mathrm{d}K(b)}{\mathrm{d}b}=\frac{-C_{1}C_{2}}{\\{(\epsilon-
C_{3})b-C_{2}\\}^{2}}\leq 0,\text{
}\frac{\mathrm{d}^{2}K(b)}{\mathrm{d}b^{2}}=\frac{2C_{1}C_{2}(\epsilon-
C_{3})}{\\{(\epsilon-C_{3})b-C_{2}\\}^{3}}\geq 0,$

which implies that $K$ is convex and monotone decreasing with respect to $b$.

(iii) We have that

$\displaystyle Kb=K(b)b=\frac{C_{1}b^{2}}{(\epsilon-C_{3})b-C_{2}}.$

Accordingly,

$\displaystyle\frac{\mathrm{d}K(b)b}{\mathrm{d}b}=\frac{C_{1}b\\{(\epsilon-
C_{3})b-2C_{2}\\}}{\\{(\epsilon-C_{3})b-C_{2}\\}^{2}},\text{
}\frac{\mathrm{d}^{2}K(b)b}{\mathrm{d}b^{2}}=\frac{2C_{1}C_{2}^{2}}{\\{(\epsilon-
C_{3})b-C_{2}\\}^{3}}\geq 0,$

which implies that $K(b)b$ is convex with respect to $b$ and

$\displaystyle\frac{\mathrm{d}K(b)b}{\mathrm{d}b}\begin{cases}<0&\text{ if
}b<b^{\star},\\\ =0&\text{ if }b=b^{\star}=\frac{2C_{2}}{\epsilon-C_{3}},\\\
>0&\text{ if }b>b^{\star}.\end{cases}$

The point $b^{\star}$ attains the minimum value
$K(b^{\star})b^{\star}=2C_{1}C_{2}/(\epsilon-C_{3})^{2}$ of $K(b)b$. This
completes the proof. ∎

###  A.3 Momentum

We show Theorem 3.1 for Momentum.

###### Proof.

(i) Lemma A.2 ensures that, for all $k\in\mathbb{N}$ and all
$\bm{\theta}\in\mathbb{R}^{d}$,

$\displaystyle\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k-1}\right]$
$\displaystyle=\frac{1}{2\alpha\beta_{1}}\left\\{\mathbb{E}\left[\left\|\bm{\theta}_{k}-\bm{\theta}\right\|^{2}\right]-\mathbb{E}\left[\left\|\bm{\theta}_{k+1}-\bm{\theta}\right\|^{2}\right]\right\\}+\frac{\alpha}{2\beta_{1}}\mathbb{E}\left[\left\|\bm{m}_{k}\right\|^{2}\right]$
$\displaystyle\quad+\frac{\hat{\beta}_{1}}{\beta_{1}}\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\nabla
f(\bm{\theta}_{k})\right],$

which, together with Lemma A.3, the Cauchy–Schwarz inequality, and (A1) and
(A2), implies that

$\displaystyle\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k-1}\right]$
$\displaystyle\leq\frac{1}{2\alpha\beta_{1}}\left\\{\mathbb{E}\left[\left\|\bm{\theta}_{k}-\bm{\theta}\right\|^{2}\right]-\mathbb{E}\left[\left\|\bm{\theta}_{k+1}-\bm{\theta}\right\|^{2}\right]\right\\}+\frac{\alpha}{2\beta_{1}}\left(\frac{\sigma^{2}}{b}+G^{2}\right)$
$\displaystyle\quad+\frac{\hat{\beta}_{1}}{\beta_{1}}\mathrm{Dist}(\bm{\theta})G.$

Summing the above inequality from $k=1$ to $k=K$ gives a relation that implies
that

$\displaystyle\sum_{k=1}^{K}\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k-1}\right]$
$\displaystyle\leq\frac{1}{2\alpha\beta_{1}}\left\\{\mathbb{E}\left[\left\|\bm{\theta}_{1}-\bm{\theta}\right\|^{2}\right]-\mathbb{E}\left[\left\|\bm{\theta}_{K+1}-\bm{\theta}\right\|^{2}\right]\right\\}+\frac{\alpha}{2\beta_{1}}\left(\frac{\sigma^{2}}{b}+G^{2}\right)K$
$\displaystyle\quad+\frac{\hat{\beta}_{1}}{\beta_{1}}\mathrm{Dist}(\bm{\theta})GK,$

and hence,

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k-1}\right]\leq\frac{\mathbb{E}\left[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}\right]}{2\alpha\beta_{1}K}+\frac{\alpha}{2\beta_{1}}\left(\frac{\sigma^{2}}{b}+G^{2}\right)+\frac{\hat{\beta}_{1}}{\beta_{1}}\mathrm{Dist}(\bm{\theta})G.$

Moreover, we have that, for all $k\in\mathbb{N}$ and all
$\bm{\theta}\in\mathbb{R}^{d}$,

$\displaystyle(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k}$
$\displaystyle=(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k-1}+\hat{\beta}_{1}(\bm{\theta}_{k}-\bm{\theta})^{\top}(\nabla
f_{B_{k}}(\bm{\theta}_{k})-\bm{m}_{k-1})$
$\displaystyle\leq(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k-1}+\hat{\beta}_{1}\mathrm{Dist}(\bm{\theta})\left(\|\nabla
f_{B_{k}}(\bm{\theta}_{k})\|+\|\bm{m}_{k-1}\|\right),$

where the first equality comes from the definition of $\bm{m}_{k}$ and the
first inequality comes from the Cauchy–Schwarz inequality, the triangle
inequality, and (A2). Hence, from Lemma A.3, (A.3), Jensen’s inequality, and
$b\geq 1$,

$\displaystyle\begin{split}\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k}\right]&\leq(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k-1}+2\hat{\beta}_{1}\mathrm{Dist}(\bm{\theta})\sqrt{\frac{\sigma^{2}}{b}+G^{2}}\\\
&\leq(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k-1}+2\hat{\beta}_{1}\mathrm{Dist}(\bm{\theta})\sqrt{\sigma^{2}+G^{2}}.\end{split}$
(A.7)

Therefore, for all $K\geq 1$ and all $\bm{\theta}\in\mathbb{R}^{d}$,

$\displaystyle\begin{split}&\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k}\right]\\\
&\leq\frac{\mathbb{E}\left[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}\right]}{2\alpha\beta_{1}K}+\frac{\sigma^{2}\alpha}{2\beta_{1}b}+\frac{G^{2}\alpha}{2\beta_{1}}+\hat{\beta}_{1}\mathrm{Dist}(\bm{\theta})\left(\frac{G}{\beta_{1}}+2\sqrt{\sigma^{2}+G^{2}}\right).\end{split}$
(A.8)

The definition of $\bm{m}_{k}$ ensures that

$\displaystyle(\bm{\theta}_{k}-\bm{\theta})^{\top}\nabla
f_{B_{k}}(\bm{\theta}_{k})$
$\displaystyle=(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k}+(\bm{\theta}_{k}-\bm{\theta})^{\top}(\nabla
f_{B_{k}}(\bm{\theta}_{k})-\bm{m}_{k-1})+(\bm{\theta}_{k}-\bm{\theta})^{\top}(\bm{m}_{k-1}-\bm{m}_{k})$
$\displaystyle=(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k}+\frac{1}{\beta_{1}}(\bm{\theta}_{k}-\bm{\theta})^{\top}(\nabla
f_{B_{k}}(\bm{\theta}_{k})-\bm{m}_{k})+\hat{\beta}_{1}(\bm{\theta}_{k}-\bm{\theta})^{\top}(\bm{m}_{k-1}-\nabla
f_{B_{k}}(\bm{\theta}_{k})),$

which, together with the Cauchy–Schwarz inequality, the triangle inequality,
and (A2), implies that

$\displaystyle(\bm{\theta}_{k}-\bm{\theta})^{\top}\nabla
f_{B_{k}}(\bm{\theta}_{k})$
$\displaystyle\leq(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k}+\frac{1}{\beta_{1}}\mathrm{Dist}(\bm{\theta})(\|\nabla
f_{B_{k}}(\bm{\theta}_{k})\|+\|\bm{m}_{k}\|)+\hat{\beta}_{1}\mathrm{Dist}(\bm{\theta})(\|\nabla
f_{B_{k}}(\bm{\theta}_{k})\|+\|\bm{m}_{k-1}\|).$

Lemma A.3, (A.3), Jensen’s inequality, and $b\geq 1$ guarantee that

$\displaystyle\begin{split}\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\nabla
f(\bm{\theta}_{k})\right]&\leq\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k}\right]+2\left(\frac{1}{\beta_{1}}+\hat{\beta}_{1}\right)\mathrm{Dist}(\bm{\theta})\sqrt{\frac{\sigma^{2}}{b}+G^{2}}\\\
&\leq\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k}\right]+2\left(\frac{1}{\beta_{1}}+\hat{\beta}_{1}\right)\mathrm{Dist}(\bm{\theta})\sqrt{\sigma^{2}+G^{2}}.\end{split}$
(A.9)

Therefore, (A.8) ensures that, for all $K\geq 1$ and all
$\bm{\theta}\in\mathbb{R}^{d}$,

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\nabla
f(\bm{\theta}_{k})\right]$
$\displaystyle\leq\underbrace{\frac{\mathbb{E}\left[\|\bm{\theta}_{1}-\bm{\theta}\|^{2}\right]}{2\alpha\beta_{1}}}_{C_{1}}\frac{1}{K}+\underbrace{\frac{\sigma^{2}\alpha}{2\beta_{1}}}_{C_{2}}\frac{1}{b}+\underbrace{\frac{G^{2}\alpha}{2\beta_{1}}+\mathrm{Dist}(\bm{\theta})\left\\{\frac{G\hat{\beta}_{1}}{\beta_{1}}+2\sqrt{\sigma^{2}+G^{2}}\left(\frac{1}{\beta_{1}}+2\hat{\beta}_{1}\right)\right\\}}_{C_{3}}.$

(ii) A discussion similar to the one showing (ii) in Theorem 3.1 for SGD would
show (ii) in Theorem 3.1 for Momentum.

(iii) An argument similar to that which obtained (iii) in Theorem 3.1 for SGD
would prove (iii) in Theorem 3.1 for Momentum. ∎

###  A.4 Adam

We show Theorem 3.1 for Adam.

###### Proof.

(i) Let $\bm{\theta}\in\mathbb{R}^{d}$. Lemma A.1 guarantees that for all
$k\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k-1}\right]$
$\displaystyle=\underbrace{\frac{\tilde{\beta}_{1k}}{2\alpha\beta_{1}}\left\\{\mathbb{E}\left[\left\|\bm{\theta}_{k}-\bm{\theta}\right\|_{\mathsf{H}_{k}}^{2}\right]-\mathbb{E}\left[\left\|\bm{\theta}_{k+1}-\bm{\theta}\right\|_{\mathsf{H}_{k}}^{2}\right]\right\\}}_{a_{k}}+\underbrace{\frac{\alpha\tilde{\beta}_{1k}}{2\beta_{1}}\mathbb{E}\left[\left\|\bm{\mathsf{d}}_{k}\right\|_{\mathsf{H}_{k}}^{2}\right]}_{b_{k}}$
$\displaystyle\quad+\underbrace{\frac{\hat{\beta}_{1}}{\beta_{1}}\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\nabla
f(\bm{\theta}_{k})\right]}_{c_{k}}.$ (A.10)

We define $\gamma_{k}:=\tilde{\beta}_{1k}/(2\beta_{1}\alpha)$
$(k\in\mathbb{N})$. Then, for all $K\geq 1$,

$\displaystyle\begin{split}\sum_{k=1}^{K}a_{k}&=\gamma_{1}\mathbb{E}\left[\left\|\bm{\theta}_{1}-\bm{\theta}\right\|_{\mathsf{H}_{1}}^{2}\right]+\underbrace{\sum_{k=2}^{K}\left\\{\gamma_{k}\mathbb{E}\left[\left\|\bm{\theta}_{k}-\bm{\theta}\right\|_{\mathsf{H}_{k}}^{2}\right]-\gamma_{k-1}\mathbb{E}\left[\left\|\bm{\theta}_{k}-\bm{\theta}\right\|_{\mathsf{H}_{k-1}}^{2}\right]\right\\}}_{{\Gamma}_{K}}\\\
&\quad-\gamma_{K}\mathbb{E}\left[\left\|\bm{\theta}_{K+1}-\bm{\theta}\right\|_{\mathsf{H}_{K}}^{2}\right].\end{split}$
(A.11)

Since $\overline{\mathsf{H}}_{k}\in\mathbb{S}_{++}^{d}$ exists such that
$\mathsf{H}_{k}=\overline{\mathsf{H}}_{k}^{2}$, we have
$\|\bm{x}\|_{\mathsf{H}_{k}}^{2}=\|\overline{\mathsf{H}}_{k}\bm{x}\|^{2}$ for
all $\bm{x}\in\mathbb{R}^{d}$. Accordingly, we also have

$\displaystyle{\Gamma}_{K}=\mathbb{E}\left[\sum_{k=2}^{K}\left\\{\gamma_{k}\left\|\overline{\mathsf{H}}_{k}(\bm{\theta}_{k}-\bm{\theta})\right\|^{2}-\gamma_{k-1}\left\|\overline{\mathsf{H}}_{k-1}(\bm{\theta}_{k}-\bm{\theta})\right\|^{2}\right\\}\right].$

From $\overline{\mathsf{H}}_{k}=\mathsf{diag}(\hat{v}_{k,i}^{1/4})$, we have
that, for all $\bm{x}=(x_{i})_{i=1}^{d}\in\mathbb{R}^{d}$,
$\|\overline{\mathsf{H}}_{k}\bm{x}\|^{2}=\sum_{i=1}^{d}\sqrt{\hat{v}_{k,i}}x_{i}^{2}$.
Hence, for all $K\geq 2$,

$\displaystyle{\Gamma}_{K}=\mathbb{E}\left[\sum_{k=2}^{K}\sum_{i=1}^{d}\left(\gamma_{k}\sqrt{\hat{v}_{k,i}}-\gamma_{k-1}\sqrt{\hat{v}_{k-1,i}}\right)(\theta_{k,i}-\theta_{i})^{2}\right].$
(A.12)

Condition (2.5) and $\gamma_{k}\geq\gamma_{k-1}$ ($k\geq 1$) imply that, for
all $k\geq 1$ and all $i\in[d]$,

$\displaystyle\gamma_{k}\sqrt{\hat{v}_{k,i}}-\gamma_{k-1}\sqrt{\hat{v}_{k-1,i}}\geq
0.$

Moreover, (A2) ensures that
$D(\bm{\theta}):=\sup\\{\max_{i\in[d]}(\theta_{k,i}-\theta_{i})^{2}\colon
k\in\mathbb{N}\\}<+\infty$. Accordingly, for all $K\geq 2$,

$\displaystyle{\Gamma}_{K}\leq
D(\bm{\theta})\mathbb{E}\left[\sum_{k=2}^{K}\sum_{i=1}^{d}\left(\gamma_{k}\sqrt{\hat{v}_{k,i}}-\gamma_{k-1}\sqrt{\hat{v}_{k-1,i}}\right)\right]=D(\bm{\theta})\mathbb{E}\left[\sum_{i=1}^{d}\left(\gamma_{K}\sqrt{\hat{v}_{K,i}}-\gamma_{1}\sqrt{\hat{v}_{1,i}}\right)\right].$

Let $\nabla f_{B_{k}}(\bm{\theta}_{k})\odot\nabla
f_{B_{k}}(\bm{\theta}_{k}):=(g_{k,i}^{2})\in\mathbb{R}_{+}^{d}$. Assumption
(A1) ensures that there exists $M\in\mathbb{R}$ such that, for all
$k\in\mathbb{N}$, $\max_{i\in[d]}g_{k,i}^{2}\leq M$. The definition of
${\bm{v}}_{k}$ guarantees that, for all $i\in[d]$ and all $k\in\mathbb{N}$,

$\displaystyle v_{k,i}=\beta_{2}v_{k-1,i}+\hat{\beta}_{2}g_{k,i}^{2}.$

Induction thus ensures that, for all $i\in[d]$ and all $k\in\mathbb{N}$,

$\displaystyle v_{k,i}\leq\max\\{v_{0,i},M\\}=M,$ (A.13)

where $\bm{v}_{0}=(v_{0,i})=\bm{0}$. From the definition of
$\hat{\bm{v}}_{k}$, we have that, for all $i\in[d]$ and all $k\in\mathbb{N}$,

$\displaystyle\hat{v}_{k,i}=\frac{v_{k,i}}{\tilde{\beta}_{2k}}\leq\frac{M}{\tilde{\beta}_{2k}}.$
(A.14)

Therefore, (A.11),
$\mathbb{E}[\|\bm{\theta}_{1}-\bm{\theta}\|_{\mathsf{H}_{1}}^{2}]\leq
D(\bm{\theta})\mathbb{E}[\sum_{i=1}^{d}\sqrt{\hat{v}_{1,i}}]$, and (A.14)
imply, for all $K\geq 1$,

$\displaystyle\begin{split}\sum_{k=1}^{K}a_{k}&\leq\gamma_{1}D(\bm{\theta})\mathbb{E}\left[\sum_{i=1}^{d}\sqrt{\hat{v}_{1,i}}\right]+D(\bm{\theta})\mathbb{E}\left[\sum_{i=1}^{d}\left(\gamma_{K}\sqrt{\hat{v}_{K,i}}-\gamma_{1}\sqrt{\hat{v}_{1,i}}\right)\right]\\\
&=\gamma_{K}D(\bm{\theta})\mathbb{E}\left[\sum_{i=1}^{d}\sqrt{\hat{v}_{K,i}}\right]\\\
&\leq{\gamma}_{K}D(\bm{\theta})\sum_{i=1}^{d}\sqrt{\frac{M}{\tilde{\beta}_{2K}}}\\\
&\leq\frac{dD(\bm{\theta})\sqrt{M}\tilde{\beta}_{1K}}{2\beta_{1}\alpha\sqrt{\tilde{\beta}_{2K}}}.\end{split}$
(A.15)

Inequality (A.15) with $\tilde{\beta}_{1K}:=1-\beta_{1}^{K+1}\leq 1$ and
$\tilde{\beta}_{2K}:=1-\beta_{2}^{K+1}\geq 1-\beta_{2}=:\hat{\beta}_{2}$
implies that

$\displaystyle\sum_{k=1}^{K}a_{k}\leq\frac{dD(\bm{\theta})\sqrt{M}\tilde{\beta}_{1K}}{2\beta_{1}\alpha\sqrt{\tilde{\beta}_{2K}}}\leq\frac{dD(\bm{\theta})\sqrt{M}}{2\beta_{1}\alpha\sqrt{\hat{\beta}_{2}}}.$
(A.16)

Lemma A.3 guarantees that, for all $k\in\mathbb{N}$,

$\displaystyle
b_{k}=\frac{\alpha\tilde{\beta}_{1k}}{2\beta_{1}}\mathbb{E}\left[\left\|\bm{\mathsf{d}}_{k}\right\|_{\mathsf{H}_{k}}^{2}\right]\leq\frac{\alpha\tilde{\beta}_{1k}}{2\beta_{1}}\frac{\sqrt{\tilde{\beta}_{2k}}}{\tilde{\beta}_{1k}^{2}\sqrt{{v}_{*}}}\left(\frac{\sigma^{2}}{b}+G^{2}\right)=\frac{\alpha\sqrt{\tilde{\beta}_{2k}}}{2\sqrt{v_{*}}\beta_{1}\tilde{\beta}_{1k}}\left(\frac{\sigma^{2}}{b}+G^{2}\right).$
(A.17)

Inequality (A.17) with $\tilde{\beta}_{1k}:=1-\beta_{1}^{k+1}\geq
1-\beta_{1}=:\hat{\beta}_{1}$ and $\tilde{\beta}_{2k}:=1-\beta_{2}^{k+1}\leq
1$ implies that

$\displaystyle
b_{k}\leq\frac{\alpha\sqrt{\tilde{\beta}_{2k}}}{2\sqrt{v_{*}}\beta_{1}\tilde{\beta}_{1k}}\left(\frac{\sigma^{2}}{b}+G^{2}\right)\leq\frac{\alpha}{2\sqrt{v_{*}}\beta_{1}\hat{\beta}_{1}}\left(\frac{\sigma^{2}}{b}+G^{2}\right).$
(A.18)

The Cauchy–Schwarz inequality and (A2) imply that, for all $k\in\mathbb{N}$,

$\displaystyle
c_{k}=\frac{\hat{\beta}_{1}}{\beta_{1}}\mathbb{E}\left[(\bm{\theta}-\bm{\theta}_{k})^{\top}\nabla
f(\bm{\theta}_{k})\right]\leq\mathrm{Dist}(\bm{\theta})G\frac{\hat{\beta}_{1}}{\beta_{1}}.$
(A.19)

Hence, (A.10), (A.16), (A.18), and (A.19) ensure that, for all $K\geq 1$,

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\bm{m}_{k-1}\right]\leq\frac{dD(\bm{\theta})\sqrt{M}}{2\beta_{1}\alpha\sqrt{\hat{\beta}_{2}}K}+\frac{\alpha(\sigma^{2}b^{-1}+G^{2})}{2\sqrt{v_{*}}\beta_{1}\hat{\beta}_{1}}+\mathrm{Dist}(\bm{\theta})G\frac{\hat{\beta}_{1}}{\beta_{1}}.$

Therefore, from (A.7) and (A.9), for all $K\geq 1$,

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[(\bm{\theta}_{k}-\bm{\theta})^{\top}\nabla
f(\bm{\theta}_{k})\right]$
$\displaystyle\leq\underbrace{\frac{dD(\bm{\theta})\sqrt{M}}{2\alpha\beta_{1}\sqrt{\hat{\beta}_{2}}}}_{C_{1}}\frac{1}{K}+\underbrace{\frac{\sigma^{2}\alpha}{2\sqrt{v_{*}}\beta_{1}\hat{\beta}_{1}}}_{C_{2}}\frac{1}{b}+\underbrace{\frac{G^{2}\alpha}{2\sqrt{v_{*}}\beta_{1}\hat{\beta}_{1}}+\mathrm{Dist}(\bm{\theta})\left\\{\frac{G\hat{\beta}_{1}}{\beta_{1}}+2\sqrt{\sigma^{2}+G^{2}}\left(\frac{1}{\beta_{1}}+2\hat{\beta}_{1}\right)\right\\}}_{C_{3}}.$

(ii) A discussion similar to the one showing (ii) in Theorem 3.1 for SGD would
show (ii) in Theorem 3.1 for Adam.

(iii) An argument similar to that which obtained (iii) in Theorem 3.1 for SGD
would prove (iii) in Theorem 3.1 for Adam. ∎

###  A.5 Additional numerical results

Table 2: Elapsed time and training accuracy of SGD when
$f(\bm{\theta}_{K})\leq 10^{-1}$ for training ResNet-20 on CIFAR-10 SGD
---
Batch Size | $2^{2}$ | $2^{3}$ | $2^{4}$ | $2^{5}$ | $2^{6}$ | $2^{7}$ | $2^{8}$ | $2^{9}$
Time (s) | 16983.64 | 9103.76 | 6176.19 | 3759.25 | — | — | — | —
Accuracy (%) | 96.75 | 96.69 | 96.66 | 96.88 | — | — | — | —
Table 3: Elapsed time and training accuracy of Momentum when
$f(\bm{\theta}_{K})\leq 10^{-1}$ for training ResNet-20 on CIFAR-10 Momentum
---
Batch Size | $2^{2}$ | $2^{3}$ | $2^{4}$ | $2^{5}$ | $2^{6}$ | $2^{7}$ | $2^{8}$ | $2^{9}$
Time (s) | 7978.90 | 3837.72 | 2520.82 | 1458.70 | 887.01 | 678.66 | 625.10 | 866.65
Accuracy (%) | 96.49 | 96.79 | 96.51 | 96.72 | 96.70 | 96.94 | 96.94 | 98.34
Table 4: Elapsed time and training accuracy of Adam when
$f(\bm{\theta}_{K})\leq 10^{-1}$ for training ResNet-20 on CIFAR-10 Adam
---
Batch Size | $2^{2}$ | $2^{3}$ | $2^{4}$ | $2^{5}$ | $2^{6}$ | $2^{7}$ | $2^{8}$ | $2^{9}$
Time (s) | 10601.78 | 4405.73 | 2410.28 | 1314.01 | 617.14 | 487.75 | 281.74 | 225.03
Accuracy (%) | 96.46 | 96.38 | 96.65 | 96.53 | 96.43 | 96.68 | 96.58 | 96.72
Table 5: Elapsed time and training accuracy of Adam when
$f(\bm{\theta}_{K})\leq 10^{-1}$ for training ResNet-20 on CIFAR-10 Adam
---
Batch Size | $2^{10}$ | $\mathbf{2^{11}}$ | $2^{12}$ | $2^{13}$ | $2^{14}$ | $2^{15}$ | $2^{16}$
Time (s) | 197.78 | 195.40 | 233.70 | 349.81 | 691.04 | 644.19 | 1148.68
Accuracy (%) | 96.74 | 97.21 | 97.54 | 97.75 | 97.51 | 99.05 | 99.03
Table 6: Elapsed time and training accuracy of SGD when
$f(\bm{\theta}_{K})\leq 10^{-1}$ for training ResNet-18 on MNIST SGD
---
Batch Size | $2^{2}$ | $2^{3}$ | $2^{4}$ | $2^{5}$ | $2^{6}$ | $2^{7}$ | $2^{8}$ | $2^{9}$
Time (s) | 1620.98 | 1002.89 | 1140.47 | 1298.52 | — | — | — | —
Accuracy (%) | 99.70 | 99.69 | 99.70 | 99.70 | — | — | — | —
Table 7: Elapsed time and training accuracy of Momentum when
$f(\bm{\theta}_{K})\leq 10^{-1}$ for training ResNet-18 on MNIST Momentum
---
Batch Size | $2^{2}$ | $2^{3}$ | $2^{4}$ | $2^{5}$ | $2^{6}$ | $2^{7}$ | $2^{8}$ | $2^{9}$
Time (s) | 1949.66 | 550.28 | 298.72 | 238.66 | 268.98 | 362.89 | 567.54 | —
Accuracy (%) | 99.68 | 99.65 | 99.68 | 99.69 | 99.71 | 99.70 | 99.72 | —
Table 8: Elapsed time and training accuracy of Adam when
$f(\bm{\theta}_{K})\leq 10^{-1}$ for training ResNet-18 on MNIST Adam
---
Batch Size | $2^{2}$ | $2^{3}$ | $2^{4}$ | $2^{5}$ | $2^{6}$ | $2^{7}$ | $2^{8}$ | $2^{9}$
Time (s) | — | 7514.43 | 614.27 | 297.97 | 216.10 | 160.93 | 127.97 | 102.98
Accuracy (%) | — | 99.74 | 99.66 | 99.64 | 99.66 | 99.66 | 99.69 | 99.71
Table 9: Elapsed time and training accuracy of Adam when
$f(\bm{\theta}_{K})\leq 10^{-1}$ for training ResNet-18 on MNIST Adam
---
Batch Size | $\mathbf{2^{10}}$ | $2^{11}$ | $2^{12}$ | $2^{13}$ | $2^{14}$
Time (s) | 93.53 | 100.22 | 129.29 | 217.23 | 375.87
Accuracy (%) | 99.68 | 99.67 | 99.67 | 99.70 | 99.69