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.

@article{tyagi17algorithms,
	author = {Hemant Tyagi and Anastasios Kyrillidis and Bernd G\"artner and Andreas Krause},
	doi = {10.1093/imaiai/iax008},
	journal = {Information and Inference: A Journal of the IMA},
	month = {August},
	number = {2},
	pages = {183-249},
	title = {Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions},
	volume = {7},
	year = {2017}}