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) $\{\alpha_n\}$ is crucial for success. An essential condition for convergence is the assumption that $\sum_n \alpha_n = \infty$. Moreover, in all theory to date it is assumed that $\sum_n \alpha_n^2 < \infty$ (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 $\alpha_n = \alpha_0 n^{-\rho}$ with $\rho \in (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 $L_p$ for any $p\ge 1$. Moreover, the rate of convergence of the the mean-squared error (MSE) is $O(\alpha_n)$, which is improved to $O(\max\{ \alpha_n^2,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 $\beta_\theta\alpha_n$ for a vector $\beta_\theta$ identified in the paper. Results from numerical experiments illustrate that $\beta_\theta$ may be large due to a combination of multiplicative noise and Markovian memory.