Year: 2018

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.

heading: 1 INTRODUCTION
text: 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 = ab+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 PyTorch 1 and several such useful tools of the trade are taught on popular deep learning courses 2. Furthermore, what is (often) puzzling (from a theory perspective) is the emphasis that is laid on “babysitting” the learning rates 3 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 ab+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:
1https://pytorch.org/docs/stable/optim.html#torch.optim.lr_scheduler. ReduceLROnPlateau
2http://cs231n.github.io/ 3http://cs231n.github.io/neural-networks-3/ 4In fact, this work shows an instance where there is a significant (provable) difference between the perfor-
mance of these two schemes.
• 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.

heading: 2 RELATED WORK
text: 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 ofO(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.

heading: 3 PROBLEM SETUP
text: 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∈Rd
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 satisfying8 E [e] = 0 and E [ ee> ] = σ2H.
Given an initial point w0 and step size sequence ηt, the SGD algorithm proceeds with the update
wt = wt−1 − ηt∇̂f(wt−1) = wt−1 − ηt (∇f(wt−1) + et) , where et are independent for various t and satisfy the above mean and variance conditions.
Let w∗ def= arg minw∈Rd 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 σ 2d t . More concretely (Van der Vaart, 2000), we have that
lim t→∞ E [f(ŵt)]− f(w∗) σ2d/t ≥ 1 .
Moreover there exist schemes that achieve this rate of (1 + o(1)) σ 2d t e.g., constant step size SGD with averaging (Polyak & Juditsky, 1992). This rate of σ2d/t is called the statistical minimax rate.

heading: 4 COMPARISON BETWEEN POLYNOMIAL DECAY SCHEMES VS CONSTANT AND CUT SCHEMES
text: 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 κ.
5see https://pytorch.org/docs/stable/optim.html for a complete list of alternatives 6Refer to their JSON file https://github.com/allenai/allennlp/blob/master/
training_config/wikitables_parser.jsonnet 7Any 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.
8While 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 [ 2t ] = σ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 σ2H significantly simplifies exposition.

heading: 4.1 SUBOPTIMALITY OF POLYNOMIAL DECAY SCHEMES
text: Our first result shows that there exist problem instances where all polynomial decay schemes i.e., those of the form ab+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(w0) ≤ σ2d, 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 = ab+tα , we have E [f(wT )]− f(w ∗) ≥ κ32 · σ2d T .

heading: 4.2 SUBOPTIMALITY OF CONSTANT AND CUT SCHEME
text: Our next result shows that there exist constant and cut schemes that achieve statistical minimax rate upto a multiplicative factor of only log κ log2 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(wT )]− f(w∗) ≤ f(w0)−f(w ∗) T 3 + 2 log κ · log 2 T · σ 2d 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(wT )]−f(w∗) ≤ f(w0)−f(w ∗) T 2−(1/100) +log κ · log T · σ 2d 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 TT , which is asymptotically worse than the statistical rate of 1T . 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(wT )]− f(w∗) ≤ f(w0)−f(w ∗) T 3 + 50 log2 κ · σ2d T .

heading: 5 INFINITE HORIZON SETTING
text: 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 κ) · σ2d/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 supT→∞ E[f(wT )]−f(w∗) (σ2d/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 C1, C2 > 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/C2τ)T ′] we have E[f(wT̃ )]−f(w ∗)
(σ2d/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 κ log2 T in the lim inf sense.
9Learning rate more than 2/κ will make the algorithm diverge.
Theorem 7. There exists an absolute constant C and a constant and cut learning rate scheme that obtains lim infT→∞ E[f(wT )]−f(w∗) (σ2d log2 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).

heading: 6 EXPERIMENTAL RESULTS
text: 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.

heading: 6.1 SYNTHETIC EXPERIMENTS: TWO-DIMENSIONAL QUADRATIC OBJECTIVE
text: 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).

heading: 6.2 NON-CONVEX OPTIMIZATION: TRAINING A RESIDUAL NET ON CIFAR-10
text: 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 cifar10 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 pytorch 11 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), might necessitate rethinking.
10https://github.com/D-X-Y/ResNeXt-DenseNet 11https://github.com/pytorch

