# Deep Learning and Hierarchal Generative Models

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2016.

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

- [A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data](https://mlsanity.com/paper/2402.16991/) (2024)
- [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)
- [Towards a theory of how the structure of language is acquired by deep neural networks](https://mlsanity.com/paper/2406.00048/) (2024)
- [Probing the Latent Hierarchical Structure of Data via Diffusion Models](https://mlsanity.com/paper/2410.13770/) (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)
- [On Data-Augmentation and Consistency-Based Semi-Supervised Learning](https://mlsanity.com/paper/2101.06967/) (2021)
- [Reconstruction on Trees and Low-Degree Polynomials](https://mlsanity.com/paper/2109.06915/) (2021)
- [Kernel Methods and Multi-layer Perceptrons Learn Linear Models in High Dimensions](https://mlsanity.com/paper/2201.08082/) (2022)
- [How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model](https://mlsanity.com/paper/2404.10727/) (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 of Compositional Targets with Hierarchical Spectral Methods](https://mlsanity.com/paper/2602.10867/) (2026)
- [Towards Worst-Case Guarantees with Scale-Aware Interpretability](https://mlsanity.com/paper/2602.05184/) (2026)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions](https://mlsanity.com/paper/2502.05073/) (2025)
- [Sampling Data with Chains of Forward-Backward Diffusion Steps](https://mlsanity.com/paper/2605.27006/) (2026)
- [Statistical Properties of Training & Generalization](https://mlsanity.com/paper/2606.20299/) (2026)
- [Learning with Shallow Neural Networks on Cluster-Structured Features](https://mlsanity.com/paper/2605.14927/) (2026)
- [Self-supervised local learning rules learn the hidden hierarchical structure of high-dimensional data](https://mlsanity.com/paper/2605.18557/) (2026)
- [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)
- [Scaling Laws from Sequential Feature Recovery: A Solvable Hierarchical Model](https://mlsanity.com/paper/2605.14567/) (2026)
- [A theory of platonic representations in language models](https://mlsanity.com/paper/2610.07168/) (2026)

## Abstract (arXiv)

It is argued that deep learning is efficient for data that is generated from hierarchal generative models. Examples of such generative models include wavelet scattering networks, functions of compositional structure, and deep rendering models. Unfortunately so far, for all such models, it is either not rigorously known that they can be learned efficiently, or it is not known that "deep algorithms" are required in order to learn them. We propose a simple family of "generative hierarchal models" which can be efficiently learned and where "deep" algorithm are necessary for learning. Our definition of "deep" algorithms is based on the empirical observation that deep nets necessarily use correlations between features. More formally, we show that in a semi-supervised setting, given access to low-order moments of the labeled data and all of the unlabeled data, it is information theoretically impossible to perform classification while at the same time there is an efficient algorithm, that given all labelled and unlabeled data, perfectly labels all unlabelled data with high probability. For the proof, we use and strengthen the fact that Belief Propagation does not admit a good approximation in terms of linear functions.