On the Convergence of Step Decay Step-Size for Stochastic Optimization
Year: 2021

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 O(lnT/ √ 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.

text: √ 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.

heading: 1 Introduction
text: We focus on stochastic programming problems on the form
min x∈X
f(x) := Eξ∼Ξ[f(x; ξ)]. (1)
Here, ξ is a random variable drawn from some source distribution Ξ over an arbitrary probability space and X is a closed, convex subset of Rd. This problem is often encountered in machine learning applications, such as training of deep neural networks. Depending on the specifics of the application, the function f can either be non-convex, convex or strongly convex; it can be smooth or 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 x using the following recursion
xt+1 = ΠX (xt − ηtĝt) (2)
where ĝt is an unbiased estimate of the gradient (or subgradient) at xt and ΠX is the Euclidean projection onto X . The step-size parameter (learning-rate) ηt > 0 is critical to control the rate at which the model learns and to guarantee that the SGD iterates converge to an optimizer of (1). Setting the step-size too large will result in iterates which never converge; and setting it too small leads to
35th Conference on Neural Information Processing Systems (NeurIPS 2021)
slow convergence and may even cause the iterates to get stuck at bad local minima. As long as the iterates do not diverge, a 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 η0/t or η0/ √ t. Both these step-size schedules have been studied extensively and guarantee a non-asymptotic convergence 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 a 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 it 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 or horizon T is known apriori, reference [11] analyzes a step decay step-size with a decay rate of 1/2 applied every T/ log2 T iterations and establishes a near-optimal O(log2 T/T ) convergence rate for vanilla SGD on least-squares problems. However, to our knowledge, 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.

heading: 1.1 Main Contributions
text: This work establishes novel convergence guarantees for SGD with the step decay step-size on nonconvex, convex and strongly convex optimization problems. We make the following contributions:
• We propose a non-uniform probability rule Pt ∝ 1/ηt for selecting the output in the smooth non-convex setting. Based on this rule, we (i) establish a near-optimal O(lnT/ √ T ) rate for
SGD with step decay step-size; (ii) improve the results for exponential decay step-size [28]; (iii) remove the lnT factor in the best known convergence rate for the 1/ √ t step-size.
• For strongly convex problems, we establish the following error bounds for the last iterate under step-decay: (i) O(lnT/T ) for smooth problem, which we also prove to be tight; (ii) O(ln2 T/T ) without the smoothness assumption.
• For the general convex case, we prove that the step decay step-size at the last iterate can achieve a near-optimal convergence rate (up to a lnT factor).

heading: 1.2 Related Work
text: For SGD, the best known bound for the expected error of the T th iterate is of O(1/ √ T ) when the objective is convex and smooth [32, 12], and of O(1/T ) 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, ηt = η0/t, the best known error bound for strongly convex and non-smooth problems is of O(lnT/T ) [38], which is also tight [17]. This rate can be improved to O(1/T ) by averaging strategies [36, 26, 38] or a step decay step-size [19]. For smooth non-convex functions, Reference [12] established anO(1/ √ T ) rate for SGD with a constant step-size ηt = O(1/ √ T ). 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], Polyak-Lójasiewicz (PL) condition [49], sharp growth (non-convex) [8]. Most of these references consider proximal algorithms (which add a quadratic term λ ‖·‖2 to the original loss function) and, in addition, perform an extra averaging step between stages. In particular, if the function f is µ-weakly convex (i.e. f + µ2 ‖·‖
2 is convex), λ is required to be larger than µ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 t is the stage index. In other words, the step-size is not cut by a constant factor between stages as 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 = 1, step-decay reduces to the exponentially decaying step-size recently studied under the PL condition and a general smoothness assumption [28].
A 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 are 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 on nonconvex case and propose a 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.

