Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining

Yunwei Ren, Yatin Dandi, Florent Krzakala, Jason D. Lee
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5556-5597, 2026.

Abstract

The empirical success of deep learning is often attributed to deep networks’ ability to exploit hierarchical structure in data, constructing increasingly complex features across layers. Yet despite substantial progress in deep learning theory, most optimization results still focus on networks with only two or three layers, leaving the theoretical understanding of hierarchical learning in genuinely deep models limited. This leads to a natural question: can we prove that deep networks, trained with gradient-based methods and standard input-label pairs, can efficiently exploit hierarchical structure? In this work, we consider Random Hierarchy Models — a hierarchical context-free grammar introduced by Cagnetta et al. (2024) and conjectured to separate deep and shallow networks. We prove that, under mild conditions, a deep convolutional network can be efficiently trained to learn this function class. Our proof builds on a general observation: if intermediate layers can receive clean signal from the labels and the relevant features are weakly identifiable, then layerwise training each individual layer suffices to hierarchically learn the target function.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-ren26a, title = {Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining}, author = {Ren, Yunwei and Dandi, Yatin and Krzakala, Florent and Lee, Jason D.}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {5556--5597}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/ren26a/ren26a.pdf}, url = {https://proceedings.mlr.press/v336/ren26a.html}, abstract = { The empirical success of deep learning is often attributed to deep networks’ ability to exploit hierarchical structure in data, constructing increasingly complex features across layers. Yet despite substantial progress in deep learning theory, most optimization results still focus on networks with only two or three layers, leaving the theoretical understanding of hierarchical learning in genuinely deep models limited. This leads to a natural question: can we prove that deep networks, trained with gradient-based methods and standard input-label pairs, can efficiently exploit hierarchical structure? In this work, we consider Random Hierarchy Models — a hierarchical context-free grammar introduced by Cagnetta et al. (2024) and conjectured to separate deep and shallow networks. We prove that, under mild conditions, a deep convolutional network can be efficiently trained to learn this function class. Our proof builds on a general observation: if intermediate layers can receive clean signal from the labels and the relevant features are weakly identifiable, then layerwise training each individual layer suffices to hierarchically learn the target function. } }
Endnote
%0 Conference Paper %T Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining %A Yunwei Ren %A Yatin Dandi %A Florent Krzakala %A Jason D. Lee %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-ren26a %I PMLR %P 5556--5597 %U https://proceedings.mlr.press/v336/ren26a.html %V 336 %X The empirical success of deep learning is often attributed to deep networks’ ability to exploit hierarchical structure in data, constructing increasingly complex features across layers. Yet despite substantial progress in deep learning theory, most optimization results still focus on networks with only two or three layers, leaving the theoretical understanding of hierarchical learning in genuinely deep models limited. This leads to a natural question: can we prove that deep networks, trained with gradient-based methods and standard input-label pairs, can efficiently exploit hierarchical structure? In this work, we consider Random Hierarchy Models — a hierarchical context-free grammar introduced by Cagnetta et al. (2024) and conjectured to separate deep and shallow networks. We prove that, under mild conditions, a deep convolutional network can be efficiently trained to learn this function class. Our proof builds on a general observation: if intermediate layers can receive clean signal from the labels and the relevant features are weakly identifiable, then layerwise training each individual layer suffices to hierarchically learn the target function.
APA
Ren, Y., Dandi, Y., Krzakala, F. & Lee, J.D.. (2026). Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:5556-5597 Available from https://proceedings.mlr.press/v336/ren26a.html.

Related Material