by H. Tyagi, A. Kyrillidis, B. Gärtner, A. Krause

Abstract:

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.

Reference:

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:

@article{tyagi17algorithms\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.}, 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}}