Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the generalization capabilities in kernel regression in the particular case where the distribution of training and testing is different. 
They quantify the mismatch between distributions for a given kernel and show that its a key determinant of generalization performance. 
They also propose how to optimize training and test distributions for a given data budget to find the best and worst case generalizations under a shift.
The authors investigate how in real data this hypothesis can be confirmed and show how learning rate with training set size changes with training distribution and cases where choosing it different than test distribution helps.
Their approach provides analytical tool for having more precise predictions.
main_review: It is a well-written and well-motivated paper. The problem of out-of-distribution generalization of neural models is a well-studied area and this work provides valuable insight in this area.    

Questions for the authors:

- The effectiveness of this approach is in knowing what the test distribution look like. What do you think about the potential of the analysis you did for when the test distribution can be estimated but is not known? In NLP problems for instance, the distribution of output
 language can be to an extent estimated.

- You show on MNIST dataset that the beneficial measure has lower generalization error while the adversarial measure has higher generalization error than the matched case. You use gradient ascent to find adversarial test measures. Does the type of adversarial samples (as opposed to less or more challenging/natural cases) influence the conclusion?

- What are the limitations (computation-wise) of this approach? How well do you think it's adaptable for large (real world) datasets. In case of machine translation for example, the training data can be a couple of million samples.

limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the out-of-distribution generalization error in kernel ridge regression (KRR) with any choice of regularization parameter $\lambda$ (including the case of interpolation), and as a general functional of the training and test distributions using the replica method in statistical physics. In addition,

-- they provide explicit closed-form expressions for the case of the linear model.

-- using the neural tangent kernel (NTK), they empirically evaluate their asymptotic formulas on modified samples of the MNIST test dataset to provide best-case training distributions, which can sometimes be different from the one that exactly matches.
main_review: The setting of transfer learning in kernel ridge regression is well-motivated and an important topic for research, especially in the context of the recent discovery of the NTK regime, which increases the relevance of kernel analyses in the context of modern ML. To the best of my knowledge, I have not seen precise asymptotic analyses of the transfer learning setting in KRR, and so I think this paper will be of interest to the theoretical ML community. The experiments done on MNIST with a 3-layer NTK are also interesting.

The paper would benefit from a more detailed comparison with the results already derived for the case where the training and test distributions are the same (e.g. citation [14] in the submission), and a discussion of the additional technical non-trivialities that arise in the analysis for the out-of-distribution case. Additionally, are there settings that are more general than the linear model where the expressions could potentially be made closed-form?
limitations_and_societal_impact: Yes, the authors have adequately addressed the limitations and potential negative societal impacts of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper applies the so-called "replica method" to tackle the generalization issue for kernel regression where there is a distribution shift between training data and testing data. It presents the derivation of kernel regression by using an alternative perspective on RKHS functions. Empirical studies on real datasets including MNIST have been shown. Discussions with the neural tangent kernel are presented.

Despite the interesting idea, the clarity of the paper can be improved to better appreciate the ideas and presentations. Moreover, the significance and impact of the work is also unclear, making it difficult to appreciate the advancement from existing results.
main_review: The paper studies the generalization issue for kernel regression. It presents an alternative perspective on deriving the objectives as well as interpret the kernel.

Despite the interesting idea, the criticism on the paper is associated with the clarity of presentation and significance of impact to the community.

It is not easy to read and follow the ideas presented in the paper as it is not self-contained. Even after reading the appendix, it is still unclear what is "replica method" and how is this useful to improve the overall learning scheme for kernel regression. 
more ideas are introduced in the Experimental section which induces more doubts and concerns. For instance, the beneficial and adversarial matrix in Fig 1 b): is this related to adversarial attack during learning procedure? 
Fig 3 b) shows the double descent phenomenon while not clearly explained.

In terms of significance and impact, it is unclear how the overall setting improves the kernel regression when testing on cases with distribution shift. The regularised kernel-based regression objective is based on scalar-valued RKHS functions and squared loss. How does this approach objective different from learning a conditional mean embedding? With conditional mean embedding, distribution shift can be easily incorporated. Results on this approach have been studied in 
 Grunewalder et, al. "Conditional mean embeddings as regressors"
