Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks

2026/07/28 by Yunwei Ren, Zihao Wang, Jason D. Lee
#cs.LG #stat.ML

paper · pdf

Abstract

Despite the empirical advantages of deep networks over shallow ones, theoretical depth separations largely concern approximation power, while algorithmic results are mostly limited to comparisons between two- and three-layer networks. In this work, we prove the first algorithmic separation between constant-depth and logarithmic-depth networks. Specifically, we identify a class of Boolean functions with hierarchically structured Fourier spectra that logarithmic-depth networks can learn efficiently using layerwise coordinate descent by reconstructing the spectra hierarchically and adaptively. We also exhibit a subclass for which every constant-depth, polynomial-width network with sufficiently regular activations and controlled spectral norms must incur constant L² approximation error under the uniform distribution over the hypercube.

Citations

• Depth Separations in Neural Networks: Separating the Dimension from the Accuracy
• A Spectral Condition for Feature Learning
• Theoretical Analysis of Inductive Biases in Deep Convolutional Networks
• Depth Separation with Multilayer Mean-Field Networks
• SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics
• The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks
• Optimization-Based Separations for Neural Networks
• The staircase property: How hierarchical structure can guide deep learning
• Depth separation beyond radial functions
• Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Failures of Gradient-Based Deep Learning
• Depth Separation for Neural Networks
• Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
• Benefits of depth in neural networks
• The Power of Depth for Feedforward Neural Networks
• Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification
• Analysis of Boolean Functions

Related

• Depth Separation with Multilayer Mean-Field Networks
• Depth Separations in Neural Networks: What is Actually Being Separated?
• The staircase property: How hierarchical structure can guide deep learning
• Learning Functions: When Is Deep Better Than Shallow
• Depth Separations in Neural Networks: Separating the Dimension from the Accuracy