The Complexity of Gradient Descent: CLS = PPAD ∧ PLS



Fearnley, John, Goldberg, Paul W, Hollender, Alexandros and Savani, Rahul ORCID: 0000-0003-1262-7831
(2021) The Complexity of Gradient Descent: CLS = PPAD ∧ PLS. STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, abs/20. pp. 46-59.

This is the latest version of this item.

Access the full-text of this item by clicking on the Open Access link.
[img] Text
2011.01929v1.pdf - Submitted version

Download (1MB) | Preview
[img] Text
stoc-elements.pdf - Author Accepted Manuscript

Download (880kB) | Preview

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 $\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.

Item Type: Article
Additional Information: Journal version
Uncontrolled Keywords: TFNP, computational complexity, continuous optimization
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 21 Jun 2021 08:22
Last Modified: 08 Jan 2024 16:09
DOI: 10.1145/3406325.3451052
Open Access URL: https://dl.acm.org/doi/pdf/10.1145/3406325.3451052
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3126955

Available Versions of this Item