Learning Sparse Additive Models with Interactions in High Dimensions

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 functionsknown 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 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).