A function $f: \mathbb{ R}^d \rightarrow \mathbb{ R}$ is referred to as 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_l$'s and $\mathcal{ S}$ to be unknown, the problem of estimating $f$ from its samples has been studied extensively. In this work, we consider a generalized SPAM, allowing for second order interaction terms. For some $\mathcal{ S}_1 \subset [d], \mathcal{ S}_2 \subset { [d] \choose 2}$, the function $f$ is assumed to be of the form: $$f(\mathbf{ x}) = \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 $\phi_{ p},\phi_{ (l,l^{ \prime})}$, $\mathcal{ S}_1$ and, $\mathcal{ S}_2$ to be unknown, we provide a randomized algorithm that queries $f$ and exactly recovers $\mathcal{ S}_1,\mathcal{ S}_2$. Consequently, this also enables us to estimate the underlying $\phi_p, \phi_{ (l,l^{ \prime})}$. We derive sample complexity bounds for our scheme and also extend our analysis to include the situation where the queries are corrupted with noise -- either stochastic, or arbitrary but bounded. Lastly, we provide simulation results on synthetic data, that validate our theoretical findings.

Categories: cs.LG cs.IT math.IT stat.ML

Learning Sparse Additive Models with Interactions in High Dimensions