{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:15:27Z","timestamp":1787505327154,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"funder":[{"name":"DARPA","award":["HR00111990021"],"award-info":[{"award-number":["HR00111990021"]}]},{"name":"NRF","award":["NRF-NRFF2018-07"],"award-info":[{"award-number":["NRF-NRFF2018-07"]}]},{"name":"NSF","award":["S-1741137, CCF-1617730, CCF-190129"],"award-info":[{"award-number":["S-1741137, CCF-1617730, CCF-190129"]}]},{"name":"Simons Foundations","award":["Investigator Award"],"award-info":[{"award-number":["Investigator Award"]}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Ph.D. Fellowship"],"award-info":[{"award-number":["Ph.D. Fellowship"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451125","type":"proceedings-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T21:26:13Z","timestamp":1623792373000},"page":"1466-1478","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["The complexity of constrained min-max optimization"],"prefix":"10.1145","author":[{"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stratis","family":"Skoulakis","sequence":"additional","affiliation":[{"name":"Singapore University of Technology and Design, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manolis","family":"Zampetakis","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Jacob Abernethy Kevin A Lai and Andre Wibisono. 2019. Last-iterate convergence rates for min-max optimization."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-012-0328-8"},{"key":"e_1_3_2_1_3_1","first-page":"495","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics","author":"Adolphs Leonard","year":"2019","unstructured":"Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. 2019. Local saddle point optimization: A curvature exploitation approach. The 22nd International Conference on Artificial Intelligence and Statistics, 2019. Pages 486\u2013495."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055464"},{"key":"e_1_3_2_1_5_1","first-page":"223","volume-title":"Proceedings of the 34th International Conference on Machine Learning-Volume 70","author":"Arjovsky Martin","year":"2017","unstructured":"Martin Arjovsky, Soumith Chintala, and L\u00e9on Bottou. 2017. Wasserstein generative adversarial networks. Proceedings of the 34th International Conference on Machine Learning-Volume 70, 2017. Pages 214\u2013223."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1956.6.1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000024"},{"key":"e_1_3_2_1_8_1","volume-title":"Prediction, Learning, and Games","author":"Cesa-Bianchi Nikolo","unstructured":"Nikolo Cesa-Bianchi and Gabor Lugosi. 2006. Prediction, Learning, and Games. Cambridge University Press."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_1_10_1","volume-title":"A proof of the equivalence of the programming problem and the game probslem","author":"Dantzig George B.","year":"1951","unstructured":"George B. Dantzig. 1951. A proof of the equivalence of the programming problem and the game probslem. Koopmans, T. C., editor(s), Activity Analysis of Production and Allocation, 1951."},{"key":"e_1_3_2_1_11_1","first-page":"209","volume-title":"Proceedings of the International Congress of Mathematicians (ICM), 1","author":"Daskalakis Constantinos","year":"2018","unstructured":"Constantinos Daskalakis. 2018. Equilibria, Fixed Points, and Computational Complexity - Nevanlinna Prize Lecture. Proceedings of the International Congress of Mathematicians (ICM), 1, 2018. Pages 147\u2013209."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_3_2_1_13_1","volume-title":"International Conference on Learning Representations (ICLR","author":"Daskalakis Constantinos","year":"2018","unstructured":"Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. 2018. Training GANs with Optimism.. In International Conference on Learning Representations (ICLR 2018)."},{"key":"e_1_3_2_1_14_1","unstructured":"Constantinos Daskalakis and Ioannis Panageas. 2018. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems. Pages 9236\u20139246."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Constantinos Daskalakis Stratis Skoulakis and Manolis Zampetakis. 2020. The complexity of constrained min-max optimization.","DOI":"10.1145\/3406325.3451125"},{"key":"e_1_3_2_1_16_1","article-title":"Adaptive subgradient methods for online learning and stochastic optimization","volume":"12","author":"Duchi John","year":"2011","unstructured":"John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12, Jul, 2011. Pages 2121\u20132159.","journal-title":"Journal of machine learning research"},{"key":"e_1_3_2_1_17_1","unstructured":"Paul Erd\\H os and L\u00e1szl\u00f3 Lov\u00e1sz. 1973. Problems and results on 3-chromatic hypergraphs and some related questions. In Colloquia Mathematica Societatis Janos Bolyai 10. Infinite and Finite Sets Keszthely (Hungary)."},{"key":"e_1_3_2_1_18_1","volume-title":"Finite-dimensional variational inequalities and complementarity problems","author":"Facchinei Francisco","unstructured":"Francisco Facchinei and Jong-Shi Pang. 2007. Finite-dimensional variational inequalities and complementarity problems. Springer Science & Business Media."},{"key":"e_1_3_2_1_19_1","volume-title":"NIPS 2016 tutorial: Generative adversarial networks. arXiv preprint arXiv:1701","author":"Goodfellow Ian","year":"2016","unstructured":"Ian Goodfellow. 2016. NIPS 2016 tutorial: Generative adversarial networks. arXiv preprint arXiv:1701.00160, 2016."},{"key":"e_1_3_2_1_20_1","volume-title":"Generative Adversarial Nets. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014","author":"Goodfellow Ian J.","year":"2014","unstructured":"Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. 2014. Generative Adversarial Nets. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada. Pages 2672\u20132680."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1561\/2400000013"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"e_1_3_2_1_23_1","first-page":"1732","volume-title":"Proceedings of the 34th International Conference on Machine Learning-Volume 70","author":"Jin Chi","year":"2017","unstructured":"Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. 2017. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Learning-Volume 70. Pages 1724\u20131732."},{"key":"e_1_3_2_1_24_1","volume-title":"What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization? arXiv preprint arXiv:1902.00618","author":"Jin Chi","year":"2019","unstructured":"Chi Jin, Praneeth Netrapalli, and Michael I Jordan. 2019. What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization? arXiv preprint arXiv:1902.00618, 2019."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_3_2_1_26_1","volume-title":"Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980","author":"Kingma Diederik P","year":"2014","unstructured":"Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014."},{"key":"e_1_3_2_1_27_1","first-page":"1976","article-title":"The extragradient method for finding saddle points and other problems","volume":"12","author":"Korpelevich GM","year":"1976","unstructured":"GM Korpelevich. 1976. The extragradient method for finding saddle points and other problems. Matecon, 12, 1976. Pages 747\u2013756.","journal-title":"Matecon"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01374-3"},{"key":"e_1_3_2_1_29_1","volume-title":"International Conference on Learning Representations.","author":"Madry Aleksander","year":"2018","unstructured":"Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. 2018. Towards Deep Learning Models Resistant to Adversarial Attacks. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_30_1","volume-title":"On the convergence of gradient-based learning in continuous games. arXiv preprint arXiv:1804.05464","author":"Mazumdar Eric","year":"2018","unstructured":"Eric Mazumdar and Lillian J Ratliff. 2018. On the convergence of gradient-based learning in continuous games. arXiv preprint arXiv:1804.05464, 2018."},{"key":"e_1_3_2_1_31_1","unstructured":"N Meggido and CH Papadimitriou. 1989. A note on total functions existence theorems and computational complexity."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175476"},{"key":"e_1_3_2_1_33_1","volume-title":"International Conference on Machine Learning. Pages 3481\u20133490","author":"Mescheder Lars","year":"2018","unstructured":"Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. 2018. Which Training Methods for GANs do actually Converge? In International Conference on Machine Learning. Pages 3481\u20133490."},{"key":"e_1_3_2_1_34_1","volume-title":"Unrolled generative adversarial networks. arXiv preprint arXiv:1611.02163","author":"Metz Luke","year":"2016","unstructured":"Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. 2016. Unrolled generative adversarial networks. arXiv preprint arXiv:1611.02163, 2016."},{"key":"e_1_3_2_1_35_1","volume-title":"Interior point polynomial time methods in convex programming. Lecture notes","author":"Nemirovski Arkadi","year":"2004","unstructured":"Arkadi Nemirovski. 2004. Interior point polynomial time methods in convex programming. Lecture notes, 2004."},{"key":"e_1_3_2_1_36_1","volume-title":"Problem complexity and method efficiency in optimization","author":"Nemirovsky Semenovich","unstructured":"Arkadi\\u \\i Semenovich Nemirovsky and David Borisovich Yudin. 1983. Problem complexity and method efficiency in optimization.. Chichester: Wiley."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 6th International Conference on Learning Representations (ICLR).","author":"Reddi Sashank J.","year":"2018","unstructured":"Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. 2018. On the Convergence of Adam and Beyond. In Proceedings of the 6th International Conference on Learning Representations (ICLR)."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.2307\/1911749"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.35"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"e_1_3_2_1_42_1","volume-title":"Understanding machine learning: From theory to algorithms","author":"Shalev-Shwartz Shai","unstructured":"Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding machine learning: From theory to algorithms. Cambridge university press."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451125","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451125","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:24:53Z","timestamp":1750181093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":43,"alternative-id":["10.1145\/3406325.3451125","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451125","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}