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 sub-optimal 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.
 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 BID13 Sutskever et al., 2013; BID11 BID10 and those methods which rely on various forms of approximate preconditioning BID6 Tieleman & Hinton, 2012; BID11 . 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 BID13 BID8 ) (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 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. 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 BID15 Rakhlin et al., 2012; BID5 ; 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. DISPLAYFORM0 the variance in the i th direction at time step t. Let the initialization be such that v DISPLAYFORM1 and v DISPLAYFORM2 . 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 DISPLAYFORM3 We consider a recursion for v DISPLAYFORM4 t with eigenvalue λ i (1 or κ). By the design of the algorithm, we know v DISPLAYFORM5 1−(1−ηλ) 2 be the solution to the stationary point equation DISPLAYFORM6 Intuitively if we keep using the same learning rate η, then v DISPLAYFORM7 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 ). DISPLAYFORM8 Proof. We can rewrite the recursion as DISPLAYFORM9 In this form, it is easy to see that the iteration is a contraction towards s(η t , λ i ). Further, v DISPLAYFORM10 t − s(η t , λ i ) have the same sign. In particular, let t 0 be the first time such that DISPLAYFORM11 0 (note that η t is monotone and so is s(η t , λ i )), it is easy to see that v DISPLAYFORM12 The claim then follows from a simple induction. DISPLAYFORM13 Therefore we must have s(η T , κ) ≤ v(1) 0 = σ 2 /κ, and by Claim 1 we know v DISPLAYFORM14 we must have η T ≤ 1 8T . Next we will show that when this happens, v DISPLAYFORM15 T must be large so the function value is still large. We will consider two cases, in the first case, b ≥ T α . Since DISPLAYFORM16 T , and we are done.In the second case, b < T α . Since DISPLAYFORM17 The sum of learning rates satisfy DISPLAYFORM18 Here the second inequality uses the fact that T α−1 i −α ≤ i −1 when i ≤ T . Similarly, we also know DISPLAYFORM19 32T . This concludes the second case and proves the theorem.
This paper presents a rigorous study of why practically used learning rate schedules (for a given computational budget) offer significant advantages even though these schemes are not advocated by the classical theory of Stochastic Approximation. This paper presents a theoretical study of different learning rate schedules that resulted in statistical minimax lower bounds for both polynomial and constant-and-cut schemes. The paper studies the effect of learning-rate choices for stochastic optimization, focusing on least-mean-squares with decaying stepsizes