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:20260404T131150Z
UID:sss/2
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/sss/2
 /">How to Trap a Gradient Flow</a>\nby Sébastien Bubeck (Microsoft Resear
 ch) as part of Stochastics and Statistics Seminar Series\n\n\nAbstract\nIn
  1993\, Stephen A. Vavasis proved that in any finite dimension\, there exi
 sts a faster method than gradient descent to find stationary points of smo
 oth non-convex functions. In dimension 2 he proved that 1/eps gradient que
 ries are enough\, and that 1/sqrt(eps) queries are necessary. We close thi
 s gap by providing an algorithm based on a new local-to-global phenomenon 
 for smooth non-convex functions. Some higher dimensional results will also
  be discussed. I will also present an extension of the 1/sqrt(eps) lower b
 ound to randomized algorithms\, mainly as an excuse to discuss some beauti
 ful topics such as Aldous’ 1983 paper on local minimization on the cube\
 , and Benjamini-Pemantle-Peres’ 1998 construction of unpredictable walks
 .\n\nJoint work with Dan Mikulincer\n
LOCATION:https://stable.researchseminars.org/talk/sss/2/
END:VEVENT
END:VCALENDAR