Learning low-degree functions from a logarithmic number of random queries

Abstract

We prove that every bounded function $f:\{-1,1{\}}^n\to [-1,1]$ of degree at most $d$ can be learned with $L_2$-accuracy $\epsilon$ and confidence $1-\delta$ from $\log (\frac{n}{\delta }){\epsilon }^{-d-1}{C}^{d^{3/2}\sqrt{\log d}}$ random queries, where $C>1$ is a universal finite constant.