A Randomized Algorithm for Nonconvex Minimization With Inexact Evaluations and Complexity Guarantees
提出一种随机算法，在仅能获得不精确梯度和海森矩阵的情况下，求解光滑非凸函数的最小化问题，达到近似二阶最优性，并给出期望和高概率收敛保证，应用于经验风险最小化可降低梯度样本复杂度。
Abstract We consider minimization of a smooth nonconvex function with inexact oracle access to gradient and Hessian (without assuming access to the function value) to achieve approximate second-order optimality. A novel feature of our method is that if an approximate direction of negative curvature is chosen as the step, we choose its sign to be positive or negative with equal probability. We allow gradients to be inexact (with a bound on their error relative to the size of the true quantity) and relax the coupling between inexactness thresholds for the first- and second-order optimality conditions. Our convergence analysis includes both an expectation bound based on martingale analysis and a high-probability bound based on concentration inequalities. We apply our algorithm to empirical risk minimization problems and obtain improved gradient sample complexity over existing works.