EUVIMEDEUVIMED entdecken
Crossref

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS

John Fearnley, Paul Goldberg, Alexandros Hollender, Rahul Savani

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →