nucleation

LIT-880: How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model

4 min read

Properties4
StatusActive — read 2026-10-09 (NOTE-684); worth reading as the sparse extension of the Random Hierarchy Model (LIT-877) and as a model-based account of why a network's insensitivity to small smooth deformations of its input tracks its test error. Each informative feature of the RHM is padded with s0 uninformative "empty" positions and may sit anywhere in its sub-patch, so the data become very sparse (s^L informative positions among (s(s0 + 1))^L) and the label is unchanged by discrete displacements of the informative features, a stand-in for diffeomorphisms of an image. On this Sparse Random Hierarchy Model, deep locally connected and convolutional networks learn from a number of examples polynomial in the input dimension: measured, P* ≈ s^(L/2)(s0 + 1)^L n_c m^L without weight sharing and P* ≈ C(s0 + 1)^2 n_c m^L with it. At about that training-set size the hidden layers become insensitive both to swapping synonymous tuples and to displacing features, so the two invariances and good performance arrive together; the paper offers this as the explanation of the correlation between deformation stability and test error measured on CIFAR-10. The laws are fitted, the (s0 + 1)^L factor has a one-step-gradient argument for locally connected networks, the CNN's (s0 + 1)^2 is unexplained, and the image case is an analogy: no synonym sensitivity was measured on images.
Tagslearning-theory, compositionality, representation-learning, anthology-candidate
Cited as “paper” byNOTE-684 — The Sparse Random Hierarchy Model
Cited as “source” byTHEORY-200 — On sparse hierarchical data, deep networks become insensitive to swapping synonymous parts and to small displacements of informative features at the training-set size at which they learn the task

Graph View

Umberto M. Tomasini and Matthieu Wyart (2024), Proceedings of the 41st International Conference on Machine Learning, PMLR 235:48369–48389 — ARXIV-2404.10727

Key takeaways

  • The model. The Random Hierarchy Model of LIT-877 (n_c classes, L levels of v symbols, each symbol rewriting to m synonymous s-tuples) with an uninformative symbol 0 added at every level. In sparsity A, each of the s informative children sits in its own sub-patch of s0 + 1 positions with exactly s0 empties, at a position chosen independently; in sparsity B, the s children may sit anywhere in the s(s0 + 1) patch in their order. An empty symbol rewrites to an all-empty patch. An input has d = (s(s0 + 1))^L positions of which s^L are informative, one-hot over v, and the label is unchanged when informative features move within their allowed positions: a discrete deformation.
  • Polynomial sample complexity, with sparsity costing differently by architecture. At maximal m = v^(s−1), n_c = v, depth-L networks with filter size and stride s(s0 + 1) matched to the tree reach 10% test error at P_LCN ≈ s^(L/2)(s0 + 1)^L n_c m^L without weight sharing (Eq. 3, Figs. 4B, 10) and P_CNN ≈ C(s0 + 1)^2 n_c m^L with it (Eq. 4, Figs. 4C, 13). Both are exponential in L, so polynomial in d. Sparsity B gives the same collapses (Figs. 7, 8). At fixed d, sparser data are easier for the locally connected network, P*_LCN ∝ F^(log m/log s − 1/2) d^(log m/log s + 1/2) with F = (s0 + 1)^(−L) the informative fraction, when m > √s (Eq. 5, Fig. 5).
  • Two invariances learned at once, and with the task. The second layer’s sensitivity to swapping synonymous tuples (S_2, Eq. 6) and to displacing features within their patches (D_2, Eq. 7) fall below fixed thresholds at training-set sizes P_S and P_D that match P* across L, v, s and s0 (Figs. 6, 11, 14), for LCNs, CNNs and fully connected networks (Fig. 16). Invariance to level-l transformations appears from layer l + 1 on, all levels at the same P (Figs. 12, 15). The thresholds for S_2 and D_2 were tuned per setting (between 10% and 50%) by looking at the curves.
  • The correlation of deformation stability with error, reproduced. VGG, ResNet and EfficientNet networks and the matched LCN and CNN, trained on one SRHM instance (L = s = s0 = 2, n_c = m = 10, P = 7400) show test error rising with the output’s sensitivity to deformations and to synonym swaps, as Petrini et al. found for deformations on CIFAR-10 (Figs. 1, 9, 17).
  • The argument. In a locally connected network each first-layer weight sees one input position, which is informative in a fraction (s0 + 1)^(−L) of the data. The first gradient step from a symmetric initialisation is then the non-sparse RHM’s step with P(s0 + 1)^(−L) examples (Appendix C, Eq. 12), so the correlation threshold n_c m^L of LIT-877 is multiplied by (s0 + 1)^L. Since all displaced and all synonymous versions of one parent carry the same class statistics, the grouping that gives synonym invariance gives displacement invariance too. The s^(L/2) prefactor and the CNN’s (s0 + 1)^2 are not derived.

Standing in the record

Filed on 2026-10-09 at the owner’s request, as one of the works cited by the batch on hierarchy and hyperbolic geometry (nucleation#113, LIT-865 to LIT-877) that neither record held. LIT-877, which introduces the Random Hierarchy Model, names it as one of the same group’s later papers built on that model. Read on its own merits (NOTE-684); the reading produces THEORY-200, which extends THEORY-195 to sparse data.

It does not bear on QUESTION-025 beyond what LIT-877 already does. Its hierarchy is the same part–whole constituency, and what it adds is a second kind of nuisance, position, beside the first, synonymy; it measures no co-occurrence matrix, embedding direction or attribute. What it adds to the record is a candidate account of why a learned representation is insensitive to small deformations: not because the architecture was built for it, but because displaced and synonymous versions of a part carry the same statistics with respect to the label and are grouped together by the same learning step. The record’s other holding on deformation stability is the geometric-deep-learning blueprint (LIT-319, §3.3), which imposes it as a prior rather than measuring when it is learned.

Backlinks