Dr John Fearnley and Professor Rahul Savani from the Department of Computer Science, along with Paul Goldberg and Alexandros Hollender (both at the University of Oxford), have had their research recognised through a prestigious Best Paper Award at the 53rd ACM Symposium on Theory of Computing (STOC 2021). The prize is awarded for their paper entitled "The Complexity of Gradient Descent: CLS = PPAD ∩ PLS.” The department and school congratulate all authors on this accolade for their research.
Professor Savani gives a summary of the paper below.
"This paper 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). The main result of the paper shows that the Gradient Descent solution-existence principle tastefully combines the PLS principle with the PPAD principle: The paper shows how to efficiently reduce any problem that is in both PPAD and PLS to a Gradient Descent problem."
To find out more about our Algorithms researchers in the Department of Computer Science visit here.