Envelope Cubic Regularized Newton Method for Nonconvex-Strongly-Concave Minimax Optimization
Abstract
We study nonconvex-strongly-concave minimax problem minx∈ℝdxmaxy∈ℝdyf(x,y) in which the objective has ρ-Lipschitz Hessian and condition number κ. We propose envelope cubic regularized Newton method (ECRN) which applies a refined inexact cubic regularized Newton method to the envelope of the primal function Φ(·) : = maxy∈ℝdyf(·,y). We show that ECRN finds approximate second-order stationary points of Φ(·) with 𝒪̃(√ρ κ3/4ε−3/2) second-order oracles, improving the condition number dependence 𝒪(κ2) achieved by the best known second-order methods. Our improvement comes from the key observation that the Hessian Lipschitz parameter of the envelope is 𝒪(ρκ3/2), which is sharper than the order of 𝒪(ρκ3) for the function Φ(·). We also conduct a lower bound on second-order methods to show that our complexity is optimal up to a logarithmic factor.
Related
- Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
- Single-Loop Stochastic Projected Damped Extragradient Methods for Nonconvex--(Strongly) Concave Minimax Optimization
- Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{zhou2026envelope,
title = {{Envelope Cubic Regularized Newton Method for Nonconvex-Strongly-Concave Minimax Optimization}},
author = {Qihao Zhou and Lesi Chen and Luo Luo and Chengchang Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20345},
eprint = {2610.20345},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20345},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Envelope Cubic Regularized Newton Method for Nonconvex-Strongly-Concave Minimax Optimization
AU - Qihao Zhou
AU - Lesi Chen
AU - Luo Luo
AU - Chengchang Liu
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20345
UR - https://arxiv.org/abs/2610.20345
AB - We study nonconvex-strongly-concave minimax problem min_x∈ℝ^d_xmax_y∈ℝ^d_yf(x,y) in which the objective has ρ-Lipschitz Hessian and condition number κ. We propose envelope cubic regularized Newton method (ECRN) which applies a refined inexact cubic regularized Newton method to the envelope of the primal function Φ(·) : = max_y∈ℝ^d_yf(·,y). We show that ECRN finds approximate second-order stationary points of Φ(·) with 𝒪̃(√ρ κ^3/4ε^−3/2) second-order oracles, improving the condition number dependence 𝒪(κ^2) achieved by the best known second-order methods. Our improvement comes from the key observation that the Hessian Lipschitz parameter of the envelope is 𝒪(ρκ^3/2), which is sharper than the order of 𝒪(ρκ^3) for the function Φ(·). We also conduct a lower bound on second-order methods to show that our complexity is optimal up to a logarithmic factor.
ER -