Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions

arXiv:2502.05073 · math.PR, cs.CC, cs.LG, math.CO · Submitted 2025-02-07 · Read on arXiv

math.PR, cs.CC, cs.LG, math.CO

Submitted: 2025-02-07

Updated: 2026-10-01

Terminology

• Agnostic Learning — 1× in this paper · explained in 1 episode
• Sample Complexity — 1× in this paper · explained in 17 episodes

Related papers

• Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms
• Local Anticoncentration for Gaussian Boson Sampling via Conditional Wishart Geometry
• Beyond the Semicircle: Free Diffusion Models with Prescribed Equilibria
• A New Bound on the Cumulant Generating Function of Dirichlet Processes
• The Site Frequency Spectrum in an Exponentially Growing Population with Selection
• Statistical inference for a multiscale stochastic model of enzyme kinetics via propagation of chaos