Explicit second-order min-max optimization methods with optimal convergence guarantees

Tianyi Lin (1) , Panayotis Mertikopoulos (2) , Michael I Jordan (1, 3)

1 Berkeley EECS - Department of Electrical Engineering and Computer Sciences
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
3 Department of Statistics [Berkeley]

We propose and analyze exact and inexact regularized Newton-type methods for finding a global saddle point of a convex-concave unconstrained min-max optimization problem. Compared to their first-order counterparts, investigations of second-order methods for min-max optimization are relatively limited, as obtaining global rates of convergence with second-order information is much more involved. In this paper, we highlight how second-order information can be used to speed up the dynamics of dual extrapolation methods despite inexactness. Specifically, we show that the proposed algorithms generate iterates that remain within a bounded set and the averaged iterates converge to an ϵ-saddle point within O(ϵ −2/3) iterations in terms of a gap function. Our algorithms match the theoretically established lower bound in this context and our analysis provides a simple and intuitive convergence analysis for second-order methods without requiring any compactness assumptions. Finally, we present a series of numerical experiments on synthetic and real data that demonstrate the efficiency of the proposed algorithms.

Domaines: Optimisation et contrôle [math.OC]

Tianyi Lin, Panayotis Mertikopoulos, Michael I Jordan. Explicit second-order min-max optimization methods with optimal convergence guarantees. 2022. ⟨hal-03873989⟩