Franccois Cl'ement

Gradient descent with exponentially increasing stepsizes and restarts

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+...