Title: RETHINKING LEARNING RATE SCHEDULES FOR STOCHASTIC OPTIMIZATION

Abstract: There is a stark disparity between the learning rate schedules used in the practice of large scale machine learning and what are considered admissible learning rate schedules prescribed in the theory of stochastic approximation. Recent results, such as in the 'super-convergence' methods which use oscillating learning rates, serve to emphasize this point even more. One plausible explanation is that non-convex neural network training procedures are better suited to the use of fundamentally different learning rate schedules, such as the "cut the learning rate every constant number of epochs" method (which more closely resembles an exponentially decaying learning rate schedule); note that this widely used schedule is in stark contrast to the polynomial decay schemes prescribed in the stochastic approximation literature, which are indeed shown to be (worst case) optimal for classes of convex optimization problems. The main contribution of this work shows that the picture is far more nuanced, where we do not even need to move to non-convex optimization to show other learning rate schemes can be far more effective. In fact, even for the simple case of stochastic linear regression with a fixed time horizon, the rate achieved by any polynomial decay scheme is suboptimal compared to the statistical minimax rate (by a factor of condition number); in contrast the "cut the learning rate every constant number of epochs" provides an exponential improvement (depending only logarithmically on the condition number) compared to any polynomial decay scheme. Finally, it is important to ask if our theoretical insights are somehow fundamentally tied to quadratic loss minimization (where we have circumvented minimax lower bounds for more general convex optimization problems)? Here, we conjecture that recent results which make the gradient norm small at a near optimal rate, for both convex and non-convex optimization, may also provide more insights into learning rate schedules used in practice.

1. INTRODUCTION:

The recent advances in machine learning and deep learning rely almost exclusively on stochastic optimization methods, primarily SGD and its variants. Here, these large scale stochastic optimization methods are manually (and often painstakingly) tuned to the problem at hand (often with parallelized hyper-parameter searches), where there is, as of yet, no class of "universal methods" which uniformly work well on a wide range of problems with little to no hyper-parameter tuning. This is in stark contrast to non-stochastic numerical optimization methods, where it is not an overstatement to argue that the l-BFGS and non-linear conjugate gradient methods (with no hyper-parameter tuning whatsoever) have provided nearly unbeatable procedures (for a number of decades) on nearly every unconstrained convex and non-convex problem. In the land of stochastic optimization, there are two dominant (and somewhat compatible approaches): those methods which often manually tune learning rate schedules to achieve the best performance (Krizhevsky et al., 2012; Sutskever et al., 2013; Kingma & Ba, 2014; Kidambi et al., 2018) and those methods which rely on various forms of approximate preconditioning (Duchi et al., 2011; Tieleman & Hinton, 2012; Kingma & Ba, 2014) . This works examines the former class of methods, where we seek a more refined understanding of the issues of learning rate scheduling, through both theoretical analysis and empirical studies.

Learning rate schedules for SGD is a rather enigmatic topic since there is a stark disparity between what is considered admissible in theory and what is employed in practice to achieve the best re-sults. Let us elaborate on this distinction more clearly. In theory, a vast majority of works starting with Robbins & Monro (1951) ; Polyak & Juditsky (1992) consider learning rates that have the form of η t = a b+t α for some a, b ≥ 0 and 1/2 < α ≤ 1 -we call these polynomial decay schemes. The key property enjoyed by these polynomial decay schemes is that they are not summable but are square summable. A number of works obtain bounds on the asymptotic convergence rates of such schemes. Note that the focus of these works is to design learning rate schemes that work well for all large values of t. In contrast, practitioners are interested in achieving the best performance given a computational budget or equivalently a fixed time horizon T e.g., 100 passes on training dataset with a batch size of 128.

The corresponding practically best performing learning rate scheme is often one where the step size is cut by a constant factor once every few epochs, or, equivalently, when no progress is made on a validation set (Krizhevsky et al., 2012; He et al., 2016b) (often called a dev set based decay scheme). Such schemes are widely popular to the extent that they are available as schemes in deep learning libraries such as PyTorch1 and several such useful tools of the trade are taught on popular deep learning courses2 . Furthermore, what is (often) puzzling (from a theory perspective) is the emphasis that is laid on "babysitting" the learning rates3 to achieve the best performance. Why do practitioners use constant and cut learning rate schemes while most of the theory work routinely works with polynomial decaying schemes? Of course, implicit to this question is the view that both of these schemes are not equivalent. Indeed if both of these were equivalent, one could parameterize the learning rate as a b+t α and do hyperparameter search over a, b and α. In practice, this simply does not give results comparable to the constant and cut schemes. 4 One potential explanation for this could be that, in the context of neural network training, local minima found by constant and cut schemes are of much better quality than those found by polynomial decay schemes, while for convex problems, polynomial decay schemes are indeed optimal.

The primary contribution of this work is to show that this is simply not the case. We concretely show how minimax optimal theoretical learning rates (i.e. polynomial decay schemes for wide classes of convex optimization problems) may be misleading (and sub-optimal for locally quadratic problems), and the story in practice is more nuanced. There important issues at play with regards to this suboptimality. First, even for the simple case of stochastic linear regression, with a fixed time horizon, the rate achieved by any polynomial decay scheme (i.e., any choice of a, b and α) is suboptimal compared to the statistical minimax rate (i.e., information theoretically best possible rate achievable by any algorithm) by a factor of condition number κ (see Section 3 for definitions), while there exist constant and cut schemes that are suboptimal only by a factor of log κ.

Second, this work shows that a factor of κ suboptimality is unavoidable if we wish to bound the error of each iterate of SGD. In other words, we show that the convergence rate of lim sup of the error, as t → ∞, has to be necessarily suboptimal by a factor of Ω(κ) compared to the statistical minimax rate, for any learning rate sequence (polynomial or not). In fact, at least Ω1/κ fraction of the iterates have this suboptimality. With this result, things become quite clear -all the works in stochastic approximation try to bound the error of each iterate of SGD asymptotically (or lim sup of the error in other words). Since this necessarily has to be suboptimal by a factor of Ω(κ) compared to the statistical minimax rates, the suboptimality of polynomial decay rates is not an issue. However, with a fixed time horizon, there exist learning rate schemes with much better convergence rates, while polynomial decay schemes fail to get better rates in this simpler setting (of known time horizon).

Thirdly, the work shows that, for stochastic linear regression, if we consider lim inf (rather than lim sup) of the error, it is possible to design schemes that are suboptimal by only a factor of log κ compared to the minimax rates. Variants of the constant and cut schemes achieve this guarantee.

In summary, the contributions of this paper are showing how widely used pratical learning rate schedules are, in fact, highly effective even in the convex case. In particular, our theory and empirical results demonstrate this showing that:

• For a fixed time horizon, constant and cut schemes are provably, significantly better than polynomial decay schemes. • There is a fundamental difference between fixed time horizon and infinite time horizon.

• The above difference can be mitigated by considering lim inf of error instead of lim sup.

• In addition to our theoretical contributions, we empirically verify the above claims for neural network training on cifar-10.

Extending results on the performance of constant and cut schemes to more general convex optimization problems, beyond stochastic linear regression, is an important future direction. However, the fact that the suboptimality of polynomial decay schemes even for the simple case of stochastic linear regression, has not been realized after decades of research on stochastic approximation is striking.

