HackerPapers

arXiv:2011.01929cs.CC

The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS

John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani

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.

arXiv comments
Journal version
Journal reference
Journal of the ACM, 70(1):Article 7 (2022)
DOI
doi:10.1145/3568163
Subjects
cs.CCComputational Complexity cs.LGMachine Learning math.OCOptimization and Control

On Hacker News

Linked by 3 identifiable commenters in 3 comments across 2 threads, from Aug 2021 to Jul 2023. Found in 1 HN submission from Aug 2021 to Aug 2021. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Computer scientists discover limits of gradient descent (2021) 2 comments

    • https://arxiv.org/abs/2011.01929 TFP

      ShamelessCView on HNParent context

    • Here's the original paper: https://arxiv.org/abs/2011.01929 And here are the complexity classes that are mentioned in the abstract: https://complexityzoo.net/Complexity_Zoo:P#ppad and https://complexityzoo.net/Complexity_Zoo:P#pls.

      eterevskyView on HNParent context

  2. The Complexity of Gradient Descent: CLS = PPAD ∩ PLS 1 comment

    • "...It is hard to overstate the importance of Gradient Descent. As noted by Jin et al. [2021], “Machine learning algorithms generally arise via formulations as optimization problems, and,despite a massive classical toolbox of sophisticated optimization algorithms and a major…

      belterView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.