mlsanityData to 7 Oct 2026

The Complexity of Gradient Descent: CLS = PPAD cap PLS

arXiv 2011.01929 ↗First posted 3 Nov 2020cs.CC cs.LG math.OCcited by 17

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Nov 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 1; 2023: 3; 2024: 3; 2025: 3; 2026: 5.

17 papers.

Sort:

By area:

  1. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 25
  2. 2021Counterfactual Explanations for Arbitrary Regression Modelscited by 22
  3. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  4. 2023The Computational Complexity of Single-Player Imperfect-Recall Gamescited by 5
  5. 2024Imperfect-Recall Games: Equilibrium Concepts and Their Complexitycited by 4
  6. 2025Computing Game Symmetries and Equilibria That Respect Themcited by 3
  7. 2023The Computational Complexity of Finding Stationary Points in Non-Convex Optimizationcited by 2
  8. 2024Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Modelscited by 2
  9. 2025Convergence of Regret Matching in Potential Games and Constrained Optimizationcited by 2
  10. 2026On the Computational Complexity of Performative Predictioncited by 2
  11. 2021Towards convergence to Nash equilibria in two-team zero-sum gamescited by 1
  12. 2025The Complexity of Finding Local Optima in Contrastive Learningcited by 1
5 more
  1. 2024On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimizationcited by 0
  2. 2026On Approximate Computation of Critical Pointscited by 0
  3. 2026Decision Making under Imperfect Recall: Algorithms and Benchmarkscited by 0
  4. 2026The Complexity of Min-Max Optimization for Quadratic Polynomialscited by 0
  5. 2026Algorithmic Collusion and the Complexity of Information-Value-Free Equilibriacited by 0