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

• URL: http://arxiv.org/abs/2109.10162v1
• Date: Tue, 21 Sep 2021 13:19:04 GMT
• Title: Learning low-degree functions from a logarithmic number of random queries
• Authors: Alexandros Eskenazis and Paata Ivanisvili
• Abstract summary: We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
• Score: 77.34726150561087
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that for any integer $n\in\mathbb{N}$, $d\in\{1,\ldots,n\}$ and any $\varepsilon,\delta\in(0,1)$, a bounded function $f:\{-1,1\}^n\to[-1,1]$ of degree at most $d$ can be learned with probability at least $1-\delta$ and $L_2$-error $\varepsilon$ using $\log(\tfrac{n}{\delta})\,\varepsilon^{-d-1} C^{d^{3/2}\sqrt{\log d}}$ random queries for a universal finite constant $C>1$.

Related papers

Err

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.