# The Computational Advantage of Depth: Learning High-Dimensional Hierarchical Functions with Gradient Descent

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2025.

## Built on by (most cited first, 3 of 3)

- [Deep Learning of Compositional Targets with Hierarchical Spectral Methods](https://mlsanity.com/paper/2602.10867/) (2026)
- [Scaling Laws from Sequential Feature Recovery: A Solvable Hierarchical Model](https://mlsanity.com/paper/2605.14567/) (2026)
- [Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks](https://mlsanity.com/paper/2607.25200/) (2026)

## Abstract (arXiv)

Understanding the advantages of deep neural networks trained by gradient descent (GD) compared to shallow models remains an open theoretical challenge. In this paper, we introduce a class of target functions (single and multi-index Gaussian hierarchical targets) that incorporate a hierarchy of latent subspace dimensionalities. This framework enables us to analytically study the learning dynamics and generalization performance of deep networks compared to shallow ones in the high-dimensional limit. Specifically, our main theorem shows that feature learning with GD successively reduces the effective dimensionality, transforming a high-dimensional problem into a sequence of lower-dimensional ones. This enables learning the target function with drastically less samples than with shallow networks. While the results are proven in a controlled training setting, we also discuss more common training procedures and argue that they learn through the same mechanisms.