by , , ,
A function $f: R^d \rightarrow R$ is referred to as a Sparse Additive Model (SPAM), if it is of the form $f(x) = \sum_(l \in S)\phi_l(x_l)$, where $S \subset [d]$, $|S| \ll \d$. Assuming $\phi_l$'s and $S$ to be unknown, there exists extensive work for estimating $f$ from its samples. In this work, we consider a generalized SPAM, that also allows for the presence of a sparse number of second order interaction terms. For some $S_1 \subset [d], S_2 \subset [d] \choose 2$, the function $f$ is now assumed to be of the form: $f(x) = \sum_(p \in S_1)\phi_p (x_p) + \sum_((l,l') \in S_2) \phi_(l,l') (x_(l),x_(l'))$. Assuming we have the freedom to query $f$ anywhere in its domain, we derive efficient algorithms that provably recover $S_1$, $S_2$ with finite sample bounds. Our analysis covers the noiseless setting where exact samples of $f$ are obtained, and also extends to the noisy setting where the queries are corrupted with noise. For the noisy setting in particular, we consider two noise models namely: i.i.d Gaussian noise and arbitrary but bounded noise. Our main methods for identification of $S_2$ essentially rely on estimation of sparse Hessian matrices, for which we provide two novel compressed sensing based schemes. Once $S_1$, $S_2$ are known, we show how the individual components $\phi_p$, $\phi_(l,l')$ can be estimated via additional queries of $f$, with uniform error bounds. Lastly, we provide simulation results on synthetic data that validate our theoretical findings.
Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions H. Tyagi, A. Kyrillidis, B. Gärtner, A. KrauseIn Information and Inference: A Journal of the IMA, volume 00, 2017
Bibtex Entry:
	Author = {Hemant Tyagi and Anastasios Kyrillidis and Bernd G\"artner and Andreas Krause},
	Journal = {Information and Inference: A Journal of the IMA},
	Month = {August},
	Pages = {1-67},
	Title = {Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions},
	Volume = {00},
	Year = {2017}}