In summary, the results of this paper show that, even for stochastic linear regression, the popular in practice, constant and cut learning rate schedules are provably better than polynomial decay schemes popular in theory and that there is a need to rethink learning rate schemes and convergence guarantees for stochastic approximation. Our results also suggest that current approaches to hyperparameter tuning of learning rate schedules might not be right headed and further suggest potential ways of improving them.

Paper organization::

The paper is organized as follows. We review related work in Section 2. Section 3 describes the notation and problem setup. Section 4 presents our results on the suboptimality of both polynomial decay schemes and constant and cut schemes. Section 5 presents results on infinite horizon setting. Section 6 presents experimental results and Section 7 concludes the paper.

2. RELATED WORK:

We will split related work into two parts, one based on theory and the other based on practice.

Related efforts in theory: SGD and the problem of stochastic approximation was introduced in the seminal work of Robbins & Monro (1951) ; this work also elaborates on stepsize schemes that are satisfied by asymptotically convergent stochastic gradient methods: we refer to these schemes as "convergent" stepsize sequences. The (asymptotic) statistical optimality of iterate averaged SGD with larger stepsize schemes of O(1/n α ) with α ∈ (0.5, 1) was proven in the seminal works of Ruppert (1988) ; Polyak & Juditsky (1992) . The notions of convergent learning rate schemes in stochastic approximation literature has been studied in great detail (Ljung et al., 1992; Kushner & Yin, 2003; Bharath & Borkar, 1999; Lai, 2003) . Nearly all of the aforementioned works rely on function value sub-optimality to measure convergence and rely on the notion of asymptotic convergence (i.e. in the limit of the number of updates of SGD tending to infinity) to derive related "convergent stepsize schedules". Along this line of thought, there are several efforts that prove (minimax) optimality of the aforementioned rates (in a worst case sense and not per problem sense) e.g., Nemirovsky & Yudin (1983) ; Raginsky & Rakhlin (2011) ; Agarwal et al. (2012) .

An alternative viewpoint is to consider gradient norm as a means to measure the progress of an algorithm. Along this line of thought are several works including the stochastic process viewpoint considered by Polyak & Juditsky (1992) and more recently, the work of Nesterov (2012) (working with deterministic (exact) gradients). The work of Allen-Zhu (2018) considers questions relating to making the gradient norm small when working with stochastic gradients, and provides an improved rate. We return to this criterion in Section 7.

In terms of oracle models, note that both this paper, as well as other results (Lacoste-Julien et al., 2012; Rakhlin et al., 2012; Bubeck, 2014) , work in an oracle model that assumes bounded variance of stochastic gradients or similar assumptions. There is an alternative oracle model for analyzing SGD as followed in papers includingBach & Moulines (2013); Bach (2014); Jain et al. (2017) which is arguably more reflective of SGD's behavior in practice. For more details, refer to Jain et al. (2017) .

It is an important direction to prove the results of this paper working in the alternative practically more applicable oracle model.

Efforts in practice::

As highlighted in the introduction, practical efforts in stochastic optimization have diverged from the classical theory of stochastic approximation, with several deep learning libraries like pytorch 5 providing unconventional alternatives such as cosine/sawtooth/dev set decay schemes, or even exponentially decaying learning rate schemes. In fact, a natural scheme used in training convolutional neural networks for vision is where the learning rate is cut by a constant factor after a certain number of epochs. Such schemes are essentially discretized variants of exponentially decaying learning rate schedules. We note that there are other learning rate schedules that have been recently proposed such as sgd with warm restarts (Loshchilov & Hutter, 2016) , oscillating learning rates (Smith & Topin, 2017) etc., that are unconventional and have attracted a fair bit of attention. Furthermore, exponential learning rates appear to be considered in more recent NLP papers (see for e.g., Krishnamurthy et al. (2017) ) 6 .

3. PROBLEM SETUP:

Notation: We represent scalars with normal font a, b, L etc., vectors with boldface lowercase characters a, b etc. and matrices with boldface uppercase characters A, B etc. We represent positive semidefinite (PSD) ordering between two matrices using . The symbol represents that the direction of inequality holds for some universal constant.

Our theoretical results focus on the following additive noise stochastic linear regression problem. We present the setup and associated notation in this section. We wish to solve: min

w∈R d f (w) where f (w) def = 1 2 w Hw -w b

for some positive definite matrix H and vector b. 7 We denote the smallest and largest eigenvalues of H by µ > 0 and L > 0. κ def = L µ denotes the condition number of H. We have access to a stochastic gradient oracle which gives us ∇f (w) = ∇f (w) + e, where e is a random vector satisfying 8 E [e] = 0 and E ee = σ 2 H.

Given an initial point w 0 and step size sequence η t , the SGD algorithm proceeds with the update

w t = w t-1 -η t ∇f (w t-1 ) = w t-1 -η t (∇f (w t-1 ) + e t )

, where e t are independent for various t and satisfy the above mean and variance conditions. Let w * def = arg min w∈R d f (w). The suboptimality of a point w is given by f (w) -f (w * ). It is well known that given t accesses to the stochastic gradient oracle above, any algorithm that uses these stochastic gradients and outputs w t has suboptimality that is lower bounded by σ 2 d t . More concretely ( Van der Vaart, 2000) , we have that

lim t→∞ E [f ( w t )] -f (w * ) σ 2 d/t ≥ 1 .

Moreover there exist schemes that achieve this rate of (1 + o(1)) σ 2 d t e.g., constant step size SGD with averaging (Polyak & Juditsky, 1992) . This rate of σ 2 d/t is called the statistical minimax rate.

4. COMPARISON BETWEEN POLYNOMIAL DECAY SCHEMES VS CONSTANT AND CUT SCHEMES:

In this section, we will show that polynomial decay schemes are suboptimal compared to the statistical minimax rate by at least a factor of κ while constant and cut schemes are suboptimal by at most a factor of log κ.

5 see https://pytorch.org/docs/stable/optim.html for a complete list of alternatives 6 Refer to their JSON file https://github.com/allenai/allennlp/blob/master/ training_config/wikitables_parser.jsonnet 7 Any linear least squares 1 2n n i=1 x i w -yi 2 can be written as above with

H def = 1 n i xix i and b def = 1 n i yixi.

8 While this might seem very special, this is indeed a fairly natural scenario. For instance, in stochastic linear regression with independent additive noise, i.e., yt = x t w * + t where t is a random variable independent of xt and E [ t] = 0 and E 2 t = σ 2 , the noise in the gradient has this property. On the other hand, the results in this paper can also be generalized to the setting where E ee = V for some arbitrary matrix V. However, error covariance of σ 2 H significantly simplifies exposition.

4.1. SUBOPTIMALITY OF POLYNOMIAL DECAY SCHEMES:

Our first result shows that there exist problem instances where all polynomial decay schemes i.e., those of the form a b+t α , for any choice of a, b and α are suboptimal by at least a factor of Ω(κ) compared to the statistical minimax rate. Theorem 1. There exists a problem instance such that the initial function value f (w 0 ) ≤ σ 2 d, and for any fixed time T satisfying T ≥ κ 2 , for all a, b ≥ 0 and 0.5 ≤ α ≤ 1, and for the learning rate scheme η t = a b+t α , we have

E [f (w T )] -f (w * ) ≥ κ 32 • σ 2 d T .

4.2. SUBOPTIMALITY OF CONSTANT AND CUT SCHEME:

Our next result shows that there exist constant and cut schemes that achieve statistical minimax rate upto a multiplicative factor of only log κ log 2 T . Theorem 2. For any problem and fixed time horizon T > κ log(κ), there exists a constant and cut learning rate scheme that achieves

