Relationship between Batch Size and Number of Steps Needed for Nonconvex Optimization of Stochastic Gradient Descent using Armijo-Line-Search Learning Rate
Authors: Yuki Tsukada
Hideaki Iiduka
Venue: Accepted by TMLR ()

Abstract: While stochastic gradient descent (SGD) can use various learning rates, such as constant or diminishing rates, previous numerical results showed that SGD performs better than other deep-learning optimizers when it uses learning rates given by line search methods. In this paper, we perform a convergence analysis on SGD with a learning rate given by an Armijo line search for nonconvex optimization indicating that the upper bound of the expectation of the squared norm of the full gradient becomes small when the number of steps and the batch size are large. Next, we show that, for SGD with the Armijo-line-search learning rate, the number of steps needed for nonconvex optimization is a monotone decreasing convex function of the batch size; that is, the number of steps needed for nonconvex optimization decreases as the batch size increases. Furthermore, we show that the stochastic first-order oracle (SFO) complexity, which is the stochastic gradient computation cost, is a convex function of the batch size; that is, there exists a critical batch size that minimizes the SFO complexity. Finally, we provide numerical results that support our theoretical results.

Published in Transactions on Machine Learning Research (03/2025)
Relationship between Batch Size and Number of Steps Needed for Nonconvex Optimization of Stochastic Gradient Descent using Armijo-Line Seacee Learning Rate
Yuki Tsukada
yuki. 11kki.11190iiduka....
Deportment of Computer Science
Meifi University
Hideaki liduka
iduka weltaa/sssmmmmii..m.mm ac.jp
Department of Computer Science
Meiji Universily
Reviewed on OpenReview: https: openreview. net/ forum? id= pg26nOm3WF
Abstract
While stochastic gradient descent (SGD) can use various learning rates, such as constant or diminishing rates, previous numerical results showed that SGD performs better than other deep-learning optimizers when uses learning rates given by line search methods. In this paper, we perform a convergence analysis on SGD with learning rate given by an Armijo line search for nonconvex optimization indicating that the upper bound of the expectation of the squared norm of the full gradient becomes small when the number of steps and the batch size are large. Next, show that, for SGD with the Armijo- lene--nanrcle learning rate, the number of steps needed for nonconvex optimization is a monotone decreasing convex function of the batch size; that is, the number of steps needed for nonconvex optimization decreases as the batch size increases. Furthermore, we show that the stochastic first-order oracle (SFO) complexity, which the stochastic gradient computation cost, is a convex function of the batch size; that is, there exists a critical batch size that minimizes the SFO complexity. Finally, we provide numerical results that support theoretical results.
1 Introduction
1.1 Background
Nonconvex optimization is useful for training deep neural networks, since the loss functions called the ex- pected risk and empirical risk are nonconvex and they need only be minimized in order to find the model parameters. Deep-learning optimizers have been presented for minimizing the loss functions. The simplest one is stochastic gradient descent (SGD) (Robbins & Monro, 1951; Zinkevich, 2003; Nemirovski et al., 2009; Ghadimi & Lan, 2012; 2013) and there are numerous thcoretical analyses on using SGD for nonconvex optimization (Jain et al., 2018; Vaswani al., 2019; Fehrman et al., 2020; Chen et al., 2020; Scaman & Mal- herbe, 2020; Loizou et al., 2021; Umeda & Tiduka, 2025). Variants of SGD have also been presented, such as momentum methods (Polyak, 1964; Nesterov, 1983) and adaptive methods including Adaptive Gradient (AdaGrad) (Duchi et al, 2011), Root Mean Square Propagation (RMSProp) (Tieleman & Hinton, 2012), Adaptíve Moment Estimation (Adam) (Kingma & Ba, 2015), Adaptive Mean Square Gradient (AMSGrad) (Reddi et al., 2018), and Adam with decoupled weight decay (AdamW) (Loshchilov & Hutter, 2019). SGD and its variants are useful for training not only deep neural networks but also generative adversarial networks (Heusel et al., 2017; Naganuma & liduka, 2023; Sato liduka, 2023).
The performance of deep-learning optimizers for nonconvex optimization depends on the batch size. The previous numerical results in (Shallue et al., 2019) and (Zhang et al., 2019) have shown that the number of

---

