BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T211802Z
UID:Seminar-EcCo-1000@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20210602T130000
DTEND:20210602T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Rahul Savani: The Complexity of Gradient Descent\n\nThis talk is about the computational complexity of Gradient Descent, one of the oldest and most widely-used algorithmic approaches for optimisation, for example of neural networks. The approach dates all the way back to an 1847 paper of Cauchy.\n\n\n\n\n\nWhen Gradient Descent is constrained to a bounded domain, there are not one but two reasons why it must terminate.\n\n\n\nReason 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).\n\n\n\nReason 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.\n\n\n\nPPAD 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.\n\n\n\nJoint work with: John Fearnley (Liverpool), Paul Goldberg (Oxford), and Alexandros Hollender (Oxford). Paper to appear at STOC'21.\n\n\n\n \n\n\n\n \n\n\n\n\n\n\n\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1000
LOCATION:
END:VEVENT
END:VCALENDAR