Research map / Architectures and efficiency / RNNs and normalization
How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the Sparse Random Hierarchy Model (SRHM), a sparse variant of the random hierarchy model, showing that deep networks learn insensitivity to discrete diffeomorphisms and synonym exchange at the same sample size where they learn the task, and quantifies sample complexity of LCNs and CNNs on it.
Problem
Why does test error correlate strongly with sensitivity to diffeomorphisms in image classification, and how does sparsity of informative features in hierarchical data affect learnability and sample complexity of deep networks?
Approach
Adding spatial sparsity (uninformative positions) to generative hierarchical models makes the task invariant to discrete versions of smooth transformations; networks learn synonym-invariant hierarchical representations and diffeomorphism insensitivity at the same training set size, which explains the correlation with performance.
Key results
- Sample complexity of LCNs scales as P* ~ C0 (s_0+1)^L n_c m^L, while CNNs scale as P* ~ C1 (s_0+1)^2 n_c m^L, showing weight sharing reduces the dependence on depth from exponential to quadratic in (s_0+1).
- Insensitivity to synonym exchange (S_2) and to discrete diffeomorphisms (D_2) is acquired at the same training set size as the test error threshold (P*_S ≈ P*_D ≈ P*_LCN) for LCNs, CNNs, VGG, ResNet, EfficientNet and FCNs.
- For fixed input dimension, higher sparsity (smaller fraction F of informative pixels) lowers LCN sample complexity, with P* growing with F for m > sqrt(s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the training set size | Deep networks trained on SRHM · SRHM | test error | Helped |
| Increase sparsity while holding input dimension fixed | LCN · SRHM | sample complexity: P^*_{LCN}\sim F^{\frac{\log m}{\log s}-\frac{1}{2}} d^{\frac{\log m}{\log s}+\frac{1}{2}} | Helped |
| Use weight sharing instead of locally connected weights | CNN versus LCN · SRHM | sample complexity: P^*_{LCN}\sim C_{0}(s,L)(s_0+1)^L n_c m^L; P^*_{CNN} \sim C_{1}(s_0+1)^{2} n_c m^L | Helped |
| Increase the training set to the task-learning scale | LCN · SRHM | sample complexity for synonym-exchange insensitivity: P_S^*\approx P^*_{LCN} | No clear effect |
| Increase the training set to the task-learning scale | LCN · SRHM | sample complexity for diffeomorphism insensitivity: P_D^*\approx P^*_{LCN} | No clear effect |
| Increase the training set to the task-learning scale | CNN · SRHM | sample complexity for synonym-exchange and diffeomorphism insensitivity: Both P^*_S and P^*_D align with P^*. | No clear effect |
| Use sparsity B instead of sparsity A (ablation) | LCN and CNN · SRHM | sample complexity scaling | No clear effect |
| Use a deep network rather than a shallow network | Networks trained on RHM · RHM | sample complexity: P^*\propto n_c m^L | Helped |
Surprising findings
- Higher sparsity makes the task easier for LCNs at fixed input dimension, so networks adapt to sparsity rather than being hurt by it.
Limitations
- Lacks an empirical procedure to measure insensitivity to synonyms on benchmark image datasets, so the prediction is not tested on real images.
- Analysis of sample complexity is heuristic for CNNs; the quadratic dependence on (s_0+1) is not yet explained.
- Results are on synthetic SRHM data with one-hot features and specific architectures (LCN/CNN with width 512).
Experimental setup
Datasets: SRHM synthetic hierarchical data CIFAR10
Benchmarks: SRHM synthetic data CIFAR10
Metrics: test error sample complexity sensitivity to synonym exchange S_k sensitivity to diffeomorphisms D_k
Baselines: VGG ResNet EfficientNet fully connected networks
Builds on: Random Hierarchy Model locally connected networks CNN
Closest papers by meaning
- From Flat to Hierarchical: Extracting Sparse Representations with Matching Pursuit (NeurIPS 2025 · similarity 0.88)
- Generative Hierarchical Learning of Sparse FRAME Models (CVPR 2017 · similarity 0.88)
- Sparsely Supervised Diffusion (NeurIPS 2026 · similarity 0.86)
- Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.86)
- Sparse maximal update parameterization: A holistic approach to sparse training dynamics (NeurIPS 2024 · similarity 0.86)
- Scaling Laws for Sparsely-Connected Foundation Models (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.