分层函数的噪声敏感性与学习下界

View PDF HTML (experimental)

Abstract: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.

Comments:	23 pages
Subjects:	Probability (math.PR); Computational Complexity (cs.CC); Machine Learning (cs.LG); Combinatorics (math.CO)
Cite as:	arXiv:2502.05073 [math.PR]
	(or arXiv:2502.05073v4 [math.PR] for this version)
	https://doi.org/10.48550/arXiv.2502.05073 arXiv-issued DOI via DataCite

Submission history

From: Rupert Li [view email]
[v1] Fri, 7 Feb 2025 16:45:27 UTC (26 KB)
[v2] Wed, 14 May 2025 22:45:07 UTC (27 KB)
[v3] Mon, 29 Sep 2025 06:18:45 UTC (20 KB)
[v4] Thu, 1 Oct 2026 21:30:42 UTC (143 KB)