E [f (w T )] -f (w * ) ≤ f (w0)-f (w * ) T 3 + 2 log κ • log 2 T • σ 2 d T .

We will now consider an exponential decay scheme (in contrast to polynomial ones from Section 4.1) which is a smoother version of constant and cut scheme. We show that the same result above for constant and cut scheme can also be extended to the exponential decay scheme. Theorem 3. For any problem and fixed horizon T , there exist constants a and b such that learning rate scheme of

η t = b • exp (-at) achieves E [f (w T )] -f (w * ) ≤ f (w0)-f (w * ) T 2-(1/100) + log κ • log T • σ 2 d T .

The above results show that constant and cut as well as exponential decay schemes, that depend on the time horizon, are much better than polynomial decay schemes. Between these, exponential decay schemes are smoother versions of constant and cut schemes, and so one would hope that they might have better performance than constant and cut schemes -we do see a log T difference in our bounds. One unsatisfying aspect of the above results is that the rate behaves as log T T , which is asymptotically worse than the statistical rate of 1 T . It turns out that it is indeed possible to improve the rate to 1 T using a more sophisticated scheme. The main idea is to use constant and polynomial schemes in the beginning and then switch to constant and cut (or exponential decay) scheme later. To the best of our knowledge, these kind of schemes have never been considered in the stochastic optimization literature before. Using this learning rate sequence successively for increasing time horizons would lead to oscillating learning rates. We leave a complete analysis of oscillating learning rates (for moving time horizon) to future work. Theorem 4. Fix κ ≥ 2. For any problem and fixed time horizon T / log T > 5κ, there exists a learning rate scheme that achieves

E [f (w T )] -f (w * ) ≤ f (w0)-f (w * ) T 3 + 50 log 2 κ • σ 2 d T .

5. INFINITE HORIZON SETTING:

In this section we show a fundamental limitation of the SGD algorithm. First we will prove that the SGD algorithm, for any learning rate sequence, needs to query a point with suboptimality more than Ω(κ/ log κ) • σ 2 d/T for infinitely many time steps T . Theorem 5. There exists a universal constant C > 0 such that for any SGD algorithm with η t ≤ 1/2κ for all t9 , we have lim sup

T →∞ E[f (w T )]-f (w * ) (σ 2 d/T ) ≥ κ C log(κ+1) .

Next we will show that in some sense the "fraction" of query points that has value more than τ σ 2 /T is at least Ω(1/τ ) when τ is smaller than the threshold in Theorem 5. Theorem 6. There exists universal constants C 1 , C 2 > 0 such that for any τ ≤ κ CC1 log(κ+1) where C is the constant in Theorem 5, for any SGD algorithm and any number of iteration T > 0 there exists a T ≥ T such that for any T ∈ [T , (1 + 1/C 2 τ )T ] we have

E[f (w T )]-f (w * ) (σ 2 d/ T ) ≥ τ .

Finally, we now show that there are constant and cut or exponentially decaying schemes that achieve the statistical minimax rate up to a factor of log κ log 2 T in the lim inf sense. Model err @50κ err @100κ err @200κ optimized for 50κ 0.00018 9.6 × 10 -5 9.6 × 10 -5 optimized for 100κ 0.00018 9.6 × 10 -5

9.6 × 10 -5 optimized for 200κ 0.00275 0.0007 2.5 × 10 -5

Table 1 : Does the learning rate sequence optimized for a given end time generalize to other end times? Observe how a model optimized to perform for a specific horizon behaves sub-optimally for other time horizons.

Theorem 7. There exists an absolute constant C and a constant and cut learning rate scheme that obtains lim inf T →∞

E[f (w T )]-f (w * ) (σ 2 d log 2 T /T ) ≤ C log κ.

Similar results can be obtained for the exponential decay scheme of Theorems 3 and 4 with moving time horizon. However the resultant learning rates might have oscillatory behavior. This might partly explain the benefits of oscillating learning rates observed in practice (Smith & Topin, 2017).

6. EXPERIMENTAL RESULTS:

We present experimental validation of our claims through controlled synthetic experiments on a twodimensional quadratic objective and on a real world non-convex optimization problem of training a residual network on the cifar-10 dataset, to illustrate the shortcomings of the traditional stochastic approximation perspective (and the advantages of non-convergent exponentially decaying and oscillating learning rate schemes) for a realistic problem encountered in practice. Complete details of experimental setup are given in Appendix D.

6.1. SYNTHETIC EXPERIMENTS: TWO-DIMENSIONAL QUADRATIC OBJECTIVE:

We consider the problem of optimizing a two-dimensional quadratic objective, similar in spirit as what is considered in the theoretical results of this paper. In particular, for a two-dimensional quadratic, we have two eigenvalues, one of magnitude κ and the other being 1. We vary our condition number κ ∈ {50, 100, 200} and use a total of 200κ iterations for optimization. The results expressed in this section are obtained by averaging over two random seeds. The learning rate schemes we search over are:

η t = η 0 1 + b • t (1) η t = η 0 1 + b √ t (2) η t = η 0 • exp (-b • t).

(3) For the schemes detailed above, there are two parameters that need to be searched over: (i) the starting learning rate η 0 and, (ii) the decay factor b. We perform a grid search over both these parameters and choose ones that yield the best possible final error at a given end time (i.e. 200κ). We also make sure to extend the grid should a best performing grid search parameter fall at the edge of the grid so that all presented results lie in the interior of our final grid searched parameters.

We will present results for the following experiments: (i) behavior of the error of the final iterate of the SGD method with the three learning rate schemes (1),(2), and (3) as we vary the condition number, and (ii) how the exponentially decaying learning rate scheme (3) optimized for a shorter time horizon behaves for a longer horizon.

For the variation of the final iterate's excess risk when considered with respect to the condition number (Figure 1 ), we note that polynomially decaying schemes have excess risk that scales linearly with condition number, corroborating Theorem 1. In contrast, exponentially decaying learning rate scheme admits excess risk that nearly appears to be a constant and corroborates Theorem 3. Finally, we note that the learning rate schedule that offers the best possible error in 50κ or 100κ steps does not offer the best error at 200κ steps (Table 1 ). We consider here the task of training a 44-layer deep residual network (He et al., 2016b) with pre-activation blocks (He et al., 2016a ) (dubbed preresnet-44) for classifying images in the cifar-10 dataset. The code for implementing the network employed in this paper can be found here10 . For all the experiments, we use the Nesterov's Accelerated gradient method (Nesterov, 1983) implemented in pytorch11 with a momentum set to 0.9 and batchsize set to 128, total number of training epochs set to 100, 2 regularization set to 0.0005.

Our experiments are based on grid searching for the best learning rate decay scheme on four parametric family of learning rate schemes described above 1,2,3; all gridsearches are performed on a separate validation set (obtained by setting aside one-tenth of the training dataset = 5000 images) and with models trained on the remaining 45000 images. For presenting the final numbers in the plots/tables, we employ the best hyperparameters from the validation stage and train it on the entire 50, 000 images and average results run with 10 different random seeds. The parameters for gridsearches and related details are presented in Appendix D. Furthermore, just as with the synthetic experiments, we always extend the grid so that the best performing grid search parameter lies in the interior of our grid search.

Comparison between different schemes: Figure 2 and Table 2 present a comparison of the performance of the three schemes (1)-(3). They clearly demonstrate that the best exponential scheme outperforms the best polynomial schemes.