Published in Transactions on Machine Learning Research (03/2025)
steps K needed to train a deep neural network halves for each doubling of the batch size b and that there is a region of diminishing returns beyond the critical batch size b*. This fact can be expressed as follows: there is a positive number C' such that N := Kb ~ C' for b I b and N := Kb 2 C' for b 2 b*. The deep neural network model uses gradients of the loss functions per step. Hence, when K is the number of stops required to train a deep neural network, the model has a stochastic gradient computation cost of Kb. We will define the stochastic first-order oracle (SFO) complerity (Tiduka, 2022; Sato & Tiduka, 2023) of a deep-learning optimizer to be N Kb. From the previous numerical results in (Shallue 2019), the SFO complexity is minimized at critical batch size b* and there are diminishing returns once the batch size exceeds by. Therefore, it is desirable to use the critical batch size when minimizing the SFO complexity of the deep-learning optimizer.
al., 2019) and (Zhang et al.,
Not only the batch size but also the learning rate affects the performance of deep-learning optimizers for non- convex optimization. A performance measure of a deep-learning optimizer generating a sequence (0x) (ex)een is the expectation of the squared norm of the gradient of a nonconvex loss function f. denoted by f( [(²] If this performance measure becomes small when the number of steps k is large, the deep-learning optimizer approximates local minimizer of f. For example, let consider the problem of minimizing a smooth fune- tion f (sce Section 2.1 for the definition of smoothness). Here, SGD uses constant lcarning rate a = O(2) satisfying minke[K] [k] E f[ = O + g). where L is the Lipschitz constant of Vf, b is the batch (see also Table 1). Moreover, SGD using a learning rate satisfying the Armijo
size, and [K] == ........, condition was presented in (Vaswani et al., 2019). The Armijo line search (Nocedal & Wright, 2006, Chapter 3.1) is standard method for finding an appropriate learning rate ag giving a sufficient decrease in f, i.e., 1(0x+1) < f(0x) (see Section 2.3.1 for the definition of the Armijo condition).
1.2 Motivation
The numerical results in (Vaswani et al., 2019) indicated that using the Ammio-line-search lcarning rate is superior to using a constant learning rate when using SGD to train deep neural networks in the sense of minimizing the training loss and improving test accuracy. Motivated by the useful numerical results in (Vaswani et al., 2019), we decided to perform convergence analyses on SGD with the Armijo-line-search learning rate for nonconvex optimization in deep neural networks.
Theorem 3 in (Vaswani et al., 2019) is a convergence analysis of SGD with the Armijo- learning rate for nonconvex optimization under a strong growth condition that implies the interpolation property. Here, let f: Rd + R be an empirical risk defined by f(0) == 1 Evema fi(0), where n is the number of training data and f:: Rd R is a loss function corresponding to the i-th training data 2,. We say that has the interpolation property if (f) = 0 implies (() 0 (i E [m]). The interpolation property holds for optimization of linear model with the squared hinge loss for binary classification on linearly separable data (Vaswani et al., 2019, Section 2). However, the strong growth condition would be unrealistic for deep neural networks, since their loss functions are nonconvex. The motivation behind this work is thus to show that SGD with the Armijo-line-serchh learning rate can solve nonconvex optimization problems in deep neural networks.
As indicated in the second paragraph in Section 1.1, the batch size has a significant effect on the performance of SGD. Hence, in accordance with the first motivation stated above, we decided to investigate appropriate batch sizes for SGD with the Armijo-iine-search learning rate. In particular, we are interested in verifying whether a critical batch size b* minimizing the SFO complexity N exists for training deep neural networks with SGD using the Armijo condition in theory and in practice. This is because the previous studies in (Shallue et al., 2019; Zhang et al., 2019; Tiduka, 2022; Sato & Tiduka, 2023) showed the existence of critical batch sizes for training deep neural networks or generative adversarial networks with optimizers with constant diminishing learning rates and without Armijo-line-search learning rates.
2

---

Published in Transactions on Machine Learning Research (03/2025)
1.3 Contribution
1.3.1
Convergence analysis of SGD with Armijo-lnne-serccl learning rates
The first contribution of this paper is to present & convergence analysis of SGD with Armijo-line-search learning rates for general nonconvex optimization (Theorem 3.1); in particular, it is shown that SGD with this rate og satisfies that, for all K 2 1,
G
C2
min E [1 S 2(f(O)) - fa) 1 ke ke(o:K
L
1
(1)
(Ln 1)a
K
(Ln 1)a 6'
B(Db.K)
V(o2,b)
where the parameters are defined in Table 1 (see also Theorem 3.1). The inequality (1) indicates that the upper bound of the performance measure minke (0x)) that consists of bias term B(Oo, K) and variance term V( b) becomes small when the number of steps K is large and the batch size b is large. Therefore, it is desirable to set K large and b large so that Algorithm 1 will approximate local minimizer of f.
The essential lemma to proving (1) is the guarantce of the existence of lower bound on the learning rates satisfying the Armijo condition (Temma 2.1). Although, general, learning rates satisfying the Armijo condition do not have any lower bound (Lemma 2i)( the corresponding Icarning rates computed by a backtracking line search (Algorithm 1) have a lower bound (Lemına 2i)( In addition, the descent lemma (i..., f S f(x)= + (Vf(x). y z) + 1 x=12 (xx y E R))) holds from the smoothness condition on f. Thus, we can prove (1) by using the existence of lower bound on the learning rates satisfying the Armijo condition and the descent lemma (see Appendix A.2 for details of the proof of Theorem 3.1).
Table 1: Relationship between batch size b and number of steps K to achieve an e approximation defined by minkgjo:x-1 (( S C + C = ²² for SGD with a constant learning rate a E (0, 2 and for L.
SGD with Armijo-lino-scarch learning rate ag E [a, a) (I0 K - 1| = f0. 1.... K 1), f = >iEnn) fi is bounded below by f., L, is the Lipschitz constant of Vf;, L, == 4 Zie(n] L; ā ā= 2601-) ô E ( 1),
L.
e (0,1 1 );,, and o² is the upper bound of the variance of the stochastic gradient)
Learning Rate
Upper Bound C1 C2 K
+
b
Steps K
SFO N
Critical Batch b*
2(f(0)) fa)
2 Ln
C
G.b
C₁
2C₂ 2
Constant a E
0,
(2 - L,a
K=
N =
===
2 C2
2b C2
C2
2 an
2(f(0n) - fa)
1 2 [
C
b
2
20₂ 2
Armijo ā E
á (In 1)ā
K 2 - C2
b'
Ln Ln
Lna00
2b - C2
C2 ā (Ln 1)a
1.3.2 Steps needed for c-approximation of SGD with Armijo line-search- rates
The previous results in (Shallue et al., 2019; Zhang et al., 2019; Tiduka, 2022; Sato & Tiduka, 2023) indicated that, for optimizers, the number of steps needed to train a deep neural network or generative adversarial networks decreases as the batch size increases. The second contribution of this paper to show that, for SGD with the Armijo-line-saarch learning rate, the number of steps K needed for nonconvex optimization decreases as the batch size increases. Let us consider the case in which the right-hand side of (1) is equal to e, where > 0 is the precision. Then, K is a rational function defined for batch size b by
C₁b
K K(6) 2b C2
(2)
3

---

Published in Transactions on Machine Learning Research (03/2025)
where C1 and C2 are the positive constants defined in (1) (see also Table 1). We can easily show that K defined above is a monotone decreasing and convex function with respect to b (Theorem 3.2). Accordingly, the number of steps needed for nonconvex optimization decreases as the batch size increases.
1.3.3 Critical batch size minimizing SFO complexity of SGD with Armijo-inee-sarchh learning rates
Using K defined by (2) above, we can further define the SFO complexity N of SGD with Armijo-inne-earch learning rates (see also Table 1):
Ci
N Kb (bbb e²b C2
(3)
We can easily show that N is convex with respect to b and that global minimizer
2C2 6" 2 fa- (L, - 1)afe²
20,
(4)
exists for it (Theorem 3.3). Accordingly, there is critical batch size b* at which N is minimized.
Here, we compare the number of steps Kc and the SFO complexity Ne for SGD using constant learning rate with KA and NA for SGD using -eneechline-search learning rate ag (E la, a.). Let C1 (resp. C2.c) be C1 (resp. C2) in Table for SGD using a constant learning rale and let CI,A (resp. C2,1) be C1 (resp. C2) in Table for SGD using the Armijo-lineseaare linc-search learning rate. We have that
CI,A Ci,c iff (2 Lna)a < (Li - 1)a, aoz
0²02 C2.A C C2 iff ā - (L,ā
(5)
2 La Ln
where oe (resp. x) denotes the upper bound of the variance of the stochastic gradient for SGD using constant learning rate (resp. the Armijo-line-search learning rate). If (5) holds, then SGD using the Armijo-line-search learning rate converges faster than SGD using a constant learning rate in the sense that Crobb 26 22_C C2.A NA Ne 2b-C2.c' It would be difficult to check exactly that (5) holds before implementing SGD, since (5) involves unknown parameters, such L, Eien Li: of and oA However, it can be expected that (5) holds, since it is known empirically (Vaswani et al., 2019, Figure 5) that the relationship between the Armijo-lino-saal learning rate ag and constant learning rate a is a ag a.
Clob 2h Cb-C2.4 KA Ke C2.c and Ci,bb²
Cj,bb
1.3.4 Numerical results supporting our theoretical results
The numerical results in (Vaswani al., 2019) showed that SGD with the Armijo-line-search learning rate performs better than other optimizers in training deep neural networks (DNNs). Hence, we seek to determine whether the numerical results match our theoretical results (Sections 1.3.1, 1.3.2, and 1.3.3). We trained residual networks (ResNets) on the CIFAR-10 and MNIST datasets. We numerically found that increasing the batch size decreases the number of steps K needed to train DNN and that there are critical batch sizes minimizing the SFO complexities. To determine whether SGD using the Armijo-line-sarrch learning rate performs better than SGD using a constant learning rate (see the discussion in condition (5)), we numerically compared SGD using the Armijo-lino-search lcarning rate with not only SGD using a constant learning rate but also variants of SGD, such the momentum method, Adamn, AdamW, and RMSProp. We found that SGD using the Armijo-line-seachh learning rate and the critical batch size performs better than other optimizers in the sense of minimizing the number of steps and the SFO complexities needed to train DNN (Section 4).
2 Mathematical Preliminaries
2.1 Definitions
Let N be the set of nonnegative integers, [n] := (1,2...., for n 2 1, and [0 n] == {0, 1,.......0 n) for n 2 Let Rdd be d-dimensional Fuclidean space with inner product (:-)) inducing the norm -|
4

---

Published in Transactions on Machine Learning Research (03/2025)
Let f: R R be continuously differentiable. We denote the gradient of by Vf: R - Rd. Let L > 0. I: Rd + R is said to be T--smooth if Vʃ: IRd - Rd is T--Lipschitz continuous, i.e., for all a. y E IR [Vf(()) ffl) < L| yll. When f: R2 + R is L smooth, the following inequality, called the descent lemma (Beck, 2017, Lemma 5.7), holds: for all æ, y E R f() I f(x)= + (Vf(z), y σ) + 2 2 - x|? Let f: Rd > is said to be bounded below by fa if, for all x RR. [(x) 2 S.
Jx E
2.2 Assumptions and problem
Given a parameter 0 E IRd and a data point z in data. domain Z, a machine learning model provides a prediction whose quality can be measured by a differentiable nonconvex loss function f(0; z). We aim to minimize the empirical average loss defined for all 0 R by f() Eienn f(0; 2,) Eiein] f())), where S = =21 22, 2n) denotes the training set and f:(.) = f(: 25) denotes the loss function corresponding to the i-th training data 2;.
This paper considers the following smooth nonconvex optimization problem. Problem 2.1 Suppose that f:: Wd R [n]) is Li-smooth and bounded below by fi,x Then,
minimize ʃ(0) = n1
Σ [(()) subject to 0 E IRd iE|n]
We assume the existence of SFO such that, for a given E R returns a stochastic gradient Gg( of the function f, where a random variable & supported on a finite/an infinite set independently of 0. We make the following standard assumptions.
Assumption 2.1
(A1) Let (Ox)keN C Rd be the sequence generated by SGD. For each iteration k,
Egg, (G.. (0x) V
(6)
where Eo, .t.... are independent samples, the rundom variable &k is independent of (0:) o and Eeg [-] stands for the expectation with respect Ek. There erists nonnegotive constont o² such that
Be, [[| (0x) V[(02))
(A2) For each ileration k, SGD samples batch By of size b independently of k and eslimates the full gradient f
VBB. (0k)
Σ GE.. (0s)
Σ v Vee.
iE|b
kE(60
where Ex,s is a rondom variable generated by the i-th sampling in the k-th iteration.
From the independence of to. Ea......, we can define the total expectation E by E = Eg Ee, ... EE
2.3
Stochastic gradient descent using Armijoline-searce learning rate
2.3.1
Armijo condition
Suppose that f: IRd - is continuously differentiable. We would like to find a stationary point 0* e Rd
such that f(0)) 0 by using an iterative method defined by
0 0₂ + azdi:
(8)
where ay 0 is the step size (called a learning rate in the machine learning field) and dæ E Rd is the search direction. Various methods be used depending the search direction dg- For example, the method
5

---

Published in Transactions on Machine Learning Research (03/2025)
d=:== (8) with d2 (Ox))) is gradient descent, while the method (8) with d, := -Vf(Ox) + + where
9k 2 0, is the conjugate gradient method. If we define dæ (e.g., dz -Vf(O))), it is desirable to set og satisfying
f(0x oz min ʃ(O,. adg).
The step size of defined by (9) can be easily computed when ʃ is quadratic and convex. However, for a general nonconvex function f, it is difficult to compute the step size a in (9) exactly, Here, we can use the Armijo condition for finding an appropriate stop size ag:: Let c E (0,1). We would like to find 0% > 0 such that
f( + axd4)) S f(0)) + coO. (V (f()))), dz)
(10)
When d2 satisfics the descent property defined by (V/(0)), dx) < (e.g., gradient descent using d; := (Ox) has the property such that (Ox),,) da) - - f(0x+1) = (0,++adds) < f(0x). Accordingly, og satisfying the Armijo condition (10) is appropriate in the sense of minimizing f.
0), the Armijo condition ensures that
The existence of step sizes satisfying the Armijo condition (10) is guaranteed.
R be continuously differentiable. Let 0 E Rd and let. d2 (+ 0) have the descent property defined by (Vf(O)). d2) <.. Let c E (0, Then, there ewists 7 > 0 such that, for all ag (0, the Armijo condition (10) holds.
Proposition 2.1 (Nocedal & Wright, 2006, Lemma 3.1) Let f: Rd +R
2.3.2 Stochastic gradient descent under Armijo condition
The objective of this paper is to solve Problem 2.1 using mini-batch SGD under Assumption 2.1 defined by
Ou+1 O2 on.da O2 ur (O,,
= 02 b
Σ GE.. (0x), (E(D)
where b > 0 is the batch size and a > 0 is the learning rate. For each iteration k we can use ox, fB., and
V/n. Hence, the Armijo condition (Vaswani et al., 2019, (1)) written as
fak (02 ag V fix (6x)) S fix ca2 V (0&))
where ik is the training sample for iteration k, at the k-th iteration for SGD can be obtained by replacing I in (10) with Sn, and using d2 VSn, (Ox):
fB. (02 a% fB. (0x)) - fB. (0x) - cark fa,
(11)
The Armijo condition (11) ensures that fR. (0x+1) fB. (0s an VfB, (0x) < fB, (Ox); i.e. the Armijo condition (11) is appropriate in the sense of minimizing the estimated objective function fB, from the full objective function f. In fact, the numerical results in (Vaswani et al., 2019) indicate that SGD using the Armijo condition (11) is superior to using other deep-learning optimizers to train DNNs.
Algorithm 1 is the SGD algorithm using the Armijo condition (11).
The search direction of Algorithm d, SB, (0x) (# 0) which has the descent property defined by (V.B, (Ox), d -I/ (0x)]l² 0. Hence, from Proposition 2.1, there exists a learning rate on (0, 7M] satisfying the Armijo condition (11). Moreover, the proposition guarantees that the learning rate can be chosen to be sufficiently small, e.g., lim inf ag = 0.
The convergence analyses of Algorithm 1 use lower bound of ag E (0,7M) 7kl satisfying the Armijo condition (11). To guarantee the existence of such a lower bound, we use the backtracking method ((Nocedal & Wright, 2006, Algorithm 3.1) and (Vaswani et al., 2019, Algorithm 2)) described in Algorithm 1.
The following lemma guarantees the existence of lower bound on the learning rates computed by Algorithm 1. The proof is given in Appendix A.1.

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm Stochastic gradient descent using Armijo-line-search learning rate
Require:
G, E (0, 1) (hyperparameter). > 0 (batch size), Oo E R² (initial point), K 2 1 (steps), a (Initialization, see Algorithm 2), 0₂ E RR, fB. I2 +R
Ensure: 0k= E Rd
+ for 0, o..., -- do
while satisfying fB, (0, a (B. > (0x) (ox) do
t- da end while
Ok ta
Compute 0k+1 = 02 or V.. (0s)
end for
Lemma 2.1 Consider Algorithm under Assumption 2.1 for solving Problem 2.1. Let ag be learning
rate satisfying the Armijo condition (11) (whose existence is guaranteed by Proposition 2.1), let LB be the Lipschitz constant of fB.. Then, the following hold.
(i) [Counter-cxample of (Vaswani al., 2019, Lemma 1)] There erists Problem 2.1 such that og does not satisfy min 2(1-o) LB, [ S Ork, where ā is upper bound of ag.
(ii) [Lower bound on learning rate determined by backtracking line search method] If af can be computed by Algorithm 1, then there erists lower bound of or such that 0 26(1-c) S okk, where is the mazimum value of Li.
3 Analysis of SGD using
Search Learning Rate
3.1 Convergence analysis of Algorithm
Here, we present a convergence analysis of Algorithm 1. The proof of Theorem 3.1 is given in Appendix A.2. Theorem 3.1 (Upper bound of the squared norm of the full gradient) Consider the sequence (Ox)ee generated by Algoritium under Assumption 2.1 for solving Problem 2.1 and suppose that the learning rate ag a is computed by Algorithm 1. Then, for all 2 1, the following hold:
(i) In the case of 1 a
Ca
O() fa)
[L, 1)a + 0.
min E [IV](())
kElU:K-1|
(2 Ln
(2 Lnā)a
B(0o.K)
V(a2.b)
where L, = : Eiem Li, f= :
Eignn Si,, a== 26(1-c) E (0, 1), and E (0, t.
(ii) Suppose that the random variable &N. follows discrete uniform distribution DU+(n). In the of Tim << α < 2
min E [IV[/1111 < 2(f(Ou) fa)
Ln
kE (0(K--11
(I, 1) K
(Ton 1)T b'
B(Ou.K)
V(02,b)
where In = Eiemm) Li, fa = 1
n. EiEjjl Si,0, à = 25(1-e)
14 1+ 1+11+ [-c]
8 E (2 1), and
In
=
2
(0, 1

---

Published in Transactions on Machine Learning Research (03/2025)
Here, we sketch proof of Theorem 3.1 (A detailed proof of Theorem 3.1 is given in Appendix A.2).
Proof outline of Theorem 3.1(1):
1. We show that there cxists a lower bound a aş satisfying the Armijo condition such that < a ==
28(1- S og (Lemma 2ii()
i. The descent lemma leads to the finding that
5 - as |V 1 -(nnax 2
- 1/ + ak [Vf(0,) - VʃB, (0+)
ii.. Under (A1) and (A2), mini-batch stochastic gradient
V (0x) satisfies the cquation I o² (see (24)). Then, we have
Eg, [VB., [0x] vf(0,), Eg, fB. (0x) (f(
Bgg [B. (0x) || 0 s [| of (see (25)).
iv. Items i, and ii above, together with the conditions 0 << az S a and 1. 2 a, lead to
EE [f(0+ & f(0x) [V((0)]11 + (Inn 1)0
[(T,, [
1)e + at
2b
which implies that, for all E
(Inn - 1)2 BlI { (f)(O,) - f(0x+1)] ((Tna- - 1)a + a)o2
26
Summing the above inoquality from h: = 0 to h K ensures that
K-1
2(f(On) - f-)
{(In 1..t--1). 1)a + 0
[[V))) < {a (L, 1)aaKK
+
K
{a -LL, 1)a}6
Proof outline of Theorem 3ii(
i. Items i, ii, and in the proof outline of Theorem 3.1(i), together with the conditions <<a= S a S a and La < a, lead
Es, (f(0++1) f(O)) 2 Es, [as] [[Vf(0+)] + (I,, 1))a
L,aaa²
[Vf(+))] +
2
2b
ii. Assuming E ~ (U)(n) and applying Jensen's inequality, we have Es, [ou] 2 have
28(1-c) In
Hence, we
à (L, 1)a
[ <Ef()))) f.]+ L
2
where ā = 26(1-c) Am
and f= == Eienn) Ji..
14/1486(1-o) 2hm
iii Let 8 1), ce (0,1 1), and â
Since à 5 < â, we have (Ln
1)a 0, which implies
K-1
Σ E (1 < 2(f(On) - f.) + T,, k=o
K
{a (L, K {ā (L, 1)abb'

---

Published in Transactions on Machine Learning Research (03/2025)
Theorem 3.1 indicates that the upper bound of the minimum value of E|| (0))) consists of bias term B B(0, K) and variance term V(a².b) b). When the number of steps K is large and the batch size b is large, B(0o, K) and V 6) become small. Therefore, we need to set K large and b large so that Algorithm 1 will approximate a local minimizer of
Here, we compare Theorem 3.1 with the convergence analysis of SGD using a constant learning rate. SGD using a constant learning rate a E (0, Te
2 satisfies
min E [[V 2(f(0o) - f.) 1 L.ad² 1 k
(12)
L2-L,a)o K 2 - L,
(The proof of (12) is given in Appendix A.5). We need to set constant learning rate a E (0, A..) depending the Lipschitz constant Ln of Vf. However, since computing Ln is NP-hard (Virmaux & Scaman, 2018),
it is difficult to set E (0, I.. Meanwhile, from Theorem 3.1(ii), we need to set c, E (0, in Algorithm 1 such that á (2. 1) and e E (0, 33) (see Section for the performance of Algorithm using 0.9 and small parameters c).
We also compare Theorem 3.1 with Theorem 3 in (Vaswani al., 2019). Theorem in (Vaswani et al., 2019) indicates that, under strong growth condition with a constant, p (i.e., ((())1 s (())) (0 E R))) and the Armijo condition, SGD satisfies that
min E [[V)())))) S f(00) - =((0) kE
AK
where L is the maximum value of the Lipschitz constant L, of V C> 1- - pt. pl.n
2
A = (ब
2(1 2(1-0) p(@ 2(1-c) L,a"), and l is local minimizer of f. Thcorem 3.1 is convergence analysis L
of Algorithu 1 without assuming the strong growth condition. Moreover, Theorem 3.1 shows that using large batch size is appropriate for SGD using Armijo line search (Algorithm 1).
3.2 Steps needed for e-approximation
To investigate the relationship between the number of steps K needed for nonconvex optimization and the batch size b, we consider an c-approximation of Algorithm 1 defined as follows:
min E [[IT Sc.
(13)
kEjo:K-11
where > is the precision.
Theorem 3.1 leads to the following theorem indicating the relationship between b and the values of K that achieves an c-approximation. The proof of Thcorem 3.2 is given in Appendix A.3.
Theorem 3.2 (Steps needed for nonconvex optimization SGD using Armijo line search) Suppose that the assumptions in Theorem 3.1 hold. Define K; E + R for all b C by
Cib K(b)
(14)
22 - C2
where the positive constants C1 and C2 are defined as in Theorem 3.1. Then, the following hold:
(i) [Steps needed for nonconvex optimization] K defined by (14) achieves an c-approzimation (13).
(ii) [Properties of the steps] K defined by (14) monotone decreasing and conver for CJ.
Theorem 3.2 ensures that the number of steps K needed for SGD using Armijo line search to be an e- approximation small when the batch size is large. Therefore, it useful to set sufficiently large batch size in the sense of minimizing the steps needed for an c-approximation of SGD using Armijo line search. In other words, Theorem 3.2 implies that large batch size accelerates DNN training.
9

---

Published in Transactions on Machine Learning Research (03/2025)
3.3 Critical batch size minimizing SFO complexity
The following theorem shows the existence of critical batch size for SGD using Armijo line search. The proof of Theorem 3.3 is given in Appendix A.4.
Theorem 3.3 (Existence of critical batch size for SGD using Armijo line search) Suppose that the assumptions in Theorem 3.1 hold. Define SFO complexity N RR - R for the number of steps K, defined by (14), needed for an e e-approzimation (13) and for a batch size b 2 by
Cib²
N(b) = K(b)b bb-C2
(15)
where the positive constants C1 and C2 are defined as in Theorem (ii( Then, the following hold:
(i) (SFO complexity] N defined by (15) is conver for b> G
(ii) [Critical batch size] There exists a crilical batch size
2C2 a² b+
12 (2 - c)o (Ln a 1
(16)
2
2
such that b* minimizes the SFO complexity (15).
While large batch sizes require substantial computational resourcos, the critical batch size that minimizes SFO is small and practical, highlighting the importance of Theorem 3.3.
The previous results in (Shallue et al., 2019; Zhang et al., 2019; liduka, 2022) show that, for deep-learning optimizers, there are critical batch sizes at which the SFO complexities are minimized. We are interested in verifying whether a critical batch size exists for SGD using Armijo line scarch. Theorem 3.3( indicates that the critical batch size can be obtained from the hyperparameters. The next section numerically examines the relationship between the batch size b and the number of steps K needed for nonconvex optimization and the relationship between b and the SFO complexity N to check if there is critical batch size b* minimizing N.
3.4 Insights into and relationships among Theorems 3.1, 3.2, and 3.3
Theorem 3.1 provides a convergence analysis of SGD using Armijo line search showing that upper bound of the gradient norm is represented by Ci Ca and that the upper bound decreases the number of steps K and batch size increase. Therefore, it is desirable for SGD with Armijo line search to use large values of K and b. However, Theorem 3.1 does not directly indicate how large K and b should be for training DNNs. Here, we are interested in clarifying the relationship between the needed to train a DNN and batch size b.
R b
To consider the case in which SGD minimizes the full gradient norm of the loss function, we assume that SGD is an e-approximation defined by minkelo: V (0x)) < e:: that is, the upper bound of the gradient norm shown in Thcorem 3.1 is less than or equal to a certain small positive value e², i.c., C1 Then, we have K 2 Cyb .5 This implies that the number of steps needed to obtain an 6-approximation of Cih SGD with Armijo line search is K(b) = 26-C, depending on batch size
K + C2 < c².
On the basis of the above discussion, we aim to clarify the rclationship between the required K for training a DNN and batch size b. Theorem 3.2 elucidates the relationship between the number of steps K and batch size b. In particular, Theorem 3.2( indicates that the number of steps needed to train a DNN is monotonically decreasing and convex with respect to batch size. That is, the mumber of steps K needed for SGD using Armijo line search to be an e approximation is small when batch size is large. Therefore, it is useful to set sufficiently large batch size in the sense of minimizing the steps needed for an e approximation of SGD using Armijo line search. That is, a large batch size can accelerate DNN training.
One particularly intriguing question is how large the batch size should be. Here we consider SFO complexity to be the stochastic gradient computation cost. Since DNN model uses b gradients of the loss function,
10

---

Published in Transactions on Machine Learning Research (03/2025)
SFO complexity is (bb) when the number of steps needed to train the DNN is [(b), which can be obtained from Theorem 3.2. Theorem 3.3 establishes the relationship between batch size b and SFO complexity (bb)b- =bb-C, In particular, Theorem (.1( indicates that there is critical batch size that minimizes SFO complexity (b) (6)6, which is convex function of batch size b. Theorem 3.2 demonstrates that, as the batch size increases, the number of required steps decreases, suggesting that increasing the batch size accelerates DNN training. However, excessively large batch sizes demand substantial computational resources. Therefore, as Theorem 3.3 indicates, the critical batch size that minimizes SFO complexity is significant and practical because moderate batch sizes are suitable for implementing SGD.
C,
4 Numerical Results
We examined whether the numerical results match our theoretical results (Theorems 3.2 and 3.3). We also compared the performance of Algorithm 1 with the performances of other optimizers, such as SGD with a constant learning rate (SGD), momentum method (Momentum), Adam, AdamW, and RMSProp. The learning rate and hyperparameters of the five optimizers used in each experiment were determined on the basis of a grid search. Python implementations of the methods used in the numerical experiments are available at https: htt///gttuu//...///////e com/ com/iiduka Sellidudarrae researches armijo linesearch.
The metries were the number of steps K and the SFO complexity N = Kb indicating for different batch sizes b, at time k, the number steps K needed for the average gradient norm over the past k steps to be less than c 0.5. We used Algorithm 1 with the Armijo-line-seachh learning rate computed by Algorithm for the setting of parameters), and various values of c. We reset the step size each epoch by using Algorithm 2 with J [[ [g]
with 5 = 0.9, ā 10 (see https:///tthbb cwtp..commsssaaaaaaiieeeeeecic conn/Isamlaradji/ae
Algorithm 2 Reset step size
Require: Ginit, J, 0lk-1,.... J+1 if J then
0gk Qinit
else
0% = E ak-j
end if
return ag
We trained ResNet-18 on the CIFAR-10 dataset (n = 50000). Figure plots the number of steps needed to train ResNet-18 on the CIFAR-10 datasct for Algorithm versus the batch size. It can be seen that A Algorithm reduced the number of steps as the batch size was increased. Figure 2 plots the SFO complexities of Algorithm 1 versus the batch size. It indicates that there are critical batch sizes that minimize the SFO complexities. The Armijo condition (sce (11)) implies that, if is large, then og satisfying the Armijo condition is small, which implies that SGD with small ag would not work. In fact, indicated in Figure 1, for training ResNet-18 on the CIFAR-10 dataset, when the batch size exceeded 27, SGD using Armijo line search with e = 0.1 required greater number of steps for convergence than with e = 0.01, 0.001 because the learning rate at c= 0.1 was much smaller than that at c = 0.01, 0.001 (see Appendix A.8). As a result, as shown in Figure 2, SGD using Armijo line search with e = 0.1 had a larger SFO complexity than with == 0.01, 0.001. However, the trend in which smaller values of e resulted in fewer steps and reduced SFO complexity was not observed when training ResNet-18 on the MINIST dataset (Figures and 6). This is because the learning rate increased with the batch size for the CIFAR-10 dataset (see Appendix A.8). Therefore, we can conclude that the appropriate value for hyperparameter e depends on the specific training dataset.
Figures 3 and compare the performance of Algorithm 1 with c = 0.01 with those of SGD variants. The figures indicate that, when the batch sizes are from 2 to 2 SGD+Armijo (Algorithm 1) performs better than the other optimizers. In particular, the SFO complexity of SGD+Armij (Algorithm 1) using 0.01 and the critical batch size (b* 25) is the smallest of the optimizers for any batch size.
11

---

Published in Transactions on Machine Learning Research (03/2025)
Therefore, can conclude that Algorithm 1 using the critical batch size b* (= 2%) performs better than other optimizers using any batch size in the sense of minimizing the SFO complexities needed to train ResNet18 on the CIFAR-10 dataset.
10
Steps
10
304
2
2'
2'
2
2
2"
26
2.0
2
Datch Size
Batch Size
cm0.1
c
cm0.001
cm0.1
c 01
c=0.001
Figure 1: Number of steps for Algorithm versus batch size needed to train ResNet-18 on CIFAR- 10
Figure 2: SFO complexity for Algorithm versus batch size needed to train ResNet-18 CIFAR- 10 (The double-circle symbol denotes the mca- sured critical batch size)
105
Steps
SPO
2
2
2
2
2
2>
25
2
2.0
2
Barch Size
Barch Size
SGD+ Armio
Momentum
AdamW
SCD+Armioo
Momentum
AdamW
RMSProp
RMSProp
Figure 3: Number of steps for Algorithm with = 0.01 and SGD variants versus batch size needed to train R8sNet-18 on CIFAR-10
Figure 4: SFO complexity for Algorithm with 0.01 and SGD variants versus batch size needed to train ResNet-18 on CIFAR-10 (The double-circle symbol denotes the measured criti- cal batch size)
201
Steps
SPO
20a
6x 10
4x 10
23
24
29
2.0
21
Batch Size
c-0.001
Figure 5: Number of steps for Algorithm versus
Figure 6: SFO complexity for Algorithm versus batch size needed to train ResNet-18 on MNIST (The double-circle symbol denotes the measured critical batch size)
batch size needed to train ResNet-18 on MNIST
12

---

Published in Transactions on Machine Learning Research (03/2025)
We also considered the case of training ResNet-18 the MNIST dataset (n 60000). Figure plots the number of steps needed to train ResNet-18 on the MNIST dataset for Algorithm versus the batch size, and Figure 6 plots the SFO complexities of Algorithm 1 versus the batch size. Here, there are critical batch sizes that minimize the SFO complexities. As Figures and 6, these figures show that Algorithm 1 decreases the number of steps as the batch size increases and there are critical batch sizes that minimize the SFO complexities.
Figures 7 and 8 compare the performance of Algorithm 1 with 0.1 with those of SGD variants. Figures 7 and 8 show that the adaptive methods, i.e. Adam and AdamW, performed well. When the batch size from 2 to 29, SGD performed better than SGD using the Armjo-line-soarch learning rate in the sense of minimizing the number of steps and SFO complexity. When the batch size was large such as b = 2 2 or 2", SGD using the Armijo-lin-ssearhh learning rate performed better than SGD and Momentum in the sense of minimizing the number of steps and SFO complexity. In short, Figures 3, 4, 7, and 8 show that, when using large batch size, SGD with Armijo line scarch performed better than SGD and Momentum.
104
10a
Steps
SPO
109
23
25
2.0
21
25
25
2
Betch Size
Baich Size
SGD+Armão
Momentum
AdamW RMSProp
SGD+Armijo
Momentum
Adamm
Adam
RMSProp
Figure 7: Number of steps for Algorithm with 0.1 and SGD variants versus batch size needed to train ResNet-18 on MNIST
Figure 8: SFO complexity for Algorithm 1 with = 0.1 and SGD variants versus batch
size needed to train ResNet-18 on MNIST (The double-circle symbol denotes the measured criti- cal batch size)
5 Conclusion
This paper presented a convergence analysis SGD using Armijo line search for noncouvex optimization. We showed that the number of steps needed for nonconvex optimization is monotone decreasing and convex with respect the batch size; L.., the steps decrease in number as the batch size increases. We also showed that the SFO complexity needed for nonconvex optimization is convex with respect to the batch size and that there exists a critical batch size at which the SFO complexity is minimized. We also presented numerical results that corroborate our theoretical findings. In particular, the numerical results indicated that SGD using Armijo line search and the critical batch size performs better than other optimizers using any batch size in the sense of minimizing the SFO complexity needed to train ResNet-18 on the CIFAR-10 dalaset.
Acknowledgments
We are sincerely grateful to the Action Editor, Alec Koppel, and the three anonymous reviewers for helping us improve the original mamuscript. This rescarch partly supported by the computational resources of the DGX A100 named TAIHO at Meiji University. This work was supported by the Japan Society for the Promotion of Science (JSPS) KAKENHI Grant Number 24K14846 awarded to Hideaki Tiduka.
13

---

Published in Transactions on Machine Learning Research (03/2025)
References
Amir Beck, Pirst- Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadel- phia, PA, 2017.
Hao Chen, Lili Zheng, Raed AL Kontar, and Garvesh Raskutti. Stochastic gradient descent in correlated set- tings: A study on Gaussian processes. In Advances in Neural Information Processing Systems, volume 33, 2020.
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 Fchrman, Benjamin Gess, and Armulf Jentzen. Convergence rates for the stochastic gradient descent method for non-convex objective functions. Journal of Machine Learning Research, 21:1-48, 2020.
Leonardo Galli, Holger Rauhut, and Mark Schmidt. Don't be monotone: Relaxing stochastic line search in over-parameterrieed models. arXiv preprint arXiv:2306.1227 2023.
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. STAM Journal Optimiza- tion, 23:2061 2089, 2013.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to a local nash equilibrium. In Advances in Neural Information Processing Systems, volume 30, 2017.
Hideaki Tiduka. Critical bach size minimizes stochastic first-order oracle complexity of deep learning optimizer using hyperparameters close to one. arXiv: 2208.09814, 2022.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: Mini bati-nat averaging, and model misspecifi- cation. Journal of Machine Learning Research, 18(223): 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of The International Conference on Learning Representations, 2015.
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.
Tly Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proceedings of The International Conference Learning Representations, 2019.
Hiroki Naganuna and Hideaki liduka. Conjugate gradient method for generative adversarial networks. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 4381-448 3381-4408. PMLR, 2023.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approxima- tion approach to stochastic programming, SIAM Journal Optimization, 19:1574 1609, 2009.
Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of convergence (11kk). Doklady AN USSR, 089:543-547, 1983.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer Series Operations Research and Financial Engineering. Springer, New York, 2nd edition, 2006.
14

---

Published in Transactions on Machine Learning Research (03/2025)
Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathemalics and Mathematical Physics, 4:1-17, 1964.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In Proceedings of The International Conference Learning Represenlations, 2018.
Herbert Robbins and Herbert Monro. A stochastic approximation method. The Annals of Mathemalical Statistics, 22:400 407, 1951.
Naoki Sato and Hideaki Tiduka. Existence and estimation of critical batch size for training generative adversarial networks with two time-scale update rule. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 100800-30000 PMLR,
2023.
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, Jaehoon Lee, Joseph Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George E. Dahl. Mcasuring the effects of data parallelism neural network training. Journal of Machine Learning Research, 20:1 10:1-9,.44 2019.
Tijmen Tieleman and Geoffrey Hinton. RMSProp: magnitude. COURSERA: Neural networks for machine learning, 4:26-34 31, 2012.
Divide the gradient by a rumning average its recent
Hikaru Umeda and Hideaki Tiduka. Increasing both batch size and learning rate accelerates stochastic gradient descent. Transactions on Machine Learning Research, 2025.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien Painless stochastic gradient: Interpolation, line-scarch, and convergence rates. In Aduances in Neural Information Processing Systems, volume 32, 2019.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Neural Information Processing Systems, volume 31, 2018.
Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George E. Dahl, Christopher 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.
15

---

Published in Transactions on Machine Learning Research (03/2025)
A Appendix
A.1 Proof of Lemma 2.1
(i) Let & E N and let LB, be the Lipschitz constant of V BB. Lemma in (Vaswani et al., 2019) is as follows:
VfB.: R² + R VC (0, 1) vOn E E va >
Eaz (0 (fB. (02 a fB, (0x)) S fB. (0%) caxllV min 2 c) .
(17)
LB² .a S ak
The negative proposition of (17) is as follows:
3fB. R R 3c 10 30,+ Bd 3a
[ - c)
(18)
3or (0, (JB, (O2 on VB (s)) S Jn, (0s) co.. /ow.///// (0x) min
0 ak.
L.B,
We will prove that (18) holds. Let. n = b = 1, d = 1, c- = 0.1, a 1, and ʃ(0) - Sn. (0) = 0². From
ff(0) = -0,, we have that LB, = 2. Since 0r = is the global minimizer of f, we set 0g E R such that
O2 * 0" The Armijo condition this case is such that (0x 2ax0x)² S 0f - can (20x)) which equivalent
a c 0.9. Hence,
3ay E (0. 1] (ox I 0.9) A (min {0.9, 1] > on)
+ 3a+ E (0, a| (aR - - c) A min 2( - c)
.a > ak
LBz
[2(1- - c)
+ 3a+ E (0, ब (fB, (0x - ax fBB, (0+)) S fB, (0x) car ffB, (0x) A min
> akk:
LB,
which implies that (18) holds.
(ii) We can show Lemma (ii using the proof (Case 2) of Lemma 1 in (Galli et al., 2023). Since at does not satisfy the Armijo condition (11), we have that
fBa (0a- ak fB. fB, (0x) c [V2 3
(19)
The LB, -moothness of fB. ensures that the descent lemma is true, i.c.,
Jn, (0x- - alk
di V/.. (0x)
< Sp. + (Ox) (0x - ak (BB (0a) 0z) +
LB.
(0.x - ak
(BB( - ool²²
2
g
which implies that
f 0 akk V (m)( s fn. (0x) (0x) +
Ln, O&k
-1) | [ fr, (0x)
(20)
8
28
Hence, (19) and (20) imply that.
ak | (n.) < ak (LB
-1) | IVV/n, [
28
which in turn implies that
0g
LB - (1 (1-)) |/V... (2x) 2 0.
8
28
Accordingly,
L 0kk
28(1 - c)
28(1 - c)
(1 c) 2 0, i.e., 2
>
28
LB.
L
16

---

Published in Transactions on Machine Learning Research (03/2025)
A.2 Proof of Theorem 3.1
The definition of ((0) = 1 (einn)(((0)) and the L, smoothness of Sa (i E [n]) imply that, for all 01. 02 IRd
[V)()))) - v.2(02))l Eiejnl Li 110 -22l:
[V)(())) (0)
1 n M
Σ
n
which in lurn implies that V is Lipschitz continuous with Lipschitz constant Iu == 1/2 Eie(m] Li- Hence, the descent lemma ensures that, for all N,
f(0R+1) - f(0s) (V.(())), 0x+1 0x) + Ln 11 0ul1?
(21)
which, together with Ox+1 = - - V fBB. (0x); implies that
L 2
f(0x+1) S f(0x) av V f(.)). fBB. (0a)) + IVB.. (0+).
(22)
From (x) = -/===/=11 + 11
|| - د (a. y E Rd., we have that, for all N
(0)) BBB. (0:)) = 1 (I V/B. (0,) 1V)
-V VIB, (0))
Accordingly, (22) implies that, for all k E N,
0 f(0x+1) S f(Ok)
2 (I -1711 fB.
L | fa. (0x)
2
= f(ww) ak 2
|VS(0)11 + (Lnax 1) VBB, (0x) + a* 2 V [v()))
V.B.(O)))
(i) We consider the case of 1.- 2 a. The condition 0 a S a implies that L, S Lnā and
28(1 < ags we have that, for all le e N,
L, 1. From 0 < a
f(0++1) f(0)) [V 1 2L V... + [V V.B. (0+)).
(23)
Assumption guarantees that
Esg [V (Os) = v)())) and Ee, [I[ (O.) v)(0))) 0zl S a²
(24)
Hence, we have
Es,. [I [0x)
-Ee, [[IV f, (0x) (02)2)) + v/(0a)]
-EEN [IIV F. (0x) (0())) [0 2E,, [V/n, V/())) E., (0x)) (25)
S [0 + a²
Inequalities (23), (24), and (25) guarantee that, for all l E N,
Ee, [5(0 Oc}] < f(2x) [V((0))11 1 -L 1)x
o²)
T
||VS(On)] 1/2++0 5
2h
(26)
(Ina -1)a
{(Innt
1)a + o
=(())) ()(0)))
[V
2b
17

---

Published in Transactions on Machine Learning Research (03/2025)
Taking the total expectation on both sides of (26) thus ensures that, for all & N,
(L -1)8 [[V]( - (()(0.) [(0++i)] + {(Lnā - 1) + =ajo²
(27)
2
2b
Let K 2 1. Summing (27) from k = 0 to A: = K ensures that
(L - 1)a
K
E (0 S (B))(0)) ʃ(0x)] + {(Lnā 1)a + ajo²
2h
k=
which, together with the boundedness of f, i.e., fa S f(0x), implies that
(Ln
1)a
K-1
E [IVf(())] & Elf( f-] {(Lnā 11aa ajo²
2
26
Accordingly,
< 2(f(0o) - f+)
[(L. 1)a a
[[VS(0+)]]]
K k=0
[a (Ln 1)a) K
{a (Ln 1)a}b
Moreover, since have
K
min
E [[V)(())1
E [IV]
kE [0:K
k=
the assertion in Theorem 3i) holds.
(ii) Let us consider the case of I., < a= 1t 1+81-8 Incan 1 L,a 1 and 0 < L,a 1. For all h: E N
From 0 < as S a, we have that, for all k E N,
21.
f(0x+1) S f(x)) a [ + (L, 1f
(0)1 [Vf(e.) (f).1
(28)
Incqualities (24), (25), and (28) guarantce that, for all N,
Eg, [1(00+1) 0 ((x)) Egg [ak
[[VS(0+)) 0z + (4, 1)a [1V σ²
ao
+
(29)
2h
Since &N and 0& (E are independent, we have that
Eg,
[kk
(V Re, Okk
(0} ( [ax]-
1 |1V
2
2
Hence, (29) implies that
1 c. [au] VV + (I, 1)a [
Exg [f(0++1)] < (0x)
(30)
2
Here, let assume that EN DU)(n). Then, have that
1 b 1
1
Eg. [B.]]
Eçe
Lean
Eçu. [Lea.]]
L,,( = =)
L, Ln.
n j=1
Moreover, Jensen's inequality implies that
25( - c)
28(1 c)
25(1 - c) ā.
त Ege [ax] 2 Ee,
LB.
Ee, [Bc
Ln
18

---

Published in Transactions on Machine Learning Research (03/2025)
Hence, (30) ensures that, for all k N,
E. [((0++1)] - f(Ox) / { (L - 1)aa [V +
1
Ln
(31)
2b
Taking the total expectation on both sides of (31) thus ensures that, for all k E E,,,
ā (L, 1)a E [(.))l < [(0++))))
Ln
(32)
2
2b
Let K 2 1. Summing (32) from to t = K ensures that
- (L, 1)a
E [I - [f((0) f(0k)] + L
which, together with the boundedness of f, i.e., fa S f(0)), implies that
á (I.n 1)a
K-1
I ona202K
[ { fa]+
2
2b
k=0
Let 8 (2, C (0, 1 and
1 / + 8(1 - c)6
2
à =
<
2Ln
|1-0< } Ln
Then, we have that c)1-c)0 > 1, - <0<G c, and 1 1-c 4. Hence,
- <3000)2233 211 -
+ 8(1 - c) (2(1 - c)o - 1] < -) +1
e (4(1 c)6 - 1)2 8 -)) +1 4(1 c)6 1+ c]]++)+++
= 1+ 1 cj8
= 26(1-c)
2hn
Ln
Since < a, we have that
σ< = 1+ / 1 + 8(1 cc6
1 V + 4Tm
144 2(1-c36 Inn
GO<T<h
2
2
1 VI + 4l.na
1
1-V1+41
1 vI 4l.aa
3 0<a <6
$
<o<a<h=
2Ln
2Ln
2L,
3 a 2 +a+ā> 0
(In 1)aa>>>
Therefore, we have
E [[[V/(()]]]] < 2(f(00) fc)
Ln
(a
- 110) K
[a (Inn 1)a
A.3 Proof of Theorem 3.2
We have
C1 C2 =2
K b
is equivalent to
C2b
K= K 2b C2
Hence, Theorem 3.1 leads to an e approximation.
(ii) We have
dK(b)
-CIC 5 0 and
d
2C
2 0,
db
(e2b (eb-C2)²
db2
(e C2)
which implies that K is monotone decreasing and convex with respect to b.
19

---

Published in Transactions on Machine Learning Research (03/2025)
A.4 Proof of Theorem 3.3
From
Ci
N(b) eb - C2
have
(b)
Cib(E2b 2C2)
and d
20103
(cab C2) 20,
db
(cab - 2
db
which implies that N is convex with respect to b.
(ii) We have
if b";
db(
0
b= 6" 2
db
0
ib
Hence, the point b* minimizes N. From Theorem 3.1(i), we have that
20(1 c)
In Σ
L
ā
iE|nl
Hence,
2C2
2 00
21, 0²
{ā (Ln 1)ate2
((25(1-c)/14
- c)/Ln) - - -Inā=
g²
I2
2 [2(1 - c)p
-[ 1)
A.5 Proof of (12)
Let K 2 1. From (22) and ag = a > 0, we have that, for all E N,
1(0++1) < ((0,) - (VV( Vn, (Ox)) + a [V (0x)1l
Hence, (24) and (25) ensure that, for all E N,
E = aE [|v])())]]]] + Inaa which implies that, for all k E N,
(E]IV)(A)) + o²) )
2
a (1- Ln
L,a002
E. [V { /(0x+1))
2h
Summing the above inequalities from k k ensures that
a (1 (1-10 I,
K-1
Σ E
(
( 1 Eif( - f(0x)]
2
2b
k=
Since f bounded below by f. EiEin) fi,e; we have
K-1
[V(())))) < (F( - ff]
+ Tn
min kE
[ <
Σ
E
K
a -,
(2 - L,
20

---

Published in Transactions on Machine Learning Research (03/2025)
A.6 Estimation of critical batch size
We estimated the critical batch size by using Theorem 3.3(iii) and the ideas presented in (Tiduka, 2022) and (Sato & liduka, 2023). We used Algorithm 1 with 0.001 for training ResNet- 18 on the CIFAR- 10 dataset (Figure 2). Theorem 3.3(iii) indicates that the equation of the critical batch size involves the unknown value o². We checked that the Armijo-ine-seane also (Vaswani et al., 2019, Figure (Teft))). Hence, we used
learning rates for Algorithm with c = 0.001 are about 10 (see
10. We estimated the unknown value X = = in equation (16) of the critical batch size by using 8 = 0.9, b" = 2 (see Figure 2) and a Ra 10 as follows:
6* 0² 22 (2(1
L² (L,ā 1)
(2(1-c66
We consider case of I. 0; since b* monotonically incrcasing when Ln 2 We have
1
X
2(1 - c)o
Sctting c = 0.001 and = 2 (scc Figure 2) gives
2 2 X
2(1 0.001)0.9
Let us estimate the critical batch size using X 460, and Theorem 3.3 For example, when Algorithm 1 with 0.01 is used to train ResNet-18 on the CIFAR-10 dataset, the equation of the critical batch size is
X 2(1 - c)8 258 b
which implies that the estimated critical batch size 258 is close to the measured critical batch size b" 2 256 in Figure 2.
A.7 Test accuracies of SGD using Armijo-line-search learning rate for training ResNet-11 18 on CIFAR-10 and MINIST datasets
3.9
0.5
0.4
Spada
Rpock
Figure 9: Comparison of test. accuracy of SGD using Armijo-line-seare learning rate with c = 0.1 and those of SGD variants for training ResNet-18 CIFAR-10 10 dataset (commonly used batch size was 128).
Figure 10: Comparison test accuracy of SGD using Armijo-lines search learning rate with 0.1 and those of SGD variants for training ResNet-18 MNIST dataset. (commonly used batch size was 128).
21

---

Published in Transactions on Machine Learning Research (03/2025)
Steps
SPO
10a
10a
24
20
2
21c
25
230
231
SGD+ Armoo
Momentum
AdamnW RMSPrap
SGD
AdamW RMSProp
SGD
Adam
SCD
Adam
Figure 11: Number of steps for Algorithm 1 with 0.1 and SGD variants to achieve test accu- racy more than 0.90 versus batch size for training ResNet-18 on CIFAR-10 dataset.
Figure 12: SFO complexity for Algorithm with 0.1 and SGD variants to achieve test accu- racy more than 0.90 versus batch size for training ResNet-18 on CIFAR-10 dataset.
10
203
Stepo
SPO
10
202
10
25
230
211
2
230
231
AGD+ormio
Momentum
Adamn RMSPrap
SGD++Ammo
Nomentum
AdamW
SCD
Adam
SCD
Adam
RMSProp
Figure 13: Number of steps for Algorithm 1 with 0.1 and SGD variants to achieve test accu- racy more than 0.99 versus batch size for training ResNet-18 on MNIST datasct.
Figure 14: SPO complexity for Algorithm with 0.1 and SGD variants to achieve test accu- racy more than 0.99 versus batch size for training ResNet-16 18 on MNIST dataset.
22

---

Published in Transactions on Machine Learning Research (03/2025)
A.8 Learning rates satisfying Armijo condition for training ResNet- 18 on CIFAR-10 and MINIST datasets
c-2.1
0.7
Rpas
Figure 15: Learning rate adjustment until average gradient norm over previous steps falls below = 0.5 when training ResNet-18 on CTFAR-10 dataset with batch size of 25.
101
32-4
Figure 16: Learning rate adjustment until average gradient norm over previous & steps falls below 0.5 when training ResNet-18 18 on CIFAR-10 dataset with batch size of 26.
191
0.9
22-4
Figure 17: Learning rate adjustment until average gradient norm previous steps falls below 0.5 when training ResNet-18 CIFAR-10 dataset with batch size of 27.
23

---

Published in Transactions on Machine Learning Research (03/2025)
c=2.1
11-1
Figure 18: Learning rate adjustment until average gradient norm over previous steps falls below 0.5 when training ResNet-Ie on CIFAR-10 dataset with batch size of 28.
Roo's
Figure 19: Learning rate adjustment until average gradient norm over previous steps falls below = 0.5 when training ResNet-18 on CIFAR-10 dataset with batch size of 29.
24

---

Published in Transactions on Machine Learning Research (03/2025)
C-2.1
099
15
Figure 20: Learning rate adjustment until average gradient norm over previous steps falls below 0.5 when training ResNet-18 on CIFAR-10 dataset with batch size of 2
Rpahk
Figure 21: Learning rate adjustment until average gradient norm over previous l steps falls below 0.5 when training ResNet-18 on MNIST dataset with batch size of 25.
10
Figure 22: Learning rate adjustment until average gradient norm over previous & steps falls below 0.5 when training ResNet-18 on MNIST dataset with batch size of 26.
25

---

Published in Transactions on Machine Learning Research (03/2025)
191
C-100
Figure 23: Learning rate adjustment until average gradient norm previous & steps falls below 0.5 when training ResNet-18 on MNIST dataset with batch size of 27.
C-2.1
Figure 24: Learning rate adjustment until average gradient norm over previous steps falls below 0.5 when training ResNet-18 18 on MNIST dataset with batch size of 28.
Figure 25: Learning rate adjustment until average gradient norm over previous steps falls below 0.5
when training ResNet-18 MNIST dataset with batch size of 29.
26

---

Published in Transactions on Machine Learning Research (03/2025)
Figure 26: Learning rate adjustment until average gradient norm over previous steps falls below 0.5 when training ResNet-18 on MNIST dataset with batch size of 2
10
Figure 27: Learning rate adjustment until average gradient norm over previous à steps falls below 0.5 when training ResNet-18 on MNIST dataset with batch size of 211
A.9 Comparisons of SGD using Himijo-line-see learning rate with SGD using constant learning rate 1/VK for training ResNet-18 on CIFAR-10 and MINIST datasets
wm
m
100
Comparison of test accuracy of SGD using Armijo-line-seacch learning rate with 0.1 and that of SGD using constant learning rate x 120 z 0.004 for
Figure 28:
Comparison of training loss of SGD using Armijo-line-search learning rate with 0.1 and that of SGD using constant learning rate = 1/VK = 1/ 1/5005000// (50000/128) 120 = 0.004 for training ResNet-18 on CIFAR-10 dataset (com- monly used batch size was 128).
Figure 29:
a= 1/VK = 1/ /150000/112 training ResNett11 on CIFAR-10 10 dataset (com- monly used batch size was 128).
27

---

Published in Transactions on Machine Learning Research (03/2025)
302
562
Figure 30: Comparison of test accuracy of SGD using Armijo-line-seard learning rate with 0.1 and that of SGD using constant learning rate a = 1/VK for training ResNet-18 on MNIST dataset (com- monly used batch size was 128).
Figure 31: Comparison of training loss of SGD using Armijo-line-search learning rate with c 0.1 and that of SGD using constant learning rate a = 1/vK = 1/ (60000/1221) x 120 s 0.004 for training ResNet-18 on MNIST datasct (com- monly used batch size was 128).
L/v (6000000000 (20000/100) x 100 0.004
28


Reviews:
[{"review_id": "R2IwHov8vV", "reviewer": "Reviewer_wtqH", "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- The Armijo line search is an effective approach to automatically determining the step size. The paper gives some interesting results on the properties of Armijo line search such as the bound on the step size found by the Armijo search. \n- The paper also gives a result to show the total iteration complexity as a function of the batch size. This implies a principled way to determine the batch size.\n- The paper includes both theoretical analysis and empirical verification.\n\n**Weakness**\n- The main result on the convergence rates involve both the upper bound and lower bound of the step size, e.g., $\\bar{\\alpha}$ and $\\underline{\\alpha}$. Note that the upper bound may be much larger than the actual step size used in the algorithm, and the lower bound may be much slower. In this case, the convergence rate in Theorem 3.1 may be very slow. For example, the authors consider the case $\\bar{\\alpha}>1/L_n$, which is a constant independent of the number of iterations. However, in practical SGD uses a much slower step size in practice, e.g., a typical choice is $1/\\sqrt{K}$ in SGD with constant step size. Furthermore, the paper use $\\bar{\\alpha}=10$ in Section 4. In this case, the upper bound and the actual step size found by the algorithm may be significant, and the resulting convergence rate may be not quite effective.\n- In the inequality above Eq (22), the upper bound involves $(L_n\\alpha_k-1)\\alpha_k\\|\\nabla f_{B_k}(\\theta_k)\\|^2$. In Eq (27), the paper bounds this term by $(L_n\\bar{\\alpha}-1)\\bar{\\alpha}\\|\\nabla f_{B_k}(\\theta_k)\\|^2$. However, it seems that this inequality is not correct. Actually, the function $\\alpha\\mapsto (L_n\\alpha-1)\\alpha$ is decreasing if $\\alpha>1/(2L_n)$. Therefore, this inequality does not hold if $\\alpha_k>1/(2L_n)$.\n- Eq (25) is not rigorous. First, $-(L_n\\bar{\\alpha}-1)\\underline{\\alpha}$ should be $(L_n\\bar{\\alpha}-1)\\underline{\\alpha}$. Second, the identity does not hold since $(L_n\\bar{\\alpha}-1)\\underline{\\alpha}+\\bar{\\alpha}$ is not equal to $L_n\\bar{\\alpha}^2$.", "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 paper considers the convergence of stochastic gradient descent with minibatch and Armijo search. The main result is a convergence rate of SGD for nonconvex problems under a smoothness assumption. The paper shows that the Armijo search implies rates within a bounded interval. Based on this, the paper shows that the total iteration complexity is a convex function of the batch size, from which the paper shows a principle to set the batch size.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like the authors to present changes to address my comments above, especially about the correctness of the proof.", "broader_impact_concerns": "not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "W6APTMTjKW", "reviewer": "Reviewer_qD9t", "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. The paper claims are clear with respect to the previous work in the field and it is easy to understand the key assumption being relaxed. \n\n2. The paper has clear writing for the most part. \n\n3. The paper derives the expressions clearly in terms of the parameters of the concern. \n\n\nWeakness: \n\n1. The authors claim three theoretical results, however I consider Theorem 3.1 to be the main theoretical result and the other results to be straightforward extensions. Would love to discuss if the authors feel otherwise. \n\n2. The proof of the main result is deferred to the appendix, being a theoretical paper there should have been a proof outline in the main text. \n\n3. There are no clear and clean insights for each of the theoretical results. \n\n4. The numerical results are not clearly discussed.", "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 paper primarily analyzes the convergence of Stochastic Gradient Descent using Armijo Line Search (performed using backtracking) for optimizing non-convex optimization problems with milder smoothness conditions in context of minimizing loss functions of a Neural Network.  \n\nThe main contribution of the paper is analyzing an expected epsilon critical point in terms of the batch size and number of steps for the nonconvex optimization case with a more general objective function than SoTA. \n\nAdditionally, the authors show that the oracle complexity is a convex function under certain conditions and that existence of a critical batch size. \n\nThe theoretical results are complemented by some numerical experiments on MNIST and CIFAR-10 dataset used for training Residual Nets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Suggest reviewing and justifying if the Theorem 3.2 and Theorem 3.3 are indeed worthy of the limelight. TMLR does not focus on novelty as much on the exactness of claims. \n\n2. It would be good to have a proof outline of the main theorem explaining the key steps of the proof in the main text itself. You can use https://arxiv.org/pdf/1308.6594 for inspiration. \n\n3. Clean the insights after the main theorem atleast clearly discussing the various implications of the result. \n\n4. What is $\\nabla f_{\\xi_k,k}$ in A2?\n\n5. Can Algorithm 1 and Algorithm 2 be combined? I understand Algorithm 2 is way to do Algorithm 1 but is there a cleaner way?\n\n6. In the numerical results a discussion on the comparision with the other methods would be nice. The conclusion \"Therefore, we can conclude that Algorithm 1 using the critical batch size b performs as well as other optimizers using any batch size in the sense of minimizing the SFO complexities needed to train ResNet18 on the MNIST dataset.\" does not seem to have enough justification given the results. Figure 7 and 8 are not even discussed. Each numerical result should ideally have a hypothesis associated with it which it either rejects or fails to.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tBwyoW6SMI", "reviewer": "Reviewer_UUd5", "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": "While the theoretical result is no doubt interesting, there are some weaknesses of this paper that need to be addressed. In summary,\n1. The writing needs to be improved. (See Requested Changes below.)\n2. In the experiments, the authors showed the number of steps needed as a function of batch size. However, in reality, we are more concerned with the metrics related to the actual task we are working on, for example, classification accuracy. It would be interesting if the authors could also present the metric as a function of the number of steps and the batch size.", "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 presents a convergence analysis of SGD using the Armijo line search for nonconvex optimization. It shows that the number of steps needed for nonconvex optimization is monotonically decreasing and convex with respect to the batch size. It also shows that the SFO complexity needed for nonconvex optimization is convex with respect to the batch size and that there exists a critical batch size at which the SFO complexity is minimized.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The requested changes about writing is below (I encourage the authors to read through the paper and make changes wherever needed):\n1. Abstract: \"the previous numerical results showed that SGD ...\" -> remove \"the\"\n2. Abstract: \"The numerical results indicate that ...\" -> This sentence is redundant.\n3. Introduction, P1: \"Variants have also been presented\" -> Variants of what?\n4. Introduction, P2: \"Not only a batch size but also a learning rate affects the performance of deep-learning\" -> change \"a\" to \"the\"\n5. Introduction, P2: \"Here, SGD using a constant learning rate ... satisfies ... \" -> change \"using\" to \"uses\" and change \"satisfies\" to \"satisfying\"\n6. Introduction, P2: \"Moreover, SGD using a learning rate ... \" -> change \"using\" to \"uses\"\n7. Introduction, P2: \"Motivated by the useful numerical results in (Vaswani et al., 2019), we decided to perform convergence analyses ...\" and \"Hence, in accordance with the first motivation stated above, we decided to investigate appropriate batch sizes for SGD with the Armijo-line-search learning rate. In particular, we were interested in verifying whether a critical ...\" -> change the past tense to present\n8. Table 1: \"Upper Bound C1/K + C2/b\" -> \"Upper Bound written as C1/K + C2/b\", also add equal sign after \"C1\" and \"C2\" in the equations\n9. Change the past tense for the sentences starting with \"we\" in Section 1.3.4 to present.\n10. Section 2.3.2: \"Hence, the Armijo condition (Vaswani et al., 2019, (1)) ...\" -> it would be better if the authors could explicitly write what (1) in Vaswani et al., 2019 is for easy reading.\n11. Section 2.3.2: \"In fact, the numerical results in (Vaswani et al., 2019, Section 7) indicate ...\" -> remove \"Section 7\"", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: See above.
Decision: Accept (poster)