{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T09:13:47Z","timestamp":1781169227094,"version":"3.54.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T00:00:00Z","timestamp":1671408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,2,28]]},"abstract":"<jats:p>\n            We study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain and show that this class is equal to the intersection of two well-known classes: PPAD and PLS. As our main underlying technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a continuously differentiable function over the domain [0,1]\n            <jats:sup>2<\/jats:sup>\n            is PPAD\u00a0\u2229\u00a0PLS-complete. This is the first non-artificial problem to be shown complete for this class. Our results also imply that the class CLS (Continuous Local Search) \u2013 which was defined by Daskalakis and Papadimitriou as a more \u201cnatural\u201d counterpart to PPAD\u00a0\u2229\u00a0PLS and contains many interesting problems \u2013 is itself equal to PPAD\u00a0\u2229\u00a0PLS.\n          <\/jats:p>","DOI":"10.1145\/3568163","type":"journal-article","created":{"date-parts":[[2022,10,17]],"date-time":"2022-10-17T13:07:21Z","timestamp":1666012041000},"page":"1-74","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["The Complexity of Gradient Descent: CLS = PPAD \u2229 PLS"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0791-4342","authenticated-orcid":false,"given":"John","family":"Fearnley","sequence":"first","affiliation":[{"name":"University of Liverpool, Liverpool, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5436-7890","authenticated-orcid":false,"given":"Paul","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5255-9349","authenticated-orcid":false,"given":"Alexandros","family":"Hollender","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1262-7831","authenticated-orcid":false,"given":"Rahul","family":"Savani","sequence":"additional","affiliation":[{"name":"University of Liverpool, Liverpool, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,12,19]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07557-0_2"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2021.108119"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01714-2"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/070697926"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451039"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1575"},{"key":"e_1_3_3_8_2","volume-title":"Nonlinear Programming","author":"Bertsekas Dimitri P.","year":"1999","unstructured":"Dimitri P. Bertsekas. 1999. Nonlinear Programming. Athena Scientific."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-6080(05)80010-3"},{"key":"e_1_3_3_10_2","first-page":"940","volume-title":"Proceedings of the 33rd Conference on Learning Theory (COLT\u201920)","author":"Bubeck S\u00e9bastien","year":"2020","unstructured":"S\u00e9bastien Bubeck and Dan Mikulincer. 2020. How to trap a gradient flow. In Proceedings of the 33rd Conference on Learning Theory (COLT\u201920). PMLR, 940\u2013960. http:\/\/proceedings.mlr.press\/v125\/bubeck20b.html."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/1009378.1009542"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2012.01.015"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01406-y"},{"key":"e_1_3_3_14_2","first-page":"536","article-title":"M\u00e9thode g\u00e9n\u00e9rale pour la r\u00e9solution des syst\u00e8mes d\u2019\u00e9quations simultan\u00e9es","volume":"25","author":"Cauchy Augustin-Louis","year":"1847","unstructured":"Augustin-Louis Cauchy. 1847. M\u00e9thode g\u00e9n\u00e9rale pour la r\u00e9solution des syst\u00e8mes d\u2019\u00e9quations simultan\u00e9es. Comptes rendus de l\u2019Acad\u00e9mie des Sciences Paris 25 (1847), 536\u2013538.","journal-title":"Comptes rendus de l\u2019Acad\u00e9mie des Sciences Paris"},{"key":"e_1_3_3_15_2","first-page":"624","volume-title":"Proceedings of the 32nd Conference on Learning Theory (COLT\u201919)","author":"Chatziafratis Vaggos","year":"2019","unstructured":"Vaggos Chatziafratis, Tim Roughgarden, and Joshua R. Wang. 2019. On the computational power of online gradient descent. In Proceedings of the 32nd Conference on Learning Theory (COLT\u201919). PMLR, Phoenix, 624\u2013662. http:\/\/proceedings.mlr.press\/v99\/chatziafratis19a.html."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.29"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.052"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316400"},{"key":"e_1_3_3_20_2","unstructured":"Chuangyin Dang Qi Qi and Yinyu Ye. 2020. Computations and complexities of Tarski\u2019s fixed points and supermodular games. (2020). arxiv:2005.09836"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.62"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451125"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188968"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3280847"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-012-9920-5"},{"key":"e_1_3_3_28_2","first-page":"18:1\u201318:19","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920)","author":"Etessami Kousha","year":"2020","unstructured":"Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. 2020. Tarski\u2019s Theorem, supermodular games, and the complexity of equilibria. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Seattle, 18:1\u201318:19. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2020.18"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/080720826"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007445"},{"key":"e_1_3_3_31_2","unstructured":"John Fearnley Spencer Gordon Ruta Mehta and Rahul Savani. 2017. CLS: New problems and completeness. (2017). arxiv:1702.06017"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.05.007"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3524044"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746558"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.05.004"},{"key":"e_1_3_3_36_2","first-page":"33:1\u201333:15","volume-title":"Proceedings of the 37th Computational Complexity Conference (CCC\u201922)","author":"G\u00f6\u00f6s Mika","year":"2022","unstructured":"Mika G\u00f6\u00f6s, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao. 2022. Further collapses in TFNP. In Proceedings of the 37th Computational Complexity Conference (CCC\u201922). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Philadelphia, 33:1\u201333:15. DOI:https:\/\/doi.org\/10.4230\/LIPICS.CCC.2022.33"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1118014"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.03.004"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451055"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3418526"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/120874655"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/280635"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(80)90098-1"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032338"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.87"},{"key":"e_1_3_3_48_2","volume-title":"Classification of search problems and their definability in bounded arithmetic","author":"Morioka Tsuyoshi","year":"2001","unstructured":"Tsuyoshi Morioka. 2001. Classification of search problems and their definability in bounded arithmetic. Master\u2019s thesis. University of Toronto. https:\/\/www.collectionscanada.ca\/obj\/s4\/f2\/dsk3\/ftp04\/MQ58775.pdf."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592948"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221030"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729586"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-9274(95)00014-L"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1137\/0803004"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568163","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3568163","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:42Z","timestamp":1750183722000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,19]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2,28]]}},"alternative-id":["10.1145\/3568163"],"URL":"https:\/\/doi.org\/10.1145\/3568163","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,19]]},"assertion":[{"value":"2021-06-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}