An ODE Method to Prove the Geometric Convergence of Adaptive Stochastic Algorithms

Abstract

We consider stochastic algorithms derived from methods for solving deterministic optimization problems, especially comparison-based algorithms derived from stochastic approximation algorithms with a constant step-size. We develop a methodology for proving geometric convergence of the parameter sequence $\{{\theta }_n{\}}_{n\ge 0}$ of such algorithms. We employ the ordinary differential equation (ODE) method, which relates a stochastic algorithm to its mean ODE, along with a Lyapunov-like function $\Psi$ such that the geometric convergence of $\Psi ({\theta }_n)$ implies -- in the case of an optimization algorithm -- the geometric convergence of the expected distance between the optimum and the search point generated by the algorithm. We provide two sufficient conditions for $\Psi ({\theta }_n)$ to decrease at a geometric rate: $\Psi$ should decrease "exponentially" along the solution to the mean ODE, and the deviation between the stochastic algorithm and the ODE solution (measured by $\Psi$) should be bounded by $\Psi ({\theta }_n)$ times a constant. We also provide practical conditions under which the two sufficient conditions may be verified easily without knowing the solution of the mean ODE. Our results are any-time bounds on $\Psi ({\theta }_n)$, so we can deduce not only the asymptotic upper bound on the convergence rate, but also the first hitting time of the algorithm. The main results are applied to a comparison-based stochastic algorithm with a constant step-size for optimization on continuous domains.

Accepted for Stochastic Processes and their Applications

References in corpus (3)

• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Drift Theory in Continuous Search Spaces: Expected Hitting Time of the (1+1)-ES with 1/5 Success Rule

Cited by in corpus (1)

• Monotone Improvement of Information-Geometric Optimization Algorithms with a Surrogate Function