The complexity of gradient descent: CLS = PPAD \(\cap\) pls
type: Item
instance of: scholarly article
title: The complexity of gradient descent: CLS = PPAD \(\cap\) pls
DOI: 10.1145/3568163
author: John Fearnley
author: Paul W. Goldberg
author: Alexandros Hollender
author: Rahul Savani
published in: Journal of the ACM
publication date: 2024-07-04T00:00:00Z
Mathematics Subject Classification ID: 68-XX
zbMATH DE Number: 7876159
zbMATH Keywords: TFNP
zbMATH Keywords: computational complexity
zbMATH Keywords: continuous optimization
MaRDI profile type: MaRDI publication profile
cites work: On Simplex Pivoting Rules and Complexity Theory
cites work: Complexity aspects of local minima and related notions
cites work: On the complexity of finding a local minimizer of a quadratic function over a polytope
cites work: On the Complexity of Numerical Analysis
cites work: Communication complexity of approximate Nash equilibria
cites work: The relative complexity of NP search problems
cites work: Q3151174
cites work: Propositional proofs and reductions between NP search problems
cites work: Lower bounds for finding stationary points I
cites work: Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
cites work: On the complexity of 2D discrete fixed point problem
cites work: Settling the complexity of computing two-player Nash equilibria
cites work: Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
cites work: Erratum/correction to: ``On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering''
cites work: The Complexity of Computing a Nash Equilibrium
cites work: Q5365081
cites work: The complexity of constrained min-max optimization
cites work: A converse to Banach's fixed point theorem and its CLS-completeness
cites work: The Simplex Algorithm Is NP-Mighty
cites work: Approximate KKT points and a proximity measure for termination
cites work: Q5875712
cites work: On the Complexity of Nash Equilibria and Other Fixed Points
cites work: The complexity of pure Nash equilibria
cites work: Unique end of potential line
cites work: A Faster Algorithm for Finding Tarski Fixed Points
cites work: The Complexity of the Simplex Method
cites work: The Hairy Ball problem is PPAD-complete
cites work: Further collapses in TFNP
cites work: Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
cites work: The complexity of the parity argument with potential
cites work: SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE
cites work: On Nonconvex Optimization for Machine Learning
cites work: How easy is local search?
cites work: Reducibility among Fractional Stability Problems
cites work: Q4369384
cites work: The polynomial solvability of convex quadratic programming
cites work: On total functions, existence theorems and computational complexity
cites work: Constant Rank Two-Player Games are PPAD-hard
cites work: The Rainbow at the End of the Line — A PPAD Formulation of the Colorful Carathéodory Theorem with Applications
cites work: Some NP-complete problems in quadratic and nonlinear programming
cites work: The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
cites work: On the complexity of the parity argument and other inefficient proofs of existence
cites work: A Stochastic Approximation Method
cites work: Polynomial interpolation schemes for internal derivative distributions on structured grids
cites work: Black-Box Complexity of Local Minimization
description: scientific article; zbMATH DE number 7876159