On the Linear Convergence of Extragradient Methods for Nonconvex–Nonconcave Minimax Problems

References

• Alves MM, Monteiro RDC, Svaiter BF (2016) Regularized HPE-type methods for solving monotone inclusions with improved pointwise iteration-complexity bounds. SIAM J. Optim. 26(4):2730–2743.Google Scholar
• Attouch H, Aze D, Wets RJB (1986) On continuity properties of the partial Legendre-Fenchel transform: Convergence of sequences of augmented Lagrangian functions, Moreau-Yosida approximates and subdifferential operators. Hiriart-Urruty JB, ed. Fermat Days 85: Mathematics for Optimization, vol. 129 (Elsevier, Amsterdam), 1–42.Google Scholar
• Bauschkel HH, Moursi WM, Xianfu Wang X (2021) Generalized monotone operators and their averaged resolvents. Math. Programming 189(September):55–74.Google Scholar
• Chambolle A, Pock T (2011) A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40(May):120–145.Google Scholar
• Daskalakis C, Panageas I (2018) The limit points of (optimistic) gradient descent in min-max optimization. Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, eds. Proc. 32nd Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 9256–9266.Google Scholar
• Daskalakis C, Ilyas A, Syrgkanis V, Zeng H (2018) Training GANs with optimism. Proc. Internat. Conf. Learn. Representations (Vancouver).Google Scholar
• Diakonikolas J, Daskalakis C, Jordan MI (2021) Efficient methods for structured nonconvex-nonconcave min-max optimization. Banerjee A, Fukumizu K, eds. Proc. 24th Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 2746–2754.Google Scholar
• Douglas J Jr, Rachford HH Jr (1956) On the numerical solution of heat conduction problems in two and three space variables. Amer. Math. Soc. 82(1):421–439.Google Scholar
• Eckstein J, Bertsekas DP (1992) On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Programming 55:293–318.Google Scholar
• Gidel G, Berard H, Vignoud G, Vincent P, Lacoste-Julien S (2020) A variational inequality perspective on generative adversarial networks. Proc. 7th Internat. Conf. Learn. Representations (New Orleans).Google Scholar
• Goodfellow I, Pouget-Abadie J, Mirza M, Xu B, Warde-Farley D, Ozair S, Courville A, Bengio Y (2014) Generative adversarial nets. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Proc. 27th Internat. Conf. Neural Inform. Processing Systems, vol. 2 (MIT Press, Cambridge, MA), 2672–2680.Google Scholar
• Grimmer B, Lu H, Worah P, Mirrokni V (2022a) The landscape of the proximal point method for nonconvex–nonconcave minimax optimization. Math. Programming 1–35.Google Scholar
• Grimmer B, Lu H, Worah P, Mirrokni V (2022b) Limiting behaviors of nonconvex-nonconcave minimax optimization via continuous-time systems. Dasgupta S, Haghtalab N, eds. Proc. 33rd Internat. Conf. Algorithmic Learn. Theory, vol. 167 (PMLR, New York), 465–487.Google Scholar
• Jin C, Netrapalli P, Jordan MI (2020) What is local optimality in nonconvex-nonconcave minimax optimization? Daumé H III, Singh A, eds. Proc. 37th Internat. Conf. Machine Learning, vol. 119 (PMLR, New York), 4880–4889.Google Scholar
• Lee S, Kim D (2021) Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. Ranzato M, Liang PS, Vaughan JW, Beygelzimer A, Dauphin Y, eds. Advances in Neural Information Processing Systems, vol. 34 (Curran Associates, Red Hook, NY), 1–13.Google Scholar
• Lu H (2021) An o(sr)-resolution ode framework for understanding discrete-time algorithms and applications to the linear convergence of minimax problems. Math. Programming 194:1061–1112.Google Scholar
• Madry A, Makelov A, Schmidt L, Tsipras D, Vladu A (2017) Toward deep learning models resistant to adversarial attacks. Preprint, submitted June 19, https://arxiv.org/abs/1706.06083.Google Scholar
• Mokhtari A, Ozdaglar A, Pattathil S (2020) A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. Proc. 23rd Internat. Conf. Artificial Intelligence Statist., vol. 108 (PMLR, New York), 1497–1507.Google Scholar
• Monteiro RDC, Svaiter BF (2010) On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM J. Optim. 20(6):2755–2787.Google Scholar
• Myerson RB (1997) Game Theory: Analysis of Conflict (Harvard University Press, Boston).Google Scholar
• Nemirovski A (2004) Prox-method with rate of convergence o(1t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Control Optim. 15(1):229–251.Google Scholar
• Nesterov Y (2005) Smooth minimization of non-smooth functions. Math. Programming 103(1):127–152.Google Scholar
• O’Connor D, Vandenberghe L (2020) On the equivalence of the primal-dual hybrid gradient method and Douglas–Rachford splitting. Math. Programming 179:85–108.Google Scholar
• Omidshafiei S, Pazis J, Amato C, How JP, Vian J (2017) Deep decentralized multi-task multi-agent reinforcement learning under partial observability. Precup D, The YW, eds. Proc. 34th Internat. Conf. Machine Learn. (PMLR, New York), 2681–2690.Google Scholar
• Pethick T, Latafat P, Patrinos P, Fercoq O, Cevher V (2022) Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems. Proc. Internat. Conf. Learn. Representations (ICLR).Google Scholar
• Rockafellar RT (1976) Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5):877–898.Google Scholar
• Tseng P (1995) On linear convergence of iterative methods for the variational inequality problem. J. Comput. Appl. Math. 60(1–2):237–252.Google Scholar
• Yang J, Kiyavash N, He N (2020) Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Red Hook, NY), 1–71.Google Scholar
• Zhang G, Poupart P, Yu Y (2022) Optimality and stability in non-convex smooth games. J. Machine Learn. Res. 23:1–71.Google Scholar