Learning curves of generic features maps for realistic datasets with a teacher-student model

Abstract:
Teacher-student models provide a framework in which the typical-case performance of high-dimensional supervised learning can be described in closed form. The assumptions of Gaussian i.i.d. input data underlying the canonical teacher-student model may, however, be perceived as too restrictive to capture the behaviour of realistic data sets. In this paper, we introduce a Gaussian covariate generalisation of the model where the teacher and student can act on different spaces, generated with fixed, but generic feature maps. While still solvable in a closed form, this generalization is able to capture the learning curves for a broad range of realistic data sets, thus redeeming the potential of the teacher-student framework. Our contribution is then two-fold: first, we prove a rigorous formula for the asymptotic training loss and generalisation error. Second, we present a number of situations where the learning curve of the model captures the one of a realistic data set learned with kernel regression and classification, with out-of-the-box feature maps such as random projections or scattering transforms, or with pre-learned ones such as the features learned by training multi-layer neural networks. We discuss both the power and the limitations of the framework.

heading: 1 Introduction
text: Teacher-student models are a popular framework to study the high-dimensional asymptotic performance of learning problems with synthetic data, and have been the subject of intense investigations spanning three decades [1–7]. In the wake of understanding the limitations of classical statistical learning approaches [8–10], this direction is witnessing a renewal of interest [10–15]. However, this framework is often assuming the input data to be Gaussian i.i.d., which is arguably too simplistic to be able to capture properties of realistic data. In this paper, we redeem this line of work by defining a Gaussian covariate model where the teacher and student act on different Gaussian correlated spaces with arbitrary covariance. We derive a rigorous asymptotic solution of this model generalizing the formulas found in the above mentioned classical works.
We then put forward a theory, supported by universality arguments and numerical experiments, that this model captures learning curves, i.e. the dependence of the training and test errors on the number of samples, for a generic class of feature maps applied to realistic datasets. These maps can be deterministic, random, or even learnt from the data. This analysis thus gives a unified framework to describe the learning curves of, for example, kernel regression and classification, the analysis of
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
feature maps – random projections [16], neural tangent kernels [17], scattering transforms [18] – as well as the analysis of transfer learning performance on data generated by generative adversarial networks [19]. We also discuss limits of applicability of our results, by showing concrete situations where the learning curves of the Gaussian covariate model differ from the actual ones.
Model definition — The Gaussian covariate teacher-student model is defined via two vectors u ∈ Rp and v ∈ Rd, with correlation matrices Ψ ∈ Rp×p,Ω ∈ Rd×d and Φ ∈ Rp×d, from which we draw n independent samples:[
uµ vµ
] ∈ Rp+d ∼ i.i.d. N ( 0, [ Ψ Φ Φ> Ω ]) , µ = 1, · · · , n. (1)
The labels yµ are generated by a teacher function that is only using the vectors uµ:
yµ = f0 ( 1 √ p θ>0 u µ ) , (2)
where f0 : R → R is a function that may include randomness such as, for instance, an additive Gaussian noise, and θ0 ∈ Rp is a vector of teacher-weights with finite norm which can be either random or deterministic. Learning is performed by the student with weights w via empirical risk minimization that has access only to the features vµ:
ŵ = arg min w∈Rd [ n∑ µ=1 g ( w>vµ√ d , yµ ) + r(w) ] , (3)
where r and g are proper, convex, lower-semicontinuous functions ofw ∈ Rd (e.g. g can be a logistic or a square loss and r a `p (p=1, 2) regularization). The key quantities we want to compute in this model are the averaged training and generalisation errors for the estimator w,
Etrain.(w) ≡ 1
n n∑ µ=1 g ( w>vµ√ d , yµ ) and Egen.(w) ≡ E [ ĝ ( f̂ ( v>neww√ d ) , f0 ( u>newθ0√ p ))] .
(4)
where g is the loss function in eq. (3), f̂ is a prediction function (e.g. f̂ = sign for a classification task), ĝ is a performance measure (e.g. ĝ(ŷ, y) = (ŷ − y)2 for regression or ĝ(ŷ, y) = P(ŷ 6= y) for classification) and (unew,vnew) is a fresh sample from the joint distribution of u and v.
Our two main technical contributions are: (C1) In Theorems 1 & 2, we give a rigorous closed-form characterisation of the properties of the estimator ŵ for the Gaussian covariate model (1), and the corresponding training and generalisation errors in the high-dimensional limit. We prove our result using Gaussian comparison inequalities [20]; (C2) We show how the same expression can be obtained using the replica method from statistical physics [21]. This is of additional interest given the wide range of applications of the replica approach in machine learning and computer science [22]. In particular, this allows to put on a rigorous basis many results previously derived with the replica method. Towards realistic data — In the second part of our paper, we argue that the above Gaussian covariate model (1) is generic enough to capture the learning behaviour of a broad range of realistic data. Let {xµ}nµ=1 denote a data set with n independent samples on X ⊂ RD. Based on this input, the features u,v are given by (potentially) elaborated transformations of x, i.e.
u = ϕt(x) ∈ Rp and v = ϕs(x) ∈ Rd (5)
for given centred feature maps ϕt : X → Rp and ϕs : X → Rd, see Fig. 1. Uncentered features can be taken into account by shifting the covariances, but we focus on the centred case to lighten notation.
The Gaussian covariate model (1) is exact in the case where x are Gaussian variables and the feature maps (ϕs,ϕs) preserve the Gaussianity, for example linear features. In particular, this is the case for u = v = x, which is the widely-studied vanilla teacher-student model [24]. The interest of the model (1) is that it also captures a range of cases in which the feature maps ϕt and ϕs are deterministic, or even learnt from the data. The covariance matrices Ψ, Φ, and Ω then represent different aspects of the data-generative process and learning model. The student (3) then corresponds to the last layer of the learning model. These observation can be distilled into the following conjecture:
Conjecture 1. (Gaussian equivalent model) For a wide class of data distributions {xµ}nµ=1, and features maps u = ϕt(x),v = ϕs(x), the generalisation and training errors of estimator (3) are asymptotically captured by the equivalent Gaussian model (1), where [u,v] are jointly Gaussian variables, and thus by the closed-form expressions of Theorem 1.
The second part of our main contributions are: (C3) In Sec. 3.3 we show that the theoretical predictions from (C1) captures the learning curves in non-trivial cases, e.g. when input data are generated using a trained generative adversarial network, while extracting both the feature maps from a neural network trained on real data. (C4) In Sec. 3.4, we show empirically that for ridge regression the asymptotic formula of Theorem 1 can be applied directly to real data sets, even though the Gaussian hypothesis is not satisfied. This universality-like property is a consequence of Theorem 3 and is illustrated in Fig. 1 (right) where the real learning curve of several features maps learning the odd-versus-even digit task on MNIST is compared to the theoretical prediction.
Related work — Rigorous results for teacher-student models: The Gaussian covariate model (1) contains the vanilla teacher-student model as a special case where one takes u and v identical, with unique covariance matrix Ω. This special case has been extensively studied in the statistical physics community using the heuristic replica method [1–3, 24, 25]. Many recent rigorous results for such models can be rederived as a special case of our formula, e.g. refs. [10–15, 26–29]. Numerous of these results are based on the same proof technique as we employed here: the Gordon’s Gaussian min-max inequalities [20, 30, 31]. The asymptotic analysis of kernel ridge regression [32], of margin-based classification [33] also follow from our theorem. See also Appendix A.6 for the details on these connections. Other examples include models of the double descent phenomenon [34]. Closer to our work is the recent work of [35] on the random feature model. For ridge regression, there are also precise predictions thanks to random matrix theory [12, 36–41]. A related set of results was obtained in [42] for orthogonal random matrix models. The main technical novelty of our proof is the handling of a generic loss and regularisation, not only ridge, representing convex empirical risk minimization, for both classification and regression, with the generic correlation structure of the model (1).
Gaussian equivalence: A similar Gaussian conjecture has been discussed in a series of recent works, and some authors proved partial results in this direction [11, 12, 28, 35, 43–46]. Ref. [45] analyses a special case of the Gaussian model (corresponding to ϕt = id here), and proves a Gaussian equivalence theorem (GET) for feature maps ϕs given by single-layer neural networks with fixed weights. They also show that for Gaussian data x ∼ N (0, ID), feature maps of the form v = σ(Wx) (with some technical restriction on the weights) led to the jointly-Gaussian property for the two scalars (v ·w,u · θ0) for almost any vector w. However, their stringent assumptions on random teacher weights limited the scope of applications to unrealistic label models. A related line of work
discussed similar universality through the lens of random matrix theory [47–49]. In particular, Seddik et al. [50] showed that, in our notations, vectors [u,v] obtained from Gaussian inputs x ∼ N (0, ID) with Lipschitz feature maps satisfy a concentration property. In this case, again, one can expect the two scalars (v ·w,u · θ0) to be jointly Gaussian with high-probability on w. Remarkably, in the case of random feature maps, [46] could go beyond this central-limit-like behavior and established the universality of the Gaussian covariate model (1) for the actual learned weights ŵ.

heading: 2 Main technical results
text: Our main technical result is a closed-form expression for the asymptotic training and generalisation errors (4) of the Gaussian covariate model introduced above. We start by presenting our result in the most relevant setting for the applications of interest in Section 3, which is the case of the `2 regularization. Next, we briefly present our result in larger generality, which includes non-asymptotic results for non-separable losses and regularizations.
We start by defining key quantities that we will use to characterize the estimator ŵ. Let Ω = S>diag(ωi)S be the spectral decomposition of Ω. Let:
ρ ≡ 1 d θ>0 Ψθ0 ∈ R, θ̄ ≡ SΦ>θ0√ ρ ∈ Rd (6)
and define the joint empirical density µ̂d between (ωi, θ̄i):
µ̂d(ω, θ̄) ≡ 1
d d∑ i=1 δ(ω − ωi)δ(θ̄ − θ̄i). (7)
Note that Φ>θ0 is the projection of the teacher weights on the student space, and therefore θ̄ is the rotated projection on the basis of the student covariance, rescaled by the teacher variance. Together with the student eigenvalues ωi, these are relevant statistics of the model, encoded here in the joint distribution µ̂d.
Assumptions — Consider the high-dimensional limit in which the number of samples n and the dimensions p, d go to infinity with fixed ratios:
α ≡ n d , and γ ≡ p d . (8)
Assume that the covariance matrices Ψ,Ω are positive-definite and that the Schur complement of the block covariance in equation (1) is positive semi-definite. Additionally, the spectral distributions of the matrices Φ,Ψ and Ω converge to distributions such that the limiting joint distribution µ is well-defined, and their maximum singular values are bounded with high probability as n, p, d→∞. Finally, regularity assumptions are made on the loss and regularization functions mainly to ensure feasibility of the minimization problem. We assume that the cost function r + g is coercive, i.e. lim‖w‖2→+∞(r + g)(w) = +∞ and that the following scaling condition holds : for all n, d ∈ N, z ∈ Rn and any constant c > 0, there exist a finite, positive constant C, such that, for any standard normal random vectors h ∈ Rd and g ∈ Rn:
‖z‖2 6 c √ n =⇒ sup
x∈∂g(z) ‖x‖2 6 C
√ n,
1 d E [r(h)] < +∞, 1 n E [g(g)] < +∞ (9)
The relevance of these assumptions in a supervised machine learning context is discussed in Appendix B.1. We are now in a position to state our result. Theorem 1. (Closed-form asymptotics for `2 regularization) In the asymptotic limit defined above, the training and generalisation errors (4) of the estimator ŵ ∈ Rd solving the empirical risk minimisation problem in eq. (3) with `2 regularization r(w) = λ2 ||w|| 2 2 verify:
Etrain.(ŵ) P−−−→
d→∞ Es,h∼N (0,1)
g proxV ?g(.,f0(√ρs)) m?√ ρ s+ √ q? − m ?2 ρ h  , f0(√ρs) 
Egen.(ŵ) P−−−→
d→∞ E(ν,λ)
[ ĝ ( f̂(λ), f0(ν) )] (10)
where prox stands for the proximal operator defined as
proxV g(.,y)(x) = arg min z {g(z, y) + 1 2V (x− z)2} (11)
and where (ν, λ) are jointly Gaussian scalar variables: (ν, λ) ∼ N ( 0, [ ρ m?
m? q?
]) , (12)
and the overlap parameters (V ?, q?,m?) are prescribed by the unique fixed point of the following set of self-consistent equations: V = E(ω,θ̄)∼µ [ ω λ+V̂ ω ] m = m̂√γE(ω,θ̄)∼µ [ θ̄2 λ+V̂ ω ] q = E(ω,θ̄)∼µ [ m̂2θ̄2ω+q̂ω2
(λ+V̂ ω) 2
] ,  V̂ = αV (1− Es,h∼N (0,1)[f ′ g(V,m, q)]) m̂ = 1√ργ α V Es,h∼N (0,1) [ sfg(V,m, q)− m√ρf ′ g(V,m, q) ] q̂ = αV 2Es,h∼N (0,1) [( m√ ρs+ √ q−m2ρ h−fg(V,m, q)
)2] (13)
where we defined the scalar random functions fg(V,m, q) = proxV g(.,f0(√ρs))(ρ −1/2ms +√
q − ρ−1m2h) and f ′g(V,m, h) = prox′V g(.,f0(√ρs))(ρ −1/2ms +
√ q − ρ−1m2h) as the first de-
rivative of the proximal operator.
Proof : This result is a consequence of Theorem 2, whose proof can be found in appendix B.
The parameters of the model (θ0,Ω,Φ,Ψ) only appear trough ρ, eq. (6), and the asymptotic limit µ of the joint distribution eq. (7) and (f0, f̂ , g, λ). One can easily iterate the above equations to find their fixed point, and extract (q∗,m∗) which appear in the expressions for the training and generalisation errors (E?train, E?gen), see eq. (4). Note that (q?,m?) have an intuitive interpretation in terms of the estimator ŵ ∈ Rd:
q? ≡ 1 d ŵ>Ωŵ, m? ≡ 1√ dp θ>0 Φŵ (14)
Or in words: m? is the correlation between the estimator projected in the teacher space, while q? is the reweighted norm of the estimator by the covariance Ω. The parameter V ∗ also has a concrete interpretation : it parametrizes the deformation that must be applied to a Gaussian field specified by the solution of the fixed point equations to obtain the asymptotic behaviour of ẑ. It prescribes the degree of non-linearity given to the linear output by the chosen loss function. This is coherent with the robust regression viewpoint, where one introduces non-square losses to deal with the potential non-linearity of the generative model. V̂ ∗ plays a similar role for the estimator ŵ through the proximal operator of the regularisation, see Theorem 4 and 5 in the Appendix. Two cases are of particular relevance for the experiments that follow. The first is the case of ridge regression, in which f0(x) = f̂(x) and both the loss g and the performance measure ĝ are taken to be the meansquared error mse(y, ŷ) = 12 (y − ŷ)
2, and the asymptotic errors are given by the simple closed-form expression:
E?gen = ρ+ q? − 2m?, E?train = E?gen
(1 + V ?)2 , (15)
The second case of interest is the one of a binary classification task, for which f0(x) = f̂(x) = sign(x), and we choose the performance measure to be the classification error ĝ(y, ŷ) = P(y 6= ŷ). In the same notation as before, the asymptotic generalisation error in this case reads:
E?gen = 1
π cos−1 ( m?√ ρq? ) , (16)
while the training error E?train depends on the choice of g - which we will take to be the logistic loss g(y, x) = log (1 + e−xy) in all of the binary classification experiments.
As mentioned above, this paper includes stronger technical results including finite size corrections and precise characterization of the distribution of the estimator ŵ, for generic, non-separable loss and
regularization g and r. This type of distributional statement is encountered for special cases of the model in related works such as [28, 29, 51]. Define V ∈ Rn×d as the matrix of concatenated samples used by the student. Informally, in high-dimension, the estimator ŵ and ẑ = 1√
d Vŵ roughly behave
as non-linear transforms of Gaussian random variables centered around the teacher vector θ0 (or its projection on the covariance spaces) as follows:
w∗ = Ω−1/2 prox
1 V̂ ∗ r(Ω−1/2.)
( 1
V̂ ∗ (m̂∗t+
√ q̂∗g) ) , z∗ =
prox V ∗g(.,z) ( m∗ √ ρ s+ √ q∗ − (m ∗)2 ρ h ) .
where s,h ∼ N (0, In) and g ∼ N (0, Id) are random vectors independent of the other quantities, t = Ω−1/2Φ>θ0, y = f0 (√ ρs ) , and (V ∗, V̂ ∗, q∗, q̂∗,m∗, m̂∗) is the unique solution to the fixed point equations presented in Lemma 12 of appendix B. Those fixed point equations are the generalization of (13) to generic, non-separable loss function and regularization. The formal concentration of measure result can then be stated in the following way: Theorem 2. (Non-asymptotic version, generic loss and regularization) Under Assumption (B.1), consider any optimal solution ŵ to 3. Then, there exist constants C, c, c′ > 0 such that, for any Lipschitz function φ1 : Rd → R, and separable, pseudo-Lipschitz function φ2 : Rn → R and any 0 < < c′:
P (∣∣∣∣φ1( ŵ√d ) − Eφ1 ( w∗√ d )∣∣∣∣ > ) 6 C 2 e−cn 4 ,P (∣∣∣∣φ2( ẑ√n ) − Eφ2 ( z∗√ n )∣∣∣∣ > ) 6 C 2 e−cn 4 . Note that in this form, the dimensions n, p, d still appear explicitly, as we are characterizing the convergence of the estimator’s distribution for large but finite dimension. The clearer, one-dimensional statements are recovered by taking the n, p, d → ∞ limit with separable functions and an `2 regularization. Other simplified formulas can also be obtained from our general result in the case of an `1 penalty, but since this breaks rotational invariance, they do look more involved than the `2 case. From Theorem 2, one can deduce the expressions of a number of observables, represented by the test functions φ1, φ2, characterizing the performance of ŵ, for instance the training and generalization error. A more detailed statement, along with the proof, is given in appendix B.

heading: 3 Applications of the Gaussian model
text: We now discuss how the theorems above are applied to characterise the learning curves for a range of concrete cases. We present a number of cases – some rather surprising – for which Conjecture 1 seems valid, and point out some where it is not. An out-of-the-box iterator for all the cases studied hereafter is provided in the GitHub repository for this manuscript at https: //github.com/IdePHICS/GCMProject.

heading: 3.1 Random kitchen sink with Gaussian data
text: If we choose random feature maps ϕs(x) = σ (Fx) for a random matrix F and a chosen scalar function σ acting component-wise, we obtain the random kitchen sink model [16]. This model has seen a surge of interest recently, and a sharp asymptotic analysis was provided in the particular case of uncorrelated Gaussian data x ∼ N (0, ID) and ϕt(x) = x in [11, 12] for ridge regression and generalised by [43, 46] for generic convex losses. Both results can be framed as a Gaussian covariate model with:
Ψ = Ip, Φ = κ1F>, Ω = κ201d1 > d + κ 2 1
FF>
d + κ2?Id, (17)
where 1d ∈ Rd is the all-one vector and the constants (κ0, κ1, κ?) are related to the non-linearity σ: κ0 = Ez∼N (0,1) [σ(z)] , κ1 = Ez∼N (0,1) [zσ(z)] , κ?= √ Ez∼N (0,1) [σ(z)2]− κ20 − κ21 . (18)
In this case, the averages over µ in eq. (13) can be directly expressed in terms of the Stieltjes transform associated with the spectral density of FF>. Note, however, that our present framework can accommodate more involved random sinks models, such as when the teacher features are also a random feature model or multi-layer random architectures.
3.2 Kernel methods with Gaussian data
the target function in the kernel feature basis.
There are many results in classical learning theory on this problem for the case of ridge regression (where the teacher is usually called "the source" and the eigenvalues of the kernel matrix the "capacity", see e.g. [54, 56]). However, these are worst case approaches, where no assumption is made on the true distribution of the data. In contrast, here we follow a typical case analysis, assuming Gaussianity in feature space. Through Theorem 1, this allows us to go beyond the restriction of the ridge loss. An example for logistic loss is in Fig. 2.
For the particular case of kernel ridge regression, Th. 1 provides a rigorous proof of the formula conjectured in [32]. App. A.6 presents an explicit mapping to their results. Hard-margin Support Vector Machines (SVMs) have also been studied using the heuristic replica method from statistical physics in [57, 58]. In our framework, this corresponds to the hinge loss g(x, y) = max(0, 1− yx) when λ → 0+. Our theorem thus puts also these works on rigorous grounds, and extends them to more general losses and regularization.

heading: 3.3 GAN-generated data and learned teachers
text: To approach more realistic data sets, we now consider the case in which the input data x ∈ X is given by a generative neural network x = G(z), where z is a Gaussian i.i.d. latent vector. Therefore, the covariates [u,v] are the result of the following Markov chain:
z 7→ G x ∈ X 7→ ϕt u ∈ Rp, z 7→ G x ∈ X 7→ ϕs v ∈ Rd. (19)
With a model for the covariates, the missing ingredient is the teacher weights θ0 ∈ Rp, which determine the label assignment: y = f0(u>θ0). In the experiments that follow, we fit the teacher weights from the original data set in which the generative model G was trained. Different choices for the fitting yield different teacher weights, and the quality of label assignment can be accessed by the performance of the fit on the test set. The set (ϕt,ϕs,G,θ0) defines the data generative process. For predicting the learning curves from the iterative eqs. (13) we need to sample from the spectral measure µ, which amounts to estimating the population covariances (Ψ,Φ,Ω). This is done from the generative process in eq. (19) with a Monte Carlo sampling algorithm. This pipeline is explained in detail in Appendix D. An open source implementation of the algorithms used in the experiments is available online at https://github.com/IdePHICS/GCMProject.
Fig. 3 shows an example of the learning curves resulting from the pipeline discussed above in a logistic regression task on data generated by a GAN trained on CIFAR10 images. More concretely,
we used a pre-trained five-layer deep convolutional GAN (dcGAN) from [59], which maps 100 dimensional i.i.d. Gaussian noise into k = 32 × 32 × 3 realistic looking CIFAR10-like images: G : z ∈ R100 7→ x ∈ R32×32×3. To generate labels, we trained a simple fully-connected four-layer neural network on the real CIFAR10 data set, on a odd (y = +1) vs. even (y = −1) task, achieving ∼ 75% classification accuracy on the test set. The teacher weights θ0 ∈ Rp were taken from the last layer of the network, and the teacher feature map ϕt from the three previous layers. For the student model, we trained a completely independent fully connected 3-layer neural network on the dcGAN-generated CIFAR10-like images and took snapshots of the feature maps ϕis induced by the 2-first layers during the first i ∈ {0, 5, 50, 200} epochs of training. Finally, once ( G,ϕt,ϕis,θ0
) have been fixed, we estimated the covariances (Ψ,Φ,Ω) with a Monte Carlo algorithm. Details of the architectures used and of the training procedure can be found in Appendix. D.1.
Fig. 3 depicts the resulting learning curves obtained by training the last layer of the student. Interestingly, the performance of the feature map at epoch 0 (random initialisation) beats the performance of the learned features during early phases of training in this experiment. Another interesting behaviour is given by the separability threshold of the learned features, i.e. the number of samples for which the training loss becomes larger than 0 in logistic regression. At epoch 50 the learned features are separable at lower sample complexity α = n/d than at epoch 200 - even though in the later the training and generalisation performances are better.

heading: 3.4 Learning from real data sets
text: Applying teacher/students to a real data set — Given that the learning curves of realistic-looking inputs can be captured by the Gaussian covariate model, it is fair to ask whether the same might be true for real data sets. To test this idea, we first need to cast the real data set into the teacher-student formalism, and then compute the covariance matrices Ω,Ψ,Φ and teacher vector θ0 required by model (1).
Let {xµ, yµ}ntotµ=1 denote a real data set, e.g. MNIST or Fashion-MNIST for concreteness, where ntot = 7 × 104, xµ ∈ RD with D = 784. Without loss of generality, we can assume the data is centred. To generate the teacher, let uµ = ϕt(xµ) ∈ Rp be a feature map such that data is invertible in feature space, i.e. that yµ = θ>0 u
µ for some teacher weights θ0 ∈ Rp, which should be computed from the samples. Similarly, let vµ = ϕs(xµ) ∈ Rd be a feature map we are interested in studying. Then, we can estimate the population covariances (Ψ,Φ,Ω) empirically from the entire data set as:
Ψ = ntot∑ µ=1 uµuµ> ntot , Φ = ntot∑ µ=1 uµvµ> ntot , Ω = ntot∑ µ=1 vµvµ> ntot . (20)
At this point, we have all we need to run the self-consistent equations (13). The issue with this approach is that there is not a unique teacher map ϕt and teacher vector θ0 that fit the true labels. However, we can show that all interpolating linear teachers are equivalent: Theorem 3. (Universality of linear teachers) For any teacher feature map ϕt, and for any θ0 that interpolates the data so that yµ = θ>0 u
µ ∀µ, the asymptotic predictions of model (1) are equivalent. Proof. It follows from the fact that the teacher weights and covariances only appear in eq. (13) through ρ = 1pθ > 0 Ψθ0 and the projection Φ
>θ0. Using the estimation (20) and the assumption that it exists yµ = θ>0 u µ, one can write these quantities directly from the labels yµ:
ρ = 1
ntot ntot∑ µ=1 (yµ) 2 , Φ>θ0 = 1 ntot ntot∑ µ=1 yµvµ . (21)
For linear interpolating teachers, results are thus independent of the choice of the teacher.
Although this result might seen surprising at first sight, it is quite intuitive. Indeed, the information about the teacher model only enters the Gaussian covariate model (1) through the statistics of u>θ0. For a linear teacher f0(x) = x, this is precisely given by the labels.
0.0
0.2
0.4
0.6
te st
m se
epochs=0 epochs=5 epochs=50 epochs=200
0 250 500 750 1000 1250 1500 samples
0.00
0.05
0.10
0.15
tra in
in g
m se
Fig. 1 (right) shows a similar experiment on the MNIST data set, but for different out-of-the-box feature maps, such as random features and the scattering transform [61], and we chose the number of random features d = 1953 to match the number of features from the scattering transform. Note the
characteristic double-descent behaviour [9, 25, 62], and the accurate prediction of the peak where the interpolation transition occurs. We note in Appendix D.1 that for both Figs. 4 and 1, for a number of samples n closer to ntot we start to see deviations between the real learning curve and the theory. This is to be expected since in the teacher-student framework the student can, in principle, express the same function as the teacher if it recovers its weights exactly. Recovering the teacher weights becomes possible with a large training set. In that case, its test error will be zero. However, in our setup the test error on real data remains finite even if more training data is added, leading to the discrepancy between teacher-student learning curve and real data, see Appendix D.1 for further discussion.
Why is the Gaussian model so effective for describing learning with data that are not Gaussian? The point is that ridge regression is sensitive only to second order statistics, and not to the full distribution of the data. It is a classical property (see Appendix E) that the training and generalisation errors are only a function of the spectrum of the empirical and population covariances, and of their products. Random matrix theory teaches us that such quantities are very robust, and their asymptotic behaviour is universal for a broad class of distributions of [u,v] [49, 63–65]. The asymptotic behavior of kernel matrices has indeed been the subject of intense scrutiny [11, 47, 48, 50, 66, 67]. Indeed, a universality result akin to Theorem 3 was noted in [41] in the specific case of kernel methods. We thus expect the validity of model (1) for ridge regression, with a linear teacher, to go way beyond the Gaussian assumption.
Beyond ridge regression — The same strategy fails beyond ridge regression and mean-squared test error. This suggests a limit in the application of model (1) to real (non-Gaussian) data to the universal linear teacher. To illustrate this, consider the setting of Figs. 4, and compare the model predictions for the binary classification error instead of the `2 one. There is a clear mismatch between the simulated performance and prediction given by the theory (see Appendix D.1) due to the fact that the classification error does not depends only on the first two moments.
We present an additional experiment in Fig. 3. We compare the learning curves of logistic regression on a classification task on the real CIFAR10 images with the real labels versus the one on dcGANgenerated CIFAR10-like images and teacher generated labels from Sec. 3.3. While the Gaussian theory captures well the behaviour of the later, it fails on the former. A histogram of the distribution of the product u>ŵ for a fixed number of samples illustrates well the deviation from the prediction of the theory with the real case, in particular on the tails of the distribution. The difference between GAN generated data (that fits the Gaussian theory) and real data is clear. Given that for classification problems there exists a number of choices of "sign" teachers and feature maps that give the exact same labels as in the data set, an interesting open question is: is there a teacher that allows to reproduce the learning curves more accurately? This question is left for future works.

heading: Acknowledgements
text: We thank Romain Couillet, Cosme Louart, Loucas Pillaud-Vivien, Matthieu Wyart, Federica Gerace, Luca Saglietti and Yue Lu for discussions. We are grateful to Kabir Aladin Chandrasekher, Ashwin Pananjady and Christos Thrampoulidis for pointing out discrepancies in the finite size rates and insightful related discussions. We acknowledge funding from the ERC under the European Union’s Horizon 2020 Research and Innovation Programme Grant Agreement 714608-SMiLe, and from the French National Research Agency grants ANR-17-CE23-0023-01 PAIL.

Review summaries:
In this papers the author proposed a new Gaussian covariate teacher-student model that is capable of accurately estimating the training and generalization errors for its learned linear coefficients of its student part with an exponentially decaying concentrate bound. Their framework covers a wide range of learning problems that either are either directly in teacher-student style or can be easily adapted into such setup. Their empirical study demonstrated the effectiveness of their framework for a variety of problems even when letting loose some of the theoretical assumptions required.   

The paper introduces a teacher student method that does not require the input data to follow the i.i.d. assumption. Authors provide a closed form expression for the asymptotic training and generalization error and provide strengths and limitations of the proposed method under empirical settings. The paper covers the related work and the theoretical arguments are sound. The method is tested on synthetic and real world data. 

This paper investigates the performance of a class of teacher-student models in the context of supervised learning, and theoretically derives learning curves in the high-dimensional limit. An important contribution of this paper is to have unified a number of related previous works by introducing a new model called Gaussian covariate model. In this model, two covariates, u and v, are assumed to be generated from a common input data in different ways; u and v are given to the teacher and student, respectively, and are assumed to be mutually correlated Gaussian characterized by generic (though some regularity is assumed) covariance. The introduction of the conversion step from the input to the covariates makes it possible to handle more realistic datasets in the teacher-student framework, while keeping the model analytically tractable by the Gaussian assumption of the covariates. Numerical experiments well support the theoretical prediction. Especially, the experiment using GAN, in which the GAN generated data exhibits a good consistency with the theory while the original one used for training the GAN shows an inconsistency, is interesting since it simultaneously shows the possibilities and limitations of the proposed theory.  

This paper introduces a Gaussian covariate teacher-student model, allowing for the teacher and student to work on different spaces introduced by different feature maps. The authors demonstrate close-form expressions for the training and generalization error in an asymptotic setting. These predicted results are compared with actual performances for kernel methods with ridge regression. The predicted quantities are shown to fit well to observed learning curves, even in the ridge regression case with real data. However, it is also observed that the prediction is limited in general for real datasets.