The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
Journal of the ACM · 28.02.2023 · 70 (1) · 1-74
DOI: 10.1145/3568163 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 19.12.2022. Verfasst von John Fearnley und 3 weiteren Autor:innen. Die Arbeit wurde bisher 24-mal zitiert (Crossref) und nennt 53 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Fearnley, J., Goldberg, P., Hollender, A., & Savani, R. (2023). The Complexity of Gradient Descent: CLS = PPAD ∩ PLS. Journal of the ACM, 70(1), 1-74. https://doi.org/10.1145/3568163
Vancouver
Fearnley J, Goldberg P, Hollender A, Savani R. The Complexity of Gradient Descent: CLS = PPAD ∩ PLS. Journal of the ACM. 2023;70(1):1-74. doi:10.1145/3568163
BibTeX
@article{Fearnley2023,
author = {Fearnley, John and Goldberg, Paul and Hollender, Alexandros and Savani, Rahul},
title = {The Complexity of Gradient Descent: CLS = PPAD ∩ PLS},
journal = {Journal of the ACM},
year = {2023},
volume = {70},
number = {1},
pages = {1--74},
doi = {10.1145/3568163}
}
EUVIMED