On the Convergence of Step Decay Step-Size for Stochastic Optimization
Authors: Xiaoyu Wang
Sindri Magnússon
Mikael Johansson
Venue: NeurIPS 2021 Poster (2021)
Keywords: Stochastic gradient descent
step-decay step-size
non-asymptotic convergence
machine learning

Abstract: The convergence of stochastic gradient descent is highly dependent on the step-size, especially on non-convex problems such as neural network training. Step decay step-size schedules (constant and then cut) are widely used in practice because of their excellent convergence and generalization qualities, but their theoretical properties are not yet well understood. We provide convergence results for step decay in the non-convex regime, ensuring that the gradient norm vanishes at an $\mathcal{O}(\ln T/\sqrt{T})$ rate. We also provide near-optimal (and sometimes provably tight) convergence guarantees for general, possibly non-smooth, convex and strongly convex problems. The practical efficiency of the step decay step-size is demonstrated in several large-scale deep neural network training tasks.

On the Convergence of Step Decay Step-Size for Stochastic Optimization
Xiaoyu Wang
Sindri Magnússon
KTH Royal Institute of Technology
Stockholm University
Stockholm, Sweden
Stockholm, Sweden
wangl0@kth.se
sindri manddiinngguussoddvv...uu
Mikael Johansson
KTH Royal Institute of Technology
Stockholm, Sweden
kikaeljakth.
Abstract
The convergence stochastic gradient descent is highly dependent the step-size, especially on non-convex problems such neural network training. Step decay step-size schedules (constant and then cut) are widely used in practice because of their excellent convergence and generalization qualities, but their theoretical properties are not yet well understood. We provide convergence results for step decay in the non-convex regime, ensuring that the gradient norm vanishes at an (In T/vT) rate. We also provide near-optimal (and sometimes provably tight) convergence guarantees for general, possibly non-smooth, convex and strongly con- vex problems. The practical efficiency of the step decay step-size is demonstrated in several large-scale deep neural network training tasks.
Introduction
We focus stochastic programming problems the form min
f(x) = [x xgX
(1)
Here, & is a random variable drawn from some source distribution E over an arbitrary probability space and A' is closed, convex subset of Rd. This problem is often encountered in machine learning applications, such as training deep neural networks. Depending on the specifies of the application, the function can either be non-convex, convex strongly convex; it can be smooth non-smooth; and it may also have additional structure that can be exploited.
Despite the many advances in the field of stochastic programming, the stochastic gradient descent (SGD) method [37, 32] remains important and is arguably still the most popular method for solving (1). The SGD method updates the decision vector æ using the following recursion
Øt+
-
where ÿr is an unbiased estimate the gradient (or subgradient) at x; and Txx is the Fuclidean projection onto X. The step-size parameter (learning-rate) 7). 0 is critical to control the rate which the model learns and to guarantee that the SGD iterates converge to an optimizer of (1), Setting the step-size large will result in iterates which never converge; and setting
small leads to
35th Conference on Neural Information Processing Systems (NcurIPS 2021)

---

slow convergence and may even cause the iterates to get stuck at bad local minima. As long as the iterates do not diverge, large constant step-size promotes fast convergence but only to a (large) neighborhood of the optimal solution. To increase the accuracy, we have to decrease the step-size.
The traditional approach is to decrease the step-size in every iteration, typically as no/t or na/ /tt. Both these step-size schedules have been studied extensively and guarantee non-asymptotic con- vergence of SGD [31, 26, 36, 19, 38, 15]. However, from a practical perspective, these step-size policies often perform poorly, since they begin to decrease too early. For non-convex problems, such as those which arise in training of deep neural networks, the most successful and popular step-size policy in practice is the step decay step-size [25, 21, 22]. This step-size policy starts with relatively large constant step-size and then cuts the step-size by a fixed number (called decay factor) at after a given number of epochs. Not only does this step-size result in a faster initial convergence, but also guarantees that the SGD iterates eventually converge to an exact solution.
The step decay step-size is the default choice in many deep learning libraries, such as TensorFlow [4] and PyTorch [35]; both use a decay rate of 0.1 and user-defined milestones when the step-size is decreased. Although some recent studies attempt to monitor the optimization process to trigger the milestones when certain conditions are met [27, 50], such approaches are difficult to analyze. Another common approach is to simply divide the targeted number of iterations into N intervals of equal length, and trigger a milestone at the end of each such interval. However, the theoretical properties of this simpler step-size policy is also not yet well understood. To make the problem more manageable theoretically, some related step-size policies that let the length of each segment increase linearly [6] or exponentially [19, 8, 49] are analyzed. On the contrary, we consider the more practical case when the horizon T' of the step-decay step-size is divided into several equal parts.
If the number of iterations horizon T is known apriori, reference [11] analyzes step decay step-size with a decay rate of 1/2 applied every T/ log, T iterations and establishes a near-optimal (log, T/T) convergence rate for vanilla SGD least-squares problems. However, to our knowl- edge, there are no convergence guarantees in the literature under more general conditions, e.g. for general strongly-convex, general convex, or non-convex problems. Motivated by this, in this paper, we study the non-asymptotic convergence of SGD with the step decay step-size in more general settings.
1.1 Main Contributions
This work establishes novel convergence guarantees for SGD with the step decay step-size on non- convex, convex and strongly convex optimization problems. We make the following contributions:
We propose non-uniform probability rule P. x 1/1; for selecting the output in the smooth non-convex setting. Based on this rule, we (i) establish a near-optimal O(n T/VT) rate for SGD) with step decay step-size; (ii) improve the results for exponential decay step-size [28]; (iii) remove the In T factor in the best known convergence rate for the 1/ V step-size.
For strongly convex problems, we establish the following error bounds for the last iterate under step-decay: (i) (In T/TT) for smooth problem, which we also prove to be tight; (ii) OIn2 T/T) without the smoothness assumption.
For the general convex case, prove that the step decay step-size at the last iterate can achieve a near-optimal convergence rate (up to a In T factor).
1.2 Related Work
For SGD, the best known bound for the expected error of the T iterate is of O(1v/T) when the objective is convex and smooth [32, 12), and of (1/TT) when the objective is also strongly convex [31, 36). Without any further assumptions, these rates are known to be optimal. If we restrict our attention to diminishing step-sizes, fp- = tp/ the best known error bound for strongly convex and non-smooth problems is of (In T (T) [38], which is also tight [17]. This rate can be improved to O(1/T) by averaging strategies [36, 26, 38] or step decay step-size [19]. For smooth non-convex functions, Reference [12] established an (1/v/T) rate for SGD with a constant step-size
? (1/VT)) Recently, this error bound has proven to be tight up to a constant, unless additional assumptions are made [9].

