BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Complexity analysis of the Lasso regularization path and an applic
 ation of sparsity to isoform detection in RNA-seq data - Julien Mairal\, I
 NRIA\, Grenoble
DTSTART:20150227T160000Z
DTEND:20150227T170000Z
UID:TALK56947@talks.cam.ac.uk
CONTACT:20082
DESCRIPTION:This talk will be composed of two independent parts. In the fi
 rst part\, we will study an intriguing phenomenon related to the regulariz
 ation path of the Lasso estimator. The regularization path of the Lasso ca
 n be shown to be piecewise linear\, making it possible to “follow” and
  explicitly compute the entire path. We analyze this popular strategy\, an
 d prove that its worst case complexity is exponential in the number of var
 iables. We then oppose this pessimistic result to an (optimistic) approxim
 ate 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. \n \nIn the seco
 nd part\, I will present a successful application of sparsity to the probl
 em 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 imp
 ortant but computationally challenging task consists of discovering isofor
 ms from the expression of exons. This can be formulated as a sparse regres
 sion problem with an exponential number of features.  We propose an approa
 ch based on an equivalence between the problem of isoform detection in spa
 rse regression and the problem of path selection in a directed acyclic gra
 phs\, which can be solved efficiently using network flow algorithms.
LOCATION:MR12\,  Centre for Mathematical Sciences\, Wilberforce Road\, Cam
 bridge
END:VEVENT
END:VCALENDAR