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 μ_hatθ and covariance C_hatθ of the ERM estimator hatθ. 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θ^top x approximately follows the convolution of the generally non-Gaussian distribution of μ_hatθ^top x with an independent centered Gaussian variable of variance tr(C_hatθ mathbbE[xx^top]). This result clarifies the scope and limits of Gaussian universality for ERMs. Numerical simulations across diverse losses and models are provided to validate our theoretical predictions and qualitative insights.