Algorithms for Learning Sparse Additive Models with Interactions in High
  Dimensions
  A function $f: \mathbb{R}^d \rightarrow \mathbb{R}$ is a Sparse Additive
Model (SPAM), if it is of the form $f(\mathbf{x}) = \sum_{l \in
\mathcal{S}}\phi_{l}(x_l)$ where $\mathcal{S} \subset [d]$, $|\mathcal{S}| \ll
d$. Assuming $\phi$'s, $\mathcal{S}$ to be unknown, there exists extensive work
for estimating $f$ from its samples. In this work, we consider a generalized
version of SPAMs, that also allows for the presence of a sparse number of
second order interaction terms. For some $\mathcal{S}_1 \subset [d],
\mathcal{S}_2 \subset {[d] \choose 2}$, with $|\mathcal{S}_1| \ll d,
|\mathcal{S}_2| \ll d^2$, the function $f$ is now assumed to be of the form:
$\sum_{p \in \mathcal{S}_1}\phi_{p} (x_p) + \sum_{(l,l^{\prime}) \in
\mathcal{S}_2}\phi_{(l,l^{\prime})} (x_l,x_{l^{\prime}})$. Assuming we have the
freedom to query $f$ anywhere in its domain, we derive efficient algorithms
that provably recover $\mathcal{S}_1,\mathcal{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 $\mathcal{S}_2$ essentially rely on estimation of sparse
Hessian matrices, for which we provide two novel compressed sensing based
schemes. Once $\mathcal{S}_1, \mathcal{S}_2$ are known, we show how the
individual components $\phi_p$, $\phi_{(l,l^{\prime})}$ 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.
