Sub-sampled Cubic Regularization for Non-convex Optimization
  We consider the minimization of non-convex functions that typically arise in
machine learning. Specifically, we focus our attention on a variant of trust
region methods known as cubic regularization. This approach is particularly
attractive because it escapes strict saddle points and it provides stronger
convergence guarantees than first- and second-order as well as classical trust
region methods. However, it suffers from a high computational complexity that
makes it impractical for large-scale learning. Here, we propose a novel method
that uses sub-sampling to lower this computational cost. By the use of
concentration inequalities we provide a sampling scheme that gives sufficiently
accurate gradient and Hessian approximations to retain the strong global and
local convergence guarantees of cubically regularized methods. To the best of
our knowledge this is the first work that gives global convergence guarantees
for a sub-sampled variant of cubic regularization on non-convex functions.
Furthermore, we provide experimental results supporting our theory.
