Abstract

We consider theP problem of learning sparse additive models, i.e., functions of the form: from point queries of f . Here S is an unknown subset of coordinate variables with |S| = Assuming 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 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.