Timezone: »
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
-
2022 Poster: Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequality »
Jalal Etesami · Ilyas Fatkhullin · Niao He · Negar Kiyavash -
2022 Poster: Causal Discovery in Linear Latent Variable Models Subject to Measurement Error »
Yuqin Yang · AmirEmad Ghassami · Mohamed Nafea · Negar Kiyavash · Kun Zhang · Ilya Shpitser -
2022 Poster: Stochastic Second-Order Methods Provably Beat SGD For Gradient-Dominated Functions »
Mohammadsaeed Masiha · Saber Salehkaleybar · Niao He · Negar Kiyavash · Patrick Thiran -
2021 Poster: Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias »
Sina Akbari · Ehsan Mokhtarian · AmirEmad Ghassami · Negar Kiyavash -
2021 Poster: On the Bias-Variance-Cost Tradeoff of Stochastic Optimization »
Yifan Hu · Xin Chen · Niao He -
2020 Poster: Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning »
Yifan Hu · Siqi Zhang · Xin Chen · Niao He -
2020 Poster: Global Convergence and Variance Reduction for a Class of Nonconvex-Nonconcave Minimax Problems »
Junchi Yang · Negar Kiyavash · Niao He -
2020 Poster: A Unified Switching System Perspective and Convergence Analysis of Q-Learning Algorithms »
Donghwan Lee · Niao He -
2020 Poster: The Devil is in the Detail: A Framework for Macroscopic Prediction via Microscopic Models »
Yingxiang Yang · Negar Kiyavash · Le Song · Niao He -
2020 Poster: The Mean-Squared Error of Double Q-Learning »
Wentao Weng · Harsh Gupta · Niao He · Lei Ying · R. Srikant -
2020 Spotlight: The Devil is in the Detail: A Framework for Macroscopic Prediction via Microscopic Models »
Yingxiang Yang · Negar Kiyavash · Le Song · Niao He