Hyperparameter selection using truncated runs: Figure 3 and Tables 3 and 4 present a comparison of the performance of three exponential decay schemes each of which has the best performance at 33, 66 and 100 epochs respectively. The key point to note is that best performing hyperparameters at 33 and 66 epochs are not the best performing at 100 epochs (which is made stark from the perspective of the validation error). This demonstrates that selecting hyper parameters using truncated runs, which has been proposed in some recent efforts such as hyperband (Li et al., 2017) Decay Scheme Train FVal @33 Train FVal @66 Train FVal @100 exp(-t) [optimized for 33 epochs] (eqn 3) 0.098 ± 0.006 0.0086 ± 0.002 0.0062 ± 0.0015 exp(-t) [optimized for 66 epochs] (eqn 3) 0.107 ± 0.012 0.0088 ± 0.0014 0.0061 ± 0.0011 exp(-t) [optimized for 100 epochs] (eqn 3) 0.3 ± 0.06 0.071 ± 0.017 0.0053 ± 0.0016 

7. CONCLUSIONS AND DISCUSSION:

The main contribution of this work shows that the picture of learning rate scheduling is far more nuanced than suggested by prior theoretical results, where we do not even need to move to nonconvex optimization to show other learning rate schemes can be far more effective than the standard polynomially decaying rates considered in theory.

Is quadratic loss minimization special? One may ask if there is something particularly special about why the minimax rates are different for quadratic loss minimization as opposed to more general convex (and non-convex) optimization problems? Ideally, we would hope that our theoretical insights (and improvements) can be formally established in more general cases. Here, an alternative viewpoint is to consider gradient norm as a means to measure the progress of an algorithm. The recent work of Allen-Zhu (2018) shows marked improvements for making the gradient norm small (when working with stochastic gradients) for both convex and non-convex, in comparison to prior results. In particular, for the strongly convex case, Allen-Zhu (2018) provides results which have only a logarithmic dependency on κ, an exponential improvement over what is implied by standard analyses for the gradient norm (Lacoste-Julien et al., 2012; Rakhlin et al., 2012; Bubeck, 2014) ; Allen-Zhu (2018) also provides improvements for the smooth and non-convex cases. Thus, for the case of making the gradient norm small, there does not appear to be a notable discrepancy between the minimax rate of quadratic loss minimization in comparison to more general strongly convex (or smooth) convex optimization problems. Interestingly, the algorithm of Allen-Zhu (2018) provides a recursive regularization procedure that obtains an SGD procedure, where the doubling regularization can be viewed as being analogous to an exponentially decaying learning rate schedule. Further work in this direction may be promising in providing improved algorithms.

A PROOFS OF RESULTS IN SECTION 4.1:

Proof of Theorem 1. The problem instance is simple.

Let H =      κ . . . 1 . . .     

, where the first d 2 diagonal entries are equal to κ and the remaining d 2 diagonal entries are equal to 1 and all the off diagonal entries are equal to zero. Let us denote by v

(i) t def = E w (i) t -(w * ) (i) 2

the variance in the i th direction at time step t. Let the initialization be such that v

(i) 0 = σ 2 /κ for i = 1, 2, ..., d/2 and v (i) 0 = σ 2 for i = d/2 + 1, ..., d.

This means that the variances for all directions with eigenvalue κ remain equal as t progresses and similarly for all directions with eigenvalue 1. We have

v (1) T def = E w (1) T -(w * ) (1) 2 = T j=1 (1 -η j κ) 2 v (1) 0 + κσ 2 T j=1 η 2 j T i=j+1 (1 -η i κ) 2 and v (d) T def = E w (d) T -(w * ) (d) 2 = T j=1 (1 -η j ) 2 v (d) 0 + σ 2 T j=1 η 2 j T i=j+1 (1 -η i ) 2 .

We consider a recursion for v

(i)

t with eigenvalue λ i (1 or κ). By the design of the algorithm, we know v

(i) t+1 = (1 -η t λ i ) 2 v (i) t + λ i σ 2 η 2 t . Let s(η, λ) = λσ 2 η 2

1-(1-ηλ) 2 be the solution to the stationary point equation x = (1 -ηλ) 2 + λσ 2 η 2 . Intuitively if we keep using the same learning rate η, then v (i) t is going to converge to s(η, λ i ). Also note that s(η, λ) ≈ σ 2 η/2 when ηλ 1.

We first prove the following claim showing that eventually the variance in direction i is going to be at least s(η T , λ i ).

Claim 1. Suppose s(η t , λ i ) ≤ v

(i) 0 , then v (i) t ≥ s(η t , λ i ).

Proof. We can rewrite the recursion as

v (i) t+1 -s(η t , λ i ) = (1 -η t λ i ) 2 (v (i) t -s(η t , λ i )).

In this form, it is easy to see that the iteration is a contraction towards s(η t , λ i ). Further, v

(i) t+1 - s(η t , λ i ) and v (i)

t -s(η t , λ i ) have the same sign. In particular, let t 0 be the first time such that s(η t , λ i ) ≤ v (i) 0 (note that η t is monotone and so is s(η t , λ i )), it is easy to see that v

(i) t ≥ v (i) 0 when t ≤ t 0 . Therefore we know v (i) t0 ≥ s(η t0 , λ i ), by the recursion this implies v (i) t0+1 ≥ s(η t0 , λ i ) ≥ s(η t0+1 , λ i ). The claim then follows from a simple induction. If s(η T , λ i ) ≥ v (i)

0 for i = 1 or i = d then the error is at least σ 2 d/2 ≥ κσ 2 d/T and we are done. Therefore we must have s(η T , κ) ≤ v

(1) 0 = σ 2 /κ, and by Claim 1 we know v

(1) T ≥ s(η T , κ) ≥ σ 2 η T /2. The function value is at least E [f (w T )] ≥ d 2 • κv (1) T ≥ dκσ 2 η T 4 .

To make sure E [f (w T )] ≤ dκσ 2 η T 32 we must have η T ≤ 1 8T . Next we will show that when this happens, v

(d)

T must be large so the function value is still large. We will consider two cases, in the first case, b ≥ T

α . Since 1 8T ≥ η T = a b+T α ≥ a 2b , we have a b ≤ 1 4T . Therefore v (d) T ≥ (1 -a b ) 2T v (d) 0 ≥ σ 2 /2, so the function value is at least E [f (w t )] ≥ d 2 v (d) T ≥ dσ 2 4 ≥ κdσ 2

T , and we are done.

In the second case, b < T α . Since 1 8T ≥ η T = a b+T α ≥ a 2T α , we have a ≤ 0.25T α-1 . The sum of learning rates satisfy

T i=1 η i ≤ T i=1 a i α ≤ T i=1 0.25i -1 ≈ 0.25 log T.

Here the second inequality uses the fact that T α-1 i -α ≤ i -1 when i ≤ T . Similarly, we also know

T i=1 η 2 i ≤ T i=1 0.25i -2 ≤ π 2 /24. Using the approximation (1 -η) 2 ≥ exp(-2η -4η 2 ) for η < 1/4, we get v (d) T ≥ exp(-2 T i=1 η i -4 T i=1 η 2 i )v (d) 0 ≥ σ 2 /5 √ T , so the function value is at least E [f (w t )] ≥ d 2 v (d) T ≥ dσ 2 20 √ T ≥ κdσ 2 32T

. This concludes the second case and proves the theorem.

