The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS

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]^2$ is PPAD
$\cap$ PLS-complete. This is the first natural problem to be shown complete for
this class. Our results also imply that the class CLS (Continuous Local Search)
- which was defined by Daskalakis and Papadimitriou as a more "natural"
counterpart to PPAD $\cap$ PLS and contains many interesting problems - is
itself equal to PPAD $\cap$ PLS.

Authors

John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani