NOTE-677: The Random Hierarchy Model

Contribution

A synthetic family of classification tasks, generated by a random context-free grammar, in which the number of examples a network needs can be measured and in part predicted. Before it, depth was known to help represent hierarchically compositional functions with few parameters (Poggio, Mhaskar et al.; Schmidt-Hieber), and to support a polynomial information-theoretic bound, but not to help networks trained by gradient descent learn from few examples. The paper shows by experiment that it does here: P* ≈ n_c m^L for deep CNNs in a feature-learning regime, against a constant fraction of P_max (exponential in d) for two-layer and lazy networks. It ties that number to two others, the onset of invariance to synonyms in the hidden layers and the detectability of patch–label correlations, and shows the correlations are necessary.

Key insight

A hierarchical task is learnable from few data when its low-level parts carry a detectable trace of the label, because the trace is the same for parts that are interchangeable. Counting how often each s-tuple appears with each class groups synonymic tuples together (same parent, same counts), and collapsing each group to one symbol reduces the input from s^L to s^(L−1) positions; repeating this L times reaches the label. The counts become reliable at about n_c m^L examples, and that is where deep networks start to generalise.

Assumptions

• Grammar. n_c classes, L levels, vocabulary v at every level, branching s, multiplicity m; constant across levels “for ease of exposition”. Each class and each level-ℓ symbol rewrites to m distinct s-tuples of level-(ℓ − 1) symbols, chosen uniformly at random; no s-tuple has two parents, so m v_{ℓ+1} ≤ v_ℓ^s. Production rules are equiprobable: every datum of a class is equally likely, and the training set is P data drawn without replacement, uniformly.
• Input. One-hot over v symbols at each of d = s^L positions, whitened over channels.
• Networks. Over-parametrised (width (4–8)·v^s, increased until test accuracy stops changing), maximal-update parametrisation so that features are learned as width grows. CNNs have depth L + 1 and non-overlapping filters of size s, i.e. matched to the tree; fully connected networks of depth L and 6 are also run. SGD on cross-entropy, batch 128, learning rate 0.1 annealed to 0.01, stopped at training loss 10⁻³; results averaged over 10 draws of grammar and initialisation.
• The theory’s regime. The signal estimate is for v ≫ 1 with m = q v^(s−1), and large n_c and P (Appendix C); the main text’s version assumes the m^L choices along a path are independent. The one-step model is a two-layer network on the first patch only, with the tuple one-hot over v^s values (orthogonalised inputs), first-layer weights all set to 1, fixed Gaussian readout, mean-field width limit, one full-batch gradient step.

Key results

• Eq. 3, 6. Data per class m^((d−1)/(s−1)); P_max = n_c m^((d−1)/(s−1)), v^(s^L) in the maximal case n_c = v, m = v
• Fig. 2. Two-layer fully connected networks: the P needed for test error 0.7 ε_rand grows linearly with P_max. Holds in: L = s = 2, n_c = v = m, v from 4 to 32.
• Eq. 7, Figs. 3, 4, 12. Depth-(L + 1) CNNs: P* (test error below ε_rand/10) ≈ n_c m^L, i.e. P*/n_c ≈ d^(ln m/ln s), independent of v. Holds in: s = 2, L = 2–4, m from 3 to 32 with m ≤ v, n_c from 8 to 64 (Fig. 12 at v = 256, m = 23, L = 2). An empirical law.
• Fig. 13. Deep fully connected networks of depth L or 6: the same law with an extra factor of about 2^L (s^L in the caption), independent of depth.
• Fig. 14. Depth-(L + 1) CNNs in the lazy limit (analytic NTK, kernel logistic regression): error stays finite up to P_max. They follow the feature-learning curves for P ≪ P*, using local correlations, but do not converge to zero.
• Eq. 8, Figs. 5, 6. S_{k,l} = ⟨‖f_k(x) − f_k(P_l x)‖²⟩/⟨‖f_k(x) − f_k(y)‖²⟩ falls from 1 to 0 around P*; S_{2,1} curves collapse on P/(n_c m^L). Invariance to level-l swaps is reached from layer k = l + 1, and all levels together. Holds in: L = 3, s = 2, n_c = m = v = 8 for Fig. 6.
• Eq. 10, C55. Relative signal σ_f² = v/m^L (Eq. C49, for v, n_c ≫ 1); relative sampling noise v n_c/P (Eq. C54); equal at P_c = n_c m
• Eq. 13, Fig. 8. After one gradient step, unit h’s response to tuple µ is Σ_α a_{hα}(N̂(µ; α)/P − N̂(µ)/(n_c P)); since the true N(µ; α) depends on µ only through its parent (Eq. C7), it becomes synonym-invariant as P grows, with S_{1,1} collapsing on P/(n_c m^L). The hidden weight matrix then has rank tending to v.
• Weight sharing over all s^(L−1) patches scales signal and noise by the same factor, so does not change P_c in the one-step setting.
• Appendix D, Fig. 10. Clustering the n_c-dimensional one-step representations separates synonyms at P ≈ √n_c m^L, a factor √n_c below P_c; a layer-wise GD-plus-k-means procedure collapses on v^(L+1/2), not v^(L+1), at n_c = m = v, L = 3.
• Fig. 9. The uncorrelated RHM (every tuple equally likely in every class at every level; parity at m = v = n_c = 2): depth-(L + 1) CNNs stay near chance for P/P_max up to 0.9 when v > 2.
• Fig. 15. A ResNet18 on subsets of CIFAR-10, set beside the estimate P* ∈ [10³, 3 × 10⁴] for n_c = 10, L = 3, m ∈ [5, 15]. An illustration of magnitudes; m and L for CIFAR-10 are guesses.

Claims

id	claim	strength	support
C1	On the RHM, two-layer networks and lazy deep CNNs need a number of examples proportional to P_max, exponential in d	moderate	Figs. 2, 14; small v and L only
C2	Deep CNNs matched to the tree, in a feature-learning regime, learn the RHM from P* ≈ n_c m^L examples, polynomial in d	moderate	Figs. 3, 4, 12; empirical, s = 2, L ≤ 4
C3	The P at which hidden representations become invariant to synonym swaps coincides with P*	moderate	Figs. 5, 6; curve collapse
C4	The class-conditional frequencies of input tuples rise above sampling noise at P_c = n_c m^L	moderate	Appendix C; large-v, large-n_c asymptotics, not a bound
C5	In a two-layer, one-step model, the onset of synonymic invariance is the onset of detectable correlations	strong	Eq. 13 (exact for that model) and Fig. 8
C6	Without patch–label correlations, deep CNNs do not escape the curse, though the hierarchy remains	moderate	Fig. 9; L = 2, 3, small v
C7	Clustering can beat end-to-end training by √n_c in sample size	weak	Appendix D, scaling argument, one setting of Fig. 10

Concepts

• Synonyms — the m s-tuples a single higher-level symbol rewrites to; interchangeable for the label. Not linguistic synonymy.
• Synonymic sensitivity S_{k,l} — Eq. 8, layer k’s response to swapping every level-l tuple for a random synonym, relative to swapping the whole datum.
• Signal — the deviation of the class probability given a tuple in a given patch, f_j(α|µ), from 1/n_c, over random draws of the rules.
• Sample complexity P* — the smallest P with test error below ε_rand/10, ε_rand = 1 − 1/n_c.
• Maximal case — n_c = v, m = v^(s−1): every string occurs.

Connections

It descends from Mossel’s hierarchical generative models (input–label correlations needed for learnability) and Malach and Shalev-Shwartz’s layer-wise clustering algorithm, and positions itself against the classical routes past the curse of dimensionality: low-dimensional manifolds, smoothness, and dependence on a few linear projections. The maximal RHM has none of the three. It cites Saxe, McClelland and Ganguli’s semantic development model (LIT-862) and DeGiuli’s random language model as earlier physics models of structured data. The lazy-regime contrast is the kernel picture of THEORY-086 seen from the failure side: a fixed kernel can use local correlations but cannot compose them.

Bearing on the record

• QUESTION-025. Named as the next step by LIT-863, but it does not answer the question. The RHM’s hierarchy is of constituency: an s-tuple in a position implies its parent symbol, and so on up to the class. It has no words with attributes, no co-occurrence of words with contexts, no PMI and no linear directions; the paper’s embedding-like object, the vector of class frequencies of a tuple, is shown only to be equal for synonyms. Two things carry over. First, the mechanism by which the latent structure is read off is the one THEORY-185 relies on, latent structure showing in first-order co-occurrence statistics, here between a tuple and a class; second, the RHM’s statistics are not independent across levels, so a derivation for QUESTION-025 built on it would need attributes defined as ancestors, which the paper does not attempt. An answer is more likely to come from a tree of attributes over items such as LIT-862’s.
• THEORY-186. Both are models of learning hierarchically generated data with a sharp, sigmoidal onset. In THEORY-186 the stages come from the singular-value spectrum of a tree of attributes and are learned coarse to fine; here every level is learned at the same P, and the onset is set by sampling noise against a random-rule signal. The two are not in conflict, being about different quantities (time against sample size) and different data, but they should not be cited as one account of “learning hierarchies”.
• CLAIM-119 and LIT-267. No bearing beyond QUESTION-025’s.
• New account. THEORY-195, Proposed: the sample-size law and its tie to detectable correlations.
• Practice. The paper gives no instruction. Its CIFAR-10 estimate is a magnitude check, and the layer-wise clustering result is an existence claim about an algorithm, not a recommendation. Its subject, what structure of data makes learning possible, is what the anthology’s signal-structure topic holds, hence the flag on the LIT.

Limitations

• P ≈ n_c m^L is fitted, not derived for the trained networks.* The derivation is of P_c, a statistical threshold, and the link to trained deep networks is the agreement of collapses plus a one-step model of one patch in a two-layer network. The authors say whether end-to-end training can reach the clustering rate “remains open”.
• Narrow ranges. s = 2 throughout the experiments; L ≤ 4; P_max is small enough to enumerate. The threshold for P* (ε_rand/10) is a choice.
• The CNNs are told the tree. Filter size s, non-overlapping patches and depth L + 1 match the generative process; the fully connected runs remove the matching and show an extra factor of about 2
• Uniform rules. Every production is equally likely and every symbol appears equally often, unlike language; the authors name non-uniform frequencies and noisy rules as extensions.
• Synonymy here is exact interchangeability under a known grammar. The paper’s suggestion to test invariance to synonym swaps in language models is not carried out.

Open questions

• A proof that gradient descent on a deep network reaches P* ≈ n_c m^L, or a counter-example in which correlations are detectable earlier than the network learns.
• What sets P* when production probabilities are non-uniform (Zipfian), so that different tuples become detectable at different P.
• Whether a co-occurrence embedding of the RHM’s tuples, or of symbols with their ancestors as attributes, has linear directions for those ancestors, which is the form in which it would bear on QUESTION-025.