@inproceedings{
jiang2024adaptive,
title={Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization},
author={Ruichen Jiang and Ali Kavis and Qiujiang Jin and sujay sanghavi and Aryan Mokhtari},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=NVDYgEFXCy}
}
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.
Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization
Ruichen Jiang Ali Kavis Qiujiang Jin sujay sanghavi Aryan Mokhtari