Learning curves of generic features maps for realistic datasets with a teacher-student model
Authors: Bruno Loureiro
Cedric Gerbelot
Hugo Cui
Sebastian Goldt
Florent Krzakala
Marc Mezard
Lenka Zdeborova
Venue: NeurIPS 2021 Poster (2021)
Keywords: Statistical Physics
Teacher-Student
Replica method
High-dimensional statistics
Gordon comparison theorem
Kernel Methods

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.

Mare Mézard Learning curves of generic features maps for realistic datasets with a teacher-student model
Bruno Loureiro IdePHICS, EPFL, Lausanne
Cédric Gerbelot
Lab. de Physique de l'École Normale Supérieure, Paris
Hugo Cui SPOC, EPFL, Lausanne
Sebastian Goldt
Florent Krzakala IdePHICS, EPFL, Lausanne
SISSA, Trieste
Lenka Zdeborová SPOC, EPFL, Lausanne
École Normale Supérieure, Paris
Abstract
Teacher-student models provide framework in which the typical-case performance nigh-dimensiooal supervised learning can be described in closed form. The assumptions of Gaussian i.i.d. input data underlying the canonical teacher-studes student model may, however, be perceived as too restrictive to capture the behaviour realistic data sets. In this paper, introduce a Gaussian covariate generalisation the model where the teacher and student can act on different spaces, generated with fixed, but generic feature maps. While still solvable in 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 number of situations where the learning curve of the model captures the one of 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.
1 Introduction
Teacher-student models are a popular framework to study the high-dimensionas asymptotic perform- ance of learning problems with synthetic data, and have been the subject of intense investigations spanning three decades TT-7] the wake of understanding the limitations of classical statistical learning approaches 1010 this direction is witnessing 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 capture properties of realistic data. In this paper, redeem this line of work by defining Gaussian covariate model where the teacher and student act on different Gaussian correlated spaces with arbitrary covariance. We derive rigorous asymptotic solution of this model generalizing the formulas found in the above mentioned classical works.
We then put forward theory, supported by universality arguments and numerical experiments, that this model captures learning curves, i.c. the dependence of the training and test errors on the number of samples, for 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 (NcurIPS 2021).

---

