Abstract
Traditional statistical learning theory (SLT) often fails to explain the success of deep learning because its generalization bounds are distribution-independent, assuming worst-case scenarios. This paper bridges the gap between SLT and statistical physics by investigating how inherent data structure affects model complexity. By modeling data as "multiplets" of points with shared labels, the authors demonstrate that the Vapnik-Chervonenkis (VC) entropy is non-monotonic and exhibits a new "data-driven" phase transition, $\alpha_*$, distinct from the classic storage capacity. This transition marks a point where the number of valid classifications for structured data begins to vanish, offering a path toward tighter, more realistic generalization bounds.
Introduction: The Theory-Practice Gap
A central mystery in modern AI is why models with massive capacity generalize well despite theoretical bounds suggesting they should overfit. Classic SLT provides upper bounds that are often too loose for practical use because they ignore the specific distribution of data. Conversely, statistical physics analyses of the "typical case" have historically assumed unstructured data, where inputs and labels are independent. This work addresses this by exploring how the specific geometry of a dataset—its structure—governs a model's expressive power through the lens of VC entropy.
Modeling Data Structure via Multiplets
To quantify "structure," the authors study kernel machines where data points are not independent but grouped into multiplets of $k$ points that must share the same label. This constraint restricts the set of "admissible" dichotomies (classifications) the model can perform.
As shown in Figure 1, for unstructured data, the number of possible dichotomies grows monotonically. However, for structured data, the number of admissible dichotomies ($C_{n,p}$) follows a non-monotonic curve: it initially increases, peaks, and then eventually drops to zero in the thermodynamic limit. This suggests that as more structured data is provided, the space of valid ways to label it actually shrinks.
The $\alpha_*$ Phase Transition
The authors identify a critical point, $\alpha_*$, where the VC entropy per dimension vanishes. This is distinct from the classic storage capacity $\alpha_c$ (the limit of what a model can learn). While $\alpha_c$ represents a hard limit on satisfiability, $\alpha_*$ represents a transition in the model's expressive power specifically tailored to the data's structure.
This transition is driven by a competition between an "entropic" term (the combinatorial growth of labels) and an "energetic" term (the constraints of the data geometry). Interestingly, the authors find that classifying unstructured data with a margin (treating points as small manifolds) is mathematically equivalent to classifying structured multiplets, leading to the same phase transition behavior.
Phase Diagrams and Analytical Bounds
For pairs of points ($k=2$) with a fixed overlap $\rho$, the authors derived a closed-form expression for the transition point: $$\alpha^{(2)}_*(\rho) = -\frac{\log(2\pi) + 1}{2 \log (1/2 + \pi^{-1} \arcsin \rho)}$$
Figure 2 illustrates the resulting phase diagram. The theoretical curves for $\alpha_*$ align closely with numerical sampling, defining the boundary between a phase where the model has high expressive power and a phase where the data structure effectively "quenches" the available dichotomies.
Conclusion
By incorporating data structure into the analysis of VC entropy, this work provides a more nuanced view of model complexity. The discovery of the $\alpha_*$ transition suggests that the "effective" complexity of a model is not a fixed property but is dynamically determined by the data it encounters. Future work aims to extend this framework to deep, multi-layer architectures to find data-dependent order parameters that can better predict generalization in real-world applications.
Summary updated