Research map / Optimization / Nonconvex and smooth optimization
Second-Order Min-Max Optimization with Lazy Hessians
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 LEN, a lazy-Hessian extra-gradient cubic-regularized Newton method for convex-concave and strongly-convex-strongly-concave minimax problems, reducing total computational complexity by a factor of d^{1/3} versus prior optimal second-order methods.
Problem
Computational cost of second-order methods for convex-concave and strongly-convex-strongly-concave minimax optimization, where each iteration typically requires a new Hessian and a d^3 linear solve.
Approach
Reuse the Hessian from a snapshot point updated every m iterations inside a cubic-regularized Newton implicit step followed by an extra-gradient step, with an analysis that bounds the lazy-Hessian error by choosing M ≥ 3ρm; restarts give a SC-SC variant with superlinear epoch convergence.
Key results
- LEN with m=Θ(d) achieves total complexity Õ((N+d^2)(d+d^{2/3}ε^{-2/3})), improving the prior Õ((N+d^2)dε^{-2/3}) by a factor of d^{1/3}.
- LEN-restart achieves Õ((N+d^2)(d+d^{2/3}κ^{2/3})) for SC-SC problems, versus Õ((N+d^2)dκ^{2/3}) for prior methods.
- Experiments on synthetic bilinear and fairness tasks show LEN (m=10) reaches low gradient norms faster in running time than EG and NPE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| reuse Hessians across iterations with m=Θ(d), instead of querying a new Hessian each iteration | second-order methods for C-C minimax · C-C minimax | computational complexity: improves ... by a factor of d^{1/3} | Helped |
| reuse Hessians with m=Θ(d) and apply restart | second-order methods for SC-SC minimax · SC-SC minimax | computational complexity: improve ... by a factor of d^{1/3} | Helped |
| set m=1, removing lazy Hessian reuse (ablation) | LEN · C-C minimax | computational complexity: \gO((N+d^2) d \epsilon^{-2/3}) | Hurt |
| vary the Hessian snapshot interval m (ablation) | LEN · regularized bilinear min-max; n ∈ {10, 100,200} | running time to gradient norm | Mixed |
| use LEN with m=10 (ablation) | LEN · fairness-aware machine learning: heart, adult, law school | running time to gradient norm | Helped |
Limitations
- Analysis restricted to convex-concave and strongly-convex-strongly-concave settings; nonconvex cases not covered.
- Assumes Hessian cost is d times gradient cost (Assumption on oracle complexity).
- Experiments are small-scale (n up to 200 and small real datasets).
Experimental setup
Datasets: heart adult law school
Benchmarks: regularized bilinear min-max problem fairness-aware ML on heart, adult, law school
Metrics: running time vs gradient norm ||F(z)||
Baselines: EG NPE search-free NPE OGDA-2 Perseus-restart ARE-restart
Builds on: Newton Proximal Extragradient Cubic Regularized Newton Extra-gradient Perseus Lazy Hessian
Closest papers by meaning
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.90)
- Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints (NeurIPS 2024 · similarity 0.88)
- The Computational Complexity of Finding Second-Order Stationary Points (ICML 2024 · similarity 0.88)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.87)
- On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms (ICML 2025 · similarity 0.87)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · 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.