# How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 65 references that are in the map.
- First posted on arXiv 16 Apr 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Visualizing and Understanding Convolutional Networks](https://mlsanity.com/paper/1311.2901/) (2013)
- [Group Equivariant Convolutional Networks](https://mlsanity.com/paper/1602.07576/) (2016)
- [E(3)-Equivariant Graph Neural Networks for Data-Efficient and Accurate Interatomic Potentials](https://mlsanity.com/paper/2101.03164/) (2021)
- [Deep Learning Scaling is Predictable, Empirically](https://mlsanity.com/paper/1712.00409/) (2017)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Making Convolutional Networks Shift-Invariant Again](https://mlsanity.com/paper/1904.11486/) (2019)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups](https://mlsanity.com/paper/1802.03690/) (2018)
- [Why do deep convolutional networks generalize so poorly to small image transformations?](https://mlsanity.com/paper/1805.12177/) (2018)
- [Spatially Transformed Adversarial Examples](https://mlsanity.com/paper/1801.02612/) (2018)
- [A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups](https://mlsanity.com/paper/2104.09459/) (2021)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [Strike (with) a Pose: Neural Networks Are Easily Fooled by Strange Poses of Familiar Objects](https://mlsanity.com/paper/1811.11553/) (2018)
- [On Translation Invariance in CNNs: Convolutional Layers can Exploit Absolute Spatial Location](https://mlsanity.com/paper/2003.07064/) (2020)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data](https://mlsanity.com/paper/2402.16991/) (2024)
- [Exploiting Cyclic Symmetry in Convolutional Neural Networks](https://mlsanity.com/paper/1602.02660/) (2016)
- [Provably Strict Generalisation Benefit for Equivariant Models](https://mlsanity.com/paper/2102.10333/) (2021)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Understanding Deep Convolutional Networks](https://mlsanity.com/paper/1601.04920/) (2016)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Geometric robustness of deep networks: analysis and improvement](https://mlsanity.com/paper/1711.09115/) (2017)
- [Learning the Irreducible Representations of Commutative Lie Groups](https://mlsanity.com/paper/1402.4437/) (2014)

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

- [Towards a theory of how the structure of language is acquired by deep neural networks](https://mlsanity.com/paper/2406.00048/) (2024)
- [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)
- [Learning curves theory for hierarchically compositional data with power-law distributed features](https://mlsanity.com/paper/2505.07067/) (2025)
- [Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures](https://mlsanity.com/paper/2505.07070/) (2025)
- [An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars](https://mlsanity.com/paper/2606.17522/) (2026)
- [A Hierarchical Language Model with Predictable Scaling Laws and Provable Benefits of Reasoning](https://mlsanity.com/paper/2605.13687/) (2026)

## Abstract (arXiv)

Understanding what makes high-dimensional data learnable is a fundamental question in machine learning. On the one hand, it is believed that the success of deep learning lies in its ability to build a hierarchy of representations that become increasingly more abstract with depth, going from simple features like edges to more complex concepts. On the other hand, learning to be insensitive to invariances of the task, such as smooth transformations for image datasets, has been argued to be important for deep networks and it strongly correlates with their performance. In this work, we aim to explain this correlation and unify these two viewpoints. We show that by introducing sparsity to generative hierarchical models of data, the task acquires insensitivity to spatial transformations that are discrete versions of smooth transformations. In particular, we introduce the Sparse Random Hierarchy Model (SRHM), where we observe and rationalize that a hierarchical representation mirroring the hierarchical model is learnt precisely when such insensitivity is learnt, thereby explaining the strong correlation between the latter and performance. Moreover, we quantify how the sample complexity of CNNs learning the SRHM depends on both the sparsity and hierarchical structure of the task.