3. Kálmán lecture by Sara van de Geer

The Lasso revisited: entropy bounds and dual certificates

Talk by Sara van de Geer from the ETH Zürich (Switzerland).

Abstract: The Lasso is least squares estimation with an ℓ1-penalty on the coeffcients. In this talk we consider the case where the design matrix is structured, and where its columns have high correlations. We consider for this situation the theory for non-adaptive (minimax) rates and adaptive (oracle) rates.
The ℓ1-penalty leads to studying the entropy of the signed convex hull of the columns of the design matrix. We will present a bound for this entropy based on projection theory. This generalizes a result in Ball and Pajor [1990] which bounds the entropy of the convex hull in terms of the covering number of its extreme points. The entropy bound is applied to obtain non-adaptive rates.
For the adaptive rates, we will combine the approach of Dalalyan et al. [2017] with dual certificates as given in Candes and Plan [2011]. This will be applied to the trend filtering problem, to higher dimensional extensions and to total variation on graphs