Critical Batch Size Minimizes Stochastic First-Order Oracle Complexity of Deep Learning Optimizer using Hyperparameters Close to One
Authors: Hideaki Iiduka
Venue: Submitted to ICLR 2023 (2023)
Keywords: Adam
adaptive method
critical batch size
hyperparameters
learning rate
nonconvex optimization
stochastic first-order oracle complexity

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).

Under review as a conference paper at ICLR 2023
CRITICAL BATCH SIZE MINIMIZES STOCHASTIC FIRST-ORDER ORACLE COMPLEXITY OF DEEP LEARNING OPTIMIZER USING HYPERPARAMETERS CLOSE TO ONE
Anonymous authors Paper under double-blind review
ABSTRACT
Practical results have shown that deep learning optimizers using small constant learning rates, hyperparameters close 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 learn- ing rate, hyperparameters close to one, and 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 sults. That is, the numerical results indicate that Adam using a small constant learning rate, hyperparameters close one, and the critical batch size minimizing SFO complexity has faster convergence than Momentum and stochastic gradient descent (SGD).
theoretical re-
INTRODUCTION
1.1 BACKGROUND
Useful deep learning optimizers have been proposed 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) (Robbins Monro, 1951; Zinkevich, 2003; Nemirovski al., 2009: Ghadimi & Lan, 2012; 2013), momentum methods (Polyak, 1964; Nesterov, 1983), and adap- tive methods. The various adaptive methods include Adaptive Gradient (AdaGrad) (Duchi al., 2011), Root Mean Square Propagation (RMSProp) (Tieleman & Hinton, 2012), Adaptive Mo- ment Estimation (Adam) (Kingma & Ba, 2015), Adaptive Mean Square Gradient (AMSGrad) (Reddi et al., 2018), Yogi (Zaheer et al., 2018), Adam with decoupled weight decay (AdamW) (Loshchilov & Hutter, 2019), and AdaBelief (named for adapting stepsizes by the belief in observed gradients) (Zhuang et al., 2020).
Theoretical analyses of adaptive methods for nonconvex optimization were presented in (Zaheer et al., 2018: Zou et al., 2019; Chen et al., 2019; Zhou et al., 2020; Zhuang al., 2020; Chen et al., 2021) (see (Jain et al., 2018; Fehrman et al., 2020: Chen et al., 2020; Scaman & Malherbe, 2020: Loizou al., 2021) for convergence analyses of SGD). A particularly interesting feature of adaptive methods is the use of hyperparameters denoted by 31 and 83, that can be set to influence the method performance P(K) := * Σk= B[]lV/(Ox)) gradient of loss function f: Rd - R. (0x) is the sequence generated by optimizer, and K is the number of steps. The previous results are summarized in Table indicating that using Bn and/or 32 close to 0 makes the upper bound of P(K) small (see also Appendix A.1).
where V is the
Meanwhile, practical results for adaptive methods were presented in (Kingma & Ba, 2015; Reddi et al., 2018; Zaheer et al., 2018; Zou al., 2019; Chen et al., 2019; Zhuang al., 2020;

---

Under review as a conference paper at ICLR 2023
Chen et al., 2021). These studies have shown that using, for example, 81 {0.9, 0.99) and 32 E {0.99, 0.999} provides superior performance for training deep neural networks. The prac- tically useful 31 and 32 are each close to 1, whereas in contrast, the theoretical results (Table 1) show that using 31 and/or B2 close to makes the upper bounds of the performance measures small.
Table Upper bounds of performance measure of optimizers with learning rate og and hyperparam- eters B1 and 32 (G > 0, E (0, 1/2), T. denotes the Lipschitz constant of the Lipschitz continuous gradient of the loss function f. K denotes the number of steps, b the batch size, Ol max depends on 6 and the largest cigenvalue of the Hessian of f h is monotone decreasing function with respect to 31, and C3 is defined as in Table 2. 3 x a implies that, if close to a, then the upper bounds are small.) Optimizer
Learning Rate ox
Parameters 31, 82
Upper Bound
1
Tail-averaged SGD
(Ob.max)
31 = 0
0
K2
Kb
(Jain et al., 2018)
B2 = 0
1
Adam
L
81 = 0
0
K
+
b)
(Zaheer et al., 2018)
32 2
G
(
log K VK
Generic Adam
0
31 ~ 0,
0
Vk
1
(Zou et al., 2019)
82
R1
1
log K VK
AdaFom
0
1
Vk
(Chen al., 2019)
AMSGrad
a
0 3 < V
K K3-8
(Zhou al., 2020)
log K VK
AdaBelicf
0,
Vk
(Zhuang al., 2020)
Padam
a = 00
o
K -
(Chen et al., 2021)
Adam, AMSGrad
a
1,8281
+ Ca
(this paper)
varying Okk
R 1 0
K Kb h(31)
+
The practical performance of deep learning optimizer strongly depends on the batch size. In (Smith et al., 2018), it was numerically shown that using an enormous batch size leads to a re- duction the number of parameter updates and model training time. The theoretical results in (Zaheer et al., 2018) showed that using large batch sizes makes the upper bound of P(K) of an adaptive method small (Table 1). Convergence analyses of SGD (Cotter et al., 2011: 1; Chen al., 2020; Arjevani et al., 2022) indicated that running SGD with decaying lcarning 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 (Shallue et al., 2019; Zhang et al., 2019), was studied how increasing the batch size affects the performances of deep learning optimizers. In both studies, it numerically shown that increas- ing batch size tends to decrease the number of steps K needed for training deep neural networks, but with diminishing returns. Moreover, it shown that momentum methods exploit larger
2

---

Under review as a conference paper at ICLR 2023
batches than SGD (Shallue et al., 2019), and that K-FAC and Adam can exploit larger batches than momentum methods (Zhang et al., 2019).
1.2 MOTIVATION
1.2.1
HYPERPARAMETER, CLOSE TO ONE AND CONSTANT LEARNING RATE
As described in Section 1.1, the practically useful B1 and B2 are each close to 1, whereas in contrast, the theoretical results show that using B1 and/or 32 close to 0 makes the upper bounds of the perfor- mance measures small. Hence, there is gap between theory (31, B2 = 0) and practice (31, /8 1) for adaptive methods. As consequence, the first motivation of this paper is to bridge this gap.
Since using small constant learning rates robust for training deep neural networks (Kingma & Ba, 2015; Reddi et al., 2018; 8; Zaheer et al., 201 8; Zou et al., 2019; Chen et al., 2019; Zhuang et al., 2020; Chen et al., 2021), we focus on using a small constant learning rate a. Here, we note that using a learning rate depending
the Lipschitz constant L of the gradient ff would be unrealistic. This is because computing the Lipschitz constant L is NP-hard (Virmaux & Scaman, 2018, Theorem 2). The results ("(this paper)" row in Table I) using varying learning rates are given in Appendix A.4.
1.2.2 CRITICAL BATCH SIZE
The second motivation of this paper is to clarify theoretically the relationship between the dimin- ishing returns reported in (Shallue et al., 2019: Zhang et al., 2019) and batch size. Numerical eval- uations in (Shallue et al., 2019; Zhang et al., 2019) have definitively shown that, for deep learning optimizers, the number of steps K needed train a deep neural network halves for each doubling of the batch size b and that there is region of diminishing returns beyond the critical batch size b*. This implies that there is a positive number C such that
Kb = 2c for b S b* and Kb 2 2 for b b-24 b",
where K and are defined for i,j N by K 2' and b = 2 (For example, Figure Section 4 shows C' z 20 and b' = 211 for Adam used to train ResNet-20 on the CIFAR-10 dataset). We define the stochastic first-order oracle (SFO) complexity 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" be a critical batch size such that there are diminishing returns for all batch sizes beyond b", asserted in (Shallue et al., 2019; Zhang et al., 2019). This fact, expressed in (1), implies that, while SFO complexity N initially almost does not change (i.e., K halves for each doubling of b), N is minimized at critical batch size b*, and there are diminishing returns once the batch size exceeds b*.
a deep learning optimizer as N K
1.3 CONTRIBUTION
Our results are summarized in Table 2 (see also the "(this paper)" row in Table 1). Our goal is
to find a local minimizer of loss function ff over Rd, i.e., a stationary point 6* E IR satisfying ff(0)) = 0. which is equivalent to the variational inequality (VI) defined for all 0 Rd by
VS(0)) (0- 0) < 0. Here, we show the relationship between (i) E [ (0p 0)
I c (k E N), where e > 0 the precision. Let us assume that (0x (ON) is bounded. Suppose that (i) holds. Then, there exists a subsequence (0x,)ie of (O KeN such that (Ox,)en converges to 0-, The continuity of V thus implies that, for all 0 E Rdd (( (0" -0] S e. Putting 0 = 0" -V f00) ensures that (( )[l] S e. Suppose that (ii) holds. Then, the definition of the inner product and Jensen's 's inequality imply that, for all e E Rd,
(0 Rd k N) and (ii) (
(O,) (0,, 0) Dist(O)/e where Dist( (0) == sup ||0 - 01| k E N) < toc. Therefore,
is adequate to use (i) and c-approximation VI(K, 0) K > (V) (0)- 0)] I c (Table 2) as the performance measure of an optimizer.
1.3.1 ADVANTAGE OF SETTING A SMALL CONSTANT LEARNING RATE AND HYPERPARAMETERS CLOSE TO ONE
We can show that the upper bound C1 + 6 + C3 of VI(K, 0) becomes small when is small, $1 and B3 are close to 1. and K is large. This implies that Momentum and Adam perform well when a is small and 31 and (g are each set close to 1. Section 3.1 shows this result in detail.
3

---

Under review as a conference paper at ICLR 2023
Table Relationship between batch size b and the number of steps K to achieve an e-approximation
of an optimizer using constant learning rate a and hyperparameters 31, .2. The critical batch size
b' minimizes SFO complexity N (G, o², M, and v, are positive constants, D(0) is a positive real
number depending on 0 E Rd and h is monotone decreasing with respect to (1)
Optimizer
SGD
Momentum
Adam
E 0
0
E|l
0
dD(O) M
C1
2a
20
20:31 v1 33
a²a
o²a
o²a
C2
2
2,31
/0,,31 (1 - (31)
G
G2
G²
C
+ +B1)
+ +((3))
2
2,31
2/0.31 - (1)
1
C1
C2
Upper Bound of VI
VI(K, 0) =
E [VV(()))
(0, - -0]] -
+
+ C3 =c
K
K
b
k=1
C1b
Cib²
Steps K and SFO N
K
N =
Cz)b C2
(e 0z)b C2
11* 202
Critical Batch b*
( C3
1.3.2 CRITICAL BATCH SIZE
As described in Section 1.2.2, the practical performance of deep learning optimizer strongly de- pends on the batch size (Shallue et al., 2019; Zhang et al., 2019). The advantage of this paper to clarify theoretically the relationship between batch size and the performance of deep learn- ing optimizers and develop a theory demonstrating the existence of critical batch sizes, which was shown numerically by (Shallue et al., 2019: Zhang et al., 2019). Motivated by the results in (Shallue et al., 2019; Zhang et al., 2019) and Section 1.2.2, we use SFO complexity N := as the performance measure of a deep learning optimizer. We first show that the number steps K to sat- isty VI(K, 0) < can be defined as in Table 2. As a function, K is convex and monotone decreasing with respect to batch size b. Next, we show that SFO complexity N defined as in Table 2 convex with respect to batch size b. This result agrees with the fact of (1). Moreover, SFO complexity N is minimized at 6* defined as in Table 2. This result guarantees the existence of the critical batch size b². Section 3.2 shows the above results in detail. However, the accurate setting of the critical batch size by defined as in Table 2 would be difficult since b' involves unknown parameters, such as G and (0) (see Section 2.2.3). The advantage of our analysis that we can estimate appropriate batch sizes using the formula for 6* before implementing deep learning optimizers. Section 4 will discuss estimation of appropriate batch sizes in detail.
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 ddd be a d-dimensional Euclidean space with inner product (x, y) : x T y inducing the norm ||ж||| and N be the set of nonnegative integers. Define [n|] == 21. for > 1. Given parameter E Rd and a data point = in a data domain Z, a machine learning model provides a prediction whose quality is measured by a differentiable nonconvex loss function E(0; z). We aim to minimize the expected loss defined for all 0 E Rdd by (0) TE [f) EE(;(()), where Dis probability distribution over Z. E denotes a random variable with distribution function P. and B||]] denotes the expectation taken with respect to ç. A particularly interesting example of f(0) is the empirical average loss defined for all 0 E 2dd by [0: 5) n Eiejni {(0: 2)) n. Eiejm) (0)),
where = (z), ......, 2n,) denotes the training set and (,(-) == ((::2) denotes the loss function corresponding to the i-th training data 21.
4

---

Under review as a conference paper at ICLR 2023
2.2
DEEP LEARNING OPTIMIZERS
2.2.1 I
CONDITIONS
We assume that a stochastic first-order oracle (SFO) exists such that, for given 0 E R it returns stochastic gradient (0) of the function f. where random variable supported E indepen- dently of 0, The following are standard conditions when considering deep learning optimizer.
(CI) f: IR + R is continuously differentiable.
(C2) Let (0x)eeN Rd be the sequence generated by deep learning optimizer. For each iteration k Ee, [Ge, (0x) = Vf(0s), where Eo, Ei.... are independent samples and the random variable & is independent of (0:) There exists a nonnegative constant o² such o².
that Eg, g. (0x) vf(
(C3) For each iteration k, the optimizer samples batch B& of size b independently of l and estimates the full gradient ff as ffB. (0x) := & EiEl Gea. (0x), where En,s a random variable generated by the i-th sampling in the k-th iteration.
2.2.2 ADAM
Algorithm is the Adam optimizer (Kingma Ba, 2015) under (CI)-(C3) The symbol in step
6 is defined for all æ = (==) E RRd x O == (x ) E Rd, and diag(a;) in step is diagonal matrix with diagonal components 21, 22, Fdd.
Algorithm 1 Adam (Kingma & Ba, 2015)
Require: a E (0, +:00), b (0, +00), ) B1 (0, 1), (0.1)
1: & +- 0, 0, E Idd m_ = 0-
2: loop
3: V fBB, (0x) 1, E [E G5. (0%)
4: my == 8,m + (1 31 V (0))
m = (1 - 8k+1
5:
m&
6:
Us 82Uk -1 1 (1 82) fB, (0x) o Va,
7:
G (1 3/11 1'
8:
H₂ diag( (k.i)
9:
O OK+1 = O2 aHH m.
10:
++ ++1
11:
end loop
The SGD optimizer under (CI)-(33 is Algorithm when 31 0 and Hş is the identity matrix. The Momentum optimizer under (C1)-(C3) is defined for all l: E N by 0 := 0 am,.
2.2.3 ASSUMPTIONS
We assume the following conditions that were used in (Kingma & Ba, 2015, Theorem 4.1):
(A1) There exist positive numbers G and B such that, for all h E N, (VF(())) < G and [,, (0x) S (see also Appendix A.5).
(A2) For all 0 E RRd, there exists a positive number (is such that, for all E N. | - 0| S Dist(@).
Let (o = (O.) @ (0x) (k E N). Assumption (A1) implies that M =
supfmaxield oh. & N) < too. Assumption (A2) implies that D(0) := sup(max (O), 0.):: A N] +oo. We define v. inf ( th.s: k E N). Theorem 3 in (Reddi al., 2018) shows that there exists a stochastic convex optimization problem such that Adam using 3 /B2 (c.g., B1 0.9 and 8g 0.999) does not converge the optimal solution. for all k E N and all E [d]. Gz in Adam satisfies
Ūet1i 0k.is
(2)
5

---

Under review as a conference paper at ICLR 2023
then Adam with decaying learning rate a;; O( vi and B1 and 32 satisfying $1 < /32 can solve
the stochastic convex optimization problem (Reddi et al., 2018, (2), Theorem 4), We thus assume condition (2) for Adam to guarantee the convergence of Adam.
3
OUR RESULTS
This section states our theoretical results (Theorem 3.1) in Table 2 and our contribution (Sections 3.1 and 3.2) in detail. The proof of Theorem 3.1 is given in Appendix A.3.
Theorem 3.1. The sequence (0x)keN generated by each of SGD, Momentum, and Adam with (2) under (CI) and (AI) and (A2) satisfies the following:
(i) [Upper bound (I(K, [)] For all K 2 and all R.d.
K
Ci C2 K b
VI(K, 0) = Σ
E
Vf(0k)
-0) -
+ + C3.
k=
where Cj (1=1,2,3 (2 for SGD are
E E
1 0
O'a
C3 = Ga
C1 =
C2 ==
2a
2
2
C (i = 1,2,3) for Momentum are
C = E1|00 - -01
0²a
C2
20,11
231
C3 = Ga + Dist((0)
[G(1 [G(1- 31)
(1 +2(1 +2(1-33)) (111-88))
+ +2V
02
G
281
B1
(1
C (i = 1,2, 35,3),,rr for Adam with (2) are
dD(O)vM C2:== 2/0.Bi (B)1)
0²a
C 20,31 /1 - "22
Gaa
{
[G(1 [G(1-B1)
B1)
(1 + - -81)
C3 = 2/ -1 B1)
+ Dist(O)
+ 2 02 G2
31
and the parameters are defined as in Section 2.2.
(ii) [Steps to satisfy VI(K, 0) S c) The number of steps K defined by
G,b
K(b) = (c-Cz)b C2
(3)
satisfies VI(K, 0) S and the the function (b) defined by (3) is convex and monotone decreasing with
respect to batch size b (> Co Ca > 0) (see also Appendix A.6 for the condition - C3 > 0).
(iii) [Minimization of SFO complexity] The SFO complexity defined by
C₂
= K(bbb (c- Cz)b CC C2
(4)
is convex with respect to batch size b (>
Ca > 0). The batch size
c
b¹ 2C₂
(5)
C33
attains the minimum value N = K(bb)b' 40,02 (c-Ca)² N.
The proof of Theorem 3.1 ensures that C, 1,2,3) for AMSGrad (Algorithm with my
mg, 6% Dk. Ūk = max (ūk-1,4, (..i) (i.e., 0x+1,, 2 ūk.i (2)), and H₃. diag( ux,
C dD(0)/M
o²a
C2:=
20
2/0,11
(6)
Pa (0)
[G(1- - 31)
+2 - 1-2(1-18)
-i))
C3
22
02
G
2v0,3
31
3

---

Under review as a conference paper at ICLR 2023
where ë_1 == 0 and 0, := inf (nf(minee]]] 0k,y &o E N) (see Appendix A.3.4).
We give a brief outline of the proof strategy of Theorem 3.1, with an emphasis on the main difficulty that has to be overcome in order not to assume Lipschitz smoothness of f (i.c., f is Lipschitz con- tinuous with the Lipschitz constant L). First, we show that (C2) and (Al) imply that
Il)
and (EE]) DeeN are bounded, where de == = mg. Since we do not assume Lipschitz smooth-
ness of f. we cannot use the descent lemma, i.e., f(y) I [(x) + Vf(x) (y =) + & - æ=|? (x. y Rd). This is the main difficulty to prove Theorem 3.1. Almost all of the previous analyses of adaptive methods are based on the descent lemma, and hence, they can use the expectation of the squared norm of the full gradient Elll V f())) [I²]] as the performance measure. Accordingly, we must use other performance measures that are different from [[)x)(())))))) This paper uses the performance measure VI(K, 0). We next show that Σ - (O2- 0)] S ak + bx + cx S G + Cgk CgK, where C1 and C2 are defined in Theorem 3.1 and C3 O. In particular, (2), (AI), and (A2) imply ax 2 C₁, the boundedness condition of [[[[) IID implies bx S C.K and (A2) and the Cauchy-Schware inequality imply ск S CgK. The definition of m,. the Cauchy- Schwarz inequality, the triangle inequality, and Jensen's 's inequality imply Theorem 3.1 Theorem 3.1 and
C2 + C3 c lead to Theorem 3. (ii) and (iii).
3.1 ADVANTAGE OF SETTING SMALL CONSTANT LEARNING RATE AND IYYPERPARAMETERS CLOSE TO ONE
We first show theoretical evidence that Adam using small constant learning rate a, 31 and B2 close to 1, and a large number of steps K performs well. Theorem 3.1 indicates that the upper bound of VI(K, 0) for Adam is
VI(K, S dD(O)VM) 20 VI -3eK 21
20026-++67
Σ V 82 gk+1 + -(BB),,
(7)
k=1
where 31 E (0, 32 E [0,1), and
h(1))= = (0) { [G(1 (G(1-31 31)
+ +2 -
+ bn))}
+ 2(1 8n))
(8)
B1
31
(the strict evaluation (7) of Theorem 3.1 comes from (31) in Appendix A). Since the function h(3)) defined by (8) is monotone decreasing, using 31 close to makes ((3)) small. Since M(-))
monotone increasing for B1 2 1/2, using 31 close makes 3((--)) large. Hence, we need to
gh+1 is monotone decreasing with set small a to make 00= small. The function /1 3/ (1-b),
respect 32. while using 82 close makes -ーΣ large. When 32 close to 1 and a small learning
rate are used, we need to use large number of steps K to make
AD(O)/M small.
20 VT 3.K
3.2 CRITICAL BATCH SIZE
Theorem 3.i indicates that the number of steps K to satisfy VI(K, 0) < e can be expressed as (3). The function (b) defined by (3) is convex and monotone decreasing. Hence, the form of K defined by (3) supports theoretically the relationship between K and shown (Shallue al., 2019; Zhang et al., 2019) (see also Figures and 3 in this paper). Theorem 3.1 (iii) indicates that SFO complexity defined by (4) is convex with respect to batch size b. This result agrees with the fact of (1) (see also Figures? 2 and 4 in this paper). Moreover, SFO complexity N == Kb is minimized at 6" defined by (5); e.g., bš for SGD, by for Momentum, and b% for Adam are respectively
aga
aa Vo. (1)
bi = (1 Cs.M) 6y c C-Csss'
where dg. J.. and a are positive constants depending on SGD, Momentum, and Adam and C3s Ca.,, Ca,,, Ca, are positive constants defined as in Theorem 3.1. From (9), the lower bounds b* of lg. Uyp and iy are respectively
aza
bg >
b
bi > bb =
by
by
== vo.3i -i)e
(10)
e
Bie¹
7

---

Under review as a conference paper at ICLR 2023
4 NUMERICAL RESULTS
We evaluated the performances of SGD, Momentum, and Adam with different batch sizes. The metries were the number of steps K and the SFO complexity N satisfying f(0x) S 10-1, where xx 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) (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 10 was commonly used. Momentum used B1 0.9. Adam used B = 0.9 and 32 = 0.999 (Kingma & Ba, 2015).
(10) and estimate appropriate batch sizes in the sense that SFO complexity is mini- mized. The definitions of e, and Uk,i (see also (26) in Appendix A) imply that, for k E [K] and all i E [d]. v S Uk.i I maXke K] [dX gh.; - E'= Ri | fB. (0x-) Ill Con- dition (C2) implies that B[Il fB. (0x) S of- + ((+))l (see also (14) in Appendix A). Conditions (C2) and (C3) imply that, if b is large, then a is small. Hence, assuming that
Here,
5 2 im-
plies that v, I flV )11² = 11 Exenn (e,(0,)) )112
E (4,(0x=) )1( =: , G
+ Eig(a id) G I nz maxield Gă- Since deep learning optimizers can approximate stationary points of f. we assume that, for example, Gk-, = c. Then, (10) implies that
o 10
Th 102e
o 10
on
by
b,
(11)
9 10v
Conditions (C2) and (C3) imply that, is large, then is small. SGG and Momentum can exploit large batch sizes, then as and σM are small. However, (11) implies that bi and 1% must be small when as and оы are small. Accordingly, SGD and Momentum would not able to use large batch sizes. Meanwhile, from (11), we expect that Adam can exploit a large batch size by by > bix for example, when 6X* < 2n (CIFAR-100 10; n = 50000, ResNet-20; se 1.1 x 10 bx x 1600) and 210 < 6%* < 2 (MNIST; Leong et al., 2020), where x x 10-2 and c = 10-3 are used.
60000, ResNet-18: 18; d Rs 1.0 10 6x* 2000) (He et al., 2016;
4.1 RESNET-20 ON THE CIFAR- 10 DATASET
5GD
10
Alam
1.0
560 Mineram
Acur
0.4
28 200
25h 20
27
200
S0tch 330
Batch 5.00
Figure 1: Number of steps for SGD, Momen- tum, 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 for Adam is inversely proportional to batch size b. Adam has critical batch size 6* = 2".
Figure 2: SFO complexities for SGD, Mo- mentum, and Adam versus batch size needed to train ResNet-20 on CIFAR-10. SFO com- plexity of Adam (resp. Momentum) is min- imized at critical batch size b' 2 (resp. b' = 29), whereas SFO complexity for SGD tends to increase with batch size.
Let consider training ResNet-20 the CIFAR-10 dataset with 50000. Figure 1 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(0x) 10-1 initially decreased. However, SGD with b > 2 and
8

---

Under review as a conference paper at ICLR 2023
Momentum with b 2 2 did not satisfy f(0x) < 10 before the stopping condition reached. Adam had an initial period of perfect scaling (indicated by dashed line) such that the number of steps K needed for f(Ox) 10- was inversely proportional to batch size b, and critical batch size b' = 21 such that K' was not inversely proportional to the batch size beyond b 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* 22; for Momentum, it was minimum at b* = 23. This implies that SGD and Momentum could not use large batch sizes, as shown in (I1). For Adam, SFO complexity was minimum at the critical batch size b* 2 that was close to estimation of critical batch 5 > 6x" with 1600 ~ by" < <b² = =2 2048, as shown in (11). We also checked that the elapsed time for Adam monotonically decreased for S 21l and that the elapsed time for
critical batch size b* = 221 was the shortest. The elapsed time for b 2 21 increased with the SFO complexity, as shown in Figure 2 (see Tables 3, 4, 5, and 6 in Appendix A).
4.2 RESNET- 18 ON THE MNIST DATASET
5GD
3.0
2G2
0.55
100
6.3
Figure 3: Number of steps for SGD, Mo- mentum, 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 batch size b. Adam has critical batch size h* = 200
Figure 4:
SFO complexities for SGD, Mo- mentum, and Adam versus batch size needed to train ResNet-18 on MNIST. SFO com- plexity of Adam (resp. Momentum) is min- imized at critical batch size b* = 2 (resp. b* = 2²). 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 3 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* = 2 and Adam minimized SFO complexity at the critical batch size b" 20 that was close to estimation of critical batch 5 > 6%" with 20 < b x 2000 < 2" as shown in (11). We can also check that the elapsed time for critical batch size b* 2 10 was the shortest (see Tables 7, 8, 9, and 10 in Appendix A).
We also estimated appropriate batch sizes of Adam for (i) CNN on MNIST (n = 60000, d RJ 7.7 x 109) and (ii) ResNet-32 on CIFAR-10 (n = 50000, d R 2.0 x 107) from bx in (11) and checked that actual critical batch sizes in (Zhang et al., 2019, Figure 5(a). (e)) are close to estimated batch sizes (i) by- = 2 2048 > bx* ss 2000, (ii) bz- = 2 = 1024 ~ by* ~ 1200).
CONCLUSION
This paper showed the relationship between batch size b and the number of steps K to achieve an e-approximation of deep learning optimizers using small constant learning rate a and hyperparam- eters 31 and 32 close to 1. From the convexity of SFO complexity N, there exists a global minimizer b" of N that is the critical batch size. We also gave numerical results indicating that Adam using small constant learning rate, hyperparameters close to one, and the critical batch size has faster convergence than Momentum and SGD. Moreover, we estimated appropriate batch sizes from our formula for b* and showed that actual critical batch sizes close to estimated batch sizes.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming. 2022.
Jonathan Borwein and Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. CMS Books in Mathematics. Springer, New York, 2000.
Hao Chen, Lili Zheng, Raed AL Kontar, and Garvesh Raskutti. Stochastic gradient descent in cor- related settings: A study on Gaussian processes. In Advances in Neural Information Processing Systems, volume 33, 2020.
Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. Closing the generalization gap of adaptive gradient methods training deep neural network. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, volume 452, pp. 3267-3277 2021.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of Adam- type algorithms for non-convex optimization. In Proceedings of The International Conference on Learning Representations, 2019.
Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. In Advances in Neural Information Processing Systems, volume 24, 2011.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011.
Benjamin Fehrman, Benjamin Gess, and Aruulf Jentzen. Convergence rates for the stochastic gradi- ent descent method for non-convex objective functions. Journal of Machine Learning Research, 21:1-48, 2020.
Saced Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly con- vex stochastic composite optimization I: generic algorithmic framework. SIAM Journal on Optimization, 22:1469-1444 1492, 2012.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly con- vex stochastic composite optimization II: Shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23:2061-2089, 2013.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge, 1985.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Paralleliz- ing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecification. Journal of Machine Learning Research, 18(223):1 -42, 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of The International Conference Learning Representations, 2015.
Mei Chee Leong, Dilip K. Prasad, Yong Tsui Lee, and Feng Lin. Semi-CNN architecture for effec- tive spatio-temporal learning action recognition. Applied Sciences, 10(2), 2020.
Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Lacoste-Julien. Stochastic polyak step- size for SGD: An adaptive learning rate for fast convergence. Proceedings of the 24th Interna- tional Conference on Artificial Intelligence and Statistics. volume 130, 2021.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proceedings of The International Conference Learning Representations, 2019.
10

---

Under review as a conference paper at ICLR 2023
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19:1574- 1609, 2009.
Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of conver- gence (11/k²). Doklady AN USSR, 269:543-547, 1983.
Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Com- putational Mathematics and Mathematical Physicx, 4:1-17, 1964.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In Proceedings of The International Conference on Learning Representations, 2018.
Herbert Robbins and Herbert Monro. A stochastic approximation method. The Annals of Mathe- matical Statistics, 12:400-407, 1951.
Kevin Scaman and Cédric Malherbe, Robustness analysis of non-convex stochastic gradient descent using biased expectations. In Advances in Neural Information Processing Systems, volume 33, 2020.
Christopher Shallue, Jaehoon Lee, Joseph Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George E. Dahl. Measuring the effects of data parallelism on neural network training. Journal of Machine Learning Research, 20:1-49, 2019.
Samuel L. Smith, Pieter-Jan Kindermans, and Quoc V. Le. Don't decay the learning rate, increase the batch size. Proceedings of The International Conference on Learning Representations, 2018.
Tijmen Tieleman and Geoffrey Hinton. RMSProp: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4:26-31, 2012.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, volume 31, 2018.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive meth- ods for nonconvex optimization. In Advances in Neural Information Processing Systems, vol- ume 31, 2018.
Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva. George E. Dahl, Christopher J. Shallue, and Roger Grosse. Which algorithmic choices matter at which batch sizes? Insights from a noisy quadratic model. In Advances in Neural Information Processing Systems, volume 32, 2019.
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the vergence of adaptive gradient methods for nonconvex optimization. In 12th Annual Workshop on Optimization for Machine Learning, 2020.
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar Tatikonda, Nicha Dvornck, Xenophon Pa- pademetris, and James S. Duncan. AdaBelief optimizer: Adapting stepsizes by the belief in observed gradients. In Advances in Neural Information Processing Systems, volume 33, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pp. 928-998--9988 93-9936,22 2003.
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. sufficient condition for con-
vergences of Adam and RMSProp. In Computer Vision and Pattern Recognition Conference, pp. 11127-11135, 2019.
A APPENDIX
Unless stated otherwise, all relationships between random variables are supposed hold almost surely. Let S be positive definite matrix, which is denoted by S E sd The S-inner product of Rdd is defined for all x, y Rd by (z, y)s Sy) (Sy), and the S-norm is defined by ||a||s Sar)..)..

---

Under review as a conference paper at ICLR 2023
A.1 PREVIOUS RESULTS IN TABLE
This section provides the upper bounds of the performance measure of optimizers indicated in Table
1.
A.1.1 TAIL-AVERAGED SGD
We consider the stochastic approximation problem of least square regression that is minimize the expected square loss function f()) := (a.))) ( - x 0 (sce Section 2.1 for the mathematical preliminaries). Tail-averaged SGD (Jain et al., 2018, Algorithm 1) with constant learning rate depending on the batch size and the largest eigenvalue of the Hessian of f satisfies
2(1 ap)
40²
B] - f(0)) - a² - 8)² (f(0)) f(0)))
(12)
6( s)
where s is the initial iterations, and the total samples, μ 0 the smallest eigenvalue of the Hessian of J. (0:)i>> is the sequence generated by Tail-averaged SGD, and = [+]-8 Eiss O (Jain al., 2018, Theorem 1). The upper bound Tail-averaged SGD when
is
- = (
1
1
Ab)
1
K2
Kb
A.1.2 ADAM
Theorem I in (Zaheer et al., 2018) and the proof of Theorem in (Zaheer al., 2018) show that, under the condition that Vf is Lipschitz continuous with the Lipschitz constant L, Adam using OLL -1, B1 O, and 32 2 1-O satisfies
\V $ (2VVB+++) ( ((0))) (GVT
La 0²) 2e b
K
aK
that is, the upper bound of Adam with 31 is
E [II o ( ( +
A.1.3 GENERIC ADAM
Theorem 4 in (Zou et al., 2019) shows that, under the condition that V o is Lipschitz continuous with the Lipschitz constant L, Generic Adam using ar ( (2))) satisfies
). 31 E (0, 1), and B2 = 1 x
D K 1 D D' Ek=
aA P B2R
V [(O))
ak K
where T is randomly chosen from {1,2,..., K). (.).a a 0, (0, 1), vo (vo,)) Do, D1 O.
D' = D3d B + 1o D:= 2Dov B + vp
BA
D4 + D2Dada log
1+
(1- 31)
1-31
Do
DiaL
31 (1 (1- (1 7),
D3 = VD - V7)
+2
+ +1]
B²
Di(1
vT)2
:::= -
This implies that the upper bound of Generic Adam is
O log K
E
|V |VS
|||
VK
(see also Corollary 10 in (Zou al., 2019) when 2/2 and 1).
12

