Abstract
Statistical learning in high-dimensional spaces is challenging without a strong underlying data structure. Recent advances with foundational models suggest that text and image data contain such hidden structures, which help mitigate the curse of dimensionality. Inspired by results from nonparametric statistics, we hypothesize that this phenomenon can be partially explained in terms of decomposition of complex tasks into simpler subtasks. In this paper, we present a controlled experimental framework to test whether neural networks can indeed exploit such "hidden factorial structures". We find that they do leverage these latent patterns to learn discrete distributions more efficiently. We also study the interplay between our structural assumptions and the models' capacity for generalization.
Introduction: Breaking the Curse of Dimensionality
In machine learning, the "curse of dimensionality" poses a fundamental challenge: as the number of input features grows, the data required to learn a distribution typically increases exponentially. For Large Language Models (LLMs), the combinatorial space of token sequences is astronomical. Yet, these models succeed, suggesting that real-world data possesses an underlying structure that makes learning tractable.
We propose the Factorization Hypothesis (FH): complex tasks are often decompositions of simpler, independent subtasks. By formalizing this as a "hidden factorial structure," we investigate whether neural networks (NNs) naturally exploit these latent patterns to achieve sample efficiency and generalization.
The Factorization Hypothesis and Framework
We model the input space $\mathcal{X}$ and output space $\mathcal{Y}$ as products of smaller, hidden factors. A task $p(y|x)$ is considered factorizable if each component of the output $y_j$ depends only on a small subset of input factors, its "parents."
To quantify this, we define two complexity measures:
- Approximation Complexity ($\bar{\chi}$): The minimum embedding dimension required for a network to perfectly represent the target distribution.
- Statistical Complexity ($\chi$): The number of samples needed to learn the distribution effectively.
Our experimental setup uses synthetically generated discrete datasets where we can precisely control the sparsity and connectivity of these hidden factors. This allows us to observe how Multilayer Perceptrons (MLPs) discover and leverage these structures.
Key Results and Insights
Efficiency and Threshold Effects
Our experiments reveal that NNs learn significantly faster when the statistical complexity $\chi$ is low, even if the total input space is massive. A critical finding is the existence of sharp performance thresholds related to model capacity.
As shown in the figure above, the population loss drops precipitously once the model's embedding dimension $d$ exceeds the theoretical approximation complexity $\bar{\chi}$. This provides a mathematical justification for architectural choices in model scaling.
Generalization and Embeddings
For a model to generalize to unseen input combinations, it must effectively "invert" its embeddings to recover underlying factors. We find that "factorization-compatible" embeddings—where the total embedding is a sum of factor embeddings—are crucial for this capability. This allows models to "fill in the blanks" of the factorial grid, predicting correct outputs for combinations never encountered during training.
Compute Efficiency
In an "isoflop" analysis, we observed that for highly structured data, it is often more compute-efficient to train on the same data for multiple epochs rather than seeking new, unique data points. This challenges the common "one-pass" training paradigm used in many LLM scaling laws, suggesting that data repetition can be beneficial when latent structures are present.
Conclusion and Future Work
This work demonstrates that neural networks can naturally exploit hidden factorial structures to overcome the curse of dimensionality. While our study focuses on MLPs, future research should investigate the role of the Attention mechanism in discovering these structures. Additionally, mapping these theoretical "hidden factors" to specific linguistic or visual features in real-world foundational models remains a vital next step. Understanding these structures could also provide a formal basis for explaining the success of transfer learning across tasks sharing similar latent factorizations.
Summary updated