@inproceedings{andoni2014learning,
author = {Andoni, Alexandr and Panigrahy, Rina and Valiant, Gregory and Zhang, Li},
title = {Learning sparse polynomials},
booktitle = {SODA},
year = {2014},
month = {January},
abstract = {We study the question of learning a sparse multi-variate polynomial over the real domain. In particular, for some unknown polynomial f(vx ) of degree-d and k monomials, we show how to reconstruct f, within error ε, given only a set of examples bar xi drawn uniformly from the n-dimensional cube (or an n-dimensional Gaussian distribution), together with evaluations f(bar xi) on them. The result holds even in the “noisy setting”, where we have only values f(bar xi)+g where g is noise (say, modeled as a Gaussian random variable). The runtime of our algorithm is polynomial in n,k,1/ε and Cd where Cd depends only on d. Note that, in contrast, in the “boolean version” of this problem, where bar x is drawn from the hypercube, the problem is at least as hard as the “noisy parity problem,” where we do not know how to break the nΩ(d) time barrier, even for k=1, and some believe it may be impossible to do so.},
publisher = {ACM},
url = {http://approjects.co.za/?big=en-us/research/publication/learning-sparse-polynomials/},
edition = {SODA},
}