The Complexity of Gradient Descent

Abstract: This talk is about the computational complexity of Gradient Descent, one of the oldest and most widely-used algorithmic approaches to doing optimisation, for example of neural networks. The approach dates all the way back to an 1847 paper of Cauchy.

When Gradient Descent is constrained to a bounded domain, there are not one but two reasons why it must terminate.

Reason 1: we are always going downhill, altitude must "bottom out". This puts the search for a solution in the complexity class PLS (polynomial local search).

Reason 2: Gradient Descent maps any point to a nearby point in the direction of the negative gradient. Brouwer's Fixed Point Theorem guarantees that such a mapping has a point mapped to itself. This puts the search for a solution in the complexity class PPAD.

PPAD and PLS correspond to existence-of-solution proof principles that guarantee solutions, but in a computationally-inefficient way. Both classes have become successful through the fact that they have been shown to exactly characterise the complexity of important problems such as finding a Nash equilibrium (PPAD) or finding a local max cut of a graph (PLS). Our main result shows that the Gradient Descent solution-existence principle tastefully combines the PLS principle with the PPAD principle: We show how to efficiently reduce any problem that is in both PPAD and PLS to a Gradient Descent problem.

Joint work with: John Fearnley (Liverpool), Paul Goldberg (Oxford), and Alexandros Hollender (Oxford). Paper to appear at STOC'21 (https://arxiv.org/abs/2011.01929).

Bio: Rahul Savani is Professor in the Economics and Computation Research Group in the Computer Science Department at the University of Liverpool. He joined the Department as a Lecturer (Assistant Professor) in October 2009, became a Senior Lecturer (Associate Professor) in 2013, a Reader in 2015, and a Full Professor in 2017. Previously he was an EPSRC Postdoctoral Research Fellow in Theoretical Computer Science studying algorithms for computing equilibria in games at the University of Warwick (2006-2009).