Moreover, Fukumizu et,al. "Kernel Bayes rule" is another useful reference in terms of manipulating conditional distributions and joint distribution in the kernel setting. 
I am curious how the proposed approach compares with the existing ones.
In addition, is the result only valid for energy-based models like Gibbs distribution presented? it will be nice to discuss what may happen beyond. 

minor issues:

- \langle \rangle are used for both RKHS norm (e.g. Eq(1)) as well as the norm w.r.t. distribution/samples (e.g. Eq(2)) which are incoherent.

- sample size notation P is non-conventional and especially can be confusing when distribution p(x) is used.

- in Eq.(6), is Z the normalizer/partition function? otherwise, function O can be better explained and notated.
limitations_and_societal_impact: The limitation is mainly the clarity of presentation and bringing up the significance/advancement from existing work (detailed in the main review). 

Social impact is not an issue here but more discussions on how the distribution shift can be connected to social issues, such as fairness machine learning or privacy-preserving concerns in machine learning can be useful.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes asymptotic convergence results of kernel regression in the out-of-distribution setting via replica tricks. Some findings and examples are given. 
main_review: I’m not an expert on statistical mechanics/physics though I know replica methods used in the machine learning community. I haven't checked the proofs in the appendix and will just trust authors in the correctness of the proof. 

**Main issues:**

Nevertheless, this paper corresponds to eigenvalue decomposition for $R^M \times R^M$ matrix (with infinite $M$ and infinite feature dimension $D$) is still questionable to me. 
As indicated by random matrix theory, matrix in spectral norm in high dimensions is quite different from the low-dimensional case. Besides, this paper does not strictly distinguish the difference between the integral operator and kernel matrix. In fact, such difference would be non-negligible: “The large eigenvalues of kernel matrix approximate the corresponding eigenvalues of kernel operator very well. The small eigenvalues are away from the smallest eigenvalues of kernel operator, but still relatively large.” Refer to the following paper:

*Ma, C., Wu, L. and Weinan, E., 2020. The slow deterioration of the generalization error of the random feature model. Mathematical and Scientific Machine Learning, 2020.*

Proposition 1 is not enough and I suggest the authors to provide further analysis. For example, quantitative analysis/discuss the gap between the training/test distribution via some metric, e.g., MMD or total variance norm, and then study how such gap effects the third term in Eq. (7). It would be nice to provide error bounds in probability.

In Section 4, the authors consider linear regression with the linear kernel for Gaussian data, and thus the kernel eigenvalue equation can be solved exactly. This is a common way in replica methods. But this appears a little “overclaim” on application to any data, any kernel, any distribution throughout the paper.


**Minor issues:**

All kernel eigenvalues are assumed to be non-zero, which means the RKHS is dense in L^2(X). This paper assumes the target function \bar{f} lies in a RKHS, which is fair and standard in learning theory. In this case, if my understanding was right, “N” should be “M” in line 86?

It would be better if the definitions of some notations and expressions follow the machine learning community. For example, “generalization error” -> “excess risk” in line 58. They are in fact different and have different meanings in learning theory. Besides, I suggest the authors to add “P” in the loss term in Eq.(1) as the empirical error:
$$\frac{1}{2P} \sum_{\mu=1}^P (f(x^\mu) - y)^2 + \lambda || f ||_{\mathcal{H}}^2$$

This setting is common in statistical learning theory though [14,15] is without $P$. 
With $P$, it is natural to assume that $\lambda = O(P^{-a})$ with $a \in (0,1]$, refer to

*Cucker, Felipe, and Ding Xuan Zhou. Learning theory: an approximation theory viewpoint. Vol. 24. Cambridge University Press, 2007.*


Typo:

The test propability meansure should be $\tilde{p}(x)$ in line 135.

The transpose operation is missing for $\Phi$ in Eq. (SI.4).

limitations_and_societal_impact: it's enough.
review_title: null

Meta-review: This paper gives a detailed study for out-of-distribution generalization in kernel regression, going substantially beyond known results in this particular problem, which are both of independent interest and also may help serve as a baseline of understanding for similar results in other methods. Some concerns did come up in the reviews both in terms of the framing – which seem to be generally resolved in the discussion phase, though please make sure that these are reflected in the final version of the paper – and in particular for the style of result in Proposition 1, which is worth thinking a little further about. Overall, though, this will be a nice contribution to the conference.
Decision: Accept (Poster)