ISL Colloquium presents "Implicit Regularization for Optimal Sparse Recovery"

Topic: 
Implicit Regularization for Optimal Sparse Recovery
Friday, December 6, 2019 - 11:00am
Venue: 
Packard 202
Speaker: 
Patrick Rebeschini (Oxford)
Abstract / Description: 

Ridge regression is a fundamental paradigm in machine learning and statistics, and it has long been known to be closely connected to the implicit regularization properties of gradient descent methods, cf. early stopping. Over the past decade, this connection has sparked research into a variety of directions aimed at developing computationally efficiency estimators, including acceleration, mini-batching, averaging, sketching, sub-sampling, preconditioning, and decentralization. Sparse recovery is another cornerstone of modern statistics and learning frameworks. Yet, here the connection to implicit regularization is not as well developed. Most results in the literature only involve limit statements (holding at convergence, for infinitesimal step sizes), apply to regimes with no (or limited) noise, and do not focus on computational efficiency. In this talk, we address the following question: Can we establish an implicit regularization theory for gradient descent to yield optimal sparse recovery in noisy settings, achieving minimax rates with the same cost of reading the data? We will highlight the key ideas to obtain the first results in this direction, along with a few surprising findings.