B PROOFS OF RESULTS IN SECTION 4.2:

Proof of Theorem 2. The learning rate scheme is as follows. Divide the total time horizon into log(κ) equal sized phases. In the th phase, the learning rate to be used is log T •log κ 2 •µ•T . Note that the learning rate in the first phase depends on strong convexity and that in the last phase depends on smoothness (since the last phase has = log κ). Recall the variance in the k th coordinate can be upper bounded by

v (k) T def = E w (k) T -(w * ) (1) 2 ≤ T j=1 1 -η j λ (k) 2 v (1) 0 + λ (k) σ 2 T j=1 η 2 j T i=j+1 1 -η i λ (k) 2 ≤ exp   -2 T j=1 η j λ (k)   v (1) 0 + λ (k) σ 2 T j=1 η 2 j exp   -2 T i=j+1 η i λ (k)   .

We will show that for every k, we have

v (k) T ≤ log κ • log T λ (k) T • σ 2 ,

which directly implies the theorem. Now choose any k. Let * denote the number satisfying 2

* •µ ≤ λ (k) < 2 * +1 • µ.

Note that * depends on k but we suppressed the dependence for notational simplicity.

v (k) T ≤ exp   -2 T j=1 η j λ (k)   v (k) 0 + λ (k) σ 2 T j=1 η 2 j exp   -2 T i=j+1 η i λ (k)   ≤ exp -2 log T log κ T • λ (k) • T log κ • 1 2 * µ v (k) 0 + λ (k) σ 2 • T log κ • * -1 =1 η 2 + λ (k) σ 2 η 2 * • 1 1 -exp -η * λ (k) + log κ = * +1 T log κ • log κ log T 2 µT 2 ≤ v (k) 0 T 3 + κσ 2 • log 2 κ log 2 T µT 3 + η * σ 2 + σ 2 • log κ log 2 T T log κ = * +1 1 2 µ ≤ v (k) 0 T 3 + σ 2 • log κ log 2 T T λ (k) + 1 2 * µ ≤ v (k) 0 T 3 + 2 log κ • log 2 T λ (k) T • σ 2 .

This finishes the proof.

Proof of Theorem 3. The learning rate scheme we consider is γ t = γ 0 • c t-1 with γ 0 = log T /(µT e ), T e = T / log κ and c = (1 -1/T e ). Further, just as in previous lemmas, we consider a specific eigen direction λ (k) and write out the progress made along this direction by iteration say, T ≤ T : err

(k) T = T t=1 (1 -γ t λ (k) ) 2 err (k) 0 + (λ (k) ) 2 σ 2 T τ =1 γ 2 τ •   T t=τ +1 (1 -γ t λ (k) ) 2   ≤ exp   -2λ (k) γ 0 T t=1 c t-1   err (k) 0 + (λ (k) ) 2 σ 2 γ 2 0 c 2 T τ =1 c 2τ exp   -2λ (k) γ 0 T t=τ +1 c t-1   = exp - 2λ (k) γ 0 1 -c • (1 -c T ) err (k) 0 + (λ (k) ) 2 σ 2 γ 2 0 c 2 T τ =1 c 2τ exp - 2λ (k) γ 0 1 -c • (c τ -c T ) = exp 2λ (k) γ 0 1 -c • c T •   exp - 2λ (k) γ 0 1 -c err (k) 0 + (λ (k) ) 2 σ 2 γ 2 0 c 2 T τ =1 c 2τ exp - 2λ (k) γ 0 1 -c • (c τ )   Represent c τ = x and 2λ (k) γ 0 /(1 -c) = α.

Substituting necessary values of the quantities, we have α = 2 log T • λ (k) /µ ≥ 2. Now, the second term is upper bounded using the corresponding integral, which is the following:

c T x=c x 2 exp (-αx) ≤ c T 1 x 2 exp (-αx)dx ≤ 1 α • 1 + 2 α + 2 α 2 exp (-α).

Substituting this in the previous bound, we have:

err (k) T ≤ exp -α(1 -c T ) •   err (k) 0 + (λ (k) ) 2 σ 2 γ 2 0 αc 2 • 1 + √ 2 α 2   ≤ exp -α(1 -c T ) • err (k) 0 + 16 (λ (k) ) 2 σ 2 γ 2 0 α ≤ exp -α(1 -c T ) • err (k) 0 + 16 (λ (k) ) 2 σ 2 log T µ 2 T 2 e • 2(λ (k) /µ) = exp -α(1 -c T ) • err (k) 0 + 8 λ (k) σ 2 log T µT 2 e

Now, setting T = T e log(Cλ (k) /µ), and using 1 -a ≤ exp (-a), with C > 1 being some (large) universal constant, we have:

err (k) T ≤ exp -2(λ (k) /µ) log T • (1 - µ Cλ (k) ) • err (k) 0 + 8 λ (k) σ 2 log T µT 2 e ≤ 1 T 2-(1/C) • err (k) 0 + 8 λ (k) σ 2 log T µT 2 e (4)

Now, in order to argue the progress of the algorithm from T + 1 to T , we can literally view the algorithm as starting with the iterate obtained from running for the first T steps (thus satisfying the excess risk guarantee in equation 4) and then adding in variance by running for the duration of time between T + 1 to T . For this part, we basically upper bound this behavior by first assuming that there is no contraction of the bias and then consider the variance introduced by running the algorithm from T + 1 to T . This can be written as:

err (k) T ≤ T t= T +1 (1 -γ t λ (k) ) 2 err (k) T + (λ (k) ) 2 σ 2 T -T τ =1 γ 2 τ + T T -T t=τ +1 (1 -γ t+ T λ (k) ) 2 ≤ err (k) T + (λ (k) ) 2 σ 2 T -T τ =1 γ 2 τ + T T -T t=τ +1 (1 -γ t+ T λ (k) ) 2

Now, to consider bounding the variance of the process with decreasing sequence of learning rates, we will instead work with a constant learning rate and understand its variance:

(λ (k) ) 2 σ 2 T -T τ =1 γ 2 (1 -γλ (k) ) 2(T -T -τ ) ≤ γ 2 σ 2 (λ (k) ) 2 (2 -λ (k) γ)γλ (k) ≤ γσ 2 λ (k) .

What this implies in particular is that the variance is a monotonic function of the learning rate and thus the overall variance can be bounded using the variance of the process run with a learning rate of γ T .

(λ (k) ) 2 σ 2 T -T τ =1 γ 2 τ + T T -T t=τ +1 (1 -γ t+ T λ (k) ) 2 ≤ (λ (k) ) 2 σ 2 T -T t=τ +1 γ 2 T (1 -γ T λ (k) ) 2 ≤ γ T σ 2 λ (k) ≤ log T µT e • µ Cλ (k) • σ 2 λ (k)

≤:

σ 2 log T log κ T Plugging this into equation 4 and summing over all directions, we have the desired result.

Proof of Theorem 4. The learning rate scheme is as follows.

We first break T into three equal sized parts. Let A = T /3 and B = 2T /3. In the first T /3 steps, we use a constant learning rate of 1/L. In the second T /3 steps, we use a polynomial decay learning rate η A+t = 1 µ(κ+t/2) . In the third T /3 steps, we break the steps into log 2 (κ) equal sized phases. In the th phase, the learning rate to be used is 5 log 2 κ 2 •µ•T . Note that the learning rate in the first phase depends on strong convexity and that in the last phase depends on smoothness (since the last phase has = log κ).

