# How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model

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

## Key facts

- Cited by 71 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 79 references that are in the map.
- First posted on arXiv 5 Jul 2023.

## Builds on (most cited first, 30 of 38)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Visualizing and Understanding Convolutional Networks](https://mlsanity.com/paper/1311.2901/) (2013)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Opening the Black Box of Deep Neural Networks via Information](https://mlsanity.com/paper/1703.00810/) (2017)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [The Intrinsic Dimension of Images and Its Impact on Learning](https://mlsanity.com/paper/2104.08894/) (2021)
- [Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation](https://mlsanity.com/paper/1404.0736/) (2014)
- [Intrinsic dimension of data representations in deep neural networks](https://mlsanity.com/paper/1905.12784/) (2019)
- [Predicting Parameters in Deep Learning](https://mlsanity.com/paper/1306.0543/) (2013)
- [Feature Learning in Infinite-Width Neural Networks](https://mlsanity.com/paper/2011.14522/) (2020)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [A mathematical theory of semantic development in deep neural networks](https://mlsanity.com/paper/1810.10531/) (2018)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation](https://mlsanity.com/paper/1902.04760/) (2019)
- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [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)
- [Towards Learning Convolutions from Scratch](https://mlsanity.com/paper/2007.13657/) (2020)
- [Dimensionality compression and expansion in Deep Neural Networks](https://mlsanity.com/paper/1906.00443/) (2019)
- [Hierarchical nucleation in deep neural networks](https://mlsanity.com/paper/2007.03506/) (2020)
- [Data-driven emergence of convolutional structure in neural networks](https://mlsanity.com/paper/2202.00565/) (2022)
- [Geometric compression of invariant manifolds in neural nets](https://mlsanity.com/paper/2007.11471/) (2020)
- [Locality defeats the curse of dimensionality in convolutional teacher-student scenarios](https://mlsanity.com/paper/2106.08619/) (2021)
- [Deep Learning and Hierarchal Generative Models](https://mlsanity.com/paper/1612.09057/) (2016)

## Built on by (most cited first, 30 of 71)

- [A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data](https://mlsanity.com/paper/2402.16991/) (2024)
- [How Linguistics Learned to Stop Worrying and Love the Language Models](https://mlsanity.com/paper/2501.17047/) (2025)
- [Critical windows: non-asymptotic theory for feature emergence in diffusion models](https://mlsanity.com/paper/2403.01633/) (2024)
- [Get rich quick: exact solutions reveal how unbalanced initializations promote rapid feature learning](https://mlsanity.com/paper/2406.06158/) (2024)
- [Towards a theory of how the structure of language is acquired by deep neural networks](https://mlsanity.com/paper/2406.00048/) (2024)
- [There Will Be a Scientific Theory of Deep Learning](https://mlsanity.com/paper/2604.21691/) (2026)
- [Probing the Latent Hierarchical Structure of Data via Diffusion Models](https://mlsanity.com/paper/2410.13770/) (2024)
- [How Compositional Generalization and Creativity Improve as Diffusion Models are Trained](https://mlsanity.com/paper/2502.12089/) (2025)
- [Bigger Isn't Always Memorizing: Early Stopping Overparameterized Diffusion Models](https://mlsanity.com/paper/2505.16959/) (2025)
- [A distributional simplicity bias in the learning dynamics of transformers](https://mlsanity.com/paper/2410.19637/) (2024)
- [Deriving Neural Scaling Laws from the statistics of natural language](https://mlsanity.com/paper/2602.07488/) (2026)
- [How transformers learn structured data: insights from hierarchical filtering](https://mlsanity.com/paper/2408.15138/) (2024)
- [U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Models](https://mlsanity.com/paper/2404.18444/) (2024)
- [Analyzing (In)Abilities of SAEs via Formal Languages](https://mlsanity.com/paper/2410.11767/) (2024)
- [Learning curves theory for hierarchically compositional data with power-law distributed features](https://mlsanity.com/paper/2505.07067/) (2025)
- [Position: A Theory of Deep Learning Must Include Compositional Sparsity](https://mlsanity.com/paper/2507.02550/) (2025)
- [On the origin of neural scaling laws: from random graphs to natural language](https://mlsanity.com/paper/2601.10684/) (2026)
- [On the Emergence of Linear Analogies in Word Embeddings](https://mlsanity.com/paper/2505.18651/) (2025)
- [Disentangling the Factors of Convergence between Brains and Computer Vision Models](https://mlsanity.com/paper/2508.18226/) (2025)
- [Feature learning in finite-width Bayesian deep linear networks with multiple outputs and convolutional layers](https://mlsanity.com/paper/2406.03260/) (2024)
- [Analyzing Neural Scaling Laws in Two-Layer Networks with Power-Law Data Spectra](https://mlsanity.com/paper/2410.09005/) (2024)
- [Generalization Dynamics of Linear Diffusion Models](https://mlsanity.com/paper/2505.24769/) (2025)
- [Inverse Depth Scaling From Most Layers Being Similar](https://mlsanity.com/paper/2602.05970/) (2026)
- [How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model](https://mlsanity.com/paper/2404.10727/) (2024)
- [Scaling can lead to compositional generalization](https://mlsanity.com/paper/2507.07207/) (2025)
- [Random features and polynomial rules](https://mlsanity.com/paper/2402.10164/) (2024)
- [How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning](https://mlsanity.com/paper/2407.05664/) (2024)
- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures](https://mlsanity.com/paper/2505.07070/) (2025)
- [Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets](https://mlsanity.com/paper/2511.20888/) (2025)

## Abstract (arXiv)

Deep learning algorithms demonstrate a surprising ability to learn high-dimensional tasks from limited examples. This is commonly attributed to the depth of neural networks, enabling them to build a hierarchy of abstract, low-dimensional data representations. However, how many training examples are required to learn such representations remains unknown. To quantitatively study this question, we introduce the Random Hierarchy Model: a family of synthetic tasks inspired by the hierarchical structure of language and images. The model is a classification task where each class corresponds to a group of high-level features, chosen among several equivalent groups associated with the same class. In turn, each feature corresponds to a group of sub-features chosen among several equivalent ones and so on, following a hierarchy of composition rules. We find that deep networks learn the task by developing internal representations invariant to exchanging equivalent groups. Moreover, the number of data required corresponds to the point where correlations between low-level features and classes become detectable. Overall, our results indicate how deep networks overcome the curse of dimensionality by building invariant representations, and provide an estimate of the number of data required to learn a hierarchical task.