The Complexity of Gradient Descent: CLS = PPAD PLS
John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani
Code Available — Be the first to reproduce this paper.
ReproduceCode
- github.com/jfearnley/PPADPLSOfficialIn papernone★ 6
Abstract
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 PLS-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) - which was defined by Daskalakis and Papadimitriou as a more "natural" counterpart to PPAD PLS and contains many interesting problems - is itself equal to PPAD PLS.