The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning

Theory and application of stochastic approximation (SA) have become increasingly relevant due in part to applications in optimization and reinforcement learning. This paper takes a new look at SA with constant step-size α>0, defined by the recursion, θn+1 = θn+ α f(θn,Phin+1) in which θn∈ℝd and Phin is a Markov chain. The goal is to approximately solve root finding problem barf(θ^*)=0, where barf(θ)=mathbbE[f(θ,Phi)] and Phi has the steady-state distribution of Phin. The following conclusions are obtained under an ergodicity assumption on the Markov chain, compatible assumptions on f, and for α>0 sufficiently small: 1. The pair process (θn,Phin) is geometrically ergodic in a topological sense. 2. For every 1≤ p≤ 4, there is a constant bp such that limsupn→∞mathbbE[|θn-θ^*|p]≤ bp αp/2 for each initial condition. 3. The Polyak-Ruppert-style averaged estimates θPRn=n-1sumk=1nθk converge to a limit θPR_∞ almost surely and in mean square, which satisfies θPR_∞=θ^*+α barUpsilon^*+O(α2) for an identified non-random barUpsilon^*∈ℝd. Moreover, the covariance is approximately optimal: The limiting covariance matrix of θ^text PRn is approximately minimal in a matricial sense. The two main take-aways for practitioners are application-dependent. It is argued that, in applications to optimization, constant gain algorithms may be preferable even when the objective has multiple local minima; while a vanishing gain algorithm is preferable in applications to reinforcement learning due to the presence of bias.