Efficient Sampling for Learning Sparse Additive Models in High Dimensions

Here $S$ is an unknown subset of coordinate variables with $\abs{S} k \ll d$. Assuming $\phi_l$'s to be smooth, we propose a set of points at which to sample $f$ and an efficient randomized algorithm that recovers a \textit{uniform approximation} to each unknown $\phi_l$. We provide a rigorous theoretical analysis of our scheme along with sample complexity bounds. Lastly we theoretically analyze the impact of noise -- either arbitrary but bounded, or stochastic -- on the performance of our algorithm. Papers published at the Neural Information Processing Systems Conference.