  We consider the problem of minimizing the average of a large number of smooth
but possibly non-convex functions. In the context of most machine learning
applications, each loss function is non-negative and thus can be expressed as
the composition of a square and its real-valued square root. This reformulation
allows us to apply the Gauss-Newton method, or the Levenberg-Marquardt method
when adding a quadratic regularization. The resulting algorithm, while being
computationally as efficient as the vanilla stochastic gradient method, is
highly adaptive and can automatically warmup and decay the effective stepsize
while tracking the non-negative loss landscape. We provide a tight convergence
analysis, leveraging new techniques, in the stochastic convex and non-convex
settings. In particular, in the convex case, the method does not require access
to the gradient Lipshitz constant for convergence, and is guaranteed to never
diverge. The convergence rates and empirical evaluations compare favorably to
the classical (stochastic) gradient method as well as to several other adaptive
methods.
