Timezone: »

 
Poster
A Catalyst Framework for Minimax Optimization
Junchi Yang · Siqi Zhang · Negar Kiyavash · Niao He

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #815
in Poster Session 4 »

We introduce a generic \emph{two-loop} scheme for smooth minimax optimization with strongly-convex-concave objectives. Our approach applies the accelerated proximal point framework (or Catalyst) to the associated \emph{dual problem} and takes full advantage of existing gradient-based algorithms to solve a sequence of well-balanced strongly-convex-strongly-concave minimax problems. Despite its simplicity, this leads to a family of near-optimal algorithms with improved complexity over all existing methods designed for strongly-convex-concave minimax problems. Additionally, we obtain the first variance-reduced algorithms for this class of minimax problems with finite-sum structure and establish even faster convergence rate. Furthermore, when extended to the nonconvex-concave minimax optimization, our algorithm again achieves the state-of-the-art complexity for finding a stationary point. We carry out several numerical experiments showcasing the superiority of the Catalyst framework in practice.

Author Information

Junchi Yang (University of Illinois)
Siqi Zhang (University of Illinois at Urbana-Champaign)
Negar Kiyavash (École Polytechnique Fédérale de Lausanne)
Niao He (ETH Zurich)

More from the Same Authors