SIAM Journal on Control and Optimization, Vol.37, No.5, 1456-1482, 1999
Asymptotic behavior of a Markovian stochastic algorithm with constant step
We first derive from abstract results on Feller transition kernels that, under some mild assumptions, a Markov stochastic algorithm with constant step size epsilon usually has a tight family of invariant distributions nu(epsilon), epsilon is an element of (0; epsilon(0)], whose weak limiting distributions as epsilon down arrow 0 are all flow-invariant for its ODE. Then the main part of the paper deals with a kind of converse: what are the possible limiting distributions among all flow-invariant distributions of the ODE? We first show that no repulsive invariant (thin) set can belong to their supports. When the ODE is a stochastic pseudogradient descent, these supports cannot contain saddle or spurious equilibrium points either, so that they are eventually supported by the set of local minima of their potential. Such results require only the random perturbation to lie in L-2. Various examples are treated, showing that these results yield some weak convergence results for the nu(epsilon)'s, sometimes toward a saddle point when the algorithm is not a pseudogradient.
Keywords:CONVERGENCE;APPROXIMATIONS