Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Learning sparse polynomials

Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang

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.

Details

Publication typeInproceedings
Published inSODA
PublisherACM
> Publications > Learning sparse polynomials