heading: 2 Preliminaries
text: In this part, we will give some definitions and notations used throughout the paper.
Definition 1. (1) The stochastic gradient oracle Õ is variance-bounded if for any input vector x̂,it returns a random vector ĝ such that E[‖ĝ − E[ĝ]‖2] ≤ V 2. (2) Õ is bounded if for any input vector x̂, it returns a random vector ĝ such that E[‖ĝ‖2] ≤ G2 for some fixed G > 0.
Definition 2. When the function f is differentiable on X , we say that f is L-smooth on X if there exists a constant L > 0 such that ‖∇f(x)−∇f(y)‖ ≤ L ‖x− y‖. It also implies that f(y) ≤ f(x) + 〈∇f(x), y − x〉+ L2 ‖x− y‖
2 for any x, y ∈ X . If f is not differentiable on X , we say that f is L-smooth with respect to x∗ if f(x)− f(x∗) ≤ L2 ‖x− x ∗‖2 ,∀x ∈ X , with L > 0.
The definition of L-smoothness for non-convex functions has been considered by [36].
Definition 3. The function f is µ-strongly convex on X ⊆ Rd if f(y) ≥ f(x) + 〈g, y − x〉 + µ 2 ‖y − x‖ 2 , ∀x, y ∈ X , g ∈ ∂f(x), with µ > 0.
Definition 4. The function f is convex on X if f(y) ≥ f(x) + 〈g, y − x〉 for any g ∈ ∂f(x) and x, y ∈ X .
Throughout the paper, we assume the objective function f is bounded below on X and let f∗ denote its infimum. If f is strongly convex, x∗ is the unique minimum point of f and f∗ = f(x∗).
Notation: Let [n] denote the set of {1, 2, · · · , n} and ‖·‖ := ‖·‖2 without specific mention. We use brc and dre 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 f on x is denoted by ∂f(x) := {v | f(y) ≥ f(x) + 〈v, y − x〉 ,∀y}.

