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

About

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 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 $\cap$ PLS and contains many interesting problems - is itself equal to PPAD $\cap$ PLS.

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

Related benchmarks

Task	Dataset	Result
Decision Making under Imperfect Recall	Detection Game Benchmarks 1.0 (full set)	Value Score18	11
Decision Making under Imperfect Recall	Random (Rand) Game Benchmarks 1.0 (full set)	Value0.55	8
Decision Making under Imperfect Recall	61 aggregate benchmark instances (Sim, Det, and Rand)	Utility (% of Best)44.3	8
Global optimization in single-player IREFGs	Randomly generated single-player IREFGs 1.0 (50 random instances)	SOS Time (s)—	8
Simulation Problem	Sim 540k	Value Score8.54	7
Subgroup Detection	Det 1k	Detection Value13	7
Random Problem	Rand-24k	Value66	7
Decision Making under Imperfect Recall	Simulation (Sim) Game Benchmarks 1.0 (full set)	Value10.38	6
Subgroup Detection	Det-2.2m	Performance Score16.2	6
Subgroup Detection	Det 10m	Performance Value24.64	6