Skip to main content

The Complexity of Gradient Descent

Seminary by Prof. Rahul Savani (University of Liverpool)

  • Date 17 Mar 2021
  • Time 3.00pm-4.00pm
  • Category Seminar

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 (


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).


Related topics

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones.

Heading to university is exciting. Finding the right place to live will get you off to a good start.

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help.

Discover more about our 21 departments and schools.

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’.

Royal Holloway is a research intensive university and our academics collaborate across disciplines to achieve excellence.

Discover world-class research at Royal Holloway.

Discover more about who we are today, and our vision for the future.

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today.

We’ve played a role in thousands of careers, some of them particularly remarkable.

Find about our decision-making processes and the people who lead and manage Royal Holloway today.