From Zero to Hero: How local curvature at artless initial conditions
  leads away from bad minima
Tony Bonnaire Giulio Biroli Chiara Cammarota
We investigate the optimization dynamics of gradient descent in a non-convex
and high-dimensional setting, with a focus on the phase retrieval problem as a
case study for complex loss landscapes. We first study the high-dimensional
limit where both the number $M$ and the dimension $N$ of the data are going to
infinity at fixed signal-to-noise ratio $\alpha = M/N$. By analyzing how the
local curvature changes during optimization, we uncover that for intermediate
$\alpha$, the Hessian displays a downward direction pointing towards good
minima in the first regime of the descent, before being trapped in bad minima
at the end. Hence, the local landscape is benign and informative at first,
before gradient descent brings the system into a uninformative maze. The
transition between the two regimes is associated to a BBP-type threshold in the
time-dependent Hessian. Through both theoretical analysis and numerical
experiments, we show that in practical cases, i.e. for finite but even very
large $N$, successful optimization via gradient descent in phase retrieval is
achieved by falling towards the good minima before reaching the bad ones. This
mechanism explains why successful recovery is obtained well before the
algorithmic transition corresponding to the high-dimensional limit.
Technically, this is associated to strong logarithmic corrections of the
algorithmic transition at large $N$ with respect to the one expected in the
$N\to\infty$ limit. Our analysis sheds light on such a new mechanism that
facilitate gradient descent dynamics in finite large dimensions, also
highlighting the importance of good initialization of spectral properties for
optimization in complex high-dimensional landscapes.