The Complexity of Gradient Descent

Savani, Rahul ORCID: 0000-0003-1262-7831 (2021) The Complexity of Gradient Descent .

Access the full-text of this item by clicking on the Open Access link.

Abstract

PPAD and PLS are successful classes that capture the complexity of important game-theoretic problems. For example, finding a mixed Nash equilibrium in a bimatrix game is PPAD-complete, and finding a pure Nash equilibrium in a congestion game is PLS-complete. Many important problems, such as solving a Simple Stochastic Game or finding a mixed Nash equilibrium of a congestion game, lie in both classes. It was strongly believed that their intersection, PPAD ∩ PLS, does not have natural complete problems. We show that it does: any problem that lies in both classes can be reduced in polynomial time to the problem of finding a stationary point of a continuously differentiable function on the domain [0, 1]². Thus, as PPAD captures problems that can be solved by Lemke-Howson type complementary pivoting algorithms, and PLS captures problems that can be solved by local search, we show that PPAD ∩ PLS exactly captures problems that can be solved by Gradient Descent. This is joint work with John Fearnley, Paul Goldberg, and Alexandros Hollender. It appeared at STOC’21, where it was given a Best Paper Award [4].

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	Computational Complexity, Continuous Optimization, TFNP, PPAD, PLS, CLS, UEOPL
Divisions:	Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	06 Jun 2022 08:55
Last Modified:	23 May 2026 06:45
DOI:	10.4230/LIPIcs.FSTTCS.2021.5
Open Access URL:	https://drops.dagstuhl.de/opus/volltexte/2021/1551...
Related Websites:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3155822
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.