Convergence to minima for the continuous version of Backtracking Gradient Descent

Abstract

The main result of this paper is: {\bf Theorem.} Let $f:{\mathbb{R}}^k\to \mathbb{R}$ be a $C^1$ function, so that $\nabla f$ is locally Lipschitz continuous. Assume moreover that $f$ is $C^2$ near its generalised saddle points. Fix real numbers ${\delta }_0>0$ and $0<\alpha <1$. Then there is a smooth function $h:{\mathbb{R}}^k\to (0,{\delta }_0]$ so that the map $H:{\mathbb{R}}^k\to {\mathbb{R}}^k$ defined by $H(x)=x-h(x)\nabla f(x)$ has the following property: (i) For all $x\in {\mathbb{R}}^k$, we have $f(H(x)))-f(x)\le -\alpha h(x)||\nabla f(x)|{|}^2$. (ii) For every $x_0\in {\mathbb{R}}^k$, the sequence $x_{n+1}=H(x_n)$ either satisfies ${\lim }_{n\to \infty }||x_{n+1}-x_n||=0$ or ${\lim }_{n\to \infty }||x_n||=\infty$. Each cluster point of $\{x_n\}$ is a critical point of $f$. If moreover $f$ has at most countably many critical points, then $\{x_n\}$ either converges to a critical point of $f$ or ${\lim }_{n\to \infty }||x_n||=\infty$. (iii) There is a set ${\mathcal{E}}_1\subset {\mathbb{R}}^k$ of Lebesgue measure $0$ so that for all $x_0\in {\mathbb{R}}^k\backslash {\mathcal{E}}_1$, the sequence $x_{n+1}=H(x_n)$, {\bf if converges}, cannot converge to a {\bf generalised} saddle point. (iv) There is a set ${\mathcal{E}}_2\subset {\mathbb{R}}^k$ of Lebesgue measure $0$ so that for all $x_0\in {\mathbb{R}}^k\backslash {\mathcal{E}}_2$, any cluster point of the sequence $x_{n+1}=H(x_n)$ is not a saddle point, and more generally cannot be an isolated generalised saddle point. Some other results are proven.

20 pages. Definition 1.2 is revised to ensure that Armijo's condition is satisfied. A part iv is added to Theorem 1.3. For readers' convenience, two lemmas are added to help make proofs easy to follow. Typos corrected, exposition revised

References in corpus (1)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization

Cited by in corpus (9)

• Preparation of the SU(3) Lattice Yang-Mills Vacuum with Variational Quantum Methods
• 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
• Unconstrained optimisation on Riemannian manifolds
• New Q-Newton's method meets Backtracking line search: good convergence guarantee, saddle points avoidance, quadratic rate of convergence, and easy implementation
• Coordinate-wise Armijo's condition
• A fast and simple modification of Newton's method helping to avoid saddle points
• Generalisations and improvements of New Q-Newton's method Backtracking