Abstract: We consider the problem of learning sparse additive models, i.e., functions of the form: $f(\text{vecx})=\sum _{l\in S}{\varphi }_l(x_l)$, $\text{vecx}\in {\text{matR}}^d$ from point queries of $f$. Here $S$ is an unknown subset of coordinate variables with $\text{abs}S=k\ll d$. Assuming ${\varphi }_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 ${\varphi }_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.