Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions

Hemant Tyagi, Anastasios Kyrillidis, Bernd Gärtner, Andreas Krause

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)183-249
Number of pages67
JournalInformation and Inference: a Journal of the IMA
Volume7
Issue number2
Early online date24 Aug 2017
DOIs
Publication statusPublished - 7 Jun 2018

Fingerprint

Dive into the research topics of 'Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions'. Together they form a unique fingerprint.

Cite this