Increasing Both Batch Size and Learning Rate Accelerates Stochastic Gradient Descent

## Abstract

Abstract The performance of mini-batch stochastic gradient descent (SGD) strongly depends on setting the batch size and learning rate to minimize the empirical loss in training the deep neural network.
In this paper, we present theoretical analyses of mini-batch SGD with four schedulers:
(i) constant batch size and decaying learning rate scheduler,
(ii) increasing batch size and decaying learning rate scheduler,
(iii) increasing batch size and increasing learning rate scheduler,
and
(iv) increasing batch size and warm-up decaying learning rate scheduler.
We show that mini-batch SGD using scheduler (i) does not always minimize the expectation of the full gradient norm of the empirical loss, whereas it does using any of schedulers (ii), (iii), and (iv).
Furthermore, schedulers (iii) and (iv) accelerate mini-batch SGD.
The paper also provides numerical results of supporting analyses showing that using scheduler (iii) or (iv) minimizes the full gradient norm of the empirical loss faster than using scheduler (i) or (ii).

## 1 Introduction

Mini-batch stochastic gradient descent (SGD) (Robbins & Monro, ; Zinkevich, ; Nemirovski et al., ; Ghadimi & Lan, ; )
is a simple and useful deep-learning optimizer for finding appropriate parameters of a deep neural network (DNN) in the sense of minimizing the empirical loss defined by the mean of nonconvex loss functions corresponding to the training set.

The performance of mini-batch SGD strongly depends on how the batch size and learning rate are set.
In particular, increasing batch size (Byrd et al., ; Balles et al., ; De et al., ; Smith et al., ; Goyal et al., ; Shallue et al., ; Zhang et al., ) is useful for training DNNs with mini-batch SGD.
In (Smith et al., ), it was numerically shown that using an enormous batch size leads to a reduction
in the number of parameter updates.

Decaying a learning rate
(Wu et al., ; Ioffe & Szegedy, ; Loshchilov & Hutter, ; Hundt et al., ) is also useful for training DNNs with mini-batch SGD.
In (Chen et al., ), theoretical results indicated that running SGD with a diminishing learning rate $\eta_{t}=O(1/t)$ and a large batch size for sufficiently many steps leads to convergence
to a stationary point.
A practical example of a decaying learning rate
with $\eta_{t+1}\leq\eta_{t}$ for all $t\in\mathbb{N}$
is a constant learning rate $\eta_{t}=\eta>0$ for all $t\in\mathbb{N}$.
However, convergence of SGD with a constant learning rate is not guaranteed (Scaman & Malherbe, ).
Other practical learning rates have been presented for training DNNs, including cosine annealing (Loshchilov & Hutter, ), cosine power annealing (Hundt et al., ), step decay (Lu, ), exponential decay (Wu et al., ), polynomial decay (Chen et al., ), and linear decay (Liu et al., ).

Contribution:
The main contribution of the present paper is its theoretical analyses of mini-batch SGD with batch size and learning rate schedulers used in practice satisfying the following inequality:

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|\right]\leq\bigg{\{}\frac{2(f(\bm{\theta}_{0})-f^{\star})}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}}_{B_{T}}+\frac{L_{n}\sigma^{2}}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}}_{V_{T}}\bigg{\}}^{\frac{1}{2}},$ $$

where $f$ is the empirical loss for $n$ training samples having $L_{n}$-Lipschitz continuous gradient $\nabla f$ and lower bound $f^{\star}$,
$\sigma^{2}$ is an upper bound on the variance of the mini-batch stochastic gradient,
and
$(\bm{\theta}_{t})_{t=0}^{T-1}$ is the sequence generated by mini-batch SGD with batch size $b_{t}$, learning rate $\eta_{t}\in[\eta_{\min},\eta_{\max}]\subset[0,\frac{2}{L_{n}})$, and total number of steps to train a DNN $T$.

