Best Paper Award at STOC

Paul Goldberg and Alexandros Hollender received a Best Paper Award at the 2021 Annual ACM Symposium on Theory of Computing (STOC), a prestigious CS theory conference. The paper, titled 'The Complexity of Gradient Descent: CLS = PPAD ∩ PLS' is co-authored with John Fearnley and Rahul Savani from the University of Liverpool.

Gradient Descent is a general-purpose optimisation procedure that was first proposed by the mathematician Augustin-Louis Cauchy in 1847. It is now widely used in optimisation and Neural Networks, and there is widespread interest in understanding its often impressive performance in practice. The paper advances this understanding by identifying for the first time, gradient descent problems that are provably 'hard to solve'. This will guide researchers to identify features of real-world gradient descent problems that should be exploited in the search for provable performance.

Details and previous winners of the STOC paper can be found here: