Colloquium Events

Colloquium: The Complexity of Gradient Descent

21 March 2022, Monday. 3PM. London Time. Online over Zoom

Title: The Complexity of Gradient Descent

SpeakerRahul Savani, University of Liverpool

Abstract PPAD and PLS are successful classes that each capture the complexity of important game-theoretic problems: 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. However, it was strongly believed that their intersection 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 function. Our result has been used to show that computing a mixed equilibrium of a congestion game is also complete for theintersection of PPAD and PLS. The talk will not assume a technical background in the area and will be aimed at a general audience.This is joint work with John Fearnley, Paul Goldberg, and Alexandros Hollender.

Bio Rahul Savani is a Professor of Economics and Computation at the University of Liverpool. He has worked extensively on the computation of equilibria in game-theoretic models. The paper that he will present won a Best Paper Award at STOC’21.

Zoom link

Meeting ID: 668 413 8396

Passcode: mdx