On Riemannian Stochastic Approximation Schemes with Fixed Step-Size
This work addresses theoretical convergence guarantees for optimization algorithms in Riemannian manifolds, which is incremental but relevant for applications where geodesic computations accelerate Euclidean methods.
The paper tackles the analysis of fixed step-size stochastic approximation schemes in a Riemannian setting, deriving non-asymptotic performance bounds and proving geometric ergodicity and convergence to a Dirac measure at the solution as step-size approaches zero.
This paper studies fixed step-size stochastic approximation (SA) schemes, including stochastic gradient schemes, in a Riemannian framework. It is motivated by several applications, where geodesics can be computed explicitly, and their use accelerates crude Euclidean methods. A fixed step-size scheme defines a family of time-homogeneous Markov chains, parametrized by the step-size. Here, using this formulation, non-asymptotic performance bounds are derived, under Lyapunov conditions. Then, for any step-size, the corresponding Markov chain is proved to admit a unique stationary distribution, and to be geometrically ergodic. This result gives rise to a family of stationary distributions indexed by the step-size, which is further shown to converge to a Dirac measure, concentrated at the solution of the problem at hand, as the step-size goes to 0. Finally, the asymptotic rate of this convergence is established, through an asymptotic expansion of the bias, and a central limit theorem.