Classification of Superstatistical Features in High Dimensions

Urte Adomaityte, Gabriele Sicuro, Pierpaolo Vivo

In the realm of theoretical machine learning, the Gaussian design hypothesis has long served as a cornerstone for analytical tractability. This hypothesis assumes that data features follow a normal distribution, a simplification often justified by "universality" principles suggesting that in high dimensions, only the first two moments (mean and variance) dictate model performance. However, real-world data—ranging from financial time series to natural language—frequently exhibits "heavy tails," where extreme outliers occur far more often than a Gaussian model would predict.

In the paper "Classification of Heavy-tailed Features in High Dimensions: a Superstatistical Approach," researchers provide a theoretical breakthrough by deriving the first exact asymptotic formulas for binary classification of such non-Gaussian data. They demonstrate that the common assumption of Gaussian universality breaks down in the presence of fat tails, necessitating a new "superstatistical" framework to accurately predict how models behave.

Methodology: The Superstatistical Framework

To model heavy-tailed data without losing analytical rigor, the authors employ a superstatistical approach combined with the replica method from statistical physics.

In this framework, data clusters are modeled as double-stochastic processes. A data point is initially drawn from a Gaussian distribution, but its variance ($\Delta$) is treated as a random variable drawn from a separate distribution ($\rho$). By varying the shape of $\rho$—for instance, using an inverse-Gamma distribution—the authors can tune the "fatness" of the tails. This allows for the simulation of everything from perfectly Gaussian data (as the shape parameter $a \to \infty$) to Cauchy-like distributions with infinite variance ($a \le 1$).

The authors then use the replica method to derive "state evolution equations." These equations describe the system's behavior in the proportional limit, where the number of samples ($n$) and dimensions ($d$) both grow to infinity while their ratio ($\alpha = n/d$) remains fixed. This analysis covers Empirical Risk Minimization (ERM) using generic convex loss functions, such as square or logistic loss, and convex regularization like ridge regression.

The Breakdown of Universality and Double Descent

The most significant finding of this work is that Gaussian universality is not a universal law. For heavy-tailed data, model performance depends on higher-order moments of the distribution, not just the mean and variance. This breakdown is most visible in the "double descent" phenomenon—the characteristic spike in error that occurs when the number of samples roughly equals the number of features ($n \approx d$).

Figure 1: Generalization error ($\epsilon_g$), training error ($\epsilon_t$), and training loss ($\epsilon_\ell$) as a function of the sample-to-dimension ratio $\alpha$. The interpolation peak at $\alpha=1$ shifts and changes magnitude as the tail parameter $a$ varies, demonstrating the breakdown of Gaussian universality. Solid lines represent theoretical predictions, while markers show numerical simulations ($d=1000$).

Interestingly, the authors identify a "Closer to Mean" paradox: heavy-tailed data can sometimes result in lower test error than Gaussian data with equivalent variance. While fat tails produce extreme outliers, the "bulk" of the data points in these distributions are actually clustered closer to the mean than they would be in a normal distribution, potentially aiding classification in certain regimes.

The Separability Transition

Another key contribution is the derivation of a closed-form expression for the separability transition. This is the critical sample-to-dimension ratio ($\alpha^*$) where a dataset transitions from being linearly inseparable (where training error is zero) to separable.

Figure 2: Analysis of the separability threshold for heavy-tailed data. The training error ($\epsilon_t$) and training loss ($\epsilon_\ell$) remain at zero until the critical ratio $\alpha^*$ is reached. As the tails become heavier (smaller $a$), the point at which the data becomes linearly separable shifts significantly.

As shown in the figures, the theoretical "state evolution" curves show near-perfect agreement with numerical simulations, even for distributions with infinite variance. This validates the superstatistical approach as a robust tool for predicting the performance of high-dimensional classifiers on realistic, non-Gaussian datasets.

Conclusion and Future Work

While this framework provides a powerful new lens for understanding heavy-tailed data, challenges remain. Applying these results to real-world data requires accurately estimating the underlying distribution $\rho$ of the variance, perhaps through Bayesian techniques. Furthermore, while the current work focuses on binary classification, extending these exact asymptotics to multiclass problems and multi-layer neural networks represents the next frontier in high-dimensional learning theory.

Summary updated

BibTeX
@inproceedings{adomaityte2023classification,
  author = {Urte Adomaityte and Gabriele Sicuro and Pierpaolo Vivo},
  title = {{Classification of Superstatistical Features in High Dimensions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=eR7PrfJe9o},
}
Figure