OFF Newton-type Methods for Unconstrained Optimization with Inexact Derivatives

Abstract

We study objective-function-free (OFF) Newton-type methods for smooth unconstrained optimization with inexact gradients and Hessians. We propose two methods for first- and second-order stationarity, coupling explicit step-size rules with derivative-accuracy and linear-solver residual conditions to guarantee sufficient decrease without evaluating the objective function. The OFF regularized Newton method finds an $\epsilon$-first-order stationary point in $\mathcal{O}({\epsilon }^{-2})$ iterations. Under strong convexity, a local Newton variant converges with \(Q\)-order at least $1+\theta$, where \(θ\in (0, 1]\). For second-order stationarity, we combine regularized Newton steps with approximate eigenvectors associated with the minimum eigenvalue. With high probability, the resulting method finds an $(\epsilon ,\sqrt{L_h\epsilon })$-second-order stationary point in $\mathcal{O}({\epsilon }^{-3/2})$ iterations, using a total of $\tilde{\mathcal{O}}({\epsilon }^{-7/4})$ approximate gradient evaluations and Hessian-vector products. For finite-sum problems, we develop subsampling schemes that yield best-iterate convergence in expectation in the nonconvex first-order setting and local \(R\)-linear convergence with high probability in the strongly convex setting, followed by \(Q\)-order at least \(1+θ\) once full sampling is reached. The subsampled second-order method achieves a high-probability $\tilde{\mathcal{O}}({\epsilon }^{-7/2})$ total sample-operation bound, counting component gradient evaluations and component Hessian-vector products.

arXiv comment28 pages