Orateur
Description
We bridge statistics, convex and discrete geometry, extremal combinatorics, spectral graph theory, and coding theory in our study of complexity of the lasso regularization path under predictor normalization. We show that normalization imposes a new global restriction on the sign patterns encountered by the path: any two full-support patterns must agree in at least two coordinates. This reduces the highest-dimensional complexity of such paths in $\mathbb R^p$ to Kleitman's binary diameter problem of calculating $h_{p,r}$, the number of binary $p$-words that match at least at $r$ places, for $r=2$, and leads us to explicit finite dimensional upper bounds.
We obtain upper and lower bounds for the total complexity of such paths and we show that the normalized lasso complexity remains exponential, while exhibiting combinatorial restrictions absent in the unrestricted problem. Furthermore, by using the concept of mutual coherence from statistics, we identify the data for which the lasso paths have $h_{p,r}$ as upper bounds for their highest dimension complexity for any given $r>2$, while $r=1$ case is identified with the unrestricted data studied by Mairal and Yu.
This is based on a joint work with Borislav Gajić.