---

Step decay step-sizes were probably first considered for deterministic subgradient methods [14] and [40]. More recently step decay step-size schemes have been employed to improve the convergence rates under various conditions: local growth (convex) [45], Dolyak---6jssiewizz (PI.) condition [49], sharp growth (non-convex) [8]. Most of these references consider proximal algorithms (which add a quadratic term X I1-11" to the original loss function) and, in addition, perform an extra averaging step between stages. In particular, if the function f is j-weakly convex (i.e. f + I1-I1* is convex), is required to be larger than 5/2 [49, 6]. In contrast, we study the performance of step decay step-size for the standard SGD algorithm. Moreover, in [45] the output of each inner-loop is an uniform average. So their complexity reflects the average performance over iterations. But for convex and strongly convex problems, we focus on the final iterate which is the most preferred choice in practice. In fact, most practitioners just use the final iterate.
Reference [6] considers slowly decaying step-sizes, ~ 1/t where is the stage index. In other words, the siep-size is not cut by constant factor between stages we do, but it decays (very) slowly. Compared to [19) and [49], where the inner-loop size S grows exponentially, we use a constant value of S, which is known to work better in practice. In the extreme case when S = step-decay reduces to the exponentially decaying step-size recently studied under the PL condition and general smoothness assumption [28].
number of adaptive step-size selection strategies have been proposed for SGD (e.g. [10, 42, 23, 30, 29]), some of which result in step-decay policies [44, 27, 50]. For example, Reference [27] develops a statistical procedure to automatically determine when the SGD iterates with a constant step-size no longer make progress, and then halve the step-size. Empirically, this automatic scheme is competitive with the best hand-tuned step-decay schedules, but no formal guarantees for this observed behaviour given.
The paper is organized as follows. Notation and basic definitions are introduced in Section 2. In Section 3, we analyze the convergence rates of step decay step-size nonconvex case and propose novel non-uniform sampling rule for the algorithm output. The convergence for general convex and strongly convex functions are investigated in Sections A and 4, respectively. Numerical results of our algorithms are presented and discussed in Section 5. Finally, conclusions are made in Section 6.
2 Preliminaries
In this part, we will give some definitions and notations used throughout the paper.
Definition 1. (1) The stochastic gradient oracle Ô is variance-bounded if for any input vector i,it
returns random vector such that _ Elg] [2r] < v2, (2) Ô is bounded if for any input vector 2 < G2 for some fixed G >>>
â, it returns a random vector 9 such that Elllol
Definition 2. When the function f is differentiable on X, we say that f is L-smooth on X if there exists constant L > such that [[) ff(ii) I L L|I yll. It also implies that f(v) < f(x) + (VI(x), y- - x) + 1 [|==--00 - wll2 for any x, E X. If f not differentiable on X, we say that f is L-smooth with respect to x² if f(x) - f(x*) < 1/2 ||x x= 112 Vx E X, with L > O.
The definition of L-smoothness for non-conver functions has been considered by [36].
Definition 3. The function f is p-strongly convex on X C Rd if f(v) 2 f(x) + (g. x) +
# lly =112, Vx, y E X, 0f(x), with p O.
Definition 4. The function f is convex on X if f(y) 2 f(x) + (g. y - x) for any g E af(xx) and z,y X.
Throughout the paper, we assume the objective function f is bounded below on X' and let f denote its infimum. If ff is strongly convex, x² is the unique minimum point of f and f = fxx)).
Notation: Let [r]] denote the set of [1, 2, ... n)) and || := 1l- without specific mention. We use [r] and [r] to denote the nearest integer to the real number r from below and above. For simplicity of notation, we assume that S, N. (log,, T)2 log,, T and T/ log, T are all integers. The subgradient
of the function ff on is denoted by 0f(*) == {u f(r f(x) + (v, y x) Vy).
3

---

3 Non-asymptotic Convergence for Non-convex Problems
In this section, we provide the first convergence bounds for SGD with step-decay step-sizes on non-convex problems. We also show that our technical approach can be used to improve the best known convergence bounds for both i) standard 1/ /VV. step-sizes and ii) exponential decay step-sizes. Before we proceed, we illustrate the theoretical novelty that allows us to derive these results. Most convergence results for SGD on non-convex problems analyze random iterate drawn from ) with some probability Pt [12, 13, 28]. For example, reference [12] provides the following result.
Proposition 3.1. Suppose that f is L-smooth on Red and the stochastic gradient oracle is variance- bounded by V2. If the step-size пn no/ S 1/L, then
LV (In T+1) S [(x1) S nu (vT +
[[[VS(
(3)
2(vT -1
where êT is randomly chosen from {=e)==1 with probability P. xc TJ--
Since Tn is decreasing, P. x T/t means that initial iterates are given higher weights in the average in Equation (3) than the final iterates. This contradicts the intuition that the iterates become better as the algorithm progresses. Ideally, we should do the opposite, i.e. put high weights on the final iterates and low weights on the initial iterates. This is exactly what we do to obtain convergence bounds for step decay step-size: we use the probability Pa x 1/me instead of Pa x T) [12, 28J or uniformly sampling [8]. This is especially important when the step-sizes decrease exponentially fast, like in step decay and exponential decay step-sizes. For example, suppose that n) x 0.9 and = 100. Then with P. nu we pick the output from the first 10 iteration with 65% probability. On the other hand, with P. x 1 1/th we pick the output from the last 10 iterations with 65% probability; see Figure 1.
There are other averaging or sampling rules which favor the last iterate in similar spirit as we do. References [26] and [16] consider SGD with a 1/t step-size and analyze the increasing weighted average ~ t (r 0) of the iterates. [6, 46] selects random iterate as output with increasing probabilities, ~ t" (r > 0) for stagewise optimization algorithms, but their step-sizes and output probabilities are very different from ours. Especially, for step-decay, their output probabilities are on the form t" (r > 0), while we use a' (a > 1) which increases much quicker with t, hence our sampling rule favours late iterates to much higher degree. Moreover, output distribution is directly related to the step-size, and does not include any new parameters that require aoper-tuning.
In the following three subsections we perform such an analysis to 1) provide convergence bounds for step decay step-size (where no bounds existed before) 2) provide improved convergence rate results for exponential decay step-size, and 3) improve the convergence bound for 1/ /t step-size.
3.1 Convergence Rates under the Step Decay Step-Size
Algorithm I describes the SGD algorithm with step decay step-size and our probability rule for selecting the output. Here, and in the analysis below, N is the number of stages, and is the decay factor by which the step-size is divided at the end of each such stage. In practical deep neural network training, 10 the default and N is typically non-convex problems, we will show that it makes sense to let N depend on the desired number of iterations T and the decay factor a. Specifically, we will derive results for N = (log,, T)/2 (which is typically small number) and show that this choice works well in numerical experiments.
syper-parameter selected by experience. For
Theorem 3.2. Suppose that the non-convex objective function f is L-smooth Rd the stochastic gradient oracle is bouuded by V2, and assume that there exists a constant Ap > 0 such that E[f ff1 I for all t > 1. we Algorithm I with T > 1, 1, N 2 1, no 1/L, and x] E RRd, then
2(a 2(a-1)A4 E B[
No
+ LLLV
(4)
a²n
T(1 T(1-a-N)
N N-
'I [12], P. & (2m, - L ). If n/ is far smaller than 1/4, we have (2m) - -TTE) = 2n. For simplicity, we rewrite the probability Pe x ne show the results.

---

Algorithm SGD with step decay step-size on the non-convex case
1: Input: initial point at, initial step-size y/o, decay factor 1, the number of iterations T, outer-loop size
2: Initialize: inner-loop size S T/N
3: for 1 = 1 N do
4: T/ = -0/aa=1
5: for = 1: do
6:
Query a stochastic gradient oracle at ot to get vector of such that Eigg (z((
7:
21+1 = - end for
8:
9:
21+1 #5$+1
10: end for
11: Return: ir is randomly chosen from all the previous iterations {Λf} with probability P. [S] and t E [N]
1/me where
SE 1/ne
Furthermore, if we assume that N (loga 72/2, then
Ao
In
2V -T
Ell [(+))(
(5)
TJo VT
where A (a ())(aa ana and B = a
The theorem establishes the first convergence guarantee of SGD with step decay step-sizes on non-convex problems. The results in Eq. (4) capture the influence of N (the number of stages) on the convergence rate. For example, if N = 1, then the step-decay schedule reduces to the constant step-size and the convergence bound in Theorem 3.2 matches the known results by setting Me //// VT [12]. For N 1, the error bound becomes more complicated. Increasing N reduces the noise term, but it increases the eтror related to the function value. So there is trade-off between making the two terms in the right hand side of Eq. (4) small.
The convergence rate is optimized by selecting N = (log,, 7)/2, which yields the rate given in Eq. (5). It ensures a (In T/VT) rate towards a stationary point, which is comparable to the results for 1) = O(IVII) step-size in [12] or Proposition 3. However, as illustrated in our experiments in Section 5, step decay step-size converges faster in practice and tends to find stationary points that generalize better. Moreover, in the deterministic case when V = 0, let N = 1, Theorem 3.2 yields the standard O(1TT)) convergence rate result for deterministic gradient descent [33, 5, 13]. Another benefit of Theorem 3.2 is that we can reduce the effect of the very large noise variance / to the convergence bound by setting = 1 + 1/V²2. This is in contrast to Proposition 3.1 and 1/v/ step-sizes, where an increased / results in a worse upper bound.
The main novel difficulty in proofing Theorem 3.2, compared to similar results, appears in that we have the new term Σ | [xf(x; - f ([) to account for. To this end, we require that the expectation of the function value each outer iterate (x, [x]] is uniformly upper bounded. [39], the authors proved that the function values at the iterates of SGD can be controlled by the initial state, provided that the step-size bounded by 1/L. Therefore, it fair to make this assumption as long as the initial state is given. Nevertheless, this assumption (or its stronger version that the objective function is upper bounded) has been widely used (or implied) in optimization [20, 47, 48, 46] and statistic machine learning [43, 7], and it has never been violated in our numerical experiments. We illustrate the details of the proof in the supplementary material.
3.2 A Special Case: Exponentially Decaying Step-Size
An interesting special case occurs when we set S = 1 in the step decay step-size. In this case, the step-size will decay exponentially. 7) no/a". The first convergence rate results for such step sizes, which we will call Exp-Decay, have only recently appeared in the preprint [28]; we compare our work to those results below.
Clearly, for S = 1, the exponential decay factor a > cannot be chosen arbitrarily: if a is too large, then Th will vanish in only a few iterations. To avoid this, we choose similar form of the decaying
5

---

factor as [28] and set = (B/T) 1/7 where 3 E [1, The intuition is that at the final iteration T the step-size is on the order of 1/vT (setting B = O()T)), and thus does not vanish over the T iterations. Note that the special case where = 1, then N = T, the choice for 3 also implied from Theorem 3.2 by setting a² = vT. We are now ready to prove the algorithm's convergence.
Theorem 3.3. Suppose that the non-convex objective function is L-smooth and there exists constant Au > 0 such that E f - f*] & Au for all t z 1, and that the stochastic gradient oracle variance-bounded by V2. If we run Algorithm with T 1, S = 1, 1o S 1/ xt E R.d, and
= (B/T)-1/T) then
no In ))) I
20o
LV
(
1)T
nu
where ir is randomly drawn from yields
{ with probability P.
1/me
In particular, 3 = VT
El-1 1/m
Ao
3V3
hT VT -1
E /]]V)(+T)\
(6)
1J0
Theorem 3.3 establishes the convergence of Exp-Decay stationary point. With B == VT, Exp- Decay yields the rate of OIIn T/ /T), which is comparable the results in [28]. However, in [28], the O(n T/ -Trate is obtained under the (arguably impractical) assumption that the initial step-size No bounded by (LI/VT). This means that the initial step-size 7ju will be small if we plan on running the algorithm for a large number of iterations T. This is in conflict to the original motivation for using exponentially decaying step-sizes, namely to allow for large initial step-sizes which decrease as the algorithm progresses. On the other hand, our results in Theorem 3.3 only require that the initial step-size bounded by L/L, which matches the largest fixed step-sizes that ensure convergence.
Another advantage of Theorem 3.3 is that it uses the output probability P; x 1/πx instead of Pt 7) as in [28]. As discussed in the beginning of the section (and in Figure 1), P. x 1/T]e means that the output is much more likely to be chosen during the final iterates, whereas with Pt t the output more likely to come from the initial iterates. Therefore, Theorem 3.3 better reflects the actual convergence of the algorithm, since in practice it is typically the final iterate that is used as the trained model. We illustrate this better in our experiments in Section 5.
3.3 Improved Convergence for the 1/vi Step-Size
The next theorem demonstrates how the idea of using the output distribution Pt x 1/m instead of Pt x tee can improve standard convergence bounds for 1/Vt step-sizes.
Theorem 3.4. Suppose that the objective function is L-smooth and there exists a constant Ao > O such that Exf(x) - f*1 I Au for all t 2 1, and that the stochastic gradient oracle is variance- bounded by 2 nf no/ /t L/L, then
(3A0
3LV2
1 VT
E {((T)
1/0
where ir is randomly drawn from (x: {x:) with probabilities P.
1/me ET 1/mc"
Theorem 3.4 establishes an O(1/VT) convergence rate of SGD with 1/Vī step-sizes. This improves the best known convergence bounds OIn T/VT) for the algorithm, see Proposition 3.1 or [12).
4 Non-asymptotic Convergence for Strongly Convex Problems
We now investigate the convergence of the step decay step-sizes in the strongly convex case. We allow general convex and closed constraint set X C Rd and possibly non-smooth convex problems. To capture this setting. Algorithm 1 needs to be adjusted by including a projection step and subgradients (see Algorithm/ supplementary material). We also give the convergence for the general convex case (see Appendix A).

---

4.1 Strongly Convex and L-Smooth Functions
We first consider the case when f strongly convex and L-smooth (with respect x*). Theorem 4.1. Assume that the objective function f is p-stroongyy convex on X and the stochastic gradient oracle is bounded by G2. If we consider Algorithm with T > N log,, T, x X, and 1jo < 1/(2,), then have
R
Gm exp
Aa In 2uA3
E 2
101
exp (Aa
(A3mmT)
T
where Ag = a in aaala 1) and R [ 1= Further, if the objective function f is L-smooth with respect to x² then we can bound the objective function as follows
L _ F =-1
- f(x)) -
The theorem provides an (In T/T) theoretical guarantee for the last iterate under step decay step- size.? This bound matches the convergence rate of [11] for strongly convex least squares problems. Therefore, Theorem 4.1 can be considered generalization of the result in [11] to general smooth and strongly convex problems.
From Theorem 4.1, we see that the effect of the initial condition || - x= 112 is forgotten exponentially fast, unlike for 1/t step-sizes (e.g.[31)). For 1/1 step-sizes, the initial learning rate is critical (both in theory and practice) to the convergence rate of SGD [32, 31J. For example, an initial step-size of 770 < 2/p, will lead to a at Pm//2 rate, far from the optimal rate 1/t. For step decay, the initial step-size only affects the constant in front of the theoretical convergence bound and is sensitive to the choice of initial step-size 7Jo < 1/22)). We also observe this property of step-decay step-size in the experiments in Figure 4(b).
Under some step-sizes, e.g. Ttt = 1/t is possible to get an O(/[T) convergence rate for SGD for smooth and strongly convex problems [31, 36, 19]. However, our next result shows that the rate in Theorem 4.1 tight for Algorithm 2.
Theorem 4.2 (Lower Bound). Consider Algorithm 2 with = looo T and x 0. For any T E N and 6 E (0,1), 1), there exists function Fr X + TR, where X [-4,4] that both I-strongly convex and I-smooth such that
Im(1/8) IT fr(x5+1) fr(x*) 9exp(2) Ina T
with probability at least 6, where x² = minsex (x))
The high probability lower bound OIn matches the upper bound in Theorem 4.1. This suggests that the bound in Theorem 4. is actually tight for Algorithm 2 in the smooth strongly-convex case.
4.2 Strongly Convex and Non-Smooth Functions
For general, not necessarily smooth, strongly convex functions have the following result.
Theorem 4.3. Suppose that the objective function f is u-strongly convex on and the stochastic gradient oracle is bounded by G?. If we run Algorithm 2 with T 1, T/log, T, x E X, and Too < 12p),, then we have
RhT
1
{)f(1 f(x")) A4 exp (B4
+ C4 T
+ D4 exp
T-a In
In
T
where A4 = ao0 In o, B, = =4=24A4/(a- - 1), C4 G2naa Da = D G2 a
EA = a4.
The theorem shows that even without the smoothness assumption, can still ensure convergence at the rate (In T/T). We can improve the rate to T/T) with averaging technique, as illustrated next. Moreover, the averaging technique improves the dependence the parameter from 1/u² 1² (see Theorem 4.3) to 1/u.
Note that exp(As/ In I') exp(As/ Iu for all 7'22 and exp(As/ In I') converges as T' goes
7

---

Theorem 4,4. Under the assumptions of Theorem 4.3
ArR
In T
E(((tr) - 5(x")) exp (B4
+
T I 1)
where êT Di=r To Σ /5 Ei 17t, , t max(0, Lloga AgT) loga T) As 2ua/(a 1). Cs a(2 1/(a² 1)) (2 and Ba is as defined in Theorem 4.3.
Numerical Experiments
In this section, we evaluate the practical performance of step decay step-size and compare it against the following popular step-size policies: 1) constant step-size, = 1o: 2) 1/t step-size, 1)t = Po/a² with (3 (3/T)-1/1 1/11 for 3 2 1. In each experiment, we perform a grid search to select the best values for the free parameters rjo dn, 3 as well as for the step decay step-size parameter a. More details about the relationship between the different step-size policies are given in the supplementary material.
/1 + aot): 3) 1/ step-size 1/, = /1 + dg dov 4) Exp-Decay [28], at
5.1 Experiments on MNIST with Neural Networks
Consider the classification task on MNIST database of handwritten digits using a fully-connected 2-layer neural network with 100 hidden nodes (784-100-10) [3]. We first explore the output at the last iterate T, which the output of the algorithm that typically used practice. The theoretical output y (in Theorem 3.2) is drawn from all the previous iterates {x{ with probability P. x 1/m-- To get an insight into the relationship between the last iterate and theoretical output in Theorem 3.2, randomly choose 6000 iterates (10% of the total iterates) with probability P. x 1/m, record their exact training loss and testing loss, and calculate the probabilities (shown in Figure I, middle and right). We see that the theoretical output reach the results of the last iterate with high probability, no matter training loss or testing loss.
In the same way. in order to show the advantages of probability P. 1/1, over P. x Th also implement Step-Decay with probability P. x Y in Figure 1. We can see that the output with probability P. 1/1/ is more concentrated at the last phase and has higher probability, especially, terms of loss, compared to the result of probability Pe x Vt--
The performance of the various step-size schedules is shown in Figure 2. Exp-Decay and Step-Decay perform better than other step-sizes both in loss (training and testing) and testing accuracy. Step- Decay has an advantage over and testing loss.
in the later stages of training where it attains lower training
5.2 Experiments on CIFARIO and CIFAR100
To illustrate the practical implications of the step decay step-size, we perform experiments with deep learning tasks on the CIFAR [1]. We will focus on results for CIFAR 100AR10OTA here, and present complementary results for CIFAR10 in the supplementary material. To eliminate the influence of stochasticity, all experiments are repeated 5 times.
We consider the benchmark experiments for CIFAR 100 on a 100-layer DenseNet [22]. We employ vanilla SGD without dampening and use a weight decay of 0.0005. The optimal step-size and algorithm parameters are selected using a grid search detailed in the supplementary material. The results are shown in Figure 3. We observe that Step-Decay achieves the best results in terms of both testing loss and testing accuracy, and that it is also fast in reaching a competitive solution. Another observation is that as the iterates proceeds in each phase, its testing loss and accuracy is getting worse because its generalization ability is weakened. Therefore, deciding when to stop the iteration or reduce the step-size is important.
Finally, we compare the performance of Exp-Decay and Step-Decay on Nesterov's 's accelerated gradient (NAG) [34, 41] and other adaptive gradient methods, including AdaGrad [10], Adam [23] and Adam W [30]. The results are shown in Table 1. All the parameters involved in step-sizes, algorithms, and models are best-tuned (shown supplementary material). The + shows 95% % confidence intervals of the mean accuracy value over 5 runs. We can that compared to the
8

---

1%%
196-
Pressettrg
60
protsaitty
cm
Beration
62.
Figure 1: Output probability distributions (left); training loss (middle) and testing loss (right)
VL.
Teatiive
Figure 2: Results on MNIST: left training loss; middle testing loss; right testing accuracy
LVT
Secry
115
335
105
41%
120
Figure 3: Results on CIFAR1ON left training loss; middle- testing loss; right testing accuracy
Exp-Decay step-size, Step-Decas can reach higher testing accuracy on Adam, AdamW and NAG. This suggest that the Step-Decay step-size can be extended other methods.
5.3 Experiments on Regularized Logistic Regression
We now turn our attention to how the step-decay step-size and other related step-sizes behave in the strongly convex setting. We consider the regularized logistic regression problem on the binary classification dataset rev1. binarr (n = 20242; = 47236) from LIBSVM [2], where a 0.75 partition is used for training and the rest is for testing.
Figure 4(a) shows how constant step-size has be well-tuned to give good performance: if choose it too small, convergence will be painstakingly slow; if we set too large, iterates will stagnate or even diverge. This effect is also visualized blue Figure 4(b), where only a narrow range of values results in low training loss for the constant step-size. In contrast, the initial step-size of both Exp-Decay and Step-Decay can be selected from a wide range (xx
10a) and still yield good results in the end. In other words, Exp-Decay and Step-Decay are more robust to the choice of initial step-size than the alternatives. more thorough evaluation of all the considered step-sizes on logistic regression can be found in Supplementary D.3.

---

Table 1: Test accuracy on CIFARI00.
CIFAR100-DenseNN
Method
Testing accuracy
AdaGrad
0.6197 1 0.00518 18
Adam Exp-Decay
0.6936
0.00483
Adam Step-Decay
0.7041
0.00971
AdamW + Exp-Decay
0.7165
0.00353
Adam + Step-Decay
0.7335
0.00261
(a) Constant step-size
(b) Initial step-sizes
NAG Exp-Decay
0.7531
0.00606
NAG Step-Decay
0.7568 :: 0.00156
Figure 4: The results on rev rinaryy logistic(Ly))
6
Conclusion
We have provided theoretical guarantees for SGD under the step decay family of step-sizes, widely used deep learning. Our first results established a near-optimal ((nT/vV)) rate for step decay step-sizes in the non-convex setting. A key step in analysis probability distribution P: x 1/rj for selecting the output the algorithm. We showed that this approach allows improve the convergence results for SGD under other step-sizes well, e.g., by removing the In T term in the best known convergence rate for 7/- 1/v2 step-sizes. Moreover, we established near-optimal (compared to the min-max rate) convergence rates for general convex, strongly convex and smooth, and strongly convex and non-smooth problems. We illustrated the superior performance of step-decay step-sizes for training of large-scale deep neural networks. In the experiments, observed that the iterates proceeding in each phase, their generalization abilities are getting worse. Therefore, it will be an interesting to study how to best select the size of inner-loop (instead of constant or exponentially growing) to avoid the loss of generalization.
novel non-uniform
Broader Impact
This is mostly a theoretical work and, therefore, it does have any direct negative societal impacts.
Acknowledgements and Disclosure of Funding
This work was supported partially by the Wallenberg Artificial Intelligence, Autonomous Systems and Software Program (WASP) funded by Knut and Alice Wallenberg Foundation, and the Swedish Research Council under contract 2019-05319 and 2020-03607.
References
[1] The CIFAR data set. https://www. http://wwwww....rotootoo edw/"kriz httl., Accessed: 2021- 01-05.
[2] The LIBSVM data set. sstps://www.csie ntu, http.uutttttttcc.//////ttttttooo datasets/. Accessed: 2021-01-05.
[3] The MNIST data set. http://yamn www...eeemmmmmmmmmmm com/ ccmm/xxb/mmist/////c//em/ Accessed: 2021-01-05.
[4] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. Software available from tensorflow.org, 2015.
[5] Coralia Cartis, Nicholas IM Gould, and Ph Toint. On the complexity of steepest descent, New- ton's s and regularized Newton's 's methods for nonconvex unconstrained optimization problems. SIAM Journal on Optimization, 20(6):2833-2522 2010.
10

---

[6] Zaiyi Chen, Zhuoning Yuan, Jinfeng Yi, Bowen Zhou, Enhong Chen, and Tianbao Yang. Universal stagewise learning for non-convex problems with convergence on averaged solutions. In International Conference on Learning Representations, 2019.
[7] Corinna Cortes, Spencer Greenberg. and Mehryar Mohri. Relative deviation learning bounds and generalization with unbounded loss functions. Annals of Mathematics and Artificial Intelligence, 85(1):45-70, 2019.
[8] Damek Davis, Dmitriy Drusvyatskiy, and Vasileios Charisopoulos, Stochastic algorithms with geometric step decay converge linearly on sharp functions. arXiv:1907.095:: 2019.
[9] Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In International Conference on Machine Learning, pages 2658-2667. PMIR, 2020.
[10] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Reseurch, 12(lul):121-2115) 2011 1.
[11] Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth 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.
[12] Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341 2013.
[13] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1- 2):267-305, 2016.
[14] Jean-Louis Goffin. On convergence rates of subgradient optimization methods. Mathematical Programming, 1329)332--347, 1977.
[15] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In International Conference on Machine Learning, pages 5200-5209, PMLR, 2019.
[16] Zhishuai Guo. Zixuan Wu. Yan Yan, Xiaoyu Wang, and Tianbao Yang. Revisiting sgd with increasingly weighted averaging: Optimization and generalization perspectives. arXiv preprint arXiv:2003.04339 2020.
[17] Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pages 1579-1613. PMLR, 2019.
[18] Nicholas JA Harvey, Christopher Liaw, and Sikander Randhawa. Simple and optimal high- probability bounds for strongly-convex stochastic gradient descent. arXiv:1909.00k3 2019.
[19] Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15(1):2489- 2512, 2014.
[20] Elad Hazan, Kfir Y Levy, and Shai Shalev-Shwartz. Beyond convexity: stochastic quasi-convex optimization. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Systems-Volume Volume 1, pages 1594-1602, 2015.
[21] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
[22] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 4700-4708, 2017.
[23] Diederik P Kingma and Jimmy Lei Ba. ADAM: method for stochastic optimization. In International Conference Learning Representations, 2015.
11

---

[24] Philip Klein and Neal E Young. On the number of iterations for dantzig wolfe optimization and packing-covert coveriing approximation algorithms. SIAM Journal on Computing, 4444):115-1112. 2015.
[25] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, pages 1 1106,1114,20 2012.
[26] Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. A simpler approach to obtaining an (L1/t) convergence rate for the projected stochastic subgradient method. arXiv: 12Xiv:1212.2002 2012.
[27] Hunter langg Lin Xiao, and Pengchuan Zhang. Using statistics to automate stochastic optimiza- tion. In Advances in Neural Information Processing Systems, pages 9540-9550, 2019.
[28] Xiaoyu Li, Zhenxun Zhuang, and Francesco Orabona. A second look exponential and cosine step sizes: Simplicity, adaptivity, and performance. In International Conference on Machine Learning, pages 6553-6564. PMLR, 2021.
[29] Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon 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.
[30] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
[31] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, pages 451-459, 2011.
[32] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574 1609, 2009.
[33] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2004.
[34] Yurii E Nesterov. A method for solving the convex programming problem with convergence rate (11)k)). Dokl, akad. nauk Sssr, 269:543-547, 1983.
[35] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De VeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS 2017 Autodiff Workshop: The Future of Gradient- based Machine Learning Software and Techniques, Long Beach, CA, US,2017 2017.
[36] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In International Conference on Machine Learning, pages 1571-1578, 2012.
[37] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400-407, 1951.
[38] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International Conference on Machine Learning, pages 71-79, 2013.
[39] Bin Shi, Weijie Su, and Michael I Jordan. On learning rates and schrödinger operators. arXiv preprint arXiv:2004.06977, 2020.
[40] Naum Zuselevich Shor.
Minimization methods for non-differentiable functions, volume 3. Springer Science & Business Media, 2012.
[41] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International Conference on Machine Learning, pages 1139-1147. PMLR, 2013.
12

