A Stochastic Tensor Method for Non-convex Optimization
  We present a stochastic optimization method that uses a fourth-order
regularized model to find local minima of smooth and potentially non-convex
objective functions with a finite-sum structure. This algorithm uses
sub-sampled derivatives instead of exact quantities. The proposed approach is
shown to find an $(\epsilon_1,\epsilon_2,\epsilon_3)$-third-order critical
point in at most $\bigO\left(\max\left(\epsilon_1^{-4/3}, \epsilon_2^{-2},
\epsilon_3^{-4}\right)\right)$ iterations, thereby matching the rate of
deterministic approaches. In order to prove this result, we derive a novel
tensor concentration inequality for sums of tensors of any order that makes
explicit use of the finite-sum structure of the objective function.