Recall the variance in the k th coordinate can be upper bounded by

v (k) T def = E w (k) T -(w * ) (1) 2 ≤ T j=1 1 -η j λ (k) 2 v (1) 0 + λ (k) σ 2 T j=1 η 2 j T i=j+1 1 -η i λ (k) 2 ≤ exp   -2 T j=1 η j λ (k)   v (1) 0 + λ (k) σ 2 T j=1 η 2 j exp   -2 T i=j+1 η i λ (k)   .

We will show that for every k, we have

EQUATION

which directly implies the theorem.

We will consider the first T /3 steps. The guarantee that we will prove for these iterations is: for any

t ≤ A, v (k) t ≤ (1 -λ (k) /L) 2t v (k) 0 + σ 2 L .

This can be proved easily by induction. Clearly this is true when t = 0. Suppose it is true for t -1, let's consider step t. By recursion of v

(k) t we know v (k) t = (1 -λ (k) /L) 2 v (k) t-1 + λ (k) σ 2 /L 2 ≤ (1 -λ (k) /L) 2t v (k) 0 + σ 2 L (1 -λ (k) /L) 2 + λ (k) /L ≤ (1 -λ (k) /L) 2t v (k) 0 + σ 2 L .

Here the second step uses induction hypothesis and the third step uses the fact that (1 -x) 2 + x ≤ 1 when x ∈ [0, 1]. In particular, since (1-λ (k) /L) 2T /3 ≤ (1-1/κ) 2T /3 ≤ (1-1/κ) 3κ log T = 1/T 3 , we know at the end of the first phase, v

(k) A ≤ v (k) 0 /T 3 + σ 2 L .

In the second T /3 steps, the guarantee would be: for any t ≤ T /3, v

A+t ≤ v (k) 0 /T 3 + 2η A+t σ 2 . We will again prove this by induction. The base case (t = 0) follows immediately from the guarantee for the first part. Suppose this is true for A + t -1, let us consider A + t, again by recursion we know

v (k) A+t = (1 -λ (k) η A+t-1 ) 2 v (k) A+t-1 + λ (k) σ 2 η 2 A+t-1 ≤ v (k) 0 /T 3 + 2η A+t-1 σ 2 (1 -λ (k) η A+t-1 ) 2 + 1 2 λ (k) η A+t-1 ≤ v (k) 0 /T 3 + 2η A+t-1 σ 2 (1 - 1 2 µη A+t-1 ) ≤ v (k) 0 /T 3 + 2η A+t σ 2 .

Here the last line uses the fact that 2η A+t-1 (1 -1 2 µη A+t-1 ) ≤ 2η A+t σ 2 , which is easy to verify by our choice of η. Therefore, at the end of the second part, we have v

(k) B ≤ v (k) 0 /T 3 + 2σ 2 µ(κ+T /6

) .

Finally we will analyze the third part. Let T = T /3 log 2 κ, we will consider the variance v (k) B+

T at the end of each phase. We will make the following claim by induction:

Claim 2. Suppose 2 • µ ≤ λ (k) , then v (k) B+ T ≤ v (k) B exp(-3 ) + 2 T η 2 λ (k) σ 2 .

Proof. We will prove this by induction. When = 0, clearly we have v

(k) B ≤ v (k)

B so the claim is true. Suppose the claim is true for -1, we will consider what happens after the algorithm uses η for T steps. By the recursion of the variance we have

v (k) T ≤ v (k) ( -1) T • exp(-2η • λ (k) T ) + T η 2 λ (k) σ 2 .

Since 2 • µ ≤ λ (k) , we know exp(-2η • λ (k) T ) ≤ exp(-3). Therefore by induction hypothesis we have

v (k) B+ T ≤ v (k) B exp(-3 ) + exp(-3) • 2 T η 2 -1 λ (k) + T η 2 λ (k) ≤ v (k) B exp(-3 ) + 2 T η 2 λ (k) .

This finishes the induction.

By Claim 2, Let * denote the number satisfying 2

* • µ ≤ λ (k) < 2 * +1 • µ, by this choice we know µ/λ (k) ≥ 1 2 exp(-3 ) we have v (k) T ≤ v (k) B+ * T ≤ v (k) B exp(-3 * ) + 2 T η 2 * λ (k) σ 2 ≤ v (k) 0 T 3 + 24σ 2 λ (k) T + 50 log 2 κ 3λ (k) T • σ 2 . ≤ v (k) 0 T 3 + 50 log 2 κ λ (k) T • σ 2 .

Therefore, the function value is bounded by

E [f (w T )] = d i=1 λ (k) v (k) T ≤ f (w0) T 3 + 50 log 2 κ T • σ 2 d.

C PROOFS OF RESULTS IN SECTION 5:

All of our counter-examples in this section are going to be the same simple function. Let H be a diagonal matrix with d/2 eigenvalues equal to κ and the other d/2 eigenvalues equal to 1. Intuitively, we will show that in order to have a small error in the first eigendirection (with eigenvalue κ), one need to set a small learning rate η t which would be too small to achieve a small error in the second eigendirection (with eigenvalue 1). As a useful tool, we will decompose the variance in the two directions corresponding to κ eigenvalue and 1 eigenvalue respectively as follows:

EQUATION

Proof of Theorem 5. Fix τ = κ/C log(κ + 1) where C is a universal constant that we choose later. We need to exhibit that the lim sup is larger than τ . For simplicity we will also round κ up to the nearest integer.

Let T be a given number. Our goal is to exhibit a T > T such that flin(w T ) (σ 2 / T ) ≥ τ . Given the step size sequence η t , consider the sequence of numbers

T 0 = T, T 1 , • • • , T κ such that T i is the first number that 1 κ ≤ Ti t=Ti-1+1 η t ≤ 3 κ .

Note that such a number always exists because all the step sizes are at most 2/κ. We will also let ∆ i be T i -T i-1 . Firstly, from ( 6) and ( 7), we see that t η t = ∞. Otherwise, the bias will never decay to zero. If f (w Ti-1+∆i ) > τ σ 2 d Ti-1+∆i for some i = 1, • • • , κ, we are done. If not, we obtain the following relations:

σ 2 ∆ 1 ≤ σ 2 ∆1 t=1 η 2 T0+t ≤ exp(3) κ • E w (1) T0+∆1 -(w * ) (1) 2 ≤ exp(3)f lin (w T0+∆1 ) ≤ exp(3)τ σ 2 T 0 + ∆ 1 ⇒ T 0 ≤ (exp(3)τ -1) ∆ 1 .

Here the second inequality is based on (6). We will use C 1 to denote exp(3). Similarly, we have

σ 2 ∆ 2 ≤ σ 2 ∆2 t=1 η 2 T1+t ≤ C 1 κ E w (1) T1+∆2 -(w * ) (1) 2 ≤ C 1 f lin (w T1+∆2 ) ≤ C 1 τ σ 2 T 1 + ∆ 2 ⇒ T 1 ≤ (C 1 τ -1) ∆ 2 ⇒ T 0 ≤ (C 1 τ -1) 2 C 1 τ ∆ 2 .

Repeating this argument, we can show that

T = T 0 ≤ (C 1 τ -1) i (C 1 τ ) i-1 ∆ i and T i ≤ (C 1 τ -1) j-i (C 1 τ ) j-i-1 ∆ j ∀ i < j.

We will use i = 1 in particular, which specializes to

T 1 ≤ (C 1 τ -1) j-1 (C 1 τ ) j-2 ∆ j ∀ j ≥ 2.

