Learning rate schedules for stochastic gradient algorithms
John E. Moody, Christian J. Darken · 1993
Stochastic gradient descent is an important class of stochastic processes which is relevant to as studied in engineering and biology. LMS adaptive filtering, online backpropagation, and forms of k-means clustering (vector quantization), all important signal processing algorithms, are stochastic gradient descent processes. Stochastic gradient processes can often be viewed as online optimization algorithms. The advantage of these algorithms is that the update complexity is typically linear in the number of system parameters as compared to quadratic or worse for variants of Newton's method. Thus there continues to be great interest in using stochastic gradient algorithms to solve the large least squares problems which are ubiquitous in engineering. Each algorithm takes steps down the gradient of some loss function. The step size is controlled by an adjustable sequence of gains (or learning rate schedule). How to choose this sequence in order to quickly find a good local minimum of the loss is the central problem studied in this work. We present a new deterministic schedule which has improved chances of escaping from local minima but which is still capable of achieving fast convergence asymptotically. These schedules keep the rate constant at small times (the search phase), and reduce the rate like c/t asymptotically (the phase). This schedule performs much better than the standard choice for k-means clustering. We propose a new adaptive rate schedule, based on our extensions to stochastic approximation theory, which tunes c on line. Our starting point is the classical result that in order to converge to a minimum as quickly as possible, the rate must go asymptotically as c/t, where c is greater than some task-dependent threshold. We develop a specific, computationally inexpensive method for determining whether a particular c is large enough and prove that it works. Additionally, experimental results on signal processing tasks are presented for both new schedules.