"...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 modern effort to further develop that toolbox, the simplest algorithms—gradient descent, which dates to the 1840s [Cauchy, 1847] and stochastic gradient descent, which dates to the 1950s [Robbins and Monro, 1951]—reign supreme in machine learning.”..."

"Our main result is to show that finding a point where Gradient Descent on a continuously differentiable function terminates—or equivalently a KKT point—is PPAD ∩ PLS-complete, when the domain is a bounded convex polytope. This continues to hold even when the domain is as simple as the unit square [0, 1]. The PPAD ∩ PLS-completeness result applies to the “white box” model, where functions are represented as arithmetic circuits.

"...As an immediate consequence, our result provides convincing evidence that the problem is computationally hard. First of all, there are reasons to believe that PPAD ∩ PLS is hard simply because PPAD and PLS are believed to be hard. Indeed, if PPAD ∩ PLS could be solved in polynomial time, then, given an instance of a PPADcomplete problem and an instance of a PLS-complete problem, we would be able to solve at least one of the two instances in polynomial time. Furthermore, since CLS ⊆ PPAD ∩ PLS, the above-mentioned cryptographic hardness of CLS applies automatically to PPAD ∩ PLS, and thus to our problem of interest..."

https://arxiv.org/pdf/2011.01929.pdf

"Computer Scientists Discover Limits of Major Research Algorithm"

https://www.quantamagazine.org/computer-scientists-discover-...