Poster
Second-Order Min-Max Optimization with Lazy Hessians
Lesi Chen · Chengchang Liu · Jingzhao Zhang
Hall 3 + Hall 2B #585
[
Abstract
]
Oral
presentation:
Oral Session 5D
Fri 25 Apr 7:30 p.m. PDT — 9 p.m. PDT
Sat 26 Apr midnight PDT
— 2:30 a.m. PDT
Fri 25 Apr 7:30 p.m. PDT — 9 p.m. PDT
Abstract:
This paper studies second-order methods for convex-concave minimax optimization. Monteiro & Svaiter (2012) proposed a method to solve the problem with an optimal iteration complexity of O(ϵ−3/2) to find an ϵ-saddle point. However, it is unclear whether thecomputational complexity, O((N+d2)dϵ−2/3), can be improved. In the above, we follow Doikov et al. (2023) and assume the complexity of obtaining a first-order oracle as N and the complexity of obtaining a second-order oracle as dN. In this paper, we show that the computation cost can be reduced by reusing Hessian across iterations. Our methods take the overall computational complexity of ~O((N+d2)(d+d2/3ϵ−2/3)), which improves those of previous methods by a factor of d1/3. Furthermore, we generalize our method to strongly-convex-strongly-concave minimax problems and establish the complexity of ~O((N+d2)(d+d2/3κ2/3)) when the condition number of the problem is κ, enjoying a similar speedup upon the state-of-the-art method. Numerical experiments on both real and synthetic datasets also verify the efficiency of our method.
Live content is unavailable. Log in and register to view live content