Department of Computer Science | Institute of Theoretical Computer Science

We consider the problem of learning sparse additive models,
i.e. functions of the form f(x)=\sum_{l\in S}\phi_l(x_l), x\in \R^d,
from point queries of. Here, S is an unknown is an unknown ubset of
coordinate variables with |S|=k\ll d. Assuming \phi_l's to be smooth,
we propose a set of points at which to sample and an efficient
randomized algorithm that recovers a uniform approximation to
each unknown \phi_l. 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.