The Complexity of Gradient Descent (Invited Talk)

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].