mlsanityData to 14 Oct 2026

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

arXiv 2607.25200 ↗First posted 28 Jul 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

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 L2 approximation error under the uniform distribution over the hypercube.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 23 of its 32 references that are in the map. First posted on arXiv 28 Jul 2026.

Builds on

23 of 32 references.

References · 23

  1. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  2. 2016Benefits of depth in neural networkscited by 250
  3. 2015The Power of Depth for Feedforward Neural Networkscited by 183
  4. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  5. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  6. 2023A Spectral Condition for Feature Learningcited by 109
  7. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  8. 2017Failures of Gradient-Based Deep Learningcited by 80
  9. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  10. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 59
  11. 2017Depth Separation for Neural Networkscited by 46
  12. 2023Theoretical Analysis of Inductive Biases in Deep Convolutional Networkscited by 21
11 more
  1. 2020Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learningcited by 19
  2. 2021Depth separation beyond radial functionscited by 18
  3. 2021Optimization-Based Separations for Neural Networkscited by 17
  4. 2026Phase Transitions for Feature Learning in Neural Networkscited by 11
  5. 2023Depth Separation with Multilayer Mean-Field Networkscited by 9
  6. 2026Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chainingcited by 6
  7. 2026Deep Learning of Compositional Targets with Hierarchical Spectral Methodscited by 5
  8. 2024Depth Separations in Neural Networks: Separating the Dimension from the Accuracycited by 4
  9. 2025The Computational Advantage of Depth: Learning High-Dimensional Hierarchical Functions with Gradient Descentcited by 3
  10. 2026Deep Networks Learn Deep Hierarchical Modelscited by 2
  11. 2026The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learningcited by 2

Built on by

Not cited yet.