{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:16Z","timestamp":1781031436045,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800767","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"489-499","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Min-Max Optimization with Product Constraints"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8594-2528","authenticated-orcid":false,"given":"Martino","family":"Bernasconi","sequence":"first","affiliation":[{"name":"Bocconi University, Milan, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1070-6766","authenticated-orcid":false,"given":"Matteo","family":"Castiglioni","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Milan, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Jacob Abernethy Kevin A Lai and Andre Wibisono. 2021. Last-iterate convergence rates for min-max optimization: Convergence of hamiltonian gradient descent and consensus optimization. In Algorithmic Learning Theory. 3\u201347."},{"key":"e_1_3_2_1_2_1","volume-title":"The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games. In The Thirty-ninth Annual Conference on Neural Information Processing Systems.","author":"Anagnostides Ioannis","year":"2025","unstructured":"Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm, and Jingming Yan. 2025. The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games. In The Thirty-ninth Annual Conference on Neural Information Processing Systems."},{"key":"e_1_3_2_1_3_1","volume-title":"International conference on machine learning. 214\u2013223","author":"Arjovsky Martin","year":"2017","unstructured":"Martin Arjovsky, Soumith Chintala, and L\u00e9on Bottou. 2017. Wasserstein generative adversarial networks. In International conference on machine learning. 214\u2013223."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908734"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451039"},{"key":"e_1_3_2_1_6_1","volume-title":"International Conference on Machine Learning. 354\u2013363","author":"Balduzzi David","year":"2018","unstructured":"David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. 2018. The mechanics of n-player differentiable games. In International Conference on Machine Learning. 354\u2013363."},{"key":"e_1_3_2_1_7_1","unstructured":"Martino Bernasconi and Matteo Castiglioni. 2026. The Complexity of Min-Max Optimization with Product Constraints. arXiv preprint arXiv:2602.04665."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","unstructured":"Martino Bernasconi Matteo Castiglioni Andrea Celli and Gabriele Farina. 2024. On the Role of Constraints in the Complexity of Min-Max Optimization. arxiv:2411.03248. https:\/\/doi.org\/10.48550\/arXiv.2602.04665 10.48550\/arXiv.2602.04665","DOI":"10.48550\/arXiv.2602.04665"},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649623"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1461928.1461951"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.62"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451125"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00022"},{"key":"e_1_3_2_1_15_1","volume-title":"International Conference on Artificial Intelligence and Statistics. 2746\u20132754","author":"Diakonikolas Jelena","year":"2021","unstructured":"Jelena Diakonikolas, Constantinos Daskalakis, and Michael I Jordan. 2021. Efficient methods for structured nonconvex-nonconcave min-max optimization. In International Conference on Artificial Intelligence and Statistics. 2746\u20132754."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3568163"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451052"},{"key":"e_1_3_2_1_18_1","volume-title":"Generative adversarial nets. Advances in neural information processing systems, 27","author":"Goodfellow Ian J","year":"2014","unstructured":"Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. Advances in neural information processing systems, 27 (2014)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"e_1_3_2_1_20_1","volume-title":"The Complexity of Two-Team Polymatrix Games with Independent Adversaries. In The Thirteenth International Conference on Learning Representations.","author":"Hollender Alexandros","year":"2025","unstructured":"Alexandros Hollender, Gilbert Maystre, and Sai Ganesh Nagarajan. 2025. The Complexity of Two-Team Polymatrix Games with Independent Adversaries. In The Thirteenth International Conference on Learning Representations."},{"key":"e_1_3_2_1_21_1","volume-title":"International Conference on Machine Learning. 4337\u20134348","author":"Hsieh Ya-Ping","year":"2021","unstructured":"Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. 2021. The limits of min-max optimization algorithms: Convergence to spurious non-critical sets. In International Conference on Machine Learning. 4337\u20134348."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3418526"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.52202\/079017-2948"},{"key":"e_1_3_2_1_24_1","unstructured":"Naveen Kodali Jacob Abernethy James Hays and Zsolt Kira. 2017. On convergence and stability of gans. arXiv preprint arXiv:1705.07215."},{"key":"e_1_3_2_1_25_1","volume-title":"International conference on machine learning. 6083\u20136093","author":"Lin Tianyi","year":"2020","unstructured":"Tianyi Lin, Chi Jin, and Michael Jordan. 2020. On gradient descent ascent for nonconvex-concave minimax problems. In International conference on machine learning. 6083\u20136093."},{"key":"e_1_3_2_1_26_1","first-page":"1","article-title":"Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization","volume":"26","author":"Lin Tianyi","year":"2025","unstructured":"Tianyi Lin, Chi Jin, and Michael I Jordan. 2025. Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization. Journal of Machine Learning Research, 26, 11 (2025), 1\u201345.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_27_1","unstructured":"Aleksander Madry Aleksandar Makelov Ludwig Schmidt Dimitris Tsipras and Adrian Vladu. 2017. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083."},{"key":"e_1_3_2_1_28_1","first-page":"1","article-title":"On finding local nash equilibria (and only local nash equilibria) in zero-sum games","volume":"2","author":"Mazumdar Eric","year":"2025","unstructured":"Eric Mazumdar, S Shankar Sastry, and Michael I Jordan. 2025. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. ACM\/IMS Journal of Data Science, 2, 2 (2025), 1\u201326.","journal-title":"ACM\/IMS Journal of Data Science"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_3_2_1_30_1","volume-title":"International Conference on Learning Representations.","author":"Mertikopoulos Panayotis","year":"2019","unstructured":"Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. 2019. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_31_1","volume-title":"Forty-first International Conference on Machine Learning.","author":"Munos R\u00e9mi","year":"2024","unstructured":"R\u00e9mi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, C\u00f4me Fiegel, et al. 2024. Nash learning from human feedback. In Forty-first International Conference on Machine Learning."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1337600"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1039274"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055589.3055596"},{"key":"e_1_3_2_1_36_1","volume-title":"Certifying Some Distributional Robustness with Principled Adversarial Training. In International Conference on Learning Representations.","author":"Sinha Aman","year":"2018","unstructured":"Aman Sinha, Hongseok Namkoong, and John Duchi. 2018. Certifying Some Distributional Robustness with Principled Adversarial Training. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_37_1","volume-title":"Efficient algorithms for smooth minimax optimization. Advances in neural information processing systems, 32","author":"Thekumparampil Kiran K","year":"2019","unstructured":"Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. 2019. Efficient algorithms for smooth minimax optimization. Advances in neural information processing systems, 32 (2019)."},{"key":"e_1_3_2_1_38_1","volume-title":"Poincar\u00e9 recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave zero-sum games. Advances in Neural Information Processing Systems, 32","author":"Vlatakis-Gkaragkounis Emmanouil-Vasileios","year":"2019","unstructured":"Emmanouil-Vasileios Vlatakis-Gkaragkounis, Lampros Flokas, and Georgios Piliouras. 2019. Poincar\u00e9 recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave zero-sum games. Advances in Neural Information Processing Systems, 32 (2019)."},{"key":"e_1_3_2_1_39_1","volume-title":"On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach. In International Conference on Learning Representations.","author":"Wang Yuanhao","year":"2019","unstructured":"Yuanhao Wang, Guodong Zhang, and Jimmy Ba. 2019. On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_40_1","volume-title":"On the algorithmic stability of adversarial training. Advances in neural information processing systems, 34","author":"Xing Yue","year":"2021","unstructured":"Yue Xing, Qifan Song, and Guang Cheng. 2021. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 34 (2021), 26523\u201326535."}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800767","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:00:54Z","timestamp":1781028054000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800767"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":40,"alternative-id":["10.1145\/3798129.3800767","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800767","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}