The complexity of gradient descent: CLS = PPAD pls

Recommendations

The complexity of gradient descent: CLS = PPAD ∩ PLS
The complexity of gradient descent (invited talk)
scientific article; zbMATH DE number 6783433
Hardness of continuous local search: query complexity and cryptographic lower bounds
Hardness of continuous local search: query complexity and cryptographic lower bounds

Cites work

scientific article; zbMATH DE number 1818892 (Why is no real title available?)
scientific article; zbMATH DE number 1099195 (Why is no real title available?)
scientific article; zbMATH DE number 6783433 (Why is no real title available?)
scientific article; zbMATH DE number 7650366 (Why is no real title available?)
A Faster Algorithm for Finding Tarski Fixed Points
A Stochastic Approximation Method
A converse to Banach's fixed point theorem and its CLS-completeness
Approximate KKT points and a proximity measure for termination
Black-Box Complexity of Local Minimization
Complexity aspects of local minima and related notions
Constant rank two-player games are PPAD-hard
Erratum/correction to: ``On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
Further collapses in TFNP
Hardness of continuous local search: query complexity and cryptographic lower bounds
How easy is local search?
Lower bounds for finding stationary points I
On Nonconvex Optimization for Machine Learning
On Simplex Pivoting Rules and Complexity Theory
On the Complexity of Nash Equilibria and Other Fixed Points
On the Complexity of Numerical Analysis
On the complexity of 2D discrete fixed point problem
On the complexity of finding a local minimizer of a quadratic function over a polytope
On the complexity of the parity argument and other inefficient proofs of existence
On total functions, existence theorems and computational complexity
Polynomial interpolation schemes for internal derivative distributions on structured grids
Propositional proofs and reductions between NP search problems
Reducibility among fractional stability problems
SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
Settling the complexity of computing two-player Nash equilibria
Some NP-complete problems in quadratic and nonlinear programming
The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
The Hairy Ball problem is PPAD-complete
The complexity of computing a Nash equilibrium
The complexity of constrained min-max optimization
The complexity of pure Nash equilibria
The complexity of the parity argument with potential
The complexity of the simplex method
The polynomial solvability of convex quadratic programming
The rainbow at the end of the line -- a \textsf{PPAD} formulation of the colorful Carathéodory theorem with applications
The relative complexity of NP search problems
Unique end of potential line

Cited in

(4)

The crossing Tverberg theorem
The complexity of gradient descent (invited talk)
Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
The complexity of gradient descent: CLS = PPAD ∩ PLS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6567266)