---

Under review as a conference paper at ICLR 2023
A.1.4 ADAFOM
Corollary 3.2 in (Chen al., 2019) shows that, under the condition that V is Lipschitz continuous with the Lipschitz constant L, the AdaGrad with First Order Momentum (AdaFom) algorithm using
ag vi and 31 E (0, 1) satisfies
K K
Q1 + Q2 log K
E
VK
where G > 0,000 c/ 0.
D2d
Dzd
Q1 G
D2
- Did(1-log(e*
+ 2 log G)
+
+
D1 j
Q2: = GD1d,
c²
c
3
L1
1
2
B1
D1
D2 = G
1-3 +2)
2
1 $1
1
$1
D3 D3:= = G2 1+ 021+
(
L
B1
B1
11 31
1-B1
1
B1
(
31 ) (G2 + G9)
81
2
1.] Vo,
D4 = 1- B1
+
G +
20,
G
+ =[f(()) f(0)))
B1
A.1.5 AMSGRAD
Theorem 3 in (Zhou et al., 2020) shows that, under the condition that V is Lipschitz continuous with the Lipschitz constant L, AMSGrad using a constant learning rate a and B1 and B2 with B1 < / satisfies
1 K
D1
D2d
aDzd K3-s²
E
[(
<
K
aK
K
k=1
where & E (0, 1), Go > 0, 7 > 0,
2G3 D1 (f( f()))) D2 7(1 -11-31)
2LG2
2,37
D3
TVI 32 80
1+
9
B1
Hence, the upper bound of AMSGrad is
1
Σ
E [
=
K
K Ki-
A.1.6 ADABELIEF
Theorem 2.2 in (Zhuang et al., 2020) shows that, under the condition that V is Lipschitz continuous with the Lipschitz constant L, AdaBelief using ag = VE where > 0, and 31, B2 E (0, 1) satisfies
1
K
Q + Q2 K
[IV
E
K
avK
k=1
where c 0, G 0.
Dia? (G2 + +22
Dyda Vc
Dyda?
GDia² + +
Q Q1 = G
+
+ +DIJ. 02:=
c
c
3
L
1
D1
L
+ +
D2 = G²
+2
2
1 31
B1
1 1- B1
L
31
3
Dg = G2
1+ 21
1- 31
1- 81
1 B1
31
B1
2
D1 =
(G2 + G2)
+
G + 2a1
+ + - -(()))
1- 31
B1
13

---

Under review as a conference paper at ICLR 2023
A.1.7 PADAM
Corollary 4.5 in (Chen al., 2021) shows that, under the condition that V Lipschitz continuous with the Lipschitz constant L, the Partially adaptive momentum estimation (Padam) method using constant learning rate a, E [0, 3.. and $1 and B2 with 31 < 62 satisfies
DI
D2d aD3dG
E |IVS(0I11)
S
K
ak K
K2-5
k=1
where E (0, Go >
D1 == 20 - [(0))), D2:= = 4G 2 81 -0 [11]
+ 4G
d(1
31)
4LG 20 (1-1111) 31)
81
D3 = (1- 82)
(1- 12)
01
1 81
02
Hence, the upper bound Padam is
K
E [[I
=0
K
K
A.2
LEMMAS
Lemma A.1. Suppose that (CI), (C2), and (C3) hold. Then, Adam satisfies the following: for all 1 E N and all O E Rdd
E |1 0lmnn]
= [100
aa2
||
B1
31 E 100 (00-0))VVS(0)))
+ 2a
E [(00 Ou)] mm=-)
BIc
BIk
where d; == -- mp. 31 = Br and B1 = 1 g/+t1
Proof.
Let 1 E IRd and & E N. The definition ox+1 == 0; + adl implies that
|0 01, || 01l, + 2a (0x - 0. deym, + a² ||dell
Moreover, the definitions of d;, m.g and my ensure that
(0p 0. 0.ds). (0p 0, Hada) = (0 Oz, mp)) = -(0 0x)
mm
BIK
31 (0- 0x) m +
B1
(0 0%) T V.B, (0x).
Bik
Bik
Hence,
|1 011H,
110
0 01H, + a² ||dxllit
B1
B1 (0 02) (BB.
(13)
2a
( 0n) T===1= +
31k
Bik
Conditions (C2) and (C3) guarantee that
E ( 0x) TV.. (0x) ea]]
E
(0- 0x)
Tx)
T
V fBB (0x)
0z]
=E [(0 (.00-a) T (v.)).)
Therefore, the lemma follows from taking the expectation on both sides of (13). This completes the proof.
The discussion in the proof of Lemma A.1 also gives the following lemma.
14

