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. ISSN 0737-8017

This is the latest version of this item.

Access the full-text of this item by clicking on the Open Access link.
[thumbnail of 2011.01929v1.pdf] Text
2011.01929v1.pdf - Submitted version
Download (1MB) | Preview
[thumbnail of stoc-elements.pdf] 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 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 PLS and contains many interesting problems - is itself equal to PPAD PLS.

Item Type: Article
Additional Information: Journal version
Uncontrolled Keywords: TFNP, computational complexity, continuous optimization
Divisions: Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 21 Jun 2021 08:22
Last Modified: 22 May 2026 16:23
DOI: 10.1145/3406325.3451052
Open Access URL: https://dl.acm.org/doi/pdf/10.1145/3406325.3451052
Related Websites:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3126955
Disclaimer: The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.

Available Versions of this Item

Altmetric
CORE (COnnecting REpositories)