heading: 7 CONCLUSIONS AND DISCUSSION
text: 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.

heading: A PROOFS OF RESULTS IN SECTION 4.1
text: 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 ith 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 η2j 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 η2j 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)2v (i) t + λiσ 2η2t .
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 t0 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 ≤ t0. 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 σ2d/2 ≥ κσ2d/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(wT )] ≥ d
2 · κv(1)T ≥ dκσ2ηT 4 .
To make sure E [f(wT )] ≤ 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 18T ≥ η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(wt)] ≥ d 2v (d) T ≥ dσ2 4 ≥ κdσ2 T , and we are done.
In the second case, b < Tα. Since 18T ≥ η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α−1i−α ≤ 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(wt)] ≥ d2v (d) T ≥ dσ2 20 √ T ≥ κdσ 2
32T . This concludes the second case and proves the theorem.

heading: B PROOFS OF RESULTS IN SECTION 4.2
text: 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 kth 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 η2j T∏ i=j+1 ( 1− ηiλ(k) )2
≤ exp −2 T∑ j=1 ηjλ (k)  v(1)0 + λ(k)σ2 T∑ j=1 η2j 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 η2j 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 κ log2 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 κ · log2 T λ(k)T · σ2.
This finishes the proof.
Proof of Theorem 3. The learning rate scheme we consider is γt = γ0 · ct−1 with γ0 = log T/(µTe), Te = T/ log κ and c = (1 − 1/Te). 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))2err(k)0 + (λ(k))2σ2 T̂∑ τ=1 γ2τ ·  T̂∏ t=τ+1 (1− γtλ(k))2 
≤ exp −2λ(k)γ0 T̂∑ t=1 ct−1 err(k)0 + (λ(k))2σ2γ20c2 T̂∑ τ=1 c2τ exp −2λ(k)γ0 T̂∑ t=τ+1 ct−1  = exp ( −2λ
(k)γ0 1− c
· (1− cT̂ ) ) err(k)0 + (λ(k))2σ2γ20
c2
T̂∑ τ=1 c2τ exp ( −2λ (k)γ0 1− c · (cτ − cT̂ ) )
= exp ( 2λ(k)γ0 1− c · cT̂ ) · exp(−2λ(k)γ0 1− c ) err(k)0 + (λ(k))2σ2γ20 c2 T̂∑ τ=1 c2τ 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:
cT̂∑ x=c x2 exp (−αx) ≤ ∫ cT̂ 1 x2 exp (−αx)dx ≤ 1 α · ( 1 + 2 α + 2 α2 ) exp (−α).
Substituting this in the previous bound, we have:
err(k) T̂ ≤ exp
( −α(1− cT̂ ) ) · err(k)0 + (λ(k))2σ2γ20αc2 · ( 1 + √ 2 α )2 ≤ exp ( −α(1− cT̂ ) ) · ( err(k)0 + 16 (λ(k))2σ2γ20
α ) ≤ exp ( −α(1− cT̂ ) ) · ( err(k)0 + 16 (λ(k))2σ2 log T
µ2T 2e · 2(λ(k)/µ) ) = exp ( −α(1− cT̂ ) ) · ( err(k)0 + 8 λ(k)σ2 log T
µT 2e ) Now, setting T̂ = Te 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 2e ) ≤ 1 T 2−(1/C) · ( err(k)0 + 8 λ(k)σ2 log T
µT 2e
) (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))2err(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 µTe · µ 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 log2(κ) equal sized phases. In the `th phase, the learning rate to be used is 5 log2 κ 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 kth 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 η2j T∏ i=j+1 ( 1− ηiλ(k) )2
≤ exp −2 T∑ j=1 ηjλ (k)  v(1)0 + λ(k)σ2 T∑ j=1 η2j exp −2 T∑ i=j+1 ηiλ (k)  . We will show that for every k, we have
v (k) T ≤
v (k) 0
T 3 +
50 log2 κ
λ(k)T · σ2., (5)
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)2tv (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)2v (k) t−1 + λ (k)σ2/L2
≤ (1− λ(k)/L)2tv(k)0 + σ2
L
( (1− λ(k)/L)2 + λ(k)/L ) ≤ (1− λ(k)/L)2tv(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(k)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) 2v (k) A+t−1 + λ (k)σ2η2A+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− 12µη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 log2 κ, 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`) + 2T̂ η 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) · 2T̂ η 2 `−1λ (k) + T̂ η2`λ (k) ≤ v(k)B exp(−3`) + 2T̂ η 2 `λ (k).
This finishes the induction.
By Claim 2, Let `∗ denote the number satisfying 2` ∗ ·µ ≤ λ(k) < 2`∗+1 ·µ, by this choice we know µ/λ(k) ≥ 12 exp(−3` ?) we have
v (k) T ≤ v (k) B+`∗T̂ ≤ v(k)B exp(−3` ∗) + 2T̂ η2`∗λ (k)σ2
≤ v (k) 0
T 3 +
24σ2 λ(k)T + 50 log2 κ 3λ(k)T · σ2.
≤ v (k) 0
T 3 +
50 log2 κ
λ(k)T · σ2.
Therefore, the function value is bounded by E [f(wT )] = ∑d i=1 λ (k)v (k) T ≤ f(w0) T 3 + 50 log2 κ T · σ2d.

heading: C PROOFS OF RESULTS IN SECTION 5
text: 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:
v (1) T def = E
[( w
(1) T − (w
∗) (1) )2] = T∏ j=1 (1− ηjκ)2 v(1)0 + κσ2 T∑ j=1 η2j T∏ i=j+1 (1− ηiκ)2
≥ exp −2 T∑ j=1 ηjκ  v(1)0 + κσ2 T∑ j=1 η2j exp −2 T∑ i=j+1 ηiκ  and (6) v
(2) T def = E
[( w
(2) T − (w
∗) (2) )2] = T∏ j=1 (1− ηj)2 v(2)0 + σ2 T∑ j=1 η2j T∏ i=j+1 (1− ηi)2
≥ exp −2 T∑ j=1 ηj  v(2)0 + σ2 T∑ j=1 η2j exp −2 T∑ i=j+1 ηi  . (7) 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(wT̃ ) (σ2/T̃) ≥ τ . Given the step size sequence ηt, consider the sequence of numbers T0 = T, T1, · · · , Tκ such that Ti 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 Ti − Ti−1. Firstly, from (6) and (7), we see that ∑ t ηt = ∞. Otherwise, the bias will never decay to zero. If f(wTi−1+∆i) > τσ2d Ti−1+∆i for some i = 1, · · · , κ, we are done. If not, we obtain the following relations:
σ2 ∆1 ≤ σ2 ∆1∑ t=1 η2T0+t ≤ exp(3) κ · E [( w (1) T0+∆1 − (w∗)(1) )2] ≤ exp(3)flin(wT0+∆1) ≤ exp(3)τσ2 T0 + ∆1
⇒ T0 ≤ (exp(3)τ − 1) ∆1. Here the second inequality is based on (6). We will use C1 to denote exp(3). Similarly, we have
σ2 ∆2 ≤ σ2 ∆2∑ t=1 η2T1+t ≤ C1 κ E [( w (1) T1+∆2 − (w∗)(1) )2] ≤ C1flin(wT1+∆2) ≤ C1τσ 2 T1 + ∆2
⇒ T1 ≤ (C1τ − 1) ∆2 ⇒ T0 ≤ (C1τ − 1)2
C1τ ∆2.
Repeating this argument, we can show that
T = T0 ≤ (C1τ − 1)i
(C1τ) i−1 ∆i and Ti ≤
(C1τ − 1)j−i
(C1τ) j−i−1 ∆j ∀ i < j.
We will use i = 1 in particular, which specializes to
T1 ≤ (C1τ − 1)j−1
(C1τ) j−2 ∆j ∀ j ≥ 2.
Using the above inequality, we can lower bound the sum of ∆j as κ∑ j=2 ∆j ≥ T1 · κ∑ j=2 (C1τ) j−2 (C1τ − 1)j−1 ≥ T1 · 1 C1τ · κ∑ j=2 ( 1 + 1 C1τ )j−2 ≥ T1 · 1
C1τ · exp (κ/(C1τ)) . (8)
This means that
E [f(wTi)] ≥ d 2 · E [( w (2) Ti − (w∗)(2) )2] ≥ exp(−6)σ2d · ∆1∑ i=1 η2T+i
≥ exp(−6)σ 2d ∆1 ≥ exp(−6)σ 2d T1 ≥ exp (κ/(C1τ)− 3) C1τ · σ 2d∑κ j=2 ∆j ,
where we used (8) in the last step. Rearranging, we obtain
E [f(wTκ)] (σ2d/Tκ) ≥ exp (κ/(C1τ)− 3) C1τ .
If we choose a large enough C (e.g., 3C1), 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 wT is bad (in the sense that it has expected value more than 10τσ2d/T ), then it takes at least Ω(T/τ) steps to bring the error back down. Lemma 8. There exists universal constantsC1, C2 > 0 such that for any τ ≤ κCC1 log(κ+1) whereC is the constant in Theorem 5, suppose at step T , the query point wT satisfies f(wT ) ≥ C1τσ2d/T , then for all T̃ ∈ [T, (1 + 1C2τ )T ] we have E [f(wT̃ )] ≥ τσ 2d/T ≥ τσ2d/T̃ .
Proof of Lemma 8. Since f(wT ) ≥ C1τσ2d/T and f(wT ) = d 2 ( κ ( w (1) T − (w∗) (1) )2 + ( w (2) T − (w∗) (2) )2) , we know either ( w (1) T − (w∗) (1) )2 ≥
C1τσ 2/2κT or ( w (2) T − (w∗) (2) )2 ≥ C1τσ2/2T . Either way, we have a coordinate i with
eigenvalue λi (κ or 1) such that ( w (i) T − (w∗) (i) )2 ≥ C1τσ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)C1τσ2/(2λiT ) just by the first term. When we choose C1 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 S2 := ∑T+∆ T̃=T+1 η2 T̃ .
If S2 ≤ C2τ/(λ2iT ) (where C2 is a large enough universal constant chosen later), then by CauchySchwartz we know
S2 ·∆ ≥ ( T+∆∑ T̃=T+1 ηT̃ ) 2 ≥ 1/λ2i .
Therefore ∆ ≥ T/C2τ , and we are done. If S2 > C2τ/(λ2iT ), by Equation (6) and (7) we know
E [(
w (i) T+∆ − (w
∗) (i) )2] ≥ σ2 T+∆∑ T̃=T+1 η2 T̃ exp −2λi T+∆∑ j=T̃+1 ηj  ≥ exp(−6)σ2
T+∆∑ T̃=T+1 η2 T̃ ≥ exp(−6) · C2τσ2/(λ2iT ).
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 S2. In this case as we can see as long as C2 is large enough, T + ∆ is also a point with E [f(wT+∆)] ≥
λiE [( w (i) T+∆ − (w∗) (i) )2] ≥ C1τσ2/(T + ∆), so we can repeat the argument there. Eventually
we either stop because we hit case 1: S2 ≤ C2τ/λ2iT or the case 2 S2 > C2τ/λ2iT happened more than T/C2τ times. In either case we know for any T̃ ∈ [T, (1 + 1/C2)T ] E [f(wT̃ )] ≥ τσ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.

heading: D DETAILS OF EXPERIMENTAL SETUP
text: 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 (−106/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 pytorch 12 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 80th 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/10th dataset. Once the best grid search parameter is chosen, we train on the entire training dataset and
12https://github.com/pytorch
evaluate on the test dataset and present the result of the final model (instead of choosing the best possible model found during the course of optimization).

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

This work provides theoretical insights on recent learning rate proposals such as Cyclical Learning Rates (Smith et al.). The authors focus on stochastic approximation i.e. how large is the SGD loss as a function of condition number and horizon. The critical contribution is the theoretical benefit of oscillating learning rates over more traditional learning rate schemes. Authors provide novel upper/lower bounds to establish benefit of oscillating LR, support their theory with experiments and provide insights on finite horizon learning rate selection. An important drawback is that results only apply to linear regression which is a fairly simple setup.