Stochastic Optimization for Non-convex Problem with Inexact Hessian
  Matrix, Gradient, and Function
Liu Liu Xuanqing Liu Cho-Jui Hsieh Dacheng Tao
Trust-region (TR) and adaptive regularization using cubics (ARC) have proven
to have some very appealing theoretical properties for non-convex optimization
by concurrently computing function value, gradient, and Hessian matrix to
obtain the next search direction and the adjusted parameters. Although
stochastic approximations help largely reduce the computational cost, it is
challenging to theoretically guarantee the convergence rate. In this paper, we
explore a family of stochastic TR and ARC methods that can simultaneously
provide inexact computations of the Hessian matrix, gradient, and function
values. Our algorithms require much fewer propagations overhead per iteration
than TR and ARC. We prove that the iteration complexity to achieve
$\epsilon$-approximate second-order optimality is of the same order as the
exact computations demonstrated in previous studies. Additionally, the mild
conditions on inexactness can be met by leveraging a random sampling technology
in the finite-sum minimization problem. Numerical experiments with a non-convex
problem support these findings and demonstrate that, with the same or a similar
number of iterations, our algorithms require less computational overhead per
iteration than current second-order methods.