Source
Cagnetta, Petrini, Tomasini, Favero and Wyart (2023; Phys. Rev. X 2024), LIT-877, read in NOTE-677. The paper’s title, “How deep neural networks learn compositional data”, and its argument present correlation detection as the mechanism: synonymous tuples share class statistics, and a network groups them once those statistics rise above sampling noise.
What is asserted
That the number of examples a deep feature-learning network needs to learn data from a random hierarchical grammar is set by when the input-patch class correlations become detectable, and that detecting them is how the network comes to represent the grammar’s hidden symbols.
What the record holds toward it
THEORY-195, Active, is the measured part: on the Random Hierarchy Model with s = 2, L ≤ 4 and small v, deep CNNs matched to the tree reach a tenth of chance error from about n_c m^L examples, where their hidden layers become synonym-invariant, while shallow and lazy learners need an exponential number and deep ones fail when the correlations are removed. In that model the correlation threshold and the grammar’s size are the same expression, so the data cannot say which sets the number; QUESTION-165 asks for the separating test. THEORY-201 proposes the corresponding mechanism for next-token prediction, and THEORY-778 holds its derived correlation statistics.
What this does not say
- Not that end-to-end training reaches the better rate a clustering algorithm attains; the authors leave it open.
- Not that depth alone escapes the curse of dimensionality.
What would confirm or reject it
Confirmed by the promote_when: moving the correlations with n_c, m and L fixed and finding that sample complexity tracks the detection threshold, or a proof for gradient descent. Rejected if, with the correlations moved and the grammar fixed, sample complexity stays at n_c m