Second-Order Min-Max Optimization with Lazy Hessians
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913793920991232 |
|---|---|
| author | Chen, Lesi Liu, Chengchang Zhang, Jingzhao |
| author_facet | Chen, Lesi Liu, Chengchang Zhang, Jingzhao |
| contents | This paper studies second-order methods for convex-concave minimax optimization. Monteiro and Svaiter (2012) proposed a method to solve the problem with an optimal iteration complexity of $\mathcal{O}(ε^{-3/2})$ to find an $ε$-saddle point. However, it is unclear whether the computational complexity, $\mathcal{O}((N+ d^2) d ε^{-2/3})$, can be improved. In the above, we follow Doikov et al. (2023) and assume the complexity of obtaining a first-order oracle as $N$ and the complexity of obtaining a second-order oracle as $dN$. In this paper, we show that the computation cost can be reduced by reusing Hessian across iterations. Our methods take the overall computational complexity of $ \tilde{\mathcal{O}}( (N+d^2)(d+ d^{2/3}ε^{-2/3}))$, which improves those of previous methods by a factor of $d^{1/3}$. Furthermore, we generalize our method to strongly-convex-strongly-concave minimax problems and establish the complexity of $\tilde{\mathcal{O}}((N+d^2) (d + d^{2/3} κ^{2/3}) )$ when the condition number of the problem is $κ$, enjoying a similar speedup upon the state-of-the-art method. Numerical experiments on both real and synthetic datasets also verify the efficiency of our method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_09568 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Second-Order Min-Max Optimization with Lazy Hessians Chen, Lesi Liu, Chengchang Zhang, Jingzhao Optimization and Control Computational Complexity Cryptography and Security Machine Learning This paper studies second-order methods for convex-concave minimax optimization. Monteiro and Svaiter (2012) proposed a method to solve the problem with an optimal iteration complexity of $\mathcal{O}(ε^{-3/2})$ to find an $ε$-saddle point. However, it is unclear whether the computational complexity, $\mathcal{O}((N+ d^2) d ε^{-2/3})$, can be improved. In the above, we follow Doikov et al. (2023) and assume the complexity of obtaining a first-order oracle as $N$ and the complexity of obtaining a second-order oracle as $dN$. In this paper, we show that the computation cost can be reduced by reusing Hessian across iterations. Our methods take the overall computational complexity of $ \tilde{\mathcal{O}}( (N+d^2)(d+ d^{2/3}ε^{-2/3}))$, which improves those of previous methods by a factor of $d^{1/3}$. Furthermore, we generalize our method to strongly-convex-strongly-concave minimax problems and establish the complexity of $\tilde{\mathcal{O}}((N+d^2) (d + d^{2/3} κ^{2/3}) )$ when the condition number of the problem is $κ$, enjoying a similar speedup upon the state-of-the-art method. Numerical experiments on both real and synthetic datasets also verify the efficiency of our method. |
| title | Second-Order Min-Max Optimization with Lazy Hessians |
| topic | Optimization and Control Computational Complexity Cryptography and Security Machine Learning |
| url | https://arxiv.org/abs/2410.09568 |