Near-Optimal Algorithms for Minimax Optimization

Tianyi Lin, Chi Jin, Michael I. Jordan

Research output: Contribution to journalConference articlepeer-review

94 Scopus citations

Abstract

This paper resolves a longstanding open question pertaining to the design of near-optimal first-order algorithms for smooth and strongly-convex-strongly-concave minimax problems. Current state-of-the-art first-order algorithms find an approximate Nash equilibrium using Õ(κxy) (Tseng, 1995) or Õ(min{κx √κy, √κxκy}) (Alkousa et al., 2019) gradient evaluations, where κx and κy are the condition numbers for the strong-convexity and strong-concavity assumptions. A gap still remains between these results and the best existing lower bound Ω̃(√κxκy) (Ibrahim et al., 2019; Zhang et al., 2019). This paper presents the first algorithm with Õ(√κxκy) gradient complexity, matching the lower bound up to logarithmic factors. Our algorithm is designed based on an accelerated proximal point method and an accelerated solver for minimax proximal steps. It can be easily extended to the settings of strongly-convex-concave, convex-concave, nonconvex-strongly-concave, and nonconvex-concave functions. This paper also presents algorithms that match or outperform all existing methods in these settings in terms of gradient complexity, up to logarithmic factors.

Original languageEnglish (US)
Pages (from-to)2738-2779
Number of pages42
JournalProceedings of Machine Learning Research
Volume125
StatePublished - 2020
Event33rd Conference on Learning Theory, COLT 2020 - Virtual, Online, Austria
Duration: Jul 9 2020Jul 12 2020

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Near-Optimal Algorithms for Minimax Optimization'. Together they form a unique fingerprint.

Cite this