# Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions

arXiv: https://arxiv.org/abs/2502.05073 · HTML: https://mlsanity.com/paper/2502.05073/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 34 references that are in the map.
- First posted on arXiv 7 Feb 2025.

## Builds on (most cited first, 8 of 8)

- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Deep Learning and Hierarchal Generative Models](https://mlsanity.com/paper/1612.09057/) (2016)
- [Learning Functions: When Is Deep Better Than Shallow](https://mlsanity.com/paper/1603.00988/) (2016)
- [Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures](https://mlsanity.com/paper/2205.13647/) (2022)
- [Approximate resilience, monotonicity, and the complexity of agnostic learning](https://mlsanity.com/paper/1405.5268/) (2014)
- [A Probabilistic Theory of Deep Learning](https://mlsanity.com/paper/1504.00641/) (2015)
- [Reconstruction on Trees and Low-Degree Polynomials](https://mlsanity.com/paper/2109.06915/) (2021)
- [Noise Sensitivity and Stability of Deep Neural Networks for Binary Classification](https://mlsanity.com/paper/2308.09374/) (2023)

## Built on by (most cited first, 2 of 2)

- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [Deep Networks Learn Deep Hierarchical Models](https://mlsanity.com/paper/2601.00455/) (2026)

## Abstract (arXiv)

Recent works explore deep learning's success by examining functions or data with hierarchical structure. To study the learning complexity of functions with hierarchical structure, we study the noise stability of functions with tree hierarchical structure on independent inputs. We show that if each function in the hierarchy is varepsilon-far from linear, the noise stability is exponentially small in the depth of the hierarchy. Our results have immediate applications for agnostic learning. In the Boolean setting using the results of Dachman-Soled, Feldman, Tan, Wan and Wimmer (2014), our results provide Statistical Query super-polynomial lower bounds for agnostically learning classes that are based on hierarchical functions. We also derive similar SQ lower bounds based on the indicators of crossing events in critical site percolation. These crossing events are not formally hierarchical as we define but still have some hierarchical features as studied in mathematical physics. Using the results of Abbe, Bengio, Cornacchiam, Kleinberg, Lotfi, Raghu and Zhang (2022), our results imply sample complexity lower bounds for learning hierarchical functions with gradient descent on fully connected neural networks. Finally in the Gaussian setting, using the results of Diakonikolas, Kane, Pittas and Zarifis (2021), our results provide super-polynomial lower bounds for agnostic SQ learning.