| Hemant Tyagi and Armin Eftekhari |
| Tue 25 Oct 2016, 11:00 - 12:00 |
| IF 4.31/4.33 |
If you have a question about this talk, please contact: Gareth Beedham (gbeedham)
Lunch provided afterwards in MF2
Hemant Tyagi
Title:
Learning Sparse Additive Models with Interactions in High Dimensions
Abstract:
Many scientific problems involve estimating an unknown function f, defined over a compact subset of R^d with d large. Information about f is available through point values which are then used for learning f. It is well known that if mere smoothness assumptions are made on f, then the problem suffers from the curse of dimensionality – the number of samples needed to approximate f can be exponentially large in d. To bypass this, additional structural assumptions on f are necessary.
In this talk we will consider f to have an intrinsically low dimensional structure and consider a specific class of functions known as Sparse Additive Models (SpAM). Here, f depends on an unknown subset of k << d coordinates in an additive manner, i.e.,as the sum of a small number of univariates, bivariates etc. We will specifically focus on the setting where f is the sum of univariate and bivariate functions, with the bivariate functions capturing the pairwise interactions amongst the coordinates. Assuming freedom to query f anywhere within a compact domain, we will look at algorithms that recover the underlying the structure, with finite sample bounds depending mildly on d. The methods essentially (a) utilize tools from compressed sensing and, (b) involve estimating the sparse gradient and sparse hessian of f on carefully constructed sets of points.
This is joint work with Bernd Gärtner (ETH Zürich), Andreas Krause (ETH Zürich) and Anastasios Kyrillidis (UT Austin).
Armin Eftekhari
Title:
SNIPE for memory-limited PCA with incomplete data: From failure to success
Abstract:
Consider the problem of identifying an unknown subspace S from data with erasures and with limited memory available. To estimate S, suppose we group the measurements into blocks and iteratively update our estimate of S with each new block.
In the first part of this talk, we will discuss why estimating S by computing the "running average" of span of these blocks fails in general. Based on the lessons learned, we then propose SNIPE for memory-limited PCA with incomplete data, useful also for streaming data applications. SNIPE provably converges (linearly) to the true subspace, in the absence of noise and given sufficient measurements, and shows excellent performance in simulations. This is joint work with Laura Balzano and Mike Wakin.
Bio:
Armin Eftekhari is a Research Fellow at the Alan Turing Institute. He received his PhD in 2015 from the Colorado School of Mines, under the supervision of Mike Wakin. After that, he was a postdoc at the Institute for Computational Engineering and Sciences, University of Texas at Austin, and then a postdoc at Rutgers University in Summer 2016.