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.
Text
2011.01929v1.pdf - Submitted version Download (1MB) | Preview |
|
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
-
The Complexity of Gradient Descent: CLS = PPAD boolean AND PLS. (deposited 11 Nov 2020 11:25)
- The Complexity of Gradient Descent: CLS = PPAD ∧ PLS. (deposited 21 Jun 2021 08:22) [Currently Displayed]