Princeton researchers prove deeper nets learn functions shallow ones cannot

In a new arXiv preprint (2607.25200), Yunwei Ren, Zihao Wang, and Jason D. Lee from Princeton University present the first algorithmic depth separation result for neural networks. While prior work largely focused on approximation power (e.g., showing deeper networks can represent certain functions with fewer parameters), this paper tackles the harder question of learnability—which depth can actually be learned efficiently. The authors identify a specific class of Boolean functions whose Fourier spectrum has a hierarchical structure. They show that logarithmic-depth networks can learn these functions using a layerwise coordinate descent algorithm that reconstructs the spectrum adaptively from bottom to top.

On the other hand, the team proves a lower bound for constant-depth networks: any network with polynomial width, sufficiently regular activation functions (e.g., ReLU, sigmoid), and controlled spectral norms must incur a constant L2 approximation error under the uniform distribution. This implies that depth beyond a constant is not just beneficial for representation but algorithmically necessary for certain hierarchical learning tasks. The result bridges a key gap between theory and practice, providing rigorous justification for why deeper networks often outperform shallow ones even when the latter have enough parameters.