Learning sparse polynomial functions

andoni, rina, Gregory Valiant, and lzha

2014

## 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 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/ε* 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*^{Ω(d)} time barrier, even for *k=1*, and some believe it may be impossible to do so.

## Details

Publication type | Inproceedings |

Published in | SODA |

Publisher | ACM |