BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Implicit Regularization for Optimal Sparse Recovery - Varun Kanade
 \, University of Oxford
DTSTART:20200529T130000Z
DTEND:20200529T140000Z
UID:TALK140260@talks.cam.ac.uk
CONTACT:Dr Sergio Bacallado
DESCRIPTION:We present an implicit regularization scheme for gradient desc
 ent methods\napplied to unpenalized least squares regression to solve the 
 problem of\nreconstructing a sparse signal from an underdetermined system 
 of linear\nmeasurements under the restricted isometry assumption. For a gi
 ven\nparameterization yielding a non-convex optimization problem\, we show
  that\nprescribed choices of initialization\, step size and stopping time 
 yield a\nstatistically and computationally optimal algorithm that achieves
  the minimax\nrate with the same cost required to read the data up to poly
 -logarithmic\nfactors. Beyond minimax optimality\, we show that our algori
 thm adapts to\ninstance difficulty and yields a dimension-independent rate
  when the\nsignal-to-noise ratio is high enough. We validate our findings 
 with numerical\nexperiments and compare our algorithm against explicit $\\
 ell_1$ penalization. \nGoing from hard instances to easy ones\, our algori
 thm is seen to undergo a\nphase transition\, eventually matching least squ
 ares with an oracle knowledge of\nthe true support.\n\n(based on joint wor
 k with Patrick Rebeschini and Tomas Vaskevicius)
LOCATION: https://zoom.us/j/95022384263?pwd=N3Z6elB2Vy9Jajd6azlCNjFHQVlKdz
 09
END:VEVENT
END:VCALENDAR