heading: 3 Non-asymptotic Convergence for Non-convex Problems
text: 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/ √ t 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 a random iterate drawn from {xt}Tt=1 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 Rd and the stochastic gradient oracle is variancebounded by V 2. If the step-size ηt = η0/ √ t ≤ 1/L, then
E[‖∇f(x̂T )‖2] ≤ f(x1)− f∗
η0( √ T − 1)
+ LV 2η0(lnT+1)
2( √ T − 1) , (3)
where x̂T is randomly chosen from {xt}Tt=1 with probability Pt ∝ ηt. 1
Since ηt is decreasing, Pt ∝ η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 Pt ∝ 1/ηt instead of Pt ∝ ηt [12, 28] 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 ηt ∝ 0.9−t and T = 100. Then with Pt ∝ ηt we pick the output from the first 10 iteration with 65% probability. On the other hand, with Pt ∝ 1/ηt 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 a similar spirit as we do. References [26] and [16] consider SGD with a 1/t step-size and analyze the increasing weighted average ∼ tr (r > 0) of the iterates. [6, 46] selects a random iterate as output with increasing probabilities, ∼ tr (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 tr (r > 0), while we use αt (α > 1) which increases much quicker with t, hence our sampling rule favours late iterates to a much higher degree. Moreover, our output distribution is directly related to the step-size, and does not include any new parameters that require hyper-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.

heading: 3.1 Convergence Rates under the Step Decay Step-Size
text: Algorithm 1 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 is the default and N is typically a hyper-parameter selected by experience. For 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 α. Specifically, we will derive results for N = (logα T )/2 (which is typically a small number) and show that this choice works well in numerical experiments.
Theorem 3.2. Suppose that the non-convex objective function f is L-smooth on Rd, the stochastic gradient oracle is variance-bounded by V 2, and assume that there exists a constant ∆0 > 0 such that E[f(xt1)− f∗] ≤ ∆0 for all t ≥ 1. If we run Algorithm 1 with T > 1, α > 1, N ≥ 1, η0 ≤ 1/L, and x11 ∈ Rd, then
E[‖∇f(x̂T )‖2] ≤ 2(α− 1)∆0 α2η0 · Nα N T (1− α−N ) + η0LV 2(α− 1) αN − 1 . (4)
1In [12], Pt ∝ (2ηt − Lη2t ). If ηt is far smaller than 1/L, we have (2ηt − Lη2t ) ≈ 2ηt. For simplicity, we rewrite the probability as Pt ∝ ηt to show the results.
Algorithm 1 SGD with step decay step-size on the non-convex case
1: Input: initial point x11, initial step-size η0, decay factor α > 1, the number of iterations T , outer-loop size N 2: Initialize: inner-loop size S = T/N 3: for t = 1 : N do 4: ηt = η0/αt−1 5: for i = 1 : S do 6: Query a stochastic gradient oracle at xti to get a vector ĝ t i such that E[ĝti ] = ∇f(xti) 7: xti+1 = x t i − ηtĝti 8: end for 9: xt+11 = x t S+1 10: end for 11: Return: x̂T is randomly chosen from all the previous iterations {xti} with probability P ti =
1/ηt S ∑N t=1 1/ηt where i ∈ [S] and t ∈ [N ]
Furthermore, if we assume that N = (logα T )/2, then
E[‖∇f(x̂T )‖2] ≤ A ∆0 η0 · lnT√ T − 1 +B LV 2η0√ T − 1 , (5)
where A = (α− 1)/(α2 lnα) and B = α− 1.
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 ηt = η0/ √ T [12]. For N > 1, the error bound becomes more complicated. Increasing N reduces the noise term, but it increases the error related to the function value. So there is a 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α T )/2, which yields the rate given in Eq. (5). It ensures a O(lnT/ √ T ) rate towards a stationary point, which is comparable to the results for ηt = O(1/ √ t) step-size in [12] or Proposition 3.1. 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(1/T ) 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 V 2 to the convergence bound by setting α = 1 + 1/V 2. This is in contrast to Proposition 3.1 and 1/ √ t step-sizes, where an increased V 2 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 ∑T t=1 E[f(xt) − f(xt+1)]/η2t to account for. To this end, we require that the expectation of the function value at each outer iterate E[f(xt)] is uniformly upper bounded. In [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 is bounded by 1/L. Therefore, it is 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.

heading: 3.2 A Special Case: Exponentially Decaying Step-Size
text: 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, ηt = η0/αt. 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 α > 1 cannot be chosen arbitrarily: if α is too large, then ηt will vanish in only a few iterations. To avoid this, we choose a similar form of the decaying
factor as [28] and set α = (β/T )−1/T , where β ∈ [1, T ). The intuition is that at the final iteration T the step-size is on the order of 1/ √ T (setting β = O( √ T )), and thus does not vanish over the T iterations. Note that in the special case where S = 1, then N = T , the choice for β is also implied from Theorem 3.2 by setting αT = √ T . We are now ready to prove the algorithm’s convergence.
Theorem 3.3. Suppose that the non-convex objective function f is L-smooth and there exists a constant ∆0 > 0 such that E[f(xt)− f∗] ≤ ∆0 for all t ≥ 1, and that the stochastic gradient oracle is variance-bounded by V 2. If we run Algorithm 1 with T > 1, S = 1, η0 ≤ 1/L, x11 ∈ Rd, and α = (β/T )−1/T , then
E[‖∇f(x̂T )‖2] ≤ η0 ln(
T β )
(Tβ − 1)T [ 2∆0 η20 ( T β )2 + LV 2T ] ,
where x̂T is randomly drawn from {xt}Tt=1 with probability Pt = 1/ηt∑T t=1 1/ηt . In particular, β = √ T yields
E[‖∇f(x̂T )‖2] ≤ (
∆0 η0 + LV 2η0 2
) · lnT√
T − 1 . (6)
Theorem 3.3 establishes the convergence of Exp-Decay to a stationary point. With β = √ T , ExpDecay yields the rate of O(lnT/ √ T ), which is comparable to the results in [28]. However, in [28], theO(lnT/ √ T )-rate is obtained under the (arguably impractical) assumption that the initial step-size η0 is bounded by O(1/ √ T ). This means that the initial step-size η0 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 is bounded by 1/L, which matches the largest fixed step-sizes that ensure convergence.
Another advantage of Theorem 3.3 is that it uses the output probability Pt ∝ 1/ηt, instead of Pt ∝ ηt as in [28]. As discussed in the beginning of the section (and in Figure 1), Pt ∝ 1/ηt means that the output is much more likely to be chosen during the final iterates, whereas with Pt ∝ ηt the output is 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/ √ t Step-Size
The next theorem demonstrates how the idea of using the output distribution Pt ∝ 1/ηt instead of Pt ∝ ηt can improve standard convergence bounds for 1/ √ t step-sizes.
Theorem 3.4. Suppose that the objective function is L-smooth and there exists a constant ∆0 > 0 such that E[f(xt) − f∗] ≤ ∆0 for all t ≥ 1, and that the stochastic gradient oracle is variancebounded by V 2. If ηt = η0/ √ t ≤ 1/L, then
E[‖∇f(x̂T )‖2] ≤ (
3∆0 η0 + 3LV 2η0 2
) · 1√
T
where x̂T is randomly drawn from {xt}Tt=1 with probabilities Pt = 1/ηt∑T t=1 1/ηt . Theorem 3.4 establishes an O(1/ √ T ) convergence rate of SGD with 1/ √ t step-sizes. This improves the best known convergence bounds O(lnT/ √ T ) for the algorithm, see Proposition 3.1 or [12].

heading: 4 Non-asymptotic Convergence for Strongly Convex Problems
text: 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 ⊂ 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 2 in 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 is strongly convex and L-smooth (with respect to x∗). Theorem 4.1. Assume that the objective function f is µ-strongly convex on X and the stochastic gradient oracle is bounded by G2. If we consider Algorithm 2 with T > 1, N = logα T , x 1 1 ∈ X , and η0 < 1/(2µ), then we have
E ∥∥xNS+1− x∗∥∥2 ≤ R
exp ( A3 T−1 lnT ) + αη0G2 exp ( A3lnT ) 2µA3 lnT T
where A3 = 2µη0α lnα/(α − 1) and R = ∥∥x11 − x∗∥∥2. Further, if the objective function f is L-smooth with respect to x∗ then we can bound the objective function as follows
E[f(xNS+1)− f(x∗)] ≤ L 2 E ∥∥xNS+1 − x∗∥∥2 .
The theorem provides an O(lnT/T ) theoretical guarantee for the last iterate under step decay stepsize.2 This bound matches the convergence rate of [11] for strongly convex least squares problems. Therefore, Theorem 4.1 can be considered a 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 ‖x11−x?‖2 is forgotten exponentially fast, unlike for 1/t step-sizes (e.g.[31]). For 1/t step-sizes, the initial learning rate is critical (both in theory and practice) to the convergence rate of SGD [32, 31]. For example, an initial step-size of η0 < 2/µ, will lead to a t−µη0/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 not sensitive to the choice of initial step-size η0 < 1/(2µ). We also observe this property of step-decay step-size in the experiments in Figure 4(b).
Under some step-sizes, e.g. ηt = 1/t , it is possible to get an O(1/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 is tight for Algorithm 2. Theorem 4.2 (Lower Bound). Consider Algorithm 2 with S = T/ logα T and x11 = 0. For any T ∈ N+ and δ ∈ (0, 1), there exists a function f̃T : X → R, where X = [−4, 4], that is both 1-strongly convex and 1-smooth such that
f̃T (x N S+1)− f̃T (x∗) ≥
ln(1/δ) 9 exp(2) lnα · lnT T
with probability at least δ, where x∗ = minx∈X f̃T (x).
The high probability lower boundO(lnT/T ) matches the upper bound in Theorem 4.1. This suggests that the bound in Theorem 4.1 is actually tight for Algorithm 2 in the smooth strongly-convex case.

heading: 4.2 Strongly Convex and Non-Smooth Functions
text: For general, not necessarily smooth, strongly convex functions we have the following result. Theorem 4.3. Suppose that the objective function f is µ-strongly convex on X and the stochastic gradient oracle is bounded by G2. If we run Algorithm 2 with T > 1, S = T/ logα T , x 1 1 ∈ X , and η0 < 1/(2µ), then we have
E[f(xNS )− f(x∗)] ≤ R lnT A4 exp ( B4 T−α lnT ) + C4 lnT + 2 T +D4 exp ( E4 lnT ) ln2 T T
where A4 = η0α lnα, B4 = 2µA4/(α− 1), C4 = G2η0α, D4 = G2/(2µ lnαB4), E4 = αB4.
The theorem shows that even without the smoothness assumption, we can still ensure convergence at the rate O(ln2 T/T ). We can improve the rate to O(lnT/T ) with an averaging technique, as illustrated next. Moreover, the averaging technique improves the dependence of the parameter µ from 1/µ2 (see Theorem 4.3) to 1/µ.
2Note that exp(A3/ lnT )≤ exp(A3/ ln 2) for all T≥2 and exp(A3/ lnT ) converges to 1 as T goes to∞.
Theorem 4.4. Under the assumptions of Theorem 4.3
E[f(x̂T )− f(x∗)] ≤ A5R exp ( B4 T lnT − 1 ) + C5 lnT T
where x̂T = ∑N t=t∗ ηt ∑S i=1 x t i/(S ∑N t=t∗ ηt), t
∗ := max{0, blogα(η0αA5T/ logα T )c}, A5 = 2µα/(α− 1), C5 = α(2 + 1/(α2 − 1))G2/(2µ lnα), and B4 is as defined in Theorem 4.3.

heading: 5 Numerical Experiments
text: 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, ηt = η0; 2) 1/t step-size, ηt = η0/(1 + a0t); 3) 1/ √ t step-size ηt = η0/(1 + a0 √ t); 4) Exp-Decay [28], ηt = η0/αt with α = (β/T )−1/T for β ≥ 1. In each experiment, we perform a grid search to select the best values for the free parameters η0, a0, β as well as for the step decay step-size parameter α. More details about the relationship between the different step-size policies are given in the supplementary material.

