Learning sparse polynomials

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

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 $\epsilon$, given only a set of examples $\bar x_i$ drawn uniformly from the $n$-dimensional cube (or an $n$-dimensional Gaussian distribution), together with evaluations $f(\bar x_i)$ on them. The result holds even in the ``noisy setting'', where we have only values $f(\bar x_i)+g$ where $g$ is noise (say, modeled as a Gaussian random variable). The runtime of our algorithm is polynomial in $n,k,1/\epsilon$ and $C_d$ where $C_d$ 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^{\Omega(d)}$ time barrier, even for $k=1$, and some believe it may be impossible to do so.

PDF file |

In SODA

Publisher ACM

Type | Inproceedings |

> Publications > Learning sparse polynomials