Using the above inequality, we can lower bound the sum of ∆ j as

EQUATION

This means that

E [f (w Ti )] ≥ d 2 • E w (2) Ti -(w * ) (2) 2 ≥ exp(-6)σ 2 d • ∆1 i=1 η 2 T +i ≥ exp(-6)σ 2 d ∆ 1 ≥ exp(-6)σ 2 d T 1 ≥ exp (κ/(C 1 τ ) -3) C 1 τ • σ 2 d κ j=2 ∆ j ,

where we used (8) in the last step. Rearranging, we obtain

E [f (w Tκ )] (σ 2 d/T κ ) ≥ exp (κ/(C 1 τ ) -3) C 1 τ .

If we choose a large enough C (e.g., 3C 1 ), the right hand side is at least exp((C/C1) log(κ+1)-3) κ ≥ κ.

To prove Theorem 6, we rely on the following key lemma, which says if a query point w T is bad (in the sense that it has expected value more than 10τ σ 2 d/T ), then it takes at least Ω(T /τ ) steps to bring the error back down. Lemma 8. There exists universal constants C 1 , C 2 > 0 such that for any τ ≤ κ CC1 log(κ+1) where C is the constant in Theorem 5, suppose at step T , the query point w

EQUATION

T -(w * )

(2) 2

, we know either w

T

EQUATION

T -(w * )

(2) 2

≥ C 1 τ σ 2 /2T . Either way, we have a coordinate i with eigenvalue λ i (κ or 1) such that w

(i) T -(w * ) (i) 2 ≥ C 1 τ σ 2 /(2T λ i ).

Similar as before, choose ∆ to be the first point such that

η T +1 + η T +2 + • • • + η T +∆ ∈ [1/λ i , 3/λ i ].

First, by ( 6) or (7), we know for any

T ≤ T ≤ T + ∆, E w (i) T -(w * ) (i) 2 ≥ exp(-6)C 1 τ σ 2 /(2λ i T )

just by the first term. When we choose C 1 to be large enough the contribution to function value by this direction alone is larger than τ σ 2 /T . Therefore every query in [T, T + ∆] is still bad.

We will consider two cases based on the value of S 2 :=

T +∆ T =T +1 η 2 T . If S 2 ≤ C 2 τ /(λ 2 i T ) (

where C 2 is a large enough universal constant chosen later), then by Cauchy-Schwartz we know

S 2 • ∆ ≥ ( T +∆ T =T +1 η T ) 2 ≥ 1/λ 2 i .

Therefore ∆ ≥ T /C 2 τ , and we are done.

If S 2 > C 2 τ /(λ 2 i T ), by Equation ( 6) and ( 7) we know E w Here the first inequality just uses the second term in Equation ( 6) or ( 7), the second inequality is because

T +∆ j= T +1 η j ≤ T +∆

j=T +1 η j ≤ 3/λ i and the last inequality is just based on the value of S 2 . In this case as we can see as long as C 2 is large enough, T + ∆ is also a point with E [f (w T +∆ )] ≥

λ i E w (i) T +∆ -(w * ) (i) 2

≥ C 1 τ σ 2 /(T + ∆), so we can repeat the argument there. Eventually we either stop because we hit case 1: S 2 ≤ C 2 τ /λ 2 i T or the case 2 S 2 > C 2 τ /λ 2 i T happened more than T /C 2 τ times. In either case we know for any T ∈ [T, (1 + 1/C 2 )T ] E [f (w T )] ≥ τ σ 2 /T ≥ τ σ 2 / T as the lemma claimed.

Theorem 6 is an immediate corollary of Theorem 5 and Lemma 8.

Proof of Theorem 7. This result follows by running the constant and cut scheme for a fixed time horizon T and then increasing the time horizon to κ • T . The learning rate of the initial phase for the new T = κ • T is 1/µT = 1/µ • κT = 1/LT which is the final learning rate for time horizon T . Theorem 2 will then directly imply the current theorem.

D DETAILS OF EXPERIMENTAL SETUP D.1 SYNTHETIC 2-D QUADRATIC EXPERIMENTS:

As mentioned in the main paper, we consider three condition numbers namely κ ∈ {50, 100, 200}. We run all experiments for a total of 200κ iterations. The two eigenvalues of the Hessian are κ and 1 respectively, and noise level is σ 2 = 1 and we average our results with two random seeds. All our grid search results are conducted on a 10 × 10 grid of learning rates × decay factor and whenever a best run lands at the edge of the grid, the grid is extended so that we have the best run in the interior of the gridsearch.

For the O(1/t) learning rate, we search for decay parameter over 10-points logarithmically spaced between {1/(100κ), 3000/κ}. The starting learning rate is searched over 10 points logarithmically spaced between {1/(20κ), 1000/κ}.

For the O(1/ (t)) learning rate, the decay parameter is searched over 10 logarithmically spaced points between {100/κ, 200000.0/κ}. The starting learning rate is searched between {0.01, 2}.

For the exponential learning rate schemes, the decay parameter is searched between {exp (-2/N ), exp (-10 6 /N )}. The learning rate is searched between {1/5000, 1/10}.

D.2 NON-CONVEX EXPERIMENTS ON CIFAR-10 DATASET WITH A 44-LAYER RESIDUAL NET:

As mentioned in the main paper, for all the experiments, we use the Nesterov's Accelerated gradient method (Nesterov, 1983) implemented in pytorch12 with a momentum set to 0.9 and batchsize set to 128, total number of training epochs set to 100, 2 regularization set to 0.0005.

With regards to learning rates, we consider 10-values geometrically spaced as {1, 0.6, • • • , 0.01}. To set the decay factor for any of the schemes such as 1,2, and 3, we use the following rule. Suppose we have a desired learning rate that we wish to use towards the end of the optimization (say, something that is 100 times lower than the starting learning rate, which is a reasonable estimate of what is typically employed in practice), this can be used to obtain a decay factor for the corresponding decay scheme. In our case, we found it advantageous to use an additively spaced grid for the learning rate γ t , i.e., one which is searched over a range {0.0001, 0.0002, • • • , 0.0009, 0.001, • • • , 0.009} at the 80 th epoch, and cap off the minimum possible learning rate to be used to be 0.0001 to ensure that there is progress made by the optimization routine. For any of the experiments that yield the best performing gridsearch parameter that falls at the edge of the grid, we extend the grid to ensure that the finally chosen hyperparameter lies in the interior of the grid. All our gridsearches are run such that we separate a tenth of the training dataset as a validation set and train on the remaining 9/10 th dataset. Once the best grid search parameter is chosen, we train on the entire training dataset and

:

https://pytorch.org/docs/stable/optim.html#torch.optim.lr_scheduler. ReduceLROnPlateau

http://cs231n.github.io/

http://cs231n.github.io/neural-networks-3/

In fact, this work shows an instance where there is a significant (provable) difference between the performance of these two schemes.

Learning rate more than 2/κ will make the algorithm diverge.

https://github.com/D-X-Y/ResNeXt-DenseNet

https://github.com/pytorch

https://github.com/pytorch

Figures and Tables:

Figure 1: Plot of final error versus condition number κ for decay schemes 1,2,3 for the 2-d regression problem.

Figure 2: Plot of the training function value (left) and test 0/1error (right) comparing the three decay schemes (two polynomial) 1, 2, (and one exponential) 3 scheme on the classification problem of cifar-10 with a 44-layer residual net with pre-activation blocks.

