On the interplay between data structure and loss function in classification problems
Authors: Stéphane d'Ascoli
Marylou Gabrié
Levent Sagun
Giulio Biroli
Venue: NeurIPS 2021 Poster (2021)
Keywords: loss function
generalization
overparametrization
double descent
random features

Abstract: One of the central features of modern machine learning models, including deep neural networks, is their generalization ability on structured data in the over-parametrized regime. 
In this work, we consider an analytically solvable setup to investigate how properties of data impact learning in classification problems, and compare the results obtained for quadratic loss and logistic loss. 
Using methods from statistical physics, we obtain a precise asymptotic expression for the train and test errors of random feature models trained on a simple model of structured data. 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.
Our results show in particular that in the over-parametrized regime, the impact of data structure on both train and test error curves is greater for logistic loss than for mean-squared loss: the easier the task, the wider the gap in performance between the two losses at the advantage of the logistic. 
Numerical experiments on MNIST and CIFAR10 confirm our insights.

On the interplay between data structure and loss function in classification problems
Stéphane d'Ascoli
Facebook AI Research, Paris
Department of Physics, Ecole Normale Supérieure, Paris stephane dascoli@ens.s.....
Marylou Gabrié
New York University, New York
Flatiron Institute, New York
mgabrie@nyu.edi
Levent Sagun Facebook AI Research, Paris
Giulio Biroli
Department of Physics, École Normale Supérieure, Paris
Abstract
One of the central puzzles in modern machine learning is the ability of heav- ily overparametrized models to generalize well. Although the low-dimensional structure of typical datasets is key to this behavior, most theoretical studies of overparametrization focus isotropic inputs. In this work, 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 ciw-diieniional 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 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.
Introduction
Classical wisdom teaches us that learning model should have just the right number of parameters to learn from dataset without overfitting it. However, recent years have seen the emergence of massively over- over-parametrized models which manage to generalize well on high-dimensional tasks [1, 21, somehow avoiding both the curse of dimensionality and the pitfall of overfitting, This generalization capacity in the wwrrperrmetriieed regime continues to puzzle rigorous understanding, particular for deep neural networks [3, 5], despite their remarkable achievements over the past decade [6. 7, 8, 9]. Various works have given evidence of a double descent curve [5, 10, 11, 12, 13]. whereby the test error first decreases as the number of parameters increases. then peaks, then decreases again monotonically. The overfitting peak occurs at the interpolation threshold where training error vanishes, well-studied phenomenon the statistical physics literature [14, 15, 16, 17, 18].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

vD
weak subepace
sigaltre) E)
0,2
B
misaligned
aligned
0,1
salient
isotropic setup
On
0x11
subspacc
it R
F R
w R
(a) Random features model
(b) Strong and weak features model of data
Figure I: Left: Random feature model considered here, which can be viewed two-layer networks where only the second layer is trained. Middle and Right: Strong and weak features model considered here. Input space is decomposed into two subspaces with different variance in the anisotropic setting: a salient one with strong variance xz.1 and weak one with smaller variance Zz,2- The labels are given by linear teacher y (g x DD) and flipped with certain probability A. We can adjust the alignment of data subspaces with the teacher. The task is easy when Ø, > 0,2,, and hard in the opposite case.
Although the underlying structure of data plays major role in the generalization ability of over- parametrized models [19]. it has been little studied from a theoretical point of view. The first aspect of data structure is the distribution of the inputs: MNIST and CIFARIO have the same number of classes and images, yet generalization is harder for CIFAR10 10 because the images are more complex than handwritten numbers. The second aspect is the rule between inputs and outputs: random labelling of CIFAR10 can be learned by neural network but offers no possibility of generalization [3]. Characterizing the structure of real-world data involves studying the interplay between these two aspects. In this direction, simple and interpretable models of structured data can prove useful to understand what underlies the behavior of generalization.
In this work, we present a simple model of learning and its analytical solution which simultaneously enables to:
(i) study the effect of overparametrization for a given task;
(ii) analyze both regression and classification tasks;
(iii) control the structure of the inputs and their relationship with the labels.
To satisfy (i), we need disentangle the input dimension from the number of parameters in the learning model, which is impossible for the linear models often studied in litterature. We instead consider random feature model [20], which
shown to exhibit double descent by [21]. To satisfy (ūi), we follow the lines of [22] and use an approach from statistical physics, enabling to generalize the result of [21] to any convex loss function. Finally, satisfy (iii) we introduce block model in which the input space is subdivided into various subspaces with different variances (saliencies) and different correlation (alignments) with the labels (see Fig. 1). This model was recently studied for linear regression under the name of strong and weak features model [23].
Our analytical solution uses the replica method from statistical physics [24]. Albeit non-rigorous in a strict mathematical sense, this method is considered exact in theoretical physics and has been influential statistical learning theory since the 80s, [25] and [26] for recent reviews. Several of their conjectures have been proven exact in the last decade [27, 28, 29, 90], including in settings very close to the considered model as discussed further at the end of Section [31, 32].
Contributions Our main analytical contribution, presented in Section 3, is the expression of the train and test errors of random feature model trained on data generated by the strong and weak features model. Our analysis is valid in the high- sic-dimennional limit both for regression and classification tasks, although we focus here on the latter. We confirm that the asymptotic prediction matches simulations finite size (see Fig. 2 and 4).
We leverage this result to present a thorough analytical study of how the data structure and the loss function interplay shape the generalization error, and in particular how they affect the double

---

descent curve (Section 4). We highlight behavioral differences between square loss and logistic loss, in particular the fact that logistic loss generalizes better for easy tasks (see Fig. 3). We validate our insights via controlled experiments on the MNIST and CIFARIO datasets described in the Section 5.
Reproducibility The code to reproduce our experiments is available at (lascoli/Gata-strucuu
com/
2
Related Work
Although most theoretical studies of generalization focus on structureless data, a few exceptions exist. The strong and weak features model has recently been studied in the context of least-squares regression, both empirically [33] and theoretically [34, 35, 23]. Several intriguing observations emerge in strongly anisotropic setup: (i) several overfitting peaks can be seen [33, 36]; (ii) the optimal ridge regularization parameter can become negative [35, 37], as it becomes helpful to encourage the weights to have very different magnitudes; (iii) extra features acting as pure noise can play a beneficial role by inducing some implicit reguilaaeegaannn regularization [23].
The strong and weak features model also includes the setup studied in [38], called the spiked covariates model. The latter involves a small block of size D (1) < 1) and a large "junk" block with no correlation with the labels. The question is then: can kernel methods learn to discard the junk features, hence "beat the curse of dimensionality" in the way neural networks do? The answer was shown to depend on the strength of the junk features: when the variance of these features is small, they are not problematic, and the kernel method ignores them, effectively learning a task of effective dimensionality D << D.
More general models for the structure of data were considered in other works. In the special case of random Fourier Feature regression, [39] derived the train and test eтror for a general input distribution. [40] achieved similar result in the non- non-parametric setting of kernel regression, which can be viewed as the limiting case of random feature regression when the number of random features P goes to infinity.
The few works studying classification analytically have mostly focused on linear models, trained on linearly separable data [41, 42, 43, 44] or gaussian mixtures [45, 46]. One of the challenges in classification (in comparison to regression) is the large set of available loss functions [47, 48]. In the context of random feature models, [22] uses tools from statistical mechanies to derive the generalization loss of random features model for any loss function with i.i.d. Gaussian input. More recently, [32] shows that this framework could extend to more complex data distributions and learned feature maps provided that key population covariances are estimated by Monte Carlo methods. Our paper crucially builds on these contributions, by deriving a fully analytical analysis for a simple interpretable model of data structure, while also analyzing the effect of label flipping.
We also note that few recent works investigate the roles of the loss and the structure in data in more realistic setups where theoretically robust results are harder to obtain. Several works have studied the low intrinsic dimensionality of real-world data distributions and how impacts sample complexity for supervised tasks [49, 50, 19, 51]. The impact of the loss function is also an active research area: [52, 53] show that square loss can perform equally or better than the ubiquitous cross-entropy loss in realistic emphasize its importance.
classification problems, if one rescales the weight of the correct class to
3 A solvable model of data structure
In this work, we focus on the random features model introduced in [20]. Using tools from statistical physics, we derive the generalization error of a teacher-student task on the strong and weak features model of structured data.
Note that this model is akin to the so-called lazy learning regime of neural networks where the weights stay
close to their initial value [54]: assuming fap = 0. we have fx(x ~ Vafe(x)]ee, (0 - 0o) [55]. In other words, lazy learning amounts to linear fitting problem with a random feature vector Vo (xxx a
3

---

Random feature model The random features model can be viewed as two-layer neural network (see Fig. 1) whose first layer fixed random matrix containing random feature vectors {Fi PRD) J=l.... acting inputs By DR
P wi
F; 2 VD
0p Σ
(I)
where (.) is a pointwise activation function and w; E R are the second layer weights. Elements of F are drawn i.i.d from AO0, 1).
The second layer weights, i.e. the elements of w RR, are trained by minimizing an fg-regularized loss on N training examples {ar E RP) [RP]p==...'' J==1...N
N ((w) = Σ
i = argmin (((w)= + ? |
(Up. 0p))
(2)
2
where denotes the logistic loss Evy 9) = log(1+e -w)) teacher Pe(yl x) corresponding the sign of a linear function possibly corrupted by label flipping:
v9). The target labels are given by probabilistic
B Fp
with probabiiiy 1 A
y/ Ti sign
M/ 1-1
(3)
vD
with probability A.
The generalization error is computed as the 0-1 loss,
Eg Enr,y 1 [sign(
(4)
Strong and weak features model To impose structure on the input space, we introduce a block- structured covariance matrix from which the elements of the inputs a E R.D and the teacher f e R are sampled as:
x ((,,E)),
B ~ N(0, Eg).
12.1
TR
0
JR D
Σg
Σg =
Our result presented in the rest Section 3 valid for an arbitrary number of blocks. In Section we will focus for interpretability and d2 D, with Φ1 Φ2 = We will typically be interested in the strongly anisotropic setup where the first subspace is much smaller (Ø) < 1), but potentially has higher saliency oz.1/On.2 > 1 (see Fig. 1).
the special case where we only have two blocks of sizes ái D
0n.
Main analytical result Using the replica method from statistical physics [24] and the Gaussian Equivalence Theeorem (GET) [56, 21, 30, 31], we derive the generalization and training errors the high-dimensional limit where D, N and P P oc with fixed ratios. The asymptotic generalization and training errors are given by
M
lim Eg = cos-1 N
(5)
VpQ
lim E, = Egg [ dy 10 Cy. SA.M//Q.P-R M2/)) fly nly, v VQ,, v)]
(6)
N
with the proximal operator ny,, a. b) = argmin(x - -2)3/(2b) + ((x, v), the random variable x
É ~ N(0, 1), the functional 20 (y,a,b) = =s de ()PP((())))) and the scalars
p= Σ d:0g = m1 Σ Mz Q = N² Σ Oz.idssi 12 V = Σ Dz, + 12-

