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

Sources

• Learning Functions: When Is Deep Better Than Shallow
• Deep Learning and Hierarchal Generative Models
• A Probabilistic Theory of Deep Learning
• Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining
• Benefits of depth in neural networks

Related papers

• Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms
• Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
• 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