Learning Sparse Additive Models with Interactions in High Dimensions: Proceedings of the 19th International Conference on Artificial Intelligence and Statistics

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

Research output: Contribution to journalArticlepeer-review

Abstract

A function f:Rd→R is referred to as a Sparse Additive Model (SPAM), if it is of the form f(x)=∑l∈Sϕl(xl), where S⊂[d], |S|≪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⊂[d], S2⊂([d]2), the function f is assumed to be of the form: f(x)=∑p∈S1ϕp(xp)+∑(l,l′)∈S2ϕl,l′(xl,xl′). Assuming ϕp, ϕ(l,l′), 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,l′. 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.
Original languageEnglish
Pages (from-to)111-120
Number of pages10
JournalJournal of Machine Learning Research: Workshop and Conference Proceedings
Volume51
Publication statusPublished - 2 May 2016

Fingerprint Dive into the research topics of 'Learning Sparse Additive Models with Interactions in High Dimensions: Proceedings of the 19th International Conference on Artificial Intelligence and Statistics'. Together they form a unique fingerprint.

Cite this