Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
The paper covers the related work and the theoretical arguments are sound. The method is tested on synthetic and real world data. 
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.

Quality: 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.

Clarity: 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).

Significance: 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.


Minor:

line 40: such as, for instance => such as

line 120: The use case for joint empirical density is not clear.

line 154: "the one of a", consider rewording.

contributions are scattered all over introduction and can be unified.


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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 


Quality:  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. 
My 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. 

Minor comments and typos:
- l.39: mention that mu corresponds to the index of a data point
- l.44: “and” rather than “&” between mathematical symbols
- Figures: mention the number of runs used to compute the standard deviation
- Equation 14: Is there an intuitive interpretation of V*? 
- l.171: Assumption (B1) is presented in the appendix only. Please introduce it in the paper. 
- l.241: that follows => that follow
- l.316-319: Explanations unclear. Could you please rephrase it?
- l. 339: two first => first two

A 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?

Clarity: The paper is extremely well-written and clear to read. 

Significance: The proposed work tackles important problems and is an important theoretical contribution.  

limitations_and_societal_impact: The paper has no direct societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 


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. 

The reviewer has a few major concerns regarding the theoretical results, as follows:

1. 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.

2. 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. 

The 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:
- Line 120, \hat{\mu}_d is defined but never used.
- \mu is double used as both a sample index and a limiting distribution
- Before Theorem 1, line 129, C_2 and C_3 are mentioned but never used.
- Theorem 1, z is double used (consider directly define z as prox).
- Theorem 2, Assumption (B.1) is not numbered in the context. 
- Line 167, (V*, .. \hat{m}*) could have their definition in the main body. 

====
Post rebuttal:

The reviewer would like to thank the authors for addressing most of the concerns, and would like to raise the rating to a 6.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 

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. 

Quality: 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. 

Clarity: 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.  
Also, 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. 

Significance: 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.

The list of typos, misleading expressions, etc.:

%%

Line 44: r and g are assumed to be convex and thus they are continuous, implying that ``lower-semicontinuous'' assumption is unnecessary.

Lines 64,66: the mathematical characters become non-italic here.

Lines 190: I think id is the abbreviation of identity, but it is better to explain at the first appearance.

Eq. (27): It is better to define Z.

A sentence below Eq. (29):
"which the deterministic case in which this is fixed given"
Is this grammatically correct?

A sentence below Eq. (38):
Inserting this ansatz in eq. (34) allow us
->
Inserting this ansatz in eq. (34) allows us
(Similar error of missing the third-person singular -s are found many times)

etc.

%%

Some other suggestions and comments:

%%

Section 3: More explanation is desired for each concrete setting. 

Theorem 3: Universality of the linear model should be explained more deeply somewhere, not only by stating the theorem. 
About 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. 
%%

limitations_and_societal_impact: Not relevant to this paper.
review_title: null

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)