Gradient descent with exponentially increasing stepsizes and restarts

Abstract

Let $f:\mathbb{R}^d \rightarrow \mathbb{R}$. We consider gradient descent $x_{n+1} = x_n - \tau_n \nabla f(x_n)$, where the stepsize $\tau_n = \tau \cdot e^{rn}$ is exponentially growing (with $\tau>0$ and $0<r \ll 1$). This diverges for almost all initial values. We show that restarting the algorithm whenever $\|x_{n+1} - x_n\| \geq e^r\|x_n - x_{n-1}\|$ has good properties: it works very well in practice; we determine the limiting convergence rate in the case of convergence to a non-degenerate local minimum: it improves on classic gradient descent even though computational cost is comparable. The precise choice of $0<r \ll 1$ does not matter much and the method is virtually independent of an initial stepsize $\tau$ that is too small: while the convergence rate for gradient descent decays linearly as $\tau \rightarrow 0$, it decays as $1/\log(1/\tau)$ in this modified version; numerical examples illustrate the results.