---

Under review as a conference paper at ICLR 2023
Lemma A.2. Suppose that (CI), (C2), and (C3) hold. Then, SGD satisfies the following: for all E N and all 0 E R.
E
k+11 = =
0 - 0|| + a a [V
(0)) ||] + 2nl [[e [v((0=)
Moreover, Momentum satisfies the following: for all ls E N and all 0 E IR",
E |0u+11 011]
E ||0 0|]
a |m [?]
2a 8 [0- 0k) T m 3 [00 0x) [.)[()()))]
where B1 1= B1.
The following lemma indicates the bounds on (E|l) m and (Bil)dlli,, Lemma A.3. Adam under (C2) and (Al), for all k E N satisfies
m 122
|
0² + G2,
E B[iddRll
S
B2x
0²
+
G2)
Pi Un
b
where v, = inf inf(miin [minse Uhet: E N}, BIR := B+t and Brx :=
32
Proof. Condition (C2) implies that (O,)(( 0n
E
V Sm. (0s) VS(O,) + (/=))) 01.
E
V SB. (0%) f(,))l 0. + + Vf(()))l
0%
(14)
[V (0x) v)((,)) ()()))) 0z
2
=
E
[VB (0x) v f(0))l 0. + +|
which, together with (C2) and (A1), in turn implies that
V fa. (0))
S b + G
(15)
The convexity of || 112, together with the definition of my and (15), guarantees that, for all e N,
E |m
[2]
B. E
(m=-1l)
[13]
3 E
LB (0w)l
0²
| ||
Induction thus ensures that, for all l E N.
0²
E mm [2]
< max
m 11
- +
G2
(16)
where m 0. For & E N, H₃. E sd guarantees the existence of unique matrix H₃ E s such that H₁ H (Horn & Johnson, 1985, Theorem 7.2.6). We have that, for all x e IR,, || At. = || Accordingly, the definitions of dę and m imply that, for all N.
1HL = E H Hedd |"]
E
EE
m& 1|
3r
where
H
diag
63 #
= max
max sE(d)
Uu.i
=
Uk.
sE[d]
32r
B2r
Moreover, the definition of and (16) imply that, for all l: E,
0. = inf (uk k KE EN]
( 0
du 11
<
G22
+
completing the proof.
15

---

Under review as a conference paper at ICLR 2023
A.3
PROOF OF THEOREM 3.1
A.3.1
SGD
We show Theorem 3.1 for SGD.
Proof. (i) Lemma A.2 and (15) imply that, for all & N and all 0 Rd.
2alE (0x - 0) - [()))))
= E 00 012 - E |0 01]
+ a² IV (0w)
0²
s E 0 0 - E |10++1 0113 + a²
T G2
Summing the above inequality from
K leads to the finding that, for all K
1,
K
2a E 00 0) vf(ex)] < EE
|0: 01 - E | 0113] + ( G2 K,
1=11
which implies that, for all K 2 and all E Rd.
1 K
E [ 00 1
0 02 G
VI(K,
E
[0
0)
TVf(0)))
K
2aK
2
(17)
E
|
0 ||
aaa
G
2a
K
2
(ii) Let 0 E Rd and e > 0. Condition
G. K
+
C2 b
+ C3 = e is equivalent to
Cib
K
K()))= K(b)
(18)
Cz)b - C2
Since C2 + C2 + C3 > C3. we consider the case b>
C2 > 0 to guarantee that K > 0. From
K (17), the function K defined by (18) satisfies VT(K, 0) <
c-Ca
C
Ca + C3 = 6. Moreover, from (18),
K
+ b
dk((b)
C2,C2
d2
20 C2(c - C3)
db =
c2
db2 =
{(c Cz) - C2 2 0,
which implies that K is convex and monotone decreasing with respect to b. (iii) We have that
C₁ Kb = K(b)b = (6 Cz)b - C2
Accordingly,
dk (6)6
Cib((e 03)6 202}
db)( {(c - [()-C3)6- b C
20,02
{(e - C3)b C2 2 0,
db
db2
which implies that K(b)b is convex with respect to and
0
if < b²:
dK(b))
0
if b' 2C,
db
c-Cs
>0 0
if > b².
The point b* attains the minimum value K(b*)b*
40,02 (e-Cs) of K(b).. This completes the proof.
16

---

Under review as a conference paper at ICLR 2023
A.3.2 MOMENTUM
We show Theorem 3.1 for Momentum.
Proof. Lemma A.2 ensures that, for all and all A Rd
E [0x 0) mmx-1]
E
| -11
E 110+11 011]] - +
a
E
mm
2
20,31
231
3
[(0 0₂)
Tv(())]
B1
which, together with Lemma A.3, the Cauchy- Saachy-Schwarz inequality, and (A1) and (A2), implies that
E [0x 0) [_mmx-1] S
E |0
016]
|0 - 012]] 23
o² + +
20
6
3
+ 31
Dist(O)).
Summing the above inequality from to k = K gives relation that implies that
E [0x- 0)" m
S
E
|10
019)
R |00+1 - -01]]
0
+
)
G2
K
20,31
23 b
k=
B Dist(O)GK,
+
Bi
and hence,
E ||10: 0
02
3
E (0x -0 T m
+ G2
Dist
20,3 K
231
31
Moreover, have that, for all l N and all 0 E Rd..
(0x 0) my (0, 0) m 1 + 8 0) (V (0s) m
S (0, 0) m + 3 Dist (0) (IIV fa. (0x) + |m
where the first equality comes from the definition of m. and the first inequality comes from the Cauchy-Schwarz inequality, the triangle inequality, and (A2). Hence, from Lemma A.3, (15), Jensen's inequality, and 2 1,
0) mp] E [(0x 0)T m>mm;-1] + 28 Dist x2 G
E [0x
(19)
E [(0 0)T "m=11] + 23 Dist
Therefore, for all K and all 0 Rd
K
1
E (0.
0) mm
TTmma
K
(20)
E ||
0|
a²a Ga
G
+ Dist(
+ 2 0² +2+
2a3 K
23,
23
3
The definition of my ensures that
(0x - 8) V.B. (0x)
=00 0) my + (0s - -) TVVB.. - m (0: - T (0m(mm=1 - -m
1
(0) 0)
m +
(0. 0) ( (V (0x) m.) + 30 0) (mp-1 (f.))
31
17

---

Under review as a conference paper at ICLR 2023
which, together with the Cauchy- Cauchy-Schwarz inequality, the triangle inequality, and (A2), implies that
(0x - 0) V L., (0x)
(0%- 0) my 81
Dist + ||x]]] 1I) + Pi (0a)l + mm
Lemma A.3, (15), Jensen's inequality, and 6 guarantee that
1
0² Dist(O))
E (0x 0) ((k))) E (0x 0) mm
+
+
B1
+
31
(21)
1
[0 0) mm +
+
$1
Dist
31
Therefore, (20) ensures that, for all K 2 and all E Rdd
K
1
E [0x
O) vf((s))
0)
K
E 0100
0
o²a
G
{
GB, B1
(1
Dis
22 G
+23
2aB1
K
2
231
B
(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.3.3 ADAM
We show Theorem 3.1 for Adam.
Proof. (i) Let 0 E Rd. Lemma A.1 guarantees that for all l E N,
31k 2a
aB.
E [6p- 0) m
E ||0x
01HH.]
|10++1 - -01
E
d
28
be
31
E
(0
0x) (vf((()
(22)
3
We define 7/ = 20,a
3yk
(k: E N). Then, for all K 2 1,
Σ ak B. [10, 011i!
T 110
011i1]
- E
|10
011,1111
k=1
(23)
Tx
IF 1 -0
Since H₂ E 444 exists such that H2. = H we have || = -|Haaal13 for all a E TRdd Accordingly, also have
nh (0x 0)112 - (Ox -0]1(3}
Tk E
18

---

Under review as a conference paper at ICLR 2023
From Hę. diag(Up, 1/4), for all K 2 2,
(kk ), have that, for all (1x)) RR, ||Hz Ei= en, Hence,
K
Tx= =
Tk n ŌK 7h- V 0k -h-
1.. (0x.; - 0.)3
(24)
2= t=1
Condition (2) and ") 2 - (k 2 1) imply that, for k 2 and E [d].
Y 0 7k v 2 0.
(25)
Moreover, (A2) ensures that D sup ma (0k.s -0..s-0,)²=- N to0. Accordingly, for all K 2 2,
T S D(O)E
Yk V / Un.
7k- 0k D(O)E Σ YK (KKōKK - 71 (TKVVKA-7IV/i 7
2==2
Let ffB. (0x) O fIB, (0x) = (g),)) E 17. Assumption (A1) ensures that there exists E R such that, for all & E N. maxee id g I M. The definition of 2y guarantees that, for all i E [d] and all E N,
1ki 320 + $292..
Induction thus ensures that, for all i E [d] and all & E N,
UK S maxx(vo.: M3 M,
(26)
where vo (vo.;) = 0. From the definition of θR. we have that, for all i E [d] and all & e N,
Uk
M
(27)
B2k
B2k
Therefore, (23), B| 01,,1 S D(O)
and (27) imply, for all K 2 1.
1=
Σ ΦK D(OEE
Vōl.
D(OE
YK VO.. - 71 v
D(O)E
UKK
(28)
d 7k ((0) Σ
M
B2K
(IDO)VMBB
23101 Box
Inequality (28) with 31K
1-39
3K+1 < 1-
and Bor := -B,
gK+1 2 1 B2 =: Bg implies that
Σ 0k ID(O)VM3.. dD(O)vM
<
(29)
23101 B2x
28 82
Lemma A.3 guarantees that, for all N.
by aBık
E
|| [1ln
5
a V B2s
o
G2)
62
a/33x Brx
av
(
o2
(30)
23,
2,
82
PlaVo. V0
b
11
Inequality (30) with 3ix 3=
gh+t1
1
B1 =; Bi and
B2s
gk+t implies that
a
Br
( 0²
+0²
{
0²
+
by 5
5
(31)
2 3131
208.B18
b
19

---

Under review as a conference paper at ICLR 2023
The Bauchy-Schwarn inequality and (A2) imply that, for all & N,
3 E [O 0w) (((O)] S (O)
31
Ck 31
(32)
31
Hence, (22), (29), (31), and (32) ensure that, for 2
1 Σ E -0) m1mm==1]
dD(OWM
+ alo²b +
$1
Dis
28107 32K 2/0.31811
B1
Therefore, from (19), for all K 1,
K
E [0.- - 0)_m, mk
K
(33)
dD(OVMM
a²a
Ga
(G
3 Bist 2/0,0131
+ 2v
22/022220 02 +3)
2 82K
2/ebB13316
33
From (21) and (33), for all K 1,
K
E
(0
0) v((+))
K
dD
V
1
o²a
1
Ga
+ Dis
G B
22 + G2 G²
+ 2v
3 +2
1 [+20) 28
20,11
B2
K
2 2.B.B1
b
2/0.318
(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.3.4 AMSGRAD
We show that C for AMSGrad are (6).
Proof. Let us consider AMSGrad (Algorithm with my = ma. 0g = Uk. ūp. max( (i, U..s). and H₃ := diag( / (k))). Induction, together with (26) and Ug.5 == max mrax(0x-)) (6,-1,5, (k,s), ensures that, for all & E N, 0k.s Σ M, where ê = (0-1.) = 0. An ar- gument similar to that which showed (i) in Appendix A.3.3 ensures that
K
dDOOM M
02 +G²) and en S (is
S
by
20:31
20..1
31
where ag. by. and C are defined as in (22) and ü. == inf(mineejd UR.s: k E N). Inequalities (21) and (33) thus imply that C, for AMSGrad are (6).
A.4 RESULTS FOR VARYING LEARNING RATES
We can establish the upper bound of VT( 0) for Adam with varying learning rates from discus- sion similar to the one for proving Theorem 3. (i) (Appendix A.3.3). Let (ox)keN be monotone
decreasing. Then, 7k 28,ax satisfies 7k+1 7k (k E N). Hence, (25) holds. The discussion in
Appendix A.3.3 thus ensures that
dD(O)VM
-2b + G
K
VI(KO 0) < 281VI- Back
Σ
as
8 + ((31).
(34)
2/0..1
31)
1=1
20

---

Under review as a conference paper at ICLR 2023
Let us consider the case where a
3 (K 2 1). From (34), we have that VR
dD(O) M
0²b G22
K
VI(K,0)
Σ
+
h(11)
231 - 32V
2/0. B1)K k= vh
dD(O)
d2b-1+ VK
+ ((11))
2 - B2VK
Vu,Bi(1- (1-11) B1) K
dD(O)VM
o26-1+62
1 +h(3)),
231 v1 - -32K VI,Bi - B1) VK
where 1 - gh+1 < < and
1-22t1
Σ 1 S 22 Hence,
vt
dD(O)VM
G
o² V1, - b)b
VI(K,0) -
x((1))
2 v 32 Vo 31)
VK
(35)
Ć1
+ C2 + h(31).
VK
bvK
Theorem 3.1 indicates that Adam with constant learning rate satisfies
VI(K, 0) S C1 C2
C3-
C in contrast to the term C2 using
Hence, using ag V mitigates the variance (the term
bVK
Og a. However, the bias term K using a₁ = a would be better than the bias term VK 0g Vk in the sense of minimizing the upper bound VI(K, 0).
using
Let T 2 1, E (0. > and P = K. Next, let consider the following varying learning rate
(ax) (ar, (ar,a aPT).
where ajr ( a a, . a (j 1,2,..., P). That is, (ax) is
(a, ar a...,, a) (na, ya..... ya),
(2--1a, P-1 ar
p-1a)).
T
Let a > 0 be the lower bound of ag. From
K
ap of + yaT + P-1 af < aT
p1 1-7
and (34), we have that
dD(O)/M
0²b G2 aT
VI(TP,0) <
2 2/v.311 (1 3TTPP 7 + h(31))
2 BATT
dD(O)M
(026-1+ G2)a
2 v1 - -1:((1 P)P h(11)
23, BP
dD(O)VM
G2a
a²a
23 V -BaT
-1
P +
2 2. 31
31)(1 Pb
h((1)
o pb
+ h(B1).
Here, we recall that Adam with aj satisfies
Ci
C₂
1) ( Cs.
VI(TP,0)
< TP
C.
=0
+ b
b
21

---

Under review as a conference paper at ICLR 2023
and Adam with ay
1 vk
satisfies
VI(TP,0) S
G1
+
C2
+ +(31)) 0
(
1 1
+ h(31).
VTP
bVTP
/P
bvP
Therefore, using
(ax) = (der, o.r....., app)
more desirable minimize the upper bound of VI(K, for Adam than using og. = 02 VE
A.5 BOUNDEDNESS CONDITION OF (V.(0t))ken
Let :: Rd -> I be convex. Then, f is Lipschitz continuous (i.e., (f)) - S G - if and only if [ s G (x E Rd) (see, e.g., Theorem 6.2.2, Corollary 6.1.2, and Exercise (.1. in (Borwein & Lewis, 2000)). Let 0" be a local minimizer of a Lipschitz continuous function f. The continuity of f ensures that f is convex around 0" Hence, for any 0 belonging to a neighborhood (6*) of 0" f[)]l < G. If the sequence (0x)keN generated by optimizer approximates 0", then 0g E N(0)) for sufficiently large k, i.e., [V G.
A.6 CONDITION c - C3 > 0
Under Lipschitz smoothness condition of (i.e., V vs(y)l -||==11) -yl), the gradient descent (GD) with a constant learning rate a ( satisfies that lim [ 0 by the descent lemma (f(y) < V(xx)) (y-x) + = Under non-smoothness condition of f. GD with constant learning rate a > 0 satisfies that lim inf ( ((0; - O) < G² 2 a. Hence, it is not guaranteed that, under non-smoothness condition of f. GD with a constant learning rate > O converges. However, we can expect that using a small constant learning rate approximates stationary point of f.
Meanwhile, under non-smoothness condition of f, GD with diminishing learning rate ay satisfies that
1
vV
D(0) VI(K, 0) 2Kag
obb-1 G
D(0)
G
(
1
2K
ag
2Kak
+
2K
aq O
V
(see also Appendix A.3.1 when a is ) Hence, GD with diminishing learning rate does not need
C3 used in Theorem 3.1. This result strongly depends on the condition 0.
Under non-smoothness condition of f, Adam with a diminishing learning rate ag = VR (i.e.. 0) satisfies that
and =
Ć2 + h(1))
VI(K,
+
+ ((11)
VK
b/K
VK
(see (35)) and Adam with constant learning rate and b n (i.e., 0) satisfies that
C1 +
C1
C2
VI(K, 0)
+ C3.
K
K
The previous results (Zaheer et al., 2018) indicated that Adam with a constant learning rate a = (T,-+),, B1 and a = 0 satisfies that
Σ E [IVS(O)) S (V f(01)-f(0)) G K
k
K
aK
The condition 81 * essential to analyze Adam since the practically useful 13 close 1. The upper bound of VI(K, 0) for Adam with 31 + 0 depends on the term with respect to 31, i.e.. Ga
C3 = 2 2/181(113 3J h(11). Hence, c > C3 and 1(31)) are needed consider K to satisfy
VI(K, 0) < C h(31) = (diminishing learning rate case) and VI(K, 0) <
C K
+ C3 =c
VR
(constant learning rate case) even if 0.
22

---

Under review as a conference paper at ICLR 2023
A.7 LOWER AND UPPER BOUNDS ON K WITH VI(K, =
Let us consider SGD under (CI)-(C3) and let 0* be a stationary point f. From Lemma A.2, we have that
2 [1
[V({)( = E [| 0-] E [100+1 0-11 + a E [ [V, (0=
Hence, for all 2 1,
K
20x
E [0 - V((=] [100 - -011 - E [|0K+1 - 0-||²] + 2
E [1] ( (0:)
Here, we assume that there exists c E [0, 1] such that co2 < EE| (0x) f() = 0². From (14), have that
ca²
E IV fB, (0x) 0x E [V (0x) f(0w))1 02: + +
b
Since 0k+1 approximates 0", we assume that there exists X(0r) 2 such that E|| 0-1 11
0 K+1
1- 2 x(0)). Hence,
c
2a
E [0x Vf((m)
2 x((0))
k=1
which implies that
D1
D2
VI(K,0") 2 +
where
X(0)
and D2 = coaa
D1 =
2a
2
Meanwhile, Theorem 3.) indicates that
C1
C2
VI(K,0") -
+
C3.
K
b
where
B 17]
a²a
Ga
C1
C2
and C3
2a
2
2
Suppose that VI(K, < Then, we have that
D1
D2
+
S.
K
b
which implies that
Dib
K(b)
Dg S K.
Suppose that VI(K, 0*) 2 c. Then, we have that
C
C2
+ +
C3 26,
K
which implies that
C₁b 2 K.
K(b)
-CC)b C2
From
X(0))
0 0 0 - [E
0 - 0 1
E
0 00
D
<
C1.
2a
2a
2a
23

---

Under review as a conference paper at ICLR 2023
D2 = ca2a σ²a
2 v
C2.
2
and
(c 03)b C2 S eb C2 S cb - D2.
have that K(b)= K()). Hence, K with VI(K, 0*) satisfies
K(b) - K - K(b)
and the SFO complexity N Kb satisfies
K(6)b N S < N = (b)6.
Moreover, b, 2D2 minimizing N and b' cc2 minimizing N (see Theorem 3.1() satisfy that b, < b.. Let a be small enough. Then, we have that b, = b' and K(bb)b, )b, R K(b")b"
where
EE 01
10
X(6))
0²a D2 ca²a and C3 2
Ga
C1
D1
C2
2a
2a
2
2
are used. Hence, the batch sizes and b* (b, b*) approximate the batch size minimizing N Kb.
A.8 SFO COMPLEXITY REGARDING COMPUTATIONAL COST OF PARALLELIZABLE STEPS
Let us consider Tail- average SGD (Jain et al., 2018, Algorithm 1) independently in P machines, each of which contains 3 samples, for minimizing the expected square loss function f(0) ==
1 {B(a.y)>Dy x 0] (see Appendix A.1.1). Let 0, be the point generated by Tail-averaged SGD with the batch size b on machine (i E [P]) and let 0 = p E 0; be the point generated by Parallelizing Tail- SGD. Then, Theorem 6 in (Jain al., 2018) guarantees that
(1-ap) + (P - 1)(1 ay))" (f(Oo) f(0))) + Pb s) -[f(0)] < a² a² s)²
40
P
where 8 is the initial iterations, and is the total samples, > 0 is the smallest eigenvalue of the Hessian of f. and (0,) and 0, : -A. Eis. 02 are the sequences generated by Tail-averaged
SGD (see also Appendix 1.1.)). This result with P = 1 coincides with (12). Setting > Ka log P (Jain al., 2018, 15, Remarks) ensures that
and a
3x
4g
[[((0) - 1(00) S exp
S)2P (J(0g) - ((0)))
Kbb
Ph
n Pb(
Ph
8)
which, together with K
n Pb
s, implies that
[[) f(0)) -(0)))
(36)
K2P KPb
Hence, (36) indicates that the larger the number of machines P is, the smaller the upper bound of (0) f(0)) becomes.
Next, let us consider SGD independently in P machines, each of which contains a minimizing the expected square loss function f. Given 03 Rd machine (i E [P]) generates the point
p samples, for
(
0x
a p
(0x) 02- b
G 16 (0k) Sk.
jEM
using SGD with the batch size b and computes
0 a++1
0
(4)
(37)
K+1
where Ehy is random variable generated by the j-th sampling in the k-the iteration for machine and we assume that the stochastic gradient G Gz(o) (0x) satisfies (C2).
$2.g
We have the following theorem.
24

---

Under review as a conference paper at ICLR 2023
Theorem A.1. Consider minimizing the expected square loss function f(0) (.) 0) and let 0r be minimizer of f. Then, under (C2) and (Al), the sequence (0x) generated by Parallelizing SGD (37) satisfies the following:
(i) [Upper bound of VI(K, 0*)] For all K 1,
K
Ci K
C
E
On
1(0)) VI(KO
S
+ C3.
K
Ph
where the number of machines,
C = [ B1100 1-
o²a
C3 = G
C2 =
2a
2
2
(ii) [Steps satisfy VI(K, 0*) c] The number of steps Kp defined by
C₁ Pb
(b) (c - Cb C2
(38)
satisfies VI(Kp, 0*) - c and the function (b) defined by (38) is convex and monotone decreasing with respect to b (>
CP) > 0).
C2
(iii) [Minimization of SFO complexity] The SFO complexity defined by
Pi
Np (r(b)b (c- Pb C2
(39)
convex with respect (>
0). The butch size
[c C
2C2
bp CC-C3)
attains the following minimum value of Np defined by (39):
4C1C2
Np = (p(bp))p (E C2)2p'
(40)
Let 0 = 0, (i E
[P). Then, the SFO complexity N = K(b*}6* for unparallelizing SGD with the batch size b* 20g is obtained by (40) with P = 1 (see also Theorem 3.i i.e.,
Cs
4C₁C₂
N No K. (b*)0" = (e C3)²
Meanwhile, Parallelizing SGD (37) with the batch size Ujp (c-Cs) where P (> 1) is the number of machines, has SFO complexity (40), i.e.,
2C,
4C₁C₂
40,C2
N = (c CBP
N* (c C2)
Therefore, we can conclude that the larger P is, the smaller SFO complexity becomes.
Proof of Theorem A.I. (i) Let l E N. The definition of 4+1 - - aV
nco ap (0x) ensures that,
for all E [P].
| 10:1 0-1 = ||0x -0 2a(0x 0*) T
B( (0x) a a 0x))
which implies that
E
[10|0
(1)
k+1 011
=1 0-112 2alE (0x -0) TV
v
B (0s)
+ a
| f
(0.))1
(0x)
0x (0x)
|00 - 11 0 -00) E
V
(0x)
0
+ a 2
|V
0x
25

---

Under review as a conference paper at ICLR 2023
Hence, (C2) implies that, for all i [P],
|10 (1) k+1 - 11
(41)
= E |10 0- 0-1 2a (0,
- -0) (')T(((())] +
E |
p (0x) 0z
A discussion similar to the one showing (14) implies that, for all i E [P].
B [V (0x)12
0x]
E
V B(o (( (0x) (f.).)) + ff()))) 0x
E
[ n(o (0x) v(()))) || 0k: + E
[V((0))] 0x
2E (V/ B (0s) v.((O)))
v/(02) 02
E | a (0x) ff=)))
+ +V 0
The definition of 0s and the linearity of V f guarantee that (0x)
E
V B
- ( 1| 02
E
G (0 (0s) vS(( k..
0k
jE
1 E
Σ
Get
1
Σ
0000
vs
1
Σ
02
172
P
P
SELD]
sE[P]
kE(PI
1
E
Σ
G EE.
(0
v f(
0x
p262
JELB]
NE[P]
which, together with (C2), in turn implies that
Pbo 0²
E
VV ( (0x) - (f(W))1
01 <
p26
Pb
Hence, from (A1),
S o²
E V p
(0x)))
+ G
(42)
Ph
Accordingly, from (41) and (42), for all i E [P].
pp (
E 1 0 0* [[2] E 0 1*]]
2xEE (0 0*) (V) +a²
Since the convexity of 21 and the definition of 02 imply that
E [1 0-1
S Σ E
1
|
0'[]]]
PEiP]
we have that
(0² g²
E [10+1 [1] S [100: -0-13]]
2nF (0 (V)T(((())))
+ o²
Pb + G2
Hence, for all K 2 1,
1 K
E [100,
10
0²
VI(K, 0¹) =
Σ
E (0
vv(0m)
<
+ G2
K
2aK
2
pb
Eie'n B[|[0 (1)
0
131
1
o²a
Ga
+
2aP
K
2 Pb
2
maX:e[P1
0- [|2]
1
j a
1
G
2a
K
2
Pb
2
C.
C2
C2
26

---

Under review as a conference paper at ICLR 2023
Since f is convex, have that
]
E
0k
1(0')
E [[s(0k) ( S VI(K (*)
f(0)))
K
(ii) A discussion similar to the one showing (ii) in Theorem 3.1 for SGD would show (ii) in Theorem A.1.
(iii) An argument similar to that which obtained (ii) in Theorem 3.1 for SGD would prove (ii) in Theorem A.I.
A.9 ADDITIONAL. NUMERICAL. RESULTS
Table 3: Elapsed time and training accuracy of SGD when f(0x) Σ 10 for training ResNet-20 on CIFAR-10
SGD 24
Batch Size
22
23
25
26
27
28
29
Time (8)
16983.64
9103.76
6176.19
3759.25
Accuracy (%)
96.75
96.69
96.66
96.88
Table 4: Elapsed time and training accuracy of Momentum when f(0x) S 10 for training ResNet-20 on CIFAR-10
Momentum
Batch Size
2
23
24
2
26
27
2
29
Time (8)
7978.90
3837.72
2520.82
1458. 70
887.01
678.66 6.66
625.10 10
866.65
Accuracy (%)
96.49
96.79
96.51
96.72
96.70
96.94
96.94
98.34
Table 5: Elapsed time and training accuracy of Adam when f(0x) S 10-1 for training ResNet-20 on CIFAR-10
Adam
Batch Size
22
23
21
25
27
28
29
Time (s)
10601.78
4405.73
2410.28
1314.01 96.53
617.14
487.75
281.74
225.03
Accuracy (%)
96.46
96.38
96.65
96.43
96.68
96.58
96.72
27

---

Under review as a conference paper at ICLR 2023
Table 6: Elapsed time and training accuracy of Adam when f(0x) - 10 for training ResNet-20 on CIFAR-10
Adam
Batch Size
2
211
212
213
214
2
2
Time (8)
197.78
T95.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 7: Elapsed time and training accuracy of SGD when f(0k) on MNIST
S 10 for training ResNet- 18
SGD 24
Batch Size
2²
23
25
26
27
2
2
Time (s)
1620.98
1002.89
1140.47
1298.52
Accuracy (%)
99.70
99.69
99.70
99.70
Table 8: Elapsed time and training accuracy of Momentum when f(0k) ResNet-18 on MNIST
S 10 for training
Momentum
Batch Size
2
23
2
2
26
27
28
20
Time (8)
1949.66
550.28
298.77 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 9: Elapsed time and training accuracy of Adam when f(0x) S 10 for training ResNet- 18 on MNIST
Adam 25
Batch Size
22
23
24
26
27
28
29
Time (s)
7514.43
614.27
297.97
216.
160.93
127.97
102.98
Accuracy (%)
99.74
99.66
99.64
99.66
99.66
99.69
99.71
Table 10: Elapsed time and training accuracy of Adam when f(0x) S 1001 for training ResNet- on MNIST
Adam
Batch Size
210
211
212
2
2
Time (s)
93.53
100.22
129.29
217.23
375.87
Accuracy (%)
99.68
99.67
99.67
99.70
99.69
28


Reviews:
[{"review_id": "WfoBWguSwQ", "reviewer": "Reviewer_hyhk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents an analysis of adaptive gradient methods with an emphasis on providing insights into the optimal setting of hyperparameters. The presented convergence results suggest settings that are in line with practical observations. From these results, the paper derives a \"critical batch size\", which minimizes the stochastic first-order oracle complexity.", "summary_of_the_review": "Given the caveats detailed above, I recommend rejection. I hope that the authors can clarify some of my questions/concerns in the rebuttal phase.", "strength_and_weaknesses": "### Strengths\n\n1. I commend the effort to shed light on the influence of hyperparameter settings in adaptive gradient methods.\n\n2. I found it very interesting to see the experimental analysis regarding the critical batch size (Fig. 2), especially seeing that the SFO complexity for Adam is minimized at a relatively large batch size, in contrast to SGD.\n\n\n### Weaknesses\n\n1. I partially disagree with the premise of the paper that previous works suggest a setting of $\\beta_1\\approx \\beta_2 \\approx 0$. I checked a few of the provided references and, e.g., Zaheer et al (2019) analyze a setting with $\\beta_2$ close to 1 (they set $\\beta_1$ to 0 though). Moreover, some of the cited papers study a situation where the batch size is increased over time, so one should be careful to transfer conclusions to the setting of a fixed batch size. I would ask that the authors make the discussion of prior work more precise and specify exact results which they think constitute a gap between theory and practice. Overall, I don't think the present version of the paper does a great job of positioning itself in the context of the (admittedly numerous) existing papers analyzing adaptive gradient methods.\n\n2. The analysis is based on the \"variational inequality\" $K^{-1}\\sum_k \\nabla f(\\theta_k)^T(\\theta_k - \\theta) \\leq \\epsilon$ for all $\\theta$. I see why this is characterizing a stationary point for $\\epsilon=0$, but this seems not very meaningful for $\\epsilon>0$. I can just pick some $k$ and set $\\theta = c (\\theta_k - \\nabla f(\\theta_k))$ and if $\\nabla f(\\theta_k) \\neq 0$, I can always break the inequality by scaling up $c$. I would like the authors to clarify: To what extent does this inequality really characterize a stationary point? Has prior work used a similar formulation (if so, it should be cited)? Why is it meaningful to establish an upper bound on this quantity?\n\n3. The paper assumes a lot of absolute upper bounds on various gradient-related quantities, most strikingly $\\Vert \\nabla f(\\theta_k)\\Vert \\leq G$. I know that many previous works have used this assumption, but I still see this very critically since it is completely unrealistic. Usually, it is possible to relax such assumptions. For example, Eq. (7) could be replaced with a bound of the form $\\mathbf{E}[\\Vert g_k- \\nabla f(\\theta_k) \\Vert^2] \\leq \\sigma_0^2 + c \\Vert \\nabla f(\\theta_k)\\Vert^2$.\n\n4. As the paper rightly points out, Adam is not guaranteed to converge on a convex stochastic optimization problem. The \"breaking point\" of the convergence proof is that Eq. (8) is _not_ fulfilled by Adam. The present paper goes on to simply _assume_ that Eq. (8) holds for Adam. In my opinion, that is not acceptable. You can analyze variants of Adam that enforce Eq. (8) to hold (AMSGrad) but you can not just _assume_ an algorithm to have a property that it demonstrably does not have. I would like the authors to clarify whether the presented analysis would extend to AMSGrad? If so, the paper should be adapted to reflect that.\n\n\n### Update after Rebuttal\n\nThanks for clarifying point (2). This was mostly a misunderstanding on my part and I apologize for that! It seems quite clear in hindsight. Point (4) is still relevant and should be addressed in a possible camera-ready. I will increase my score.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VTD6ozOhHD", "reviewer": "Reviewer_vE9x", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the batch size for fastest convergence of optimization algorithms applied in deep learning. The metric is the total number of stochastic gradient estimations, which is the product of number of iterations and batch size. The optimal point should be in the middle, that both number of iterations and batch size are reasonably big. The proof is given in details and the experiments verify the conclusion.", "summary_of_the_review": "I would like to see the authors' response to my questions above to judge its quality/correctness. If they are addressed, I believe the paper is sound and solid. I think the score is 5 or 6 but I feel/expect the above questions can be addressed later and give a 6 here.\n\n=======================\n\nI still have some questions about the tightness but I think it matches the intuition and some other results. But given the proof technique for diminishing step sizes, I would like to tentatively rescore it as 8 (I would say 7 if the tightness issue still remains, and I'd suggest more reasoning about the SFO regarding the computational cost of \"parallelizable\" or \"unparallelizable\" steps). I believe diminishing step size is more important than constant step size if the bound is more optimal, since it can also achieve any small error for a non-smooth function and tweak the variance, etc., so I'd like to see it in the paper or appendix.", "strength_and_weaknesses": "I think this paper treats the theory seriously and gives thorough proof in all details, on a fundamental problem in machine learning. The algorithm covers the most widely used optimization algorithms with tuning parameters such as momentum, adaptive gradient, etc. so is very practical. I have a few questions below.\n\nCritical: This paper proposes the upper bound and minimizes this upper bound wrt batch size. However, I’m not sure if the upper bound of VI is tight, say, whether it’s also a lower bound? Basically you want to minimize the exact rate (in big O) or at least a somehow tight upper bound, rather than a loose one. Does the experiment result exactly align with the upper bound? A figure with both experimental and theoretical \"iteration vs. error\" curves would justify the point. \n\nBut on the other hand, I think the bound makes some sense. The $1/K$ term is the bias and the $1/b$ term is the variance, but I'm not sure they are exact like both a plain inverse, in big O sense. With the same decomposition of bias/variance, does the bound, by any chance, match the bound for Table 1 of https://www.jmlr.org/papers/volume18/16-595/16-595.pdf? It should also be convincing if the bounds matches previous works' results. \n\nI would like to see more justification of SFO as a metric. For example, the gradient computation in batches can be parallel, thus intrinsically faster than running more GD iterations that cannot be concurrent. I think it also depends on how many machines you have, so that, in terms of experiments, I like the ones with SFO as y-axis rather than the tables using time as a metric (computation time really depends on the device, like how many computational “units” it has). \n\nAre the step sizes among different batch sizes the same? And within the algorithm on a same batch size, is the step size fixed? For the latter question, I think ADAM can adapt the step size by itself but one can still vary batch size along the iterations to get a better result. Intuitively, when batch size is smaller, the noise is bigger and one needs smaller steps sizes for the same convergence error target $\\epsilon$. A diminishing step size can handle/mitigate the error caused by noise variance, i.e., caused by finite batch sizes, somehow.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "MAlxX6PQXDf", "reviewer": "Reviewer_vJ3a", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the gap between the theoretical and empirical optimal hyperparameters values for adaptive gradient methods such as Adam for stochastic non-convex optimization. It provides new convergence upper bounds for several of these methods under bounded gradients and variance assumptions. These upper bounds are shown to be the lowest for the aforementioned hyperparameters being close to one, which is close to practice. \n\n", "summary_of_the_review": "The paper tries to study an interesting gap between the theory and practice of adaptive methods. However, it lacks a clear comparison to existing theoretical results, and the provided guarantees seem weaker than usual stationarity guarantees. The experiments don't have any new insights, as similar experiments exist on much larger datasets in the references cited within the paper. I thus recommend rejecting the paper. \n\n", "strength_and_weaknesses": "The first major problem with the paper is assuming both bounded variance and bounded gradients. It is well known that in this setting, mini-batching doesn't help because for usual problems $G\\approx \\sigma$ unless there is some stylized noise structure. Bounded variance assumptions are usually paired with smoothness assumptions, for instance, [this paper](https://arxiv.org/pdf/1912.02365.pdf). Under the paper's assumptions, if $\\sigma$ is replaced by $G$, then $C_2 \\leq C_3$ so there is no benefit of mini-batching! Similarly, it is not reasonable to assume the boundedness of parameters without explicitly making any projection steps in the algorithm. \n\nThe second major problem is that the paper makes no comparison to the existing upper bounds for these algorithms. As a result, it is unclear if Adam's analysis is an improvement over the existing work. And if the upper bounds are worse than the previous bounds, then it is a fallacy to make any conclusions about the optimal hyper-parameters. Ideally, one would never make such conclusions with just upper bounds without matching lower bounds. \n\nAnother issue is that the final guarantees in the paper are not comparable to usual guarantees upper bounding $\\frac{1}{K}\\sum_{k\\in[K]} \\mathbb{E}||\\nabla f(\\theta_k)||^2$, which guarantees that at least one iterate was an approximate stationary point. The paper instead uses a variational metric, but it is not reasonable to average it across $k$ because that doesn't imply that the best $\\theta_k$ satisfies the variational metric for all $\\theta$. \n\nOverall, the paper is not technically sound. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "KvHQjjc6A4J", "reviewer": "Reviewer_U2qx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the relationship between the batch size and the required step number to achieve the local optimum in the conditions of small constant learning rate and hyperparameters close to 1. The authors also present a critical batch size. These theoretical results are also supported by numerical results.", "summary_of_the_review": "Overall, I recommend \"5: marginally below the acceptance threshold.\" I need the authors to give more details in their responses, and if this paper is accepted, the draft needs a revision.", "strength_and_weaknesses": "Overall, this paper presents novel results with solid foundations. My concerns mainly exist in the presentation. Some details are missing; some are not clear enough.\n\n1. The presented results on critical results are new to me, though the suggestion of using a small batch size is not new. The current draft needs a more detailed, comprehensive comparison with the related results. As described in Section 1.2, some similar results have been seen in the literature. The authors need to clarify the advances this paper has made more clearly.\n\n2. The proofs are given in the appendices in detail. However, I suggest the authors give a sketch in the main text. Also, the authors need to clarify the significance and difficulty of their proofs in the response and the revised draft.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject