License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.5
URN: urn:nbn:de:0030-drops-155167
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15516/
Go to the corresponding LIPIcs Volume Portal

Savani, Rahul

The Complexity of Gradient Descent (Invited Talk)

pdf-format:
LIPIcs-FSTTCS-2021-5.pdf (0.4 MB)

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 [Fearnley et al., 2021].

BibTeX - Entry

@InProceedings{savani:LIPIcs.FSTTCS.2021.5,
  author =	{Savani, Rahul},
  title =	{{The Complexity of Gradient Descent}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{5:1--5:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15516},
  URN =		{urn:nbn:de:0030-drops-155167},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.5},
  annote =	{Keywords: Computational Complexity, Continuous Optimization, TFNP, PPAD, PLS, CLS, UEOPL}
}

Keywords: Computational Complexity, Continuous Optimization, TFNP, PPAD, PLS, CLS, UEOPL
Collection: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Issue Date: 2021
Date of publication: 29.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI