# On the interplay between data structure and loss function in classification problems

arXiv: https://arxiv.org/abs/2103.05524 · HTML: https://mlsanity.com/paper/2103.05524/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 59 references that are in the map.
- First posted on arXiv 9 Mar 2021.

## Builds on (most cited first, 30 of 39)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Intrinsic dimension of data representations in deep neural networks](https://mlsanity.com/paper/1905.12784/) (2019)
- [High-dimensional dynamics of generalization error in neural networks](https://mlsanity.com/paper/1710.03667/) (2017)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks](https://mlsanity.com/paper/1805.12076/) (2018)
- [Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Tasks](https://mlsanity.com/paper/2006.07322/) (2020)
- [Generalisation error in learning with random features and the hidden manifold model](https://mlsanity.com/paper/2002.09339/) (2020)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [Optimal Regularization Can Mitigate Double Descent](https://mlsanity.com/paper/2003.01897/) (2020)
- [On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regression](https://mlsanity.com/paper/2006.05800/) (2020)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks](https://mlsanity.com/paper/1910.01663/) (2019)
- [Scaling description of generalization with number of parameters in deep learning](https://mlsanity.com/paper/1901.01608/) (2019)
- [A Model of Double Descent for High-dimensional Binary Linear Classification](https://mlsanity.com/paper/1911.05822/) (2019)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent](https://mlsanity.com/paper/2006.05013/) (2020)
- [A jamming transition from under- to over-parametrization affects loss landscape and generalization](https://mlsanity.com/paper/1810.09665/) (2018)
- [Triple descent and the two kinds of overfitting: Where & why do they appear?](https://mlsanity.com/paper/2006.03509/) (2020)
- [The role of regularization in classification of high-dimensional noisy Gaussian mixture](https://mlsanity.com/paper/2002.11544/) (2020)
- [The jamming transition as a paradigm to understand the loss landscape of deep neural networks](https://mlsanity.com/paper/1809.09349/) (2018)
- [Asymptotics of Ridge (less) Regression under General Source Condition](https://mlsanity.com/paper/2006.06386/) (2020)
- [The committee machine: Computational to statistical gaps in learning a two-layers neural network](https://mlsanity.com/paper/1806.05451/) (2018)

## Built on by (most cited first, 13 of 13)

- [A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networks](https://mlsanity.com/paper/2310.07891/) (2023)
- [Bayes-optimal Learning of Deep Random Networks of Extensive-width](https://mlsanity.com/paper/2302.00375/) (2023)
- [Deterministic equivalent and error universality of deep random features learning](https://mlsanity.com/paper/2302.00401/) (2023)
- [Multi-scale Feature Learning Dynamics: Insights for Double Descent](https://mlsanity.com/paper/2112.03215/) (2021)
- [The Training Process of Many Deep Networks Explores the Same Low-Dimensional Manifold](https://mlsanity.com/paper/2305.01604/) (2023)
- [Demystifying Disagreement-on-the-Line in High Dimensions](https://mlsanity.com/paper/2301.13371/) (2023)
- [High-dimensional learning of narrow neural networks](https://mlsanity.com/paper/2409.13904/) (2024)
- [Estimation under Model Misspecification with Fake Features](https://mlsanity.com/paper/2203.03398/) (2022)
- [MIME: Minority Inclusion for Majority Group Enhancement of AI Performance](https://mlsanity.com/paper/2209.00746/) (2022)
- [Modeling Structured Data Learning with Restricted Boltzmann Machines in the Teacher-Student Setting](https://mlsanity.com/paper/2410.16150/) (2024)
- [The impact of memory on learning sequence-to-sequence tasks](https://mlsanity.com/paper/2205.14683/) (2022)
- [Exploring Disparity-Accuracy Trade-offs in Face Recognition Systems: The Role of Datasets, Architectures, and Loss Functions](https://mlsanity.com/paper/2503.14138/) (2025)
- [Explaining Machine Learning and Memorization with Statistical Mechanics](https://mlsanity.com/paper/2606.31110/) (2026)

## Abstract (arXiv)

One of the central puzzles in modern machine learning is the ability of heavily overparametrized models to generalize well. Although the low-dimensional structure of typical datasets is key to this behavior, most theoretical studies of overparametrization focus on isotropic inputs. In this work, we instead consider an analytically tractable model of structured data, where the input covariance is built from independent blocks allowing us to tune the saliency of low-dimensional structures and their alignment with respect to the target function. Using methods from statistical physics, we derive a precise asymptotic expression for the train and test error achieved by random feature models trained to classify such data, which is valid for any convex loss function. We study in detail how the data structure affects the double descent curve, and show that in the over-parametrized regime, its impact is greater for logistic loss than for mean-squared loss: the easier the task, the wider the gap in performance at the advantage of the logistic loss. Our insights are confirmed by numerical experiments on MNIST and CIFAR10.