BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Sébastien Bubeck (Microsoft Research)
DTSTART:20200424T150000Z
DTEND:20200424T160000Z
DTSTAMP:20260423T021727Z
UID:sss/2
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/sss/2/">How 
 to Trap a Gradient Flow</a>\nby Sébastien Bubeck (Microsoft Research) as 
 part of Stochastics and Statistics Seminar Series\n\n\nAbstract\nIn 1993\,
  Stephen A. Vavasis proved that in any finite dimension\, there exists a f
 aster method than gradient descent to find stationary points of smooth non
 -convex functions. In dimension 2 he proved that 1/eps gradient queries ar
 e enough\, and that 1/sqrt(eps) queries are necessary. We close this gap b
 y providing an algorithm based on a new local-to-global phenomenon for smo
 oth non-convex functions. Some higher dimensional results will also be dis
 cussed. I will also present an extension of the 1/sqrt(eps) lower bound to
  randomized algorithms\, mainly as an excuse to discuss some beautiful top
 ics such as Aldous’ 1983 paper on local minimization on the cube\, and B
 enjamini-Pemantle-Peres’ 1998 construction of unpredictable walks.\n\nJo
 int work with Dan Mikulincer\n
LOCATION:https://researchseminars.org/talk/sss/2/
END:VEVENT
END:VCALENDAR