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

arXiv: https://arxiv.org/abs/2607.25200 · HTML: https://mlsanity.com/paper/2607.25200/

## 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 (most cited first, 23 of 23)

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [A Spectral Condition for Feature Learning](https://mlsanity.com/paper/2310.17813/) (2023)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [Theoretical Analysis of Inductive Biases in Deep Convolutional Networks](https://mlsanity.com/paper/2305.08404/) (2023)
- [Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning](https://mlsanity.com/paper/2001.04413/) (2020)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [Optimization-Based Separations for Neural Networks](https://mlsanity.com/paper/2112.02393/) (2021)
- [Phase Transitions for Feature Learning in Neural Networks](https://mlsanity.com/paper/2602.01434/) (2026)
- [Depth Separation with Multilayer Mean-Field Networks](https://mlsanity.com/paper/2304.01063/) (2023)
- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [Deep Learning of Compositional Targets with Hierarchical Spectral Methods](https://mlsanity.com/paper/2602.10867/) (2026)
- [Depth Separations in Neural Networks: Separating the Dimension from the Accuracy](https://mlsanity.com/paper/2402.07248/) (2024)
- [The Computational Advantage of Depth: Learning High-Dimensional Hierarchical Functions with Gradient Descent](https://mlsanity.com/paper/2502.13961/) (2025)
- [Deep Networks Learn Deep Hierarchical Models](https://mlsanity.com/paper/2601.00455/) (2026)
- [The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learning](https://mlsanity.com/paper/2607.03347/) (2026)

## 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.