# The staircase property: How hierarchical structure can guide deep learning

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

## Key facts

- Cited by 62 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 55 references that are in the map.
- First posted on arXiv 24 Aug 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Visualizing and Understanding Convolutional Networks](https://mlsanity.com/paper/1311.2901/) (2013)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation](https://mlsanity.com/paper/1604.06057/) (2016)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [SGD on Neural Networks Learns Functions of Increasing Complexity](https://mlsanity.com/paper/1905.11604/) (2019)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Training Neural Networks with Local Error Signals](https://mlsanity.com/paper/1901.06656/) (2019)
- [The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies](https://mlsanity.com/paper/1906.00425/) (2019)
- [Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks](https://mlsanity.com/paper/1904.13262/) (2019)
- [Greedy Layerwise Learning Can Scale to ImageNet](https://mlsanity.com/paper/1812.11446/) (2018)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Decoupled Greedy Learning of CNNs](https://mlsanity.com/paper/1901.08164/) (2019)
- [The Implicit Bias of Depth: How Incremental Learning Drives Generalization](https://mlsanity.com/paper/1909.12051/) (2019)
- [Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective](https://mlsanity.com/paper/2002.06262/) (2020)
- [Towards Understanding Hierarchical Learning: Benefits of Neural Representations](https://mlsanity.com/paper/2006.13436/) (2020)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [Deep Learning and Hierarchal Generative Models](https://mlsanity.com/paper/1612.09057/) (2016)
- [Is Deeper Better only when Shallow is Good?](https://mlsanity.com/paper/1903.03488/) (2019)
- [A Provably Correct Algorithm for Deep Learning that Actually Works](https://mlsanity.com/paper/1803.09522/) (2018)
- [Learning Functions: When Is Deep Better Than Shallow](https://mlsanity.com/paper/1603.00988/) (2016)
- [ID3 Learns Juntas for Smoothed Product Distributions](https://mlsanity.com/paper/1906.08654/) (2019)
- [A Corrective View of Neural Networks: Representation, Memorization and Learning](https://mlsanity.com/paper/2002.00274/) (2020)
- [Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth](https://mlsanity.com/paper/2006.04048/) (2020)

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

- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Scaling Laws for Precision](https://mlsanity.com/paper/2411.04330/) (2024)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [How Two-Layer Neural Networks Learn, One (Giant) Step at a Time](https://mlsanity.com/paper/2305.18270/) (2023)
- [How Feature Learning Can Improve Neural Scaling Laws](https://mlsanity.com/paper/2409.17858/) (2024)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [Asymptotics of feature learning in two-layer networks after one gradient-step](https://mlsanity.com/paper/2402.04980/) (2024)
- [Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions](https://mlsanity.com/paper/2405.15459/) (2024)
- [Catapults in SGD: spikes in the training loss and their impact on generalization through feature learning](https://mlsanity.com/paper/2306.04815/) (2023)
- [A Mathematical Model for Curriculum Learning for Parities](https://mlsanity.com/paper/2301.13833/) (2023)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Mixed Dynamics In Linear Networks: Unifying the Lazy and Active Regimes](https://mlsanity.com/paper/2405.17580/) (2024)
- [On the Limitations of Compute Thresholds as a Governance Strategy](https://mlsanity.com/paper/2407.05694/) (2024)
- [Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures](https://mlsanity.com/paper/2205.13647/) (2022)
- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [Towards a theory of model distillation](https://mlsanity.com/paper/2403.09053/) (2024)
- [On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries](https://mlsanity.com/paper/2407.05622/) (2024)
- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [Hidden Breakthroughs in Language Model Training](https://mlsanity.com/paper/2506.15872/) (2025)
- [Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networks](https://mlsanity.com/paper/2506.06489/) (2025)
- [Position: A Theory of Deep Learning Must Include Compositional Sparsity](https://mlsanity.com/paper/2507.02550/) (2025)
- [Sliding down the stairs: how correlated latent variables accelerate learning with neural networks](https://mlsanity.com/paper/2404.08602/) (2024)
- [Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methods](https://mlsanity.com/paper/2205.14818/) (2022)
- [From Kernels to Features: A Multi-Scale Adaptive Theory of Feature Learning](https://mlsanity.com/paper/2502.03210/) (2025)
- [Tilting the Odds at the Lottery: the Interplay of Overparameterisation and Curricula in Neural Networks](https://mlsanity.com/paper/2406.01589/) (2024)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [On the symmetries in the dynamics of wide two-layer neural networks](https://mlsanity.com/paper/2211.08771/) (2022)

## Abstract (arXiv)

This paper identifies a structural property of data distributions that enables deep neural networks to learn hierarchically. We define the "staircase" property for functions over the Boolean hypercube, which posits that high-order Fourier coefficients are reachable from lower-order Fourier coefficients along increasing chains. We prove that functions satisfying this property can be learned in polynomial time using layerwise stochastic coordinate descent on regular neural networks -- a class of network architectures and initializations that have homogeneity properties. Our analysis shows that for such staircase functions and neural networks, the gradient-based algorithm learns high-level features by greedily combining lower-level features along the depth of the network. We further back our theoretical results with experiments showing that staircase functions are also learnable by more standard ResNet architectures with stochastic gradient descent. Both the theoretical and experimental results support the fact that staircase properties have a role to play in understanding the capabilities of gradient-based learning on regular networks, in contrast to general polynomial-size networks that can emulate any SQ or PAC algorithms as recently shown.