TY - GEN
T1 - SAPD+
T2 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022
AU - Zhang, Xuan
AU - Aybat, Necdet Serhat
AU - Gürbüzbalaban, Mert
N1 - Publisher Copyright:
© 2022 Neural information processing systems foundation. All rights reserved.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85144327502
UR - https://www.scopus.com/pages/publications/85144327502#tab=citedBy
M3 - Conference contribution
AN - SCOPUS:85144327502
T3 - Advances in Neural Information Processing Systems
BT - Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022
A2 - Koyejo, S.
A2 - Mohamed, S.
A2 - Agarwal, A.
A2 - Belgrave, D.
A2 - Cho, K.
A2 - Oh, A.
PB - Neural information processing systems foundation
Y2 - 28 November 2022 through 9 December 2022
ER -