Gaussian Universality of Linear Classifiers with Random Labels in High-Dimension

• URL: http://arxiv.org/abs/2205.13303v1
• Date: Thu, 26 May 2022 12:25:24 GMT
• Title: Gaussian Universality of Linear Classifiers with Random Labels in High-Dimension
• Authors: Federica Gerace, Florent Krzakala, Bruno Loureiro, Ludovic Stephan, Lenka Zdeborov\'a
• Abstract summary: We prove that data coming from a range of generative models in high-dimensions have the same minimum training loss as Gaussian data with corresponding data covariance. In particular, our theorem covers data created by an arbitrary mixture of homogeneous Gaussian clouds, as well as multi-modal generative neural networks.
• Score: 24.503842578208268
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While classical in many theoretical settings, the assumption of Gaussian i.i.d. inputs is often perceived as a strong limitation in the analysis of high-dimensional learning. In this study, we redeem this line of work in the case of generalized linear classification with random labels. Our main contribution is a rigorous proof that data coming from a range of generative models in high-dimensions have the same minimum training loss as Gaussian data with corresponding data covariance. In particular, our theorem covers data created by an arbitrary mixture of homogeneous Gaussian clouds, as well as multi-modal generative neural networks. In the limit of vanishing regularization, we further demonstrate that the training loss is independent of the data covariance. Finally, we show that this universality property is observed in practice with real datasets and random labels.

Related papers

• The Breakdown of Gaussian Universality in Classification of High-dimensional Mixtures [6.863637695977277]
  We provide a high-dimensional characterization of empirical risk minimization for classification under a general mixture data setting. We specify conditions for Gaussian universality and discuss their implications for the choice of loss function.
  arXiv  Detail & Related papers  (2024-10-08T01:45:37Z)
• Learning a Gaussian Mixture for Sparsity Regularization in Inverse Problems [2.375943263571389]
  In inverse problems, the incorporation of a sparsity prior yields a regularization effect on the solution. We propose a probabilistic sparsity prior formulated as a mixture of Gaussians, capable of modeling sparsity with respect to a generic basis. We put forth both a supervised and an unsupervised training strategy to estimate the parameters of this network.
  arXiv  Detail & Related papers  (2024-01-29T22:52:57Z)
• A theory of data variability in Neural Network Bayesian inference [0.70224924046445]
  We provide a field-theoretic formalism which covers the generalization properties of infinitely wide networks. We derive the generalization properties from the statistical properties of the input. We show that data variability leads to a non-Gaussian action reminiscent of a ($varphi3+varphi4$)-theory.
  arXiv  Detail & Related papers  (2023-07-31T14:11:32Z)
• The Implicit Bias of Batch Normalization in Linear Models and Two-layer Linear Convolutional Neural Networks [117.93273337740442]
  We show that gradient descent converges to a uniform margin classifier on the training data with an $exp(-Omega(log2 t))$ convergence rate. We also show that batch normalization has an implicit bias towards a patch-wise uniform margin.
  arXiv  Detail & Related papers  (2023-06-20T16:58:00Z)
• Are Gaussian data all you need? Extents and limits of universality in high-dimensional generalized linear estimation [24.933476324230377]
  We consider the problem of generalized linear estimation on Gaussian mixture data with labels given by a single-index model. Motivated by the recent stream of results on the universality of the test and training errors in generalized linear estimation, we ask ourselves the question: "when is a single Gaussian enough to characterize the error?"
  arXiv  Detail & Related papers  (2023-02-17T14:56:40Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks [51.1848572349154]
  neural network models that perfectly fit noisy data can generalize well to unseen test data. We consider interpolating two-layer linear neural networks trained with gradient flow on the squared loss and derive bounds on the excess risk.
  arXiv  Detail & Related papers  (2021-08-25T22:01:01Z)
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions [79.35722941720734]
  Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. We prove exacts characterising the estimator in high-dimensions via empirical risk minimisation. We discuss how our theory can be applied beyond the scope of synthetic data.
  arXiv  Detail & Related papers  (2021-06-07T16:53:56Z)
• RATT: Leveraging Unlabeled Data to Guarantee Generalization [96.08979093738024]
  We introduce a method that leverages unlabeled data to produce generalization bounds. We prove that our bound is valid for 0-1 empirical risk minimization. This work provides practitioners with an option for certifying the generalization of deep nets even when unseen labeled data is unavailable.
  arXiv  Detail & Related papers  (2021-05-01T17:05:29Z)
• Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularization [39.35822033674126]
  We study binary linear classification under a generative Gaussian mixture model. We derive novel non-asymptotic bounds on the classification error of the latter. Our results extend to a noisy model with constant probability noise flips.
  arXiv  Detail & Related papers  (2020-11-18T07:59:55Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.