A Sub-sampled Tensor Method for Non-convex Optimization

Abstract

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 (_1,_2,_3)-third-order critical point in at most ((_1^-4/3, _2^-2, _3^-4)) 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.

Tasks

Reproductions