heading: 5.1 Experiments on MNIST with Neural Networks
text: 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 xT at the last iterate T , which is the output of the algorithm that is typically used in practice. The theoretical output x̂T (in Theorem 3.2) is drawn from all the previous iterates {xti} with probability Pt ∝ 1/ηt. To get an insight into the relationship between the last iterate and theoretical output in Theorem 3.2, we randomly choose 6000 iterates (10% of the total iterates) with probability Pt ∝ 1/ηt, record their exact training loss and testing loss, and calculate the probabilities (shown in Figure 1, middle and right). We can see that the theoretical output can 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 Pt ∝ 1/ηt over Pt ∝ ηt, we also implement Step-Decay with probability Pt ∝ ηt in Figure 1. We can see that the output with probability Pt ∝ 1/ηt is more concentrated at the last phase and has a higher probability, especially, in terms of loss, compared to the result of probability Pt ∝ ηt. 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. StepDecay has an advantage over Exp-Decay in the later stages of training where it attains a lower training and testing loss.

heading: 5.2 Experiments on CIFAR10 and CIFAR100
text: 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 CIFAR100 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 CIFAR100 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 accelerated gradient (NAG) [34, 41] and other adaptive gradient methods, including AdaGrad [10], Adam [23] and AdamW [30]. The results are shown in Table 1. All the parameters involved in step-sizes, algorithms, and models are best-tuned (shown in supplementary material). The ± shows 95% confidence intervals of the mean accuracy value over 5 runs. We can see that compared to the
Exp-Decay step-size, Step-Decay can reach higher testing accuracy on Adam, AdamW and NAG. This suggest that the Step-Decay step-size can be extended to other methods.

