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

09/21/2021

∙

by   Alexandros Eskenazis, et al.

∙

0

∙

share

We prove that for any integer n∈ℕ, d∈{1,…,n} and any ε,δ∈(0,1), a bounded function f:{-1,1}^n→[-1,1] of degree at most d can be learned with probability at least 1-δ and L_2-error ε using log(nδ) ε^-d-1 C^d^3/2√(log d) random queries for a universal finite constant C>1.