Learning Sparse Additive Models with Interactions in High Dimensions
Hemant Tyagi, Anastasios Kyrillidis, Bernd Gärtner, Andreas Krause
Abstract
A function f: \mathbbR^d →\mathbbR is referred to as a Sparse Additive Model (SPAM), if it is of the form f(x) = \sum_l ∈S \phi_l(x_l), where S ⊂[d], |S| ≪d. Assuming \phi_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 S_1 ⊂[d], S_2 ⊂[d] \choose 2, the function f is assumed to be of the form: f(x) = \sum_p ∈S_1 \phi_p (x_p) + \sum_(l,l’) ∈S_2 \phi_l,l’ (x_l, x_l’). Assuming \phi_p, \phi_(l,l’), S_1 and S_2 to be unknown, we provide a randomized algorithm that queries f and exactly recovers S_1,S_2. Consequently, this also enables us to estimate the underlying \phi_p, \phi_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.
BibTeX
@InProceedings{pmlr-v51-tyagi16,
title = {Learning Sparse Additive Models with Interactions in High Dimensions},
author = {Tyagi, Hemant and Kyrillidis, Anastasios and Gärtner, Bernd and Krause, Andreas},
booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics},
pages = {111--120},
year = {2016},
editor = {Gretton, Arthur and Robert, Christian C.},
volume = {51},
series = {Proceedings of Machine Learning Research},
address = {Cadiz, Spain},
month = {09--11 May},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v51/tyagi16.pdf},
url = {https://proceedings.mlr.press/v51/tyagi16.html},
abstract = {A function f: \mathbbR^d →\mathbbR is referred to as a Sparse Additive Model (SPAM), if it is of the form f(x) = \sum_l ∈S \phi_l(x_l), where S ⊂[d], |S| ≪d. Assuming \phi_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 S_1 ⊂[d], S_2 ⊂[d] \choose 2, the function f is assumed to be of the form: f(x) = \sum_p ∈S_1 \phi_p (x_p) + \sum_(l,l’) ∈S_2 \phi_l,l’ (x_l, x_l’). Assuming \phi_p, \phi_(l,l’), S_1 and S_2 to be unknown, we provide a randomized algorithm that queries f and exactly recovers S_1,S_2. Consequently, this also enables us to estimate the underlying \phi_p, \phi_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.}
}