---

[42] Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rosprop, coursera: Neural networks for machine learning. Technical Report, University of Toronto, 2012.
[43] Vladimir Vapnik. Statistical learning theory. Wiley, New York, 1998.
[44] Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. In Advances in Neural Information Processing Systems, 2019.
[45] Yi Xu, Qihang Lin, and Tianbao Yang. Stochastic convex optimization: Faster local growth implies faster global convergence. In International Conference Machine Learning, pages 3821-3838 PMLR, 2017.
[46] Yi Xu, Qi Qi. Qihang Lin, Rong Jin, and Tianbao Yang. Stochastic optimization for DC functions and non-smooth non-convex regularizers with non-asymptotic convergence. In International Conference Machine Learning, pages
PMLR, 2019.
[47] Yi Xu, Zhuoning Yuan, Sen Yang, Rong Jin, and Tianbao Yang. On the convergence of (stochastic) gradient descent with extrapolation for non-convex minimization. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), 2019.
[48] Yi Xu, Shenghuo Zhu, Sen Yang. Chi Zhang, Rong Jin, and Tianbao Yang. Learning with non-convex truncated losses by sgd. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115, pages 701-711. PMLR, 2020.
[49] Zhuoning Yuan, Yan Yan, Rong Jin, and Tianbao Yang. Stagewise training accelerates con- vergence of testing error over SGD. In Advances in Neural Information Processing Systems, volume 32, pages 2608-2618, 2019.
[50] Pengchuan Zhang, Hunter Lang, Qiang Liu, and Lin Xiao. Statistical adaptive stochastic gradient methods. 2059,, 2020.
13


