Learning Sparse Additive Models with Interactions in High Dimensions

A function f: ℝd rightarrow ℝ is referred to as a Sparse Additive Model (SPAM), if it is of the form f(x) = suml ∈ Sφl(xl), where S subset [d], |S| ll d. Assuming φl's and 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 S1 subset [d], S2 subset [d] choose 2, the function f is assumed to be of the form: f(x) = sump ∈ S1φp (xp) + sum_(l,lprime) ∈ S2φ_(l,lprime) (xl,x_lprime). Assuming φp,φ_(l,lprime), S1 and, S2 to be unknown, we provide a randomized algorithm that queries f and exactly recovers S1,S2. Consequently, this also enables us to estimate the underlying φp, φ_(l,lprime). 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.