Learning low-degree functions from a logarithmic number of random queries
arXiv:2109.10162v323 citations
Originality Incremental advance
AI Analysis
This provides a theoretical improvement in query complexity for learning low-degree functions, which is incremental but addresses a known bottleneck in computational learning theory.
The paper tackles the problem of learning bounded low-degree Boolean functions from random queries, achieving an L2-accuracy of ε with a query complexity that scales logarithmically in n and exponentially in d, specifically log(n/δ) * ε^{-d-1} * C^{d^{3/2}√log d}.
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 $\varepsilon$ and confidence $1-δ$ from $\log(\tfrac{n}δ)\,\varepsilon^{-d-1} C^{d^{3/2}\sqrt{\log d}}$ random queries, where $C>1$ is a universal finite constant.