Paperlane

no. 4 · Wednesday 28 October 2026

Proximal Point Newton Methods for Nonconvex Optimization

Chang He and Shuzhong Zhang

math.OC

Abstract

Tensor methods offer improved complexity guarantees for nonconvex optimization, but evaluating high-order derivatives and solving the corresponding subproblems can be computationally expensive. In this paper, we develop a proximal point Newton framework that exploits third-derivative smoothness using only gradients and Hessians. Under Hessian Lipschitz continuity, a single-loop proximal point Newton method that alternates between negative-curvature directions and Newton steps finds an $(\varepsilon_g,\varepsilon_H)$-approximate second-order stationary point within $\mathcal{O}(\max\{\varepsilon_g^{-3/2},\varepsilon_H^{-3}\})$ second-order oracle evaluations. When the third derivative is also Lipschitz continuous, we introduce an accelerated proximal point Newton method and obtain a dimension-free complexity of $\widetilde{\mathcal{O}}(\max\{\varepsilon_g^{-4/3},\varepsilon_H^{-2}\})$, matching that of the third-order tensor methods up to logarithmic factors without constructing tensors or solving tensor subproblems. We further develop an adaptive inexact Newton–CG variant that requires no prior knowledge of Lipschitz constants and preserves the improved oracle complexity with high probability. Under uniformly bounded queried Hessians, this variant achieves a Hessian-vector product complexity of $\widetilde{\mathcal{O}}(\max\{\varepsilon_g^{-5/3},\varepsilon_H^{-5/2}\})$, improving upon the previous $\widetilde{\mathcal{O}}(\max\{\varepsilon_g^{-3}\varepsilon_H^{5/2},\varepsilon_H^{-7/2}\})$ result attained by existing second-order methods such as cubic regularized Newton method and Newton–CG method. Preliminary numerical experiments are encouraging.

fields
Optimization and Control
pdf ↗ page arXiv:2610.36256 ↗