Complexity analysis of the Lasso regularization path and an application of sparsity to isoform detection in RNA-seq data

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

• Julien Mairal, INRIA, Grenoble
• Friday 27 February 2015, 16:00-17:00
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

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

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.

This talk is part of the Statistics series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Infectious Diseases
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Guy Emerson's list
• Hanchen DaDaDash
• Interested Talks
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• Machine Learning
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Statistics
• Statistics Group
• Trust & Technology Initiative - interesting events
• bld31
• custom
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.