Gaussian Universality of Perceptrons with Random Labels
arXiv:2205.13303 · doi:10.1103/PhysRevE.109.034305
Abstract
While classical in many theoretical settings - and in particular in statistical physics-inspired works - the assumption of Gaussian i.i.d. input data is often perceived as a strong limitation in the context of statistics and machine learning. In this study, we redeem this line of work in the case of generalized linear classification, a.k.a. the perceptron model, with random labels. We argue that there is a large universality class of high-dimensional input data for which we obtain the same minimum training loss as for Gaussian data with corresponding data covariance. In the limit of vanishing regularization, we further demonstrate that the training loss is independent of the data covariance. On the theoretical side, we prove this universality for an arbitrary mixture of homogeneous Gaussian clouds. Empirically, we show that the universality holds also for a broad range of real datasets.
References in corpus (38)
- Scikit-learn: Machine Learning in Python
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labels
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- The dynamics of message passing on dense graphs, with applications to compressed sensing
- Benign Overfitting in Linear Regression
- Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
- Prevalence of Neural Collapse during the terminal phase of deep learning training
- Exploring Generalization in Deep Learning
- The generalization error of random features regression: Precise asymptotics and double descent curve
- Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems
- Modelling the influence of data structure on learning in neural networks: the hidden manifold model
- The spectrum of kernel random matrices
- The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
- Generalisation error in learning with random features and the hidden manifold model
- Surprises in High-Dimensional Ridgeless Least Squares Interpolation
- Learning curves of generic features maps for realistic datasets with a teacher-student model
- Statistical Mechanics of Deep Linear Neural Networks: The Back-Propagating Kernel Renormalization
- The Gaussian equivalence of generative models for learning with shallow neural networks
- Storage capacity in symmetric binary perceptrons
- Linear Readout of Object Manifolds
- The Lasso with general Gaussian designs with applications to hypothesis testing
- Data-driven emergence of convolutional structure in neural networks
- Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization
- What Do Neural Networks Learn When Trained With Random Labels?
- Kernel Alignment Risk Estimator: Risk Prediction from Training Data
- Universality of empirical risk minimization
- Probing transfer learning with a model of synthetic correlated datasets
- Counting the learnable functions of structured data
- Phase Transitions in Transfer Learning for High-Dimensional Perceptrons
- Storage of correlated patterns in a perceptron
- High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation
- Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
- Universality in Learning from Linear Measurements
- Provable tradeoffs in adversarially robust classification
- Algorithmic pure states for the negative spherical perceptron
- Rademacher complexity and spin glasses: A link between the replica and statistical theories of learning
- Failure and success of the spectral bias prediction for Kernel Ridge Regression: the case of low-dimensional data