Explicit second-order min-max optimization: Practical algorithms and complexity analysis
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 generate iterates that remain within a bounded set and that the averaged iterates converge to an ϵ-saddle point within O(ϵ−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(loglog(1/ϵ)) 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(loglog(1/ϵ)) 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.
Related
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- On the complexity of two-stage stochastic linear optimization with small second stage
- Explicit second moments of symplectic Siegel transforms
- Second-order regularity for weighted widely degenerate problems with explicit u-dependence
- Accelerated Convergence of a Second-Order Dynamical System and its Application to Splitting Algorithms for Comonotone Inclusions
BibTeX
@article{lin2026explicit,
title = {{Explicit second-order min-max optimization: Practical algorithms and complexity analysis}},
author = {Tianyi Lin and Panayotis Mertikopoulos and Michael I. Jordan},
journal = {Transactions on Machine Learning Research},
year = {2026},
month = may,
eprint = {2210.12860},
archivePrefix = {arXiv},
url = {https://hal.science/hal-03873989v2},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Explicit second-order min-max optimization: Practical algorithms and complexity analysis
AU - Tianyi Lin
AU - Panayotis Mertikopoulos
AU - Michael I. Jordan
PY - 2026
DA - 2026/05/26
JO - Transactions on Machine Learning Research
UR - https://hal.science/hal-03873989v2
AB - 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 ϵ-saddle point within O(ϵ^−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(loglog(1/ϵ)) 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(loglog(1/ϵ)) 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.
SN - 2835-8856
ER -