Research map / Optimization / Nonconvex and smooth optimization
Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization
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 line-search-free, adaptive second-order optimistic methods for convex-concave min-max problems that achieve the optimal O(1/T^1.5) rate, with a fully parameter-free variant under Lipschitz-gradient assumption.
Problem
Second-order methods for convex-concave min-max optimization typically need line search or cubic subproblems and knowledge of the Hessian Lipschitz constant to reach the optimal O(1/T^1.5) rate.
Approach
Combines the second-order optimistic method with a recursively defined adaptive step size (function of gradient norm and optimistic prediction error) and an adaptive regularization lambda_t estimated from local curvature, yielding one linear solve per iteration with no line search and, in the parameter-free variant, no Hessian Lipschitz constant.
Key results
- Both variants achieve the optimal O(1/T^1.5) primal-dual gap rate without line search (Option I requires known L2; Option II is parameter-free under L1-Lipschitz gradient assumption).
- In numerical experiments on large-dimension synthetic problems, the line-search-free methods outperform optimal SOM and HIPNEX in runtime, with the gap widening as dimension grows.
- On AUC maximization with large L2 and d=10^4, both proposed methods outperform optimal SOM and HIPNEX in runtime, especially early in execution.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a line-search-free adaptive second-order optimistic method | Synthetic min-max problem · Synthetic min-max problem | runtime | Helped |
| Use a line-search-free adaptive second-order optimistic method | AUC maximization · AUC maximization | runtime | Helped |
| Adaptively estimate the Hessian Lipschitz constant instead of requiring its prior value | Adaptive SOM · Convex-concave min-max optimization | primal-dual gap convergence rate: \mathcal{O}(1/T^{1.5}) | No clear effect |
Surprising findings
- The adaptive step size rule can be non-monotonic, unlike conventional adaptive approaches.
Limitations
- Parameter-free variant requires an additional assumption that the gradient is Lipschitz (L1), so the matching lower bound does not directly apply.
- Extending parameter-free guarantees without the Lipschitz gradient assumption is left open.
- Results are stated for unconstrained min-max problems; extension to monotone inclusion is deferred to future work.
Experimental setup
Datasets: synthetic min-max problem AUC maximization problem
Benchmarks: synthetic min-max problem AUC maximization
Metrics: normalized squared operator norm ||F(z_T)||^2/||F(z_0)||^2 runtime
Baselines: HIPNEX Optimal SOM (line-search second-order optimistic method)
Builds on: second-order optimistic method optimistic gradient method proximal point method HIPNEX
Closest papers by meaning
- Second-Order Min-Max Optimization with Lazy Hessians (ICLR 2025 · similarity 0.90)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.90)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.89)
- Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes (NeurIPS 2024 · similarity 0.89)
- Fundamental Benefit of Alternating Updates in Minimax Optimization (ICML 2024 · similarity 0.88)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.88)
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.