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

arXiv: https://arxiv.org/abs/1811.06703 · HTML: https://mlsanity.com/paper/1811.06703/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2018.

## Built on by (most cited first, 2 of 2)

- [On the Stability of a non-hyperbolic nonlinear map with non-bounded set of non-isolated fixed points with applications to Machine Learning](https://mlsanity.com/paper/2401.03051/) (2024)
- [Beyond IGO-Flow: Toward Convergence Analysis of IGO in Continuous Spaces](https://mlsanity.com/paper/2606.17523/) (2026)

## Abstract (arXiv)

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 θnn≥ 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(θ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(θ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(θ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(θ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.