The complexity of gradient descent: CLS = PPAD \(\cap\) pls

Related Items (2)

Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024 ⋮ The crossing Tverberg theorem

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Propositional proofs and reductions between NP search problems
On total functions, existence theorems and computational complexity
On the complexity of 2D discrete fixed point problem
How easy is local search?
The relative complexity of NP search problems
On the complexity of the parity argument and other inefficient proofs of existence
Polynomial interpolation schemes for internal derivative distributions on structured grids
The complexity of the parity argument with potential
Complexity aspects of local minima and related notions
On the complexity of finding a local minimizer of a quadratic function over a polytope
Communication complexity of approximate Nash equilibria
Unique end of potential line
Lower bounds for finding stationary points I
The Hairy Ball problem is PPAD-complete
Erratum/correction to: ``On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
Approximate KKT points and a proximity measure for termination
The Complexity of the Simplex Method
On the Complexity of Nash Equilibria and Other Fixed Points
Settling the complexity of computing two-player Nash equilibria
The complexity of pure Nash equilibria
On the Complexity of Numerical Analysis
Some NP-complete problems in quadratic and nonlinear programming
The polynomial solvability of convex quadratic programming
The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
Constant Rank Two-Player Games are PPAD-hard
The Rainbow at the End of the Line — A PPAD Formulation of the Colorful Carathéodory Theorem with Applications
The Simplex Algorithm Is NP-Mighty
Black-Box Complexity of Local Minimization
On Nonconvex Optimization for Machine Learning
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
The Complexity of Computing a Nash Equilibrium
Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
A converse to Banach's fixed point theorem and its CLS-completeness
Reducibility among Fractional Stability Problems
On Simplex Pivoting Rules and Complexity Theory
A Stochastic Approximation Method
A Faster Algorithm for Finding Tarski Fixed Points
The complexity of constrained min-max optimization
SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE
Further collapses in TFNP

This page was built for publication: The complexity of gradient descent: CLS = PPAD \(\cap\) pls