  Learning rate schedules are ubiquitously used to speed up and improve
optimisation. Many different policies have been introduced on an empirical
basis, and theoretical analyses have been developed for convex settings.
However, in many realistic problems the loss-landscape is high-dimensional and
non convex -- a case for which results are scarce. In this paper we present a
first analytical study of the role of learning rate scheduling in this setting,
focusing on Langevin optimization with a learning rate decaying as
$\eta(t)=t^{-\beta}$. We begin by considering models where the loss is a
Gaussian random function on the $N$-dimensional sphere ($N\rightarrow \infty$),
featuring an extensive number of critical points. We find that to speed up
optimization without getting stuck in saddles, one must choose a decay rate
$\beta<1$, contrary to convex setups where $\beta=1$ is generally optimal. We
then add to the problem a signal to be recovered. In this setting, the dynamics
decompose into two phases: an \emph{exploration} phase where the dynamics
navigates through rough parts of the landscape, followed by a
\emph{convergence} phase where the signal is detected and the dynamics enter a
convex basin. In this case, it is optimal to keep a large learning rate during
the exploration phase to escape the non-convex region as quickly as possible,
then use the convex criterion $\beta=1$ to converge rapidly to the solution.
Finally, we demonstrate that our conclusions hold in a common regression task
involving neural networks.
