  In this paper we investigate how gradient-based algorithms such as gradient
descent, (multi-pass) stochastic gradient descent, its persistent variant, and
the Langevin algorithm navigate non-convex loss-landscapes and which of them is
able to reach the best generalization error at limited sample complexity. We
consider the loss landscape of the high-dimensional phase retrieval problem as
a prototypical highly non-convex example. We observe that for phase retrieval
the stochastic variants of gradient descent are able to reach perfect
generalization for regions of control parameters where the gradient descent
algorithm is not. We apply dynamical mean-field theory from statistical physics
to characterize analytically the full trajectories of these algorithms in their
continuous-time limit, with a warm start, and for large system sizes. We
further unveil several intriguing properties of the landscape and the
algorithms such as that the gradient descent can obtain better generalization
properties from less informed initializations.