feature maps random projections [16], neural tangent kernels [17], scattering transforms [8 as well as the analysis of transfer learning performance on data generated by generative adversarial networks [9]]. 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 E IR" and v E R4, with correlation matrices V E RPxP, S2 E Rdxd and & E Rxxd from which we draw n independent samples:
+ St
)
Rotd
N
0,
1 p= - n..
Lid.
The labels y are generated by a teacher function that is only using the vectors w":
y" ="=fo ( w"
where fo R -> R is a function that may include randomness such as, for instance, an additive Gaussian noise, and Ou R" 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 ot::
T y
i = arg min WER'
Σ g
Vd 34 + r(w)
(3)
where and are proper, convex, swwer-semiconiinuuus functions of w E Idd (e.g. can be logistic or square loss and a Ep 1,2) regularization). The key quantities we want to compute this model are the averaged training and generalisation errors for the estimator w,
Eirain. (wr) = Σ
an
y²
and Egen. (w) E [ (f
11 new w
) 5o
u new Og
)
Vd
Vp
where g is the loss function eq. B.. is prediction function (e.g. f = sign for classification
task), 9 is performance measure (e.g. ((. (y y)² for regression ( 9) PlO + v) for
classification) and (Unew: Unew) is a fresh sample from the joint distribution of u and v.
Our two main technical contributions are:
(C1) In Theorems & 2 we give rigorous closed-form characterisation of the properties of the estimator v for the Gaussian covariate model [ 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 physies 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 rigorous basis many results previously derived with the replica method.
Towards realistic data In the second part of paper, we argue that the above Gaussian covariate model
| is generic enough to capture the learning behaviour of a broad range of realistic data. Let (xr n w==1 denote data with independent samples on X' RDD. Based on this input, the features u, u are given by (potentially) elaborated transformations of æ, i.c.
u = (xr) E R and v = (ar) ) RRd
(5)
for given centred feature maps Φ:: X Rº and &p : X' + Rdd see Fig. Uncentered features 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 are Gaussian variables and the feature maps (4s.) PPx) preserve the Gaussianity, for example linear features. In particular, this is the case for = v which is the widely-studied vanilla teacher-studens model [24]. The interest of model ① is that it also captures a range of cases in which the feature maps (p, and yo are deterministic, or even learnt from the data. The covariance matrices V, t. and Ω then represent different aspects of the deneraenee 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:

---

u E R
No traneform
Scatherig
Random Featues
Kernel
0.6
9/00
bu(u 0g)
8 E R
X RD
Rd
= j(v-w)
training
0.4
== (x)))
R
0.0
1000
2000
3000
4000
5000
samples
Figure 1: Left: Given a data set [== teacher u = ()r(()) and student maps v (2))., we assume (u. v) to be jointly Gaussian random variables and apply the results of the Gaussian covariate model (I) Right: Illustration on real data, here ridge regression on even vs odd MNIST digits, with regularisation X 10-2 Full line is theory, points are simulations. We show the performance with no feature map (blue), random feature map with erf & Gaussian projection (orange), the scattering transform with parameters J 3,
8 [8] (green), and of the limiting kernel of the random map [23] (red). The covariance fi is empirically estimated from the full data set, while the other quantities appearing in the Theorem I are expressed directly as a function of the labels, see Section 3.4 Simulations are averaged over 10 independent runs.
م==1 and features maps u = (z)()), v = (z), the generalisation and training errors of estimator are asymptotically captured by the equivalent Gaussian model (7), where [u, v) are jointly Gaussian variables, and thus by the closed-form expressions of Theorem
Conjecture 1. (Gaussian equivalent model) For a wide class of data distributions {a²")
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 imput data are generated using a trained generative adversarial network, while extracting both the feature maps from neural network trained real data.
(C4) In See. 3.4 we show empirically that for ridge regression the asymptotic formula of Theorem I can be applied directly to real data sets, even though the Gaussian hypothesis is not satisfied. This universality- like property is consequence of Theorem 3 and is illustrated in Fig. [ (right) where the real learning curve of several features maps learning the odd-versus-ewe 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 [T3]] (24, 255. Many recent rigorous results for such models can be rederived as special case of our formula, e.g. refs. [10 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
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 [1] A related set of results was obtained in [2) 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 I..
Gaussian equivalence: A similar Gaussian conjecture has been discussed in series of recent works, and some authors proved partial results in this direction [1] 12
43 46). Ref. [45] analyses a special case of the Gaussian model (corresponding to Φ id here), and proves Gaussian equivalence theorem (GET) for feature maps & given by single-layer neural networks with fixed weights. They also show that for Gaussian data æ ~ .N(0, feature maps of the form v = (War) (with some technical restriction on the weights) led to the jointly- scalars (n w. u. fg) for almost any vector us However, their stringent assumptions on random teacher weights limited the scope of applicationn unrealistic label models. A related line of work
28
35
property for the two
3

---

discussed similar universality through the lens of random matrix theory 47 49. In particular, Seddik al. [50] showed that, in our notations. vectors [u, v| obtained from Gaussian inputs æ -O, with Lipschitz feature maps satisfy concentration property. In this case, again, one can expect the two scalars (vr w. u fo) to be jointly Gaussian with tigh-probbbility on w. Remarkably, in the case of random feature maps, [46] could go beyond this central-limit-Ie behavior and established the universality the Gaussian covariate model ( for the actual learned weights w.
2 Main technical results
Our main technical result is 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 B which is the case of the l 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 v. Let Q S diag(w))S S be the spectral decomposition of Ω. Let:
1 0
SΦ Oo
E R,
θ
R
(6)
vp
and define the joint empirical density paa between (wa, 0.):
Ba(w, 0) Σ
1 d i=1
-ww wi)(( 0.).
Note that & TTo, Oo is the projection of the teacher weights the student space, and therefore 0 is the rotated projection on the basis the student covariance, rescaled by the teacher variance, Together with the student eigenvalues wi, these are relevant statistics of the model, encoded here in the joint distribution pla-
Assumptions Consider the high-dimensional limit in which the number of samples n and the dimensions p, d go to infinity with fixed ratios:
and 7=
(8)
Assume that the covariance matrices L, Q are desitive-definite and that the Schur complement of the block covariance in equation (T) is positive semi-definite. Additionally, the spectral distributions of the matrices Φ V and 52 converge to distributions such that the limiting joint distribution μ is well-defined, and their maximum singular values are bounded with high probability as n, d - co. 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 + g is coercive, i.c. lim 20 (r + ()w) = +o and that the following scaling condition holds for all n, d E N, E IR and any constant > 0, there exist a finite, positive constant C, such that, for any standard normal random vectors h E Rd and g E R":
|| & cvn
sup |لا|| < CVn, e=]g(=)
1 Bl((h)) < to0,
1 n
E[gg() < to0
(9)
The relevance of these assumptions a supervised machine learning context is discussed in Appendix B.1 We are now in position to state result.
Theorem 1. (Closed-form asymptotics for l2 regularization) In the asymptotic limit defined above, the training and generalisation errors (4) of the estimator vú E Rd solving the empirical risk minimisation problem in eq. (3) with &g regularization r(w) = w verify:
E, (E,,mNi [o g proxv- d
]
Etrain. (w))
P
m"
s + v
m
fo((ps))
vp
Egen,(tt) (w)
P,,
P E(eis) (F())
(10)
d=s00

---

where prox stands for the proximal operator defined as
1
proxv s(.u)) (z) arg min + 2V (x 2)2}
(1I)
and where (v, X) are jointly Gaussian scalar variables:
(v. N (o. [0. a )
(12)
and the overlap parameters (V*, q², m²) prescribed by the unique fixed point of the following set of self- self-consistent equations:
V Biwwd)ym
V + N
[V m. m).)))
A+WW
62
-
JoF (.B,A-N(0.))
(V m. q)
v/ (V. m. m,
m
\t m uu (*+Va)
q q= Ex.
m (
/ m² h fo
h- VVm,,9)
p
(13)
where we defined the scalar random functions fg m. = gl. (7a)) (p 1/2 ms
1/2 1/2 + V p mm² h) as the first de- V 4q-p" hm²h) and SV m,,)) - -proxp g(. (p (0-
rivative of the proximal operator.
Proof: This result a consequence of Theorem 2 whose proof can be found in appendix B
The parameters of the model (Oo, Q2 2, 4) only appear trough eq. (6) and the asymptotic limit j of the joint distribution eq. 7 and (Jo, f g, A). One can easily iterate the above equations to find their fixed point, and extract (g m²) which appear in the expressions for the training and generalisation errors (Etrain ). see eq. (4). Note that (g" m²) have an intuitive interpretation terms of the
estimator E Rd.
1
q' = Urr, d
m
Og vD Vdp
(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 Q2. The parameter V also has concrete interpretation it parametrizes the deformation that must be applied to Gaussian field specified by the solution of the fixed point equations to obtain the asymptotic behaviour of 2. 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. 4 plays 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 fo(x)= (x) and both the loss g and the performance measure 9 are taken to the mean- squared enror mse(y. Ø) {3 ÿ)?, and the asymptotic errors are given by the simple closed-form expression:
E* gen
+ g" 2mm"
Eraain
gen
(15)
V.
The second case of interest the one of a binary classification task, for which fo(x) = f(x)
sign(z), and we choose the performance measure to be the classification error g(y, 9) = IPy + 0). In the same notation as before, the asymptotic generalisation error this case reads:
1 -os---
m
CA 'gen
(VPgTT
(16)
while the training error Eigain depends on the choice of which we will take to be the logistic loss x(y,x) log (1 e> 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
5

---

regularization g and This type of distributional statement is encountered for special cases of the model in related works such as [28 29 5T. Define V xnd as the matrix of concatenated samples used by the student. Informally, in high-dimension, the estimator ip and å = va Vuù roughly behave as non-linear transforms of Gaussian random variables centered around the teacher vector Oo (or its projection on the covariance spaces) as follows:
prox w² - -Q-112 G. T 1/2.)
- V
prox (m VT x" V(....))
m
(m )2 h
P
where 8, h ~ (N, I,) and ~ (O, La) are random vectors independent of the other quantities, t Q-1/24 On. y fo (Vps). and (V*, V* ."" .,, ,,²) is the unique solution to the fixed point equations presented in Lemma o2 appendix [ 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 the following way:
Theorem 2. coon-asymptotic version, generic loss and regularization) Under Assumption B.I
consider any optimal solution to Then, there exist constants C, c, d' > 0 such that, for any Lipschitz function Φ1 R IR, and separable, pseudo-l.pschitzz function Φ2 IR"" - R and any
0<6
-oeenet onE P
11
EØ1
02
Ed2
one
V
Note that in this form, the dimensions P, d still appear explicitly, we are characterizing the convergence of the estimator's 's distribution for large but finite dimension. The clearer, one- mieedimnnsional limit with separable functions and an l
statements recovered by taking the n, p, regularization. Other simplified formulas can also be obtained from our general result the case of an la penalty, but since this breaks rotational invariance, they do look more involved than the la case. From Theorem 2 one can deduce the expressions of a number observables, represented by the test functions Φ1, Ø2, characterizing the performance of út, for instance the training and generalization error. A more detailed statement, along with the proof, is given in appendix B
Applications of the Gaussian model
We now discuss how the theorems above are applied to characterise the learning curves for range of concrete cases. We present number of cases - some rather surprising - for which Conjecture [ seems valid, and point out some where it is not. An out-of-the-boo iterator for all the cases studied hereafter provided in the GitHub repository for this manuscript at https //gi
3.1 Random kitchen sink with Gaussian data
If choose random feature maps (x))) (Fx)) for random matrix F and chosen scalar function a acting component-wise, we obtain the random kitchen sink model [6]] This model has surge of interest recently, and sharp asymptotic analysis
provided in the particular
of uncorrelated Gaussian data æ ~ (O,,Ip) and (pr(x) æ in [1] for ridge regression and
generalised by 43 46 model with:
for generic convex losses. Both results can be framed as a Gaussian covariate
FF
V
Ip
F
Ω x
K
L
(17)
where 1, E Rdd is the all-one vector and the constants (No, K1, KI, K.) are related to the non non-linearity a:
Ki = (o [a(=)), K1 = E.-A((..) [zo(:)), K4 k+= ( (a(=)² - x x (18)
In this case, the averages over f in eq. 1 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

---

Logistic regression
Another direct application of our formalism is kemnel methods. Kernel methods admit a dual representation in terms of optimization over feature space [53]. The connection is given by Mercer's s theorem, which provides an bigen-decomposition of the kernel and of the target function in the feature basis, effect- ively mapping kernel regression to a teacher- student problem feature space. The clas- sical way of studying the performance of ker- nel methods [54] [55] is then to directly ana- lyse the performance of convex learning in this space. In our notation, the teacher and stu- dent feature maps are equal, and we thus set p= d, v/ = + S diag(w;) where wi the eigenvalues of the kernel and we take the teacher weights 0g to be the decomposition of the target function in the kernel feature basis.
classification error
0.2
0.1
0.0
0
1000
2000
3000
4000
5000
Ridge regression
1.00
1.25
test mse
0.75
1.5
0.50
0.25
0.00
1000
2000
3000
4000
5000
samples
Figure 2: Learning in kernel space: Teacher and student live in the same (Hilbert) feature space = u E Rd with d >> n, and the performance only depends on the relative decay between the student spectrum Wi di 2- (the capacity) and the teacher weights in feature space Bz:,; d i- (the source). Top: task with sign teacher (in kernel space), fitted with max-margin support vector machine (logistic regression with vanishing regularisation [52)). Bot- tom: a task with linear teacher (in kernel space) fitted via kemne ridge regression with vanishing regularisa- tion. Points are simulation that matches the theory (lines). Simulations are averaged over 10 independ- ent runs.
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) How- ever, these are worst case approaches, where no assumption is made on the true distribu- tion of the data. In contrast, here we follow a typical case analysis, assuming Gaussianity in feature space. Through Theorem [ 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 [3.. App. presents explicit mapping their results. Hard-margin Support Vector Machines (SM have also been studied using the heuristic replica method from statistical physics in (57 58 In our framework, this corresponds the hinge loss g(z, y) max(0, ya) when À - 0+. Our theorem thus puts also these works on rigorous grounds, and extends them to more general losses and regularization.
3.3 GAN-generated data and learned teachers
To approach more realistic data sets, we now consider the case in which the input data x E X' is given by generative neural network x ((2), where is Gaussian i..dd latent vector. Therefore, the covariates [u,, U] are the result of the following Markov chain:
x E X + u ERP,
(19)
With model for the covariates, the missing ingredient is the teacher weights Og E R.,, which determine the label assignment: y fo) 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 (42t. Px. G. 0p) defines the data generative process. For predicting the learning curves from the iterative eqs. 333 we need to sample from the spectral measure J4, which amounts to estimating the population covariances (L, C (2). This is done from the generative process in eq. (9) with 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 /eettp://ggthhee com/
Fig. shows an example of the learning curves resulting from the pipeline discussed above in a logistic regression task on data generated by GAN trained on CIFARIO images. More concretely,
7

---

classificatoon error
Epech
tpach
classification efror
0.3
0.4
Epoch =
Epoch 200
0.4
0.2
0.2
Real data
0.1
0.0
10
10
0.6
training loss
0.4
0.3
0.4
training
0.2
0.2
0.2
0.1
0.0
0.00
0.25
0.50
0.75
1.00
1.25
1.50 1.75
2.00
0
1000
2000
10
0
10
sample complexity r/d
samples
samples
Figure 3: Left: generalisation classification error (top) and (unregularised) training loss (bottom) the sample complexity deGAN--enerated CIFARIO-BE 10-like images labelled by a teacher fully-connected neural network (see Appendix for architecture details), with vanishing l2 regularisation. The different curves compare featured maps at different epochs of training. The theoretical predictions based on the Gaussian covariate model (full lines) are in very good agreement with the actual performance (points). Right: Test classification error (top) and (unregularised) training loss, (bottom) for logistic regression as function of the number of samples n for an animal vs not-animal binary classification task with & regularization À = 10 comparing real CIFARI0 grey-scale images (blue) with dcGAN deGAN-gennrated generrated CIFARTON li-kee gray-scale images (red). The real-data learning curve was estimated, just as Figs. from the population covariances on the full data set, and it is not in agreement with the theory in this case. On the very right we depict the histograms of the variable <a" for fixed number of samples n = 2d 2048 and the respective theoretical predictions (solid line). Simulations are averaged over 10 independent runs.
n/d for logistic regression
learned feature map trained
we used a pre-trained five-layer deep convolutional GAN (deGAN) from 59 which maps 100 dimensional i..d. Gaussian noise into k 32 x 32 3 realistic looking CIFARIO-like images: G : E 100 + x 32x332x3 To generate labels, we trained simple fully-connected four-layer neural network the real CIFARIO data set, odd (y +1) ~ 75% classification accuracy on the test set. The teacher weights 0g E R were taken from the last layer of the network, and the teacher feature map &,, from the three previous layers. For the student model, we trained a completely independent fully connected 3-layer neural network on the deGAN-generated CIFAR 1i-like images and took snapshots of the feature maps s induced by the 2-first layers during the first i E {0,5, 50, 200} epochs of training. Finally, once (G, Pi. 4p', 0o) have been fixed, we estimated the covariances (T) 4. Ω) with a Monte Carlo algorithm. Details of the architectures used and of the training procedure can be found in Appendix, D.I
(y = 1) task, achieving
Fig. 3 depicts the resulting learning curves obtained by training the last layer of the student. Interest- ingly, 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 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 training and generalisation performances are better.
n/d than at epoch 200 even though in the later the
3.4 Learning from real data sets
Applying feacher/students to a real data set Given that the learning curves of realistic-looking inputs can be captured by Gaussian covariate model, it is fair to 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 Q2 V, and teacher vector O required by model

---

Let fa" 3 j denote a real data set, e.g. MNIST or Dushion-MNIST for concreteness, where foor 7 10a, x E RD with D 784. Without loss of generality, we can assume the data is centred. To generate the teacher, let w" = (p ) E Iº be a feature map such that data is invertible in feature space, i.. that y = 0 un for some teacher weights 6g E IR,, which should be computed from the samples. Similarly, let T = sp,(2")) E TR: be feature map we are interested in studying. Then, we can estimate the population covariances (V, (2) empirically from the entire data set as:
Thus
u u
Rut
(20)
Thro
Reot
Root
At this point, we have all we need to run the self-consistent equations (3 approach is that there is not unique teacher map 9: and teacher vector Oo that fit the true labels. However, we can show that all interpolating linear teachers are equivalent:
The issue with this
Theorem 3. (Universality of linear teachers) For any feature map 4t:, and for any Oo that interpolates the data so that y 0g u² Vy, the asymptotic predictions of model (/) are equivalent. Proof. It follows from the fact that the teacher weights and covariances only appear in eq. (13) through p y 0 V and the projection & 0n- Using the estimation (20) and the assumption that
exists y = 0g un,,, one can write these quantities directly from the labels y
1 7h
1 Than
(Ur))
T
T
0
yd od
(21)
Thet
nhot
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 (I) through the statistics of u 6g- For a linear teacher fa( = 2r, this is precisely given by the labels.
Ridge Regression with linear teachers
We now test the prediction of model (T) on real data sets, and show that it is surprisingly ef- fective in predicting the learning curves, at least for the ridge regression task. We have trained a 3-layer fully connected neural network with the full Fashion-MNIST data set to distinguish clothing used above vs. below the waist [60). The student feature map 9, : R781 + Rd is obtained by removing the last layer, see Appendix D.I] for a detailed de- scription. In Fig. 4 we show the test and training errors of the ridge estimator on sub-sample of n < Aoot on the Fashion-MNIST images. We observe remarkable agreement between the learning curve obtained from simulations and the theoretical prediction by the matching Gaus- sian covariate model. Note that for the square loss and for X < 1, the worst performance peak is located at the point in which the linear system becomes invertible. Curiously, Fig. 4 shows that the fully-connected network progressively learns a low-rank representation of the data as training proceeds. This can be directly verified by counting the number of zero eigenvalues of Ω. which go from a full-rank matrix to matrix of rank 380 after 200 epochs of training.
0.6
ntechs-10
163
0.2
0.0
ReLU activations
0.15
training mse
0.10
0.05
0.00
250
500
750
1000
1250
1500
samples
Figure 4: Test and training mean mean-squaree squared errors eqs. (15) as a function of the number of samples for ridge regression. The Fashion-MNIST data set, with vanishing regularisation = 10-5, In this plot, the student feature map ş. is 3-yerr fully-comnected neural network with = 2352 hidden neurons trained on the full data set with the square loss. Different curves correspond to the feature map obtained at different stages of training. Simulations are averaged over 10 independent runs. Further details on the simulations are described in Appendix D.I
Fig. (right) shows a similar experiment on the MNIST data set, but for different out-of-the-bor feature maps, such as random features and the scattering transform [T], and we chose the number of random features d = 1953 to match the number of features from the scattering transform. Note the

---

characteristic Couble-descent behaviour 9 25 62 and the accurate prediction of the peak where the interpolation transition occurs. We note in Appendix that for both Figs, and II for number of samples n closer to Thot 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.I 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 classical property (see Appendix F. 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 broad class of distributions of [u, v] [49 65-65. The asymptotic behavior of kernel matrices has indeed been the subject of intense scrutiny 41 48 50 66 67]. Indeed, a universality result akin to Theorem 3 was noted in 4I in the specific case of kernel methods. We thus expect the validity of model 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 (I) 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 E one. There is clear mismatch between the simulated performance and prediction given by the theory (see Appendix D.I due to the fact that the classification error does not depends only on the first two moments.
We present an additional experiment in Fig. We compare the learning curves of logistic regression on classification task the real CIFAR 10 images with the real labels versus the one on dcGAN- generated CIFAR 10-like images and teacher generated labels from Sec. (33 While the Gaussian theory captures well the behaviour of the later, it fails the former. A histogram of the distribution of the product u v for 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 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 teacher that allows to reproduce the learning curves more accurately? This question is left for future works.
Acknowledgements
We thank Romain Couillet, Cosme Louart, Loucas Pillaud-Vivise 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 21460--SMiLe and from the French National Research Agency grants ANR-17-CE23-0023-00 PAIL.
10

---

References
[1] Hyunjune Sebastian Scung, Haim Sompolinsky, and Naftali Tishby. Statistical mechanics of learning from examples. Physical review A, 45(8):605,, 1992.
[2] Timothy LH Watkin, Albrecht Rau, and Michael Bichl. The statistical mechanies of learning a rule. Reviews of Modern Physics, 65(2))499, 1993.
[3] Andreas Engel and Christian Van den Broeck. Statistical mechanics of learning. Cambridge University Press, 2001.
[4] David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45::18114-18119 2009.
[5] Noureddine EI Karoui, Derek Bean, Peter J Bickel, Chinghway Lim, and Bin Yu. On robust regression with high-dimensional predictors. Proceedings of the National Academy of Sciences, 110336)14557-1456,, 2013.
[6] Lenka Zdeborová and Florent Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 65(5):453-552, 2016.
[7] David Donoho and Andrea Montanari. High dimensional robust m-estimation: Asymptotic variance via approximate message passing. Probability Theory and Related Fields, 166(3- 4):935-969, 2016.
[8] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
[9] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias- variance trade-off. Proceedings of National Academy of Sciences, 16633):15849--158
2019.
[10] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1167-118)) 2020.
[11] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint :t0i:::9000.035555 2019.
[12] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint (rXiv:1903.085000 2019.
[13] Emmanuel J Candès, Pragya Sur, et al. The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression. The Annals of Statistics, 48(1):27- 42, 2020.
[14] Benjamin Aubin, Florent Krzakala, Yue M Lu, and Lenka Zdeborová. Generalization error in high-dimensional perceptrons: Approaching bayes error with convex optimization. In Advances in Neural Information Processing Systems, volume 33, 2020.
[15] Fariborz Salchi, Ehsan Abbasi, and Babak Hassibi. The performance analysis of generalized margin maximizers on separable data. In International Conference on Machine Learning, pages 8417-8426. PMLR, 2020.
[16] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pages 1177-1184, 2008
[17] 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
[18] Mathieu Andreux, Tomás Angles, Georgios Exarchakis, Roberto Leonarduzzi, Gaspar Rochette, Louis Thiry, John Zarka, Stéphane Mallat, Joakim Andén, Fugene Belilovsky, al. Kymatio: Scattering transforms in python. Journal of Machine Learning Research, 21(60) 2020.
11

---

[19] Ian J. Goodfellow, Jean Pouget- Abadie. Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks, 2014.
[20] Yehoram Gordon. Some inequalities for gaussian processes and applications. Israel Journal of Mathemafics, 50(4):265- 289, 1985.
[21] Mare 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.
[22] Marc Mézard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009,
[23] Christopher K. I. Williams. Computing with infinite networks. In Proceedings of the 9th International Conference on Neural Information Processing Systems, NIPS*96, page 295-301, Cambridge, MA, USA, 1996. MIT Press.
[24] Elizabeth Gardner and Bernard Derrida. Three unfinished works on the optimal storage capacity of networks. Journal of Physics A: Mathematical and General, 22(12):1983, 1989.
[25] Manfred Opper and Wolfgang Kinzel. Statistical mechanies of generalization. In Models of neural networks III. pages 159- Springer, 1996.
[26] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? In Advances in Neural Information Processing Systems, volume 33, 2020.
[27] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592-5628, 2018.
[28] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: figh-dimensional asymptotics in the overparametrized regime. 2019.
arXiv preprint arXiv:
[29] Michael Celentano, Andrea Montanari, and Yuting Wei. The lasso with general gaussian designs with applications to hypothesis testing. arXiv preprint 20xXiv:000..37166 2020.
[30] Mihailo Stojnic. A framework characterize performance of lasso algorithms. arXiv preprint arXiv:1303.7291, 2013.
[31] Samet Oymak, Christos Thrampoulidis, and Babak Hassibi. The squared-error of generalized lasso: A precise analysis. In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1002-1009. IEEE, 2013.
[32] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pages 1024-1034. PMLR, 2020.
[33] Hanwen Huang and Qinglong Yang. Large scale analysis of generalization error in learning using margin based classification methods. Journal of Statistical Mechanics: Theory and Experiment, 1030(10) 2020.
[34] Partha P Mitra. Understanding overfitting peaks in generalization error: Analytical risk curves for 1_2 and 1_1 penalized interpolation. arXiv preprint arXiv: 1906.0366, 2019.
[35] Oussama Dhifallah and Yue M Lu. A precise performance analysis of learning with random features. arXiv preprint arXiv:2008. / 1904, 2020.
[36] Edgar Dobriban. Stefan Wager, et al. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
[37] Denny Wu and Ji Xu. On the optimal weighted &g regularization in overparameterized linear regression. In Advances in Neural Information Processing Systems, volume 33, 2020.
12

---

[38] 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. In Advances in Neural Information Processing Systems, volume 33, 2020.
[39] Fanghui Liu, Zhenyu Liao, and Johan AK Suykens. Kemel regression in high dimension: Refined analysis beyond double descent. arXiv preprint arXiv:2010.02681,2222 2020.
[40] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30063-30077 2020.
[41] Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernel alignment risk estimator: Risk prediction from training data, arXiv preprint arXiv:2006.09796, 2020.
[42] Cédric Gerbelot, Alia Abbara, and Florent Krzakala. Asymptotic errors for high-dimensional convex penalized linear regression beyond gaussian matrices. In Conference on Learning Theory, pages 1682-1713. PMLR, 2020.
[43] Gerace, B. Loureiro, F. Krzakala, M. Mézard, and Zdeborová. Generalisation error in learning with random features and the hidden manifold model. In 37th International Conference on Machine Learning, 2020.
[44] S. Goldt, M. Mézard, F. Krzakala, and I.. Zdeborová. Modeling the influence of data structure on learning in neural networks: The hidden manifold model. Phys. Rev. X, (044):01144, 2020.
[45] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. The gaussian equivalence of generative models for learning with two-layer neural networks. In Mathematical and Scientific Machine Learning, 2021.
[46] Hong Hu and Yue M Lu. Universality laws for high-dimensional learning with random features. arXiv preprint arXiv:2009.00 07660,, 2020.
[47] Noureddine El Karoui et al. The spectrum of kernel random matrices. Annals of statistics, 38(1):1-50, 2010.
[48] Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. In Advances Neural Information Processing Systems, volume 30, pages 2637-2646, 2017.
[49] Cosme Louart and Romain Couillet. Concentration of measure and large random matrices with an application sample covariance matrices. arXiv preprint arXiv: 1 080508829, 2018.
[50] Mohamed El Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet. Random matrix theory proves that deep learning representations of gan-data behave as gaussian mixtures. In International Conference on Machine Learning, pages 8573-8582. PMLR, 2020.
[51] Léo Miolane and Andrea Montanari. The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning. arXiv preprint
2018.
[52] Saharon Rosset, Ji Zhu, and Trevor Hastie. Margin maximizing loss functions. In NIPS, pages 1237-1244, 2003.
[53] B. Scholkopf and A.J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. Adaptive Computation and Machine Learning. MIT Press, 2018
[54] Ingo Steinwart, Don R Hush, Clint Scovel, et al. Optimal rates for regularized least squares regression. In COLT, pages 79,93, 2009.
[55] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
[56] Loucas Fillad-Viiveen Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Advances in Neural Information Processing Systems, volume 31, pages 81 3114-8124, 2018.
13

---

[57] Rainer Dietrich, Manfred Opper. and Haim Sompolinsky. Statistical mechanics of support vector networks. Phys. Rev. Lett., 82:2975-299 2978, Apr 1999.
[58] M. Opper and R. Urbanczik. Universal learning curves of support vector machines. Phys. Rev. Lett., 86:4410-4413, May 2001.
[59] A. Radford, L. Metz, and S. Chintala. Unsupervised representation learning with deep convolu- tional generative adversarial networks. In ICLR, 2016.
[60] Han Xiao. Kashif Rasul, and Roland Vollgraf. Fashion-mnise mnist:: a novel image dataset for benchmarking machine learning algorithms, 2017.
[61] J. Bruna and S. Mallat. Invariant scattering convolution networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1872-1886 2013.
[62] Stefano Spigler, Mario Geiger, Stéphane d' Ascoli, Levent Sagun, Giulio Biroli, and Matthieu Wyart. A jamming transition from under-to wer-ppaaametrization affects generalization in deep learning. Journal of Physics A: Mathematical and Theoretical, 52(47):474001, 2019.
[63] Zhidong Bai and Wang Zhou. Large sample covariance matrices without independence structures columns. Statistica Sinica, pages 425-442, 2008
[64] Olivier Ledoit and Sandrine Péché. Eigenvectors of some large sample covariance matrix ensembles. Probability Theory and Related Fields, 151(1):233 264, 2011.
[65] Noureddine El Karoui et al. Concentration of measure and spectra of random matrices: Applic- ations to correlation matrices, elliptical distributions and beyond. Annals of Applied Probability, 19(6):2362-2444 2009.
[66] Xiuyuan Cheng and Amit Singer. The spectrum of random inner-product kernel matrices. Random Matrices: Theory and Applications, 2(04))1350011 2013.
[67] Zhou Fan and Andrea Montanari. The spectral norm of random inner-product kernel matrices. Probability Theory and Related Fields, 173(1):27-85, 2019.
[68] Heinz H Bauschke, Patrick L Combettes, et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
[69] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
[70] Yanting Ma, Cynthia Rush, and Dror Baron. Analysis of approximate message passing with a class of non-separable denoisers. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 231-235. IEEE, 2017.
[71] Roman Vershynin. Introduction to the non-asymptotic analysis random matrices. In Y. Eldar and G. Kutyniok., editors, Compressed Sensing, Theory and Applications. Cambridge University Press, 2012.
[72] Rick Durrett. Probability: theory and examples, volume 49, Cambridge university press, 2019.
[73] Per Kragh Andersen and Richard D Gill. Cox's regression model for counting processes: large sample study. The annals of statistics, pages 1100-1120, 1982.
[74] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[75] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. 2015 IEEE International Conference Computer Vision (ICCV), pages 1026-1034, 2015.
(76] Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Proceedings of the 3rd International Conference for Learning Representations, volume 3, 2015.
14

---

[77] Greg W Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction to random matrices. Number 118. Cambridge university press. 2010.
[78] Vladimir Alexandrovich Marchenko and Leonid Andreevich Pastur. Distribution eigenvalues for some sets of random matrices. Matematicheskii Sbornik, 114(4):507-536, 1967.
[79] Djalil Chafai and Konstantin Tikhomirov. On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence. Probability Theory and Related Fields, 170 2018.
[80] Walid Hachem, Philippe Loubaton, Jamal Najim, et al. Deterministic equivalents for certain functionals of large random matrices. The Annals of Applied Probability, 17(3):875-930, 2007.
15


Reviews:
[{"review_id": "uiCPNOTHhs", "reviewer": "Reviewer_Dp3D", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "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": "Originality: The paper presents an interesting step forward compared to the current literature based on teacher-student models. The proposed extension makes it possible in particular to have different working spaces for the teacher and the student, which is an important characteristic. In particular, this echoes the paradigm of learning with privileged information, which is not discussed in the paper but could be an interesting application case. Otherwise, the paper is will located in the state of the art and the authors are very explicit about related works, and their contributions. \n\n\nQuality:  The paper seems of a very high technical quality, with some reservation which I will discuss later. I particularly appreciated that the main paper focuses on a the explanation and intuition aspect of the work, proposing extremely pertinent discussions on the presented results. Unlike in many other papers, here the authors have a rigorous approach, presenting their observations and analyses of these observations (a typical example is the final discussion on why ridge regression predictions work so well even on real datasets which are not Gaussian). Based on the main paper only, my opinion is that the paper is a sound and rigorous research. \nMy main concern however is that the results presented in the paper all depend on proofs which are all detailed in appendix. I could not complete a thorough review of the proofs in the reviewing time. What I read and reviewed seems correct, but I do not think it is possible to accept the paper with a doubt on the technical validity of the presented results. Actually, the problem here is that the technical content contained in the appendix is at least as important as the content of the main paper, and not additional information. For this reason, I tend to think that the paper would be more adapted to a journal. I will continue reviewing the proof until the end of the reviewing process and hope that some other reviewers could have checked the proofs already. If I can confirm the validity of the appendix (and depending on errors that other reviewers may have noticed), then I will change my score to a 8. \n\nMinor comments and typos:\n- l.39: mention that mu corresponds to the index of a data point\n- l.44: “and” rather than “&” between mathematical symbols\n- Figures: mention the number of runs used to compute the standard deviation\n- Equation 14: Is there an intuitive interpretation of V*? \n- l.171: Assumption (B1) is presented in the appendix only. Please introduce it in the paper. \n- l.241: that follows => that follow\n- l.316-319: Explanations unclear. Could you please rephrase it?\n- l. 339: two first => first two\n\nA very open question: Do you think a general teacher able to reproduce learning curves for more general cases could exist? I can imagine here that some no-free-lunch result could be proven, showing that no such general teachers could be found. What is your opinion on this question?\n\nClarity: The paper is extremely well-written and clear to read. \n\nSignificance: The proposed work tackles important problems and is an important theoretical contribution.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper has no direct societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concern", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "XtSzCdAD-_H", "reviewer": "Reviewer_mfPa", "summary": "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. \n", "questions": "", "limitations": "", "rating": 6, "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": "Originality: The above idea introducing the conversion from the input to the covariates is new and interesting. Methods mainly used in the analysis are the replica method and the Gordon's theorem; they are not new. \n\nQuality: The results are well supported by the consistency between the analysis and the numerical experiment. The theoretical computations are also described and I do not find any serious error in it. The quality is high in this sense. \n\nClarity: I think the presentation is not clear: there are too many claims in the manuscript, which makes it hard to see what the important points are. In my opinion, the crucial contribution of this paper is the introduction of the Gaussian covariate model which is flexible and opens a possibility to treat modern realistic datasets in the teacher-student scenario; thus, it is better to mainly focus on this point. In this context, I do not understand why two computations by the replica method and by the Gordon's theorem are both necessary in the present manuscript. The position of the non-asymptotic case results is also unclear.  \nAlso, I found small but many typos, unexplained details of the model/problem setting, misleading expressions, undeclared abbreviations, and redundant repetitions, especially in the Supplementary Material. (I will give a very brief list of these things below.) These make the manuscript hard to read. Overall, I think the level of clarity is low. \n\nSignificance: I think the analysis based on the above idea potentially has a large significance, since it provides a possibility to make the theory closer to the practice in real data analysis. Unfortunately, this point is not fully pursued in the present manuscript. Overall, I think the significance level is medium.\n\nThe list of typos, misleading expressions, etc.:\n\n%%\n\nLine 44: r and g are assumed to be convex and thus they are continuous, implying that ``lower-semicontinuous'' assumption is unnecessary.\n\nLines 64,66: the mathematical characters become non-italic here.\n\nLines 190: I think id is the abbreviation of identity, but it is better to explain at the first appearance.\n\nEq. (27): It is better to define Z.\n\nA sentence below Eq. (29):\n\"which the deterministic case in which this is fixed given\"\nIs this grammatically correct?\n\nA sentence below Eq. (38):\nInserting this ansatz in eq. (34) allow us\n->\nInserting this ansatz in eq. (34) allows us\n(Similar error of missing the third-person singular -s are found many times)\n\netc.\n\n%%\n\nSome other suggestions and comments:\n\n%%\n\nSection 3: More explanation is desired for each concrete setting. \n\nTheorem 3: Universality of the linear model should be explained more deeply somewhere, not only by stating the theorem. \nAbout regularization: In this manuscript, mainly the $\\ell_2$ regularization is considered. What happens if the $\\ell_1$ is used? I think the $\\ell_1$ regularization breaks the rotational symmetry and thus the computation does not proceed well in this case. If so, it is better to state this as one of limitations of the theory. \n%%\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not relevant to this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}, {"review_id": "VXzsxqC8DHR", "reviewer": "Reviewer_azvB", "summary": "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.\nThe paper covers the related work and the theoretical arguments are sound. The method is tested on synthetic and real world data. ", "questions": "", "limitations": "", "rating": 6, "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": "Originality: The paper builds on existing teacher student setting and take it to the next level by dropping the requirement of iid data which makes the method applicable to real data.\n\nQuality: The theoretical discussions in the paper are solid and experimental results back the claims. Authors have tested the method under different synthetic and real data settings.\n\nClarity: My main concern with this submission is clarity. The reader needs to go back and forth between the main body and the appendix to follow the theoretical discussions which is time consuming. The flow of the paper is not well organized in parts and theoretical discussions and experimental results are mixed. Authors could have double clicked on some interesting observations in the experimental results (e.g. Fig 4 vs. Fig 3 and the effect of the number of epochs on the classification errors across data sets with different characteristics).\n\nSignificance: The contributions are fairly significant. The authors could have shed more light into the trade offs between the computational overhead of the proposed approach versus the classification error improvement.\n\n\nMinor:\n\nline 40: such as, for instance => such as\n\nline 120: The use case for joint empirical density is not clear.\n\nline 154: \"the one of a\", consider rewording.\n\ncontributions are scattered all over introduction and can be unified.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal impact from this work is very comparable to any other machine learning model that my suffer from bias or skewed training data and not necessarily related to the proposed method.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "EFrDRcX3E4J", "reviewer": "Reviewer_Yv7K", "summary": "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. \n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 authors deliver a strong theoretical study on their new model of framing a wide range of learning problems into a Gaussian covariate teacher and student model. The guaranteed training and generalization errors and the versatility of their framework are all promising results, and the paper is relatively sound in its theoretical development. That said, the presentation of the results could be clarified. \n\nThe reviewer has a few major concerns regarding the theoretical results, as follows:\n\n1. Regarding Theorem 1, how closed-form it is seems to depend on the optimization problem of prox_{V, g} and the iterative steps to find the fixed points of the parameters for the projected 2d Gaussian distribution. The former part would not be closed form should the loss function do not have closed form solution. The latter part seems unlikely to finish exactly in finite steps. It would also be nice to have more discussions on prox_{V, g} - it is quite strong in the theorem in the sense that it technically solves the problem in the projected space therefore determines the training error term.\n\n2. Regarding Theorem 3, the fact that the result is independent of all perfect linear teachers somehow suggests that the teacher part of the framework can be omitted in practice since all its influence is through the covariance structure after the feature map, while this structure, as shown in the theorem, can be estimated directly from the label and the student's feature map. \n\nThe reviewer also thinks the deliver of the paper, especially the theoretical development, could be more clarified and use more explanations. There are typos that prevent a smooth pass through the theory in its current shape. To name a few:\n- Line 120, \\hat{\\mu}_d is defined but never used.\n- \\mu is double used as both a sample index and a limiting distribution\n- Before Theorem 1, line 129, C_2 and C_3 are mentioned but never used.\n- Theorem 1, z is double used (consider directly define z as prox).\n- Theorem 2, Assumption (B.1) is not numbered in the context. \n- Line 167, (V*, .. \\hat{m}*) could have their definition in the main body. \n\n====\nPost rebuttal:\n\nThe reviewer would like to thank the authors for addressing most of the concerns, and would like to raise the rating to a 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper received four reviews in total, with the scores/confidences (after the author response) being 6/3, 6/3, 6/2, and 6/3. Upon reading by myself the reviews and the author response, as well as the paper itself, my judgement on this paper is that, whereas it has a clarity issue as pointed out by most reviewers, it presents an interesting piece of theoretical work. Overall, the reviewers evaluated quite positively this paper's contributions such as:
- Crystallizing those problem settings in some recent pieces of work into the formulation which the authors call the novel Gaussian covariance teacher-student model.
- Providing a rigorous characterization of the properties of the proposed model (summarized in Theorems 1 ($d\to\infty$) and 2 (non-asymptotic)) under fairly generic settings (although the reviewers would not have checked all the details of the proofs in SM).
- Demonstrating applicability of the theoretical predictions to more realistic scenarios. The problem setting in the proposed model would seem rather simplistic as both the teacher and the student are essentially assumed to be single-layer perceptrons. Nevertheless, the authors argue via what is called the Gaussian equivalence conjecture (GEC; Conjecture 1) that the analytical results would be able to capture asymptotic behaviors of a wider class of models beyond the proposed model. The GEC was empirically confirmed on the teacher-student setting in this paper via the experiments on trained generative networks (Section 3.3), where one focuses on the last layers of the trained teacher and student networks which allows us to cast the problem into the analytical framework of this paper except the Gaussianity, as well as on ridge regression (Section 3.4), where not the Gaussianity but second-order statistics determine the learning behaviors. The empirical validation of the GEC on the teacher-student setting is another main contribution of this paper.

On the basis of the positive scores as well as the above evaluations, I am happy to recommend acceptance of this paper.

I agree with the authors that some comments on computational aspects as non-essential. As for the clarity issue, I also agree with the authors that this paper contains a lot of theoretical and experimental results so that it may be somehow unavoidable for such a paper to be dense. Still, my impression is that there exist some gaps between the arguments given in natural language and those given in the form of mathematical expressions. As an example, one could explain significance of the density $\hat{\mu}_d$ in equation (7) in terms of a kind of gauge transform, as follows:
> As the teacher sees its input $u$ through its one-dimensional projection $\theta_0^Tu$, the distribution of the teacher input is characterized by the variance of the projection $\theta_0^Tu$, which is proportional to $\rho$. Also, one can rotate the coordinates of the student input $v$ so that its elements are independent. Thus the joint input distribution is fully characterized under the teacher-student setting in this paper by the variances of the independent elements of the student input, which are proportional to $\bar{\theta}_i$s, and their covariances with the projection $\theta_0^Tu$, which are proportional to $\omega_i$s.

Such an explanation should be beneficial not only as it clarifies the meaning of these quantities but also as it would furthermore suggest how to extend the theoretical discussion in this paper to more general cases, for example, to the case with a committee machine as the teacher.

Some very minor points:
- Font styles in mathematical formulas are sometimes inconsistent. For example, vector quantities such as $x,u,v$ are in some occasions written in bold roman, whereas in other occasions they appear in bold italic.
- Equation (4): The argument of $f_0$ should be divided by $\sqrt{p}$.
- Line 51: In Theorem(s)
- Lines 52-53: training and generalisation error(s)
- Lines 152, 233: $x$ and $y$ should be italic.
- Line 157: the training (loss $\to$ error)
- Line 162: such as (e.g.)
- Line 188: kitchen sink(s) model
- Line 193: all-one(s) vector
- Line 196: random sink(s) models
- Line 241: that follow(s)
- Line 252: five-layer(s) Deep convolutional GAN
- Line 274: the covariance(s) matrices
- Line 283: that fit(s) the true labels
- Line 314: Fig(s). 4 and 1
Decision: Accept (Poster)