On the interplay between data structure and loss function in classification problems
Year: 2022

Abstract:
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 overparametrized 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.

heading: 1 Introduction
text: Classical wisdom teaches us that a learning model should have just the right number of parameters to learn from a dataset without overfitting it. However, recent years have seen the emergence of massively over-parametrized models which manage to generalize well on high-dimensional tasks [1, 2], somehow avoiding both the curse of dimensionality and the pitfall of overfitting. This generalization capacity in the over-parametrized regime continues to puzzle rigorous understanding, in particular for deep neural networks [3, 4, 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, a well-studied phenomenon in the statistical physics literature [14, 15, 16, 17, 18].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Although the underlying structure of data plays a major role in the generalization ability of overparametrized 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 CIFAR10 have the same number of classes and images, yet generalization is harder for CIFAR10 because the images are more complex than handwritten numbers. The second aspect is the rule between inputs and outputs: a random labelling of CIFAR10 can be learned by a 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 us 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 to 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 a random feature model [20], which was shown to exhibit double descent by [21]. To satisfy (ii), 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, to satisfy (iii), we introduce a 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 to statistical learning theory since the 80s, see [25] and [26] for recent reviews. Several of their conjectures have been proven exact in the last decade [27, 28, 29, 30], including in settings very close to the considered model as discussed further at the end of Section 3 [31, 32].
Contributions Our main analytical contribution, presented in Section 3, is the expression of the train and test errors of a random feature model trained on data generated by the strong and weak features model. Our analysis is valid in the high-dimensional limit both for regression and classification tasks, although we focus here on the latter. We confirm that the asymptotic prediction matches simulations at 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 to 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 CIFAR10 datasets described in the Section 5.
Reproducibility The code to reproduce our experiments is available at https://github.com/ sdascoli/data-structure.

heading: 2 Related Work
text: 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 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) 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 error for a general input distribution. [40] achieved a similar result in the 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 mechanics 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 a 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 it 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 multi-class classification problems, if one rescales the weight of the correct class to emphasize its importance.

heading: 3 A solvable model of data structure
text: In this work, we focus on the random features model1 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.
1Note 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 f✓0 =0, we have f✓(x) ⇡ r✓f✓(x)|✓=✓0 · (✓ ✓0) [55]. In other words, lazy learning amounts to a linear fitting problem with a random feature vector r✓f✓(x)|✓=✓0 .
Random feature model The random features model can be viewed as a two-layer neural network (see Fig. 1) whose first layer is a fixed random matrix containing P random feature vectors {Fi 2 RD}i=1...P acting on inputs xµ 2 RD:
ŷµ = PX
i=1
wi
✓ Fi · xµp
D
◆ , (1)
where (·) is a pointwise activation function and wi 2 R are the second layer weights. Elements of F are drawn i.i.d from N (0, 1). The second layer weights, i.e. the elements of w 2 RP , are trained by minimizing an `2-regularized loss on N training examples {xµ 2 RD}µ=1...N :
ŵ = argmin w
 ✏t(w) +
2 kwk22 , ✏t(w) =
NX
µ=1
` (yµ, ŷµ) , (2)
where ` denotes the logistic loss `(y, ŷ) = log(1+e yŷ). The target labels are given by a probabilistic teacher y ⇠ Pt(y| · x) corresponding to the sign of a linear function possibly corrupted by label flipping:
yµ = ⌘µ sign ✓
· xµp D
◆ , ⌘µ = ⇢ 1 with probability 1 1 with probability . (3)
The generalization error is computed as the 0-1 loss,
✏g = Ex,y ⇥ sign(ŷ(x)),y(x) ⇤ . (4)
Strong and weak features model To impose structure on the input space, we introduce a blockstructured covariance matrix from which the elements of the inputs x 2 RD and the teacher 2 RD are sampled as:
x ⇠ N (0, ⌃x), ⇠ N (0, ⌃ ),
⌃x =
2 64 x,1I 1D 0 0 0 x,2I 2D 0
0 0 . . .
3
75 , ⌃ =
2 64 ,1I 1D 0 0 0 ,2I 2D 0
0 0 . . .
3
75 .
Our result presented in the rest of Section 3 is valid for an arbitrary number of blocks. In Section 4 we will focus for interpretability on the special case where we only have two blocks of sizes 1D and 2D, with 1 + 2 = 1. We will typically be interested in the strongly anisotropic setup where the first subspace is much smaller ( 1 ⌧ 1), but potentially has higher saliency rx = x,1/ x,2 1 (see Fig. 1).
Main analytical result Using the replica method from statistical physics [24] and the Gaussian Equivalence Theorem (GET) [56, 21, 30, 31], we derive the generalization and training errors in the high-dimensional limit where D, N and P ! 1 with fixed ratios. The asymptotic generalization and training errors are given by
lim N!1
✏g = 1
⇡ cos 1 ✓ Mp ⇢Q ◆ , (5)
lim N!1
✏t = E⇠ Z
R dy
h Z0 ⇣ y, ⇠M/ p Q, ⇢ M2/Q ⌘ `(y, ⌘(y, p Q⇠, V ) i (6)
with the proximal operator ⌘(y, a, b) = arg min x (x a)2/(2b) + `(x, y), the random variable
⇠ ⇠ N (0, 1), the functional Z0 (y, a, b) = R R dx N (x; a, b)Pt(y|x) and the scalars ⇢ = X
i
i ,i x,i, M = 1 X
i
x,ims,i, Q =  2 1
X
i
x,iqs,i +  2 ?qw, V =  2 1
X
i
x,ivs,i +  2 ?vw.
The parameters 1, ? are related to the activation function: denoting r = P
i i x,i and ⇠ ⇠ N (0, r), one has
1 = 1
r E⇠[⇠ (⇠)]], ? =
q E⇠ [ (⇠)2] r21. (7)
Besides these constants and the ones defining the data structure ( i, ,i, x,i), the key ingredients to obtain asymptotic errors are the so-called order parameters ms, qs, qw, vs and vw. They correspond to the high-dimensional limit of the following expectations and variances (denoted by V):
ms,i = lim D!1
1 D EP [si · i] , qs,i = lim D!1 1 D EP [si · si] , qw = lim P!1 1 P EP [ŵ · ŵ] ,
vs,i = lim D!1
1 D VP [si · si] , vw = lim P!1 1 P VP [ŵ · ŵ] ,
where s = 1p P Fŵ 2 RD and si, i 2 R iD denote the orthogonal projections of s and onto subspace i 2 {1, 2} and P denotes the joint distribution of all random quantities in the problem (the teacher weights, the random features and the training data).
Intuitively, ⇢ is 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 obtain Q and M are one of the outputs of the replica computation deferred to SM B. They are obtained by solving a 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) we 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. A 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.

