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.

本文提出一种基于子采样的方法，以降低cubic regularization方法的高计算复杂度，并利用浓度不等式提出相应的采样方案，从而在保证cubic regularization方法的全局和局部收敛性的同时，给出其全局收敛保证的首个子采样变体在非凸函数的设置中的实验证明。

非凸优化的子采样三次正则化