Learning sparse polynomials - Andoni, Alexandr; Panigrahy, Rina; Valiant, Gregory; Zhang, Li (SODA, 2014)
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.