SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems

Xuan Zhang, Necdet Serhat Aybat, Mert Gürbüzbalaban

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

We propose a new stochastic method SAPD+ for solving nonconvex-concave minimax problems of the form min max L(x, y) = f(x) + Φ(x, y) − g(y), where f, g are closed convex and Φ(x, y) is a smooth function that is weakly convex in x, (strongly) concave in y. For both strongly concave and merely concave settings, SAPD+ achieves the best known oracle complexities of O(Lκy−4) and O(L3−6), respectively, without assuming compactness of the problem domain, where κy is the condition number and L is the Lipschitz constant. We also propose SAPD+ with variance reduction, which enjoys the best known oracle complexity of O(Lκ2y−3) for weakly convex-strongly concave setting. We demonstrate the efficiency of SAPD+ on a distributionally robust learning problem with a nonconvex regularizer and also on a multi-class classification problem in deep learning.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022
EditorsS. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh
PublisherNeural information processing systems foundation
ISBN (Electronic)9781713871088
StatePublished - 2022
Event36th Conference on Neural Information Processing Systems, NeurIPS 2022 - New Orleans, United States
Duration: Nov 28 2022Dec 9 2022

Publication series

NameAdvances in Neural Information Processing Systems
Volume35
ISSN (Print)1049-5258

Conference

Conference36th Conference on Neural Information Processing Systems, NeurIPS 2022
Country/TerritoryUnited States
CityNew Orleans
Period11/28/2212/9/22

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Cite this