Reviews:
[{"review_id": "yKUbbuRCo7o", "reviewer": "Reviewer_Dkst", "summary": "This paper proved convergence results for SGD with step decay step-size (the step size is decayed by some factor after certain iterations). \n\nIn the smooth non-convex setting, this paper sampled the output from $\\\\{x_t\\\\}$ with probability of $x_t$ being $O(1/\\eta_t).$ Based on this novel approach of sampling the output, the authors \n1. proved the first convergence bound for SGD with step-decay step-sizes on non-convex problems and achieved a $O(\\ln T/\\sqrt{T})$ rate towards a stationary point, which is comparable to the folklore results for $\\eta_t = O(1/\\sqrt{t})$ step-size;\n2. improved the convergence results for exponentially decaying step-size, which allows larger initial step size compared with previous work;\n3. improved the convergence rate from $O(\\ln T/\\sqrt{T})$ to $O(1/\\sqrt{T})$ for the $1/\\sqrt{t}$ step-size.\n\nFor the strongly convex and smooth functions, this paper proved an $O(\\ln T/T)$ convergence rate for the last iteration, which generalized the result of Ge et al. The paper also proved a $O(\\ln^2 T/T)$ convergence rate for the strongly convex and non-smooth functions.\n\nIn the experiments, the authors verified that step-decay step-size scheduling have better performance in training neural networks compared with constant step size or polynomially decaying step-size. ", "questions": "", "limitations": "", "rating": 7, "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": "I think this is a good theory paper that studied the convergence rate of SGD for different class of functions under step decay step-size. There are not many theoretical guarantees for SGD with step decay step-size. I believe this paper is a good step along this direction. \n\nIt's an interesting idea to sample the output from the trajectory with the probability of each point inverse to the step size. This novel sampling scheme allowed the proof of the convergence bounds with step-decay step-sizes and also allowed the improvement of some other results. I think this sampling scheme might be of interests also in other settings, and also might be useful in practice.\n\nSome suggestions:\nSince this is mostly a theory paper, I think it might be good to talk more about the challenges in the proof and also the technical contributions. Currently, the results are well explained, but it's unclear what the novelty of the analysis is and how the proof differs from the previous works. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "wa5RI7drAyc", "reviewer": "Reviewer_AbDY", "summary": "\nThis paper studies theoretical properties and practical efficiencies of a step decay step-size policy for non-convex, convex and deep learning problems. The main contribution is to establish a novel convergence guarantee for a practical step decay step-size scheme of SGD beyond existing results on least-squares problems. \n", "questions": "", "limitations": "", "rating": 7, "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": "\nIt is known that decaying step sizes too fast may result in poor performance in SGD. Step decay step-size policies are hence often used in non-convex optimization such as deep learning problems. They can sometimes achieve a fast convergence towards solutions with a good generalization performance. This papers focuses on a practical step decay step-size policy and two stopping rules (either a random iterate or the last iterate), and analyzed their theoretical properties. The practical performance are then evaluated against popular step-size policies. \n\nThe paper is well-organized and well-written. \nI have a few questions/comments: \n* The first main contribution, such as the removal of ln(T) factor for the 1/sqrt(t) step-size, comes from an important assumption that the objective function is upper bounded, isn’t it? It seems that this assumption is in all the results of non-convex cases, therefore it is better to be mentioned in the introduction, e.g. to make a comparision on such assumptions with related works. \n* In Figure 3, why the method with Step-decay has a loss that is increased over epochs 60-110? \n* Enlarge the legend size in all the figures if possible. They are too small to read. \n* Typo: line 16 can be, line 77 for. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "Wp4kMM_5-4X", "reviewer": "Reviewer_5Mza", "summary": "The authors present a new analysis of SGD with the very popular step decay implemented in all DL framework for instance. They provide convergence guarantee in various setting and show that the classical exponential decay is a very special case of their result, still achieving the state of the art result in this special case. They also provide some lower bound to show tightness of their results and finally propose a new sampling of the iterates that allows to remove some annoying log term in the convergence bound.", "questions": "", "limitations": "", "rating": 7, "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": "\\paragraph{Strengths:}\n\nThe authors provide new convergence result on a very popular setting, used in practice but not studied theoretically. They provide some comprehension on this scheduler and their general bound allows to understand how to choose optimally the length of the plateau.\nMoreover their general analysis is sufficiently tight to be able to recover known results of another scheduler as a special case.\n\n\\paragraph{Weaknesses:}\n\nIn Theorem 4.1, 4.3 and 4.4, the condition \"bounded gradient oracle\" with the strong convexity is very problematic in my humble opinion. Indeed, bounded gradient oracle implies that the (deterministic) gradient of the objective function is bounded as well, while strong convexity implies it is lower bounded by the distance of the iterate to optimum. The 2 conditions combined together implies that the authors assume the iterates to be bounded, which is problematic to me as this is not an assumption on the problem, but on the result itself, excluding some possible scenario.\nA minor weakness is that to reach the sqrt convergence bound, one needs to know in advance the number of iterations.\n\n\\paragraph{Correctness:}\n\nI have not check all the proofs in details, but from what I checked, I have not spotted any mistake.\n\n\\paragraph{Clarity:}\n\nThe claim is clear and results follow. I would still make a couple of very minor suggestions to make some point clearer:\n\n- Definition 4: I m a bit confused by the definition of subgradient. I generally consider the subgradient is precisely the set of vector verifying the inequality provided in Definition. Therefore a convex function is a function which subgradient is non empty in any point. And for non convex function, we need a new definition of the subgradient. For sake of clarity, could the authors add the definition of $\\partial f(x)$ before using it?\n- Theorem 3.2 l.166: it became clear to me after equation 5, that $N = \\log_{\\alpha} T / 2$ actually meant $\\frac{\\log_{\\alpha} T}{2}$, and not $\\log_{\\alpha} \\frac{T}{2}$. In my humble opinion, the lack of parenthesis is confusing. Could the authors either add parenthesis, or use \"frac\" or replace the division by 2 by a sqrt inside the log? I think it would improve clarity here.\n- l.181: I think the authors means that when $V$ gets large, it doesn't slow too much the convergence of the algorithm in the sense we can bound the rate uniformly in $V$. In that sense, I think we can say, the convergence bound inn not affected by very large $V$. However, \"the convergence bound unaffected by the noise variance\" can bring a confusion as a reader can understand that the bound does not depend at all of $V$ and we can derive, in the stochastic setting, the deterministic setting's bound, which I think is not the case here.\n\n\\paragraph{General remarks and suggestions:}\n\n\\begin{itemize}\n- l.16: \"can either be\"\n- l.67: \"smooth with Lipschitz continuous gradient\": isn't repetitive?\n- Algorithm 1: To my point of view, \" inner-loop size S = T/N\" should go after the input line, as $S$ is not an input but some value the method computes from inputs.\n- l.175: there is a typo here, a $T$ is missing into the log\n- l.191-192: the authors propose here to consider $\\alpha = \\left(\\frac{\\beta}{T}\\right)^{-1/T}$ and then $\\beta = O(\\sqrt(T))$. Note that Theorem 3.2 suggests to consider $N$ such that $\\alpha^N = \\sqrt(T)$. In the special case where $S=1$, then $N=T$, this equality suggests the choice of $\\alpha$ to be $alpha = \\sqrt(T)^{1/T}$ which is aligned with l.191-192's choice. I think it would worth adding a word on this. Especially since the authors say that the choice $\\alpha = \\left(\\frac{\\beta}{T}\\right)^{-1/T}$ comes from another paper. I think they should stress they not only make this choice based on another paper, but that it is also a consequence of a very special case of their own Theorem.\n\\end{itemize}\n\n\\paragraph{Conclusion}\n\nI think this paper brings interesting new analysis of some very used technique in practice. In my humble opinion, this type of results is of great importance for the community to understand what makes this scheduler works well and then have insight on how to tune it (choose N or equivalently S, and choose alpha). Even if the proposed tuning depends on inaccessible noise of gradient, or on the final number of iterations, I think those results are interesting and open future work. For instance estimate V to try to set $\\alpha$ without exterior knowledge, or set $N$ independently of $T$ by for instance, changing it online. I would vote the accept the paper. However, in my humble opinion authors should consider either removing theorems using contradictory assumptions or fix them if possible.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think this section does not apply for this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "EceCkjTTT-8", "reviewer": "Reviewer_JpYA", "summary": "This paper investigates the step decay schedule (constant then cut) for SGD. It provides theoretical analyzes of this strategy in strongly-convex, convex, and non-convex settings showing near-optimal results. Empirical experiments illustrate its advantage over other popular optimizers.", "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": "The step decay (constant then cut) strategy is widely used in training deep neural networks. There have been quite a few works dedicated to it, both theoretical and empirical. This paper does a great job in synthesizing the related works, identifying their contributions and limits, and pointing out where this work stands.\n\nThis strategy is of course not novel, nor are the rates they obtained in any setting, but providing the theoretical guarantees for the step decay schedule as proved in this paper for various settings are new. In addition, the sampling scheme of being inversely proportional to $\\eta_t$ is novel and very intuitive in giving weights to last iterates.\n\nSome of my concerns are:\n1. The assumption on the upper-boundedness of $f$ is worrisome, especially when it appears in the bound with the term $f_{max} - f^*$ showing that if it is unbounded then the bound is trivial. If the domain is bounded then this assumption would be more natural but for unbounded domain, this assumption seems too restrictive. Note that other results typically include a term $f(x_1) - f^*$ which is fine as $f(x_1)$ can be manually selected and easily be bounded. Looking at the proofs, however, the term $f_{max} - f^*$ is not just a simple upper-bound of $f(x_1) - f^*$ and the assumption on $f_{max} < \\infty$ is indispensable.\n2. In the paper on exponential step sizes [Li et al., 2020], they also studied the cosine step sizes and showed that it also performs really well and surpasses the exponential step sizes and the step decay in some settings. Also, in their paper, the step decay schedule has the flexibility of using different inner-loop sizes thus should be different from your definition in this paper. Hence, I would like to see a comparison with it.\n3. I see that you answered Yes to Checklist 3.a, but could not find your codes on implementing the algorithm and comparing with other optimizers, apart from download link to datasets you used.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes the step decay schedule (constant and then cut) for nonconvex optimization problems, showing that it can find an approximate first order stationary point in O(ln T/\sqrt{T}) rate. Most reviewers found the result interesting and that it gives a better understanding of the step decay schedule. There are some concerns that should be addressed in the revision: 1. clarifying why the requirement on boundedness of f can be replaced by E[f(x_t) - f(x^*)] and why the latter expectation can be bounded in natural cases; 2. detailed comparisons with previous results acknowledging that similar (or even better) rates were achieved by different algorithms in all the settings.
Decision: Accept (Poster)