---

The parameters K1, are related to the activation function: denoting r = E, 2102,1 and (),, one has
1
K1 r R (Ea((E))
Ri V (o(5)) -
rng.
Besides these constants and the ones defining the data structure (di, T3.s on,i), the key ingredients to obtain asymptotic errors the so-called order parameters may qs tws and tw- They correspond to the high-dimensional limit of the following expectations and variances (denoted by V):
1
q lim - Ep (st sil, qu lim 1 Ep [úo w p-00
1
ma lim Ep [st B.],
D-vxx D
D D
1
1 p V i 10)
Us lim
Vp 84 8i], Uw lim
D-+0c D
where 1 Fr R and s,, Br R denote the orthogonal projections of and [ onto vT subspace (1, and P denotes the joint distribution of all random quantities in the problem (the teacher weights, the random features and the training data).
Intuitively, p the variance of the outputs of the teacher, Q is the variance of the outputs of the student, and M is their covariance. The generalization error is given by the "angle" between the teacher and the student, as expressed by Eq. 5. The order parameters allowing to obtaín Q and M are one of the outputs of the replica computation deferred to SM B. They are obtained by solving set of non-linear saddle-point equations (see Section B.5 of the SM). Our framework is valid for any convex loss function, although the replica equations need to be evaluated numerically in the general case. In the case of the square loss however, some simplifications arise, e.g. an explicit expression for the training error can be obtained from the order parameters (see Section B.6 of the SM).
Steps and validity of the replica analysis The necessary steps of the derivation are detailed in SM B. In particular, (i) obtain an anistropic extension of the GET, (ii) conduct random matrix analysis for block matrices and finally (iii) derive the analytical saddle-point equations which yield the values of the order parameters. Our result generalizes the strategy of [22] from isotropic to anisotropic data and additionally covers the effect of label flipping. Our result is also related to [32] which establishes rigorously the replica prediction in related learning problems. rigorous proof of our replica results is within reach: it requires a small extension of [31] (to prove the anisotropic GET derived in Section B.2 of the SM) combined with the recent results of [32]. Moreover, results in the following section show perfect agreement with numerical experiments.
4 Effect of data structure and loss function on double descent
In this section, we investigate how the interplay between the data structure and the loss function shapes the train and test error curves. In the main text, we only examine parameter- we increase the number of parameters P at fixed number of data N. In SM. A, we also examine the sample-wise dependency by plotting the train and test error in the entire (N, P) phase space.
curves, where
Modulating the teacher-date alignment We compare three cases illustrated on Fig. 1. The first is the isotropic setup where r. (blue curves Fig. 2). the two next setups, the data anisotropic with small subspace (#) 0.1) of large variance and large subspace (#2 0.9) of small variance. The ratio the variances r2 = 12,1//0p, is set to 10, and their values are chosen to keep the total variance of the inputs unchanged: + ||||=||] = 010.,1 + 020,.22 =
We study two cases for the outputs: (i) the aligned scenario where the strong features are highly correlated with the labels (r33 0 100, green curves in Fig. 2); (ii) the misaligned scenario, where the strong features have low correlation with the labels (r = 0.01, orange curves in Fig. 2). In both cases, we choose the σB, such that the total variance of the teacher scores is unchanged: 1 E ) 01 10 + 2 1.
Validity at finite size We begin by comparing our analytical predictions with the outcomes of numerical experiments, both for test loss (Fig. 2) and train loss (Fig. 4). The agreement is excellent even for moderately large dimensions D 100. Note that the replica method, which relies on solving
5

---

0.5
lsotropic
0.5
1sotropic
Misalaguad
Masalggeed
Aligmed
Aligned
Tost orror
0.3
0.3
Test
0.2
0.2
0.1
0.1
0.0
10
10
10
10"
10:
16a
107
10
10"
10
10"
10
10a
102
P/D
P/D
(a) Square loss true labels
(b) Logistic loss, true labels
0.4
0.4
Test error
0.3
0.3
Test
0.2
Iaatropic Misaligned
laotropic
Misaligned
Aligned
Aligned
0.0
10
10-a
10 0.0
10-2
10"
10'
10a
P/D
P/D
(c) Square loss, label flip probability A = 0.3
(d) Logistic loss, label flip probability = 0.3
Figure 2: Anisotropic data strongly affects the double descent curves. Theoretical results (solid curves) and numerical results (dots with vertical bars denoting standard deviation over 10 runs) agree even at moderate size 100. We set a Tanh, À 10- and N/D= 1
a set of scalar fixed point equations, is also computationally efficient. It allows here to probe ratios of P/D and N/D far beyond what is tractable by the numerics (P, D and N only appear in the replica equations through the values of the ratios N/P and P/D).
Effeet of data structure on generalization Looking at Fig. 2, a first immediate observation is that strong teacher-data alignment makes the task easier: as number parameters P increases the test loss drops earlier and eventually reaches a lower asymptotic value, both for square loss and logistic loss. SM. A, we show that the same phenomenon occurs when varying the number of samples N instead of the number of parameters P. These observations are in line with the results of [38] and show that relevant salient features make the problem low-dimensional with an effective dimension close to Φ1 D. This setup is the most akin to real-world tasks in which the most salient features of an image are often the most relevant to its recognition. In this sense, the impressive performance of kernel methods such the Convolutional NTK real-world datasets [57] can be associated with the anisotropy of the data: feature learning is not indispensable to beat the curse of dimensionality the irrelevant features are weakly salient to begin with [51].
Conversely, misalignment generally makes the task harder and increases the value of the test loss. Note however that for square loss, an interesting crossover occurs in presence of noise (panel c): the irrelevant features are detrimental from small P, but become helpful at large P, as can be seen from the orange curve reaching lower asymptotic value than the blue curve. We associate this to the phenomenon discovered for linear regression in [23], whereby adding noisy features acts as a form of implicit regularization.
Logistic is better than square loss effects of using logistic loss rather than square loss.
Comparing the two loss functions, observe two beneficial
First, we observe that the overfitting peak characteristic of the double descent curve which appears at
P = D for square loss absent for logistic loss in the noiseless setting (Fig. 2), and vastly reduced
in presence of noise (we use in both cases the same small amount of regularization for square and

---

Tsotropie
0.50
MNIST logistic
0.45
MNIST square
brror
CIPARIO logistic
0.40
CIFARIO square
Notseless logistic
Test
0.35
Noiselass square
Noiey logistic
0.30
Noisy square
0.25
Isotropic
10
10
10:1
10"
10a
0.25
0.50
1.00
2.00
4.00
Teacher-daaa alignment rp
1/c
(a) Strong and weak features model
(b) Real data
Figure 3: The easier the task, the wider the gap between logistic and square loss. (a) Strong and
weak feature model in the noiseless (A 0) and noisy (A 0.3) setups, where we make the task easier from left to right by increasing the alignment between the data and the teacher. (b) Real data (MNIST parity and CIFARIO airplanes vs cars), where we make the task easier by decreasing the exponent controlling the saliency of the top PCA components (see Sec. 5). In both cases, we considered an over-vvrrette parrmarrmttriieed RF model (P/D 100) learning from a moderate amount of data (N/D = 1), with = Tanh and À = 10
0.7
Isotropoc
0.7
Isotropic
0.6
Misaligned
0.6
Misaligned
0.5
Aligned
0.5
Allined
Troin loss
Train loss
0.4
0.3
0.2
0.1
0.1
0.0
0.0
10ah
10-1
10a
10
10a
10-2
10-1
10a
10
10a
P/D
(a) Square loss
(b) Logistic loss
Figure 4: Structure of data affects the position of the interpolation threshold for logistic loss. We depicted the train loss curves in the noiseless setup of Fig. where Tanh, À 10-3 N/D 1.
logistic loss). This suggests that the logistic loss exerts some form of implicit regularization, reducing the amount of overfitting.
Second, in the aligned and isotropic setups, the asymptotic test loss reached in the "kernel" regime P/D - xc is lower with logistic loss, especially in the aligned setup. To better highlight this phenomenon, we continuously vary the teacher-date alignment Fig. 3(a) for an overparametrized model. Logistic loss performs similarly outperforms square loss as soon as the alignment sufficient. The gap between the two then grows as we increase alignment. In other words, logistic loss is particularly powerful on tasks made easy by the structure the data.
worse than square loss at very small alignment, but
The better ability of logistic loss to detect structure in the data is also reflected in the train loss curves of Fig. 4. For square loss, the interpolation threshold, i.c. the point when the the train loss vanishes, occurs at P = N. For logistic loss, there is no interpolation threshold strictly speaking since the train loss cannot be zero. However, one can define an effective threshold as the point where the training loss reaches the near-zero plateau. Notably, this effective threshold depends on the data structure: is lower for the aligned setup, where the data easier to fit, and higher for the misaligned setup, where the data is harder to fit.
Behavioral differences between losses Further understanding of the differences between logistic and square loss can be gained thanks to the replica approach which gives access to the order parameter
7

---

3,0
Isotropic
10
Misalaguadd
Aligned
300
10-4
10
10
102
200
10
10a
Jsotropic
0.5
Misabagaed
Aligned
0.0
10
10
10
10"
10.
16a
107
10
10
10
10F
101
10"
107
P/D
P/D
0.7
17.5
10
12.5
10-2
0.4
102
10.0
7.5
0.2
leotropic
Isotropic
0.1
Misaligned
2.5
Misaligned
Aligned
Aligned
10"3
10"2
10
10"
10
10a
10a
10"3
10"2
10
107
10'
10a
P/D
P/D
(a) Square loss
(b) Logistic loss
Figure 5: Overparametrization causes the weights to diverge for logistic loss. We depicted the order parameters Q and M, quantifying the variance of the outputs the student and their covariance with the outputs of the teacher, in the noiseless setup of Fig. Insets: log-log plot, showing the power-law asymptotic behaviors.
Q and M defined in Eq. 7, see Fig. 5. For recall, Q corresponds to the variance of the outputs of the student and M to their covariance with the linear scores of the teacher.
For square loss, Q and M increase and reach a finite value (with peak in Q at the interpolation threshold), reflecting the fact that the lincarized estimator Fw converges towards fixed norm vector more or less correlated with the teacher vector B3 depending on the depending on the data structure. For logistic loss, M increases linearly with overparametrization and Q increases logarithmic insets), reflecting the fact the the estimator endlessly grows the direction the teacher vector [41] the number of parameters increases. This growth appears shield the peak observed in Q for the squared loss explaining the very mild double descent observed in Fig. 2. Interestingly, these quantities grow much faster in the aligned setup, where the estimator predictions, which also hints at the better performance of the logistic loss when the structure of data favorable.
power law (see
"confident" in its
Numerical results
To examine the applicability of our results, we consider two realistic binary classification tasks: parity of digits in the MNIST dataset and airplanes cars in the CIFAR10 10 dataset. In both cases, we learn with an RF model in the same setup as described above. To control the alignment, we apply PCA transformation to the inputs (keeping the D 100 components and discarding the rest), then apply following component-wiss rescaling: æ; + x std(æ;) where std(æ;, denotes standard deviation of feature æ; the whole training dataset, and the exponent allows to tune the saliency of the features:
Q yields aligned scenario, since the top PCA features are naturally the most relevant;
Q yields the isotropic scenario, where all features have same variance;
α yields misaligned scenario, since the strong features will become weak and the weak features become strong.

---

0.5
0.5
Lootropic Misaligned
Lactropic Misaligned
Aligued
Aligued
Test error
Test error
0.3
0.3
0.2
Train loss
0.5
0.2
Train
0.1
0.1
0.0
10a
10a
10
10"
10
10"1
10a
10'
P/D
P/D
(a) Square loss, MNIST
(b) Logistic loss, MNIST
0.5
Isotropic Misalianed Allgned
Isctropic
0.4
Misalianed
Aligned
Test orror
Test error
0.3
0.3
Train loss
0:5
0.2
Trai loss
0.5
0.1
0.0
0.0
0.0
10-1
10
10a 0.0
10-1
10
P/D
P/D
(c) Square loss, CIFARIO
(d) Logistic loss, CIFARIO
Figure Test error and train loss (inset) on realistic tasks. Top: MNIST dataset with labels given by the digit parity. Bottom: CIFARIO dataset with airplanes and cars. We synthetically reproduce the isotropic, aligned and misaligned scenarios by applying PCA transformation to the inputs and tuning how salient the largest PCA features are compared to the smallest PCA features (see Sec. 5). We set Tanh, x 10-3 and N/D
The corresponding train and test error curves shown in Fig. (we a 0 for the aligned scenario and a = 1.5 for the misaligned scenario). Remarkably, we recover many of the phenomenological features described previously. The test error drops earlier and reaches a lower asymptotic value in the aligned setup, and conversely reaches a higher value in the misaligned setup. We observe double descent curve for square loss, but the peak is suppressed for logistic loss. The location of the interpolation threshold depends on the teacher-data alignment for logistic loss, whereas it does for square loss. Finally, logistic loss has a lower asymptotic error than square loss in the aligned setup, signalling that it is favorable for "easy" data distributions.
To strengthen the latter observation, we vary continuously the difficulty of the task by adjusting the exponent a and show the results in Fig. 3(b) (increasing a makes the task harder). As observed analytically in Fig. 3(a), the gap between square loss and logistic loss increases decrease
Conclusion
In this work, we studied how the loss function interplays with the data structure to shape the generalization curve of random feature models. Our results show strong behavioral differences between quadratic and logistic loss, the latter performing particularly well for easy datasets where most of the information comes from low-dimension projections of the inputs.
As possible direction of future work, we conclude with the observation that our results, which apply random feature (or lazy learning) tasks, appear in contrast with those of [52], which suggest that cross-entropy losses can be traded at no cost for quadratic losses in modern deep learning tasks, which are known to have low intrinsic dimensionality [19]. This opens up an interesting direction for future work: does feature learning help quadratic losses by better capturing the low-dimensional structure of the inputs, as suggested by [51]? Or does the key difference reside in the multi-class nature of practical classification problems [53]?

---

Acknowledgements We thank Berfin Simsek, Armand Joulin, Bruno Loureiro and Federica Gerace for helpful discussions. SD and GB acknowledge funding from the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' l'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). MG acknowledges funding from the Flatiron Institute. We also thank Lenka Zdeborova and Florent Krzakala, and Les Houches Summer School for organizing a workshop on Statistical Physics and Machine Learning where this work was partially done.
References
[1] Sergey Zagoruyko and Nikos Komodakis. arXiv:1605.07144 2016.
Wide residual networks.
arXiv preprint
[2] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 14166, 2020.
[3] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint S.Xi:1661..35300 2016.
[4] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of peeepaaraetiinnioonn in generalization of neural networks. arXiv preprint arXiv: 1805. 1805 2018
[5] Madhu Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensional dynamics of generalization error in neural networks. Neural Networks, (32:428-446 2020.
[6] Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097-1105, 2012.
[7] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436 2015.
[8] Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups.
IEEE Signal processing magazine, 29(6):82-97, 2012.
[9] Uya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104-3112, 2014.
[10] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the bias-variance trade-off. arXiv preprint arXiv:1812.11111. 2018.
[11] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv: 1903308500000 2019.
[12] S Spigler, M Geiger, S d' Ascoli, L Sagun, G Biroli, and M Wyart. A jamming transition from under-to over-parametrizzaion affects generalization in deep learning. Journal of Physics A: Mathematical and Theoretical, 52(47):47400, 2019.
[13] Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description generalization with number of parameters in deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2020(2):023401, 2020.
[14] Manfred Opper and Wolfgang Kinzel. Statistical mechanics of generalization. In Models of neural networks III, pages 151-209. Springer, 1996.
[15] Andreas Engel and Christian Van den Broeck. Statistical mechanics of learning. Cambridge University Press. 2001.
[16] Florent Krzakala and Jorge Kurchan. Landscape analysis of constraint satisfaction problems. Physical Review E, 76(2):02112) 2007.
[17] Silvio Franz and Giorgio Parisi. The simplest model of jamming. Journal of Physics A: Mathematical and Theoretical, (9(14,
10

---

[18] Mario Geiger. Stefano Spigler, Stéphane d' d'Ascoli, Levent Sagun, Marco Baity-Jesi, Giulio Biroli, and Matthieu Wyart. Jamming transition as a paradigm understand the loss landscape of deep neural networks. Physical Review E, (00(1):012115) 15, 2019.
[19] Phillip Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact on learning. arXiv preprint arXiv:2104.0884. 2021.
[20] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pages 1177-1184, 2008.
[21] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv: 05355, 2019.
[22] Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Generalisation error in learning with random features and the hidden manifold model. arXiv preprins arXiv:2002.09333, 2020.
[23] Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regression under general source condition. arXiv preprint arXiv:2006. 06386, 2020.
[24] Marc Mézard, Giorgio Parisi, and Miguel Virasoro. Spin glass theory and beyond: An Intro- duction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987.
[25] Marylou Gabrié. Mean-field field inference methods for neural networks. Journal of Physics A: Mathematical and Theoretical, 53(22), 2020.
[26] Yasaman Bahri, Jonathan Kadmon, Jeffrey Pennington, Sam Schoenholz, Jascha Sohl-Dickstein, and Surya Ganguli. Statistical Mechanics of Deep Learning. Annual Review of Condensed Matter Physics, 11(1):501-523 2020.
[27] Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová. Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences of the United States of America, 116(12):451-5466 2019.
[28] Benjamin Aubin, Antoine Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris, and Lenka Zdeborová. The committee machine: Computational to statistical gaps in learning a two-layers neural network. In Neural Information Processing Systems 2018, pages 1-44, 2018
[29] Marylou Gabrié. Andre Manoel, Clément Luneau, Jean Barbier, Nicolas Macris, Florent Krzakala, and Lenka Zdeborová. Entropy and mutual information in models of deep neural networks. pages 1821-1831. Curran Associates, Inc., 2018.
[30] Sebastian Goldt, Galen Reeves, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. The gaussian equivalence of generative models for learning with two-layer neural networks. arXiv preprint arXiv:2006. 14709, 2020.
[31] Hong Hu and Yue M Lu. Universality laws for high nigh-diimnsional learning with random features. arXiv preprint arXiv:2009.0766 2020.
[32] Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mézard, Lenka Zdeborová, École Fédérale, and Polytechnique De Lausanne. Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model. 2102.08127, 2021.
[33] Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. arXiv preprint w:Xiv:2003.0189) 2020.
[34] Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regres- sion and classification. arXiv preprint arXiv: 507.000030000... 2015.
[35] Denny Wu and Ji Xu. On the optimal weighted 12 regularization in overparameterrized linear regression. arXiv preprint arXiv:2006.05880 2020.
[36] Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi. Multiple descent: Design your own generalization curve. arXiv preprint arXiv:2008.00 20t.:22000000336,, 2020.
[37] Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization. liver, 1:1-2, 2019.
11

---

[38] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz. and Andrea Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33, 2020.
[39] Zhenyu Liao, Romain Couillet, and Michael W Mahoney. A random matrix analysis of random fourier features: beyond the gaussian kernel, precise phase transition, and the corresponding double descent. arXiv preprint arXiv:2006.05013 2020.
[40]
Abdulkadir Canatar, Blake Bordelon, and Cengiz. Pehlevan. Statistical mechanics of generaliza- tion in kernel regression. arXiv preprint arXiv:2006. 13198, 2020.
[41] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research (JMLR), 19:1-57, 2018.
[42] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime. arXiv preprint arXiv: 1911.0154, 2019.
[43] Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. arXiv preprint arXiv:2004. /2019, 2020.
[44] Tengyuan Liang and Pragya Sur. precise high-dimensional asymptotic theory for boosting and min-l1-norm interpolated classifiers. arXiv preprint arXiv:2002.01188 2020.
[45] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high-dimensional binary linear classification. arXiv preprint arXiv: 1.05822, 2019.
[46] Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborova. The role of regularization in classification of high-dimensional noisy gaussian mixture. In International Conference Machine Learning, pages
PMLR, 2020.
[47] Ganesh Ramachandra Kini and Christos Thrampoulidis. Analytic study of double descent in binary classification: The impact of loss. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2527-2532. IEEE, jun 2020.
[48] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification regression in overparameterizee regimes: Does the loss function matter? arXiv preprint arXiv:2005.08003 2020.
[49] Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data vs teacher-student paradigm. arXiv preprint 1905. 2019.
[50] Alessio Ansuini, Alessandro Laio, Jakob H Macke, and Davide Zoccolan. Intrinsic dimension of data representations in deep neural networks. arXiv preprint arXiv: 2019.
[51] Aristide Baratin. Thomas George, César Laurent, R Devon Hjelm, Guillaume Lajoie, Pascal Vincent, and Simon Lacoste-Julics Implicit regularization in deep learning: view from function space. arXiv preprint arXiv:2008. 00938, 2020.
[52] Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross-entropy in classification tasks. arXiv preprint arXiv:2006.077 2020.
[53] Ahmet Demirkaya, Jiasi Chen, and Samet Oymak. Exploring the role of loss functions in multiclass classification. In 2020 54th Annual Conference on Information Sciences and Systems (CISS), pages 1-5. IEEE, 2020.
[54] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
[55] Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 2933-2943. Curran Associates, Inc., 2019.
[56] Noureddine El Karoui et al. The spectrum of kernel random matrices. Annals of statistics, 38(1):1-50, 2010.
[57] Sanjeev Arora, Simon S Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. arXiv preprint 1711v:1910.01663, 2019.
12


Reviews:
[{"review_id": "QIQ8AYonnGp", "reviewer": "Reviewer_WQoW", "summary": "This paper studies the generalization in an analytically solvable setup: a two-layer network with random features on the first layer and learnable features on the second layer, under squared loss and logistic loss. The authors derive asymptotic expressions for the train and test errors of the above model trained on a dataset with block covariance matrix with tunable saliency (for input) and noise (for mapping). In experiments, the authors studied and compared how the data structure and loss function affect the double descent, generalization, and also test it in the case of MNIST and CIFAR10 datasets.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On the theoretical side, I did not check the proof of the theorems, but I believe that the derivation is correct and reasonable. I think the theoretical contribution is novel. For clarity, it would make the paper much more insightful if the authors can provide clear intuition about the cause of the double descent using the main analytical result, and why in noiseless scenario with logistic loss this phenomenon disappear.\n\nOn the experiment side, I think the experiment is well-conducted. \n\nThe authors note that their results appear to be in stark conflict with those of (Hui and Belkin, 2020), which train on large-scale models. Could the authors address the following question: to which extend can the results in this two-layer network generalize to larger models and more complex datasets?\n\nOverall, I think the paper is well-written, novel, and makes a step that offers interesting technique to address the generalization of NNs on structured datasets.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address the limitation that their analytical results are based on non-rigorous tools from statistical physics. It would be better if the authors can also discuss how their results and insights can generalize over more complex models and datasets.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "NLCM5LdFKy", "reviewer": "Reviewer_Xc21", "summary": "The authors study the loss achieved by random feature models that learns from simple (but structured) data.\nThe main result consists in the comparison of two losses (square and logistic) under three settings in the data structure (misaligned, isotropic and aligned that roughly represent the difficulty of the task).\nThe paper is well written and presents a thorough analysis of the related works. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper uses standard and new tools of statistical physics to address the problem summarized above.\n\nThe comparison between the two losses is very interesting. A direct comparison between the results would be unfair and the authors make nice considerations to convince of the benefits of logistic loss. Considerations that are confirmed in the experimental setup on real data.\n\nIn the end, the authors conclude that their results may be limited to the random feature models as there is a contrast with the results of ref.[51] about DNNs. I do not understand why the authors did not include this analysis in their paper using the framework of ref.[32]. I strongly believe that it would be more natural to answer these questions in this paper instead of waiting for future works. \nadd \nIn the end, the role of the data structure seems to play a minor role in the paper (and in the results). Apart from a shift of the curves and a counter-intuitive result on the regularization effect of misalignment in the square loss, I do not see many considerations on this aspect.\nIs it because the model is still too simple? The author should extend their discussion and maybe analysis to highlight the importance of data structure. \n\nMy impression is that, although it is pointing in the right direction, the paper needs more results to meet the acceptance bar.\n\n################# after rebuttal #################\n\nThanks to the authors for the clarification and the promised changes.\n\nThe authors are indeed right about ref.32, the analysis I suggest is more complex than what appeared in the first place. Nevertheless, it may be worth integrating their analytical result with some empirical ones and give a partial answer to the questions they asked. I still believe it is more natural to provide an answer (although partial) in this paper, instead of waiting for future works. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is a simple yet instructive model.\nNo societal impact is foreseen. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Lq6ZcwxMZif", "reviewer": "Reviewer_LCY7", "summary": "This paper used the replica method to derive the high dimensional asymptotics of the test error of random features model in the strong and weak features model with square loss and logistic loss. The observations drawn from plotting the analytical prediction are the following: 1. When the parameters vector of the target function is aligned with the covariance structure of the covariates, the generalization error is smaller (given fixed N/D, P/D, lambda, loss function). 2. In the aligned settings, the test error of using the logistic loss is smaller than that of using the square loss (in a specific setting). This paper also performed experiments on parity MNIST and CIFAR10(2), and the experimental result coincides with the results with idealized assumptions. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this is a decent result. The theoretical part which is the replica calculation seems like a straightforward generalization of previous results (it didn’t appear in the literature though). The strong and weak features model setup in the proportional limit has not been fully investigated before, so drawing some useful conclusions from the analytical prediction would be very interesting. \n\nAn issue with this paper is that it drew conclusions based on a very specific choice of parameters and specific settings. It is not clear whether this is representative enough to lead to the conclusions. \n1) In the figures, this paper just chooses N = D. It is not clear whether the conclusion still holds for some larger N/D (in practice, the sample size is several times larger than the dimension). In the appendix, there seem to be more experiments for other N/D, but the author didn’t use these experimental results to support the conclusions drawn in this paper. The reviewer suggests the author draw necessary figures for other N/D to demonstrate that the conclusions consistently hold. \n2) This paper just fixes lambda to be a small parameter like 10^{-3} or 10^{-4}. However, it is not clear whether one should compare logistic/square loss by choosing a vanishing regularization. Another scenario would be to choose the optimal lambda that minimizes the test error and then compare the logistic/square loss. \n\nOther issues: \n1. In Eq (8), please explain what is x_i. Is it the eigenvectors of top PCs, or the coordinates of the covariates? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In general, the reviewer suggests the authors consider more scenarios and perform a more thorough investigation to support their conclusions. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an interesting analytical result on generalization which all three reviewers considered worthwhile.
Based on the given scores (5,6,7) and the fact that the machine learning field would likely benefit from some more theoretical contributions I recommend acceptance as a poster presentation. 
Decision: Accept (Poster)