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

DOI10.1145/3519935.3519981MaRDI QIDQ6083477zbMATH OpenWikidataFDO

Authors Alexandros Eskenazis, Paata Ivanisvili

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.10162

zbMATH Keywords

Bohnenblust-Hille inequalitydiscrete hypercubelearning theory

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

Cited in

(10)

• Learning counting functions with queries
• Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
• Approximation of polynomials from Walsh tail spaces
• Bohnenblust-Hille inequality for cyclic groups
• Dimension-free discretizations of the uniform norm by small product sets
• Learning low-degree quantum objects
• Quantum and classical low-degree learning via a dimension-free Remez inequality
• Classical verification of quantum learning
• A cb-Bohnenblust-Hille inequality with constant one and its applications in learning theory
• Random algebraic graphs and their convergence to Erdős-Rényi

This page was built for publication: Learning low-degree functions from a logarithmic number of random queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083477)