Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers kernel ridge regression (KRR) where the target is assumed to be invariant with the actions of a compact group. 
The authors show a reduced generalisation error for the feature-averaged version of the KRR estimator, proving the benefit of incorporating invariant features. 

main_review: To my knowledge, this is a novel quantitative result on KRR with invariant features. 
The authors show a strictly positive generalisation gap (test error difference) between the vanilla KRR estimator and its invariant version (realised by posthoc symmetrisation with respect to the group); it is a finite-sample lower bound expressed with kernel and RKHS quantities. 
The paper provides rigorous insights into the learning problem, and auxiliary results that contain an interesting interplay between RKHSs and invariance; therefore, I am in favour of its acceptance. 

There is one minor negative point that contributes to my score: the use of Fubini's theorem in Theorem 5 (L247). 
The integrated is not necessarily non-negative and Eq. (5) does not seem to suffice. We should be able to prove the $L_2(\mathcal{X} \times \mathcal{X}, \mu \otimes \mu)$-convergence of the finite sum kernel to $j^{\perp}$. Other uses such as the display below L256 can also be replaced with different techniques such as the monotone convergence theorem. If these are fixed, I can confidently support the technical results in the paper and raise my score. 


### Minor comments:
* Typos: RHKS, Reisz 
* Reference for Lemma 2. The result in the cited paper concerns equivariant functions. Is this reference okay?
* L232: Typo, $\mathbb{E}[\xi_i^2]=0$. 
* You might want to replace the symbol for the operator norm in the supplementary, as it can be read as the Frobenius norm. 
* It might be good if some properties of $j(x, y)$ such as the boundedness are mentioned for later results.
* It would also be great if the authors could provide analysis for the symmetrised KRR when it is approximated by finite samples (from the Haar measure); orbit averaging appears to be intractable in practice. 
* Lemma C.3: The first line in the proof should mention that a and b are defined as Bochner integrals; and therefore they are weakly integrable. 
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: Paper presents a theoretical result extending [8] showing a strict generalization benefit for invariant/equivariant models for kernel ridge regression. Presented results (Theorem 8) is novel and interesting and shows addition of feature invariance provides strictly better generalization in terms of effective dimension of H_A.
main_review: Paper addresses the idea of how incorporating model invariance provides stricter benefit in terms of generalization.  It only addresses the case for kernalized ridge regression with square loss but the insights are helpful for a broad understanding.  

Idea presented is a theoretical result so does not shed more insight on choice of invariance for problem of computation of effective dimension dim(H_A) that can inform practice.

Paper seems to be technically sounds with ideas very well laid out leading to the final results Theorem 8.
limitations_and_societal_impact: Paper addresses limitations of the proposed results clearly in Section 2. There is no analysis needed for societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors present a theoretical generalization gap based on the invariance incorporated by the kernel. An orbit-averaged functional is defined with a set of invariant transformations G on data to produce an operator which maps a function to another function that averages the functions of the transformed data. The functional is used as the projection operator to produce the set of orthogonal functions to the invariant functions, and the generalization gap has been derived for kernel ridge regression using the effective dimensionality of those orthogonal functions. 
main_review: The paper shows an interesting theoretical effect of incorporating invariances on the reduction of generalization gap. Introducing the notion of effective dimensionality of kernels and its usage in bounding the reduction of generalization gap is a clear contribution of the paper.
My concern is that the presentation of the paper is quite abstract, and it is not clear how the theory can be applied to real applications. Unfortunately, the authors did not show any examples of invariance incorporation or experimental results, and it is hard to have an idea how well-known invariances can be formulated in terms of the equations in this paper. For example, the translation invariance in vision problem is a local property, and it depends on the point of interest. A single invariant transformation g\in G (e.g. one tangent vector) does not apply globally to all data (in the data manifold) violating the assumptions in lines 80-81. 
For the same reason, the condition for the target function f* in line 232 is too strong. In real problems, the invariance is a model that is not necessarily exist in true data-generating function or some invariances can be ignored by the model, so f* can be outside of (though can be close to) the invariant functions.
Also, the way to calculate the effective dimensionality in real problems is unclear. Given a kernel with invariance G, can the effective dimensionality be obtained?
All these questions arise because the authors did not present a concrete example and an experiment that confirms the theoretical derivation. Though the way to present the theoretical results is nice in this paper, the meaning of equations and its usefulness in real applications are limited.


limitations_and_societal_impact: 1. Invariances in many real problems depend on a particular datum, and they do not apply globally.

2. The target function f* is often outside the invariant function set.