| Scheduler | $B_{T}$ | $V_{T}$ | $O(\sqrt{B_{T}+V_{T}})$ |
| --- | --- | --- | --- |
| Case (i) (Theorem [3.1](#S3.Thmtheorem1); Section [3.1](#S3.SS1)) | $\displaystyle{\frac{H_{1}}{T}}$ | $\displaystyle{\frac{H_{2}}{b}+\frac{H_{7}}{bT}}$ | $\displaystyle{O\left(\sqrt{\frac{1}{T}+\frac{1}{b}}\right)}$ |
| $b_{t}\colon$Constant; $\eta_{t}\colon$Decay |  |  |  |
| Case (ii) (Theorem [3.2](#S3.Thmtheorem2); Section [3.2](#S3.SS2)) | $\displaystyle{\frac{H_{3}}{T}}$ | $\displaystyle{\frac{H_{4}}{b_{0}T}}$ | $\displaystyle{O\left(\frac{1}{\sqrt{T}}\right),\text{ }O\left(\frac{1}{\sqrt{M}}\right)}$ |
| $b_{t}\colon$Increase; $\eta_{t}\colon$Decay |  |  |  |
| Case (iii) (Theorem [3.3](#S3.Thmtheorem3); Section [3.3](#S3.SS3)) | $\displaystyle{\frac{H_{5}}{\gamma^{M}}}$ | $\displaystyle{\frac{H_{6}}{b_{0}\gamma^{M}}}$ | $\displaystyle{O\left(\frac{1}{\gamma^{\frac{M}{2}}}\right)}$ Remark: |
| $b_{t}\colon$Increase; $\eta_{t}\colon$Increase | $\frac{1}{\gamma^{\frac{M}{2}}}<\frac{1}{\sqrt{M}}$ |  |  |
| Case (iv) (Theorem [3.4](#S3.Thmtheorem4); Section [3.4](#S3.SS4)) | $\displaystyle{\frac{H_{5}}{\gamma^{M}}\to\frac{H_{3}}{T}}$ | $\displaystyle{\frac{H_{6}}{b_{0}\gamma^{M}}\to\frac{H_{4}}{b_{0}T}}$ | $\displaystyle{O\left(\frac{1}{\gamma^{\frac{M}{2}}}\right)\to O\left(\frac{1}{\sqrt{T}}\right)}$ |
| $b_{t}\colon$Increase; $\eta_{t}\colon$Increase $\to$ Decay |  |  |  |

$H_{i}$ ($i\in[6]$) (resp. $H_{7}$) is a positive (resp. nonnegative) number depending on $\eta_{\min}$ and $\eta_{\max}$.
$\gamma$ and $\delta$ are such that $1<\gamma^{2}<\delta$
(e.g., $\delta=2$ when batch size is doubly increasing every $E$ epochs).
The total number of steps when batch size increases $M$ times is $T(M)=\sum_{m=0}^{M}\lceil\frac{n}{b_{m}}\rceil E\geq ME$.

(i) Using constant batch size $b_{t}=b$ and decaying learning rate $\eta_{t}$ (Theorem [3.1](#S3.Thmtheorem1); Section [3.1](#S3.SS1)):
Using a constant batch size and practical decaying learning rates, such as constant, cosine-annealing, and polynomial decay learning rates, satisfies that, for a sufficiently large step $T$, the upper bound on
$\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla f(\bm{\theta}_{t})\|]$ becomes approximately $O(\frac{1}{\sqrt{b}})>0$, which implies that mini-batch SGD does not always converge to a stationary point of $f$.
Meanwhile, the analysis indicates that using the cosine-annealing and polynomial decay learning rates decreases $\mathbb{E}[\|\nabla f(\bm{\theta}_{t})\|]$ faster than using a constant learning rate (see ([7](#S3.E7))), which is supported by the numerical results in Figure [1](#S4.F1).

(ii) Using increasing batch size $b_{t}$ and decaying learning rate $\eta_{t}$ (Theorem [3.2](#S3.Thmtheorem2); Section [3.2](#S3.SS2)):
Although convergence analyses of SGD
were presented in (Vaswani et al., ; Fehrman et al., ; Scaman & Malherbe, ; Loizou et al., ; Wang et al., ; Khaled & Richtárik, ),
providing the theoretical performance of mini-batch SGD with increasing batch sizes that have been used in practice may not be sufficient.
The present paper shows that mini-batch SGD has an $O(\frac{1}{\sqrt{T}})$ rate of convergence.
Increasing batch size every $E$ epochs makes the polynomial decay and linear learning rates
become small at an early stage of training (Figure [2](#S4.F2)(a)).
Meanwhile, the cosine-annealing and constant learning rates are robust to increasing batch sizes (Figure [2](#S4.F2)(a)).
Hence, it is desirable for mini-batch SGD using increasing batch sizes to use the cosine-annealing and constant learning rates, which is supported by the numerical results in Figure [2](#S4.F2).

(iii) Using increasing batch size $b_{t}$ and increasing learning rate $\eta_{t}$ (Theorem [3.3](#S3.Thmtheorem3); Section [3.3](#S3.SS3)):
From Case (ii), when batch sizes increase, keeping learning rates large is useful for training DNNs.
Hence, we are interested in verifying whether mini-batch SGD with both the batch sizes and learning rates increasing can train DNNs.
Let us consider a scheduler doubly increasing batch size (i.e., $\delta=2$).
We set $\gamma>1$ such that $\gamma<\sqrt{\delta}=\sqrt{2}$ and we set an increasing learning rate scheduler such that the learning rate is multiplied by $\gamma$ every $E$ epochs
(Figure [3](#S4.F3)(a)).
This paper shows that, when batch size increases $M$ times, mini-batch SGD has an $O(\gamma^{-\frac{M}{2}})$ convergence rate
that is better than the $O(\frac{1}{\sqrt{M}})$ convergence rate in Case (ii).
That is, increasing both batch size and learning rate accelerates mini-batch SGD.
We give practical results (Figure [3](#S4.F3)(b); $\delta=2$ and Figure [5](#S4.F5)(b); $\delta=3,4$) such that Case (iii) decreases $\|\nabla f(\bm{\theta}_{t})\|$ faster than Case (ii) and tripling
and quadrupling batch sizes ($\delta=3,4$) decrease $\|\nabla f(\bm{\theta}_{t})\|$ faster than doubly increasing batch sizes ($\delta=2$).

(iv) Using increasing batch size $b_{t}$ and warm-up decaying learning rate $\eta_{t}$ (Theorem [3.4](#S3.Thmtheorem4); Section [3.4](#S3.SS4)):
One way to guarantee fast convergence of mini-batch SGD with increasing batch sizes is to increase learning rates (acceleration period; Case (iii)) during the first epochs and then decay the learning rates (convergence period; Case (ii)), that is, to use a decaying learning rate with warm-up (He et al., ; Vaswani et al., ; Goyal et al., ; Gotmare et al., ; He et al., ).
We give numerical results (Figure [4](#S4.F4)) indicating that using mini-batch SGD with increasing batch sizes and decaying learning rates with a warm-up minimizes $\|\nabla f(\bm{\theta}_{t})\|$ faster than using a constant learning rate in Case (ii) or increasing learning rates in Case (iii).

## 2 Mini-batch SGD for empirical risk minimization

### 2.1 Empirical risk minimization

Let $\bm{\theta}\in\mathbb{R}^{d}$ be a parameter of a deep neural network; let $S=\{(\bm{x}_{1},\bm{y}_{1}),\ldots,(\bm{x}_{n},\bm{y}_{n})\}$ be the training set, where data point $\bm{x}_{i}$ is associated with label $\bm{y}_{i}$; and let $f_{i}(\cdot):=f(\cdot;(\bm{x}_{i},\bm{y}_{i}))\colon\mathbb{R}^{d}\to\mathbb{R}_{+}$ be the loss function corresponding to the $i$-th labeled training data $(\bm{x}_{i},\bm{y}_{i})$. Empirical risk minimization (ERM) minimizes the empirical loss defined for all $\bm{\theta}\in\mathbb{R}^{d}$ as
$f(\bm{\theta})=\frac{1}{n}\sum_{i\in[n]}f_{i}(\bm{\theta})$.
This paper considers the following stationary point problem:
Find $\bm{\theta}^{\star}\in\mathbb{R}^{d}$ such that $\nabla f(\bm{\theta}^{\star})=\bm{0}$.

We assume that the loss functions $f_{i}$ ($i\in[n]$) satisfy the conditions in the following assumption (see Appendix [A](#A1) for definitions of functions, mappings, and notation used in this paper).

###### Assumption 2.1 .

Let $n$ be the number of training samples and let $L_{i}>0$ ($i\in[n]$).

(A1) $f_{i}\colon\mathbb{R}^{d}\to\mathbb{R}$ ($i\in[n]$) is differentiable and $L_{i}$-smooth, and $f_{i}^{\star}:=\inf\{f_{i}(\bm{\theta})\colon\bm{\theta}\in\mathbb{R}^{d}\}\in\mathbb{R}$.

(A2) Let $\xi$ be a random variable that is independent of $\bm{\theta}\in\mathbb{R}^{d}$. $\nabla f_{\xi}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ is the stochastic gradient of $\nabla f$ such that
(i) for all $\bm{\theta}\in\mathbb{R}^{d}$, $\mathbb{E}_{\xi}[\nabla f_{\xi}(\bm{\theta})]=\nabla f(\bm{\theta})$
and
(ii) there exists $\sigma\geq 0$ such that, for all $\bm{\theta}\in\mathbb{R}^{d}$, $\mathbb{V}_{\xi}[\nabla f_{\xi}(\bm{\theta})]=\mathbb{E}_{\xi}[\|\nabla f_{\xi}(\bm{\theta})-\nabla f(\bm{\theta})\|^{2}]\leq\sigma^{2}$,
where $\mathbb{E}_{\xi}[\cdot]$ denotes expectation with respect to $\xi$.

(A3) Let $b\in\mathbb{N}$ such that $b\leq n$; and let $\bm{\xi}=(\xi_{1},\xi_{2},\cdots,\xi_{b})^{\top}$ comprise $b$ independent and identically distributed variables
and be independent of $\bm{\theta}\in\mathbb{R}^{d}$. The full gradient $\nabla f(\bm{\theta})$ is estimated as the following mini-batch gradient at $\bm{\theta}$:
$\nabla f_{B}(\bm{\theta}):=\frac{1}{b}\sum_{i=1}^{b}\nabla f_{\xi_{i}}(\bm{\theta})$.

###### Assumption 2.1 .

### 2.2 Mini-batch SGD

Given the $t$-th approximated parameter $\bm{\theta}_{t}\in\mathbb{R}^{d}$ of the deep neural network, mini-batch SGD uses $b_{t}$ loss functions $f_{\xi_{t,1}},f_{\xi_{t,2}},\cdots,f_{\xi_{t,b_{t}}}$ randomly chosen from $\{f_{1},f_{2},\cdots,f_{n}\}$ at each step $t$, where $\bm{\xi}_{t}=(\xi_{t,1},\xi_{t,2},\cdots,\xi_{t,b_{t}})^{\top}$ is independent of $\bm{\theta}_{t}$ and $b_{t}$ is a batch size satisfying $b_{t}\leq n$.
The pseudo-code of the algorithm is shown as Algorithm [1](#alg1).

Figure: Algorithm 1 Mini-batch SGD algorithm

The following lemma can be proved using Proposition [A.1](#A1.Thmproposition1), Assumption [2.1](#S2.Thmassumption1), and the descent lemma (Beck, , Lemma 5.7): for all $\bm{\theta}_{1},\bm{\theta}_{2}\in\mathbb{R}^{d}$,
$f(\bm{\theta}_{2})\leq f(\bm{\theta}_{1})+\langle\nabla f(\bm{\theta}_{1}),\bm{\theta}_{2}-\bm{\theta}_{1}\rangle+\frac{L_{n}}{2}\|\bm{\theta}_{2}-\bm{\theta}_{1}\|^{2}$,
where Assumption [2.1](#S2.Thmassumption1)(A1) ensures that $f$ is $L_{n}$-smooth ($L_{n}:=\frac{1}{n}\sum_{i\in[n]}L_{i}$). The proof itself is given in Appendix [A.1](#A1.SS1).

###### Lemma 2.1 .

Suppose that Assumption [2.1](#S2.Thmassumption1) holds and consider the sequence $(\bm{\theta}_{t})$ generated by Algorithm [1](#alg1) with $\eta_{t}\in[\eta_{\min},\eta_{\max}]\subset[0,\frac{2}{L_{n}})$ satisfying $\sum_{t=0}^{T-1}\eta_{t}\neq 0$, where
$L_{n}:=\frac{1}{n}\sum_{i\in[n]}L_{i}$ and $f^{\star}:=\frac{1}{n}\sum_{i\in[n]}f_{i}^{\star}$.
Then, for all $T\in\mathbb{N}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|^{2}\right]\leq\frac{2(f(\bm{\theta}_{0})-f^{\star})}{2-L_{n}\eta_{\max}}\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}+\frac{L_{n}\sigma^{2}}{2-L_{n}\eta_{\max}}\frac{\sum_{t=0}^{T-1}\eta_{t}^{2}b_{t}^{-1}}{\sum_{t=0}^{T-1}\eta_{t}},$ $$

where $\mathbb{E}$ denotes the total expectation, defined by $\mathbb{E}:=\mathbb{E}_{\bm{\xi}_{0}}\mathbb{E}_{\bm{\xi}_{1}}\cdots\mathbb{E}_{\bm{\xi}_{t}}$.

###### Lemma 2.1 .

## 3 Convergence Analysis of Mini-batch SGD

### 3.1 Constant batch size and decaying learning rate scheduler

This section considers a constant batch size and a decaying learning rate:

$$ $\displaystyle b_{t}=b\text{ }(t\in\mathbb{N})\quad\text{and}\quad\eta_{t+1}\leq\eta_{t}\text{ }(t\in\mathbb{N}).$ (1) $$

Let $p>0$ and $T,E\in\mathbb{N}$; and let $\eta_{\min}$ and $\eta_{\max}$ satisfy $0\leq\eta_{\min}\leq\eta_{\max}$.
Examples of decaying learning rates are as follows:
for all $t\in[0:T]$,

$$ $\displaystyle\text{[Constant LR] }\eta_{t}=\eta_{\max},$ (2) $\displaystyle\text{[Diminishing LR] }\eta_{t}=\frac{\eta_{\max}}{\sqrt{t+1}},$ (3) $\displaystyle\text{[Cosine-annealing LR] }\eta_{t}=\eta_{\min}+\frac{\eta_{\max}-\eta_{\min}}{2}\left(1+\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}\right),$ (4) $\displaystyle\text{[Polynomial Decay LR] }\eta_{t}=(\eta_{\max}-\eta_{\min})\left(1-\frac{t}{T}\right)^{p}+\eta_{\min},$ (5) $$

where $K=\lceil\frac{n}{b}\rceil$
is the number of steps per epoch, $E$ is the total number of epochs, and the number of steps $T$ in ([4](#S3.E4)) is given by $T=KE$.
A simple, practical decaying learning rate is the constant learning rate defined by ([2](#S3.E2)).
A decaying learning rate used in theoretical analyses of deep-learning optimizers is the diminishing learning rate defined by ([3](#S3.E3)).
The cosine-annealing learning rate
defined by ([4](#S3.E4)) and the linear learning rate
defined by ([5](#S3.E5)) with $p=1$ (i.e., an example of a polynomial decay learning rate) are used in practice.
Note that the cosine-annealing learning rate is updated each epoch, whereas the polynomial decay learning rate is updated each step.

Lemma [2.1](#S2.Thmlemma1) leads to the following (the proof of the theorem is given in Appendix [A.2](#A1.SS2)).

###### Theorem 3.1 (Upper bound on $\min_{t}\mathbb{E}\|\nabla f(\bm{\theta}_{t})\|^{2}$ for SGD using ( 1 )).

Under the assumptions in Lemma [2.1](#S2.Thmlemma1),
Algorithm [1](#alg1) using ([1](#S3.E1)) satisfies that, for all $T\in\mathbb{N}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|^{2}\right]\leq\frac{2(f(\bm{\theta}_{0})-f^{\star})}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}}_{B_{T}}+\frac{L_{n}\sigma^{2}}{2-L_{n}\eta_{\max}}\underbrace{\frac{\sum_{t=0}^{T-1}\eta_{t}^{2}}{b\sum_{t=0}^{T-1}\eta_{t}}}_{V_{T}},$ $$

where $\eta$, $p$, $\eta_{\min}$, $\eta_{\max}$, $K$, and $E$ are the parameters used in ([2](#S3.E2))–([5](#S3.E5)),
$T=KE=\lceil\frac{n}{b}\rceil E$ for Polynomial LR ([5](#S3.E5)),

$$ $\displaystyle\begin{split}B_{T}\leq\begin{cases}\displaystyle{\frac{1}{\eta_{\max}T}}&\text{ {\em[Constant LR (\ref{constant})]}}\\ \displaystyle{\frac{1}{2\eta_{\max}(\sqrt{T+1}-1)}}&\text{ {\em[Diminishing LR (\ref{diminishing})]}}\\ \displaystyle{\frac{2}{(\eta_{\min}+\eta_{\max})T}}&\text{ {\em[Cosine LR (\ref{cosine})]}}\\ \displaystyle{\frac{p+1}{(p\eta_{\min}+\eta_{\max})T}}&\text{ {\em[Polynomial LR (\ref{polynomial})]}},\end{cases}\end{split}$ (6) $$

$$ $\displaystyle V_{T}\leq\begin{cases}\displaystyle{\frac{\eta_{\max}}{b}}&\text{ {\em[Constant LR (\ref{constant})]}}\\ \displaystyle{\frac{\eta_{\max}(1+\log T)}{2b(\sqrt{T+1}-1)}}&\text{ {\em[Diminishing LR (\ref{diminishing})]}}\\ \displaystyle{\frac{3\eta_{\min}^{2}+2\eta_{\min}\eta_{\max}+3\eta_{\max}^{2}}{4(\eta_{\min}+\eta_{\max})b}+\frac{\eta_{\max}-\eta_{\min}}{bT}}&\text{ {\em[Cosine LR (\ref{cosine})]}}\\ \displaystyle{\frac{2p^{2}\eta_{\min}^{2}+2p\eta_{\min}\eta_{\max}+(p+1)\eta_{\max}^{2}}{(2p+1)(p\eta_{\min}+\eta_{\max})b}+\frac{(p+1)(\eta_{\max}^{2}-\eta_{\min}^{2})}{(p\eta_{\min}+\eta_{\max})bT}}&\text{ {\em[Polynomial LR (\ref{polynomial})]}}.\end{cases}$ $$

Let us consider using Constant LR ([2](#S3.E2)), Cosine LR ([4](#S3.E4)), or Polynomial LR ([5](#S3.E5)).
Theorem [3.1](#S3.Thmtheorem1) indicates that the bias term including $B_{T}$ converges to 0 0 as $O(\frac{1}{T})$,
whereas the variance term including $V_{T}$ does not always converge to 0 0.
Hence, the upper bound on $\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla f(\bm{\theta}_{t})\|^{2}]$ does not converge to 0 0.
In fact, Theorem [3.1](#S3.Thmtheorem1) with $\eta=\eta_{\max}$ and $\eta_{\min}=0$ implies that

$$ $\displaystyle\limsup_{T\to+\infty}\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|^{2}\right]\leq\frac{L_{n}\sigma^{2}}{(2-L_{n}\eta)b}\times\begin{cases}\eta&\text{ [Constant LR (\ref{constant})]}\\ \displaystyle{\frac{3\eta}{4}}&\text{ [Cosine LR (\ref{cosine})]}\\ \displaystyle{\frac{(p+1)\eta}{(2p+1)}}&\text{ [Polynomial LR (\ref{polynomial})]}.\end{cases}$ (7) $$

Since
$\frac{3\eta}{4}<\eta$ and
$\frac{(p+1)\eta}{(2p+1)}<\eta$ ($p>0$),
using the cosine-annealing learning rate or the polynomial decay learning rate is better than using the constant learning rate in the sense of minimizing the upper bound on
$\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla f(\bm{\theta}_{t})\|^{2}]$.
Theorem [3.1](#S3.Thmtheorem1) also indicates that Algorithm [1](#alg1) using Diminishing LR ([3](#S3.E3)) converges to 0 0 with the convergence rate $\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla f(\bm{\theta}_{t})\|]=O(\frac{\sqrt{\log T}}{T^{\frac{1}{4}}})$. However, since Diminishing LR ([3](#S3.E3)) defined by $\eta_{t}=\frac{\eta}{\sqrt{t+1}}$ decays rapidly (see Figure [1](#S4.F1)(a)), it would not be useful for training DNNs in practice.

###### Theorem 3.1 (Upper bound on min t 𝔼 ∥ ∇ f ( θ t ) ∥ 2 fragments 𝑡 E ∥ ∇ f ( θ 𝑡 ) ∥ 2 \min_{t}\mathbb{E}\|\nabla f(\bm{\theta}_{t})\|^{2} for SGD using ( 1 )).

### 3.2 Increasing batch size and decaying learning rate scheduler

An increasing batch size is used to train DNNs in practice (Byrd et al., ; Balles et al., ; De et al., ; Smith et al., ; Goyal et al., ).
This section considers an increasing batch size and a decaying learning rate following one of ([2](#S3.E2))–([5](#S3.E5)):

$$ $\displaystyle b_{t}\leq b_{t+1}\text{ }(t\in\mathbb{N})\quad\text{and}\quad\eta_{t+1}\leq\eta_{t}\text{ }(t\in\mathbb{N}).$ (8) $$

Examples of $b_{t}$ are, for example, for all $m\in[0:M]$ and all $t\in S_{m}=\mathbb{N}\cap[\sum_{k=0}^{m-1}K_{k}E_{k},\sum_{k=0}^{m}K_{k}E_{k})$ ($S_{0}:=\mathbb{N}\cap[0,K_{0}E_{0})$),

$$ $\displaystyle\text{[Polynomial growth BS] }b_{t}=\left(am\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil+b_{0}\right)^{c},$ (9) $\displaystyle\text{[Exponential growth BS] }b_{t}=\gamma^{m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil}b_{0},$ (10) $$

where $a\in\mathbb{R}_{++}$, $c,\gamma>1$,
and
$E_{m}$ and $K_{m}$ are the numbers of, respectively, epochs and steps per epoch when the batch size is $(am+b_{0})^{c}$ or
$\gamma^{m}b_{0}$.
For example, the exponential growth batch size defined by ([10](#S3.E10)) with $\gamma=2$ makes batch size double each $E_{m}$ epochs.
We may modify the parameters $a$ and $\gamma$ to $a_{t}$ and $\gamma_{t}$ monotone increasing with $t$.
The total number of steps for the batch size to increase $M$ times is $T=\sum_{m=0}^{M}K_{m}E_{m}$.
An analysis of Algorithm [1](#alg1) with a constant batch size $b_{t}=b$ and decaying learning rates satisfying ([8](#S3.E8)) is given in Section [3.1](#S3.SS1).

Lemma [2.1](#S2.Thmlemma1) leads to the following them (the proof of the theorem and the result for Polynomial BS ([9](#S3.E9)) are given in Appendix [A.2](#A1.SS2)).

###### Theorem 3.2 (Convergence rate of SGD using ( 8 )).

Under the assumptions in Lemma [2.1](#S2.Thmlemma1),
Algorithm [1](#alg1) using ([8](#S3.E8)) satisfies that, for all $M\in\mathbb{N}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|^{2}\right]\leq\frac{2(f(\bm{\theta}_{0})-f^{\star})}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}}_{B_{T}}+\frac{L_{n}\sigma^{2}}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}}_{V_{T}},$ $$

where $T=\sum_{m=0}^{M}K_{m}E_{m}$, $E_{\max}=\sup_{M\in\mathbb{N}}\sup_{m\in[0:M]}E_{m}<+\infty$, $K_{\max}=\sup_{M\in\mathbb{N}}\sup_{m\in[0:M]}K_{m}<+\infty$,
$B_{T}$ is defined as in ([6](#S3.E6)),
and $V_{T}$ is bounded as

$$ $\displaystyle V_{T}\leq\begin{cases}\displaystyle{\frac{\gamma\eta K_{\max}E_{\max}}{(\gamma-1)b_{0}T}}&\text{ {\em[Constant LR (\ref{constant})]}}\\ \displaystyle{\frac{\gamma\eta K_{\max}E_{\max}}{2(\gamma-1)b_{0}(\sqrt{T+1}-1)}}&\text{ {\em[Diminishing LR (\ref{diminishing})]}}\\ \displaystyle{\frac{2\gamma\eta_{\max}^{2}K_{\max}E_{\max}}{(\gamma-1)(\eta_{\min}+\eta_{\max})b_{0}T}}&\text{ {\em[Cosine LR (\ref{cosine})]}}\\ \displaystyle{\frac{(p+1)\gamma\eta_{\max}^{2}K_{\max}E_{\max}}{(\gamma-1)(\eta_{\max}+\eta_{\min}p)b_{0}T}}&\text{ {\em[Polynomial LR (\ref{polynomial})]}}.\end{cases}\text{ {\em([Exponential BS (\ref{exponential_bs})])}}$ $$

That is, Algorithm [1](#alg1) using
Exponential BS ([10](#S3.E10)) has the convergence rate

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|\right]=\begin{cases}\displaystyle{O\left(\frac{1}{\sqrt{T}}\right)}&\text{ {\em[Constant LR (\ref{constant}), Cosine LR (\ref{cosine}), Polynomial LR (\ref{polynomial})]}}\\ \displaystyle{O\left(\frac{1}{T^{\frac{1}{4}}}\right)}&\text{ {\em[Diminishing LR (\ref{diminishing})]}}.\end{cases}$ $$

Theorem [3.2](#S3.Thmtheorem2) (Theorem [A.1](#A1.Thmtheorem1)) indicates that, with increasing batch sizes such as Polynomial BS ([9](#S3.E9)) and
Exponential BS ([10](#S3.E10)),
Algorithm [1](#alg1) using each of Constant LR ([2](#S3.E2)), Cosine LR ([4](#S3.E4)), and Polynomial LR ([5](#S3.E5)) has the convergence rate $O(\frac{1}{\sqrt{T}})$, in contrast to Theorem [3.1](#S3.Thmtheorem1).

###### Theorem 3.2 (Convergence rate of SGD using ( 8 )).

### 3.3 Increasing batch size and increasing learning rate scheduler

This section considers an increasing batch size and an increasing learning rate:

$$ $\displaystyle b_{t}\leq b_{t+1}\text{ }(t\in\mathbb{N})\quad\text{and}\quad\eta_{t}\leq\eta_{t+1}\text{ }(t\in\mathbb{N}).$ (11) $$

Example of $b_{t}$ and $\eta_{t}$ satisfying ([11](#S3.E11)) is as follows:
for all $m\in[0,M]$ and all $t\in S_{m}=\mathbb{N}\cap[\sum_{k=0}^{m-1}K_{k}E_{k},\sum_{k=0}^{m}K_{k}E_{k})$
($S_{0}=\mathbb{N}\cap[0,K_{0}E_{0})$),

$$ $\displaystyle\text{[Exponential growth BS and LR] }b_{t}=\delta^{m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil}b_{0},\text{ }\eta_{t}=\gamma^{m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil}\eta_{0},$ (12) $$

where $\delta,\gamma>1$ such that $\gamma^{2}<\delta$;
and
$E_{m}$ and $K_{m}$ are defined as in ([10](#S3.E10)).
We may modify the parameters $\gamma$ and $\delta$ to be monotone increasing parameters in $t$.
The total number of steps when both batch size and learning rate increase $M$ times is $T=\sum_{m=0}^{M}K_{m}E_{m}$.

Lemma [2.1](#S2.Thmlemma1) leads to the following theorem (the proof of the theorem and the result for Polynomial growth BS and LR ([25](#A1.E25)) are given in Appendix [A.2](#A1.SS2)).

###### Theorem 3.3 (Convergence rate of SGD using ( 11 )).

Under the assumptions in Lemma [2.1](#S2.Thmlemma1),
Algorithm [1](#alg1) using ([11](#S3.E11)) satisfies that, for all $M\in\mathbb{N}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|^{2}\right]\leq\frac{2(f(\bm{\theta}_{0})-f^{\star})}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}}_{B_{T}}+\frac{L_{n}\sigma^{2}}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}}_{V_{T}},$ $$

where
$T$, $E_{\max}$, and $K_{\max}$ are defined as in Theorem [3.2](#S3.Thmtheorem2),
$E_{\min}=\inf_{M\in\mathbb{N}}\inf_{m\in[0:M]}E_{m}<+\infty$,
$K_{\min}=\inf_{M\in\mathbb{N}}\inf_{m\in[0:M]}K_{m}<+\infty$,
$\hat{\gamma}=\frac{\gamma^{2}}{\delta}<1$,

$$ $\displaystyle B_{T}\leq\frac{\delta}{\eta_{0}K_{\min}E_{\min}\gamma^{M}},\text{ }V_{T}\leq\frac{K_{\max}E_{\max}\eta_{0}\delta}{K_{\min}E_{\min}b_{0}(1-\hat{\gamma})\gamma^{M}}.$ $$

That is, Algorithm [1](#alg1) has the convergence rate

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|\right]=\displaystyle{O\left(\frac{1}{\gamma^{\frac{M}{2}}}\right)}$ $\displaystyle\text{ {\em[Exponential growth BS and LR (\ref{scheduler_5})]}}.$ $$

Under Exponential BS ([10](#S3.E10)), using Exponential LR ([12](#S3.E12)) improves the convergence rate from $O(\frac{1}{\sqrt{M}})$ with Constant LR ([2](#S3.E2)), Cosine LR ([4](#S3.E4)), or Polynomial LR ([5](#S3.E5)) (Theorem [3.2](#S3.Thmtheorem2)) to $O(\sqrt{\gamma}^{-M})$
($\gamma>1$).

###### Theorem 3.3 (Convergence rate of SGD using ( 11 )).

### 3.4 Increasing batch size and warm-up decaying learning rate scheduler

This section considers an increasing batch size and a decaying learning rate with warm-up for a given $T_{w}=\sum_{m=0}^{M_{w}}K_{m}E_{m}>0$ (learning rate increases $M_{w}$ times):

$$ $\displaystyle b_{t}\leq b_{t+1}\text{ }(t\in\mathbb{N})\quad\text{and}\quad\eta_{t}\leq\eta_{t+1}\text{ }(t\in[T_{w}-1])\land\eta_{t+1}\leq\eta_{t}\text{ }(t\geq T_{w}).$ (13) $$

Examples of $b_{t}$ in ([13](#S3.E13)) are Exponential BS ([12](#S3.E12)) and Polynomial BS ([25](#A1.E25)).
Examples of $\eta_{t}$ in ([13](#S3.E13)) can be obtained by combining
([12](#S3.E12)) with
([2](#S3.E2))–([5](#S3.E5)).
For example,
for all $m\in[0:M]$ and all $t\in S_{m}$,

$$ $\displaystyle\text{[Constant LR with warm-up] }\eta_{t}=\begin{cases}\displaystyle{\gamma^{m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil}\eta_{0}}&\text{ }(m\in[M_{w}])\\ \displaystyle{\gamma^{M_{w}}\eta_{0}}&\text{ }(m\in[M_{w}:M])\end{cases}$ (14) $$

and [Cosine LR with warm-up]

$$ $\displaystyle\eta_{t}=\begin{cases}\displaystyle{\gamma^{m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil}\eta_{0}}&\text{}(m\in[M_{w}])\\ \displaystyle{\eta_{\min}+\frac{\eta_{\max}-\eta_{\min}}{2}}\\ \displaystyle{\times\left\{1+\cos\left(\sum_{k=0}^{m-1}E_{k}+\left\lfloor\frac{t-\sum_{k=0}^{m-1}K_{k}E_{k}}{K_{m}}\right\rfloor-E_{w}\right)\frac{\pi}{E_{M}-E_{w}}\right\}}&\text{}(m\in[M_{w}:M]),\end{cases}$ (15) $$

where
$E_{w}$ is the number of warm-up epochs,
$\eta_{\min}\geq 0$, $\eta_{\max}=\gamma^{M_{w}}\eta_{0}$, and $\gamma$ is defined as in ([12](#S3.E12)).

Theorems [3.2](#S3.Thmtheorem2) and [3.3](#S3.Thmtheorem3) lead to the following theorem.

###### Theorem 3.4 (Convergence rate of SGD using ( 13 )).

Under the assumptions in Lemma [2.1](#S2.Thmlemma1),
Algorithm [1](#alg1) using ([13](#S3.E13)) satisfies that, for all $M\in\mathbb{N}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|^{2}\right]\leq\frac{2(f(\bm{\theta}_{0})-f^{\star})}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}}_{B_{T}}+\frac{L_{n}\sigma^{2}}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}}_{V_{T}},$ $$

where $b_{t}$ is the exponential growth batch size defined by ([12](#S3.E12)) with $\delta,\gamma>1$ such that $\gamma^{2}<\delta$;
$K_{\min}$, $K_{\max}$, $E_{\min}$, and $E_{\max}$ are defined as in Theorems [3.2](#S3.Thmtheorem2) and [3.3](#S3.Thmtheorem3);

$$ $\displaystyle B_{T}\leq\begin{cases}\displaystyle{\frac{\delta}{\eta_{0}K_{\min}E_{\min}\gamma^{M_{w}}}+\frac{1}{\eta_{\max}(T-T_{w})}}&\text{ {\em[Constant LR (\ref{constant_warm_up})]}}\\ \displaystyle{\frac{\delta}{\eta_{0}K_{\min}E_{\min}\gamma^{M_{w}}}+\frac{1}{(\eta_{\min}+\eta_{\max})(T-T_{w})}}&\text{ {\em[Cosine LR (\ref{cosine_warm_up})]}}\end{cases}$ $\displaystyle V_{T}\leq\begin{cases}\displaystyle{\frac{K_{\max}E_{\max}\eta_{0}\delta}{K_{\min}E_{\min}b_{0}(1-\hat{\gamma})\gamma^{M_{w}}}+\frac{\delta\eta_{\max}K_{\max}E_{\max}}{(\delta-1)b_{0}(T-T_{w})}}&\text{ {\em[Constant LR (\ref{constant_warm_up})]}}\\ \displaystyle{\frac{K_{\max}E_{\max}\eta_{0}\delta}{K_{\min}E_{\min}b_{0}(1-\hat{\gamma})\gamma^{M_{w}}}+\frac{2\delta\eta_{\max}^{2}K_{\max}E_{\max}}{(\delta-1)(\eta_{\min}+\eta_{\max})b_{0}(T-T_{w})}}&\text{ {\em[Cosine LR (\ref{cosine_warm_up})]}}.\end{cases}$ $$

That is, Algorithm [1](#alg1) has the convergence rate

$$ $\displaystyle\min_{t\in[T_{w}:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|\right]=O\left(\frac{1}{\sqrt{T-T_{w}}}\right)\text{ {\em[Constant LR (\ref{constant_warm_up}), Cosine LR (\ref{cosine_warm_up})]}}.$ $$

Since Algorithm [1](#alg1) with ([14](#S3.E14)) and ([15](#S3.E15)) uses increasing batch sizes and decaying learning rates for $t\geq T_{w}$, it has the same convergence rate as using ([8](#S3.E8)) in Theorem [3.2](#S3.Thmtheorem2).
Meanwhile, since Algorithm [1](#alg1) with ([14](#S3.E14)) and ([15](#S3.E15)) uses the warm-up learning rates for $t\in[T_{w}]$, Algorithm [1](#alg1) speeds up during the warm-up period, based on Theorem [3.3](#S3.Thmtheorem3).
As a result, for increasing batch sizes, Algorithm [1](#alg1) using decaying learning rates with warm-up minimizes $\mathbb{E}[\|\nabla f(\bm{\theta}_{t})\|]$ faster than using decaying learning rates in Theorem [3.2](#S3.Thmtheorem2).

###### Theorem 3.4 (Convergence rate of SGD using ( 13 )).

## 4 Numerical results

We examined training ResNet-18 on the CIFAR100 dataset ($n=50000$) by using Algorithm [1](#alg1)
(see Appendix [A.3](#A1.SS3) and [A.4](#A1.SS4) for training Wide-ResNet-28-10 on the CIFAR100 and ResNet-18 on Tiny ImageNet).
The experimental environment was two NVIDIA GeForce RTX 4090 GPUs and Intel Core i9 13900KF CPU. The software environment was Python 3.10.12, PyTorch 2.1.0, and CUDA 12.2. The code is available at [https://anonymous.4open.science/r/IncrBothBSLRAccelSGD_arXiv](https://anonymous.4open.science/r/IncrBothBSLRAccelSGD_arXiv).

Figure: (a) Learning rate $\eta_{t}$ and batch size $b$ versus epochs
Refer to caption: /html/2409.08770/assets/x1.png

Figure: (a) Learning rate $\eta_{t}$ and batch size $b_{t}$ versus epochs
Refer to caption: /html/2409.08770/assets/x5.png

We set the total number of epochs $E=300$, the initial learning rate $\eta_{0}=0.1$, and the minimum learning rate $\eta_{\min}=0$ in ([4](#S3.E4)) and ([5](#S3.E5)).
The solid line in the figure represents the mean value, and the shaded area in the figure represents the maximum and minimum over three runs.

Let us first consider the case (Figure [1](#S4.F1)(a)) of a constant batch size ($b=2^{7}$) and decaying learning rates $\eta_{t}$ defined by ([2](#S3.E2))–([5](#S3.E5)) discussed in Section [3.1](#S3.SS1), where “linear" in Figure [1](#S4.F1) denotes Polynomial LR ([5](#S3.E5)) with $p=1$.
Figure [1](#S4.F1)(b)–(d) indicate that using Diminishing LR ([3](#S3.E3)) did not work well, since it decayed rapidly and was very small (Figure [1](#S4.F1)(a)).
Figure [1](#S4.F1)(b)–(d) also indicate that Cosine LR ([4](#S3.E4)) and Polynomial LR ([5](#S3.E5)) performed better than Constant LR ([2](#S3.E2)), as promised in the theoretical results in Theorem [3.1](#S3.Thmtheorem1) and ([7](#S3.E7)).

Next, let us consider the case (Figure [2](#S4.F2)(a)) of doubly increasing batch size every $30$ epochs from an initial batch size $b_{0}=2^{3}$ and decaying learning rates $\eta_{t}$ defined by ([2](#S3.E2))–([5](#S3.E5)).
Figure [2](#S4.F2)(a) indicates that the learning rate of Polynomial LR ([5](#S3.E5)) updated each step (“linear" and “polynomial ($p=2.0$)") becomes small at an early stage of training.
This is because the smaller the batch size $b_{t}$ is, the larger the required number of steps $K_{t}=\lceil\frac{n}{b_{t}}\rceil$ per epoch becomes and the smaller the decaying learning rate $\eta_{t}$ becomes.
Hence, in practice,
increasing batch size is not compatible with Polynomial LR ([5](#S3.E5)) updated each step.
Meanwhile, Figure [2](#S4.F2)(a) indicates Constant LR ([2](#S3.E2)) (“constant") and Cosine LR ([4](#S3.E4)) (“cosine") were compatible with increasing batch size,
since Constant LR ([2](#S3.E2)) and Cosine LR ([4](#S3.E4)) updated each epoch maintain large learning rates even for small batch sizes.
In particular, Figure [2](#S4.F2)(b)–(d) indicate that using Constant LR ([2](#S3.E2)) performed well.

Figure: (a) Learning rate $\eta_{t}$ and batch size $b_{t}$ versus epochs
Refer to caption: /html/2409.08770/assets/x9.png

Let us consider the case (Figure [3](#S4.F3)(a)) of doubly increasing batch size ($\delta=2$) every $30$ epochs and increasing learning rates defined by Exponential growth LR ([12](#S3.E12)) with $\eta_{0}=0.1$ .
The parameters $\gamma$ in the increasing learning rates considered here were
(i) $\gamma\approx 1.080$ when $\eta_{\max}=0.2$,
(ii) $\gamma\approx 1.196$ when $\eta_{\max}=0.5$,
and
(iii) $\gamma\approx 1.292$ when $\eta_{\max}=1.0$,
which satisfy the condition $\gamma^{2}<\delta$ ($=2$) to guarantee the convergence of Algorithm [1](#alg1) (see Theorem [3.3](#S3.Thmtheorem3)).
Figure [3](#S4.F3) compares the result for “constant" in Figure [2](#S4.F2) with the ones for the increasing learning rates (i)–(iii).
Figure [3](#S4.F3)(b) indicates that the larger the learning rate $\eta_{t}$ was, the smaller the full gradient norm $\|\nabla f(\bm{\theta}_{e})\|$ became and that Algorithm [1](#alg1) with increasing learning rates minimized the full gradient norm faster than Algorithm [1](#alg1) with a constant learning rate (“constant" in Figures [2](#S4.F2) and [3](#S4.F3)), as promised in Theorem [3.3](#S3.Thmtheorem3).

Figure: (a) Learning rate $\eta_{t}$ and batch size $b_{t}$ versus epochs
Refer to caption: /html/2409.08770/assets/x13.png

Figure: (a) Learning rate $\eta_{t}$ and batch size $b_{t}$ versus epochs
Refer to caption: /html/2409.08770/assets/x17.png

Let us consider the case (Figure [4](#S4.F4)(a)) of a doubly increasing batch size and decaying learning rates (Constant LR ([2](#S3.E2)) and Cosine LR ([4](#S3.E4))) with warm-up based on Figure [3](#S4.F3)(a).
Figure [4](#S4.F4)(b) indicates that using decaying learning rates with warm-up accelerated Algorithm [1](#alg1) more than using only increasing learning rates in Figure [3](#S4.F3)(b) and only a constant learning rate in Figure [2](#S4.F2)(b).

From the sufficient condition $\gamma^{2}<\delta$ to guarantee convergence of Algorithm [1](#alg1) with both batch size and learning rate increasing (Theorem [3.3](#S3.Thmtheorem3)),
we can set a larger $\gamma$ when $\delta$ is large.
Since Algorithm [1](#alg1) has an $O(\gamma^{-\frac{M}{2}})$ convergence rate (Theorem [3.3](#S3.Thmtheorem3)), using triply ($\gamma=1.5<\sqrt{\delta}=\sqrt{3}$) and quadruply ($\gamma=1.9<\sqrt{\delta}=\sqrt{4}$) increasing batch sizes theoretically decreases $\|\nabla f(\bm{\theta}_{e})\|$ faster than doubly increasing batch sizes ($\gamma=1.080<\sqrt{\delta}=\sqrt{2}$ when $\eta_{\max}=0.2$; Figure [3](#S4.F3)).
Finally, we would like to verify whether the theoretical result holds in practice.
The scheduler was as in Figure [5](#S4.F5)(a) with $\eta_{0}=0.1$ and
$\eta_{\max}=0.2$, where schedulers were modified such that batch sizes belong to $[2^{3},2^{12}]$ and learning rates belong to $[0.1,0.2]$ (e.g., $b_{e}=a\delta^{\lfloor\frac{e}{30}\rfloor}+b$ and $\eta_{e}=c\gamma^{\lfloor\frac{e}{30}\rfloor}+d$,
where
$a\approx 0.2077$, $b\approx 7.7923$, $c\approx 0.00267$, and $d\approx 0.09733$ when $\delta=3$ and $\gamma=1.50$
and $a\approx 0.0155$, $b\approx 7.9844$, $c\approx 0.00031$, and $d\approx 0.09969$ when $\delta=4$ and $\gamma=1.90$).
Figure [5](#S4.F5)(a) and (b) indicate that the larger the increasing rate of batch size was (the cases of $\delta=3,4$ after $180$ epochs), the larger the increasing rate of the learning rate became ($\gamma=1.5,1.9$ when $\delta=3,4$) and the smaller $\|\nabla f(\bm{\theta}_{e})\|$ became.
That is, using increasing learning rates based on tripling and quadrupling batch sizes minimizes $\|\nabla f(\bm{\theta}_{e})\|$ faster than using increasing learning rates based on doubly increasing batch sizes.
Figure [5](#S4.F5)(c) and (d) indicate that using $\delta=3,4$ was better than using $\delta=2$ in the sense of minimizing $f(\bm{\theta}_{e})$ and achieving high test accuracy.

## 5 Conclusion

This paper presented theoretical analyses of mini-batch SGD under batch size and learning rate schedulers used in practice.
Our results indicated that using increasing batch sizes and decaying learning rates guarantees convergence of mini-batch SGD
and
using both batch sizes and learning rates that increase accelerates mini-batch SGD.
That is,
using increasing batch sizes and decaying learning rates with warm-up guarantees fast convergence of mini-batch SGD in the sense of minimizing the expectation of the full gradient norm of the empirical loss.
This paper also provided numerical results to support the analysis results
that increasing both batch sizes and learning rates accelerates mini-batch SGD.
One limitation of this study is that the numbers of models and datasets in the experiments were limited. Hence, we should conduct similar experiments with larger numbers of models and datasets to support our theoretical results.

## Appendix A Appendix

We here give the notation and state some definitions.
Let $\mathbb{N}$ be the set of natural numbers.
Define $[n]:=\{1,2,\cdots,n\}$ and $[0:n]:=\{0,1,\cdots,n\}$ for $n\in\mathbb{N}$. Let $\mathbb{R}^{d}$ be the $d$-dimensional Euclidean space with inner product $\langle\bm{\theta}_{1},\bm{\theta}_{2}\rangle=\bm{\theta}_{1}^{\top}\bm{\theta}_{2}$ $(\bm{\theta}_{1},\bm{\theta}_{2}\in\mathbb{R}^{d})$ and its induced norm $\|\bm{\theta}\|:=\sqrt{\langle\bm{\theta},\bm{\theta}\rangle}$ $(\bm{\theta}\in\mathbb{R}^{d})$. Let $\mathbb{R}_{+}^{d}:=\{\bm{\theta}=(\theta_{1},\theta_{2},\ldots,\theta_{d})^{\top}\in\mathbb{R}^{d}\colon\theta_{i}\geq 0\text{ }(i\in[d])\}$ and $\mathbb{R}_{++}^{d}:=\{\bm{\theta}=(\theta_{1},\theta_{2},\ldots,\theta_{d})^{\top}\in\mathbb{R}^{d}\colon\theta_{i}>0\text{ }(i\in[d])\}$.
The gradient of a differentiable function $f\colon\mathbb{R}^{d}\to\mathbb{R}$ at $\bm{\theta}\in\mathbb{R}^{d}$ is denoted by $\nabla f(\bm{\theta})$. Let $L>0$. A differentiable function $f\colon\mathbb{R}^{d}\to\mathbb{R}$ is said to be $L$-smooth if the gradient $\nabla f\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ is Lipschitz continuous, i.e., for all $\bm{\theta}_{1},\bm{\theta}_{2}\in\mathbb{R}^{d}$, $\|\nabla f(\bm{\theta}_{1})-\nabla f(\bm{\theta}_{2})\|\leq L\|\bm{\theta}_{1}-\bm{\theta}_{2}\|$.
Let $(x_{t}),(y_{t})\subset\mathbb{R}_{+}$ be sequences. Let $O$ be Landau’s symbol, i.e., $y_{t}=O(x_{t})$ if there exist $c\in\mathbb{R}_{+}$ and $t_{0}\in\mathbb{N}$ such that, for all $t\geq t_{0}$, $y_{t}\leq cx_{t}$.

### A.1 Proofs of Proposition A.1 and Lemma 2.1

The following proposition holds for the mini-batch gradient.

###### Proposition A.1 .

Let $t\in\mathbb{N}$ and $\bm{\xi}_{t}$ be a random variable that is independent of $\bm{\xi}_{j}$ ($j\in[0:t-1]$); let $\bm{\theta}_{t}\in\mathbb{R}^{d}$ be independent of $\bm{\xi}_{t}$; let $\nabla f_{B_{t}}(\bm{\theta}_{t})$ be the mini-batch gradient defined by Algorithm [1](#alg1), where $f_{\xi_{t,i}}$ ($i\in[b]$) is the stochastic gradient (see Assumption [2.1](#S2.Thmassumption1)(A2)). Then, the following hold:

$$ $\displaystyle\mathbb{E}_{\bm{\xi}_{t}}\left[\nabla f_{B_{t}}(\bm{\theta}_{t})\Big{|}\hat{\bm{\xi}}_{t-1}\right]=\nabla f(\bm{\theta}_{t})\text{ and }\mathbb{V}_{\bm{\xi}_{t}}\left[\nabla f_{B_{t}}(\bm{\theta}_{t})\Big{|}\hat{\bm{\xi}}_{t-1}\right]\leq\frac{\sigma^{2}}{b_{t}},$ $$

where $\mathbb{E}_{\bm{\xi}_{t}}[\cdot|\hat{\bm{\xi}}_{t-1}]$ and $\mathbb{V}_{\bm{\xi}_{t}}[\cdot|\hat{\bm{\xi}}_{t-1}]$ are respectively the expectation and variance with respect to $\bm{\xi}_{t}$ conditioned on $\bm{\xi}_{t-1}=\hat{\bm{\xi}}_{t-1}$.

The first equation in Proposition [A.1](#A1.Thmproposition1) indicates that the mini-batch gradient $\nabla f_{B_{t}}(\bm{\theta}_{t})$ is an unbiased estimator of the full gradient $\nabla f(\bm{\theta}_{t})$. The second inequality in Proposition [A.1](#A1.Thmproposition1) indicates that the upper bound on the variance of the mini-batch gradient $\nabla f_{B_{t}}(\bm{\theta}_{t})$ is inversely proportional to the batch size $b_{t}$.

Proof of Proposition [A.1](#A1.Thmproposition1):
Assumption [2.1](#S2.Thmassumption1)(A3) and the independence of $b_{t}$ and $\bm{\xi}_{t}$ ensure that

$$ $\displaystyle\mathbb{E}_{\bm{\xi}_{t}}\left[\nabla f_{B_{t}}(\bm{\theta}_{t})\Big{|}\hat{\bm{\xi}}_{t-1}\right]=\mathbb{E}_{\bm{\xi}_{t}}\left[\frac{1}{b_{t}}\sum_{i=1}^{b_{t}}\nabla f_{\xi_{t,i}}(\bm{\theta}_{t})\Bigg{|}\hat{\bm{\xi}}_{t-1}\right]=\frac{1}{b_{t}}\sum_{i=1}^{b_{t}}\mathbb{E}_{\xi_{t,i}}\left[\nabla f_{\xi_{t,i}}(\bm{\theta}_{t})\Big{|}\hat{\bm{\xi}}_{t-1}\right],$ $$

which, together with Assumption [2.1](#S2.Thmassumption1)(A2)(i) and the independence of $\bm{\xi}_{t}$ and $\bm{\xi}_{t-1}$, implies that

$$ $\displaystyle\mathbb{E}_{\bm{\xi}_{t}}\left[\nabla f_{B_{t}}(\bm{\theta}_{t})\Big{|}\hat{\bm{\xi}}_{t-1}\right]=\frac{1}{b_{t}}\sum_{i=1}^{b_{t}}\nabla f(\bm{\theta}_{t})=\nabla f(\bm{\theta}_{t}).$ (16) $$

Assumption [2.1](#S2.Thmassumption1)(A3), the independence of $b_{t}$ and $\bm{\xi}_{t}$, and ([16](#A1.E16)) imply that

$$ $\displaystyle\mathbb{V}_{\bm{\xi}_{t}}\left[\nabla f_{B_{t}}(\bm{\theta}_{t})\Big{|}\hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle=\mathbb{E}_{\bm{\xi}_{t}}\left[\|\nabla f_{B_{t}}(\bm{\theta}_{t})-\nabla f(\bm{\theta}_{t})\|^{2}\Big{|}\hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle=\mathbb{E}_{\bm{\xi}_{t}}\left[\left\|\frac{1}{b_{t}}\sum_{i=1}^{b_{t}}\nabla f_{\xi_{t,i}}(\bm{\theta}_{t})-\nabla f(\bm{\theta}_{t})\right\|^{2}\Bigg{|}\hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle=\frac{1}{b_{t}^{2}}\mathbb{E}_{\bm{\xi}_{t}}\left[\left\|\sum_{i=1}^{b_{t}}\left(\nabla f_{\xi_{t,i}}(\bm{\theta}_{t})-\nabla f(\bm{\theta}_{t})\right)\right\|^{2}\Bigg{|}\hat{\bm{\xi}}_{t-1}\right].$ $$

From the independence of $\xi_{t,i}$ and $\xi_{t,j}$ ($i\neq j$) and Assumption [2.1](#S2.Thmassumption1)(A2)(i), for all $i,j\in[b_{t}]$ such that $i\neq j$,

$$ $\displaystyle\mathbb{E}_{\xi_{t,i}}[\langle\nabla f_{\xi_{t,i}}(\bm{\theta}_{t})-\nabla f(\bm{\theta}_{t}),\nabla f_{\xi_{t,j}}(\bm{\theta}_{t})-\nabla f(\bm{\theta}_{t})\rangle|\hat{\bm{\xi}}_{t-1}]$ $\displaystyle=\langle\mathbb{E}_{\xi_{t,i}}[\nabla f_{\xi_{t,i}}(\bm{\theta}_{t})|\hat{\bm{\xi}}_{t-1}]-\mathbb{E}_{\xi_{t,i}}[\nabla f(\bm{\theta}_{t})|\hat{\bm{\xi}}_{t-1}],\nabla f_{\xi_{t,j}}(\bm{\theta}_{t})-\nabla f(\bm{\theta}_{t})\rangle$ $\displaystyle=0.$ $$

Hence, Assumption [2.1](#S2.Thmassumption1)(A2)(ii) guarantees that

$$ $\displaystyle\mathbb{V}_{\bm{\xi}_{t}}\left[\nabla f_{B_{t}}(\bm{\theta})\Big{|}\hat{\bm{\xi}}_{t-1}\right]=\frac{1}{b_{t}^{2}}\sum_{i=1}^{b_{t}}\mathbb{E}_{\xi_{t,i}}\left[\left\|\nabla f_{\xi_{t,i}}(\bm{\theta}_{t})-\nabla f(\bm{\theta}_{t})\right\|^{2}\Big{|}\hat{\bm{\xi}}_{t-1}\right]\leq\frac{\sigma^{2}b_{t}}{b_{t}^{2}}=\frac{\sigma^{2}}{b_{t}},$ $$

which completes the proof.
$\Box$

Proof of Lemma [2.1](#S2.Thmlemma1): The $L_{n}$-smoothness of $f$ implies that the descent lemma holds; i.e., for all $t\in\mathbb{N}$,

$$ $\displaystyle f(\bm{\theta}_{t+1})\leq f(\bm{\theta}_{t})+\langle\nabla f(\bm{\theta}_{t}),\bm{\theta}_{t+1}-\bm{\theta}_{t}\rangle+\frac{L_{n}}{2}\|\bm{\theta}_{t+1}-\bm{\theta}_{t}\|^{2},$ $$

which, together with $\bm{\theta}_{t+1}:=\bm{\theta}_{t}-\eta_{t}\nabla f_{B_{t}}(\bm{\theta}_{t})$, implies that

$$ $\displaystyle\begin{split}f(\bm{\theta}_{t+1})&\leq f(\bm{\theta}_{t})-\eta_{t}\langle\nabla f(\bm{\theta}_{t}),\nabla f_{B_{t}}(\bm{\theta}_{t})\rangle+\frac{L_{n}\eta_{t}^{2}}{2}\|\nabla f_{B_{t}}(\bm{\theta}_{t})\|^{2}.\end{split}$ (17) $$

Proposition [A.1](#A1.Thmproposition1) guarantees that

$$ $\displaystyle\begin{split}\mathbb{E}_{\bm{\xi}_{t}}\left[\left\|\nabla f_{B_{t}}(\bm{\theta}_{t})\right\|^{2}|\hat{\bm{\xi}}_{t-1}\right]&=\mathbb{E}_{\bm{\xi}_{t}}\left[\left\|\nabla f_{B_{t}}(\bm{\theta}_{t})-\nabla f(\bm{\theta}_{t})+\nabla f(\bm{\theta}_{t})\right\|^{2}\Big{|}\hat{\bm{\xi}}_{t-1}\right]\\ &=\mathbb{E}_{\bm{\xi}_{t}}\left[\left\|\nabla f_{B_{t}}(\bm{\theta}_{t})-\nabla f(\bm{\theta}_{t})\right\|^{2}\Big{|}\hat{\bm{\xi}}_{t-1}\right]\\ &\quad+2\mathbb{E}_{\bm{\xi}_{t}}\left[\langle\nabla f_{B_{t}}(\bm{\theta}_{t})-\nabla f(\bm{\theta}_{t}),\nabla f(\bm{\theta}_{t})\rangle\Big{|}\hat{\bm{\xi}}_{t-1}\right]\\ &\quad+\mathbb{E}_{\bm{\xi}_{t}}\left[\left\|\nabla f(\bm{\theta}_{t})\right\|^{2}\Big{|}\hat{\bm{\xi}}_{t-1}\right]\\ &\leq\frac{\sigma^{2}}{b_{t}}+\left\|\nabla f(\bm{\theta}_{t})\right\|^{2}.\end{split}$ (18) $$

Taking the expectation conditioned on $\bm{\xi}_{t-1}=\hat{\bm{\xi}}_{t-1}$ on both sides of ([17](#A1.E17)), together with Proposition [A.1](#A1.Thmproposition1) and ([18](#A1.E18)), guarantees that, for all $k\in\mathbb{N}$,

$$ $\displaystyle\mathbb{E}_{\bm{\xi}_{t}}\left[f(\bm{\theta}_{t+1})\Big{|}\hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle\leq f(\bm{\theta}_{t})-\eta_{t}\mathbb{E}_{\bm{\xi}_{t}}\left[\langle\nabla f(\bm{\theta}_{t}),\nabla f_{B_{t}}(\bm{\theta}_{t})\rangle\Big{|}\hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle\quad+\frac{L_{n}\eta_{t}^{2}}{2}\mathbb{E}_{\bm{\xi}_{t}}\left[\left\|\nabla f_{B_{t}}(\bm{\theta}_{t})\right\|^{2}\Big{|}\hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle\leq f(\bm{\theta}_{t})-\eta_{t}\left\|\nabla f(\bm{\theta}_{t})\right\|^{2}+\frac{L_{n}\eta_{t}^{2}}{2}\left(\frac{\sigma^{2}}{b_{t}}+\left\|\nabla f(\bm{\theta}_{t})\right\|^{2}\right).$ $$

Hence, taking the total expectation on both sides of the above inequality ensures that, for all $t\in\mathbb{N}$,

$$ $\displaystyle\eta_{k}\left(1-\frac{L_{n}\eta_{t}}{2}\right)\mathbb{E}\left[\left\|\nabla f(\bm{\theta}_{t})\right\|^{2}\right]\leq\mathbb{E}\left[f(\bm{\theta}_{t})-f(\bm{\theta}_{t+1})\right]+\frac{L_{n}\sigma^{2}\eta_{t}^{2}}{2b_{t}}.$ $$

Let $T\in\mathbb{N}$. Summing the above inequality from $t=0$ to $t=T-1$ ensures that

$$ $\displaystyle\sum_{t=0}^{T-1}\eta_{t}\left(1-\frac{L_{n}\eta_{t}}{2}\right)\mathbb{E}\left[\left\|\nabla f(\bm{\theta}_{t})\right\|^{2}\right]\leq\mathbb{E}\left[f(\bm{\theta}_{0})-f(\bm{\theta}_{T})\right]+\frac{L_{n}\sigma^{2}}{2}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}},$ $$

which, together with Assumption [2.1](#S2.Thmassumption1)(A1) (the lower bound $f^{\star}:=\frac{1}{n}\sum_{i\in[n]}f_{i}^{\star}$ of $f$), implies that

$$ $\displaystyle\sum_{t=0}^{T-1}\eta_{t}\left(1-\frac{L_{n}\eta_{t}}{2}\right)\mathbb{E}\left[\left\|\nabla f(\bm{\theta}_{t})\right\|^{2}\right]\leq f(\bm{\theta}_{0})-f^{\star}+\frac{L_{n}\sigma^{2}}{2}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}.$ $$

Since $\eta_{t}\in[\eta_{\min},\eta_{\max}]$,
we have that

$$ $\displaystyle\left(1-\frac{L_{n}\eta_{\max}}{2}\right)\sum_{t=0}^{T-1}\eta_{t}\mathbb{E}\left[\left\|\nabla f(\bm{\theta}_{t})\right\|^{2}\right]\leq f(\bm{\theta}_{0})-f^{\star}+\frac{L_{n}\sigma^{2}}{2}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}},$ $$

which, together with $\eta_{t}\in[\eta_{\min},\eta_{\max}]\subset[0,\frac{2}{L_{n}})$, implies that

$$ $\displaystyle\sum_{t=0}^{T-1}\eta_{t}\mathbb{E}\left[\left\|\nabla f(\bm{\theta}_{t})\right\|^{2}\right]\leq\frac{2(f(\bm{\theta}_{0})-f^{\star})}{2-L_{n}\eta_{\max}}+\frac{L_{n}\sigma^{2}}{2-L_{n}\eta_{\max}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}.$ $$

Therefore, from $\sum_{t=0}^{T-1}\eta_{t}\neq 0$, we have

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla f(\bm{\theta}_{t})\|^{2}]\leq\frac{2(f(\bm{\theta}_{0})-f^{\star})}{2-L_{n}\eta_{\max}}\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}+\frac{L_{n}\sigma^{2}}{2-L_{n}\eta_{\max}}\frac{\sum_{t=0}^{T-1}\eta_{t}^{2}b_{t}^{-1}}{\sum_{t=0}^{T-1}\eta_{t}},$ (19) $$

which implies that the assertion in Lemma [2.1](#S2.Thmlemma1) holds.
$\Box$

###### Proposition A.1 .

### A.2 Proofs of Theorems

We can also consider the case where batch sizes decay.
For simplicity, let us set a constant learning rate $\eta_{t}=\eta>0$ and a decaying batch size $b_{t}=\frac{1}{t+1}$.
Then, we have that $V_{T}\leq\frac{\eta}{T}\sum_{t=0}^{T-1}\frac{1}{b_{t}}=\frac{\eta(T+1)}{2}\to+\infty$ ($T\to+\infty$), which implies that convergence of mini-batch SGD is not guaranteed.
Accordingly, this paper focuses on the four cases in the main text.

Proof of Theorem [3.1](#S3.Thmtheorem1):
Let $\eta_{\max}=\eta$.

[Constant LR ([2](#S3.E2))]
We have that

$$ $\displaystyle B_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta}=\frac{1}{\eta T},\text{ }V_{T}=\frac{\sum_{t=0}^{T-1}\eta^{2}}{b\sum_{t=0}^{T-1}\eta}=\frac{\eta}{b}.$ $$

[Diminishing LR ([3](#S3.E3))]
We have that

$$ $\displaystyle\sum_{t=0}^{T-1}\frac{1}{\sqrt{t+1}}\geq\int_{0}^{T}\frac{\mathrm{d}t}{\sqrt{t+1}}=2(\sqrt{T+1}-1),$ $$

which implies that

$$ $\displaystyle B_{T}=\frac{1}{\sum_{t=0}^{T-1}\frac{\eta}{\sqrt{t+1}}}\leq\frac{1}{2\eta(\sqrt{T+1}-1)}.$ $$

We also have that

$$ $\displaystyle\sum_{t=0}^{T-1}\frac{1}{t+1}\leq 1+\int_{0}^{T-1}\frac{\mathrm{d}t}{t+1}=1+\log T,$ $$

which implies that

$$ $\displaystyle V_{T}=\frac{\eta\sum_{t=0}^{T-1}\frac{1}{t+1}}{b\sum_{t=0}^{T-1}\frac{1}{\sqrt{t+1}}}\leq\frac{\eta(1+\log T)}{2b(\sqrt{T+1}-1)}.$ $$

[Cosine LR ([4](#S3.E4))]
We have

$$ $\displaystyle\sum_{t=0}^{KE-1}\eta_{t}$ $\displaystyle=\eta_{\min}KE+\frac{\eta_{\max}-\eta_{\min}}{2}KE+\frac{\eta_{\max}-\eta_{\min}}{2}\sum_{t=0}^{KE-1}\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}.$ $$

From
$\sum_{t=0}^{KE}\cos\lfloor\frac{t}{K}\rfloor\frac{\pi}{E}=K-1$,
we have

$$ $\displaystyle\sum_{t=0}^{KE-1}\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}=K-1-\cos\pi=K.$ (20) $$

We thus have

$$ $\displaystyle\sum_{t=0}^{KE-1}\eta_{t}$ $\displaystyle=\eta_{\min}KE+\frac{\eta_{\max}-\eta_{\min}}{2}KE+\frac{\eta_{\max}-\eta_{\min}}{2}K$ $\displaystyle=\frac{1}{2}\{(\eta_{\min}+\eta_{\max})KE+(\eta_{\max}-\eta_{\min})K\}$ $\displaystyle\geq\frac{(\eta_{\min}+\eta_{\max})KE}{2}.$ $$

Moreover, we have that

$$ $\displaystyle\sum_{t=0}^{KE-1}\eta_{t}^{2}$ $\displaystyle=\eta_{\min}^{2}KE+\eta_{\min}(\eta_{\max}-\eta_{\min})\sum_{t=0}^{KE-1}\left(1+\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}\right)$ $\displaystyle\quad+\frac{(\eta_{\max}-\eta_{\min})^{2}}{4}\sum_{t=0}^{KE-1}\left(1+\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}\right)^{2},$ $$

which implies that

$$ $\displaystyle\sum_{t=0}^{KE-1}\eta_{t}^{2}$ $\displaystyle=\eta_{\min}\eta_{\max}KE+\frac{(\eta_{\max}-\eta_{\min})^{2}}{4}KE+\eta_{\min}(\eta_{\max}-\eta_{\min})\sum_{t=0}^{KE-1}\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}$ $\displaystyle\quad+\frac{(\eta_{\max}-\eta_{\min})^{2}}{2}\sum_{t=0}^{KE-1}\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}+\frac{(\eta_{\max}-\eta_{\min})^{2}}{4}\sum_{t=0}^{KE-1}\cos^{2}\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}.$ $$

From

$$ $\displaystyle\sum_{t=0}^{KE}\cos^{2}\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}$ $\displaystyle=\frac{1}{2}\sum_{t=0}^{KE}\left(1+\cos 2\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}\right)$ $\displaystyle=\frac{1}{2}(KE+1)+\frac{1}{2}$ $\displaystyle=\frac{KE}{2}+1,$ $$

we have

$$ $\displaystyle\sum_{t=0}^{KE-1}\cos^{2}\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}=\frac{KE}{2}+1-\cos^{2}\pi=\frac{KE}{2}.$ $$

From ([20](#A1.E20)), we have

$$ $\displaystyle\sum_{t=0}^{KE-1}\eta_{t}^{2}$ $\displaystyle=\frac{(\eta_{\min}+\eta_{\max})^{2}}{4}KE+\eta_{\min}(\eta_{\max}-\eta_{\min})+\frac{(\eta_{\max}-\eta_{\min})^{2}}{2}+\frac{(\eta_{\max}-\eta_{\min})^{2}}{4}\frac{KE}{2}$ $\displaystyle=\frac{3\eta_{\min}^{2}+2\eta_{\min}\eta_{\max}+3\eta_{\max}^{2}}{8}KE+\frac{(\eta_{\max}-\eta_{\min})(\eta_{\max}+\eta_{\min})}{2}.$ $$

Hence, we have

$$ $\displaystyle B_{T}=\frac{1}{\sum_{t=0}^{KE-1}\eta_{t}}\leq\frac{2}{(\eta_{\min}+\eta_{\max})KE}$ $$

and

$$ $\displaystyle V_{T}=\frac{\sum_{t=0}^{KE-1}\eta_{t}^{2}}{b\sum_{t=0}^{KE-1}\eta_{t}}$ $\displaystyle\leq\frac{3\eta_{\min}^{2}+2\eta_{\min}\eta_{\max}+3\eta_{\max}^{2}}{4(\eta_{\min}+\eta_{\max})b}+\frac{\eta_{\max}-\eta_{\min}}{bKE}.$ $$

[Polynomial LR ([5](#S3.E5))]
Since $f(x)=(1-x)^{p}$ is monotone decreasing for $x\in[0,1)$, we have that

$$ $\displaystyle\int_{0}^{1}(1-x)^{p}\mathrm{d}x<\frac{1}{T}\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{p},$ $$

which implies that

$$ $\displaystyle T\int_{0}^{1}(1-x)^{p}dx<\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{p}.$ (21) $$

Since
$\int_{0}^{1}(1-x)^{p}\mathrm{d}x=\frac{1}{p+1}$,
([21](#A1.E21)) implies that

$$ $\displaystyle\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{p}>\frac{T}{p+1}.$ $$

Accordingly,

$$ $\displaystyle\sum_{t=0}^{T-1}\eta_{t}$ $\displaystyle=(\eta_{\max}-\eta_{\min})\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{p}+\eta_{\min}T$ $\displaystyle>(\eta_{\max}-\eta_{\min})\frac{T}{p+1}+\eta_{\min}T$ $\displaystyle=\left(\frac{\eta_{\max}-\eta_{\min}}{p+1}+\eta_{\min}\right)T$ $\displaystyle=\frac{\eta_{\max}+\eta_{\min}p}{p+1}T.$ $$

Since $f(x)=(1-x)^{p}$ and
$g(x)=(1-x)^{2p}$ are monotone decreasing for
$x\in[0,1)$, we have that

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{p}<\frac{1}{T}+\int_{0}^{1}(1-x)^{p}\mathrm{d}x,\text{ }\frac{1}{T}\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{2p}<\frac{1}{T}+\int_{0}^{1}(1-x)^{2p}\mathrm{d}x,$ $$

which imply that

$$ $\displaystyle\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{p}<1+T\int_{0}^{1}(1-x)^{p}\mathrm{d}x,\text{ }\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{2p}<1+T\int_{0}^{1}(1-x)^{2p}\mathrm{d}x.$ (22) $$

Since we have that
$\int_{0}^{1}(1-x)^{p}\mathrm{d}x=\frac{1}{p+1}$
and
$\int_{0}^{1}(1-x)^{2p}\mathrm{d}x=\frac{1}{2p+1}$,
([22](#A1.E22)) ensures that

$$ $\displaystyle\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{p}<1+\frac{T}{p+1},\text{ }\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{2p}<1+\frac{T}{2p+1}.$ $$

Hence,

$$ $\displaystyle\sum_{t=0}^{T-1}\eta_{t}^{2}$ $\displaystyle=(\eta_{\max}-\eta_{\min})^{2}\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{2p}+2(\eta_{\max}-\eta_{\min})\sum_{t=0}^{T-1}\left(1-\frac{t}{T}\right)^{p}\eta_{\min}+\eta_{\min}^{2}T$ $\displaystyle<(\eta_{\max}-\eta_{\min})^{2}\left(1+\frac{T}{2p+1}\right)+2(\eta_{\max}-\eta_{\min})\left(1+\frac{T}{p+1}\right)\eta_{\min}+\eta_{\min}^{2}T$ $\displaystyle=\frac{\eta_{\max}^{2}(p+1)(2p+T+1)+2\eta_{\max}\eta_{\min}pT+\eta_{\min}^{2}(2p^{2}(T-1)-3p-1)}{(p+1)(2p+1)}.$ $$

Therefore,

$$ $\displaystyle B_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\leq\frac{p+1}{(\eta_{\max}+\eta_{\min}p)T}$ $$

and

$$ $\displaystyle V_{T}$ $\displaystyle=\frac{\sum_{t=0}^{T-1}\eta_{t}^{2}}{b\sum_{t=0}^{T-1}\eta_{t}}$ $\displaystyle=\frac{\eta_{\max}^{2}(p+1)(2p+T+1)+2\eta_{\max}\eta_{\min}pT+\eta_{\min}^{2}(2p^{2}(T-1)-3p-1)}{(2p+1)(\eta_{\max}+\eta_{\min}p)bT}$ $\displaystyle=\frac{2p^{2}\eta_{\min}^{2}+2p\eta_{\min}\eta_{\max}+(p+1)\eta_{\max}^{2}}{(2p+1)(p\eta_{\min}+\eta_{\max})b}+\frac{(p+1)(2p+1)\eta_{\max}^{2}-(p+1)(2p+1)\eta_{\min}^{2}}{(2p+1)(p\eta_{\min}+\eta_{\max})bT}$ $\displaystyle=\frac{2p^{2}\eta_{\min}^{2}+2p\eta_{\min}\eta_{\max}+(p+1)\eta_{\max}^{2}}{(2p+1)(p\eta_{\min}+\eta_{\max})b}+\frac{(p+1)(\eta_{\max}^{2}-\eta_{\min}^{2})}{(p\eta_{\min}+\eta_{\max})bT}.$ $$

This completes the proof.
$\Box$

We will now show the following theorem, which includes Theorem [3.2](#S3.Thmtheorem2).

###### Theorem A.1 (Convergence rate of SGD using ( 8 )).

Under the assumptions in Lemma [2.1](#S2.Thmlemma1),
Algorithm [1](#alg1) using ([8](#S3.E8)) satisfies that, for all $M\in\mathbb{N}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|^{2}\right]\leq\frac{2(f(\bm{\theta}_{0})-f^{\star})}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}}_{B_{T}}+\frac{L_{n}\sigma^{2}}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}}_{V_{T}},$ $$

where $T=\sum_{m=0}^{M}K_{m}E_{m}$, $E_{\max}=\sup_{M\in\mathbb{N}}\sup_{m\in[0:M]}E_{m}<+\infty$, $K_{\max}=\sup_{M\in\mathbb{N}}\sup_{m\in[0:M]}K_{m}<+\infty$,
$B_{T}$ is defined as in ([6](#S3.E6)),
and $V_{T}$ is given by

$$ $\displaystyle V_{T}\leq\begin{cases}\displaystyle{\frac{3\eta K_{\max}E_{\max}}{a^{c}T}}&\text{ {\em[Constant LR (\ref{constant})]}}\\ \displaystyle{\frac{3\eta K_{\max}E_{\max}}{2a^{c}(\sqrt{T+1}-1)}}&\text{ {\em[Diminishing LR (\ref{diminishing})]}}\\ \displaystyle{\frac{6\eta_{\max}^{2}K_{\max}E_{\max}}{a^{c}(\eta_{\min}+\eta_{\max})T}}&\text{ {\em[Cosine LR (\ref{cosine})]}}\\ \displaystyle{\frac{3(p+1)\eta_{\max}^{2}K_{\max}E_{\max}}{a^{c}(\eta_{\max}+\eta_{\min}p)T}}&\text{ {\em[Polynomial LR (\ref{polynomial})]}}\end{cases}\quad\text{ {\em([Polynomial BS (\ref{polynomial_bs})])}}$ $\displaystyle V_{T}\leq\begin{cases}\displaystyle{\frac{\gamma\eta K_{\max}E_{\max}}{(\gamma-1)b_{0}T}}&\text{ {\em[Constant LR (\ref{constant})]}}\\ \displaystyle{\frac{\gamma\eta K_{\max}E_{\max}}{2(\gamma-1)b_{0}(\sqrt{T+1}-1)}}&\text{ {\em[Diminishing LR (\ref{diminishing})]}}\\ \displaystyle{\frac{2\gamma\eta_{\max}^{2}K_{\max}E_{\max}}{(\gamma-1)(\eta_{\min}+\eta_{\max})b_{0}T}}&\text{ {\em[Cosine LR (\ref{cosine})]}}\\ \displaystyle{\frac{(p+1)\gamma\eta_{\max}^{2}K_{\max}E_{\max}}{(\gamma-1)(\eta_{\max}+\eta_{\min}p)b_{0}T}}&\text{ {\em[Polynomial LR (\ref{polynomial})]}}.\end{cases}\text{ {\em([Exponential BS (\ref{exponential_bs})])}}$ $$

That is, Algorithm [1](#alg1) using each of
Polynomial BS ([9](#S3.E9)) and
Exponential BS ([10](#S3.E10)) has the convergence rate

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|\right]=\begin{cases}\displaystyle{O\left(\frac{1}{\sqrt{T}}\right)}&\text{ {\em[Constant LR (\ref{constant}), Cosine LR (\ref{cosine}), Polynomial LR (\ref{polynomial})]}}\\ \displaystyle{O\left(\frac{1}{T^{\frac{1}{4}}}\right)}&\text{ {\em[Diminishing LR (\ref{diminishing})]}}.\end{cases}$ $$

Proof of Theorem [A.1](#A1.Thmtheorem1):
Let $M\in\mathbb{N}$ and $T=\sum_{m=0}^{M}K_{m}E_{m}$,
where $E_{\max}=\sup_{M\in\mathbb{N}}\sup_{m\in[0:M]}E_{m}<+\infty$, $K_{\max}=\sup_{M\in\mathbb{N}}\sup_{m\in[0:M]}K_{m}<+\infty$,
$S_{0}:=\mathbb{N}\cap[0,K_{0}E_{0})$,
and
$S_{m}=\mathbb{N}\cap[\sum_{k=0}^{m-1}K_{k}E_{k},\sum_{k=0}^{m}K_{k}E_{k})$ ($m\in[M]$).
Let us consider using ([9](#S3.E9)).

[Constant LR ([2](#S3.E2))]
Let $m\in[M]$. We have that

$$ $\displaystyle\sum_{t\in S_{m}}\frac{1}{b_{t}}$ $\displaystyle=\sum_{t\in S_{m}}\frac{1}{\left(am\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil+b_{0}\right)^{c}}\leq\sum_{t\in S_{m}}\frac{1}{a^{c}m^{c}\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil^{c}}$ $\displaystyle\leq\sum_{t\in S_{m}}\frac{1}{a^{c}m^{c}}\leq\frac{1}{a^{c}m^{c}}K_{m}E_{m}\leq\frac{K_{\max}E_{\max}}{a^{c}}\frac{1}{m^{c}}$ $$

and

$$ $\displaystyle\sum_{t\in S_{0}}\frac{1}{b_{t}}=\sum_{t\in S_{0}}\frac{1}{\left(a\left\lceil\frac{t}{K_{0}E_{0}}\right\rceil+b_{0}\right)^{c}}\leq\frac{K_{\max}E_{\max}}{a^{c}}.$ $$

Accordingly, we have that

$$ $\displaystyle\begin{split}\sum_{m=0}^{M}\sum_{t\in S_{m}}\frac{1}{b_{t}}&\leq\frac{K_{\max}E_{\max}}{a^{c}}\left(1+\sum_{m=1}^{M}\frac{1}{m^{c}}\right)\leq\frac{K_{\max}E_{\max}}{a^{c}}\left(1+\sum_{m=1}^{+\infty}\frac{1}{m^{c}}\right)\\ &\leq\frac{3K_{\max}E_{\max}}{a^{c}}.\end{split}$ (23) $$

Hence, we have that

$$ $\displaystyle V_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta}\sum_{t=0}^{T-1}\frac{\eta^{2}}{b_{t}}\leq\frac{3\eta K_{\max}E_{\max}}{a^{c}T}.$ $$

[Diminishing LR ([3](#S3.E3))]
From ([23](#A1.E23)), we have that

$$ $\displaystyle V_{T}$ $\displaystyle=\frac{1}{\sum_{t=0}^{T-1}\frac{\eta}{\sqrt{t+1}}}\sum_{t=0}^{T-1}\frac{\eta^{2}}{(t+1)b_{t}}$ $\displaystyle\leq\frac{\eta}{2(\sqrt{T+1}-1)}\sum_{t=0}^{T-1}\frac{1}{b_{t}}\leq\frac{3\eta K_{\max}E_{\max}}{2a^{c}(\sqrt{T+1}-1)}.$ $$

[Cosine LR ([4](#S3.E4))]
The cosine LR is defined for all $m\in[0:M]$ and all $t\in S_{m}$ by

$$ $\displaystyle\eta_{t}=\eta_{\min}+\frac{\eta_{\max}-\eta_{\min}}{2}\left\{1+\cos\left(\sum_{k=0}^{m-1}E_{k}+\left\lfloor\frac{t-\sum_{k=0}^{m-1}K_{k}E_{k}}{K_{m}}\right\rfloor\right)\frac{\pi}{E_{M}}\right\}.$ $$

We have that

$$ $\displaystyle\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\eta_{\max}^{2}\sum_{t=0}^{T-1}\frac{1}{b_{t}},$ $$

which, together with ([23](#A1.E23)), implies that

$$ $\displaystyle\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\frac{3\eta_{\max}^{2}K_{\max}E_{\max}}{a^{c}}.$ $$

Hence, we have that

$$ $\displaystyle V_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\frac{6\eta_{\max}^{2}K_{\max}E_{\max}}{a^{c}(\eta_{\min}+\eta_{\max})T}.$ $$

[Polynomial LR ([5](#S3.E5))]
We have that

$$ $\displaystyle\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}=\sum_{t=0}^{T-1}\frac{1}{b_{t}}\left\{(\eta_{\max}-\eta_{\min})\left(1-\frac{t}{T}\right)^{p}+\eta_{\min}\right\}^{2}\leq\eta_{\max}^{2}\sum_{t=0}^{T-1}\frac{1}{b_{t}},$ $$

which, together with ([23](#A1.E23)), implies that

$$ $\displaystyle\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\frac{3\eta_{\max}^{2}K_{\max}E_{\max}}{a^{c}}.$ $$

Hence, we have that

$$ $\displaystyle V_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\frac{3(p+1)\eta_{\max}^{2}K_{\max}E_{\max}}{a^{c}(\eta_{\max}+\eta_{\min}p)T}.$ $$

Let us consider using ([10](#S3.E10)).

[Constant LR ([2](#S3.E2))]
We have that

$$ $\displaystyle\sum_{t\in S_{m}}\frac{1}{b_{t}}$ $\displaystyle=\sum_{t\in S_{m}}\frac{1}{\gamma^{m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil}b_{0}}\leq\sum_{t\in S_{m}}\frac{1}{\gamma^{m}b_{0}}\leq\frac{K_{\max}E_{\max}}{\gamma^{m}b_{0}},$ $$

which implies that

$$ $\displaystyle\sum_{m=0}^{M}\sum_{t\in S_{m}}\frac{1}{b_{t}}\leq\frac{K_{\max}E_{\max}}{b_{0}}\sum_{m=0}^{M}\frac{1}{\gamma^{m}}\leq\frac{K_{\max}E_{\max}\gamma}{b_{0}(\gamma-1)}.$ (24) $$

Hence, we have that

$$ $\displaystyle V_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta}\sum_{t=0}^{T-1}\frac{\eta^{2}}{b_{t}}\leq\frac{\eta K_{\max}E_{\max}\gamma}{b_{0}(\gamma-1)T}.$ $$

[Diminishing LR ([3](#S3.E3))]
From ([24](#A1.E24)), we have that

$$ $\displaystyle V_{T}$ $\displaystyle=\frac{1}{\sum_{t=0}^{T-1}\frac{\eta}{\sqrt{t+1}}}\sum_{t=0}^{T-1}\frac{\eta^{2}}{(t+1)b_{t}}$ $\displaystyle\leq\frac{\eta}{2(\sqrt{T+1}-1)}\sum_{t=0}^{T-1}\frac{1}{b_{t}}\leq\frac{\eta K_{\max}E_{\max}\gamma}{2(\sqrt{T+1}-1)b_{0}(\gamma-1)}.$ $$

[Cosine LR ([4](#S3.E4))]
We have that

$$ $\displaystyle\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\eta_{\max}^{2}\sum_{t=0}^{T-1}\frac{1}{b_{t}},$ $$

which, together with ([24](#A1.E24)), implies that

$$ $\displaystyle\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\frac{\eta_{\max}^{2}K_{\max}E_{\max}\gamma}{b_{0}(\gamma-1)}.$ $$

Hence, we have that

$$ $\displaystyle V_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\frac{2\eta_{\max}^{2}K_{\max}E_{\max}\gamma}{(\gamma-1)(\eta_{\min}+\eta_{\max})b_{0}T}.$ $$

[Polynomial LR ([5](#S3.E5))]
We have that

$$ $\displaystyle\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}=\sum_{t=0}^{T-1}\frac{1}{b_{t}}\left\{(\eta_{\max}-\eta_{\min})\left(1-\frac{t}{T}\right)^{p}+\eta_{\min}\right\}^{2}\leq\eta_{\max}^{2}\sum_{t=0}^{T-1}\frac{1}{b_{t}},$ $$

which, together with ([24](#A1.E24)), implies that

$$ $\displaystyle\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\frac{\eta_{\max}^{2}K_{\max}E_{\max}\gamma}{b_{0}(\gamma-1)}.$ $$

Hence, we have that

$$ $\displaystyle V_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\frac{(p+1)\eta_{\max}^{2}K_{\max}E_{\max}\gamma}{(\gamma-1)(\eta_{\max}+\eta_{\min}p)b_{0}T}.$ $$

$\Box$

Example of $b_{t}$ and $\eta_{t}$ satisfying ([11](#S3.E11)) is as follows:

$$ $\displaystyle\begin{split}&\text{[Polynomial growth BS and LR]}\\ &b_{t}=\left(a_{1}m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil+b_{0}\right)^{c_{1}},\text{ }\eta_{t}=\left(a_{2}m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil+\eta_{0}\right)^{c_{2}},\end{split}$ (25) $$

where $a_{1},a_{2}>0$; $c_{1}>1$, $c_{2}>0$ such that $c_{1}-2c_{2}>1$.

We next show the following theorem, which includes Theorem [3.3](#S3.Thmtheorem3).

###### Theorem A.2 (Convergence rate of SGD using ( 11 )).

Under the assumptions in Lemma [2.1](#S2.Thmlemma1),
Algorithm [1](#alg1) using ([11](#S3.E11)) satisfies that, for all $M\in\mathbb{N}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|^{2}\right]\leq\frac{2(f(\bm{\theta}_{0})-f^{\star})}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}}_{B_{T}}+\frac{L_{n}\sigma^{2}}{2-L_{n}\eta_{\max}}\underbrace{\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}}_{V_{T}},$ $$

where $T=\sum_{m=0}^{M}K_{m}E_{m}$,
$E_{\max}=\sup_{M\in\mathbb{N}}\sup_{m\in[0:M]}E_{m}<+\infty$,
$E_{\min}=\inf_{M\in\mathbb{N}}\inf_{m\in[0:M]}E_{m}<+\infty$,
$K_{\max}=\sup_{M\in\mathbb{N}}\sup_{m\in[0:M]}K_{m}<+\infty$,
$K_{\min}=\inf_{M\in\mathbb{N}}\inf_{m\in[0:M]}K_{m}<+\infty$,
$\underline{\eta}=\min\{a_{2},\eta_{0}\}$,
$\overline{\eta}=\max\{a_{2},\eta_{0}\}$,
$\underline{b}=\min\{a_{1},b_{0}\}$,
$\hat{\gamma}=\frac{\gamma^{2}}{\delta}<1$,

$$ $\displaystyle B_{T}\leq\begin{cases}\displaystyle{\frac{1+c_{2}}{\underline{\eta}^{c_{2}}K_{\min}E_{\min}M^{1+c_{2}}}}&\text{ {\em[Polynomial growth BS and LR (\ref{scheduler_4})]}}\\ \displaystyle{\frac{\delta}{\eta_{0}K_{\min}E_{\min}\gamma^{M}}}&\text{ {\em[Exponential growth BS and LR (\ref{scheduler_5})]}}\end{cases}$ $\displaystyle V_{T}\leq\begin{cases}\displaystyle{\frac{2K_{\max}E_{\max}(1+c_{2})\overline{\eta}^{2c_{2}}}{K_{\min}E_{\min}\underline{\eta}^{c_{2}}\underline{b}^{c_{1}}M^{1+c_{2}}}}&\text{ {\em[Polynomial growth BS and LR (\ref{scheduler_4})]}}\\ \displaystyle{\frac{K_{\max}E_{\max}\eta_{0}\delta}{K_{\min}E_{\min}b_{0}(1-\hat{\gamma})\gamma^{M}}}&\text{ {\em[Exponential growth BS and LR (\ref{scheduler_5})]}}.\end{cases}$ $$

That is, Algorithm [1](#alg1) has the convergence rate

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\|\nabla f(\bm{\theta}_{t})\|\right]=\begin{cases}\displaystyle{O\left(\frac{1}{M^{\frac{1+c_{2}}{2}}}\right)}&\text{ {\em[Polynomial growth BS and LR (\ref{scheduler_4})]}}\\ \displaystyle{O\left(\frac{1}{\gamma^{\frac{M}{2}}}\right)}&\text{ {\em[Exponential growth BS and LR (\ref{scheduler_5})]}}.\end{cases}$ $$

Proof of Theorem [A.2](#A1.Thmtheorem2):
Let $M\in\mathbb{N}$ and $T=\sum_{m=0}^{M}K_{m}E_{m}$,
where $E_{\max}=\sup_{M\in\mathbb{N}}\sup_{m\in[0:M]}E_{m}<+\infty$, $K_{\max}=\sup_{M\in\mathbb{N}}\sup_{m\in[0:M]}K_{m}<+\infty$,
$S_{0}:=\mathbb{N}\cap[0,K_{0}E_{0})$,
and
$S_{m}=\mathbb{N}\cap[\sum_{k=0}^{m-1}K_{k}E_{k},\sum_{k=0}^{m}K_{k}E_{k})$ ($m\in[M]$).

[Polynomial growth BS and LR ([25](#A1.E25))]
We have that

$$ $\displaystyle\sum_{t\in S_{m}}\eta_{t}=\sum_{t\in S_{m}}\left(a_{2}m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil+\eta_{0}\right)^{c_{2}}\geq\sum_{t\in S_{m}}\left(a_{2}m+\eta_{0}\right)^{c_{2}},$ $$

which, together with $\underline{\eta}=\min\{a_{2},\eta_{0}\}$, implies that

$$ $\displaystyle\sum_{t\in S_{m}}\eta_{t}\geq\underline{\eta}^{c_{2}}\sum_{t\in S_{m}}(m+1)^{c_{2}}\geq\underline{\eta}^{c_{2}}K_{\min}E_{\min}(m+1)^{c_{2}}.$ $$

Hence,

$$ $\displaystyle\sum_{m=0}^{M}\sum_{t\in S_{m}}\eta_{t}\geq\underline{\eta}^{c_{2}}K_{\min}E_{\min}\sum_{m=1}^{M+1}m^{c_{2}}\geq\frac{\underline{\eta}^{c_{2}}K_{\min}E_{\min}}{1+c_{2}}M^{1+c_{2}}.$ $$

We also have that

$$ $\displaystyle\sum_{t\in S_{m}}\frac{\eta_{t}^{2}}{b_{t}}=\sum_{t\in S_{m}}\frac{\left(a_{2}m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil+\eta_{0}\right)^{2c_{2}}}{\left(a_{1}m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil+b_{0}\right)^{c_{1}}}\leq\sum_{t\in S_{m}}\frac{\left(a_{2}m+\eta_{0}\right)^{2c_{2}}}{\left(a_{1}m+b_{0}\right)^{c_{1}}}.$ $$

Let $\overline{\eta}=\max\{a_{2},\eta_{0}\}$
and
$\underline{b}=\min\{a_{1},b_{0}\}$.
Then,

$$ $\displaystyle\sum_{m=0}^{M}\sum_{t\in S_{m}}\frac{\eta_{t}^{2}}{b_{t}}$ $\displaystyle\leq K_{\max}E_{\max}\frac{\overline{\eta}^{2c_{2}}}{\underline{b}^{c_{1}}}\sum_{m=0}^{M}\frac{(m+1)^{2c_{2}}}{(m+1)^{c_{1}}}\leq K_{\max}E_{\max}\frac{\overline{\eta}^{2c_{2}}}{\underline{b}^{c_{1}}}\sum_{m=1}^{M+1}\frac{1}{m^{c_{1}-2c_{2}}}$ $\displaystyle\leq\frac{2K_{\max}E_{\max}\overline{\eta}^{2c_{2}}}{\underline{b}^{c_{1}}}.$ $$

Hence,

$$ $\displaystyle B_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\leq\frac{1+c_{2}}{\underline{\eta}^{c_{2}}K_{\min}E_{\min}M^{1+c_{2}}}$ $$

and

$$ $\displaystyle V_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\frac{2K_{\max}E_{\max}(1+c_{2})\overline{\eta}^{2c_{2}}}{K_{\min}E_{\min}\underline{\eta}^{c_{2}}\underline{b}^{c_{1}}M^{1+c_{2}}}.$ $$

[Exponential growth BS and LR ([12](#S3.E12))]
We have that

$$ $\displaystyle\sum_{m=0}^{M}\sum_{t\in S_{m}}\eta_{t}$ $\displaystyle=\sum_{m=0}^{M}\sum_{t\in S_{m}}\gamma^{m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil}\eta_{0}\geq\eta_{0}K_{\min}E_{\min}\sum_{m=0}^{M}\gamma^{m}$ $\displaystyle=\eta_{0}K_{\min}E_{\min}\frac{\gamma^{M}-1}{\gamma-1}>\frac{\eta_{0}K_{\min}E_{\min}\gamma^{M}}{\gamma^{2}}>\frac{\eta_{0}K_{\min}E_{\min}\gamma^{M}}{\delta}$ $$

and

$$ $\displaystyle\sum_{m=0}^{M}\sum_{t\in S_{m}}\frac{\eta_{t}^{2}}{b_{t}}$ $\displaystyle=\sum_{m=0}^{M}\sum_{t\in S_{m}}\frac{\gamma^{2m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil}\eta_{0}^{2}}{\delta^{m\left\lceil\frac{t}{\sum_{k=0}^{m}K_{k}E_{k}}\right\rceil}b_{0}}\leq K_{\max}E_{\max}\frac{\eta_{0}^{2}}{b_{0}}\sum_{m=0}^{M}\frac{\gamma^{2m}}{\delta^{m}}$ $\displaystyle\leq K_{\max}E_{\max}\frac{\eta_{0}^{2}}{b_{0}}\sum_{m=0}^{M}\left(\frac{\gamma^{2}}{\delta}\right)^{m}\leq K_{\max}E_{\max}\frac{\eta_{0}^{2}}{b_{0}}\frac{1}{1-\hat{\gamma}},$ $$

where
$\hat{\gamma}=\frac{\gamma^{2}}{\delta}<1$.
Hence,

$$ $\displaystyle B_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\leq\frac{\delta}{\eta_{0}K_{\min}E_{\min}\gamma^{M}}$ $$

and

$$ $\displaystyle V_{T}=\frac{1}{\sum_{t=0}^{T-1}\eta_{t}}\sum_{t=0}^{T-1}\frac{\eta_{t}^{2}}{b_{t}}\leq\frac{K_{\max}E_{\max}\eta_{0}\delta}{K_{\min}E_{\min}b_{0}(1-\hat{\gamma})\gamma^{M}}.$ $$

$\Box$

Proof of Theorem [3.4](#S3.Thmtheorem4):
Theorem [3.4](#S3.Thmtheorem4) follows immediately from Theorems [3.2](#S3.Thmtheorem2) and [3.3](#S3.Thmtheorem3). $\Box$

###### Theorem A.1 (Convergence rate of SGD using ( 8 )).

###### Theorem A.2 (Convergence rate of SGD using ( 11 )).

### A.3 Training Wide-ResNet-28-10 on CIFAR100

Figure: (a) Learning rate $\eta_{t}$ and batch size $b$ versus epochs
Refer to caption: /html/2409.08770/assets/x21.png

Figure: (a) Learning rate $\eta_{t}$ and batch size $b_{t}$ versus epochs
Refer to caption: /html/2409.08770/assets/x25.png

Figure: (a) Learning rate $\eta_{t}$ and batch size $b_{t}$ versus epochs
Refer to caption: /html/2409.08770/assets/x29.png

Figure: (a) Learning rate $\eta_{t}$ and batch size $b_{t}$ versus epochs
Refer to caption: /html/2409.08770/assets/x33.png

Figure: (a) Learning rate $\eta_{t}$ and batch size $b_{t}$ versus epochs
Refer to caption: /html/2409.08770/assets/x37.png

### A.4 Training ResNet18 on Tiny ImageNet

Figure: (a) Learning rate $\eta_{t}$ and batch size $b$ versus epochs
Refer to caption: /html/2409.08770/assets/x41.png

Figure: (a) Learning rate $\eta_{t}$ and batch size $b_{t}$ versus epochs
Refer to caption: /html/2409.08770/assets/x45.png

Figure: (a) Learning rate $\eta_{t}$ and batch size $b_{t}$ versus epochs
[Uncaptioned image]: /html/2409.08770/assets/x49.png

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: I would encourage the authors to respond to the points listed as weaknesses (1) and (2). It is quite possible that I am misunderstanding something here.
soundness: 2
strengths: - The paper is generally well-written.
- The work is adequately positioned in the context of related work.
- The paper explicitly compares various batch size and learning rate schedules, demonstrating and contrasting quite clearly the effect of these choices.
summary: This paper presents a convergence analysis of mini-batch stochastic gradient descent which highlights the interplay of batch size and learning rate schedules. The paper then proceeds to apply this analysis to various combinations of batch size and learning rate schedules.
weaknesses: 1) The main issue I see with the paper is that the convergence analysis is formulated purely in terms of the number of steps $T$, without regard to the cost per step of different batch size schedules. In particular, if my understanding is correct, this pertains to the main conclusion (in the title) that "increasing both batch size and learning rate accelerates stochastic gradient descent". This statement is rather void if acceleration means it requires fewer steps, but each step is (after a certain point) more expensive.
2) I have some reservations about the correctness of the analysis with increasing batch size and learning rate. The learning rate grows exponentially without an upper bound. Irrespective of batch size / stochasticity, this should not lead to convergence. Shouldn't a simple noise-free quadratic $f_i(\theta) = \Vert \theta \Vert^2$ be a counter-example?
3) The bounded noise assumption (Assumption 2.1, A2) is quite strong. In my experience, it can often be weakened to a quadratically bounded noise, such as $\mathbb{V}[\nabla f_\xi ] \leq a + b\Vert \nabla f_\xi\Vert^2$.
4) Minor nitpick: The notation $L_n$ is ambiguous and could be replaced with somethign like $\bar{L}$.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 2
questions: I think there needs to be a sufficient increase in theoretical contribution, if possible. Alternatively, or in addition to it, I think the paper requires extensive additional experimentation to support the claims of faster convergence of the proposed scheduler.
soundness: 2
strengths: There is a wide range of schedulers that are popular in practice. Their effect on the bound from the descent lemma is very clearly presented. The assumptions are clearly stated and the statements are rigorous.
summary: The paper presents a theoretical analysis of different learning rates and batch size schedulers in the case of mini-batch SGD. They theoretically provide a justification for a scheduler that increases the learning rate as it increases the batch size to accelerate convergence of SGD.
weaknesses: I am uncertain whether this paper provides a substantial contribution. From a theoretical perspective, the primary upper bound utilized, Lemma 2.1, is a fairly standard result, which limits the theoretical novelty primarily to a detailed analysis of the \(B_T\) and \(V_T\) terms across different schedulers. While the analysis is rigorous, the bounds derived are relatively coarse, and the results may not provide sufficient novelty. The findings on SGD speed-ups with corresponding schedulers also align with expected outcomes—namely, that increasing batch size accelerates SGD by reducing noise, and increasing the learning rate speeds up convergence. Theorem 3.4, in particular, seems a straightforward combination of these established insights. On the other hand it doesn’t really explain why we need learning rate warm-up and not just start with a high learning rate. Moreover, I am not sure there is a confirmation for the claim in introduction, part (iv): “using mini-batch SGD with increasing batch sizes and decaying learning rates with a warm-up minimizes [..] faster than using a constant learning rate in Case (ii) or increasing learning rates in Case (iii)” - I am not sure this agrees with the results of Section 3.4 or the claims in the abstract. That is, I am not sure some of the claims of the paper are stated consistently.

From a practical and empirical standpoint, I have additional reservations. Specifically, the proposed bound generally does not constitute a tight upper bound on the rate of convergence, and its applicability is limited by certain assumptions. Furthermore, there appears to be insufficient empirical evidence to substantiate the claims regarding the practical effectiveness of schedules that simultaneously increase learning rate and batch size, or increasing batch size with decaying lr with warm-up.

---

confidence: 5
contribution: 1
initial_rating: 1
presentation: 2
questions: See the weaknesses section.
soundness: 2
strengths: The paper presents a comprehensive analysis of different choices of learning rates and batch sizes for optimizing a nonconvex and smooth objective.
summary: This paper provides a convergence analysis of stochastic gradient descent (SGD) with various learning rates and batch sizes. Some experiments on image classification tasks in deep learning are conducted to verify the theoretical results.
weaknesses: 1. The theoretical proofs are straightforward extensions of SGD analysis (e.g., Ghadimi and Lan 2013), which have limited technical novelty.

2. There are limited discussions about why some learning rate/batch size choices are preferred in practice, as well as the connection between the theoretical and empirical results. 

2. The main message of this paper about increasing both batch size and learning rate is well-known in the literature (e.g., Goyal et al. 2018), which significantly weakens the contribution of this paper.

3. The experimental results offer limited insight compared with (Goyal et al. 2018).

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: no
soundness: 2
strengths: The paper is clearly written. Theoretical proofs seem correct. Most of the currently popular schedulers are analyzed/discussed in the paper.
summary: This paper analyzes the dependence of a SGD convergence upper bound on different scheduling strategies of learning rate and batch size. Specifically, it conveys the summation terms in the upper bound for several popularly used scheduling strategies. Based on these upper bound analysis, it further claims that increasing batch size and learning rate can accelerate the SGD training.
weaknesses: 1. The analysis of the paper is quite simple and straightforward. It basically just conveyed the summation over time $T$ (appeared in Lemma 2.1), for several popular scheduling methods. For each of these schedulings, the step size function and batch size function are already well-defined. It is just a matter of elementary level of math to write out these summation or their upper bounds. Therefore, the paper is not technically strong.

2. The analysis and claims are only based on a single upper bound expression (Lemma 2.1). It is unclear how loose the bound is. Note that having a smaller upper bound does not mean having a faster convergence, especially when the bound is very loose.

I am suspicious about the claim of acceleration via an increasing learning rate schedule. Typically, having a constant learning rate with a value that is similar to the largest value of the learning rate scheduling should have a faster convergence than the increasing scheduling. However, the paper claims the opposite. One possibility is that the bound itself is not tight enough to reflect the true trend; another is that the constant absorbed by $O()$ may not be ignored. 

3. It is inappropriate to consider the constant learning rate as a “decaying” learning rate.

4. In Lemma 2.1, the optimal loss $f^* $ should not be equivalent to the average of $f_i^* $. Note that the optimal solution of each individual loss $f_i$ is generally not the same as the optimal solution $\theta^* $. Therefore, $f^* = 1/n \sum f_i^* $ is generally not true.