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

2021/09/21 by Alexandros Eskenazis, Paata Ivanisvili, Eskenazis, Alexandros +1 · 2 citations
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms

paper · doi:10.48550/arxiv.2109.10162

openalex publication_date 2021/09/21 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

Abstract

We prove that every bounded function f:\-1,1\ⁿ→[-1,1] of degree at most d can be learned with L₂-accuracy ε and confidence 1-δ from log(\tfracnδ) ε^-d-1 C^d^3/2√(log d) random queries, where C>1 is a universal finite constant.

Cited by

• Approximating the operator norm of local Hamiltonians via few quantum states
• Entropy and Learning of Lipschitz Functions under Log-Concave Measures

Related

• Low-degree learning and the metric entropy of polynomials
• Learning from satisfying assignments under continuous distributions
• Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
• Low-degree tests at large distances
• Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness