Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions

A function f:Rd→R is a Sparse Additive Model (SPAM), if it is of the form f(x)=∑l∈Sϕl(xl) where S⊂[d], |S|≪d. Assuming ϕ's, 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 S1⊂[d],S2⊂([d]2), with |S1|≪d,|S2|≪d2, the function f is now assumed to be of the form: ∑p∈S1ϕp(xp)+∑(l,l′)∈S2ϕ(l,l′)(xl,xl′). Assuming we have the freedom to query f anywhere in its domain, we derive efficient algorithms that provably recover S1,S2 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 S2 essentially rely on estimation of sparse Hessian matrices, for which we provide two novel compressed sensing based schemes. Once S1,S2 are known, we show how the individual components ϕp, ϕ(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.