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

arXiv:2604.03146v1 Announce Type: new
Abstract: 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 $text{Tr}(C_{hat{theta}}mathbb{E}[xx^top])$. 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.