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) is essential for success. For the sake of clarity, this paper focuses on the special case ₙ = ₀ n^- at iteration n, with 0, 1 and ₀>0 design parameters. It is most common in practice to take =0 (constant step-size), while in more theoretically oriented papers a vanishing step-size is preferred. In particular, with (1/2, 1) it is known that on applying the averaging technique of Polyak and Ruppert, the mean-squared error (MSE) converges at the optimal rate of O (1/n) and the covariance in the central limit theorem (CLT) is minimal in a precise sense. The paper revisits step-size selection in a general Markovian setting. Under readily verifiable assumptions, the following conclusions are obtained provided 0<<1: Parameter estimates converge with probability one, and also in Lₚ for any p 1. The MSE may converge very slowly for small, of order O (ₙ²) even with averaging. For linear stochastic approximation the source of slow convergence is identified: for any (0, 1), averaging results in estimates for which the error covariance vanishes at the optimal rate, and moreover the CLT covariance is optimal in the sense of Polyak and Ruppert. However, necessary and sufficient conditions are obtained under which the bias converges to zero at rate O (ₙ). This is the first paper to obtain such strong conclusions while allowing for 1/2. A major conclusion is that the choice of =0 or even <1/2 is justified only in select settings -- In general, bias may preclude fast convergence.