The complexity of gradient descent: CLS = PPAD pls

DOI10.1145/3568163MaRDI QIDQ6567266FDOQ6567266

Authors: John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani 

Publication date: 4 July 2024

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitycontinuous optimizationTFNP

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

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

Cited In (4)

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

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)