Proximal Point Newton Methods for Nonconvex Optimization
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 (εg,εH)-approximate second-order stationary point within 𝒪(max{εg−3/2,ε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 𝒪̃(max{εg−4/3,ε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 𝒪̃(max{εg−5/3,εH−5/2}), improving upon the previous 𝒪̃(max{εg−3εH5/2,ε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.
Related
- Proximal Limited-Memory Quasi-Newton Methods for Nonsmooth Nonconvex Optimization
- Interior-point proximal methods for nonsmooth optimization in Hilbert spaces with cone-ordered constraints
- Convergence of a Randomized Newton Method in Nonconvex Optimization
- Primal-Dual Inexact Newton-MR for Nonconvex Optimization with Equality Constraints
- Envelope Cubic Regularized Newton Method for Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{he2026proximal,
title = {{Proximal Point Newton Methods for Nonconvex Optimization}},
author = {Chang He and Shuzhong Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36256},
eprint = {2610.36256},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36256},
}
RIS
TY - UNPB
TI - Proximal Point Newton Methods for Nonconvex Optimization
AU - Chang He
AU - Shuzhong Zhang
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.36256
UR - https://arxiv.org/abs/2610.36256
AB - 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 (ε_g,ε_H)-approximate second-order stationary point within 𝒪(max{ε_g^−3/2,ε_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 𝒪̃(max{ε_g^−4/3,ε_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 𝒪̃(max{ε_g^−5/3,ε_H^−5/2}), improving upon the previous 𝒪̃(max{ε_g^−3ε_H^5/2,ε_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.
ER -