3. The example should be provided for the calculation of the effective dimensionality for a given kernel and a invariance set.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proves a benefit, in terms of expected risk, of orbit-averaging the solution of kernel ridge regression (with respect to actions by a given compact group) compared to the original solution of kernel ridge regression. The extent of this benefit depends on the "effective dimension" of the space orthogonal to the space invariant to group action, as well as what the authors call "differences in bias". Finally, the authors demonstrate a simple example in which the input domain is the unit sphere in d-dimensions, and the kernel is linear. The contributions are entirely theoretical. 
main_review: My review is based on the supplementary material, because it seemed to me that the submission is simply a condensed version of the supplementary material. 

My overall impression is overwhelmingly positive. It is written in good English, the structure of the paper is solid and I really appreciated the superb clarity of mathematical exposition, which is oftentimes lacking in machine learning papers. I have tried my best to do it justice with the review, although I must admit I was not familiar with the literature of group invariant models before reading this submission. I thank the authors for their work, and I apologise in advance for any misunderstandings on my part. 

[8] is important prior work, where Elesedy and Zaidi proved benefit in terms of expected risk of orbit-averaged linear solutions. This work extends their contributions by proving an analogous result for kernel ridge regression, which is a much more flexible regression technique. I tried to read up [8] as much as possible, and even though I am not familiar with the related work that came before [8], I am prepared to believe that no prior work proved the kind of generalisation benefits that [8] and the current submission provide, and if that is the case, I deem the contributions significant. I checked the proofs as much as I can, and although of course there may be things that I have missed, they look correct. Often in learning theory papers for RKHS-based regression, the input space is constrained to be compact, but I appreciated that they relaxed this assumption. I would have liked to give a higher overall rating than a 7, but I can't help thinking that the main original contributions came in [8], and this is rather an extension of that. But I do very much value the extension to kernel ridge regression. 

I foresee that some reviewers will not like the fact that no experiments have been conducted to validate the results, but I am prepared to argue that the theoretical contributions suffice for acceptance. 

Some additional points / questions:

1) I'm a bit confused by the paragraph of lines 55-59. It says that Delta(f,f')>0 then f has strictly better test performance at f', but shouldn't it be the other way round, or "larger test error than"? This would be consistent with the rest of the paragraph, and also with the definition of Delta(f,f') in Section 4.2. 
2) Just a matter of exposition - it would be good if the displayed equation after line 105 had a full stop. 
3) On line 388, it is currently written iota:L_2(X,mu) -> H, which I imagine is not what the authors intended. In the proof of Lemma C.1, iota:H->L_2(X,mu) is correctly written. 
4) Lines 259-260 need to be re-written. 
5) In the displayed equations after lines 261 and 262, M needs to be M_k. 
6) In the displayed equations after line 290, the first and second lines on the right-hand side seem identical. 
7) The term “effective dimension” was coined in [Optimal Rates for the Regularised Least-Squares Algorithm, Caponnetto and de Vito, 2007]; however, in that paper, it depends on the regulariser lambda (rho, in your notation) of kernel ridge regression, and is defined, if I’m not mistaken, as the trace of (T+lambda)^{-1}T, where T, unlike your T_k, is the operator H -> H. So the order of composing the inclusion of H into L_2 and its adjoint is opposite to yours. 
From my limited knowledge and expertise, I think there is a case to be made for both; on the one hand, any kind of “dimension” of a space should be an inherent property of itself, and shouldn’t depend on the regulariser used, which is a case for your definition, but then again, if the dimension is to take into account the functions considered for kernel ridge regression, then it does make sense that the amount of regularisation plays a role. I would be extremely grateful if the authors could comment on this difference, and also the fact that you consider the trace of T_k^2, whereas they consider (T+lambda)^{-1}T. I think it might still be worth using a different terminology, or at the very least mention the existing usage and explain how your definition is different. 
8) I am more familiar with the kernel literature, and I know that the assumptions that you placed on the kernels are not restrictive. However, I am not familiar with the group invariance literature, and I would be very grateful if you could just mention whether or not the assumptions you placed on G are not restrictive (e.g. that it is compact). Also, the assumption that the measure is supported on the whole of X seems crucial, since it is required for Lemma C.1 and thence the rest of the results, but this loses a little bit of generality. 
limitations_and_societal_impact: The authors have discussed some limitations of their work, and possible directions for future research. 
The authors did not discuss societal impact, but I do not deem it necessary, given the theoretical nature of the work.
review_title: null

Meta-review: The paper provides theoretical work on the invariance of positive definite kernels and RKHS.  The obtained results are novel and of high theoretical significance.  On the other hand, its practical meaning is not very clear in this paper.   Overall, the theoretical development on the invariance of kernel/RKHS is significant enough and applicable to a variety of problems in the future.  We judge the work is worth presented in NeurIPS.  
Decision: Accept (Poster)