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):
 This paper presents a theoretical study of different learning rate schedules. Its main result are statistical minimax lower bounds for both polynomial and constant-and-cut schemes. I enjoyed reading the paper and I think the contributions in it shed some light in step size schedules that have shown to be useful in practice. I do have however some concerns that I hope the authors can address in their rebuttal. My initial rating is marginally below acceptance but I will gladly increase this rating if my concerns are addressed. # Pros * The paper is written in a way that*s both clear and accessible. * The Theoretical contributions are important, as they address the choice of step size in one of the most used optimization methods machine learning and are novel to the best of my knowledge. * Due to time constraints, I only skimmed through the proofs, but results seem correct. # Concerns My biggest concern is that its unclear how realistic is their noise model. The authors assume that the noise in the stochastic gradients e verifies E[e e^T ] = .sigma H. While they claim that this is verified for problems like least squares, it is not clear to me that this is indeed the case. Related work like (Moulines and Bach, 2013) and (Flammarion and Bach, 2015) take the same setting but can only assume that the covariance of the noise is _bounded_ by a matrix of sigma times H. How do the authors obtain a much stronger condition on the noise covariance with the same assumption? I would be much more convinced with a proof in appendix clearly showing that the assumptions in footnote 8 imply the aforementioned covariance of the noise and a paragraph comparing their noise model with that of related literature like the aforementioned references (I*m not affiliated with any of that work). Also, the authors claim that their results hold for an arbitrary noise covariance matrix but the proofs are all done with the specific .sigma H matrix. I don*t think its OK to say "our results hold for a more general setting" without proof. If they do hold for a more general setting then the proofs should be done in the general setting. If not, it should only be mentioned as future work. Please edit that remark accordingly. * The paper does not compare or discuss against constant step size with averaging, which has been shown to be theoretically optimal in some scenarios (see aforementioned papers). This should at least be mentioned, and ideally also included in experiments. # Presentation issues Clarity of the proofs can be improved. For example, in Theorem 1, the formula for v_T(1) and v_T(d) follow from a recurrence that is stated _below_ the formula, needing several passes to understand. The proofs could benefit from a pass on them to improve the flow. It is never clear whether expectations are taken with respect to the full randomness of the algorithm or conditioned on previous randomness. The E in Eq. just-before-section-4 (please add equation numbers) is a full expectation while the E[e] should be conditioned on previous randomness. The expectation in footnote 8 is also unclear if its wrt to the stochasticity of the algorithm or the randomness in the data generating process. No equation numbers makes it difficult to reference equations. Please add equation numbers so that reviewing is not more difficult than it should (and others can reference your work more precisely). Other minor presentation issues include: * Page 1: Why l-BFGS and not L-BFGS? the lowercase l makes it look like a 1. * Page 2: There important -> There *are* important. * Page 2: In fact, at least ... (missing parenthesis around Omega tilde). * Page 4: "a stochastic gradient oracle which gives us" the second w should also be boldface. * Page 4: I would have appreciated * Page 11: "variance in the i-th" direction. It would be more correct to say in the i-th coordinate as otherwise it can be mistaken with the i-th update direction. Update: I am satisfied with the answers and have upgraded my rating.