Figure 3: Plot of the training function value (left) and test 0/1error (right) comparing the exponential decay scheme (equation 3), with parameters optimized for 33, 66 and 100 epochs on the classification problem of cifar-10 with a 44-layer residual net with pre-activation blocks.

≥ exp(-6) • C 2 τ σ 2 /(λ 2 i T ).

Comparing Train Softmax Function Value and Test 0/1 Error of various learning rate decay schemes for the classification task on cifar-10 using a 44-layer residual net with pre-activations.

Table content: <table><tr><td>, might</td></tr></table>

Comparing Train Softmax Function Value of various learning rate decay schemes for the classification task on cifar-10 using a 44-layer residual net with pre-activations.

Table content: <table><tr><td>Decay Scheme</td><td>Test 0/1 @33</td><td>Test 0/1 @66</td><td>Test 0/1 @100</td></tr><tr><td colspan="3">exp(-t) [optimized for 33 epochs] (eqn 3) 10.36 ± 0.235% 8.6 ± 0.26%</td><td>8.57 ± 0.25%</td></tr><tr><td>exp(-t) [optimized for 66 epochs] (eqn 3)</td><td colspan="3">10.51 ± 0.45% 8.51 ± 0.13% 8.46 ± 0.19%</td></tr><tr><td>exp(-t) [optimized for 100 epochs] (eqn 3)</td><td>14.42 ± 1.47%</td><td>9.8 ± 0.66%</td><td>7.58 ± 0.21%</td></tr></table>



Table content: <table/>

Peer review (iclr2019):
 The paper studies the effect of learning-rate choices for stochastic optimization, focusing on least-mean-squares with decaying stepsizes. The main result is showing that exponentially decaying stepsizes can yield improved rates of convergence of the final iterate in terms of dependence on the condition number. The proposed learning rate schedule depends on the condition number and the number of iterations. This positive result is complemented by showing that without prior knowledge of the time horizon, any stepsize sequence will frequently yield suboptimal solutions. I have mixed feelings about the paper. On the positive side, the particular observation that exponential learning-rate schedules lead to faster convergence for SGD in linear least-squares problems indeed seems to be a novel result, and the lower bound also appears to be new and interesting. The analysis seems to be technically correct as well. On the other hand, I have several concerns about the presentation of the results: - The abstract and the introduction sets up a misleading narrative around the results: the authors seem to suggest that their work somehow explains why certain learning-rate schedules work better than others for deep learning applications / non-convex optimization, although the actual results exclusively concern the classical problem of linear least-squares regression. This presentation is completely uncalled for as the authors themselves admit that it is unclear how the results would generalize to other convex optimization settings, let alone non-convex optimization. Also, I think that this presentation style is rather harmful as it suggests that learning-theory results concerning classical setups are somehow embarrassing, so they need to be sold through some made-up connections to trendy topics in deep learning. I would suggest that the authors completely "rethink" the presentation of the paper and write it in a style that is consistent with the actual results: as a learning theory paper, without the irrelevant deep learning experiments (that only show well-known phenomena anyway). - The paper misrepresents a large body of work on stochastic/online optimization. Specifically, the authors suggest that the stochastic optimization literature exclusively suggests the use of polynomially decaying stepsizes. This picture is grossly inaccurate for multiple reasons: *** It has been known for a while that the de facto optimal tuning of SGD for least squares involves a large constant stepsize and iterate averaging (see, e.g., Bach and Moulines, NIPS 2013). This approach is only mentioned in passing without any discussion, even though it yields convergence rates that do not involve *any* dependence on the condition number in the leading term---thus achieving a much more significant improvement than the learning-rate schedule studied in this paper. In light of these results, learning-rate schedules are already being "re-thought" as we speak, and studying the behavior of the last iterate has received less attention in the past couple of years. If anything, the present paper only provides further evidence (through the negative result) that the individual iterates are ill-behaved in general and it is better to average the iterates instead. I would consider this negative result as an interesting addition to the stochastic-optimization literature, had it been presented in a completely different narrative (e.g., augmenting the discussion in "Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes" by Shamir and Zhang, 2013). *** Exponentially decaying (or "constant-and-cut", as they are called here) schedules have actually been studied before in the paper "Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex Optimization" by Hazan and Kale (JMLR 2014). This significantly weakens the main intended selling point of the paper which was being the first-ever study of such learning-rate schedules. The results in said paper are of a somewhat different nature, but they have arguably as little to do with deep learning as the results of the present paper has. Notably, both the present paper and the cited work rely on *strong convexity* of the objective (through assuming prior knowledge of the condition number), so I would expect that none of these results would explain anything in the context of deep learning. On the technical side, the proofs appear to be correct but presented somewhat sloppily, with most of the notation appearing without proper definitions. For instance, the proof of Theorem 2 seems to import notation from the proof of Theorem 1, although without explicitly mentioning that the covariance matrix is assumed to be diagonal(ized). The proof of Theorem 3 then seems to again replace this previously (non-)established notation by another one (e.g., v becomes err and .eta becomes .gamma). The proofs also involve long sequences of inequalities without explanation, and only bound the variances (w_k-w^*_k)^2 without mentioning how this quantity is related to the excess risk. (The relation is well-known but not obvious at all for first-time readers of such proofs.) One technical limitation of the results is that they assume a simple additive-noise model for the gradients, which the authors conveniently call "fairly natural" and incorrectly claim to hold for linear regression with well-specified models (footnote 8). In reality, the gradient noise in this setting also depends on the current iterate w_t, which makes analysis significantly harder. (To see the difference, just compare the complexity of the proofs of Lemma 1 and Theorem 2 that correspond to these different settings in "Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression" by Dieleveut, Flammarion and Bach, 2017.) Overall, I don*t think that this paper is fit for publication in its present form. Once again, I would suggest that in a future version, the authors focus solely on discussing the actual results without attempting to draw disproportionate conclusions from them. Detailed comments ================= - pp.1, abstract: the first half of the abstract is completely irrelevant to the rest of the paper, so I*d suggest removing it. - pp.1, "learning-rate schedules for SGD is a rather enigmatic topic"---"enigmatic" feels like a bit of a strong adjective here, given that there are many aspects of learning-rate tuning that are actually pretty well-understood. - pp.2: The second paragraph on page 2 is again irrelevant to the actual technical content of the paper. - pp.2, "all the works in stochastic approximation try to bound the error of each iterate of SGD"---This is simply not true, given the growing literature concerning the behavior of the *averaged iterates*. - pp.4, first display: poor typesetting. - pp.6, Eqs. 1--3: ditto. - pp.8, last paragraph: Singling out the particular setting of gradient-norm minimization feels arbitrary and poorly justified. - pp.11: the first and second displays should be switched for better readability (otherwise the first one comes without explanation). Also note that this form is not just due to the algorithm design, but also to the simplified noise model. - pp.12, App B: *** It appears that you forgot to mention here that you*re working in the coordinate system induced by the eigenvectors, and also forgot to define the eigenvalues, etc. *** The indices (1) and (k) are incoherent in the first display. *** Although you promise you*ll prove the inequality in the second display, you eventually prove something else. *** It is not very clear on first sight that .ell^* actually exists and falls within the scope of .ell---you should explain that it exists due to the choice of the number of phases. (Which, by the way, should be rounded up to allow this property?) *** The sequence of inequalities in the last display seems correct but unnecessarily hard to verify due to the lack of explanations.