  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 sense to be positive or negative with equal probability. We
allow gradients to be inexact in a relative sense 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.
