A Homogeneous Second-Order Descent Ascent Algorithm for Nonconvex-Strongly Concave Minimax Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917275479572480 |
|---|---|
| author | Chen, Jia-Hao Xu, Zi Zhang, Hui-Ling |
| author_facet | Chen, Jia-Hao Xu, Zi Zhang, Hui-Ling |
| contents | This paper introduces a novel Homogeneous Second-order Descent Ascent (HSDA) algorithm for nonconvex-strongly concave minimax optimization problems. At each iteration, HSDA uniquely computes a search direction by solving a homogenized eigenvalue subproblem built from the gradient and Hessian of the objective function. This formulation guarantees a descent direction with sufficient negative curvature even in near-positive-semidefinite Hessian regimes--a key feature that enhances escape from saddle points. We prove that HSDA finds an $\mathcal{O}(\varepsilon,\sqrt{\varepsilon})$-second-order stationary point within $\tilde{\mathcal{O}}(\varepsilon^{-3/2})$ iterations, matching the optimal $\varepsilon$-order iteration complexity among second-order methods for this problem class. To address large-scale applications, we further design an inexact variant (IHSDA) that preserves the single-loop structure while solving the subproblem approximately via a Lanczos procedure. With high probability, IHSDA achieves the same $\tilde{\mathcal{O}}(\varepsilon^{-3/2})$ iteration complexity and attains an $\mathcal{O}(\varepsilon, \sqrt{\varepsilon})$-second-order stationary point, with the total Hessian-vector product cost bounded by $\tilde{\mathcal{O}}(\varepsilon^{-7/4})$. Experiments on synthetic minimax problems and adversarial training tasks confirm the practical effectiveness and robustness of the proposed algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_14058 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Homogeneous Second-Order Descent Ascent Algorithm for Nonconvex-Strongly Concave Minimax Problems Chen, Jia-Hao Xu, Zi Zhang, Hui-Ling Optimization and Control This paper introduces a novel Homogeneous Second-order Descent Ascent (HSDA) algorithm for nonconvex-strongly concave minimax optimization problems. At each iteration, HSDA uniquely computes a search direction by solving a homogenized eigenvalue subproblem built from the gradient and Hessian of the objective function. This formulation guarantees a descent direction with sufficient negative curvature even in near-positive-semidefinite Hessian regimes--a key feature that enhances escape from saddle points. We prove that HSDA finds an $\mathcal{O}(\varepsilon,\sqrt{\varepsilon})$-second-order stationary point within $\tilde{\mathcal{O}}(\varepsilon^{-3/2})$ iterations, matching the optimal $\varepsilon$-order iteration complexity among second-order methods for this problem class. To address large-scale applications, we further design an inexact variant (IHSDA) that preserves the single-loop structure while solving the subproblem approximately via a Lanczos procedure. With high probability, IHSDA achieves the same $\tilde{\mathcal{O}}(\varepsilon^{-3/2})$ iteration complexity and attains an $\mathcal{O}(\varepsilon, \sqrt{\varepsilon})$-second-order stationary point, with the total Hessian-vector product cost bounded by $\tilde{\mathcal{O}}(\varepsilon^{-7/4})$. Experiments on synthetic minimax problems and adversarial training tasks confirm the practical effectiveness and robustness of the proposed algorithms. |
| title | A Homogeneous Second-Order Descent Ascent Algorithm for Nonconvex-Strongly Concave Minimax Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2602.14058 |