Bandwidth-based Step-Sizes for Non-Convex  Stochastic Optimization
Authors: Xiaoyu Wang
Mikael Johansson
Venue: ICLR 2022 Submitted (2022)
Keywords: Stochastic gradient descent
bandwidth-based step size
non-asymptotic analysis

Abstract: Many popular learning-rate schedules for deep neural networks combine a decaying trend with local perturbations that attempt to escape saddle points and bad local minima. We derive convergence guarantees for bandwidth-based step-sizes, a general class of learning-rates that are allowed to vary in a banded region. This framework includes many popular cyclic and non-monotonic step-sizes for which no theoretical guarantees were previously known. We provide worst-case guarantees for SGD on smooth non-convex problems under several bandwidth-based step sizes, including stagewise $1/\sqrt{t}$ and the popular \emph{step-decay} (``constant and then drop by a constant’’), which is also shown to be optimal. Moreover, we show that its momentum variant  converges as fast as SGD with the bandwidth-based step-decay step-size. Finally, we propose novel step-size schemes in the bandwidth-based family and verify their efficiency on several deep neural network training tasks.

Under review as a conference paper at ICLR 2022
BANDWIDTH-BASED STEP-SIZES FOR NON-CONVEX STOCHASTIC OPTIMIZATION: -ON-MONOTONICITY, WORST-CASE CONVERGENCE AND PERFORMANCE
Anonymous authors Paper under doublc-blind review
ABSTRACT
Many popular learning-rate schedules for deep neural networks combine decay- ing trend with local perturbations that attempt to escape saddle points and bad local minima. We derive convergence guarantees for bandwidth- based step-sizes, general class of learning-ratee catnin that are allowed to vary in banded region. This framework includes many popular cyclic and non-monotonic step-sizes for which no theoretical guarantees were previously known. We provide worst-case guaran- for SGD on smooth non-convex problems under several bandwidth-baseed step sizes, including stagewise 1/ and the popular step-decay ("constant and then drop by a constant"), which is also shown to be optimal. Morcover, we show that its momentum variant converges fast SGD with the bandwidth-based step-decay step-size. Finally, we propose novel step-size schemes in the bandwidth-ban based family and verify their efficiency on several deep neural network training tasks.
INTRODUCTION
Stochastic gradient methods including stochastic gradient descent (SGD) (Robbins and Monro, 1951) and its accelerated variants (e.g., SGD with momentum (Polyak, 1964; Sutskever et al., 2013)) have become the algorithmic workhorse in much machine learning. The step-size (learning rate) the most important hyper-paramett for controlling the speed which gradient-based methods converge to stationarity. For problems with multiple local minima, the step-size also affects which local optimum the optimization process converges to. It therefore needs to be both well-designed and well-tuned to make SGD) and its variants effective practice.
In the deep learning literature, cyclical step-sizes (Loshchilov and Hutter, 2017: Smith, 2017) and non-monotonic schedules (Keskar and Saon, 2015; An et al., 2017; Scong et al., 2018; Loizou et al., 2021) have attracted strong recent interest, with significant benefits for non-convex problems with poor local minima or saddle points (Seong et al., 2018). Popular cyclical schedules include the cosine step-size (cosine with restart) (Loshchilov and Hutter, 2017) and the triangular policy (Smith, 2017), which have become the default choices in some deep learning libraries, e.g., Py PyTorch and TensorFlow However, non-monotonic policies are much
(cf. Ir_scheduler. Cirreduuer..yllcl... and Annealinn more complex analyze than decaying ones, and theoretical results for these non-monotonic policies are scarce. This motivates us to focus on a bandwidth step-size framework, in which
mo(() S n < Mō(()
for some boundary function 6(t and positive constants m and M. This framework allows for non- monotonic step-sizes and covers most of the situations discussed above. In particular, it includes the cosine (Loshchilov and Hutter, 2017), triangular (Smith, 2017), sine wave (An al., 2017) step-sizes special cases. The framework provides uniform convergence rate guarantee for all step-size policies which remain in the band (1). This gives a lot of freedom to design novel step-sizes schedules with improved practical performance without loosing track of their theoretical convergence guarantee.
The generic bandwidth framework has recently been proposed by Wang and Yuan (2021), but they only analyzed strongly convex problems. We believe that more significant potential lies in the non-convex regime. For non-convex problems, non-monotonic step-sizes have distinct advantages, helping iterates to escape local minima and producing final iterates of high quality. In the paper,

---

Under review as a conference paper at ICLR 2022
demonstrate this point on both simple toy example and large-scale neural network training tasks. Our main contribution is a sequence of non- non-asymptotic convergence results for the bandwidth step- size non-convex optimization problems, based the popular "constant and then drop" step-size schedules (Krizhevsky et al., 2012; He et al., 2016; Hazan and Kale, 2014; Ge et al., 2019; Wang al., 2021). This allows non-monotonic variations both within each (inner) stage and between stages.
1.1 CONTRIBUTIONS
Inspired by the strong potential of non-monotonic step-size schedules demonstrated above, extend the bandwidth-base based step-size framework to "constant and then drop" (multi-stage) profiles, where the bands stay constant throughout each stage and drops between stages. We provide convergence guarantees for both SGD and its momentum variant (SGDM) on non-convex problems. Specifically,
We establish worst-case theoretical guarantees for SGD with bandwidth step-size on smooth nonconvex problems. We (i) derive an optimal rate for SGD under bandwidth step-size with 6(t) 1/vt; (ii) and achieve optimal and near-optimal rates for step-decay (constant and then drop by a constant), improving the results by Wang et al. (2021).
We provide worst-case theoretical guarantees for SGDM with bandwidth- step-size in the smooth non-convex setting. To the best of our knowledge, these the first results that provide optimal (Theorem 4.3) and near-optimal (Theorem 4.2) results for momentum with step-decay step-sizes. Moreover, our results significantly improve the convergence results from Liu et al. (2020) (see Remark 4.4).
step-decay
Our analysis results also provide state-of-the tie-thhert art theoretical guarantees for co- sine (Loshchilov and Hutter, 2017) and triangular (Smith, 2017) step-sizes their boundary functions are within our bands. Especially, we improve the result of Li et al. (2021) for cosine step-size and achieve state-of-art rate (see Remark 3.4). Moreover, our results first provide the convergence guarantees for triangular step-size (Smith, 2017).
We propose novel, possibly non-monotonic, step-size schedules (e.g., step-decay with linear- mode and cosine-mode) based on the bandwidth-bad based framework and demonstrate their efficacy several large-scale neural network training tasks.
1.2 RELATED WORK
This subsection reviews the theoretical development of the SGD algorithm and its momentum variant in the smooth non-convex setting, with a special focus on different step-size policies.
SGD for nonconvex problems The first non-asymptotic convergence of SGD to stationary point of a general smooth non-conved function was established in Ghadimi and Lan (2013). The authors proved that a constant step-size (LI/VT) attains a convergence rate of (L/vVT), where T the iteration budget. To the best of our knowledge, this rate is not improvable and was proven to be tight up to a constant without additional assumptions (Drori and Shamir, 2020). For the 1/Vt decay step-size, an OIn T/VT) rate can be easily obtained from (Ghadimi and Lan, 2013). This rate can be improved to the optimal by selecting a random iterate using weights proportional to the inverse of the step-size (Wang et al., 2021). The sampling rule in (Wang et al., 2021) depends on the step-size and is easily applicable to different step-size policies. Thus, in this paper, we choose similar sampling rule as (Wang et al., 2021) favor the later iterates when selecting the output for SGD and its momentum variant.
Step-decay step-sizes Recently, the theoretical performance of step-decay or stagewise strategies has attracted an increasing attention due to their excellent practical performance (Yuan et al., 2019; Ge et al., 2019; Chen et al., 2019; Li et al., 2021; Wang et al., 2021). For a class of least-squares problems, Ge et al. (2019) established near-optimal OIn T/T) rate for the step-decay step-size (cut by 2 every T/ log2(")) (T") iterates) and showed that step-decay can perform better than the polynomial decay step-size. Stochastic optimization methods with stagewise step-sizes decaying 1/t were analyzed in Chen et al. (2019). A near-optimal rate for the continuous version of step-decay, called exp-decay, well for cosine decay step-sizes under the Polyak-Lojasiewice (PL) condition and a general smooth assumption were established in Li et al. (2021). However, in the smooth case, to achieve such results for exponential and cosine decay step-sizes, the initial step-size is required to
2

---

Under review as a conference paper at ICLR 2022
be bounded by O(1/VT). This is obviously impractical when the number of iterations T is large. Near-optimal rates (up to In T) of SGD with step-deeay step-size in several general settings including strongly convex, convex and smooth (non-convex) problems were proved in Wang et al. (2021). They also removed the restriction on the initial step-size for exponential decay step-sizes. Empirical evidences have been given in (Wang and Yuan, 2021) that madwwdthh-bssed strategies improve the performance of the step-decay step-size on some large scale neural network tasks. However, no theoretical guarantees for non-convex problems were given.
SGD with momentum on nonconvex problems The momentum variant of SGD (SGDM) has been widely used in deep neural networks (Krizhevsky al., 2012; Sutskever al., 2013: He et al., 2016; Zagoruyko and Komodakis, 2016). Due to its practical success on neural networks, its theoretical performance now attracting lot of interest, especially for nonconvex problems (Yan al., 2018; Gadat et al., 201 8; Chen et al., 2019; Gitman et al., 2019; Mai and Johansson, 2020; Liu et al., 2020;
Defazio, 2020). Under the assumption of bounded gradients, Yan al. (2018) proposed a unified analysis framework for stochastic momentum methods and proved an optimal O rate under constant step-sizes. A similar result for the Nesterov-acceeeratee variant was established in Ghadimi and Lan (2016). However, studies related to the multi-stage performance of SGD with momentum is lacking and far from being complete. Reference Chen et al. (2019) considers momentum method with a stagewise step-size, but the method is proximal point algorithm with extra averaging between stages, and not the widely used momentum SGD considered here. More recently, Liu et al. (2020) established the convergence for multi-stage SGDM and provided empirical evidence to show that multi-stage SGDM is faster. However, their results require inverse relationship between stage length and step-size which limits the initial stage length or step-size. A detailed comparison with (Liu et al., 2020) will be given Section 4 (see Remark 4.4).
Organization:
The rest of this paper is organized as follows. Notations and basic definitions are introduced Section 2. Our novel theoretical results for SGD and its momentum variant (SGDM) under bandwidth -baed step-sizes are introduced in Sections 3 and 4, respectively. Numerical experiments are presented and reported in Section 5. Finally, Section 6 concludes the paper.
PROBLEM SET-UP
We study the following, possibly non-convex, stochastic optimization problem
min RERd f(x) = (x:=[f(xx;
where & is a random variable drawn from some (unknown) probability distribution E and f(x; {) is the instantaneous loss function over the variable Rdd We consider stochastic gradient methods that generate iterates x. according to
x¹ - 17
where of is the step-size and d' the search direction (e.g., d' ff(x"; {) for SGD). We assume that there constants >> 0 and M m, and two functions n(t) and 6(t): R + R such that such that
of (())(()), VI 1,
where nl)) (m, M and 5(1) is monotonically decreasing function satisfying 5(1) = 1. Note that even though the boundary function 5(t) is monotonic, the step-size itself is not restricted to be. Throughout the paper, we make the following assumptions:
ull every x,y E dom (f)- Assumption 2. For any input vector I, the stochastic gradient oracle O returns a vector such that (a) Elllg - f=))) < f(x)] + a where p 2 0 and a 2 0; (b) E|llg| < G².
Assumption 1. The loss function I satisfies [V)(x) (
3 NON-ASYMPTOTIC CONVERGENCE OF SGD WITH BANDWIDTH-BASED STEP-SIZE
In this section, provide the first non-asymptotic convergence guarantees for SGD with bandwidth- based step-sizes on smooth non-convex problems. The results consider a general family of bandwidth- based step-sizes which includes the classical multi-stage SGD special case.
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1 SGD with Bandwidth-basel Step-Size
1: Input: initial point z/. # iterations T, # stages N, stage length {S.) such that E S T,
the sequences { and { (n(t,
1"t t=1 E [m, with < m S M
2:
for t= 1: N do
3:
for i= 1: S: do
4:
Query a stochastic gradient oracle O at of to get a vector of such that Blgt = Vz() Update step-size nn nl(, i)o(()
5:
6:
x;41 = - = end for
7:
8: x =x's
9:
end for
10: Return: är is uniformly chosen from {-1 ,.."... . where the integer t* is chosen from
(1,2,-.., with probability P. = 8 (1) (0)
Algorithm details our bandwidth- based version of the popular "constant and then drop" policy for SGD, Here, the boundary function 5() adjusted in an outer stage, and the length of each stage S, is allowed to vary. Similar to Wang et al. (2021). I), the output distribution depends on the inverse of d(), hence puts more weight on the final iterates. By considering specific combinations of ö(t) and S., this framework allows us to analyze several important multi-stage SGD algorithms, including those with constant, polynomial-decay and step-decay step-sizes. For example, we consider the step-decay step-size by letting n(t, i) = and 5(t) 1/a where m denotes its initial step-size and a > 1. Many interesting results on polynomial-dest step-size (e.g., 5(t) = 1/V2, we called it 1/ /-ndd) are given in Appendix A.
3.1 CONVERGENCE UNDER BANDWIDTII STEP-DECAY STEP-SIZE
Another important step-size is Step-Decay ("constant and then drop by constant"), which is popular and widely used in practice, e.g. for neural network training (Krizhevsky et al., 2012; He et al., 2016). In this subsection, analyze bandwidth step-sizes that include step-decay
special case.
For Step-Decay, the stage length S, typically a hyper-parameter selected by experience. We first analyze bandwidth version of the algorithm analyzed in ['Theorem 3.2g al., 2021), namely Algorithm 1 with N [log. /2] outer loops where a > 1, each with constant length of S, / log,, 77.. The logarithmic dependence of N on T leads to a small number of stages in practice, and was demonstrated to perform well in deep neural network tasks (Wang et al., 2021).
Theorem 3.1. Under Assumptions and 2(a), and assume that there exists a constant Ag > 0 such that [xf - f*] < Do for each > 1 where f min f()), if we Algorithm 1 with T a?, vi < 1/((p + 1)L), N = L(log, T)/2), S. = [2T/ loga TT, and 8(1) = 11/a² 1- for 1 < l < N,
where O >> 1 then
Ao 20m
2
(a 1)
l
B V
2m
In
VT-a
Theorem 3.1 establishes near-optimal (up In T) rate for the step-decay bandwidth scheme which matches the result achieved at its boundaries i.e., r/f m0)() () or v/ = M8(() (Wang et al., 2021). As the next theorem shows, this guarantee can be improved by appropriate tuning of the stage length S,
Remark 3.2. (Justification of uniformly bounds on the function values) In Theorem 3.1, require that the expectation of the function value at each outer iterate [[f(=a]] is uniformly upper bounded. As shown by Shi et al. (2020), the function values at the iterates of SGD can be controlled (bounded) by the initial state provided the step-size is bounded by L/L. So the assumption is fair if the initial state is settled. Nevertheless, this assumption (or its stronger version that the objective function is bounded) is commonly used or implied in optimization (Hazan et al., 2015; Xu et al., 2019b; 2020; 2019a) and statistic machine learning (Vapnik, 1998; Cortes el al., 2019), and it has never been violated in our numerical experiments.
We use Fi to denote o-algebra formed by all the random information before current iterate xf and xf Fl.
4

---

Under review as a conference paper at ICLR 2022
Theorem 3.3. Under Assumptions I and 2(a), and assume that there exists constant Ag > 0 such that (zf - f Σ Ao for each t 2 1. if we run Algorithm 1 with T > a², n/ S 1/((p + 1)L),
So = VT, S, = [Spa (t-1 and 8(t) = 1//a"1 where a > L, then
Ma a- 1 ( m m
++ (200
+
Optimal rate for step-decay step-size The theorem shows that if the stage length St increases exponentially, and the length of the first stage is set appropriately, then can achieve an optimal OLL/VT) rate for the bandwidth step-decay step-size in the non-convex case. If M m, which means that the bandwidth scheme degenerates to the step-decay type step-size, Theorem 3.3 removes the logarithmic term present in the results of Wang al. (2021). To the best of our knowledge, this is the first result that demonstrates that vanilla SGD with step-decay step-sizes can achieve the optimal rate for general non-convex problems. The numerical performance of the two step-size schedules in Theorems 3.1 and 3.3 are reported in Figure 4.
Benefits of Theorems 3.5 vs the references of Hazan and Kale (2014); Yuan al. (2019) Another commonly used step-decay scheme in theory which halves the step-size after each stage and then doubles the length of each stage (e.g., (Hazan and Kale, 2014; Yuan et al., 2019)). In Hazan and Kale (2014), which considers strongly convex problem, the initial stage is very short, S = 4, while the analysis in Yuan al. (2019) for PL. functions use an inverse relation between stage length and step-size, which means that longer initial stage length requires smaller stepsize. In contrast to these references, Theorem 3.3 considers step-decay with long first stage, S [VT], which allows us to benefit from a large constant step-size for more iterations.
Remark 3.4. (Guarantees for cyclical step-sizes) In (Loshchilov and Hutter, 2017), the authors decay the step-size with cosine annealing and use Miin Vruax to control the range of the step-size. If mm(() S "min Miaxx S M8(t), then our results provide convergence guarantees for their step-size. To achieve a near-optimal rate, Li et al. (2021, Theorem 4) need use an initial step-size that is smaller than O(1/ D()/TT) which is obviously impractical. In contrast, we allow the cosine step-size to start from a relatively large step-size and then gradually decay (see Theorem 3.1) and also improve the convergence rate to be optimal (Theorem 3.3).
A triangular cyclical step-size is proposed by Smith (2017) which is varied around the two boundaries that drop by constant after a few iterations. Our analysis first provides theoretical guarantees (e.g.. Theorems 3.1 and 3.3) also for this step-size. The details are shown in Appendix D.2.
Staelie
the 2510
Iteratiin
Renatien
Figure 1: Cosine step-size (left) and triangular step-size (right)
The bandwidth step-sizes we consider above are independent on the random information. In recent years, some non-monotonic step-sizes have been proposed that are dependent on the current random information, e.g., the trust-region-ish algorithm (Curtis et al., 2019) and stochastic Polayk step- size (Loizou et al., 2021). We provide some interesting results for these step-sizes (see Lemma B.2 in Appendix B).
4 NON-ASYMPTOTIC CONVERGENCE OF SGDM UNDER BANDWIDTH-BBAEED STEP-SIZE
In this section, we establish the first non-asymptotic convergence properties of SGD with momentum (SGDM) under the bandwidth-band based step-size on smooth nonconvex problems.
5

---

Under review as a conference paper at ICLR 2022
In this scheme, the inner iterations in Step 6 of Algorithm are essentially replaced by
o Bof + - (1-
(4)
4|+1 2 of44
(5)
for 3 E (0, 1). We refer to Algorithm 2 in Appendix C' for more detailed description.
As in many studies momentum moonettum-methods methods (e.g. Ghadimi al. (2015); Yan et al. (2018); Liu et al. (2020); Mai and Johansson (2020)), we establish an iterate relationship of the form B[[W++] <
E - Con) + enr², where W Lyapunov function, et a performance measure (here, e' = =V= is the step-size and ep and Cj are constants. However, due to the time-dependent and possibly non-monotonic handwidth-based step-size,
cannot use the Lyapunov functions suggested in Yan et al. (2018); Liu et al. (2020) but rely on the following non-trivial construction:
Lemma 4.1. Suppose that Assumption and Assumption 2(b) hold. Let 2 (1- (x} -x4-1)
and assume that there exists a constant Do such that [[[( [*] S Do for L, 2 and the step-size in each stage is monotonically decreasing. Define the function W
(((+1)) + rll aill? + +2rlf(x(+1) f*).
W
T
T
where
3L 2(1-8")1-0)> Then, if S L. any and i 2 2, we have
(
1
1
E(W! i+1
F W +A
n
V + n) BiG
(6)
where A
8Ag 1-9 +
A.
B1 = r(1 3) - B) + 2(1-B)2- and A, = Ao + 2(1-8)=L 1
1-3
Note that even though the size is assumed to be monotonically decreasing in each stage, it may be increased between stages, leading globally non-monotonic step-size. The proposed bandwidth- based step-sizes (c.g., step-decay with linear or cosine modes) in the numerical experiments and the cosine annealing policy proposed in (Loshchilov and Hutter, 2017) all satisfy this condition. Note that, unlike (Mai and Johansson, 2020; Liu et al., 2020), the momentum parameter 3 does not rely on the step-size, but can be chosen freely in the interval (0, 1). In particular, our analysis supports the common choice of 3 = 0.9 used default in many deep learning libraries (Krizhevsky et al., 2012; He et al., 2016). Similar to Remark 3.2, the function value of the iterates for momentum can also be controlled (bounded) by the initial state given of < 1/L; see (Shi, 2021). Therefore, we believe our assumptions are reasonable.
If we restrict the analysis to single stage, N = the lemma allows to recover the optimal rate for SGDM under the step-size of no/ V (Yan et al., 2018; Mai and Johansson, 2020; Liu et al., 2020; Defazio, 2020) and to prove, for the first time, optimal O(1/VT) rate for SGDM under the 1 1/Vi stepsize. These results are formalized in Appendix D.I.
4.1 CONVERGENCE OF SGDM FOR BANDWIDTH STEP-DECAY STEP-SIZE
We now show the convergence complexity of SGDM with the bandwidth step-decay step-size. Here step-decay means that the bandwidth limits are divided by a constant after some iterations.
We first consider the total number of iterations T' to be given, the stage length S, be constant, and the number of stages N as a hyper-parameter.
Theorem 4.2. Assume the same setting as Lemma 4.1. If given the total number of iterations T 2 1. N 2 1, S. = S = [T, d(t) = 1/a 11 for each 1 t N and a > 1, then
W1 N
N
(A. C1) Na
N
T- + (aCo + C2)
MB
T
m
N-
where Co r( + 2Do),. C1 A1 1 A,
1-3' and C2 = + A2G Ag =1+
8
2(1-333
and W1 Ai, Bi, Az, and are defined in Lemma 4.1. Furthermore, N [(log T
and
S. = 12T loga T for each S 1 S where a > 1, we have
E||l (((r)(1)) a2W1 I
a T3/2 + (aCo + C2) InT
(A, + + I
a GB ln
(8)
2la
T
2m l VT
2 VT

---

Under review as a conference paper at ICLR 2022
o When N 1, m n/ I M and the bound (7) reduces to E| { If, in particular, m and M are of order D(1/vT)), then we can derive the optimal convergence for constant bandwidth step-sizes, comparable to the literature for constant step-sizes (Yan et al., 2018; Liu et al., 2020; Mai and Johansson, 2020; Defazio, 2020).
mT + M).
It is not easy to explicitly minimize the right-hand-side of (7) with respect to N. However, N = [[lgg, / attempts to balance the last two terms and appears to be a good choice in practice. The theorem (see (8) establishes an (In T/ /T) rate under step-decay bandwidth step-size. If M = m, which means that the step-size follows the boundary functions, we get near-optimal (up to In T) rate for stochastic momentum with a step-decay step-size on non-convex problems. We believe that this is the first near-optimal rate for stochastic momentum with step-decay step-size. The next result shows how an exponentially increasing stage-length allow to sharpen this guarantee even further.
Theorem 4.3. Suppose the same setting as Lemma 4.1. Consider Algorithm 2, if the functions (tt 1/a"- with a > S. [Soa* '1 with So VT, we have
W T3/2
Co
A
C
G VT
E [
+
T
mvT
MVT
The stage length Se in Theorem 4.3 increases exponentially from S1 = [VT] over N [log ((a 1) + 1)] stages, resulting in an (1/vT) optimal rate for SGDM under the bandwidth- based step-decay scheme. This removes the In T term of Theorem 8. To the best of our knowledge, this work is the first that is able to achieve an optimal rate for stochastic momentum with step-decay step-size in general non-convex setting.
Remark 4.4. (Better convergence than Liu et al. (2020)) We notice that reference Liu et al. (2020)
analyzes multi-stage momentum and obtains the bound
[(x1) [(())- - OL EL
(9)
N
N
Here, E is uniformly sampled iterate (unlike results, which favour later iterates) and N is the number of stages. The result uses a time-van tine-varying momentum parameter, whose value is determined by the step-size 1f,, and also assumes inverse relationship between the step-size and stage stage-length, i.e. that S, is constant. Hence, is of Ologg, T) and the convergence guarantee in (9) is of O(1 loga T), which is far worse than the rate of Theorem 4.2 and the optimal rate of Theorem 4.3.
NUMERICAL EXPERIMENTS
In this section, we design and evaluate several specific step-size policies that belong to the bandwidth- based family. We consider SGD with and without momentum, and compare their performances on neural network training tasks on the CIFARIO and CIFAR 100 datasets.
5.1 BASELINES AND PARAMETER SELECTION FOR THE BANDWIDTH STEP-SIZES
The bandwidth framework allows for unified and streamlined (worst-case) analysis of all step-size policies that lie in the corresponding band. Within this family, the band gives lot of freedom in crating innovative step-size policies with additional advantages. In particular, we will design a number of step-size policies that add periodic perturbations a baseline step-size, attempting to both escape bad local minima and to improve the local convergence properties.
The step-decay bandwidth step-sizes divide the total number of iterations into small number of stages, in which the boundary functions are constant. The width of the band are determined by the constants and M. We will explore step-sizes that add decreasing perturbation within each stage, starting at the upper band at the beginning of the stage, ending at the lower bound at the end of the stage, and decaying as 1/i,J 1/Vi, linearly or according to cosine function. As baseline, we consider the step-decay step-size that follows the lower boundary function mā(t). To use the same maximum value for the bandwidth step-sizes, we do not add any perturbation in the first stage; cf. Figure 5.
For the 1/ /F-bnnd on the other hand, stages correspond to epochs and perturbing the step-size within a stage would be too frequent and lead to bias. Rather, we choose add similar perturbations
7

---

Under review as a conference paper at ICLR 2022
Table The percentage (%) of the final iterates (10000 runs) close to each local minima
constant
step-decay
small
large
baseline
lineur
1
29.61
0.12
0.40
0.14
24.66
3.45
6.89
2.95
25.13
3.28
7.55
2.99
Figure 2: The scatter plots (left); function value distribution around global minima (middle)
20.60
93.15
85.16
93.92
as for the step-decay band, but adjust the perturbation between stages. In our experiments, the two step-size policies perform roughly the same number of periods of perturbations over the training set. As baseline, we consider the step-size n = m// /L. In all experiments, the hyper- param-rarameterss (e.g.. m and M) have been determined using grid search, see Section E.2 for details.
5.2 NON-MONOTONIC SCHEDULE HELPS TO ESCAPE LOCAL MINIMA
To demonstrate the potential benefits of sandwidth-based non-monotonic step-size schedules, we consider the toy example (see Section E.3 for details and further results) from (Shi et al., 2020), which is non-convex and has four local minima?; see Figure 2. We then compare the final iterates of SGD with constant step-sizes (both large and small), step-decay, and bandwidth-based step-decay step size which we call linear-mode (illustrated in Figure 5). As shown in Figure 2, a large constant step-size more easily escapes the bad local minima to approach the global minimum at -0.7) than a small constant step-size. However, with a large constant step-size, the final iterates are scattered and end up far from the global minimum, which also has been observed in Figure 5 of (Shi et al., 2020). Therefore, we have to reduce the step-size at some points to reduce the error. This is exactly the intuition of step-decay step-size. As shown in Figure 2, the scatter plots of SGD with step-decay (red) and step-decay with linear-mode (green) are more concentrated around the global minimum than the constant step-sizes.
To quantify the ability of different step-sizes to escape the local minima, Table reports the percentage of the final iterates under the different step-size policies that are close to each minima. We can see that the ability of the step-decay policy (named baseline) to escape the local minima is slightly worse than the large constant step-size, but Figure 2 shows that the variance of the near-optimal iterates is reduced significantly. In a similar way, we can see that linear-mode not only improves the ability to escape the local minima, but also produces final iterates that are more concentrated around the global optimum. Hence, it appears (at least in this example) that non-monotonic step-size schedules allow SGD to escape local minima and produce final iterates of high quality.
5.3 NUMERICAL RESULTS ON CIFARIO AND CIFAR100
To illustrate the practical performance of the bandwidth-basee step-sizes, we choose the well- known CIFAR10 and CIFAR 100 (Krizhevsky, 2009) image classification datasets. We consider the benchmark experiments of CIFAR10 10 on ResNet-18 (He et al., 2016) and CIFAR 100 on 28 x 10 wide residual network (WRN-28-100 10) (Zagoruyko and Komodakis, 2016), respectively. All the experiments are repeated 5 times to eliminate the influence of randomness.
We begin by evaluating our step-sizes for SGD. The left column of Figure 3 present the results of the 1/Vi-band step-sizes the two datasets. As shown in Figure 5, these stepsizes are all non-monotonic. The sudden increase in the step-size leads to a corresponding cliff-like reduction in accuracy followed by recovery phase that consistently ends up better performance than in the previous stage. The three 1 /t-andd step-sizes achieve significant improvements compared to their baseline (nξ m/ /t), in terms of both test loss and test accuracy. Moreover, the linear-mode performs the best compared to other polynomial decaying modes. Then, the results of SGD with step-decay band (described in Section 5.1 or see Figure Appendix) on CIFARIO and CIFAR100
Notation: 1 3 denote the local minima at top left, top right and bottom left, respectively: and 4 denotes the global minimum hottom right.
8

---

Under review as a conference paper at ICLR 2022
with hand en CIMME1B-aattecce
5GD on RTARA1-RRaNeeti
SCOM NetiB
1211 mode
$14
Simmoda
Test SEEGUNEE
00%
Test aeeurmery
20%
$26
Yext
00C
130 Epocto
120
140
309
140
100
004
120
140
110
100
Epects
Epprctt
560 with boart en CIPAR100 WRN-28-10
SGD OFARL 00 W89--28-10
500M on CIFAR100 WRN-28-10
Alirede
L mode
Sievie
090.
Teak accuraey
Test aceurery
55%
69%
Epoche
Spache
*
xpocch
Figure 3: The test accuracy of 1/ b/ndd (left column), Step- band for SGD (middle column), step-decay
band for SGDM (right column)
are given in Figure (middle column), respectively. At the final stage, the bandwidth step-sizes improve both test loss (see Figures 6 and 7 in Appendix) and test accuracy compared to the baseline. In particular, the cosine-mode performs the best on this problem. In the second stage, baseline methods have sharp boost. Our guess is that the noise accumulates quickly under a relatively large constant step-size. But this phenomenon is only temporary. When we drop the step-size in the third stage, the performance improves.
Next, we evaluate the performance of step-decay bandwidth step-sizes on SGDM. The results are reported in Figure 3 (right column). The first observation from Figure 3 (right column) that the step-decay bandwidth step-sizes also work well for SGDM, and that again, the cosine-mode performs better than the others. Another interesting observation that the performance of vanilla SGD with cosine-mode (red) in Figure 3 is comparable to (even better than) SGDM with the baseline step-decay step-size (black) in Figure 3. similar conclusion can also be made on CIFARIO0
6 CONCLUSION
We have studied a general family of bandwidth step-sizes for non-convex optimization. The family specifies globally decaying band in which the actual step-size is allowed to vary, and includes both stage-wise and continuously decaying step-size policies as special cases. We have derived convergence rate guarantees for SGD and SGDM under all step-size policies in two important classes of bandwidth step-sizes (1/V and step-decay), some of which are optimal. Our results provide theoretical guarantees for several popular "cyelical" step-sizes (Loshchilov and Hutter, 2017: Smith, 2017), as long as they are tuned to lie within our bands. We have also designed number of novel step-sizes that add periodic perturbations to the global trend in order to escape bad local minima and to improve the local convergence properties. These step-sizes were shown to have superior practical performance in neural network training tasks on the CIFAR data set.
In the analysis of SGDM, we assume that the stochastic gradient is bounded (see Assumption 2(b)). is interesting to see how to relax this assumption in some special cases, for example, when the step-size is constant throughout each stage. It would also be interesting to see if the bandwidth framework could be specialized to a more narrow class of siep-sizes, for which we can provide even stronger convergence rates.

---

Under review as a conference paper at ICLR 2022
REFERENCES
W. An, H. Wang, Y. Zhang, and Q. Dai. Exponential decay sine wave learning rate for fast deep neural network training. In 2017 IEEE Visual Communications and Image Processing (VCIP), pages 1-4, 2017.
Z. Chen, Z. Yuan. J. Yi, B. Zhou, E. Chen, and T. Yang. Universal stagewise learning for non non-convex problems with convergence on averaged solutions. In International Conference on Learning Representations, 2019.
C. Cortes, S. Greenberg, and M. Mohri. Relative deviation learning bounds and generalization with unbounded loss functions. Annals of Mathematics and Artificial Intelligence, 85(1):45-70, 2019.
E. Curtis, K. Scheinberg, and R. Shi. A stochastic trust region algorithm based on careful step normalization. Informs Journal on Optimization, 1(3):200-220) 2019.
A. Defazio. Understanding the role of momentum in non-convex optimization: Practical insights from yyapunov analysis. arXiv preprint 1.kv:20000.00000 2020.
Y. Drori and O. Shamir. The complexity of finding stationary points with stochastic gradient descent. In International Conference on Machine Learning, pages 2658-2667. PMLR, 2020.
S. Gadat, F. Panloup, S. Saadane, et al. Stochastic heavy ball. Electronic Journal of Statistics, 12(1): 461-529, 2018.
R. Ge. S. M. Kakade, R. Kidambi, and P. Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. In Advances in Neural Information Processing Systems, pages 14977-14988, 2019.
E. Ghadimi, H. R. Feyzmahdavian, and M. Johansson. Global convergence of the heavy-ball method for convex optimization. In 2015 European Control Conference (ECC), pages 310-315, 2015. doi: 10.1 00.10099CC.2015533355622
S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341 2013.
Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1-2):59-99) 2016.
I. Gitman, H. Lang, P. Zhang, and L. Xiao. Understanding the role of momentum in stochastic gradient methods. Advances in Neural Information Processing Systems, 32:9633-9643 2019.
E. Hazan and S. Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly- convex optimization. Journal Machine Learning Research,
2014.
E. Hazan, K. Y. Levy, and S. Shalev-Shwarzz. Beyond convexity: stochastic quasi-convex optimization. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume 1, pages 1594-1602, 2015.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
N. S. Keskar and G. Saon. A nonmonotone learning rate strategy for SGD training of deep neural networks. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4974-4978. IEEE, 2015.
A. Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, pages 1106-1114, 2012.
X. Li, Z. Zhuang, and F. Orabona. A second look exponential and cosine step sizes: Simplicity, adaptivity, and performance. In International Conference on Machine Learning, pages 6553-6564 PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2022
Y. Liu, Y. Gao, and W. Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33, 2020.
N. Loizou, S. Vaswani, I. H. Laradji, and S. Lacoste-Julies Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In International Conference Artificial Intelligence and Statistics, pages 1306-1314, PMLR, 2021.
I. Loshchilov and F. Hutter. SGDR: Stochastic gradient descent with warm restarts. In 5th Interna- tional Conference on Learning Representations, ICLR 2017, Toulon, France, 2017.
V. Mai and M. Johansson. Convergence of stochastic gradient method with momentum for non- smooth non-convex optimization. In International Conference on Machine Learning, pages 6630-6639, PMLR, 2020.
B. T. Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964.
H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400-407, 1951.
Seong, Lee, Y. Kee, Han, and J. Kim. Towards flatter loss surface via nonmonotonic learning rate scheduling. In UA12018 Conference on Uncertainty in Artificial Intelligence, pages 1020-1030, 2018.
B. Shi. the hyperparameters in stochastic gradient descent with momentum. arXiv preprint 00.-2108.03944,, 2021.
B. Shi, W. J. Su, and M. I. Jordan. On learning rates and schrödinger operators. arXiv preprint arXiv:2004.06977 2020.
L. Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Conference Applications of Computer Vision (WACV), pages 464 472. IEEE, 2017.
I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and momentum in deep learning. In International Conference on Machine Learning, pages 1139-1147. PMLR, 2013.
V. Vapnik. Statistical learning theory. Wiley, New York, 1998.
X. Wang and Y--x. Yuan. On the convergence of stochastic gradient descent with bandwidth-based step size. arXiv preprint arXiv:2102.09003 2021.
X. Wang, S. Magnússon, and M. Johansson. On the convergence of step decay step-size for stochastic optimization. arXiv preprint arXiv:2102.09393, 2021.
Y. Xu. Q. Qi. Q. Lin, R. Jin, and T. Yang. Stochastic optimization for de functions and non- smooth non-convex regularizers with mon-ssympooiic convergence. In International Conference on Machine Learning, pages 6942-6951. PMLR, 2019a
Y. Xu, Yuan, S. Yang, R. Jin, and T. Yang. On the convergence of (stochastic) gradient descent with extrapolation for non-convex minimization. In Proceedings of the Twenty-Fighth International Joint Conference on Artificial Intelligence (IJCAI-19,, 2019b.
Y. Xu, Zhu, Yang, C. Zhang, R. Jin, and T. Yang. Learning with non-convex truncated losses by sgd. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 1 115, pages 701-711. PMLR, 22 25 Jul 2020.
Y. Yan, T. Yang, Z. Li, Q. Lin, and Y. Yang. A unified analysis stochastic momentum methods for deep learning. In Proceedings of the 27th International Joint Conference Artificial Intelligence, IJCAI' 18, page
AAAI Press, 2018
Z. Yuan, Y. Yan, R. Jin, and Yang. Stagewise training accelerates convergence of testing error over SGD. Advances in Neural Information Processing Systems, 32:2608 2-12008-6688, 2019.
S. Zagoruyko and N. Komodakis. Wide residual networks. arXiv preprint arXiv: 1605.070 146, 2016.
11

---

Under review as a conference paper at ICLR 2022
A CONVERGENCE FOR BANDWIDTH POLYNOMIAL-DECAY STEP-SIZES
Our first more specific result considers the 1/vtt bandwidth step-size with fixed stage length.
Theorem A.1. Under Assumptions I and 2(a), and assume that there exists a constant Ao > such that [=f( - f*) S for each 2 1. If the step-size rf S 11((pp + 1)L), the stage length S S
5 2 and the boundary function 8(t) 1/ ft each 1 st N, we have
3
3M
S
E [[|
(10)
m
V ST
2m
T
Theorem A.1 shows how multi-stage SGD with polynomial-decay bandwidth step-sizes converges to a stationary point. In the extreme case that S = 1, the step-size reduces to m/ //V S ni S MM/V and our result is comparable to the non-asymptotic optimal rate derived for m M 7J0 in (Wang et al., 2021, Theorem 3.5).
Multi-stage traditional 1/vt step-size (S = 1) In general, during the initial iterations when the first term of (10) dominates the error bound, the multi-stage technique can accelerate the convergence by larger step-size and longer inner-loop S. However, large S will make the error bound worse when the noise term begins to dominate the bound. The next theorem analyzes an algorithm with a decreasing stage length.
Theorem A.2. Under Assumptions I and 2(a),and assume that there exists constant Do > such that Exf(xa) - f*] S for each 2 1. If the step-size of S 1/((pp + 1)L), the stage length S. [So/ /t] with So VT. and ö(t) = 1/ Vt for each 1 S t N, we have
M
( < 20o + 3- 2/2
mVT
Schedule of Theorem A.2 Chen et al. (2019) The theorem establishes optimal rate for multi- stage SGD with 1/v2 bandwidth step-size. Note that Chen et al. (2019) also analyzes a stagewise algorithm with varying stage length, but their step-size decays as 1/t and stage length increases with An important novelty with our result is that it uses a long initial stage, S = =VT while a large stage length in Chen et al. (2019) requires a small initial step-size (of O11/ (T)) Figure illustrates the performance of different step-size policies: 1) 1/vE with S = 1; 2) 1/ with S. = [n/b]] where n is total sample size and is the batch size; 3) 1/ /2 with time-decreasing S, = [Sp/ /t] and So = <T; 4) and 1/t step-size with S. Sot and So = 12 from Chen et al. (2019). We can see that the step-size policies proposed in Theorem A.2 are more stable and perform the best.
For completeness, we also compare the performance of step-size schedules proposed by Theorems 3.1 and 3.3 in Figure 4 (right). Although step-decay with iineiincrassing stage length has superior theoretical convergence guarantee, constant stage length performs better in this particular example.
schedules stage length
schedules stage length
50%
Test accurac
83%
85%
73%
80%
Test
75%
with 5,-1
69%
quV't with by mymn
55%
gut with 5, +igite
55%
siep-deccy with
AitWko S Sut (Chen 12018)
stap decay with Sup!
60
150
123
140
380
20
40
60
100
120
360
180
# Epochs
Epechs
Figure 4: SGD CIFARI0- ResNet18
12

---

Under review as a conference paper at ICLR 2022
B PROOFS OF LEMMA AND THEOREMS IN SECTION 3
Lemma B.I. Suppose that Assumption I and Assumption 2(a) hold. If we run the Algorithm 1 with and nft I 1/(lp + I)L), we have
N
- MLOTT (1I)
(( S
mo(t)²
Σ (t)
Proof. (of Lemma B.1) The L-smoothness of f (see Assumption 1), i... [Vf(z) v s L || yll for all x, E dom(f) implies that
f(x) + (V =) - | v11 s f(y) S
x) || vl (12)
Applying the L-smoothness property of ʃ and recalling Algorithm at current iterate x/. we have
f(z(11) S f(x)) + (V((t)) - 21) - | - =!1
s f ne (vi(2)) ( ||0:11?
Taking conditional expectation of F! on the above inequality and due to the unbiased estimator gf such that [[9 Fij] = fzf), we obtain that
(v/)² 2
([ 1 ((a) - n/ [ 2
E 9f F...
(13)
By Assumption 2(a) that Ellgf f((a))| F - P [x))))
a. we have
|||
| = E g
||
E| go =(c+
(14)
Then incorporating the above inequality into (13) gives
B[S(+(4))))) & f(x!) + (-nA+ (n (1))T((+11) |[ + (nt)
(15)
2
If step-size of S 1/([p++1 1), we have -1² ((+)) S / For any t 2 1, the inequality
(15) can be estimated as:
ni 2
S ((x)) ElS( (n
(16)
2
Applying the assumption of step-size that oi ()(t) with m S nlt, I M for all t (1, ,N to (16) gives
mā(()
M
|V 5 s(x))- [IF
8(t)2
(17)
2
and dividing m/ into the both sides, we have
(1) [V(())|| 2 (f(x))
(lf(
M
(18)
m²(t)²
Recalling the output ir of Algorithm and then taking expectation, we have
{(]\ EN S
1
Σ
E [
(19)
13

---

Under review as a conference paper at ICLR 2022
Applying (18) recursively from 1 to St and using the fact that xf+1 +1 1- the sum of (19) for t 2 can be estimated as
N
S1
( - ([((2+)))))
M
Σ
5
(t) Σ
(20)
mo(t)²
1=1
Then plugging (20) into (19), we get
1
-
M M T
EE
(t)-
mo(t)²
as desired.
Proof. (of Theorem A.1) In this case, the step size r/. satisfies that m/Vi rh & M/VI, where 5(t) = 1/vl. /.. By the definition of (()), we have
N Σ
N
2N
dt
(21)
8(t)
1= 8(t)
Applying the assumption that B[f(x() fr1 S Do where f ming f(x) and the definition of 6()..
we have
2(E[f(x{)] - (x((4))41)
2
<
t(E[f(z))
- E(f(xtt) f)
md(t)²
m t=1
N
2
2N
Do
+
Σ
Bl((+1) - <
(22)
1=
Under Assumptions and ((a) and of 1/((p 1)), thus Lemma B.1 holds. Incorporating these inequalities into Lemma B.1 gives
1
N
SM Lo 2(E[f(x1) - [[f(+++)))
T
S SE 8-1(1)
md(t)2
1=1
2N
L T
2SN3/2
m
m
3
2 Lo S
VST
2m
T
Then the proof is finished.
Proof. (of Theorem A.2) In this theorem, we consider SGD with the 1/ Vt bandwidth step-size,
ie.. Vi Sf V for < < N, where the stage length S, = [So/ vl with So = vT, and the
boundary function (() = 1/ //v By the relationship that Σ S = T and x [x] S x + 1 for all I, get that
T
(3 - 2V2 < N <
2 + 1)
(23)
Under Assumptions and 2(a) and v/ <1/((p + 1)L), thus Lemma B.1 holds. Following the same process as Theorem A.1, the inequality (22) also holds, that is
2(E[ Bl 2N
(24)
mō(t)²
14

---

Under review as a conference paper at ICLR 2022
Then incorporating the above inequalities to Lemma B.I, have
1 Ex= 1=1
2N
Lo
B B[[V)(}>)1
+
T
525-1(1)
2N
Lo
TT
Σ
[S0/ Vtl .
1NND
M2
+
S6N
m
m
2
M
2 + 3 3-2/2
mS.
(3 22/2222m
/T
which concludes the proof.
Proof. (of Theorem 3.1) In this case, the step-size ntf exponentially decays every S iterations. By the definition of n/. we have (() = 1/a" for all 1 I t s N. The sum of 1/((t) can be estimated as
N Σ
N a-
a
8(1)
1=1
t=1
Recalling the assumption that [zf - fr1
s Au for all t 2 1, we have
N
- -E((at+))
2
N
2(- 1)
[E [E(())) - -(( - 1*)
mt(t)²
t=1
2
2(1 Bls( 1 +0)
(a² 1)
m
2a N(N-1)
1) Do
m
Under Assumptions I and 2(a) and of < 1//((e + 1).) thus Lemma B. holds. Then applying the result of Lemma B.1 and incorporating the above inequalities into Lemma B.1 gives
1
2(B[f(zi) (ff md(t)²
SM (t))
E([VS(TT)
SE 8- a
m
8(1)2
201(NN11)
L SN
5(aN~1 1)
m
Substituting the specific values of [(loga T)/2J,5 / loga T into the above inequality, we have
(a-1) 1) (Da2(N-1)
+ M
B B[|[
SN
5(a 1)
m
m
Ao + 20m
LM
(a- 1) loga
2m
VT
then transform the base log, the natural logarithm In, we can get the desired result.
Proof. (of Theorem 3.3) If So = VT and S. = [S - 11, by En S, = T, the stage length N is llog, ((a - 1)VT+ + +)J. In this case, have 5(t) 1/a- for each t [N]. Under Assumptions I and 2(a) and Th < <1/((p + 1)L), thus Lemma B.1 holds. Before applying the result of Lemma
B.I, first give the following estimations:
Spa- --11 VT 1 2N Q-
(a 1)T + 2T
Σ S S
Σ t=1
(25)
a 1
15

---

Under review as a conference paper at ICLR 2022
and also
[[[[((1) (x 1
2
N
(a² -
Σ
a
2(1-2) 2( f4] 20))
md(()2
1=
20
2((a 1)vT 1)220
m
am
Applying these results into Lemma B.I, we have
a a+1
2((a - 1)VT + 1)
M T
E|| Vf
<
(a - 1)T
+ -2
a²m
a +
200
L
+
m
VT
+ O
7
Thus the proof is complete.
In Lemma B.1, provide unified analysis framework for bandwidth step-sizes which are indepen- dent on the current random information. Recently, there are some interesting non-monotonic step- sizes, c.g., the trust-region-ish algorithm (Curtis al., 2019) and stochastic Polyak step-sizes (Loizou et al., 2021), which can also be regarded to be in a band, but those are related to the current stochastic information. We provide a unified framework for these kind of step-sizes below.
Lemma B.2. Under the same conditions in Lemma B.I, we assume that the step-size na satisfies mt(t) S off & Mō(f) and is dependent the current random information. If m S Lip+1) and
m S M s M == -pt p2 (2p++(()) we have
L(++1)
+ (M - m + LMPOT) 5(N)2
Do
V
(26)
2
where Ex - E 5(t) and dhu (2 + p)m pM - LMd2 (p 1).
Proof. We consider the step-size of is depended on the current random information and mo(1) s vi Mō((). By the L-smoothness of f, that is (vx) v S L| - y/]. implies that
L f(v) + 2) + 2 1| yl
(27)
Let x/ and 2/41 then
s(a)) v/91) L
||
(28)
Next we turn to estimate the product term
(Vf(zt).
- (V)(a)) nkott o (Ilof - v -|aa|| 2 - [|V
- sM(() v)(xa)]
mm)()) ||,;f1 m [[
(29)
16

---

Under review as a conference paper at ICLR 2022
Then taking conditional expectation on Fi to (28) and applying Assumption 2(a) and (14), we have
B(/(+(+1) 1 S ((x) m)(() || [=)))| - (
| + Mo(D)Blllo - V (((ai)| [
LM)
2
$ fxx) - mm(()) | mt)
(Bilo) - v)(xa)) [
LM2
+ + V F
(Bilot - v 1 [[
2
- f(() (2mo(t) - IM22(1)2
|[ 1 (M (m0(t) LM22(()²
B Billot VVf(a)
2
2
12m LM(2((()
(M-
2 ) 8(1) |QS
S ((a))
2
M + T.25((()
8(t)o
where by M 2 m we have M8(t) mm(() + 8
Let &b := 2m LM
0.
p M - m + 2
L.M2 We know that ö(t) - 1, then
LM
3 #2 (2+ pm pM
(0 1).
(30)
2
Let 400 (2 + p)m
pM
LM
3 (p 1). By solving the quadratic expression of M in tho if
S M < M p + 0² + 2( 1)(2 p)mL
(31)
[(p+1) 11)
then we have v0 2 t0 > 0. To guarantee that m I M, we require that (lo(m) > 0. then m S L(p-1j
Recalling the output ã which is selected from {a{} for all i E [S.] and [M] with probability Pt x 1/8(1), we have
N
E {()))
Σ
8(t)
E
En S,5(1)-1
1=1
1=1
E (E[[(a]) - EE
LM
+ (M - mm)o
8(1)-1 +
2 T
8(t)2
(2)
Do
+ (M - m + LMP
(32)
Do
8(N)2
2
where En = N S,8(1) -1 and (a) follows from the assumption that B[f(x1) -M Ao where f = min, f(z and o ++1 = -'s.+1-
The above lemma immediately results in the following convergence results for bandwidth step-sizes which depend on the current random information.
If N = and S. T, that is m information, we have
S nf
S M and of is related the current random
A
(M m) + LM
-|
(33)
7 T
1
In this case, the boundary function 5(t) = 1, so the assumption on function value can be replaced by f=(]) - f is bounded. We can achieve O(1/T)) convergence rate to reach a neighborhood of the stationary point. This error bound is comparable to the results of (Loizou et al., 2021, Theorem 3.8) and (Curtis al., 2019, Theorem 3.5).
17

---

Under review as a conference paper at ICLR 2022
Algorithm 2 SGDM with Bandwidth-based Step-Size
1: Input: initial point øt E R. of 0, # iterations T, # stages N, stage length (8 N
such that Σt= St
momentum parameter (0,1), the sequences {6(t)) and
{ {(n(t, e) 1 N
E [m, M] with 0 < S M
t=1
2:
for 1= do
3:
for :==1:S, do
4:
Query stochastic gradient oracle O at æ to get vector of such that Elg Fi Vf(x)) Update step-size ii ntt, i))(t), which belongs to the interval [mo((t, Má(())
5:
6:
of But + (1 B)g
7:
r1+1 x -
8:
end for
9:
of+1 - U and 21t1 S1
10: end for
11: Return: br is uniformly chosen from ....... J. where the integer t" is randomly
chosen from (1,2, ,N} with probability P. = (tt(()
I > S, S and 5(1) 1/a--1,
we have
E| ||] <
a-
IMPo T
(M -)m
vos(a 1)
2
vo
1 N-
LM (a (1-1)
+ (M m)oo
(34)
1
T
2 (a.V 11
4/0
Compared to the case that N
observe that increasing N 1 can improve the error
term L.M/22 of (33). If M - m S
LM² i.e., m 2 M LM² then LM turns out to
2
%
dominate the error bound of (33). If we increase N appropriately, then the error term of (33) can be improved.
C PROOFS OF LEMMA AND THEOREMS IN SECTION
We recall the momentum scheme of Algorithm 2 below
o But (1 B)g
(35)
o n! nf
(36)
where 3 E (0, 1). Before giving the proofs, we introduce an extra variable 2f then
2;
0
1-3
1-3
B 1
2 xf
(ot xi_1),
(37)
(ri+1 a²)
(38)
However, the bandwidth-base step-size t/द in our analysis is time dependent and also possibly non-monotonie, the commonly used equalities x[41 x !or + 3(x - (Yan al., 2018) or 2f41 2 vn' gf (see lemma 3 of Liu et al. (2020) do not hold in analysis. This significantly increases the level of difficulty of the analysis. The results of Lemma 4.1 is based on sequence of lemmas introduced below.
Lemma C.I. Suppose that the objective function f satisfies Assumption 1. At each stage t, the step-size Tf is monotonically decreasing. Then, for 2 2, we have
3
(1
of
Blʃ(=1+1) F [(+))
+
(f(z)) - ((x
T-
3
BL
< - |\((at)
x 11
+
10
2
2:|1² [F])
2(1 - 8y2
2(1
332
18

---

Under review as a conference paper at ICLR 2022
Proof. Using the L-smoothness of f (Assumption 1) and taking conditional expectation gives
((((2(+1) Fil
((x!)
S E V [) - - z Fil Bl|| - x²11 [il
<
1
EK V f( (xx. o x [ + 2(1 - 3)²
L
/1| - 2/ [
B
<
1
E
E(VI(a)) - (11 3)st + +Be())
|
L
Bll 1/41 - x1ll [F
3
2(1 - 3)2
3
L
S 1 [ - 1-8 (V)())) ot) + 2(1 - 3)2
Rl |||10/1 - x [il]
- - - -1- 3 (V)(z)), x - x!{
+ 2(1 - 3)2 B1 111 - =/ll²² [F].
L
Re-using the L-smoothness property of f at 2 and x gives
f( (a.)) + (Vi(=.) 2 z!)
L
|| | 11
2
3 = f = 1- B (f)(z) . =}-1)
L.32
+
|| 1/11
(39)
2(1 - B)2
Then, combining the two inequalities above, we have
B(((+(+1 F < f(+)) vi [|))(=))
1
1
(VI(x)) x =ff)
1-
7
+ 2(1 - By² - - =11 Fl + 2(1 - B)2 |0 x 1| (40)
L
L
The step-size ni for each stage is monotonically decreasing, i.c. n I 1 for 2 2, so
(1 nf > O. By the I-smoothness of f, the inner product of (40) can be estimated as
(vS(c), - x1) s f(x(-1) f(x))= + 2 | - 1!-1!??
(41)
Applying (41) into (40), we find
B[f(+(+1) Fi
$ fz(2) - n/
2
3
1
nt )
(1((t-)) f(x))
T. ||ا
x/111 11²
1-33
n//11
2
L
L
+ 2(1 - 3)2
Bl
-
-2
Fi
+
2(1 332 1 - -2/-11?
(42)
Finally, we re-write the above inequality as
B[/(+(++) F - f(z)) +
B
1
m
(f(x))- -s(xi=1)
1-3
7/-1
S |
8
+
3L
)
||0| - -x/_il²
L 2(1 - B)² Flll B1l - 1
2(1 - B)2
2(1 - 8)
< < |
BL
2
L
E1 B1| - ==l1² Ft
2(1 3y2
2(1 - 3)²
The proof is complete.
Lemma C.2. Suppose that the objective function satisfies Assumption I and the step-size oi is monotonically decreasing with of Σ 1
i at each stage, then
E || - x112 F - 3² - -
+ 2(1 - B)nk (E]f(z)+)) -( +2 (1))))) [|aiا|| | + (11)3(11- - B)L 1o?1?
<
- (1)))
19

---

Under review as a conference paper at ICLR 2022
Proof. First, due to the L-smoothness of the objective function f, we have
= + L
x s f(x)) + (Vf(z)), (11 B)g + Bu()) (n))_zz 1| B)gt + Bool1
2 || - =2:l²²
2 f(a)) - (1 - m)n (V(())))))))))))))))) - Byg (Vf(x)), ut) + (g)))
(11 3) |1:51 + =l:b)))))
2
where inequality (a) follows the Cauchy-Schwarz inequality that (I(1 - B)g + Buğll 1 - (1
8) Ilof + B || Then taking conditional expectation on both sides and due to that of is an
unbiased estimator of fx i... Eigi F = f.())). we have
[[((o(+) IF] S ((a)) - (1 - B3 [()))| Byt (VI(z). w/)
(n - B) E of 2 Fi
(g
||03
(43)
2
2
We recall the definition of of42 and incorporate (35) into (36), then
E -| Fi]]
= -ill + (1 B)st)|| [ = (n)) 3 + (1- (1-
[Fl
= (x))) (32 ||a]|| + (1_-)\"(|l[||) | + 23(1 3) (cf, vf(x))))
2
(9)
B² | - 12 + (vi) (1 - B) (11 (1- (3 || 11 23 (vt, v((e)))
(44)
2 8² ||05 1/
2 + (1)) ()) ((1 - (111))B1 1|
23 (vf, ((l
(45)
where (a) uses the fact that Blgt | [ (=x); (b) follows the procedure that u² x ;/ 1 1// 1/:
(c) applies the fact that the step-size per stage is monotonically decreasing, i.e., no < // for 2 2. Then multiplying 2n/ (1 B3 into (43) and combining (45), we get that
E || - 2 |マ| - 82 |ز 1| + 27 (1 B) (Bif(2)+)) Fi f(x!))
< 212(1t)(11 8)8 |
(1 1} || 2 | + (1:)2 ()) ||
S (2 |( + 2( (1 プリ |10:1| | + (nh) - 3)L ||uf|
where the last inequality follows from the fact that r/f - 1/L
Proof. (of Lemma 4.1) First we apply the result of Lemma C. and divided by oo to the both side,
have
B[f(2{+)) | F. f(x1)
B (f(xt)- - -(((
B (f(x!) - 1))
T B
1//
1- 3
1//11
< -- + (2(1
2((1 - )/yr))
3T,
) |101 1 -1/=11/++ +
n
Bl|l [1|0o//a1 1| 1 (FT).
(46)
2(1 3)2
Then we recall the result of Lemma C.2
E E||| | =rl1? F - || - 11 2nd (BI - f(a\))
< < - /1) - - 2 - 2( B)² |}<>)|
+ 21 2E [|0:|] 1 [
(11)) - (1))"((1-)))111333 ||
20

---

Under review as a conference paper at ICLR 2022
multiplying constant into (46), we have
BL 2(1-82)(1-88 882
0 and dividing n/ to the both side, and then incorporating
[[ ) FM] [(=))
B (f(x!) - (()
B (f(xt) ((xt))((af...) (c)
o/
1 1- B
1//
1-3
1/-1
+
r
(Ell - 2/11 [F] - -1123 - =1)) + 2r (Bif(z(+1)
-f(1))
7/
S |V 2r(()))(1 -
()) B||0!1 [F + +()))) 9)L
1 L
2(1 - 3)2 Bill o 1 F
(47)
We define a function W as follows:
f( - + r| xtll
W i+1 nf
+ (r(((())1)) - f*].
r/.
Because of 1/ S n at each stage, we have -1/n S -1/1//11 (1 262 2), then
W S f((/m)) fr
1/ + B (f(x)) -5)
B (f(x)) f*)
1- B n/
1- B
7/-1
| = + 2r (f(a)11) l*)
(48)
Taking conditional expectation W W1 and applying (47) to the above inequality, we have
1
1
B (f(a f*)
(1)
- 1*) BI [ & W + (((=))
+
1/2
v/-1
1- 3
1/
+r || - 112
|| 1| +
[
1/2
1//1
v/ L
+ -
- ||:11
2(1 - 3)² Bill 2 | 2 |
(49)
We recall that of = 0, due to the assumption that El[lgt 1 9 S G², and 8/41 is a convex combination of of and v/. then by induction if [|] [|] < G2, then
E But + (1 3)o;1| s B
+ + 3) |s G2.
(50)
Therefore, we have E|||o|| [] is bounded by G². Then we apply E|lloS1 E of S 1/L L into (49)
G2 and
B[ | | w s (f(2)) - 1
) ( - 84) (")
1
17
m//1
1-3
mi
+r 1|1 - 11-111 (1) x - -|(
G (r(1 - ()(2)) 33 2(1 - 3y2
L
(51)
The step-size is decreasing at each stage, then no S n (i 2 2). thus
1
2 0. Due to the
7/
%/
fact that of is bounded (see (50)), i.e., ||]|b[11 2 < G2, we have
G2 T3¹
Elllot - = = (ni ( | || < 10/2
(52)
21

---

Under review as a conference paper at ICLR 2022
Recalling the definition of 2f, and applying the assumption that E[f(a)) - fd] - Ao for each i, 2 1 and f is L-smooth on its domain, and nj I 1/L gives
5 E [(x) + (V/(2)) of m4) + 1 B
2 || - =1'l
L
$ ((4) 1- (VI(x)) at =/-1) +
| - 1|
2(1 -)3
2 f(a))
8
(f(e)) - f(a/-1)
L
|| xا-1ll
L
|
1-3
2(1 - B)
1.3
s f(() 1- (f(x)) - -((+-11) + 2(1 B32
|| -2/-211 11?
1 1--1((1)
B B (0t_1) + 2(1 B)2 || - -x/-21 1
L8
<
(53)
where the inequality (a) dues to the fact that (((-11 S S(x)) + (V
+
L 1 Then we have
B[((=)) - M 1
LB
(1/ S 1 1-3
Ao
3
(54)
2(1 2113333
2(1
3)
Let A. = T-8 2 -1-
Aa
8G
Finally, applying (52) and (54), the bounded assumption on (x.((a))---)
and o/ S L/L, we have
rG2)
(
E[W |
S W
+
(1 B
+
A +
L2
of T
)
|
L
+ m
r(1 B) B) +
G²
2(1 3)2
(
(1
---++)= [ 2 + B.
= W + Ai
(55)
1/
where A =
8Ag 1-3 + A,
+
rC
L and A L3, Bi = r(11 - B) + マーー
Ag 1-3 + 2(1-3YI
BG
The bandwidth step-size highly rises the difficulty of the analysis for momentum, especially when the step-size has an increase between the stages, i.c. 1-1 == ná < r/. Before giving the results, we consider two situations:
nb > off We can apply Lemma 4.1 from i = 1 to S,. Recalling the definition of W 1+1 we have W W $ then
[[(a))]] (E[W])- - B[W(+1)) +A (
+ G2
(56)
7/9. %
1=1
Otherwise if vá I nf. the results of Lemma 4.1 only hold from = 2 to S.. Then
E B|| (E[W)- E[W]] + E[W E(W + E {((+))
1 TS.
1/1
1 m/
B2 St T
A
(57)
For the bandwidth step-size, the initial step-size of stage t, v/ is possibly larger than the ending step-size of the previous stage, 1/6- Thus, we can not use the simpler condition (56), but have to rely on (57) in our derivations below.
22

---

Under review as a conference paper at ICLR 2022
Lemma C.3. Suppose the same setting Lemma 4.1, we have
C1 N
N
( Es
1
W +
+ +(N+1) mŌ(N))(N +1)
Co
A
1
+ C2 _
1
+ B.
m ==1
0(t)
8(t)
[=1
where E. = E1 S,5(t)-1, C. - + 20o), C = A + A +
A
C2 = Co + A2G and
A1, B1, and A. are defined in Lemma 4.1.
Proof.
Applying the result of Lemma 4.1 from i = 2 to S,, the step-size n7! E [mm(t), Mt), and
W = WW we have
St
Ei =|| (B[WS) - B[W + B[wi]- - 1(W + BI vf{+\)
1
1
+ A1
+ Mss 1))(())
(58)
T/s. m/
Recalling the output of Algorithm 2, we have
9,
E|| |
Σ
5(1)
Σ
E
(59)
ΣM S,5(1)
Then we divide 5(1) into the both side of (58), apply (58) from t = 1 to N and let Σs = ΣM S,8(t)-1
BIIV |[]))(())))))
S
1
E[
- E[1
+ EEW - E(W
A
N
1
1
8(t)
8(t)
7/5.
t=1
1
BIGHMT)
(60)
Σ3
8(1)
B||
s(=s)) o(()
First, we estimate Σ/= (43) and (44), we have
From Lemma C.2, let i = 1, then incorporating the inequalities
m1i3 ) ||a| - ==81 - El| z 1|91 2 (1) ||]
- (1- V/
+ (vi) ) 331 - B) |uull - 2n - 3) (s(x1) - (+((())))))
Then dividing (1 3)3 to the both side and applying the fact that || x/11 = (16)) |uff
E|llg[1 < G2 and Ei[l of 12= S G² for any i, t. f(a))
f S Ao and r/f 2 mm((), we have
B ||] G2 (
8
Do S A² + (1 - B)mo(t)
An
+ (1 B)
(61)
2(1 3)2
where Ag = (1+ 2(-
Then
N
Elll E 1
N
A²G
Do
N
<
+
(62)
5(1)
8(t)
(1
3 3)m
(²(()
Next we turn estimate ΣN -W o())
Recalling the definition of W W we have W > 0.
Applying the inequalities (52), (54) and the assumption that s(x!) - f < Ao for any i, we have
Blf(z{) f*] TBll - = 11 + 2r - s"]
B - E[W < E[W
A
G2
mt(() +r +200
(63)
23

---

Under review as a conference paper at ICLR 2022
dividing 8(t and applying (63) from t = 1 to N, we have
B B[Wil
6(t)
m
N
s(t)2
+r
r
G
I
+
2
Σ
N
5(1)
1
(64)
Then we consider
E Wi] - 1
B[i
E[
1
+
B[
8(t)
0(t)
8t + 1)
61(t + 1)
8(t)
1=1
W1
+
N
1
1
B[W/+]].
(65)
81
81
61(1+1)
8(1)
Recalling the definition of E[
E[W [1 ["]
r
1
1+1
20
1+1
2
+
+2rr[f(x(+)) 3- ff",
G/S.
T/S,
and applying the assumption that [xf((x)) -f Do and E[f(2t)
f*] S Ag. and 1+1 1/S..
El|aat+ 1191 = (n's,) BBll 1| S (n's, we have
A rnj. G2 + 2r (a)
A
G² T.
E[W+*|
25o
(66)
Tss
(t)
where (a) follows from v/s, > ml( and n/s, S 1/L. Applying (66) into (65), we have
r 1 + +240)
E B
1
W1
A
1
1
+
5(1)
8(1)
5(N +1)
m
5(t + 1)ō(()
3(1)2
1=1
r
(f + +24o)
W1
A
1
8(1)
5(N +1)
m
5(t + 1)0(t) 8(t)o(t - 1)
( + -00
W 8(1)
A.
+ 5(N + +1)
(67)
mo(N)6(N +1)'
where the second inequality follows that 8(t) is decreasing, so 5(t) I 5(t - 1), then -1/5(t) <
-1/8(t - 1). Finally, due to that n's, E [mo(t), MM(()), we have
Σ
1
(68)
8(1)
%
(t)
Incorporate the inequalities (62). (64), (67) and (68) into (60), we have
W
r
G +
+200)
A
N
+ A
Σ
Σ9
8(1)
8(N
+1)
MO(N)O(N
+ 1)
mo(t)²
t=1
1
N
G2
N
1
+r
+
200
Σ
+ +BIGMM
Σ9 8
5(t)2
L
8(t)
1=1
1=1
1
Ap
1
Σ
+
(69)
Σ
6(t)
(1
B
m t=1
87(t)
24

---

Under review as a conference paper at ICLR 2022
The above result can be re-written (recall 6(1) 1)
W7 +
+
A
(A1 + +4+ 1-8
Σ
1
Σ8
6(N +1)
mo((N)8(V + +1)
8(t)2
( (1(C
G²
N
+ +220)
+ A22?
Σ
+ BTT
8(t)
1=1
$ Σ3
W1
Co
++ mé
A.
C1
8(t) + +C2
1
Σ 8(t)
1
+ B.GGMMT)
+1N
+1)
m
where Co = -( + 20)) C A + A
and C2 Co A₂G².
Proof. (of Theorem 4.2) In this case, given the total number iteration T 1, the number of stages N 2 1, S. S = [T/N]. 6(1) = 1 1/a"-1 for each 1 S 1. S N, then the boundary function at the
final stage ((N) = 1/a and 6LV + 1) = 1/a"". Applying the specific value of 6(t) and gives
N
N
(70)
8(t)
a-1
1=1
1
2N
(71)
8(1)2
a²
1=1
Then by St [T/N] and (70), we easily get
N
T(a: - 1) N(a 1)
Σ St/((t)
(72)
We then plug the above results into Lemma C.3,
E
f
$ N(a 1)
A Ci(a2N-1 -1
C2(a -1) +
[ + Coa
+BB
T(aN 1)
m(a² 1
a-1
N
N
+ (A. +C1) Na
N
< W1 TaN-I + (aCo + C2)
T + MB
(73)
T
NN-
where Co = r G2 2Du)) C1 A + An 1-33 and C2 Co + A2G², A2 1+ 8 2(1-8)2 and
Wi, A1, B1, A,, and r are defined in Lemma 4.1.
Especially, we consider the number of outer-stage N [llog, T)/2], the stage length S. / log, 77 and the boundary functions 8(1) = 1/a for all E 2 .N.. Let N = [llog, 2)/2]. have
[[][S(>>))) S a I
(aCo + C2) Tn
In a²MB,G In
2 73/2 +
T + 2mlaa VT 2na
2laa
VT
(74)
Therefore, complete the proof.
Proof. (of Theorem 4.3) In this theorem, we consider the boundary functions 5(() = 1/a--1,
and the stage length S, = [S with Sp = vT, then we have the number of stages N
[log, ((a 1)vT + 1)J and 8(N) N-1 Next estimate Σ3 -EN S.8 ( 2 (a
1)2/3/2 + 2(a 1)2. Then applying these results into Lemma C.3, have
W1
Co
Ax
C MB
E {
50
+ mVT
(75)
T3/2
T
mVT
VT
25

---

Under review as a conference paper at ICLR 2022
D SUPPLEMENTARY CONVERGENCE RESULTS
D.1 CONVERGENCE OF SGDM WITH CONSTANT AND 1/v2 BANDWIDTH DECAYING STEP-SIZE
We focus on single stage that N = 1. In this case, we first consider the constant step-size of no/ /T. Recalling the result of Lemma 4.1 and letting r/! = 7o/ /T for each i 2 1, we have
W1 T
B1G n0
Σ E
T
VT
3L where B1 = r(1 () 3) カリ and r 2 -113
Next we turn to analyze the 1/v bandwidth step-size oi E [m/ Vi, M/ Vi (which is also monotonic decreasing). Recalling the result of Lemma 4.1
1 r
E[ [ S W + A
B
(76)
and applying the result from i= to T, we have
T Σ
1 (w: E[W A
(1
(1-1) --1) +
G2G
Σmh
T
T
17 no
Then applying the step-size of E [mm/vi M/MM/V gives
T
W T
A
2MB
Σ
E vi
+ VT
(77)
MVT
Thus, we can achieve an O(IvT) optimal rate for SGDM with 1/v\ bandwidth step-size on nonconvex problems. When M m, then the step-size reduces to n! = m/Vi, we also provide the convergence guarantee for the commonly used 1/vi decaying step-size.
D.2 CONVERGENCE GUARANTEES FOR CYCLICAL STEP-SIZES
In Loshchilov and Hutter (2017), the authors proposed cosine annealing step-size
vf = Virii
(Timax - v/min) (1 + cos(Tour n m/TT))-
(78)
where Minnn and V/ are ranges of the step-size, and Teur accounts for how many epochs since the beginning of the current stage and T, accounts for the current stage length (epoch). At each stage f, the step-size is monotonically decaying within the range Vian and n'aax- In this paper, propose general bandwidth framework for step-size which can cover this situation as long as m)) S vinin and V/ < & If the ranges (M/in M } and the stage length are chosen as for example 1/v/ Theorems A.I and A.2 or step-decay Theorems 3.1 and 3.3, the theoretical convergence of SGD under the cosine annealing step-size is guaranteed by our analysis in Section 3. Moreover, because the cosine annealing is monotonic at each stage, so the convergence of SGD with momentum under the cosine annealing policy is also guaranteed by the analysis of Section 4 as long as the ranges V V/nax are within our bands. the best our knowledge, convergence guarantee for cosine step-size. However, to achieve a near-optimal rate for the general smooth (non-convex) problems, the initial step-size is required to be bounded by (1/vTT) which is obviously impractical when the total number of iteration T' is large (also discussed in related work). In our framework, the cosine step-size is allowed to start from a larger step-size and gradually decay. Besides, our results (e.g.. Theorems 3.3 and 4.3) provide ofate-of-thh-arr convergence guarantees for cosine size-size which remove the log T term of Li et al. (2021).
et al. (2021) 1) provides a
Another interesting example triangular cyclical step-size proposed by Smith (2017), which sets minimum viin and maximum n/axx boundaries and the learning rate eyclically varies (linearly
26

---

Under review as a conference paper at ICLR 2022
increasing then linearly decreasing) in these bounds. In each stage, the step-size is non-monotonic. In their paper, the author also consider a variant which cuts Viiin and Vaax in half after each stage. This is exactly the step-decay boundary we discussed. Our analysis in Section 3 can provide the convergence guarantees for such kinds of step-sizes. However, such cyclical step-size is not monotonic in each stage, so our analysis for SGDM in Section 4 is not suitable for this situation.
E ADDITIONAL DETAILS OF THE EXPERIMENTS ON BANDWIDTH STEP-SIZES
In this section, we provide additional details about the numerical experiments in Section 5.
E.1 How TO DESIGN THE BANDWIDTH STEP-SIZES AND SELECT PARAMETERS
To better understand the bandwidth step-sizes tested in the numerical experiments, we visualize the step-size ry. (y-axis is log(n()) vs the number of epochs in Figure 5. We first consider the popular "step-decay" policy the baseline. During the first stage, the bandwidth step-size follows the lower bound. From the second stage and on, we let the initial step-size in each stage to be equal to the upper bound and the last step-size in the stage to reach the lower bound. Our numerical experience has shown that the best performance is obtained when the initial step-size of each stage is larger than the final step-size of the previous stage, which means that the step-size experiences sudden increase before it decreases again. For the step-decay band, we consider four decay modes: 1/8, 1/ 1/vī, linearly, and according to a cosine function (Loshchilov and Hutter, 2017) and update the step size each epoch. the training size n and sample size per iteration b, then one epoch n/b iterations.
We also adopt the polynomial 1/v2 step-size as the boundary function, named 1 1/Vi-band, and update the step-size every epoch. We add similar perturbation as for the step-decay band, but we do not apply the perturbation per stage. Otherwise, the perturbation too frequent and just increases the variance of the iterates. We tune the frequency of the perturbations (denoted No) to undergo similar number of cycles as the step-decay perturbations. In the first cycle, the bandwidth step-sizes agree with their lower bound, just for step-decay. From the second cycle, we begin add the decreasing perturbations, e.g., 1/Vi, 1 1/i and linearly. As discussed above, these perturbations only adjusted between stages. Several different 1/v2 bandwidth step-sizes are shown in Figure 5.
2e/T-baand with difforent modey
Stop-dacay hand with difieeet modes
Supp-be thst
UP
Epacha
Figure 5:
Bandwidth step-sizes: 1/ 1/Vi-band (left); step-decay- (right)
We perform a grid search for the initial step-size no E [0.01, 0.05, 0.1,0.5, 1,5) of the baseline step- sizes. For step-decay step-size (baseline), we select the decay factor a from {1.5, 2,3, ......., 12) and set the number of stages N = [log, T/2] according to Theorems 3.1 and 4.2. We choose the lower bound parameter m = no to agree with the bascline. The bandwidth s = M/m = al where 0 E {0.5, 0.8, 1, 1.2, 1.3, 1.5, 1.8). If 1, it means that the starting step-size at the current stage is larger than the ending step-size from the previous stage. For the 1/VL-band step-sizes, we choose of (1 + avt) as the baseline and select the best > 0 to make the final step-size reach the interval {0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1}. Morcover, we select the lower bound parameter m 7ou to make sure that the lower bound agrees with the baseline. For the upper bound parameter M. we do a grid search for = M/m E (2,3, 4, 5, 6). The number of perturbation cycles N, for the 1/ //dd- step-sizes is chosen from {1, 2, 3, 4). All the
are selected to work
best according to their performance the test dataset.
27

---

Under review as a conference paper at ICLR 2022
550 (sartbaand) Paott-t
5GP on CIAAR1D-Reneett
SCOM CIPAR10 Sen
305
Training loss
Training lass
270
16-
10
14
130
140
110
100
Spects
Spochs
66. with Isert land en CoNkit--eoseeci
SGB en CIFARID Reshert2a
SCDM on CIFAR 10 RosNetl0
1.0
8:50
0.0
8:40
0.6
0.2
044
3.20
0.55
Epocie
Spacts
ESpcch
Figure 6: The training loss and test loss of I/Vd-baan (left column), step-decay band for SGD (middle column). and step-decay band for SGDM (right column) on CIFARIO
E.2 EXPERIMENTS DETAILS ON CIFARIO 10 AND CIFARIOO DATASETS
In this subsection, we will give the implementation details for the experiments on CIFARIO and CIFARI00. The benchmark datasets CIFARIO and CIFARIO0 (Krizhevsky, 2009) both consist of 60000 colour images (50000 training images and the rest 10000 images for testing). The maximum epochs called for the two datasets is 180 and the batch size is 128. All the experiments datasets are implemented in Python 3.7.4 and run on 2 x Nvidia Tesla V100 SXM2 GPUs with 32GB RAM. All experiments are repeated 5 times to eliminate the effect of the randomness. The performance of different algorithms is evaluated in terms of their loss function value and classification accuracy on the training and test datasets. All the results for training loss, test loss, and test accuracy are reported in Figures 6, 7, and 3.
CIFAR
For CIFAR 10, we train an 18-layer Resident Network model (He et al., 2016) called ResNet-18. We first test the vanlia SGD with weight decay of 0.0005. The initial step-size no = 1 and = 1.41618 for 1/v2 siep (baseline). For 1/Vd-band step-sizes, we set: 2 and N, = 3 for 1 1/Vi mode; s = 3 and No = 3 for 1/i mode; and s = 4 and N₂ = for linear mode. For the step-decay step-size (baseline) and also the bandwidth step-sizes, the initial step-size 1/0- 0.5 and decay factor a = 6. For step-decay band step-sizes, the parameter 0 is 1.3 for the 1/Vi, 1/i and linear modes, and is 1.2 for cosine mode. We also implement the SGD with momentum (SGDM) algorithm, with the momentum parameter of 0.9 and weight decay of 0.0005. For the step-decay step-size, the initial step-size 7/o is 0.05 and the decay factor a is 6. We choose the same initial step-size and decay factor for the step-decay bandwidth step-sizes. The best 0 is 1.3 for the four decay modes.
In a similar way, we also detail our parameter selection for the experiments on CIFAR100. On this data set, we train 28 x 10 wide residual network (WRN-28- 10) (Zagoruyko and Komodakis, 2016). We first implement vanilla SGD with a weight decay of 0.0005. For the baseline of the 1 1/Vi band, we set Noo 0.5 and a 3.65224. For the // /l-band step-sizes we use: 2 and No = 3 for 1/ i/Vi-mode; s = 4 and No 3 for 1/i-mode; band, we choose 7/u = 0.5 and a = 6. The parameter / is set to 1.3 for 1/i mode and 1.2 for the other modes. Then we also apply the step-decay band step-sizes al algorithm, where the momentum parameter is 0.9 and the weight decay parameter is 0.0005. We set the initial step-size no0 0.1 and a for the baseline and other step-decay band step-sizes; 0 = 1.2 for //vi and linear modes; and 0 1.3 for 1 / and cosine modes.
4 and No 2 for linear-mode. For the step-decay
the SGD with momentum (SGDM)
28

---

Under review as a conference paper at ICLR 2022
500 with Lagrbband on CIFARD02 WRN-2-28
SCDM CIPM8-D--ReHHei
50OM on CIFARLOP WRI-28-19
LaV--mode
Training losa
Training Icsa
278
Training BAR
16-4
30-
10
130
120
140
15-
100
142
140
33"
140
16
Epocto
Epache
Epocio
560 with bsartbaad en CIPAR300 WRM-28-00
SGDM on CIFAR ResMee
SCOM on CIFAR100 WRN-28-11 -10
8:0
Jadie
Aérroce
TeAE lAke
3.5
4.0
Epoche
Spacha
Epocch
Figure 7: The training loss and test loss of l/vdtbaand (left column), step-decay band for SGD (middle column).
and step-decay band for SGDM (right column) on CIFARI00
E.3 EXPERIMENTS RESULTS OF THE TOY EXAMPLE ON BANDWIDTH STEP-SIZE
In this subsection, we describe the toy example and also report additional results using other bandwidth step-sizes.
The foss-function is the two-dimensional (x, y E R are the variables) non-convex function: +
f(x,y) ((x + 0.7)* 0.1) (x 0.7)² (v 0.7)² (1y- - 0.7)²+ 0.1)
which has four local minima (denoted by 1 to 4)), one of which is global (4) We execute 10000
algorithm runs with an initial point (-0.9, 0.9). The total number of iterations is set to T 3000. The gradient noise is drawn from the standard normal distribution. The setting of the experiments follows (Shi et al., 2020). The step-sizes we tested in this part are similar to Section E. The difference is that here we update the step-size per iterate instead of per epoch, as we did on the CIFAR datasets. We report the percentage (%) of the final iterate close to each local minima in Table 2. Note that the results for constant (large and small) step-size, step-decay (baseline), and step-decay with linear have already been presented in the introduction of the main document. The large constant step-size is 0.1 and the small constant step-size is 0.05. As we can see, 1/ /i-baad with 1/Vi, 1/i and linear modes more likely to escape the bad local minima and find the global solution than their bascline. Except the result of step-decay with linear (shown in Figure 2 and Table I), we also find that other bandwidth step-sizes achieve good performance and work better than the baseline.
In the toy experiment, we also test the performance of step-decay (baseline) and step-decay with linear on different initial points. We evenly select 100 initial points Zy from the region [-1, 1] x [-1, 1]. At each initial point, we repeat the same process as previous initial point ( (-0.9, 0.9) and do 10000 runs. We record the percentage of final iterate close to global minima 4 at each initial point in Figure 8. The z-axis denotes the distance of the initial point 2o and the global minima x². We can see that compared to its baseline, step-decay with linear is less sensitive to the selection of the initial point and relatively large 0 >> 1 works better if the initial point is far from the global minima.
NNotation: ! denotes the local minima at (-0.7, 0.7): 2 denotes the local minima at (0.7,0.7) O denotes the local minima (-0.7, -0.7); ④ denotes the global minima at (0.7, -077).
29

---

Under review as a conference paper at ICLR 2022
Table The percentage (%) the final iterate close to each local minima
step-size
type
small large
29.61
24.66
25.13
20.60
const
0.12
3,45
3.28
93.15
baseline
54.93
18.65
19.48
6.94
1/vi-mode
10.92
22.25
23.51
42.96
1/ B-nnd
1/i-mode
6.92
21.57
22.63
45.74
lonear-mode
3.75
15,86
16.37
63.97
baseline
0.40
6.89
7.55
85.16
1/Vi-mode
0.09
3.73
4.16
92.02
step-decay-band
1/i-mode
0.09
3.55
3.85
92.51
linear-mode
0.14
2.95
2.99
93.92
cosine-mode
0.18
3.36
3.48
92.98
Different initial points
96%
94%
Percentage (close
92%
90%
#*
88%
baseline
linear with 0 1.5
linear with = 1.3
linear with 0=
0.5
1.0
1.5
2.0
2.5
||xa
1=2
Figure 8: The toy example with different initial points for step-decay (baseline) and step-decay with linear
30


Reviews:
[{"review_id": "xwKyBZIvWTw", "reviewer": "Reviewer_p6jS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem and assumption setup is proper, the convergence derivation is clear and covers multiple variants of bandwidth step size application. \n\nI have a few concerns:\nregarding the theory, \n\n1. the experiments shows that the multistage gradient methods helps avoid the local minima, can you provide any theoretical inspiration for this? \n\nregarding to the experiments\n\n2. why the accuracies saw a sudden increase after 60 epochs for baseline SGD and SGDM in Figure 3? \n\n3. In the toy example, it is difficult for small constant step size to jump out of bad local minima, and large constant step size achieves comparable performance with step-decay methods. Therefore, in the numerical examples for CIFAR, why do you choose the lower bound step size $m\\delta(t)$ as baseline instead of  $M\\delta(t)$. Can you add the experiments for $M\\delta(t)$ to show band-width methods indeed helps exploration even compared with larger step size?\n\n4. can you design numerical experiment to illustrate the convergence rate from previous theorems?", "summary_of_the_paper": "This paper studies the bandwidth based step size optimization mainly from theoretical guarantee and experimental validation is also provided. For step-decay SGD, the paper proves the non-asymptotic convergence and an optimal rate is derived. In the SGDM scenario, an optimal convergence result is provided and beats the result from previous literature. Bandwidth schedules are first tested on a toy example showing its power to avoid local minima, then further experiments of SGDM and SGD are performed on CIFAR dataset and achieve a better final accuracy compared with baseline.", "summary_of_the_review": "The overall paper is well orgainzed and easy to follow. The theoretical results improves the current convergence rate than previous work. The experiments show the performance of bandwidth SGD. The connection between theorems and experiments could be stronger. Suggest marginally accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "k8w84x05Nv8", "reviewer": "Reviewer_xLQE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The strengths of this paper are: \n-  The authors formalize a class of bandwidth-based step-sizes where the learning rates are allowed to vary in a region, and are specified using some stage length $S_t$ and decreasing function $\\delta(t)$. Hence the step-sizes scheme has a tendency to decrease along the training process.\n- They provide the convergence guarantees for SGD and SGD-M using some choices of step sizes including the step-decay and other cyclical step-sizes. Their results matches the best convergence rate in literature, under some standard assumptions (Lipschitz smooth, bounded gradients and/or variance) and an additional condition. \n- They experiment these methods for neural network training tasks on the CIFAR10 and CIFAR100 datasets.\n\nThe weaknesses of this paper are: \n- The main weakness is that the authors use an additional assumption that restricts the expectation of the term $[f(x_1^t) - f_*]$ for every $t\\geq 1$. This assumption is not standard and is stronger than the previous ones in literature, because it basically assumes that the algorithm can not behave too bad along the training process, when $t \\geq 1$. Given the fact that the step-sizes scheme is a \"perturbed\" version of the diminishing learning rate, I see that this perturbation is the main reason behind this additional assumption, and therefore I think it can not be removed easily. \n- The bandwidth-based step-sizes in Algorithm 1 requires a lot of parameters to tune, and it takes effort to understand what kinds of learning rate scheme fall into the scope of this paper. To my surprise, $\\delta(t)$ cannot be a constant. In all theorems, we need $\\delta(t) = 1/ \\alpha^{t-1}$ where $\\alpha$ is strictly greater than 1. The stage lengths are also chosen using some particular choices, which further restricts the setting of this paper. \n- For these reasons, and since the bandwidth step size framework is introduced before, the results of this paper are not quite new. Using an additional (strong) assumption, the authors design some step-sizes schemes that are related to existing practice. Hence it is not surprising that these schemes achieve the same rate of convergence as the $\\mathcal{O}(1/\\sqrt{T})$ learning rate in the previous work. \n\nOther comments: \n- The stage lengths and number of stages should be integers. I think the authors might want to modify the results using floor and/or ceiling notations.\n- The experiment does not really tell which step-sizes scheme is dominant, and since they all require more parameters to tune, it is not surprising that they usually give better results than the constant step-sizes. And since the theoretical results does not address the generalization performance of our algorithms, it might be more reasonable to report the training loss in the classification examples.\n\nSome references might be added: \n- Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence - [Loizou et al., 2020].\n- A Unified Convergence Analysis for Shuffling-Type Gradient Methods - [Nguyen et al, 2020].\n", "summary_of_the_paper": "This paper investigates a general class of step-sizes for stochastic gradient algorithms. The step-sizes are chosen based on some boundary function $\\delta(t)$ where $\\delta(t)$ decays exponentially fast throughout the stages. Then the step-sizes are bounded between two bandwidth $m \\delta(t)$ and $M \\delta(t)$ where $m < M$. The bandwidth-based scheme allows some flexibilities in the choice of learning rates, although the theoretical results are restricted to some settings where every hyperparameter is carefully chosen. The authors provide the theoretical results for these settings for stochastic gradient descent (SGD) and for momentum version (SGD-M), and show that these schemes attain the standard rate of convergence for this nonconvex stochastic problem. They show the numerical results for these step-sizes using a toy example and classification example for CIFAR dataset. \n", "summary_of_the_review": "The authors make some improvements over the existing literature for SGD and SGD-M algorithms, using a class of bandwidth-based step-sizes that is specified by stage lengths. The main weakness of this paper is the bounded assumption on the expected output of the problem. \n\nSince this assumption is quite strong, it is not quite comparable with the existing works for SGD without this condition. The novel aspect of this paper is also moderate. For these reasons, I recommend rejection. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SCfrRhBZkmL", "reviewer": "Reviewer_ij2i", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The theoretical analysis, particularly, the analysis for momentum SGD seems to be novel. I have not looked into the literature but non-monotone learning rate seems to be not well-understood previously.\n\n\nCondition (1) is the basic setup of the stepsize policy. While it is related to many cyclic stepsizes, this assumption appears to be too general,  and is not exactly equivalent to the cyclic schedule such as (Loschilov and Hutter 2017, Smith 2017). Can the author elaborate any possible difference?\n\n\nThe author argues (in conclusion) that \"our results provide theoretical guarantees for several popular cyclic stepsizes (Loshchilov, Smith) as long as **they are tuned to lie with in our bands?**\" Can the author explain this more clearly?\n\nIn the remark after Lemma 4.1 the author claims the paper uses $\\beta$ irrelevant to the stepsize, and highlight that this is different from Mai and Johnason 2020, Liu et al 2020. However, this is wrong. haven't Mai and Liu both use arbitrary beta in [0,1)?\n\nIn the toy example in 5.2, do you need to consider cyclic stepsize alternate between \"large\" and \"small\"?\n\nIn the experiments, what is m and M? Is this choice consistent with those in the literature?\n\nSince the paper discuss cyclic stepsize, can you also compare with those standard cyclic stepsize in the literature, not the stagewise stepsize? \n\n", "summary_of_the_paper": "The paper proposes a unified framework to analyze convergence conclusion of SGD/SGDM with bandwidth step-size including popular \"constant and then drop\" step-size,  cosine step-size and the triangular step-size. Experiments justify the advantage of the proposed bandwidth-based decaying stepsize over standard decaying stepsize. ", "summary_of_the_review": "It occurs to me that the main contribution is some new convergence analysis of SGD(M) with non-monotone stepsize in a multistage setting. The convergence rate of SGDM improves the state-of-the-art result of momentum methods. I could be wrong, however, whether the perturbation is cosine, triangular or any cyclic rule does not really matter, which makes this work less precise in characterizing the real effectiveness of each specific cyclic rule.  \nSince the stepsize is decreasing, the influence of bandwidth is also decreasing, which makes the dynamic of this algorithm quite different from standard bandwidth algorithm, and more close to standard SGD. Although I agree with the author on the technical novelty in handling the non-monotoniticity, it was somewhat misleading given the title only mention Bandwidth stepsize. For these reasons, I think the paper still needs some restructure and improvement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Mpjh_SmzhE8", "reviewer": "Reviewer_wt4Y", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\nThe optimal rates for non-convex stochastic optimization in this paper are novel and significant for the bandwidth step size setting, especially for the case of stage-wise step decay. In particular, the SGD with momentum result with stage-wise step decay is very close to what practitioners use, modulo the fact that the result only holds for a sampled iterate rather than the last iterate, and the use of unbiased gradients which do not apply to the epoch-wise random reshuffled training. Nonetheless, these are known challenges in stochastic non-convex optimization that can be dealt separately, and the optimal rates given in this paper are still good to have. For SGD (without momentum), the fixed stage-length size tradeoff in Theorem A.1 is interesting, well-interpreted, and complemented by Theorem A.2 which is very clean in terms of its constant dependence. Although the bandwidth step size framework has already been introduced in Wang et al., 2021, the results presented in this paper are either new or improving upon existing rates. Overall, the paper is well-organized and easy to follow. \n\n\n**Weaknesses and concerns**\n- Another popular line of non-monotonic step sizes include stochastic line search [Vaswani et al., 2019, Paquette and Scheinberg, 2020], stochastic Polyak step sizes [Loizou et al., 2020] and its derivative [Gower et al., 2021]. As far as I'm aware, these step sizes are all non-monotonic and have upper and lower bounds, which correspond to a \"band\" with $m$ and $M$ given by expressions involving the Lipschitz smoothness constant and other parameters. However, as these step sizes do not have a monotonically decreasing component (like $\\delta(t)=1/\\sqrt{t}$), we must set $\\delta(t)=\\delta$ to be a constant. However, to apply Lemma B.1, we need the step sizes to be de-correlated with the randomness in the current iteration (for equation 13-15 to work, which is not the case for these methods as they use the stochastic gradients to compute the step size. A discussion of whether the analysis in this paper covers these types of \"bandwidth\" non-monotonic step sizes would be helpful.\n- I'm a bit unsure whether the step size given by Curtis et al., 2019 can indeed be applied to the analysis in this paper. In particular, equation (70) on page 25 gives the step size for different sizes of the stochastic gradient norms. This implies that $\\eta^t$ is correlated with the stochastic gradient received at the particular iteration, and we have the same issue as the point above? It would be great if the authors can clarify whether I'm missing something here about the randomness dependence. \n- Toy example as evidence for \"bandwidth schedule helps to avoid bad local minima\": I'm not sure if this toy setup is strong enough to demonstrate what it's meant to show. It is unconvincing to me why the step size alone should allow the final iterates to concentrate around the global minimum rather than local minima. It would be helpful to see what happens with different initializations (rather than just 10000 runs from a single initial point). Additionally, the theory requires sampling the iterates, but here the final iterates are taken? \n- For the deep learning experiments, plots for the training loss (or the gradient norms) can be included as well. This would help demonstrate how close the training loss approximates the test loss. \n- The significance of the newly introduced schedules are mainly a combination of decreasing step size and existing cosine/linear rules, and it's hard to tell whether they are significantly better.  \n\n**References mentioned**\n- [Curtis et al., 2019] A stochastic trust region algorithm based on careful step normalization\n- [Vaswani et al., 2019] Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates\n- [Paquette and Scheinberg, 2020] A stochastic line search method with expected complexity analysis\n- [Loizou et al., 2020] Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence\n- [Gower et al., 2021] Stochastic Polyak Stepsize with a Moving Target\n- [Wang et al., 2021] On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size\n\n**Clarifications and other comments**\n1. In Section 1.2 you mentioned that in this paper, you \"choose a similar sampling rule as Wang et al. 2021\", which is essentially sampling iterates inversely proportional to the step size used at that iteration. Does this approach imply you need to store all the iterates? My guess is not, as long as the step size sequence does not depend on other quantities generated during the course of training, we can pre-compute it and sample (with a decoupled seed) prior to training, which can be halted pre-maturely at the sampled iterate. Is the latter approach I described typically how you would employ such sampling?\n\n\n**Typos and minor issues**\n- Section 1.1 second bullet point: \"this is the first results that provide\" --> \"these are the first results that provide\"\n- Page 4, Section 3.1\n\t- Should $N$ and $S_t$ have a ceiling in their respective expressions?\n\t- \"namely Algorithm 1 with $N=(\\log_\\alpha T)/2 \\,(\\alpha>1)$ outer loops\" --> \"namely Algorithm 1 with $N=(\\log_\\alpha T)/2$ outer loops, where $(\\alpha>1)$\" \n\t- \"each with a constant length of with $S_t$\" --> \"each with a constant stage length of $S_t$\"\n- Page 5: two lines above Remark 3.4: \"which allows to benefit from\" --> \"which allows us to benefit from\"\n- Page 6, below equation (5): \"an iterate relationship on the form\" --> \"an iterate relationship of the form\" \n- Page 7, second paragraph: \n\t- missing closing parenthesis after \"(see (8)\"\n\t- \"upto\" --> \"up to\"\n\t- \"allow to\" --> \"allows us to\"\n- Page 8: Section 5.3: Reference for CIFAR10 and CIFAR100 (Kri) should be (Krizhevsky et al. 2012)?\n- Page 16: between Eq 27 and 28: \"Before given the proofs\" --> \"Before giving the proofs\"  (and on page 20)\n", "summary_of_the_paper": "This paper presents a general framework for analyzing SGD with a bandwidth-based step size. This step size scheme uses a monotonically decreasing boundary function along with upper and lower bound constants to cover several non-monotonic step sizes strategies, including epoch-wise step decay, cosine annealing and triangular step sizes that are commonly adopted in training deep neural networks. They provide near-optimal convergence guarantees for smooth, non-convex functions when the boundary function is $1/\\sqrt{t}$, where $t$ can be thought of as the epoch counter. The analysis works by dividing the total number of iterations into stages, where the stage length can either be constant or increasing exponentially. By appropriately selecting the number of stages and the stage length, they obtained optimal rate for the stage-wise step decay scheme. Furthermore, near-optimal and optimal rates are also provided for SGD with heavy-ball momentum under the bandwidth step size assumption that covers the stage-wise step decay setting. Lastly, they proposed non-monotonic step size schedules (step-decay with linear/cosine perturbation) and compared their empirical performance on several deep learning benchmarks.", "summary_of_the_review": "Although the bandwidth step size has been previously introduced, the theoretical results presented in this paper are interesting and novel. Additional discussions to some relevant works mentioned above should be included. The empirical contribution is somewhat weaker, but overall I am leaning towards accepting the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have the following remain concerns:
1. The bounded function value assumption is strong. Note that the previous works for SGD and SGD-M for other LR schemes do not necessarily need this assumption, hence it may be unfair to compare with existing results and say that this work has improvements for non-monotonic schemes. The authors also agree that it is not easy to prove and remove this assumption. 
2. The novelty is limited, and the contributions are somewhat incremental. The bandwidth step size scheme was already introduced in a previous work with a very similar setting. The convergence rate for the proposed LR scheme is the same as previous works for other schemes (or only better by a logarithmic term), which makes the results incremental. 
3. Some of the claims are not well supported. For example, the reviewers comment that it is not clear how the proposed bandwidth step size can help to escape local minima. Although the authors aim to show this empirically, the toy setting is not strong enough to conclude the superior performance of the proposed scheme.

We encourage the authors to improve their paper and resubmit to another venue. Here are the related suggestions:
1. The authors might try to investigate and provide a rigorous proof of how the non-monotonic step size can help to escape local minima. It also helps to characterize the effectiveness of each cyclic rule (cosine/ triangular or any other) and make clear what property (cosine/linear rules or bandwidth or non-monotonicity) contributes most in the good performance of a LR scheme.
2. It is better if the assumption on the bounded function value can be removed. In addition, a theoretical/empirical analysis on the generalization performance of the proposed scheme might also be helpful.
Decision: Reject