by H. Tyagi, A. Krause, B. Gärtner

Abstract:

We consider the problem of learning sparse additive models, i.e., functions of the form: $f(x)=\sum_{i\in S} \phi_i(x_i)$ from point queries of f. Here S is an unknown subset of coordinate variables with $|S|=k\leq d$. Assuming the $\phi_i$ to be smooth, we propose a set of points at which to sample f and an efficient randomized algorithm that recovers a uniform approximation to each unknown $\phi_i$. We provide a rigorous theoretical analysis of our scheme along with sample complexity bounds. Our algorithm utilizes recent results from compressive sensing theory along with a novel convex quadratic program for recovering robust uniform approximations to univariate functions, from point queries corrupted with arbitrary bounded noise. Lastly we theoretically analyze the impact of noise – either arbitrary but bounded, or stochastic – on the performance of our algorithm.

Reference:

Efficient Sampling for Learning Sparse Additive Models in High Dimensions H. Tyagi, A. Krause, B. GärtnerIn Proc. Neural Information Processing Systems (NeurIPS), 2014

Bibtex Entry:

@inproceedings{tyagi14efficient\phi_i(x_i)$ from point queries of f. Here S is an unknown subset of coordinate variables with $|S|=k\leq d$. Assuming the $\phi_i$ to be smooth, we propose a set of points at which to sample f and an efficient randomized algorithm that recovers a uniform approximation to each unknown $\phi_i$. We provide a rigorous theoretical analysis of our scheme along with sample complexity bounds. Our algorithm utilizes recent results from compressive sensing theory along with a novel convex quadratic program for recovering robust uniform approximations to univariate functions, from point queries corrupted with arbitrary bounded noise. Lastly we theoretically analyze the impact of noise -- either arbitrary but bounded, or stochastic -- on the performance of our algorithm.},
	author = {Hemant Tyagi and Andreas Krause and Bernd G\"artner},
	booktitle = {Proc. Neural Information Processing Systems (NeurIPS)},
	title = {Efficient Sampling for Learning Sparse Additive Models in High Dimensions},
	year = {2014}}