Revisiting Step-Size Assumptions in Stochastic Approximation

Many machine learning and optimization algorithms are built upon the framework of stochastic approximation (SA), for which the selection of step-size (or learning rate) αn is crucial for success. An essential condition for convergence is the assumption that sumn αn = ∞. Moreover, in all theory to date it is assumed that sumn αn2 < ∞ (the sequence is square summable). In this paper it is shown for the first time that this assumption is not required for convergence and finer results. The main results are restricted to the special case αn = α0 n-ρ with ρ ∈ (0,1). The theory allows for parameter dependent Markovian noise as found in many applications of interest to the machine learning and optimization research communities. Rates of convergence are obtained for the standard algorithm, and for estimates obtained via the averaging technique of Polyak and Ruppert. bullet Parameter estimates converge with probability one, and in Lp for any p≥ 1. Moreover, the rate of convergence of the the mean-squared error (MSE) is O(αn), which is improved to O(max αn2,1/n ) with averaging. Finer results are obtained for linear SA: bullet The covariance of the estimates is optimal in the sense of prior work of Polyak and Ruppert. bullet Conditions are identified under which the bias decays faster than O(1/n). When these conditions are violated, the bias at iteration n is approximately βθαn for a vector βθ identified in the paper. Results from numerical experiments illustrate that βθ may be large due to a combination of multiplicative noise and Markovian memory.