Unconstrained optimisation on Riemannian manifolds

Abstract

In this paper, we give explicit descriptions of versions of (Local-) Backtracking Gradient Descent and New Q-Newton's method to the Riemannian setting.Here are some easy to state consequences of results in this paper, where X is a general Riemannian manifold of finite dimension and $f:X\to \mathbb{R}$ a $C^2$ function which is Morse (that is, all its critical points are non-degenerate). {\bf Theorem.} For random choices of the hyperparameters in the Riemanian Local Backtracking Gradient Descent algorithm and for random choices of the initial point $x_0$, the sequence $\{x_n\}$ constructed by the algorithm either (i) converges to a local minimum of $f$ or (ii) eventually leaves every compact subsets of $X$ (in other words, diverges to infinity on $X$). If $f$ has compact sublevels, then only the former alternative happens. The convergence rate is the same as in the classical paper by Armijo. {\bf Theorem.} Assume that $f$ is $C^3$. For random choices of the hyperparametes in the Riemannian New Q-Newton's method, if the sequence constructed by the algorithm converges, then the limit is a critical point of $f$. We have a local Stable-Center manifold theorem, near saddle points of $f$, for the dynamical system associated to the algorithm. If the limit point is a non-degenerate minimum point, then the rate of convergence is quadratic. If moreover $X$ is an open subset of a Lie group and the initial point $x_0$ is chosen randomly, then we can globally avoid saddle points. As an application, we propose a general method using Riemannian Backtracking GD to find minimum of a function on a bounded ball in a Euclidean space, and do explicit calculations for calculating the smallest eigenvalue of a symmetric square matrix.

29 pages. Some experimental results (on singular cost functions on Euclidean spaces, and on minimum on the closed unit ball in the Euclidean spaces) are given. References updated

References in corpus (8)

• ADADELTA: An Adaptive Learning Rate Method
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems
• Convergence to minima for the continuous version of Backtracking Gradient Descent
• Some convergent results for Backtracking Gradient Descent method on Banach spaces
• Backtracking Gradient Descent allowing unbounded learning rates
• Asymptotic behaviour of learning rates in Armijo's condition
• Coordinate-wise Armijo's condition