mlsanityData to 7 Oct 2026

Universality of empirical risk minimization

arXiv 2202.08832 ↗First posted 17 Feb 2022math.ST cs.LG stat.MLcited by 73

Not on the map. Why?

Abstract (arXiv)

We study a general class of optimization problems with decision variable boldsymbolTheta ∈ ℝp × k and cost function which is the sum of n terms, each dependent on boldsymbolTheta through the k-dimensional projection boldsymbolTheta^top boldsymbolxi, where boldsymbolxi, i ≤ n are i.i.d. random vectors. This setting is general enough to include examples of current interest in statistical physics, high-dimensional statistics, and statistical learning theory. We consider the proportional asymptotics n, p → ∞, with n/p = Theta(1), and prove that, whenever there exists a minimizer satisfying a suitable generalization of a "delocalization" condition, the minimum value is universal. Namely, (for subgaussian boldsymbolxi) it depends on the distribution of boldsymbolxi only through its asymptotic mean and covariance. This delocalization condition is essentially necessary. Earlier universality results for such problems were limited to strongly convex loss functions. We derive applications of our theory to statistical learning and prove general universality results both for train and (under additional conditions) test error. In particular, we establish universality for vectors boldsymbolxi generated by random 1-layer neural networks (random features models) and first-order Taylor approximations of 2-layer networks (neural tangent models). Finally, we establish that the delocalization property holds for a class of statistical learning problems under a condition that is easy to verify.

Key facts. Cited by 73 papers in the map (data through 7 Oct 2026). Builds on 11 of its 38 references that are in the map. First posted on arXiv 17 Feb 2022.

Builds on

11 of 38 references.

References · 11

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  3. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  4. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  5. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  6. 2020Generalisation error in learning with random features and the hidden manifold modelcited by 126
  7. 2020The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Trainingcited by 84
  8. 2019A Model of Double Descent for High-dimensional Binary Linear Classificationcited by 81
  9. 2020Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimizationcited by 51
  10. 2020The Lasso with general Gaussian designs with applications to hypothesis testingcited by 40
  11. 2015Universality laws for randomized dimension reduction, with applicationscited by 21

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 9; 2023: 19; 2024: 22; 2025: 16; 2026: 7.

73 papers.

Sort:

By area:

  1. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 146
  2. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 67
  3. 2024Asymptotic theory of in-context learning by linear attentioncited by 54
  4. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
  5. 2023A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networkscited by 46
  6. 2024Scaling and renormalization in high-dimensional regressioncited by 45
  7. 2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 42
  8. 2023Bayes-optimal Learning of Deep Random Networks of Extensive-widthcited by 41
  9. 2023Deterministic equivalent and error universality of deep random features learningcited by 35
  10. 2024Asymptotics of feature learning in two-layer networks after one gradient-stepcited by 35
  11. 2023Universality laws for Gaussian mixtures in generalized linear modelscited by 28
  12. 2022Gaussian Universality of Perceptrons with Random Labelscited by 26
38 more
  1. 2023Are Gaussian data all you need? Extents and limits of universality in high-dimensional generalized linear estimationcited by 25
  2. 2024Nonlinear spiked covariance matrices and signal propagation in deep neural networkscited by 25
  3. 2024Bayes-optimal learning of an extensive-width neural network from quadratically many samplescited by 23
  4. 2023Precise Asymptotic Analysis of Deep Random Feature Modelscited by 22
  5. 2024Asymptotics of Random Feature Regression Beyond the Linear Scaling Regimecited by 22
  6. 2023High-dimensional Asymptotics of Denoising Autoencoderscited by 19
  7. 2023Six Lectures on Linearized Neural Networkscited by 19
  8. 2022On double-descent in uncertainty quantification in overparametrized modelscited by 15
  9. 2024A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilitiescited by 14
  10. 2023Learning curves for deep structured Gaussian feature modelscited by 13
  11. 2023Demystifying Disagreement-on-the-Line in High Dimensionscited by 12
  12. 2023Fundamental limits of overparametrized shallow neural networks for supervised learningcited by 12
  13. 2024High-dimensional learning of narrow neural networkscited by 12
  14. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11
  15. 2023Classification of Heavy-tailed Features in High Dimensions: a Superstatistical Approachcited by 11
  16. 2025The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networkscited by 11
  17. 2023Injectivity of ReLU networks: perspectives from statistical physicscited by 10
  18. 2025Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterizationcited by 9
  19. 2024Risk and cross validation in ridge regression with correlated samplescited by 8
  20. 2025On the Mechanisms of Weak-to-Strong Generalization: A Theoretical Perspectivecited by 7
  21. 2024Random features and polynomial rulescited by 6
  22. 2024Theoretical Limitations of Ensembles in the Age of Overparameterizationcited by 6
  23. 2022A New Central Limit Theorem for the Augmented IPW Estimator: Variance Inflation, Cross-Fit Covariance and Beyondcited by 5
  24. 2023A High-dimensional Convergence Theorem for U-statistics with Applications to Kernel-based Testingcited by 5
  25. 2023High-dimensional Asymptotics of VAEs: Threshold of Posterior Collapse and Dataset-Size Dependence of Rate-Distortion Curvecited by 5
  26. 2024A High Dimensional Statistical Model for Adversarial Training: Geometry and Trade-Offscited by 5
  27. 2025Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Lawscited by 5
  28. 2022Optimal Activation Functions for the Random Features Regression Modelcited by 4
  29. 2023Universality of max-margin classifierscited by 4
  30. 2024A Novel Gaussian Min-Max Theorem and its Applicationscited by 4
  31. 2024High-dimensional logistic regression with missing data: Imputation, regularization, and universalitycited by 4
  32. 2024The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixturescited by 4
  33. 2025Asymptotic Analysis of Two-Layer Neural Networks after One Gradient Step under Gaussian Mixtures Data with Structurecited by 4
  34. 2025High-Dimensional Learning Dynamics of Quantized Models with Straight-Through Estimatorcited by 4
  35. 2022Random Features Model with General Convex Regularization: A Fine Grained Analysis with Precise Asymptotic Learning Curvescited by 3
  36. 2022Fundamental Limits of Two-layer Autoencoders, and Achieving Them with Gradient Methodscited by 3
  37. 2023Multinomial Logistic Regression: Asymptotic Normality on Null Covariates in High-Dimensionscited by 3
  38. 2024Effect of Weight Quantization on Learning Models by Typical Case Analysiscited by 3

50 most cited of 73 All 73 (JSON)