  Many modern learning tasks involve fitting nonlinear models to data which are
trained in an overparameterized regime where the parameters of the model exceed
the size of the training dataset. Due to this overparameterization, the
training loss may have infinitely many global minima and it is critical to
understand the properties of the solutions found by first-order optimization
schemes such as (stochastic) gradient descent starting from different
initializations. In this paper we demonstrate that when the loss has certain
properties over a minimally small neighborhood of the initial point, first
order methods such as (stochastic) gradient descent have a few intriguing
properties: (1) the iterates converge at a geometric rate to a global optima
even when the loss is nonconvex, (2) among all global optima of the loss the
iterates converge to one with a near minimal distance to the initial point, (3)
the iterates take a near direct route from the initial point to this global
optima. As part of our proof technique, we introduce a new potential function
which captures the precise tradeoff between the loss function and the distance
to the initial point as the iterations progress. For Stochastic Gradient
Descent (SGD), we develop novel martingale techniques that guarantee SGD never
leaves a small neighborhood of the initialization, even with rather large
learning rates. We demonstrate the utility of our general theory for a variety
of problem domains spanning low-rank matrix recovery to neural network
training. Underlying our analysis are novel insights that may have implications
for training and generalization of more sophisticated learning problems
including those involving deep neural network architectures.
