Gaussian Universality of Linear Classifiers with Random Labels in High-Dimension
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.