Increasing Both Batch Size and Learning Rate Accelerates Stochastic Gradient Descent
Authors: Hikaru Umeda
Hideaki Iiduka
Venue: Accepted by TMLR ()

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

Published in Transactions on Machine Learning Research (02/2025)
Increasing Both Batch Size and Learning Rate Accelerates Stochastic Gradient Descent
Hikaru Umeda Meiji University
ee227115@metji.o....
Hideaki Tiduka Meiji University
iddua www.ss.smmmiiiii. ac.jp
Reviewed on OpenReview: https: // openreview. net/ met/forunu forum? id= 3bmp55k66.
Abstract
The performance of mini-batch stochastic gradient descent (SGD) strongly depends set- ting the batch size and learning rate to minimize the empirical loss in training the deep neural network. In this paper, 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 1951 Zinkevich 2003 Nemirovski et al. 2009 Ghadimi & Lan 2012 2013) simple and useful deep-learning optimizer for finding appropriate parameters of deep neural network (DNN) 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 how the batch size and learning rate set. In particular, increasing batch size [Bydd et al. 2012 Balles et al. 2016 De et al. 2017 Smith et al.) 2018: Goyal et al. 2018 Shallue et al. 2019 Zhang et al. 2019) is useful for training DNNs with mini-batch SGD. In (Smith et al. 2018). was numerically shown that using an enormous batch size leads to a reduction in the number of parameter updates.
Loshchilov & Hutter 2017 Hundt al. 2019) is also useful for training DNNs with mini-batch SGD. In (Chen al.) 2020 theoretical results indicated that running SGD with diminishing learning rate n O and large batch size for sufficiently many steps lcads to convergence to stationary point. A practical example of a docaying lcarning rate with 7441 5 T). for all E N is a constant learning rate 7). = 1) > 0 for all / e N. However, convergence of SGD with a constant learning rate not guaranteed (Scaman Malherbe 2020). Other practical learning rates have been presented for training DNNs, including cosine anncaling [Loshchilov Hutter 2017), cosine power annealing (Hundt al. 2019), step decay (Lu 2024). exponential decay (Wu al.] 2014), polynomial decay
Decaying learning rate (Wu al. 2014 loffe & Szegedy 2015
Chen et al. 2018), and linear decay (Liu et. al. 2020

---

Published in Transactions on Machine Learning Research (02/2025)
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:
(2) -f)
1
Lo²
E [IV 10
min
2 Limmxx
Ei=o
Lmmax
b
1t=
11
t=
Br
VT
where f the empirical loss for n training samples having L-Lipschitz continuous gradient f and lower
bound f" o² is an upper bound on the variance of the mini-batch stochastic gradient, and (0) is the sequence generated by mini-bateh SGD with batch size by, learning rate Ue E [mmnn Thuax C [0, 2) and total number of steps to train a DNN T.
Scheduler
Br
VT
Case (i) (Theorem 3.1; Section 3.1
H1 T
H2
H7
1
V T
by: Constant; 7) Decay
b
bT
b
Case (ii) (Theorem
3.2. Section 3.2
H3
H4
O
by: Increase; Mp: Decay
T
byT
VT
VM
Case (iii) (Theorem
3.3 Section
3.3
H5
H6
by: Increase; y):
Increase
yM
b M
7 3
VM
Case (iv) (Thcorem 3.4; Section
3.4
Hs
H3
H
H4 bo
1
+ 0
b.: Increase; Yt: Increase Decay
7 MM
T
b M
H; (i E [6] (resp. H7) is positive (resp. nonnegative) number depending on Mmain and M/max Y and 5 are such that 1 < 72 < 8 (e.g., 8 8=2 2 when batch size is doubly increasing every E epochs). The total number of steps when batch size increases M times is T(M) o ME. 0 +(+)) - / implies that
the convergence rate changes from ( to ( when the learning rate т)t changes from an increasing learning rate to decaying learning rate (n): Increase + Decay).
(i) Using constant batch size b, = b and decaying learning rate d (Theorem 3.1 Section 3.1): : Using 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 [[[[V] becomes approximately O (( > 0. This result provides an upper bound on the best. ilerate within T iterations and characterizes how the expected gradient norm scales with the batch size 6 under the considered learning rate schedules. However, this bound does not necessarily mean that mini-batch SGD does not converge to a stationary point in the long run, as it does not characterize the last iterate. Meanwhile, the analysis indicates that using the cosine-annealing and polynomial decay learning rates would decrease [ faster than using a constant learning rate (see S the numerical results in Figure|]
which supported by
(ii) Using increasing batch size b, and decaying learning rate n) (Theorem 3.2 Section 3.2
Although convergence analyses of SGD were presented in (Vaswani et al. 2019 Fehrman et al. 2020 Scaman & Malherbe 2020 Loizou et al. 2021 Wang et al. 2021 Khaled & Richtárik (023). 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 ( rate of convergence, where T represents the total number of optimization steps, and M represents the number of times the batch size is increased during training. Since the total number of training steps when batch size increases M times satisfies T(M) = - bm EE ME, the convergence rates can be analyzed either in terms T or M, giving 0 ) 0 respectively. This result highlights that increasing batch sizes affects the variance
2

---

Published in Transactions on Machine Learning Research (02/2025)
reduction in mini-batch SGD. By analyzing the convergence rate in terms of M instead of Tf we are able to make a more direct comparison with Case (iii), where the geometric batch size scheduling achieves an O x
?
convergence rate. Increasing batch size every E epochs makes the polynomial decay and linear learning rates become small at an early stage of training (Figure 2 2aa)). Meanwhile, the cosine-annealing and constant learning rates are robust to increasing batch sizes (Figure [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
(iit) Using increasing batch size b, and increasing learning rate Tit (Theorem 3.3 Section 3.3
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 scheduler doubly increasing batch size (i.e., 8 = 2). We set >> 1 such that < Vō= = v2 and we set an increasing learning rate scheduler such that the learning rate is multiplied by Y every E epochs (Figure a)). This paper shows that, when batch size increases M times, mini-batch SGD has an O F convergence rate that is better than the O ((/))) convergence rate in Case (ii). That is,
increasing both batch size and learning rale accelerates mini-butch SGD. We give practical results (Figure bb; 5 0= 2 and Figures 5 8 b); 5 = 3, 4) such that Case (iii) decreases [V faster than Case (ii) and tripling and quadrupling batch sizes (5 = 3, 4) decrease [[,) faster than doubly increasing batch sizes (6 = 2). The intuition for why increasing batch size and learning rale can provide fast convergence is as follows:
(1) Increasing batch size decreases the variance of the stochastic gradient, since the upper bound on the variance is inversely proportional to the batch size (see also Proposition [A.]p. Hence, increasing batch size improves convergence to stationary points of the empirical loss f. This fact is based on Case (i) that the upper bound of min (()))l is Oly + !),, where b is the batch size.
(2) Mini-batch SGD does not work when learning rates are small at an early stage of training. This fact is supported by the numerical results in Figure | (Case (i)) indicating that using the decaying learning rate 7) = 0 -(74) (FT)) does not train a DNN. Hence, keeping learning rates large implies that
SGD works well.
(3) From (1) and (2), increasing batch size and learning rate can provide fast convergence of SGD.
Here, let us compare Case (ii) with Case (iii). For simplicity, we use a scheduler tripling batch size, i.c., b, is multiplied by 8 = 3 at each step and consider Case (ii) with a constant learning rate The = satisfying M141 S T7, (t E {0} UN) and Case (iit) with the learning rate no that is multiplied by y (< v8 = v3) at each step. Br in Case (ii) is given by
1
1
BT =
=0
=
T
1
while By in Case (iii) is given by
1
1
BT
0
(
E 1/1
ΣT-
7'100
110 7-1
1-
Vi in Case (ii) is given by
T-1
T-1
17
"
0 (
VF=
Σ
be
Σ
11
t=0
b.
1=0
5bby
by
T 1
Mcanwhile, Vy in Case (iii) is given by
T c
T
7 2
T
2 1
n
1
V/= -t-1 1/t b
S
0
Σ 7/
8'bb
700
T
by
5
T-
by
32
--1
7-1
3

---

Published in Transactions on Machine Learning Research (02/2025)
where 72 < 8 is used to guarantee Et=o (g)) < +o0. Therefore, Case (iii) has B| ( which is better than Case (ii) with oor-
O
(iv) Using increasing batch size by and warm-up decaying learning rate v/e (Theorem 3.4 Section
3.4
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., 2016:
Vaswani et al. 2017 Goyal et. al.) 2018 Gotmare et al. 2019 He et al.] 2019). : We give numerical results SGD with increasing batch sizes and docaying learning rates with a warm-up minimizes [(,)] faster than using a constant learning rate in Case (ii) or increasing learning rates in Case (iii). Our results are numerically supported by the previous results reported in (He et al., 2016 Goyal et al.) 2018 Gotmare et al.) 2019 He et al.) 2019) indicating that a warm-up learning rate is useful for training deep neural networks, such as ResNets and Transformer networks (Vaswani al. 2017).
(Figure 4 ò 2 and Figure 10 ò = 3) indicating that using
2 Mini-batch SGD for Empirical Risk Minimization
2.1 Empirical Risk Minimization
Let 0 E Rd be parameter of a deep neural network; let S {()1))))))))........)))))))))))) (x... yn)3 be the training set, where data point x; is associated with label yı and let f((-) == f(; (z, v.)): Rd R+ be the loss function corresponding to the i-th labeled training data (æ;; (.:.).). Empirical risk minimization (FRM) minimizes the empirical loss defined for all 0 E Id as f(0) = Ligjnn f((O). This paper considers the following stationary
point problem: Find 0 E Rd such that vf(0))= = O.
We assume that the loss functions fo (i E [n]) satisfy the conditions in the following assumption (sec Appendix A 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, > 0 E [n]).
(A1) f:: Rd +R (i E [n]) is differentiable and Lm-shhhth, and ft == in) 0 e R
(A2) Let & be a random variable that is independent of E Rd. Vg:: Rdd Rd is the stochastic gradient of f such that (i) for all E Rd, Eg V5 = ((0) and (ii) there crists a 2 0 such that, for all O E Rdd [c (c - (0) S o², where Be(l]] denotes expectation with respect to E.
(A3) Let b E N such that b S n; and let & = (EI, _6)T comprise b independent and identically distributed variables and be independent of 0 E Rdd The full gradient (() is estimated as the following mini-batch gradient at 0: fB((0) = ; E (O).
The L-smmothhesss of ft in Assumption (A1) is used to analyze mini-batch SGD (Garrigos & Gower 2024 Assumption 4.3), since almost all of the analyses of mini-batch SGD have been based on the descent lemma [Beck] 2017 Lemma 5.7) that is satisfied under smoothness of ft. If f = (f 0 E [d] = -o holds, then the loss function ft corresponding to the i-th labeled training data (æ,, y1) does not have any global minimizer, which implies that the empirical loss f satisfies ft == (f((: e E Rd) = -o. Hence, the interpolation property (Garrigos & Gower, 2024 Section 4.3.1) (i..., there exists 0- E Rd such that, for all i E [n], fi(0*) = f E IR) does not hold, whereas the interpolation property does hold for optimization of linear model with the squared hinge loss for binary classification on linearly separable data (Vaswani le al. 2019. Section 2). Moreover, in the case where f is convex with f -oo, there are no stationary points of f. which implics that no algorithm ever finds stationary points of f. Accordingly, the condition J : (0): 0 E R2) E IR in (A1) is natural under training DNNs including the case where the empirical loss f is the cross-entrop with 0* E Rd such that f(0*) = inf (f): 0 E Hd = O. Assumption (A2) is satisfied when (A1) holds and the random variable & follows the uniform distribution that used to train DNNs in practice (see Appendix A.I for details). Assumption (A3) holds under sampling with replacement (see Appendix A.2 for details).
4

---

Published in Transactions on Machine Learning Research (02/2025)
2.2 Mini-batch SGD
Given the I-th approximated parameter 0, E Rd of the deep neural network, mini-batch SGD uses by loss functions f fe..:".. .ee,, randomly chosen from {f1, f2.... ,nn at each step t, where & = (4,2, _(,,,) is independent of 0, and b, is batch size satisfying b, n. The pseudo-code of the algorithm is shown as Algorithm
Algorithm Mini-batch SGD algorithm
Require: 0g E Rd (initial point), b, > 0 (batch size), > 0 (lcarning rate), 2 (steps)
Ensure: (0.) C Rd
for f ...., T do
fBa. (0,) = b, L
bb 0++1 == 0, T1 V... (0)
V fe... (0.)
4: end for
The following lemma can be proved using Proposition A.1 Assumption 2.1 and the descent lemma (Beck
2017 Lemina 5.7): for all 01, 02 R.a f(02) S ((0))+(V/(()) 02 0,) 1 00 01 112, where Assumption
2.1 A1) ensures that f is L-smooth (L == EiE(n) L.).
Lemma 2.1 Suppose that Assumption
holds and consider the sequence (0t) generated by Algorithm
with Te Mminn Tmaax] C [0, 7) for all T E N,
salisfying
1= 1/2 + O, where L. == 3/2 Eie(m) Li and I" == Enejn] fi- Then,
E [IVS(0)) S 2(f(0o) - f")
Lo²
11= 11 12
min tE
2 Lmmax 2 Lmmax Et= 1/2
21= 1/t
where E denotes the total expectation, defined by E = EE Be.
...
The proof of Lemma 2.1 depends on the following standard inoquality (Garrigos & Gower 2024 (27)) from
the literature on SGD analysis (Garrigos & Gower 2024 Section 5.4, Theorem 5.12) using the descent lemma:
f((,)l1 < f(0n) S"
min rE(O:T-1
+ nLLmax
(1)
17 Σ at
where (at) is defined by a1(1 + 1 LL = 01-1; Imax == maxieln] Li: I the optimal value of ʃ over Idd,
and A - While the existing approach (Garrigos & Gower 2024h uses a sequence (ax) satisfying
Et' a2 2n LLmas the present paper uses learning rate 7)t satisfying E Me 2 O(T) and increasing batch size by satisfying ΣT- 1 +00 in Lemma 2.1 As a result, mini-batch SGD with v) > 0 and the increasing batch size b, satisfy that minleeo-r- B V (0) 0 (Theorem 3.2 which is better than
by
the existing result that SGD with ===- LLmseT satisfies min ( = 0
2
+(+)
(Garrigos &
74
Gower 2024 Theorem 5.1 Section 3.5 compares our results with the existing ones in detail.
The theorems in the present paper are based on Lemma 2. Here, we sketch a proof of Lemma 2.1 The descent lemma under (A1) and the definition of 0.41 imply the following inequality:
f(0++1) < f(0.) - nh (V.... ffa. + Lif
(0))l?
2
Under (A2), the mini- batc- gradient f.B, (0:) is an unbiased estimator of Vf())),, ie., E[ (0:) = (e,)), and the upper bound on the variance of f.p, (0,) inversoly proportional to the batch size b, i.c., V(V fa, (0:) < d² leads to the following:
br (see Proposition A.1 for details). Using the properties of V f., (0t), the above inequality
Lui (0² bb + + [IV)())1
E [f((++))) S (.)) - n. E [[V(
+ 2
5

---

Published in Transactions on Machine Learning Research (02/2025)
Finally, summing the above inequality from t = 0 to - together with f R under (A1) and
E Th + 0, leads to the assertion in Lemma 2.1 A detailed proof given in Appendix A.2
3 Convergence Analysis of Mini-batch SGD
3.1 Constant Batch Size and Decaying Learning Rate Scheduler
This section considers constant batch size and docaying learning rate:
by b (f (EEN N) and 7+11 To NN).
(2)
Let p > 0 and E N; and let 7mmn and 7/max satisfy 1/min Mmax- Examples of decaying learning rates are follows: for all t [0:T].
[Constant LR] 1/max:
(3)
Mmax
[Diminishing LR] Th Vt
(4)
[Cosinc-anncaling LR) = 7min + 7max M/min
1 + cos
(5)
2
K
E
1
[Polynomial decay LR) 1): (Mmax Tmnin)
7mmin
(6)
T
where K= [ is the number of steps per epoch, E is the total number of epochs, and the number of steps T in (5) is given by = K. A simple, practical decaying learning rate is the constant learning rate defined by 3 A decaying learning rate used theoretical analyses of doep-learning optimizers is the diminishing learning rate defined by 4 The cosine-annealing learning rate defined by (5) and the lincar learning rate defined by (6) with p = (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 leads to the following (the proof of the theorem is given in Appendix A.3)
Theorem 3.1 (Upper bound on min, ( for SGD using 2 Under the assumptions in Lemma Algorithm
using satisfies that, for all T E N,
2(S(On) 1()
Loa
2 mi
min 00:T
E [ <
1=0
Lilmax
Lituax
Lt= n
1=0
V/
where p, Muin Maaxx K, and E are the parameters used in
KE = [ E for Cosine LR
5
[Constant LR
Tmaxx
1
[Diminishing LR
mmmxx y T
+
Br S
(7)
Cossiee LR
5
MMain + 7mpax) T
Polynomial LR
(pTmin Tmaxx) T
fmax
[Constant LR
b
Mmxx (1 + log T)
Diminishing LR
2b( TT 1
VT <
31 217mi Vmnx + 37 (mmax Mmin K
[Cosine LR
4(1min 1maxx
6T
2p Amin + +2p7/ain Mhaxx + (p + 1)
(p + 1) Prin)
Polynomial LR
6
(2p + (pmmin Tmnaxb6
(prmin + Tmmax WT

---

Published in Transactions on Machine Learning Research (02/2025)
Let consider using Constant LR. 13
Cosine LR 55 Polynomial LR 6 Theorem 3.1 indicates that
the bias term including Br converges to 0 as ((7), whereas the variance term including Vr does not always converge to O. Hence, the upper bound on min B [(0+))] does not converge to 0. In fact, Theorem 3.1 with 17 = Mmax and Muin
implics that
?
[Constant LR
(3
Lo
3n
sup min E [IV](0))
x
4
[Cosine LR 5
(8)
T4+00 teJo:T
(2 Enyb
1)m (p
[Polynomial LR 6
(2p +1)
[2p+1] <n (p > 0), using the cosine-annealing learning rate the polynomial decay learning rate is botter than using the constant learning rate the sense of minimizing the upper bound on mineg EIIV Theorem 3.1 also indicates that Algorithml 1 using Diminishing LR converges
Since in
1y and 1p+1in
to 0 with the convergence rate minee[ ||| V f(.) O
However, since Diminishing LR. (4) defined by - decays rapidly (see Figure 1 a)), it would not be useful for training DNNs in practice.
TogT
T
3.2 Increasing Batch Size and Decaying Learning Rate Scheduler
An increasing batch size is used to train DNNs in practice (Byrd et al. 2012 Balles et al., 2016 De et al.
2017 Smith et al.) 2018 Goyal et al, 2018). This section considers an increasing batch size and a decaying learning rate following one of (3)
S bet1 (t E N) and M+ S T (t E N).
(9)
Examples of b, are, for example, for all m E [0 M] and all E Sm (So = N n [0, Ko),),
N n [ kk= K2 Eg, E KR Fx)
[Polynomial growth BS) b. am t
10
(10)
Ex
[Eponenniil growth BS) b = Em Ky
bo:
(11)
where a E R4+, c, > 1, and Em and Km are the numbers of, respectively, epochs and steps per epoch when the batch size is (am + bo) or 5 For example, the exponential growth batch size defined by 11 with 5 makes batch size double each Em epochs. We may modify the parameters a and ö to a and monotone increasing with The total number of steps for the batch size to increase M times is T Em= Km Em An analysis of Algorithm I with constant batch size b and decaying learning
rates satisfying 9 is given in Section 3.1
Lemma 2.1 leads to the following them (the proof of the theorem and the result for Polynomial BS 10 are
given in Appendix A.3
Theorem 3.2 (Convergence rate of SGD using 99 Under the assumplions in Lemma using satisfies that, for all M N,
2.
Algorithm
2(f(0)) - f³)
L
2
min E [ rE
+
Limmax
ΣT=1
m
2 Limax
1==
1)t
t=0
by
By
Vr

---

Published in Transactions on Machine Learning Research (02/2025)
where T -=Em=, K Em, Emax dau MEN suPmE]( Em +00, Kmax BT is defined as in (7), and VT is bounded as
sup POPMeNNUPPMeppe supme(0: Km < +00,
Öyhaax Kmax Emnax
Constantt LR
3
(6
-1)60T
07max Kmax Emax
[Diminishing LR
2(6 1)bol VT 11+-111)
Vr -
28mmax max Emax
(Exponential BS
[Cosine LR
(6 (Tmij +max YbyT
(p + 1) K max Ernax
[Polynomial LR
6
(6 (Tmax + "TmimP)bboT
That is, Algorithm 7 using Exponential BS
11 has the converyence rate
[Constant LR.
13, Cosine LR.
55) Polynomial LR
6
min E [
1E
[Diminishing LR
Theorem 3.2
T Theorem
A.1 indicates that, with increasing batch sizes such as Polynomial BS
10 and
Exponential BS 11
A Aggorithm using each of Constant LR (3 Cosine LR and Polynomial LR
(6
has the convergence rate O in contrast to Theorem 3.1
3.3
Increasing Batch Size and Increasing Learning Rate Scheduler
This section considers increasing batch size and an increasing learning rale:
S b (t N) and 1) S M++1 (t E N).
(12)
Example of be and bo satisfying 22 as follows: for all m [0 M] and all Sm
EnE KRE Eno Kx)x) (So = N n [0, KoEn)),
Exponeetiia growth BS and LR] be = Ei Kx bu. 17t =
Σm
k==
Kx
170-
(13)
where d, y > such that 72 < 8; and E,, and Km are defined as in y and 8 be monotone increasing parameters in The total number of steps when both batch size and learning rate increase M times is T= EM Km Em.
11 We may modify the parameters
Lemma 2.1 leads to the following theorem (the proof of the theorem and the result for Polynomial growth
BS and LR [27] are given in Appendix A.3)
Theorem 3.3 (Convergence rate of SGD using 12
Under the assumptions in Lemma
Algo-
rilhm using 12 salisfies thal, for all M E N,
2(S(00) 1*)
Lo²
T-1
m
E [[V < r
min
2 Lopmax
T- Σ Tht 2 Lapmax Et=
br
Ttt
t=0
V4
where T, Emax, and Kmax are defoned as in Theorem 3.2 Emin = inf inf inf j.M] Em < 400, Kmin
inf MEN infme Km < too, f < 1,
8
Kmax 800
BT
VT <
1n K Emin M
Kmin Eminn by 7
That is, Algorithm 1 has the convergence rate
(1}1
min tE 0:
[[]V/(0))]]= = x
[Exponential growth BS and LR
8

---

Published in Transactions on Machine Learning Research (02/2025)
Under Exponential BS 111, using Exponential LR 13 improves the convergence rate from O ( with
Constant LR (3) Cosine LR. (5, or Polynomial LR (6) (Thcorem 3.2) to O M (>>1)
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 Mw
T Σ = Em 0 (learning rate increases My times):
b S b (1 E N)
and Te S 7h+1 (T 11) A M41 S T (1 Tw).
(14)
Examples of by in obtained by combining 11 with 3
are Exponential
BS 13 and Polynomial BS 27 Examples of q in 14 can be For example, for all m E [0 M and all E Sm:
m
[Constant LR with warm-up) f =
Kx
(m E [Mel]
(15)
7 M 170
(m E [Mw M))
and [Cosine LR with warm-upp
?
k=o
KR
170
(m [Mb])
1mnxx
7mmin
7min
+
(16)
1 + cos
mm-1
E5 +
1
-
m
k==
KsEa
Few
(m E [M M)),
Km
Ex
Ens
K=
where Fas is the total number of epochs when batch size increases M times, Enp is the number of warm-up
epochs, Mmin 2 0, 7max = 7 and is defined as in (13
Theorems 3.2 and 3.3 lead to the following theorem.
Theorem 3.4 (Convergence rate of SGD using
14 Under the assumplions in Lemaaa
Algo-
rithm using 14 satisfies that, for all M E N,
E [[ < 2(f(0o) 1t)
Lo
T
min
6E/0:T--
Lipmax
21=0 m
2 Lammax 1==
1)
t=0
b
Vr
where by is the exponentiol growth batch size defined by Emin; and Emax are defined in Theorems 3.2 and 3.3
13 with 8, 7 such that 72 8; Kmins K Kmax,
[Costtant LR
15
170 K min Emin Me
Tmax (T - T
Br S
[Cosine LR 16
1/0 K min Emin Ma
(1min + Prmaa) (T Too)
Kmax Emas 8
Smmaa Kaax Emnax
[Constant LR
15
K min (1
Mw
(6 1)00 Tw)
V
Kmax E Emnax 8
20 Kmax Finx
[Cosine LR 16
Kmin Emiabul Mw
(8 () Tunax bo Tw)
That is, Algorithm I has the convergence rale
min E ([]])(())]| 0
[Constant L.R 15
Cosine LRR
16
VT T
9

---

Published in Transactions on Machine Learning Research (02/2025)
Since Algorithm with 15 and 16 uses increasing batch sizes and decaying learning rates for t Tw. it has the same convergence rate as using (9) in Theorem 3.2 Meanwhile, since Algorithm 1 with 15) and (16) uses the warm-up learning rates for & E [Tw], Algorithm speeds up during the warm-up period, based on Theorem 3.3 As a result, for increasing batch sizes, Algorithm || using docaying learning rates with
warm-up minimizes ((I))( faster than using decaying learning rales in Theorem 3.2
3.5 Comparisons of Our Convergence Rate Results with Existing Ones
This section compares our results with the existing analyses of SGD for nonconvex optimization. The comparisons are summarized in Table [T] Let us consider the case where learning rate тIt is constant,
i.., ?) rj 0. Theorem 11 in (Scaman & Malherbe 2020) indicated that SGD with "f O
satisfies m B f(O))ll - Corollary 1 in (Khaled & Richtárik 2023 showed that, under a weaker condition (the expected smoothness (Khaled & Richtarik 2023 Assumption 2)) than (A2), SGD with f - 0 satisfies minte [BIIV (( Meanwhile, Theorem 3.2 indicates that SGD with 7 = x and an increasing batch size b, satisfies min ( = O {/) ). For example, let us consider training DNN on the CIFAR-100 dataset (n = 50000) over F. = 200 epochs. When the batch size by is 25, the number of steps per epoch is K = hg 1 = 1563. Hence, we have T K 312600. Since the Lipschitz constant L. of f would be large, SGD with too small learning rate 7 = 0 Vi. would not work in practice. Meanwhile, since the learning rate v O is constant with respect to T, SGD with 1 7 ) will work well.
Table 1: Comparisons of convergence analyses of SGD for nonconvex optimization. "Noise" in the Gradient column means that SGD uses noisy observation, i.e. (0) = f(0) + (Noise), of the full gradient (O), where o² is the upper bound on (Noise), while "Mini-batch" in the Gradient column means that SGD uses a mini-batch gradient VfB((). "Strong Growth' in the Additional Assumption column means that there exists k > such that, for all t E N and all i [m], (O.)l 2 xl(Vf((0)]l? "Bounded Gradient" in the Additional Assumption column means that there exists G > 0 such that, for all t E N, B[I.V (0.) s G. "Polyak-Lojastewice in the Additional Assumption column means that there exists p >>> 0 such that, for all E N, [V)(())) 2 2p( f*,, where f is the optimal value of f over Rd, "Armijo" in the Learning Rate column mcans that satisfies the Armijo line search condition. "Step Decay' in the Learning Rate column means that V/2 is step decay. "Polyak" in the Learning Rate column means that tt is a stochastic Polyak learning rate. Here, we let fr|| == minge|o:T11 E|| (0):)l and Bifr] == B[f(Or)]. v E (0, 1) and e positive constant.
Reference and Theorem
Gradient
Additional Assumption
Learning Rate
Convergence Analysis
Scaman & Malherbe
2020
Noise
7 ==0
E B = 0 (+)
VLT
Vaswani al.
2019
Noise
Strong Growth
Armijo
fr
(+)
Vingg
Wang et al.
2021
Noise
Bounded Gradient
Step Decay
E V 0
T
Loizou et al.
2021
Noise
Lojjsk-Eojasiiiiiz
Polyak
B[Sr] = l O(U + 4
Khaled & Richtárik
2023
Mini-batch
==
VLT
E V
Theorem
3.2
Case (ii))
Mini-batch
=
(+)
B =
Theorem 3.3
Case (iii)
Mini-batch
Increasing
E V
Theorem 3.4
Case (iv))
Mini-batch
Warm-up
E V 0
The previous results reported in (Vaswani et al. 2019 Wang et al.) 2021 Loizou et al. 2021 showed
convergence of SGD with specialized learning rates, such as the Armijo line search learning rate, step decay
10

---

Published in Transactions on Machine Learning Research (02/2025)
learning rate, and stochastic Polyak learning rate. Our results indicate that SGD using practical learning rates, such as the cosine-annealing and polynomial decay learning rates, minimizes min [III (O,,) (0,)]] in the sense of rate of convergence O( (T)) (Theorem 3.2 In addition, would like to emphasize that, using an increasing batch size, SGD with an increasing learning rate accelerates SGD with constant learning rate (Theorem 3.3) The acceleration of SGD is guaranteed during 1/t - and the convergence of SGD is not guaranteed during 1i > - Therefore, using a warm-up constant learning rate (Case (iv)) is appropriate to guarantee fast convergence of SGD.
3.6 Comparisons of Convergence Rates under Nonconvexity with Ones under Convexity
While Sections 3.1 3.5 consider the case where is not always convex, this section considers the case where f is convex and compares convergence rates under nonconvexity with ones under convexity. Table 2 summarizes the convergence rates under nonconvexity and convexity. The left column in Table 2 obtained from the results in Sections 3.1 3.4 (see also the table in Section 1). A well-known performance measure of Algorithm [ when f is convex is mi (e.) - f*] [Garrigos & Gower 2024 Section 9.1), where f is the optimnal value of minimizing convex function f. The right column Table gives the results under convexity of f. An upper bound of mine 10:7-1] (0.) f*] for the sequence (0.) generated by Algorithm can be obtained by using Lemma 2.1 that is, the result when f is not always convex (the proof of the results for convexity is given in Appendix A.4. While the performance measure min+gjo:TT ((()) for nonconvexity of f differs from the measure min (0.) - [*] for convexity of f. Algorithm under, for example, Case (ii) with convexity of satisfies that min E[f(0;) f1 = 0
Comparisons of convergence rates under nonconvexity (Left) with ones under convexity (Right). f* the optimal value of the minimization problem for a convex function f. and Case -aCee (iv) are the learning rates and batch size schedulers considered in Section 3.1 3.4 (see the table in Section for the definitions of b, 7, M, and T)
Table 2:
Upper bound of min B[[[V/(O,)]
Upper bound of min E(S(O,) S*) (f convex)
Schedular
(f is nonconvex)
tE|0:7-11 xonconvex)e((o771
1e(0:T1]
1
1
Case
0
T
b
7
1 VT
(
Case (ii)
0
O
VM
M
1
1
Case (iii)
0
0
M
7
1
1
Case (iv)
0
+
0
0
1f
VT
MM
7
4
Numerical Results
We examined training R8sNet-18 on the CIFAR100 dataset by using Algorithm 1 (see Appendices A.9 and A.10 for training Wide-ResNet-22-11 on CIFAR100 and ResNet-18 18 on Tiny ImageNet). The experimental environment was two NVIDIA GeForce RTX 4090 GPUs and Intel Core 19 13900KF CPU. The software environment was Python 3.10.12 12, Py Torch 2.1.0, and CUDA 12.2. The code is available at https://github: both bs 1r
We the total number of epochs E 300, the initial learning rate no 0.1, and the minimum learning Mwin in (5) and 66) The solid line in the figure represents the mean value, and the shaded area in the figure represents the maximum and minimum three runs.
11

---

Published in Transactions on Machine Learning Research (02/2025)
Let first consider the case (Figure [aa) of constant batch size (b 2²) and decaying learning rates
The defined by 13 6 discussed in Section 3.1 where "linear" in Figure | denotes Polynomial LRR (6) with
p= == L. Figure Lb) (d) indicate that using Diminishing LR 4 did not work well, since it decayed rapidly
and was very small (Figure Ia)). Figure [b)-dd) also indicate that Cosine LR (5 and Polynomial LR (6)
performed better than Constant LR as promised in the theoretical results in Theorem 3.1 and
Taren Spe
(a) Learning rate tp and batch size versus epochs
(b) Full gradient norm (0.)l
versus epochs
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 1: (a) Decaying learning rates (constant, diminishing, cosine, linear, and polynomial) and constant
batch size, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train ResNet-18 on CIFAR100 dataset.
Learthg hota and Bast dbe Strcklt
Fertect en DEOZEE
413
640
0.40
110
(a) Learning rate H/e and batch size versus epochs CR0030
(b) Full gradient norm
|f(()))] versus epochs
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 2: (a) Decaying learning rates and doubly increasing batch size every 30 epochs, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train ResNet-18 C10 dataset.
12

---

Published in Transactions on Machine Learning Research (02/2025)
Next, let us consider the case (Figure a)a of doubly increasing batch size every 30 epochs from an initial batch size bn = 2 and decaying learning rates 1/8 defined by (3 Figure 2(a) indicates that the learning rate of Polynomial LR (6p updated each step ("linear' and "polynomial (p )) becomes small at an early stage of training. This because the smaller the batch size b, is, the larger the required number of steps K2 = per epoch becomes and the smaller the decaying learning rate T/ becomes. Hence, practice, increasing batch size is not compatible with Polynomial LR (6) updated cach step. Mcanwhile, Figure 2aa indicates Constant LR (3) (*constant') and Cosine LR (5) ("cosine") were compatible with increasing batch size, since Constant LR. (3) and Cosine LR 5 updated each epoch maintain large learning rates even for
small batch sizes. In particular, Figure (d) indicate that using Constant LR
(3 performed well.
Let us consider the case (Figure 3 a)) of doubly increasing batch size (ō = 2) every 30 epochs and increasing learning rates defined by Exponential growth LR (13) with To = 0.1 The parameters y in the increasing learning rates considered here were (i) 7 R 1.080 when 7max 0.2, (ii) Y Rs 1.196 when 7mma = 0.5, and (iii) y R 1.292 when 7max 1.0, which satisfy the condition 72 < 8 (= 2) to guarantoe the convergence of Algorithm]] [ (see Theorem 3.3). Figure compares the result for "constant" in Figure with the ones for the
increasing learning rates (i) (iit). Figure 3(b) b) indicates that the larger the learning rate ?t was, the smaller
the full gradient norm |/ ((.) became and that Algorithm wwth increasing learning rates minimized the
full gradient norm faster than Algorithm with a constant learning rate ("constant' in Figures and
Leuring
AMtret en CENAEE
0.2
(a) Learning rate ip and batch size versus epochs
(b) Full gradient norm (0.)l versus epochs
Rodil CONTER
18
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 3: (a) Increasing learning rates (7max 0.5, 1.0) and doubly increasing batch size every 30 epochs, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train R8 on CIFAR100 dataset.
Let us consider the case (F)gurefaa) of a doubly increasing batch size and decaying learning rates (Constant LR (3) and Cosine LR (5) with warm-up based on Figure Ba). Figure [b) indicates that using decaying learning rates with warm-up accelerated Algorithm more than using only increasing learning rates in Figure Bb) and only a constant learning rate in Figure b).
From the sufficient condition 7² < 8 to guarantee convergence of Algorithm with both batch size and learning rate increasing (Theorem 3.3). we can set larger when is large. Since Algorithm [ has an O 1, convergence rate (Thcorem 3.3). using triply (7 = 1.5 < v8 = v3) and quadruply (> =
1.9 < V8 = / increasing batch sizes theoretically decreases || V [(e))l) faster than doubly increasing batch sizes (r 1.080 < V8 v2 when 7max = 0.2; Figure 3 Finally, we would like to verify whether the theoretical result holds in practice. The scheduler was as in Figure 5(a) with nu = 0.1 and Mmax 0.2, where schedulers were modified such that batch sizes belong to [23 212] and learning rates belong to |0.1, 0.2) (e.g..
13

---

Published in Transactions on Machine Learning Research (02/2025)
be adl b and ? ecl d, where 0.2077, b 7.7923, 0.00267, and d 0.09733 when 8 = 3 and 7 1.50 and a z 0.0155, b x 7.9844, R 0.00031, and z 0.09969 when å = 4 and Figure a) and (b) indicate that the larger the increasing rate of batch size was (the cases of 8 = 3, after 180 epochs), the larger the increasing rate of the learning rate became (7 = 1.5, 1.9 when d = 3,4) and the smaller [[=)( became. That is, using increasing learning rales based on tripling and quadrupling batch sizes minimizes V (0.)) faster than using increasing learning rates basod on doubly increasing batch sizes (see also Appendix A. Figure (c) and (d) indicate that using 6 3, 4 better than using 8 2 in the and achieving high test accuracy.
-1.00).
sense of minimizing f(0.)
Learn lats un Batch ConOUu
bealln03 on O'NNSE
(a) Learning rate N and batch size b versus epochs Ne chease
(b) Full gradient norm [[a)) versus epochs
sumeece aweiee
cad
13
couted
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 4: (a) Warm-up learning rates and doubly increasing batch size every 30 epochs, (b) full gradient norm empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train ResNet- on CIFAR100 dataset.
(a) Learning rate and batch size b versus epochs
(b) Full gradient norm [(.)) versus epochs
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 5: (a) Increasing learning rates and increasing batch sizes based on 8 2,3,4, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train ResNet-18 CIFAR100 dataset.
14

---

Published in Transactions on Machine Learning Research (02/2025)
To better understand the impact of increasing both batch size and learning rate, compare the full gradient norm across the four cases Case (i) -ase (iv) using ResNet-18 on CTFAR-100 in Figure [ The results highlight that Case (iv), which employs both a larger batch size and warm-up learning rate, exhibits the most favorable convergence properties. Specifically, Case (iv) achieves a significantly reduced full gradient norm throughout training compared to the other cases, confirming its effectiveness. Building on these observations, we validate the scalability of Case (iv) on the larger ImageNet dataset. The results, presented in Appendix A.5] further highlight the advantages of this scaling strategy in improving training efficiency and accelerating convergence large-scale tasks.
ResNet-18 on CIFAR100
Caseli): Const-BS, Decay-LR
Full Gra Gra dient Norm of Empirical Loss for Training
Caselii) Incr-BS, Decay-LR
10
Case(iil) Incr-BS, Incr-LR
Casellv): Incr-BS, Warmup-LR
10-1
10-2
50
100
150
200
250
300
Epochs
Figure 6: Performance comparison of best configurations for full gradient norm using Case (i) to Case (iv)
to train ResNet-18 on CIFAR100 dataset.
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 guaran- tees 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 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 mum- bers of models and datasets in the experiments were limited. Hence, should conduct similar experiments with larger nunbers of models and dalasets to support our theoretical results.
Acknowledgments
We are sincerely grateful to the Action Editor, Ali Ramezani-Kebrya, and the three anonymous reviewers for helping us improve the original manuscript. This research is partly supported by the computational resources of the DGX A100 named TAIHO at Mejji University. This work was supported by the Japan
Society for the Promotion of Science (JSPS) KAKENHI Grant Number 24K14846 awarded Hidcaki
liduka. The authors thank FORTE Science Communications (https://www. wwwp::fforttteieeneeeo co.ience.co..p./ for English language editing.
15

---

Published in Transactions on Machine Learning Research (02/2025)
References
Lukas Balles, Javier Romero, and Philipp Hennig. Coupling adaptive batch sizes with learning rates, 2016. Thirty-Third Conference on Uncertainty in Artificial Intelligence, 2017.
Amir Beck. First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadel- phia, PA, 2017.
Richard H. Byrd, Gillian M. Chin, Jorge Nocedal, and Yuchen Wu. Sample size selection in optimization methods for machine learning. Mathematical Programming, 134(1):127-155, 2012.
Hao Chen, Lili Zheng, Raed AL Kontar, and Garvesh Raskutti. Stochastic gradient descent in correlated set- tings: study on Gaussian processes. In Advances in Neural Information Processing Systems, volume 33, 2020.
Blang-Chiell Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan L. Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. IEEE Transactions on Pattern Analysis and Machine Intelligence, (0(4):834-848 2018
Soham De, Abhay Yadav, David Jacobs, and Tom Goldstein. Automated Inference with Adaptive Batches. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp.
PMLR, 2017.
Benjamin Fehrman, Benjamin Gess, and Arnulf Jentzen. Convergence rates for the stochastic gradient descent method for non-convex objective functions. Journal of Machine Learning Research, 21:1-44 48, 2020.
Guillaume Garrigos and Robert M. Gower. Handbook of convergence theorems for (stochastic) gradient methods, 2024. URL httts:///arttii wttp:/wwww.o////b////111213
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochas- tic composite optimization A generic algorithmic framework. SIAM Journal on Optimization, 22:1469- 1492, 2012.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochas- tic composite optimization II: Shrinking procedures and optimal algorithms. SIAM Journal on Optimiza- tion, 23:2061-2089, 2013.
Akhilesh Gotmare, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. closer look at deep learning heuristics: Learning rate restarts, warmup and distillation. In International Conference on Learning Representations, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training imagenet in hour, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Computer Vision and Pattern Recognition, pp. 770 778,7777 2016.
T. He, 7. Zhang, Zhang, 7. Zhang, J. Xie, and M. Li. Bag of tricks for image classification with convo- lutional neural networks. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 558 567, 2019.
Andrew Hundt, Varun Jain, and Gregory D. Hager. sharpDARTS: Faster and more accurate differentiable architecture search, 2019.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 448-456, 2015.
16

---

Published in Transactions on Machine Learning Research (02/2025)
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. Transactions Machine Learning Research, 2023.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In International Conference on Learning Representations, 2020.
Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Lacoste-Julien, Stochastic polyak step-size for SGD: An adaptive learning rate for fast convergence. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, volume 130, 2021.
llya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In International Conference on Learning Represenlations, 2017.
Jun Lu. Gradient descent, stochastic optimization, and other tales, 2024.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approxima- tion approach to stochastic programming. STAM Journal Optimization, 19:1574-1609, 2009.
Herbert Robbins and Herbert Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22: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 J. Shallue, Jachoon Lee, Joseph Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George Dahl. Measuring the effects of data parallelism on neural network training. Journal of Machine Learning Research, 20:1-49, 2019.
Samuel L. Smith, Picter-Jan Kindermans, and Quoc V. Le. Don't decay the learning rate, increase the batch sizc. In International Conference on Learning Representations, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention All you Need. In Advances in Neural Information Processing Systems, volume 30, 2017.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. In Advances in Neural Information Processing Systems, volume 32, 2019.
Xiaoyu Wang, Sindri Magnússon, and Mikael Johansson. On the convergence of step decay step-size for stochastic optimization. In Advances in Neural Information Processing Systems, 2021.
Yuting Wu, Daniel Holland, Mick D. Mantle, Andrew G. Wilson, Sebastian Nowozin, Andrew Blake, and Lynn F. Gladden. A Bayesian method to quantifying chemical composition using NMR: Application porous media systems. In 2014 22nd European Signal Processing Conference, pp. 2515-2519, 2014.
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.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. Proceedings of the 20th International Conference on Machine Learning, pp. 928 936, 2003.
17

---

Published in Transactions on Machine Learning Research (02/2025)
A
Appendix
We here give the notation and state some definitions. Let N be the set of natural numbers. Define [n] == 21, n and [0: :n] : 1,, .n) for n E N. Let R2 be the d-dimensional Euclidean space with inner
product 02) = 0 02 10,,02= E IR4) and its induced norm ||0]| = v (00.0) 0) (0 E Rd). Let R == {0 = (01, (..00.,00)). 0J) :R: 0, ( [d]} and I == {0 = (01,02. ....0...... 0a) E R 0, > 0 ( [d))- The R. R 0 E Ed is denoted by Vf(0). Let L>
diffcrentiable function I: Rd IR is said to be I-smooth if the gradient Vʃ: I2d RR Lipschitz continuous, i.e., for all 01, 02 Id [(1) vf(02)) s LI|01 02ll- Let (xz), (yt) C R+ be sequences. Let O be Landau's symbol, i.c,, Yr = (z,) if there exist E R., and to N such that, for all t 2 to, S C.
gradient of a differentiable function f:
A.1 Example of Stochastic Gradient satisfying (A2) under (A1)
Suppose that (A1) holds and random variable & follows uniform distribution. Then, let us show that (A2) holds, that is, for all 0 E IR,, (i) [v(V)((0)) = (0) and (ii) Ve(VSe(OO) s o².
(i) Since & is independent of 0, we have that
E Ve Σ Vf(()= =
Σ fi (E(n)
(0) Vf(0).
VE(N)
iii) Let 0 = 0 T, V)()). The descent lemma and J = (:)): 0 E [Rd E R ensure that
L
f ((() & ((() (V) 0 0)
0 0
|V + - |V
= - T
2T.
1
= f((0) 2L, [V)(00)
which implies that, for all i [n].
( < (f. ft) s 2L,M.
where M4 =
- su: R..
Hence from (i),
V=(V/f(()] = E3 V f 0) (
EE -EelIIV/e
- -
Σ -
n sEin
< 2 L.M.
SE|n]
A.2 Proofs of Proposition A.1 and Lemma 2.1
The following proposition holds for the mini-batch gradient.
Proposition A.1 Let N and & be random variable that is independent of & 10 11); let 0, E Rd be independent of Ex; let f. (0.) be the mini-balch gradient defined by Algorithm 1 where SeL. (i [bz]) is the stochostic gradient (see Assumption 2.1)))) Then, the following hold:
Eg. VfB, (1)( vf(), and Ve. (.)) s o²
be"
18

---

Published in Transactions on Machine Learning Research (02/2025)
where Eg, [/(-11 and V2,1-E6-1 are respectivcly the expectation and variance with respect to conditioned on Er-1 11
The first equation in Proposition A.1 indicates that the mini-batch gradient V.n, (0:) is an unbiased estima of the full gradient v.( The second inequality in Proposition A.1 indicates that the upper bound on the variance of the mini-batch gradient VfB, (0:) inversely proportional to the batch size by.
Assumption 2.1 2.1.A3. A33) holds under sampling with replacement, where ç = (fi, (2. _6) are independent and identically distributed (ii.d.). In practice, however, sampling without replacement is commonly used to im- prove data efficiency and diversity. Under sampling without replacement, minor dependencies arise between samples, particularly when b = n. These dependencies reduce the conditional variance V4, fe, (0:)),-1)) resulting in behavior that closely resembles full-batch gradient computation. On the other hand, when < n, the dependencies introduced by sampling without replacement become negligible, and the behavior of the mini-batch gradient closcly approximates that of i.i.d. samples. Under such conditions, the theoretical properties of Assumption A.3) are approximately satisfied. Therefore, in large-scale datasets, the approx- imation of i.i.d. is sufficient to ensure that the theoretical predictions remain valid under sampling without replacement. The experimental results (Appendix (A.8) further confirm the validity of this approximation, as the observed behavior aligns closely with the theoretical predictions.
The proof of Proposition A.1 is based on standard results from the literature on SGD analysis Garrigos
Gower 2024 Section 6).
Proof of Proposition A.1 1 Assumption 2.1 A3) and the independence of be and & ensure that
b.
b. E
Eg. V ff. (0.) E-
Bg. be
(0))
(0)
be
which, together with Assumption 2.1 (i) and the independence of & and Er-1, implies that
be vf(0,) = v.).))
Ee (0.)
(17)
b
Assumption 2.1 A3), the independence of by and E,, and 17 imply that
Ve. VSD, [in,
(0.) Ec = Fe,
V V (0,)
(((0)))
b,
= =Fe
Je,, (0.) - v)(0.)
E.
b
b
//-
1 Egg
(.).. \/(0,)) (0).
From the independence of E., and &.j (i * j) and Assumption 2.1 (2)(1), for all i, [bx] such that i + j.
Eg. I. (0,) ( V (0,) - v.(0))))
(B (.. Es., Vf(0.) V Vfe,, Vf((.))
0.
Hence, Assumption 2.1 (ii
guarantees that
b.
j2b, r²
Ve. VIn (0)
E-]]
Bec.
[IV (((0)))(($á-1) 5
b² by
which completes the proof.
19

---

L Published in Transactions on Machine Learning Research (02/2025)
Proof of Lemma 2.1 The L-smoothness of implies that the descent lemma holds; i... for all E N,
f(0(+1) s
(V.(0.), 0v 0.) + 110 0rl1
which; logether with O.-1 = 02 1). VB B, (0.), implies that.
L
5 f(,)) - (V. Vf
Vff,((,)))
(18)
2
Proposition A. guarantees that
Ee, | [.B (0,))
Eg
[VV5 - v)((,) + V/(0,11 E
[IV (0.) - v/(0,11 [
Ee,
(19)
+ 2Eç, (V... (0.) - vf(O.). v(((.)) { + +Eg [IV [--]
+ [VS(0)11
Taking the expectation conditioned on f Ê on both sides of 18 together with Proposition A.1 and 19h. guarantees that, for all E N,
Lud Eg. (e)))(0)) [c-1
Es. [(0041) & f(0,) - 7B (V(())). VfB. (0:)) f(0.) ne ( + Lud
61-1
+
2
o²
by
Hence, taking the total expectation both sides of the above inequality ensures that, for all / N,
The (1
Laf E
Lo 2b.
|V(0,)11 ((S(0,) f(0+
Let T E N. Summing the above inequality from 0 to t T ensures that
T-1
(1 Lape
[f((0) f(0r)] + Lo 2
Σ 7
E
[
2
2
1=U
t=0
which, together with Assumption
2.1
A1) (the lower bound f Σie(n] (m]) Ji of f), implics that
T-1
Σ
Lnp.
[VT(O)))P] s f(0)) - f +
Lo T
m
T/
2
b
Since Tt E [imin 7mmax], we have that
(1 (1- Lmmax
Loa
T
2 ME [V+ s s(0o) fr
m
2
b
1=0
which, together with Ne [Prain , Mmnax]
[0, 2). implics that
T-1
< ((0 - 1") +
Loa
T-1
Σ E [V.(0)111
(20)
ITmmax
2 Lmpaax
b,
0
1=
Therefore, from E o O, we have
2(,( -fr
Loa
Σ1 17 D
min -
+
(21)
2 Lmpmax
> 7)c 2 Lipuax
Σ1 7t.
which implies that the assertion in Lemma 2.1 holds.
20

---

Published in Transactions on Machine Learning Research (02/2025)
A.3 Proofs of Theorems
We can also consider the case where batch sizes decay. For simplicity, let set constant learning rate n) 7) and a decaying batch size b, - where b > 0. Then, we have that VT S 7 o b, 2b
z(7 +00
(T - +o0), 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.
Let 7max = 1).
[Constant LR. 8 We have that
T- 21 11
7 b
By
VT
Σ -1=0 11
T-1
1/T
6 Σ 11= "
[Diminishing LR
We have that
T-1
/
Σ
2
=
1=
0
Vt+1
which implies that
Br T-1 $ Dn(vT+1-
Et= ViII
We also have that
T-1
(-1
T-1 dt
Σ
t+1 11
t+1 = 1 + log T,
t=
which implics that
E HI
(1 + log T)
VT = T-
2b( T + 1)
V
(Cosine LR
We have
KE-1 1
KE-1
Σ
Mmin K +
Mmax
7mmin
KE-
Mmax
7min
Σ
COs
1. π
2
K
E
t=
1=
From ΣKB cos|
K
E
= K 1, we have
KE-1
π
CoS
COS π
(22)
K
E
We thus have
KE-1
Σ T) Mmin KE Tmax 7min KE Mmax 1mmin K
2
1
- 2 (Tmin + Mmna JE + (Tmax Mmnin }}
(7min + 7max >
21

---

Published in Transactions on Machine Learning Research (02/2025)
Moreover, we have that
KF-1 Σ
KE
ne
Mmin K + Mmmnn (7mxx 7minn
Σ
1
+ cos
π E
K
1=
(mmax
Mmin )2
KB-1 Σ
π
+ Cos
4
K
E
1=0
which implies that
KE-I Σ t=
(mmxx
Mmin )2
KE
π
N =
Mmnin Tmax K E +
+ -mmin (7max 7mmin)
COs
K
E
t=
Mmnxx
7min )
KE-1
Σ
π E
Mmax
7min )2
KE-1
Σ
π
+
COs
cos
2
K
K
E
1=0
1=
From
KE
KE
π
COS
1
cos
cos
K
E
2 1=0
K E
1=0
2 - + 1)
KE
+1,
we have
KE-1
Σ
cos2
K
KE
+
COS π
KE
K
E
2
2
From 22
we have
KE-1
(Mmin + Mmnax)
Muiin ) K + (Amax Mmain) )2
(Tmax - "min )2 K F.
Σ
nh
KE + Main (fmax
+
4
2
4
2
t=0
3ymin + 2//min Phnax + 31 KE E + (hhax Mnin (Thaa + Manin K.
Hence, have
1
By
-KE 5
(/min 1/maxxx KR
2m=0
and
Σ
11= 1/1
KE-1
31 + 2mqimn Mmax + 31/
Mauax Muin
VT
DEKE-1 176
4(1mio + Mmax) b
bE
PPolynomial LR. 6
Since f(x) (1 - -)) monotone docreasing for x E [0, 1), we have that
1'' (1- dx -
M (1-1 (1-)),
which implies that.
T (1 (1-
<
T-1 1
Σ
- t
)
(23)
1=0
22

---

Published in Transactions on Machine Learning Research (02/2025)
1 Since 1o x) p+1
23
implies that
1
T
Σ
T
p+1
t=
Accordingly,
T-1 Σ t=0
T (7max
7min
Σ
1
t
P
Tmin T
t=0
T
(7max
7min
Vmin
T
p+1
Imax
Mmin
+ 1mii
T
p
7max + 7mminP T.
p
Since ((x) (1 =P and g(x) (1 22 are monotone decreasing for x E [0, 1), have that
T-1
1
t T
+ [ (1 Pd
Σ
T-1
(1
1
2p
1 + / (1 - dx
T
T
T
which imply that
T
Σ 0=
P 1 (1-4)²
< 1 +T (110 (1- x:) dr.
T-1
Σ
1 1- 7) (
<1 < + T //' (1 p.
(24)
1=
Since we have that Jo - (1-))dd
= p+1
1 and 1o - x))
2p+1'
24
ensures that
T- l
Σ
t
p
<
T
T-1
Σ
1
t
+
T
p+1'
T
2p
+
1
t=
1=0
Hence,
T
T-1 1
T-1
P
2 (Tmax Mmin )2
Σ
+ 2 ((7max 7min))
Σ
1
Mmin + m T
T
T
1=0
1=
1=0
T
T
(Tmax mmin )2
+ +(1mmxx 1mln))
1+
Mmnin + m T
2p +
p + 1
manx (p + 1)(2p + T + 1) + "MmaxxmmiiPP pf + When
(2p² - 1) -3p - 1)
(p + () +1)
Therefore,
1
p+1 1
BT
Σ Σ1=0 171
(Tmax + 7min T
and
Vr 1== Vh
Viax (p + (2p + + 1) + 2mxx pT + 2 ( - 1) - -3p 1)
(2p + 1) + D)
23

---

Published in Transactions on Machine Learning Research (02/2025)
2p2n Mmin + 2p7mmin maxx + (p + 1)
(p + 12(pp ()2pp + 1) (p 1)(2p 1)
(2p + 1) (pTmin 7mmax)
(2p + (p 7mma))6
2p Tmin + 2p7mmiu Mmax + (p + 1)xuxx
(p + 1) mminn)
(2p + 1) (pTain Mmaax )b
(Munin + 1/max )67
This completes the proof.
We will now show the following theorem, which includes Theorem 3.2
Theorem A.1 (Convergence rate of SGD using (9) Under the assumplions in Lemma rithm
Algo-
using g
satisfies that, for all M N,
2(S(00) 1))
Lo²
T-1
min 1
[
2 Limmx
Σt
2 Lijmax Σt- T/
be
t=0
VT
where T EM Km Em, Emax suPMeN sup m Em +00, K Kmax supMEN Sup Km < +00,
min min(a, (a, bo), Br is defined as in 7 and VT given by
31max Kmax Fmax T 3mmax maxx E Fmax
Constant LR.
Diminishing LR (4)
20 (a(Tv++I 1) 6 K Kmax Emax
S
([Polynomial BS
10
[Cosine LR.
5
(1min + Mmmax) YT 3(p + M)xax Emax @ (Tmmax + Tminp]T
Polynomial LR
6
Ö7haax K Maxx Emax
[Constant LR
3
18 -
87hmax Kax Emax
[Diminishing LR
2(8
+ 28mmax K max Fmax
1)0ol
V/ s
(EExpnential BS
[Cosine LR
(6 () + Mmax IbyT
(p + 1)ō1fmax K maxx Frnax
[Polynomial LR
6
(5 1)mmax + MmainP)by
That is, Algorithm i using each of Polynomial BS
10 and Exponential BS
11 has the convergence rate
o
[Constant LR
Cosine L.R. 5) Polynomial LRR
G
min 10
E [[|
Diminishing LR
T
Proof of Theorem A.1 Let M E and T IM Km where Emax = supMeN sup supmee(o:M Em < to0, Kmax suPMeN sup suPme]u:M) Km < +00, So = N [0, KoEo), and Sm N En K2 Ex, En KxEs) (m E [M). Let us consider using 10). Let Mmna = n and a min(a, bo)
[Constant LR
3
Let m E [M]. We have that
Σ SESm
Σ
b
LES
am
KeEe
+
reSm amme
Σm KeEi
Kmax Emax
Km Em
S
m
m
a"
m
a
m
S
24

---

Published in Transactions on Machine Learning Research (02/2025)
and
Σー
K max Emax
bb
b6
α
tESo
rESu
Accordingly, we have that
M
max Emax
M
max Emax
Σ
1+
1+
b
a
m
a
m
m== S.Sm
m=1
m=1
(25)
3K max Emax
Hence, we have that
T-1
11
max Fmax
V
S
Ei=
1
1=
b1
a
Diiinishiig LRR
4
From
25
have that
T-1
VT
Σ
T-1
7
(t + 1)bt
f=
VtII
0=
"
T
3n max max Emax
2(vT+I-
b
29 -I
[Cosine LR.
The cosine LR is defined for all
[0 M] and all E Sm by
mm-1 1
> mm k-O
Th 7min + Tmax
7min
+ c0s
co8
Σ
Ex +
2
Km
EMs
k=U
We have that
T
1max
b,
1=0
1=U
which, together with 25
implies that
3/ Kmax
71
by
a²
Hence, we have that
1
11
6 K KmaxEmas
VT
T-
b
a (Tmin + Mmaxx T
1==
1Jt
1=0
PPolynoiil LR
6
We have that
T-1
T-1
(fmax Bmin) (1 (1- 7
2
T
+ Mmin
S
b
b
by
which, logether with
25
implies that
T
3 Kmax Emax
by
a
O
25

---

Published in Transactions on Machine Learning Research (02/2025)
Hence, we have that
T-1 R v
3(p + 1)mmax Kmax Fanx
VT
Ei=0
b a (mmaax Mmiaa)) T
t=0
Let us consider using
Let Mmax = 17.
[Constant LR
3
We have that
max Emax bm
b
80
BESm
BESm
rESm
k-
K2
bo
which implies that
Σ
M
Σ
K max Emax
M
S
K Kmax
(26)
b
bo
8m
6o 1)
m=D:ESm
m==
Hence, we have that
Kax (.maxEmaxl
VT
Et=
17
bt
66 1)T
[Diminishing LR
4
From
26
have that
17
K maxx E Emax 8
V
S
Σ 0
T-1
(t 1)b
+I
bt
2 2(vT T + 1000 - 1)
1=
[Cosine LR We have that
T
Mmax
b
which, together with 26
implies that
T Kmax Emaxd
6p
1=
Hence, we have that
T-1 1
111 <
2m K max Emaxx
Vr
ΣT-
b
(6
(T + Imax TbT
1)
1=0
[Polynomial LR.
6
We have that
T-1
T-1
1 [ ))² T
2
T-1 Mmax
(mmax Imiu)
+ Mmin
b
b,
which, together with
26
implics that
2 K Kmax Emax
66
1=0
26

---

Published in Transactions on Machine Learning Research (02/2025)
Hence, we have that
T-1
" (p 1 1) K max 6
VT
1
bt
(6 (Mmax + Mminn bu T
-1=
1/t
Example b, and de satislying 12 is as follows:
[Polynomial growth BS and LR]
o1
t Lk=
02
(27)
b, a1m Ek=o K&EK
+ bu
n
a2m
170
Ex
where 01,as 02 > 0; 6 1, 02 such that 202 1.
We next show the following theorem, which includes Theorem 3.3
Theorem A.2 (Convergence rate of SGD using 12 Under the assumptions in Lemma 2.1 rilhm using 12) satisfies that, for all M E N,
Algo-
2(S(00) 1n)
Lo²
min rE(O.T-1
[IV)())
2 Limmxx
Et= the
2 Lijmax
b0.
2t=
t=0
Bo
VT
where T Em EmEm Emax MuN suPme]]:M] Em < t00, Emin inf MEN inf.e] En +00,
Kmax su su Km < t00, Kmin inf inf me(oda] Km < toc, n min no), π
max(az, no), min min but, 9- 2 <1,
1 C2
[Polynomial growth BS and LR
27
212 Kiin Emin M
Br S
[Exponential growth BS and LR 13
1/o Kmin Emin M
2 Fruaxe (1 20)
Polynomial growth BS and LR 27
K min Emiin c M maaxe F 8
Vr
Exponential growth BS and LR 13
Kminn MM
That is, Algorithm 7 has the convergence rate
[Polynomial growth BS and LR (27
min E | telo:T-11
M
[Epponentia growth BS and LR
13
Proof of Theorem 2. Let M and T' Em=o Kmbi where Emax supMeN sup supme](:M E' < t00,
.M
Kmax suP sup M Km < +00, So = Nn [0, KoEo), and Sm N n En K2 Er, En K&Es) (m E [M].
[Polynomial growth BS and LR 27
We have that
22
Σ Tr
a2m
170
>
Σ
(a2m + 72
k= Ex
S....
LES..
which, together with 7 min min(az, no), implies that
Σ n 2
Σ 1
(m +
1m 1722 Kmin + 1)
27

---

Published in Transactions on Machine Learning Research (02/2025)
Hence,
M
M+1
17 Kmiii Minin M t
Σ
2 8
K min min
Σ
m 2
1 C2
m=D DE Sm
m=1
We also have that
202
amm
Ti k=n
Bx
+ 170
(agm + 170
2n2
b
CT
(a + bo)
Sm
Sm
amm
Ex Kebi
+ bo
tESm
Let 7j max no} and = minfar, but. Then,
Σ
M
S K max Emax
M
(m 1)202
S max Emnx
M+1
1
be
(m + 1)01
b
m - 202
m= EESm
m=0
m=1
2K max T) 202
6
Hence,
1+ Kinn Emin +02
By
I
ET-1 tl
11.2
and
T
2k max Faaa + C22 02)
1
S
E1= Ut
T
b
Kmin a ba M
t=0
Exponential growth BS and LR
13
We have that
Σ
Σ T
Σ
Σ
Emzo KEEK
n7u 2 no min Emin Σ y"
y.M -1
K Emiut M
Kiin Eminga
Yo Kmin Emin
7-1
72
5
and
2m
Σ
M
M
km
Ni
2
max
E Emax
7 Σ
M
2m
b
bo
8m
m=0
m S
m
K4
bo
nl
2
nl
2
1
<
K Kmax Emax
K Kmax Emax
bo
bo
3
m=0
where 7 = < 1. Hence,
Br
S
Σ1=0 11
no K Kmin Emii o
and
T-1
Kmax Emax 8
VT
b
Kmin Eminn by A)
1==
Th
1=
Proof of Theorem
3 Theorem
3.4 follows immediately from Theorems
3.2 and
3.3
28

---

Published in Transactions on Machine Learning Research (02/2025)
A.4 Proofs of Convergence Results under Convexity
Using Lemma
2.1 have the following lemma.
Lemma A.1 Suppose that Assumption 2. holds and f is convex and consider the sequence (0,) generated
by Algorithm with E [Tmin Thmax] C [0, 2t salisfying Et-1 * O, where = 1, Eie(n) Li, _ =
1 Eiein] f
Rd is a global minimizer of f, and f == f(0)). Then, for all T E N,
n
min B[f(0r)
-f
LE
00:2
1|
100 00
Mmax Tm (f -f)
f)
+ 0² (1
1+ Limax
T-1
Dr
2
2 Tammax
T
2 - Lammax
0m Te
r= Te
Br
V/
where E denoles the lotal expectation, desined by = Rgg Bei ... .....
Proof: Since |10 - -0211²= =|||== - -2 02) + ||0 holds for all 0,, O2 E R2, we have that, for all t E N,
10+1 - 0+ I1(0, 0r) 1/t VIB. (0.)11
100 0- 2n (0 0", V', + vi Vn,
Taking expectation conditioned on ε Ê on both sides of the above equation, Proposition A.1 and
19h ensure that, for all E N
Ee.
10++1 0-112(
= =|00, -01113 - -2n, (0, 0-, Vfn. f... [--1 + n/ E [I. (0)))
S 11, - 1- - 2m, (r - -0,, ((),)) + nh _²
( + +11[5(00)11)
Since convexity of f implics that, for all 0,, 02 Rdd, f(0)) 2 f(0)) + (0) 02 vf(02)), we have that
Eg, [10041 0-113|6--1 s 110, 0+112 (f.)) fr) ti (or [V
Taking the total expectation on both sides of the above inequality gives that, for all t N,
E [1 1-] < E 0, 001 - - ff] ni (o- + + +
Let T E N. Summing the above inequality from
0 gives that
T-1
E f(()) f4 10
0-
111
Maax Σ E [V)())))
b
1=0
t=0
29

---

Published in Transactions on Machine Learning Research (02/2025)
where 7/ I Mmax is used. Since Lemma 2.1 (see 20
guarantees that
v 2(f(0o) f")
L
T-1
1/1
EE
[V
+
LMmax
2 Limmax
bi
1=0
have that
Σ E (f(0,) -f |10 1
Mmax (f(0o) fr)
0² 1+ + 2
Lmmax
Σ
T-1 2
171
Limaa
2 - Lmmax
bc
Therefore, from Ei=0 7t * 0, we have
min 1e(0:T-1
[[ sn]
|00 100--0 0r0l 12 Tmax (f(0o) - -
+ σ² (
LMjaxx
T-1 n2,,
1
2 - Limmax
D m
2
Lmmaxx
21=0 171
which completes the proof.
The right column in Table 2 can be obtained by using Lemma
A.1 and Theorems 3.1 3.4
A.5 Training ResNet- 34 on ImageNet: Evaluating Case (iv)
Leantrng Eate and Smeedder
Teaten-3 en mageter
100
(a) Learning rate H/ and batch size versus epochs
(b) Full gradient
V (0.))l epochs
Boshil rageter
130
Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 7: (a) Warm-up decaying learning rates (Nuax 1.0) and increasing batch sizes based on 8 2, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train 34 on ImageNet dataset.
30

---

Published in Transactions on Machine Learning Research (02/2025)
A.6
Training ResNet- 18 on CIFAR10 and CIFAR100 using Doubling, Tripling, and Quadrupling Batch Sizes
Ieavnay wreck
Perkee 1ihre 0993111
533
(a) Learning rate t/ and batch size versus epochs Incestttooos
(b) Full gradient norm f(.))
I
versus epochs
18-
(c) Empirical loss f(..) versus epochs
(d) Test accuracy score versus epochs
Figure 8: (a) Increasing learning rates and doubling, tripling, and quadrupling batch sizes ((8,7) (2, 1.4), (3, 1.7), (4, 1.9) satisfying v8 > 7) every 100 epochs, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in lesting for SGD to train R8 on CIFAR10 dataset.
Legrihg hata and bast tbe Strcklr
Fertent en DEOZZE
4.15
110
(a) Learning rate H/e and batch size versus epochs CRA0C0
(b) Full gradient
[((e)))
epochs
200
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 9: (a) Increasing learning rates and doubling, tripling, and quadrupling batch sizes ((5,7) (2, 1.4), (3, 1.7), (4, 1.9) satisfying v 7) every 100 epochs, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train ResNet-18 on CIFAR100 dataset.
31

---

Published in Transactions on Machine Learning Research (02/2025)
A.7 Comparisons of Case (ii) with Cases (iii) and (iv) for Training ResNet-18 CIFAR100 using Increasing Batch Size based on = 3
fartoct es Doaas
(a) Learning rate t/e and batch size versus epochs
(b) Full gradient norm [(ez) versus epochs
(c) Empirical loss f(O.) versus epochs
(d) Test accuracy score versus epochs
Figure 10: (a) Increasing or warm-up docaying learning rates (Mmin = 0.01) and increasing batch sizes basod on 6 = 3, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing
for SGD to train ResNet-18 on CIFAR100 dataset.
Figures compare Case (ii) with Cases (iii) and (iv) for training ResNet-18 on CIFAR100 using increasing batch size based on 8 2.
A.8 Comparisons of With vs. Without Replacement for Training ResNet- 18 on CIFAR100
Marri by
hew
(a) Learning rate zp and batch size versus epochs Retee thee Cean
(b) Full gradient norm (0=))
epochi
Rodble en CONTER
11a
(c) Empirical loss f(0)) versus epochs
(d) Test accuracy score versus epochs
Figure 11: (a) Increasing warm-up decaying learning rates (7mna 1.0) and increasing batch sizes based å = 2, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train ResNet-18 on CIFAR100 datasct.
32

---

Published in Transactions on Machine Learning Research (02/2025)
A.9 Training
CIFAR100
Lranky has Sreek
0.44
442
640
(a) Learning rate T/ and batch size versus epochs
(b) Full gradient norm | f(0))l versus epochs
2-200
(c) Empirical loss f())) versus epochs
(d) Test accuracy score versus epochs
Figure 12: (a) Decaying learning rates (constant, diminishing, cosine, linear, and polynomial) and constant batch size, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train -ide-ReesNet-2S100 on CIFAR100 dataset.
pall
Caree
(a) Learning rate 7/ and batch size by versus epochs Wilskedte
(b) Full gradient norm
| (0=))l versus epochs
wdd-aamee 2010
714
Sanda
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 13: (a) Decaying learning rates and increasing batch size every 30 epochs, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train Wide- Mide-ResNeet28-111 10 on CIFAR100 dataset.
33

---

Published in Transactions on Machine Learning Research (02/2025)
100--100)
Cants
(a) Learning rate T/e and batch size by versus epochs Wit-kateda00
(b) Full gradient norm
V f0=)) versus epochs
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 14: (a) Increasing learning rates (Tmax 0.2, 0.5, 1.0) and increasing batch size every 30 epochs, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train Wide-ResNet-28--11 on CIFAR100 dataset.
Learihg has and bact dbs Shhedlrr
de 94-0am-920000 GRAIEE
cade
(a) Learning rate Ne and batch size versus epochs
(b) Full gradient norm |/ (0.)) versus epochs
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 15: (a) Warm-up learning rates and increasing batch size every 30 epochs, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in lesting for SGD to train Wide- ResNee-2811 C1FAR100 dataset.
34

---

Published in Transactions on Machine Learning Research (02/2025)
Cants
(a) Learning rate Tee and batch size by versus epochs Witokatedaaa
(b) Full gradient norm
V f(=)) versus epochs
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 16: (a) Increasing learning rales and increasing batch sizes based on 5 = 2, 4, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train Wide-ResNed 28-10 on CIFAR100 dataset.
A.10 Training ResNet-18 on Tiny ImageNet
Leavasy Kitrorn Sheck
k14
642
(a) Learning rate N) and batch size versus epochs
(b) Full gradient norm
/ f(ee)l versus epochs
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 17: (a) Decaying learning rates (constant, diminishing, cosine, linear, and polynomial) and constant
batch size, (b) full gradient norm empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train ResNet-18 on Tiny ImageNet dataset.
35

---

Published in Transactions on Machine Learning Research (02/2025)
Maar my
648
6.4
(a) Learning rate te and batch size be epochs
(b) Full gradient
epochs
13.0
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 18: (a) Decaying learning rates and increasing batch size every 30 epochs, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train ResNet-18 18 on Tiny ImageNet dataset.
Mereelyy Luaring and
(a) Learning rate ne and batch size by epochs wac.antaeeee
(b) Full gradient
(0=))l versus epochs
Empirical loss f(0.) epochs
(d) Test accuracy score versus epochs
Figure 19: (a) Increasing learning rates (Muax 0.2, 0.5, 0.5, and incrcasing batch size every 30 epochs, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train Res 18 on Tiny ImageNet dataset.
36

---

Published in Transactions on Machine Learning Research (02/2025)
Maar my
Beac 241
Learning rate We and batch size be epochs
(b) Full gradient
(0=))l
epochs
435
(c) Empirical loss f(0.) versus epochs
(d) Test accuracy score versus epochs
Figure 20: (a) Warm-up learning rates and increasing batch size every 30 epochs, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train ResNet-18 on Tiny ImageNet dataset.
Luaring 2r.r
110
111
(a) Learning rate ne and batch size by versus epochs waw.hnaaeaa
(b) Full gradient
|/ (0=))l versus epochs
114
18
(c) Empirical loss f(0)) epochs
(d) Test accuracy score versus epochs
Figure 21: (a) Increasing learning rates and increasing batch sizes based 5 = 2, 3,4, 4, (b) full gradient norm of empirical loss, (c) empirical loss value, and (d) accuracy score in testing for SGD to train ResNet-18 on Tiny ImageNet dataset.
37


Reviews:
[{"review_id": "FByRB9PAKB", "reviewer": "Reviewer_YADH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: \n1. Authors provide detailed and complex theoretical math manipulations for the convergence bound of the different learning schedulers,\nbringing more theoretical insights for the choice of learning schedulers.\n2. The complete empirical results are provided and analyzed.\n\nCons:\n1. Assumptions need to be discussed more. I think the assumption is not weak in reality (or for the learning cases in the empirical cases).\n2. The contribution in theoretical techniques should be re-evaluated. I can not clearly identify the novelty theoretically.\n3. More comparisons in both theoretical and empirical should be made for better positioning the work in the optimization community,", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The manuscript presents an analysis of the scheduler within mini-batch SGD, including both theoretical and empirical aspects. The authors propose a clear convergence bound for mini-batch SGD under the assumptions of Lipschitz continuity and bounded functions, as well as bounded variance. The theoretical results might be sound with super-martingale-like manipulations and the detailed empirical results show great efforts of authors.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. More discussion about the assumption should be made (like Lipschitz, lower bounded f and variance bounded...) How are they employed in others' work and how is it closed to the reality/empirical cases.\n2. More comparisons should be made with other work theoretically. There should be lots of work providing convergence bounds for miniSGD and please state how to differentiate you and them\n3. Maybe more proof sketch needs to be added to reflect some insights and technical contributions.\n4. If possible, more numerical studies can be made with large datasets and networks to improve the value of the work in the training process   today.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oLBqpTpSz8", "reviewer": "Reviewer_Z3gv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n-\tThe paper provided the convergence rate of four different schemes in mini-batch SGD.\n\nWeaknesses:\n\n-\tIt is hard to follow the main results of the paper. In the table on page 2, for increasing batch-size and decreasing learning rate (case (ii)), the convergence rate is written as $O(1/\\sqrt{T})$, $O(1/\\sqrt{M})$. Do the authors mean $\\max(O(1/\\sqrt{T}), O(1/\\sqrt{M}))$? The other issue is that the convergence rate for case (ii) is $ O(1/\\sqrt{T})$ (except for diminishing LR). For the case (iii), the convergence rate is $O(1/\\gamma^{M/2})$ where $1\\leq \\gamma^2 \\leq 2$ and $M$ is the number of times that the batch-size increases. In the table, it is mentioned the $O(1/\\gamma^{M/2})$ converges to $O(1/\\sqrt{T})$ (which is not clear to me why). Even if it is the case, there is no improvement over case (ii) as there, we also have the convergence rate of $ O(1/\\sqrt{T})$ (except for diminishing LR).\n-\tI think one of the main contributions of the current work is to validate the theoretical findings in training deep neural networks. However, as also mentioned by the authors, the experiments are very limited on a relatively simple dataset (CIFAR100). Therefore, it is not clear whether these trends can be observed in more complex tasks.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors analyzed the convergence rate of mini-batch SGD to reach an approximate first-order stationary point. In particular, they considered four cases: (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. They first provided Lemma 2.1 which shows how the minimum norm of gradient along the trajectory of optimization can be bounded by the terms that depend on the batch size $b_t$ and the learning rate $\\eta_t$. Based on this lemma, the rates of convergence for the four cases mentioned above are derived. The theoretical findings are evaluated in the experiment of training ResNet-18 on the CIFAR100 dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "-\tPlease revise the table on page 2 and compare cases (ii) and (iii) in more detail.\n-\tIt would be nice to provide intuition why increasing batch-size and learning rate can provide the convergence rate of $O(1/\\sqrt{T})$. Moreover, is it sensitive how we set the initial learning rate (as the learning rate is increasing in time)? Finally, is there any work in training deep neural networks using this scheme?\n-\tTo my understanding, Lemma 2.1 can be proved fairly straightforward. If not, it is good to mention what are the key challenges in proving Lemma 2.1. The main theorems are just based on applying this lemma to the four cases.\n-\tIt is good to do experiments on complex tasks (such as training on ImageNet dataset) to see whether these trends hold there too.\n-\tI think it is good to pick the best method for each case and then put them in the same plot.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YRHoISBKi0", "reviewer": "Reviewer_onDZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Broad Applicability Without Convexity Assumption:\n\nThe paper provides theoretical guarantees and convergence analysis without relying on the often unrealistic assumption of convexity. This makes the results applicable to a broader range of real-world deep learning problems, which frequently involve nonconvex loss functions.\n\n2. Thorough Theoretical Analysis of Scheduling Strategies:\n\nThe theoretical exploration of four distinct scheduling strategies for batch size and learning rates is comprehensive, offering rigorous mathematical insights supported by explicit inequalities. This analysis bridges theoretical advancements with practical utility.\n\n3. Effective Presentation of Results:\n\nThe use of clear figures, tables, and theoretical bounds effectively conveys the impact of the different scheduling strategies, aiding understanding for both theoretical and applied audiences.\n\nWeaknesses:\n\n1. Independence Assumption in Assumption A3:\n\nThe independence assumption on $\\xi_1, \\dots, \\xi_b$ could be replaced with a more practical setting where $\\xi_1, \\dots, \\xi_b$ are drawn identically but with replacement. Under this modification, the conditional variance result in Proposition A.1 would require slight adjustments. Specifically:\n\na) When $b = n$, the conditional variance becomes exactly zero.\n\nb) When $b \\ll n$, the i.i.d. assumption remains a good approximation to the case of sampling with replacement.\n\nClarifying these distinctions and addressing the practical implications would strengthen the paper.\n\n2. Comparison of Convergence Rates With and Without Convexity:\n\nWhile the paper avoids assuming convexity, it would benefit from a direct comparison of the convergence rates under convex and nonconvex assumptions. Highlighting the differences would provide valuable insights into the trade-offs and implications of removing convexity assumptions.\n\n3. Proofs of Proposition A.1 and Lemma 2.1 Rely on Established Results:\n\nThe proofs appear to depend heavily on standard results from the literature on SGD analysis. Including more detailed citations for foundational work would enhance the paper's scholarly rigor and appropriately acknowledge prior contributions. Additionally, clearly specifying the original contributions in the analysis would help distinguish this work from existing approaches.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper explores the theoretical and empirical impacts of different scheduling strategies for mini-batch stochastic gradient descent (SGD), focusing on variations in batch size and learning rate. Key contributions include:\n\n1. Theoretical Analysis: \n\nThe paper provides a detailed examination of four scheduling strategies for batch size and learning rates, backed by rigorous theoretical analyses. For each strategy, the authors derive explicit inequalities that bound the gradient norm and explain the conditions under which convergence can be accelerated.\n\n2. Practical Insights: \n\nDemonstrates that increasing both batch size and learning rates can accelerate mini-batch SGD.\n\nHighlights how warm-up in strategy (iv) ensure convergence with faster empirical loss reduction, combining the benefits of early acceleration and stable convergence.\n\n3. Empirical Validation:\n\nExperiments using ResNet-18 on the CIFAR-100 dataset confirm the theoretical findings.\n\nVisualizations effectively illustrate the advantages of combining batch size and learning rate schedules, showing faster convergence and improved test accuracy compared to standard methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weaknesses and address the raised concerns.", "broader_impact_concerns": "This is a theoretical work. There is no such concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors have analyzed convergence of mini-batch SGD under four batch-size and step-size schedulers. They consider empirical risk minimization to optimize a smooth function with unbiased stochastic gradients considering mini batches where indices are drawn i.i.d., i.e., sampling with replacement. 

Lemma 2.1 is the key result where an upper bound on the expected full gradient norm (the best iterate) is obtained for a general batch-size and step-size scheduler, and the following rates for four special cases are obtained using this lemma. 

The reviewers had major concerns regarding theoretical contributions and comparison with current results. The reviewers’ concerns have been properly addressed after discussing with the authors, and all reviewers are positive with the revised version.The reviewers highlighted detailed empirical studies and providing theoretical insights for the choice hyperparameters' schedulers as strengths of this paper. I’d share the same view as the reviewers that the revised manuscript can be accepted after addressing these comments: 

Schedule i) This is an upper bound and you show that the upper bound is larger than 0 no matter how large $T$ becomes. It does not necessarily imply that “mini-batch SGD does not converge to a stationary point.” BTW, even in other cases where the upper bound goes to zero as $T$ increases, you essentially show error bounds for the best iterate within $T$ iterates, not the last iterate. For the last iterate, none of the key results in Page 2 guarantee that the mini-batch SGD always converges to the stationary point. 

When describing the second row of the table in Page 2  (Case (ii)), please clarify what $M$ is. Also it is not clear what you mean by $O(\frac{1}{\sqrt{T}}),\quad O(\frac{1}{\sqrt{M}})$
Decision: Accept (poster)