Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee

arXiv:2210.12860v4 Announce Type: replace-cross
Abstract: We propose and analyze several inexact regularized Newton-type methods for finding a global saddle point of \emph{convex-concave} unconstrained min-max optimization problems. Compared to first-order methods, our understanding of second-order methods for min-max optimization is relatively limited, as obtaining global rates of convergence with second-order information is much more involved. In this paper, we examine how second-order information can be used to speed up extra-gradient methods, even under inexactness. Specifically, we show that the proposed methods …

abstract analyze arxiv convergence cs.cc cs.lg global information math.oc max min optimization type understanding