Abstract

This talk will be composed of two independent parts. In the first part, we will study an intriguing phenomenon related to the regularization path of the Lasso estimator. The regularization path of the Lasso can be shown to be piecewise linear, making it possible to “follow” and explicitly compute the entire path. We analyze this popular strategy, and prove that its worst case complexity is exponential in the number of variables. We then oppose this pessimistic result to an (optimistic) approximate analysis: We show that an approximate path with at most O(1/sqrt(ε)) linear segments can always be obtained, where every point on the path is guaranteed to be optimal up to a relative ε-duality gap.

In the second part, I will present a successful application of sparsity to the problem of isoform identification and quantification from RNA -Seq data. A gene is composed of several coding (exon) and non-coding parts (introns). Exons are combined into sequences called isoforms that encode a protein. An important but computationally challenging task consists of discovering isoforms from the expression of exons. This can be formulated as a sparse regression problem with an exponential number of features. We propose an approach based on an equivalence between the problem of isoform detection in sparse regression and the problem of path selection in a directed acyclic graphs, which can be solved efficiently using network flow algorithms.