Fearnley, John, Goldberg, Paul, Hollender, Alexandros and Savani, Rahul 
ORCID: 0000-0003-1262-7831
(2023)
The Complexity of Gradient Descent: CLS = PPAD boolean AND PLS.
.
 | There is a more recent version of this item available. |
|
Text
2011.01929v1.pdf - Submitted version Download (1MB) | 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 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.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | Updated based on reviewer comments, including a non-computer-assisted proof |
| Uncontrolled Keywords: | TFNP, computational complexity, continuous optimization |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 11 Nov 2020 11:25 |
| Last Modified: | 23 Feb 2023 21:07 |
| DOI: | 10.1145/3568163 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3106588 |
Available Versions of this Item
- The Complexity of Gradient Descent: CLS = PPAD boolean AND PLS. (deposited 11 Nov 2020 11:25) [Currently Displayed]
Dimensions
Dimensions
