Gradient descent with exponentially increasing stepsizes and restarts

Let $f:{\mathbb{R}}^d\to \mathbb{R}$. We consider gradient descent $x_{n+1}=x_n-{\tau }_n\mathrm{\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 $\mathrm{\parallel }{x}_{n+1}-x_n\mathrm{\parallel }\ge e^r\mathrm{\parallel }{x}_n-x_{n-1}\mathrm{\parallel }$ 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 \to 0$, it decays as $1\mathrm{/}\log (1\mathrm{/}\tau )$ in this modified version; numerical examples illustrate the results.