Characterization of Gaussian Universality Breakdown in High-Dimensional Empirical Risk Minimization

We study high-dimensional convex empirical risk minimization (ERM) under general non-Gaussian data designs. By heuristically extending the Convex Gaussian Min–Max Theorem (CGMT) to non-Gaussian settings, we derive an asymptotic min–max characterization of key statistics, enabling approximation of the mean $\mu_{\hat{\theta}}$ and covariance $C_{\hat{\theta}}$ of the ERM estimator $\hat{\theta}$. Specifically, under a concentration assumption on the data matrix and standard regularity conditions on the loss and regularizer, we show that for a test covariate $x$ independent of the training data, the projection $\hat{\theta}^\top x$ approximately follows the convolution of the (generally non-Gaussian) distribution of $\mu_{\hat{\theta}}^\top x$ with an independent centered Gaussian variable of variance $\mathrm{tr}\!\big(C_{\hat{\theta}}\,\mathbb{E}[xx^\top]\big)$. This result clarifies the scope and limits of Gaussian universality for ERMs. Additionally, we prove that any $\mathcal{C}^2$ regularizer is asymptotically equivalent to a quadratic form determined solely by its Hessian at zero and gradient at $\mu_{\hat{\theta}}$. Numerical simulations across diverse losses and models are provided to validate our theoretical predictions and qualitative insights.

Modern machine learning models often make predictions from data with many features, sometimes as many features as training examples. In this high-dimensional setting, it is important to understand how well a learning method will perform on new data. Much of the existing theory relies on the simplifying assumption that the data are Gaussian, meaning that they behave like a bell-shaped random distribution. This assumption is mathematically convenient, but real data can be skewed, correlated, heavy-tailed, or composed of several groups. This paper studies when Gaussian-based predictions remain reliable, and when they break down, for a broad class of convex learning methods. We develop a framework that predicts the distribution of the model’s score on a new test point. Our result shows that this score can be viewed as the sum of two parts: a structured component that reflects the true data distribution, and an independent Gaussian noise component. Therefore, the score is Gaussian only when the structured component is itself Gaussian. This distinction explains why some performance predictions based on Gaussian approximations are accurate, while others can fail. The theory also simplifies the role of smooth regularization and is supported by numerical experiments across several losses and data models.