Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929587464699904 |
|---|---|
| author | Jiang, Ruichen Kavis, Ali Jin, Qiujiang Sanghavi, Sujay Mokhtari, Aryan |
| author_facet | Jiang, Ruichen Kavis, Ali Jin, Qiujiang Sanghavi, Sujay Mokhtari, Aryan |
| contents | We propose adaptive, line search-free second-order methods with optimal rate of convergence for solving convex-concave min-max problems. By means of an adaptive step size, our algorithms feature a simple update rule that requires solving only one linear system per iteration, eliminating the need for line search or backtracking mechanisms. Specifically, we base our algorithms on the optimistic method and appropriately combine it with second-order information. Moreover, distinct from common adaptive schemes, we define the step size recursively as a function of the gradient norm and the prediction error in the optimistic update. We first analyze a variant where the step size requires knowledge of the Lipschitz constant of the Hessian. Under the additional assumption of Lipschitz continuous gradients, we further design a parameter-free version by tracking the Hessian Lipschitz constant locally and ensuring the iterates remain bounded. We also evaluate the practical performance of our algorithm by comparing it to existing second-order algorithms for minimax optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_02016 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization Jiang, Ruichen Kavis, Ali Jin, Qiujiang Sanghavi, Sujay Mokhtari, Aryan Optimization and Control Machine Learning We propose adaptive, line search-free second-order methods with optimal rate of convergence for solving convex-concave min-max problems. By means of an adaptive step size, our algorithms feature a simple update rule that requires solving only one linear system per iteration, eliminating the need for line search or backtracking mechanisms. Specifically, we base our algorithms on the optimistic method and appropriately combine it with second-order information. Moreover, distinct from common adaptive schemes, we define the step size recursively as a function of the gradient norm and the prediction error in the optimistic update. We first analyze a variant where the step size requires knowledge of the Lipschitz constant of the Hessian. Under the additional assumption of Lipschitz continuous gradients, we further design a parameter-free version by tracking the Hessian Lipschitz constant locally and ensuring the iterates remain bounded. We also evaluate the practical performance of our algorithm by comparing it to existing second-order algorithms for minimax optimization. |
| title | Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2406.02016 |