2026-07-22T21:03:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15516 2024-03-06T10:55:29Z ddc:004 open_access

The Complexity of Gradient Descent (Invited Talk) Savani, Rahul Computational Complexity Continuous Optimization TFNP PPAD PLS CLS UEOPL PPAD and PLS are successful classes that capture the complexity of important game-theoretic problems. For example, finding a mixed Nash equilibrium in a bimatrix game is PPAD-complete, and finding a pure Nash equilibrium in a congestion game is PLS-complete. Many important problems, such as solving a Simple Stochastic Game or finding a mixed Nash equilibrium of a congestion game, lie in both classes. It was strongly believed that their intersection, PPAD ∩ PLS, does not have natural complete problems. We show that it does: any problem that lies in both classes can be reduced in polynomial time to the problem of finding a stationary point of a continuously differentiable function on the domain [0,1]². Thus, as PPAD captures problems that can be solved by Lemke-Howson type complementary pivoting algorithms, and PLS captures problems that can be solved by local search, we show that PPAD ∩ PLS exactly captures problems that can be solved by Gradient Descent. This is joint work with John Fearnley, Paul Goldberg, and Alexandros Hollender. It appeared at STOC'21, where it was given a Best Paper Award [Fearnley et al., 2021]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rahul Savani 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.5 urn:nbn:de:0030-drops-155167 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.5 eng https://creativecommons.org/licenses/by/4.0/legalcode