Implicit Regularization for Optimal Sparse Recovery

Add to your list(s) Download to your calendar using vCal

• Varun Kanade, University of Oxford
• Friday 29 May 2020, 14:00-15:00
• https://zoom.us/j/95022384263?pwd=N3Z6elB2Vy9Jajd6azlCNjFHQVlKdz09.

If you have a question about this talk, please contact Dr Sergio Bacallado.

We present an implicit regularization scheme for gradient descent methods applied to unpenalized least squares regression to solve the problem of reconstructing a sparse signal from an underdetermined system of linear measurements under the restricted isometry assumption. For a given parameterization yielding a non-convex optimization problem, we show that prescribed choices of initialization, step size and stopping time yield a statistically and computationally optimal algorithm that achieves the minimax rate with the same cost required to read the data up to poly-logarithmic factors. Beyond minimax optimality, we show that our algorithm adapts to instance difficulty and yields a dimension-independent rate when the signal-to-noise ratio is high enough. We validate our findings with numerical experiments and compare our algorithm against explicit $\ell_1$ penalization. Going from hard instances to easy ones, our algorithm is seen to undergo a phase transition, eventually matching least squares with an oracle knowledge of the true support.

(based on joint work with Patrick Rebeschini and Tomas Vaskevicius)

This talk is part of the Statistics series.

This talk is included in these lists:

• https://zoom.us/j/95022384263?pwd=N3Z6elB2Vy9Jajd6azlCNjFHQVlKdz09
• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Guy Emerson's list
• Hanchen DaDaDash
• Interested Talks
• Machine Learning
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Statistics
• Statistics Group
• bld31
• custom
• rp587

Note that ex-directory lists are not shown.