Research map / Optimization / Nonconvex and smooth optimization
A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ARNCG, a parameter-free regularized Newton-CG method with gradient-based regularizers and capped CG, achieving O(eps^-3/2) second-order oracle complexity and quadratic local convergence.
Problem
Finding an epsilon-stationary point of a nonconvex function with Lipschitz Hessian while attaining both optimal global complexity and quadratic local convergence with a parameter-free regularized Newton method.
Approach
A new class of gradient-based regularizers built from current and previous gradients (rho_k = sqrt(M_k g_k) times a ratio term, with a fallback to sqrt(g_k)) combined with capped CG negative-curvature monitoring and an adaptive Lipschitz estimate M_k, so the method needs no knowledge of L_H.
Key results
- Achieves O(eps^-3/2) second-order oracle complexity plus additive tilde O(1), and tilde O(eps^-7/4) Hessian-vector products.
- Quadratic local convergence when theta > 1 and the Hessian at the limit point is positive definite.
- On CUTEst, the method without fallback is comparable to ARC_qK and slightly faster than CAT and AN2CER; uses about 6GB vs 74GB for CAT on the largest problem.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ε_k-based rather than g_k-based regularizers (ablation) | ARNCG · Nonconvex optimization | iteration complexity: O(L_H^{\frac{1}{2}}\epsilon^{-\frac{3}{2}}\log\log\frac{1}{\epsilon}) + \tilde O(1) -> O(L_H^{\frac{1}{2}}\epsilon^{-\fr | Helped |
| Set θ > 1 in the regularizers (ablation) | ARNCG · Local convergence with positive definite Hessian | local convergence order: 1.5 -> 2 | Helped |
| Remove the fallback step (ablation) | ARNCG_g on CUTEst · CUTEst | computational cost | Helped |
| Use a fixed regularizer ω_k = √ε (ablation) | Regularized Newton method on CUTEst · CUTEst | success rate | Hurt |
| Use ARNCG_g instead of NNCG | PINN reaction problem · PINN reaction problem | iteration complexity | Helped |
| Use ARNCG_g instead of NNCG | PINN reaction problem · PINN reaction problem | runtime | Helped |
Limitations
- Each iteration requires multiple CG iterations, which is costly for neural network training.
- Assumes globally Lipschitz Hessian, which may fail for nonsmooth activations such as ReLU.
Experimental setup
Datasets: CUTEst (124 unconstrained problems with more than 100 variables) PINN reaction problem
Benchmarks: CUTEst
Metrics: success rate vs elapsed time success rate vs Hessian evaluations loss curves peak GPU memory
Baselines: CAT AN2CER ARC_qK NNCG Fixed-regularizer capped CG
Builds on: Cubic regularization Capped CG (Royer et al.) NNCG AN2CER
Closest papers by meaning
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.90)
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning (NeurIPS 2025 · similarity 0.89)
- Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions (ICML 2024 · similarity 0.88)
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.88)
- Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis (NeurIPS 2025 · similarity 0.88)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.