  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 generate iterates that remain within a
bounded set and that the averaged iterates converge to an $\epsilon$-saddle
point within $O(\epsilon^{-2/3})$ iterations in terms of a restricted gap
function. This matched the theoretically established lower bound in this
context. We also provide a simple routine for solving the subproblem at each
iteration, requiring a single Schur decomposition and $O(\log\log(1/\epsilon))$
calls to a linear system solver in a quasi-upper-triangular system. Thus, our
method improves the existing line-search-based second-order min-max
optimization methods by shaving off an $O(\log\log(1/\epsilon))$ factor in the
required number of Schur decompositions. Finally, we present numerical
experiments on synthetic and real data that demonstrate the efficiency of the
proposed methods.
