Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions

Rupert Li, Elchanan Mossel

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,…