heading: 5.3 Experiments on Regularized Logistic Regression
text: 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 rcv1.binary (n = 20242; d = 47236) from LIBSVM [2], where a 0.75 partition is used for training and the rest is for testing.
Figure 4(a) shows how a constant step-size has to be well-tuned to give good performance: if we choose it too small, convergence will be painstakingly slow; if we set it too large, iterates will stagnate or even diverge. This effect is also visualized in blue in Figure 4(b), where only a narrow range of values results in a 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 (≈ 10 − 104) 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. A more thorough evaluation of all the considered step-sizes on logistic regression can be found in Supplementary D.3.
Table 1: Test accuracy on CIFAR100.
Method CIFAR100-DenseNet
Testing accuracy
AdaGrad 0.6197 ± 0.00518 Adam + Exp-Decay 0.6936 ± 0.00483 Adam + Step-Decay 0.7041 ± 0.00971 AdamW + Exp-Decay 0.7165 ± 0.00353 AdamW + Step-Decay 0.7335 ± 0.00261 NAG + Exp-Decay 0.7531 ± 0.00606 NAG + Step-Decay 0.7568 ± 0.00156

heading: 6 Conclusion
text: We have provided theoretical guarantees for SGD under the step decay family of step-sizes, widely used in deep learning. Our first results established a near-optimal O(lnT/ √ T ) rate for step decay step-sizes in the non-convex setting. A key step in our analysis was to use a novel non-uniform probability distribution Pt ∝ 1/ηt for selecting the output of the algorithm. We showed that this approach allows to improve the convergence results for SGD under other step-sizes as well, e.g., by removing the lnT term in the best known convergence rate for ηt = 1/ √ t 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, we observed that as 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 S (instead of constant or exponentially growing) to avoid the loss of generalization.
Broader Impact
This is mostly a theoretical work and, therefore, it does not 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.

Review summaries:
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.

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.

This paper proved convergence results for SGD with step decay step-size (the step size is decayed by some factor after certain iterations).   In 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  1. 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; 2. improved the convergence results for exponentially decaying step-size, which allows larger initial step size compared with previous work; 3. improved the convergence rate from $O(\ln T/\sqrt{T})$ to $O(1/\sqrt{T})$ for the $1/\sqrt{t}$ step-size.  For 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.  In 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.