heading: 4 Effect of data structure and loss function on double descent
text: 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-wise curves, where 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.
Modulating the teacher-data alignment We compare three cases illustrated on Fig. 1. The first is the isotropic setup where rx = 1 (blue curves in Fig. 2). In the two next setups, the data is anisotropic with a small subspace ( 1 = 0.1) of large variance and a large subspace ( 2 = 0.9) of small variance. The ratio of the variances rx = x,1/ x,2 is set to 10, and their values are chosen to keep the total variance of the inputs unchanged: 1D E[kxk 2] = 1 x,1 + 2 x,2 = 1.
We study two cases for the outputs: (i) the aligned scenario where the strong features are highly correlated with the labels (r = ,1/ ,2 = 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 ,i such that the total variance of the teacher scores is unchanged: 1D E[( · x) 2] = 1 x,1 ,1 + 2 x,2 ,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
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).
Effect 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 of parameters P increases the test loss drops earlier and eventually reaches a lower asymptotic value, both for square loss and logistic loss. In 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 1D. 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 as the Convolutional NTK on real-world datasets [57] can be associated with the anisotropy of the data: feature learning is not indispensable to beat the curse of dimensionality if 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 a 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 Comparing the two loss functions, we observe two beneficial effects of using logistic loss rather than square loss.
First, we observe that the overfitting peak characteristic of the double descent curve which appears at P = D for square loss is 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
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 ! 1 is lower with logistic loss, especially in the aligned setup. To better highlight this phenomenon, we continuously vary the teacher-data alignment in Fig. 3(a) for an overparametrized model. Logistic loss performs similarly or worse than square loss at very small alignment, but outperforms square loss as soon as the alignment is 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 in the data.
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.e. 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: it is lower for the aligned setup, where the data is 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
Q and M defined in Eq. 7, see Fig. 5. For recall, Q corresponds to the variance of the outputs of the student ŷ 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 a peak in Q at the interpolation threshold), reflecting the fact that the linearized estimator Fw converges towards a fixed norm vector more or less correlated with the teacher vector depending on the depending on the data structure. For logistic loss, M increases linearly with overparametrization and Q increases as a power law (see logarithmic insets), reflecting the fact the the estimator endlessly grows in the direction of the teacher vector [41] as the number of parameters increases. This growth appears to 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 is more “confident” in its predictions, which also hints at the better performance of the logistic loss when the structure of data is favorable.

heading: 5 Numerical results
text: To examine the applicability of our results, we consider two realistic binary classification tasks: parity of digits in the MNIST dataset and airplanes vs cars in the CIFAR10 dataset. In both cases, we learn with an RF model in the same setup as described above. To control the alignment, we apply a PCA transformation to the inputs (keeping the top D = 100 components and discarding the rest), then apply the following component-wise rescaling: xi ! xi/ std(xi)↵, where std(xi) denotes the standard deviation of feature xi over the whole training dataset, and the exponent ↵ allows us to tune the saliency of the features:
• ↵ < 1 yields an aligned scenario, since the top PCA features are naturally the most relevant; • ↵ = 1 yields the isotropic scenario, where all features have same variance; • ↵ > 1 yields a misaligned scenario, since the strong features will become weak and the
weak features become strong.
The corresponding train and test error curves are shown in Fig. 6 (we set ↵ = 0 for the aligned scenario and ↵ = 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 a 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 not 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 ↵ and show the results in Fig. 3(b) (increasing ↵ makes the task harder). As observed analytically in Fig. 3(a), the gap between square loss and logistic loss increases as we decrease ↵.

heading: 6 Conclusion
text: 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 a possible direction of future work, we conclude with the observation that our results, which apply to 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’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.

Review summaries:
The authors study the loss achieved by random feature models that learns from simple (but structured) data. The 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). The paper is well written and presents a thorough analysis of the related works. 

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.

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.