The complexity of gradient descent: CLS = PPAD ∩ PLS

DOI10.1145/3406325.3451052arXiv2011.01929OpenAlexW3171998715MaRDI QIDQ6065170

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

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.01929

zbMATH Keywords

computational complexitycontinuous optimizationTFNP

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (7)

On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ Non-interactive universal arguments ⋮ Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Two's company, three's a crowd: consensus-halving for a constant number of agents ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

This page was built for publication: The complexity of gradient descent: CLS = PPAD ∩ PLS