Provably Strict Generalisation Benefit for Invariance in Kernel Methods
Authors: Bryn Elesedy
Venue: NeurIPS 2021 Poster (2021)
Keywords: generalization
kernel methods
invariance
equivariance
symmetry
geometric deep learning
statistical learning theory

Abstract: It is a commonly held belief that enforcing invariance improves generalisation. Although this approach enjoys widespread popularity, it is only very recently that a rigorous theoretical demonstration of this benefit has been established. In this work we build on the function space perspective of Elesedy and Zaidi [8] to derive a strictly non-zero generalisation benefit of incorporating invariance in kernel ridge regression when the target is invariant to the action of a compact group. We study invariance enforced by feature averaging and find that generalisation is governed by a notion of effective dimension that arises from the interplay between the kernel and the group. In building towards this result, we find that the action of the group induces an orthogonal decomposition of both the reproducing kernel Hilbert space and its kernel, which may be of interest in its own right.

Provably Strict Generalisation Benefit for Invariance in Kernel Methods
Bryn Elesedy University of Oxford bryn@robots ox ac
Abstract
It is a commonly held belief that enforcing invariance improves generalisation. Although this approach enjoys widespread popularity, it is only very recently that a rigorous theoretical demonstration of this benefit has been established. In this work we build the function space perspective of Elesedy and Zaidi [8] to derive a strictly zero generalisation benefit of incorporating invariance in kernel ridge regression when the target invariant to the action of compact group. We study invariance enforced by feature averaging and find that generalisation is governed by notion of effective dimension that arises from the interplay between the kernel and the group. In building towards this result, we find that the action of the group induces an orthogonal decomposition of both the reproducing kernel Hilbert space and its kernel, which may be of interest in its own right.
Introduction
Recently, there has been significant interest in models that invariant to the action of a group on their inputs. It is believed that engineering models in this way improves sample efficiency and generalisation. Intuitively, a task has an invariance, then a model that is constructed be invariant ahead of time should require fewer examples to generalise than one that must learn to be invariant. Indeed, there are many application domains, such as fundamental physies or medical imaging, in which the invariance is known priori [29, 32). Although this intuition is certainly not new (e.g. [33]), has inspired much recent work (for instance, see [36, 15]).
However, while implementations and practical applications abound, until very recently a rigorous theoretical justification for invariance was missing. As pointed out in [8], many prior works such as [28, 24] provide only worst-case guarantees on the performance of invariant algorithms. It follows that these results do not rule the possibility of modern training algorithms automatically favouring invariant models, irrespective of the choice of architecture. Steps towards a more concrete theory of the benefit of invariance have been taken by [8, 20] and our work is a continuation along the path set by [8].
In this work we provide precise characterisation of the generalisation benefit of invariance in kernel ridge regression. In contrast to [28, 24], this proves a provably strict generalisation benefit for invariant, feature-averaged models. deriving this result, we provide insights into the structure of reproducing kernel Hilbert spaces in relation to invariant functions that we believe will be useful for analysing invariance in other kernel algorithms.
The use of feature averaging to produce invariant predictors enjoys both theoretical and practical success [17, 9]. For the purposes of this work, feature averaging is defined as training model as normal (according to any algorithm) and then transforming the learned model to be invariant. This transformation is done by orbit-averaging, which means projecting the model the space of invariant functions using the operator O introduced in Section 2.3.
Kernel methods have long been mainstay of machine learning (see [30, Section 4.7] for brief historical overview). Kernels can be viewed as mapping the input data into a potentially infinite
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

dimensional feature space, which allows for analytically tractable inference with non-linear predictors. While modern machine learning practice is dominated by neural networks, kernels remain at the core of much of modern theory. The most notable instance of this is the theory surrounding the neural tangent kernel [11], which states that the functions realised by an infinitely wide neural network belong to a reproducing kernel Hilbert space (RKHS) with kernel determined by the network architecture. This relation has led to many results on the theory of optimisation and generalisation of wide neural networks (e.g. [14, 3J) In the same vein, via the NTK, we believe the results of this paper can be extended to study wide, invariant neural networks.
1.1 Summary of Contributions
This paper builds towards precise characterisation of the benefit of incorporating invariance in kernel ridge regression by feature averaging.
Lemma 3, given in Section 3, forms the basis of work, showing that the action of the group G on the input space induces an orthogonal decomposition of the RKHS H as
H H ( Hi
where each term is an RKHS and H. consists of all of the invariant functions in H. We stress that, while the main results of this paper concern kernel ridge regression, Lemma 3 holds regardless of training algorithm and could be used to explore invariance in other kernel methods.
Our main results are given in Section 4 and outline them here. We define the generalisation gap f') for two predictors J' as the difference in their test errors. If (ff. > O then f' has strictly better test performance than f. Theorem describes ff) for being the solution to kernel ridge regression and f' its invariant (feature averaged) version and shows that it is positive when the target is invariant.
More specifically, ly, let X ~ I where μ is G-invariant and Y = fx)) + with f G-invariant and Elg] 0, [ a² cc. Let f be the solution to kernel ridge regression with kernel k and regularisation parameter P >> 0 on n i.i.d. training examples [(X,, Y2) ~ (X, i 1,..., n) and let f' be its feature averaged version. Our main result, Theorem says that
0² diman((H))) +
E E[A(f.)))
(VTM² + p/ n22
where M₁ sup, k(x,,) < 00, 2 describes the approximation errors and dimea(HH)) is the effective dimension of the RKHS H. For an RKHS H with kernel k the effective dimension is defined by
dim (7) k(x, u)² du(()) du(v).
where X = supp μ. We return to this quantity at various points in the paper.
It is important to note that the use of the feature averaged predictor f' as comparator is without loss of generality. Any other predictor f that has test risk not larger than f' would satisfy the above bound, simply because this means A( [ f") 2 0 so A(f, f") A + A(f, A(f,
Finally, for intuition, in Theorem we specialise Theorem 5 to the linear setting and compute the bound exactly. Assumptions and technical conditions are given in Section 2 along with outline of the idcas of Elesedy and Zaidi [8] on which we build. Related works are discussed in Section 5.
2 Background and Preliminaries
In this section we provide a brief introduction to reproducing kernel Hilbert spaces (RKHS) and the ideas we borrow from Elesedy and Zaidi [8]. Thhoouhhout this paper, H. with be RKHS with kernel k. In Section 2.2 we state some topological and measurability assumptions that are needed for our proofs. These conditions are benign and the reader not interested in technicalities need take from Section 2.2 only that is G-invariant and that the kernel k is bounded and satisfies Eq, (1). We defer proofs to the Supplementary Material.
'To be completely clear: if, for instance, so happens that projecting the RKHS onto space of invariant predictors before doing KRR gives lower test risk than projecting afterwards (what we are calling feature averaging), then result applies in that case

---

2.1 RKHS Basics
A Hilbert space is an inner product space that is complete with respect to the norm topology induced by the inner product. A reproducing kernel Hilbert space (RKHS) H is Hilbert space of real functions f X' + IR on which the evaluation functional 82 H + I with 6g [ = f(x) is continuous Vd E X, or, equivalently is bounded operator. The Riesz. Representation Theorem tells that there is a unique function kg H. such that 8=[f]= = (k2, f)x for any f E H. where (: : H. H + IR the inner product on H. We identify the function k: X x X' + E. with k(x, y) (k ky) H as the reproducing kernel of H. Using the inner product representation, one can see that k is positive-definite and symmetric. Conversely, the Moore-Arone Arons-anon Theorem shows that for any positive-definte and symmetric function k, there is a unique RKHS with reproducing kernel k. In addition, any Hilbert space admitting a reproducing kernel is an RKHS. Finally, another characterisation of H is as the completion of the set of linear combinations of the form fe(x) > cyk(ar, 24)) for C12 ..... E IR and ,...... Fn E X. For (many) more details, see [30, Chapter 4).
2.2 Technical Setup and Assumptions
Input Space, Group and Measure Let & be compact", second countable, Hausdorfi topological group with Haar measure À (see [12, Theorem 2.27J). Let X' be non-empty Polish space admitting a finite, G-invariant Borel measure μr, with supp μr X. We normalise μ²(²) = X = 1, the latter possible because À is Radon measure. We assume that & has measurable action on X' that we will write as gz for E G. I E X. A measurable action is one such that the map g 9 x X' - X (A @ pt) meeasuaabee A function f X E is G-invariant if f(gz) f(x) Vr E X Vg E G. Similarly, measure ls X' is G-invariant if Vg E 9 and any p-measurable B C X' the pushforward of j by the action of 9 equals μr, i.e. (g.p) (B) = u(B), This means that if X j then gX ~ f Vg E G. We will make use of the fact that the Haar measure is G-invariant when G acts on itself by either left or right multiplication, the latter holding because G is compact. Up to normalisation, is the unique measure on G with this property.
The Kernel and the RKHS Let l: X' x X + H be measurable kernel with RKHS H such that k(,,)) x) : X + R is continuous for any x E X. Assume that supzex k( x) = Ma < co and note that this implies that k is bounded since
k(x,, x²) = (kas ) S 1/ = v A(I, x) ((())) k(x',x')== S Mr.
Every f E H is y-measurable, bounded and continuous by [30, Lemmas 4.24 and 4.28] and in addition H. is separable using [30, Lemma 4.33]. These conditions allow the application of [30, Theorem 4.26] to relate H to L2(X', 11) in the proofs building towards Lemma 3, given in the Supplementary Material. We assume that the kernel satisfies, for all x. y E X.
1 ((gn = -/ ((a.99) [(LO..0)) dX(g).
(1)
Equation (1) is our main assumption and we will make frequent use of it. For Eq. (I) to hold, it is sufficient to have k(gx, y) equal to k(zz, gu) k(xx, "yy, "y). where the latter uses compactness (hence unimodularity) of G to change variables g <+ g -1 Highlighting two special cases: any inner product kemel k(r, xx) (z, x²)) such that the action of G is unitary with respect to (:-)) satisfies Eq. (1), as does any stationary kernel k(2, x') = R( [|æ z'll) with norm that is preserved by G in the sense that l| gz' || || æ'Il for any g G. x' X. If the norm/inner product is Euclidean, then any orthogonal representation of G will have this property.
2.3 Invariance from Function Space Perspective
Given function f X + R we can define corresponding orbit-averaged function Of X I with values
of(z)= = [ f(gz) dX(g).
'The set of compact groups covers almost all invariances in machine learning. including all finite groups (such as permutations or reflections). many continuous groups such as rotations translations on bounded domain (e.g. an image) and combinations thereof.
3 An orthogonal representation of G on Rd is an action of & via orthogonal matrices, i.e. homomorpishm
g + Od).
3

---

Of will exist whenever f is y-measurable. Note that O is a linear operator and, from the invariance of X, Of is always G-invariant. Interestingly, f G-invariant only if f Of Elesedy and Zaidi [8] use these observations to characterise invariant functions and study their generalisation properties. In short, this work extends these insights to kernel methods. Along the way, we will make frequent use of the following (well known) facts about O.
Lemma 1 ([8, Propositions 24 and 25]). A function f is G-invariant if and only if Of f. This implies that O is projection operator, can have only two eigenvalues 0 and 1.
Lemma 2 ([S, Lemma IJ. O (2 (d) - [22(X, is well-defined and self-adjoint. Hence, (2 n)) has the orthogonal decomposition
L2(X, 1b) S + A
where S = ( E (2),,,)) : is G invariant) and A {s E (2( 05 03.
The meaning of Lemma that any f E [z) has (unique) decomposition f f= f where f = =f is G-invariant and Of = 0. A noteworthy consequence of this setup, as discussed in [8], is a provably non-negative generalisation benefit for feature averaging. In particular, for any predictor f E La(X, n)) if the target f E L2 p.) is G-invariant then the test error R(J)
Ex-,((((X) - (X))* satisfies
R(f) R(f) = 1f
L2(X,,) 1 2 0.
The same holds if the target is corrupted by independent, zero mean (additive) noise. 4
3 Induced Structure of H
In this section present Lemma which is an analog of Lemma 2 for RKHSs. Lemma shows that for any compact group G and RKHS H. if the kernel for HH satisfies the assumptions in Section 2.2, then H. can be viewed being built from two orthogonal RKHSs, one consisting of invariant functions and another of those that vanish when averaged over G. Later in the paper, this decomposition will allow us to analyse the generalisation benefit of invariant predictors.
It may seem at first glance that Lemma 3 should follow immediately from Lemma 2, but this is not the case. First, it not obvious that for any f E H. its orbit averaged version Of is also in H. Moreover, in contrast with L2 (X', p.), an explicit form for the inner product on H. is not immediate, which means that some work is needed to check that O is self-adjoint on H. These are important requirements for the proofs of both Lemmas 2 and 3 and we establish them, along with O being continuous on H, in the Supplementary Material. The assumption that the kernel satisfies Eq. (1) plays a central role.
Lemma 3. H. admits the orthogonal decomposition
# = H Φ> H.
where H ( E H f is G-invariant) and H. E Os 0). Moreover, H is an RKHS
with kernel
T(x,V) v) = 1
dA(g)
and H. is an RKHS with kernel
k- 1+(z, v) = k(æ, v) - T(x.vl)
Finally, le is G-invariant in both arguments.
As stated earlier, the perspective provided by Lemma will support our analysis of generalisation. Just as with Lemma 2, Lemma 3 says that any f E 7 can be written as f = f + f where f is G G-invariant and O 0 with {f. >' = 0. As an aside, Ie happens to qualify as Haar Integration Kernel, concept introduced by Haasdonk, Vossen, and Burkhardt [10]. We will see that notion of effective dimension of the RKHS H. with kernel k- governs the generalisation gap between an arbitrary predictor f and its invariant version Of. This effective dimension arises from the spectral theory of an integral operator related to k which we develop in the next section.
'The result [8, Lemma 1] is given for equivariance, of which invariance is special case.

---

3.1 Spectral Representation and Effective Dimension
In this section we consider the spectrum of an integral operator related to the kernel k. This analysis will ultimately allow to define notion of effective dimension of H. that we will later see is important to the generalisation of invariant predictors. While the integral operator setup is standard, the use of this technique to identify effective dimension of H. is novel.
Define the integral operator Sk
L2(X, 14) - H by
Sxf(x) = / k( x (f(a')
One way of viewing things that S₁ assigns to every element in L2(X, ()) a function in H. On the other hand, every / E H. is bounded has ||]llla((x,)) co and belongs of L2 (2 μ). We write H L2(X, μ)) for the inclusion map that sends f to the element of L2(X, (X, μi) that contains f. the Supplementary Material we show that is injective, so any element of L2(X, uu) contains at most one f 7..
element
One can define T& : Lg(X, (4) + L,((X,, μ)) by co Sg. and [30, Theorem 4.27] says that Tę is compact, positive, self-adjoint and trace-class. In addition, L2(X. p4) is separable by [7. Proposition 3.4.5], because X' is Polish and is a Borel measure, so has a countable orthonormal basis. Hence, by the Spectral Theorem, there exists countable orthonormal basis {ē:} for L2(X, μ)) such that The: = X₂ē; where A 2 X2 2 ... 2 0 are the eigenvalues of Tg. Moreover, since is injective, for each of the for which X; > 0 there is unique e H such that (e; é and Sg4; X,e.
Now, since th2 E L2 p)) we have
dkiz = Z(kko Ei) = ((She)(o)E = E (ee(())e.
From now on we permit ourself to drop the to reduce clutter. We use the above to define
j(z, = (ka, ky) Lx(,,))) 7(x, v) (ka, ky) (2(x,,)) and j'(x, 9) (ki La
These quantities will appear again in our analysis of the generalisation of invariant kernel methods. Indeed, we will see later in this section that [Xj+ (X, X)] is a type of effective dimension of Hi. Following Eq. (2), one finds the series representations given below in Lemma 4.
The reader may have noticed that our setup is very similar to the one provided by Mercer's 's theorem. However, we do not assume compactness of and so the classical form of Mercer's Theorem does not apply. This aspect of our work is feature, rather than a bug: the loosening of the compactness condition allows application to common settings such X' R For generalisations of Mercer's Theorem see [31] and references therein.
Lemma 4. We have
j Furthermore, let Oe: and oj = Ea then
j(x,y) = E ((er(w)))()), j(0,y) Σ (((()))) and j' j'(x,y)= Σ Xfe
Finally, the function everywhere.
Σ,
X&e 2 o : X X + R with values (x, + Σ, (22(()) vanishes
Before turning to generalisation, we describe how the above quantities can be used to define measure effective dimension. We define
dimen (H) E[j(X, X))
where X μ.. Applying Fubini's theorem, find
dim (H) = Σ X² EX), Σ 1e Σ
(3)
The series converges by the comparison test because X 0 and Σ, A Tr(Tis) (using Lidskii's 's theorem) because T3 is trace-class. We have dim (H) Tr(TT) and we can think of this
5

---

(very informally) as taking (2 μ1), pushing it through 7. twice using Tę and then measuring its size. Now because j = + we get
dimen = (H) + dimee(HH.)
with
dH = Σ X 2 12 = Th(T)) == Tr)(())))))))))))
where é ce Again, very informally, this can be thought of as pushing L2 (X' μ)) through Hi twice and measuring the size of the output. the next section we will consider the generalisation of kernel ridge regression and find that dim.r(H..) plays critical role.
4
Generalisation
In this section we apply the theory developed in Section 3 to study the impact of invariance on kernel ridge regression with an invariant target. We analyse the generalisation benefit feature averaging, finding strict benefit when the target is G-invariant.
4.1 Kernel Ridge Regression
Given input/output pairs {(z;, yi) = L.... .......) n where E X' and Vs R, kernel ridge regression (KRR) returns predictor that solves the optimisation problem
argmin C(J) fEH
where C()= (((a)) - vi)²
and >> 0 is the regularisation parameter. KRR can be thought of as performing ridge regression in possibly infinite dimensional feature space H. The representer theorem tells us that the solution to this problem is of the form f(z) = -E= 0:ki,, (x) where a E IR" solves
argmin oER=
{ Kall2 + pa' Ka),
(5)
Y R" is the standard row-stacking of the training outputs with Y, y/ and K is the kernel Gram matrix with Kg = 2g)) We consider solutions of the form a = (K' + pf)- which results in the predictor
f(x) k. (K + p
where he (X) R" is the vector with components (X):;;; (x;).. We will compare the generalisation performance of this predictor with that of its averaged version
= k. (X)
p e H.
To do this we look at the generalisation gap.
4.2 Generalisation Gap
The generalisation gap is quantity that compares the expected test performances of two predictors on a given task. Given a probability distribution PP, data (X, Y) ~ and loss function I defining a supervised learning task, we define the generalisation gap between predictors f and f to be
AJ, f')
where the expectations are conditional on the given realisations of f, f' if the predictors are random.
In this paper consider ((a, b) (a-b)a b)2 the squared-erro loss and we will assume = =f*(X)++ + for some target function f" where is has mean 0, finite variance and is independent of x. In this case, the generalisation gap reduces
(ff f')
Clearly, if ((F, > 0 then we expect strictly better test performance from f' than f.
When K is positive definite matrix this will be the only solution. If K is singular then 3e _ with E,, Kygc, 11,, cakz, 11 = E. Cıka, is identically and Vf 7. we get Σ, (x,) 0 (see [18, Section 4.6.2J). Clearly, this can't 't happen if H. is sufficiently expressive. In any case, the chosen a is the minimum Euclidean norm of all possible solutions.

---

4.3 Generalisation Benefit of Feature Averaging
We are now in a position to give our main result, which is a characterisation of the generalisation benefit of invariance in kernel methods. This is in some sense generalisation of [8, Theorem 6] and we will return to this comparison later. We emphasise that Theorem 5 holds under quite general conditions that cover many practical applications.
Theorem 5. Let the training data be {(x,, Y)) i I....,,, nn ii.d. with Y; (X;) + & where X; ~ μ. f L2(X, μ1) is G-invariant and bounded, and {E: each other and the {Xe). with Eig,] 0 and [B[ o² < oc. Let f = arginin Jew. C(J) be the solution to Eq. (4) and let f Of H be the result of applying feature averaging to f. then the generalisation gap with the squared-error loss satisfies
1,...,,7 nn are independent of
(X) x)] 0² of (H.)
f)
(VnMa + t./
where each term non-negative and
dim = Tr(T2) Tr((OT))²) = Ei = Σ 2a 12 20
is the effective dimension of Hh1
Theorem shows that feature averaging is provably beneficial in terms of generalisation if the mean of the target distribution is invariant. If H contains any functions that are not G-invariant then the lower bound is strictly positive. One might think that, given enough training examples, the solution f to Eq. (4) would learn to be G-invariant. Theorem 5 shows that this cannot happen unless the number of examples dominates the effective dimension of H.1
Recall the subspace in Lemma 2. The role of diment (H.,) mirrors that of dim A in [8, Theorem 6] and in the context of the theorem (linear models) A can be thought of as H_ when k is the linear kernel. In this sense Theorem is a generalisation of [8. Theorem 6]. It is for this reason that we believe that, although the constant Mj in the denominator is likely not optimal, the D(1/n) rate that matches [8] is tight. We leave more precise analysis of the constants future work.
The second term in the numerator can be interpreted as quantifying the differences in bias. One has by the definition of j², that
| (1)))((((x dp(x) du(y)
[X((X)
(6)
using (r v) fx k- 2h du(t). We also have the following proposition.
Proposition 6.
Jx (r)) du(x) / (v) (k(z, -k(,, u)2) du(x) du(y)
For intuition, we present simple special case of Theorem 5. In particular, the next result shows that Eq. (6) reduces to an approximation error that is reminiscent of the one in [8, Theorem 6) in a linear setting. For the rest of this section we find it helpful to refer to the action of G explicitly, writing o(g)x instead gr.
Theorem 7. Assume the setting and notation of Theorem 5. addition, let S be the unit d - 1 sphere and let f4 = Un).(X(). Let G act via an orthogonal representation & on A' and define the matrix + Jg ((g) dA(g). Let k(x,1) = x y be the linear kernel and suppose f*x) = 0 x for some / dRd Then the bound in Theorem 5 becomes
1
(L-101P d2
d dd
(d-
| 12)00 d2
E((f, f) (Vnn + p/vnz
2)
where ||= the Frobenius norm. The first term the parentheses is exactly (?..a(H.)) and the second term is exactly (x)
7

---

One can confirm that the generalisation gap cannot be negative in Theorem 7 usiin Jensen's 's inequality
| 10112=1 = - (6 (10
- f [1(G0))(aa))
J / Tr(((g) ((()) Tr(I)= = d
because the representation @ is orthgonal.
The matrix & in Theorem can be computed analytically for various G and in the linear setting describes the importance of the symmetry to the task. For instance, in the simple case that 9 = Sz the permutation group on elements and & is the natural representation in terms of permutation matrices, we have Φ 1 where 1 R is the vector of all 1s. In this case, since the target is assumed to be G-invariant, we must have = 11 for some t E R. Specifically, Theorem then asserts
(d 1) +
E E
d'd 2l
5 Related Work
Incorporating invariance into machine learning models is not new idea. The majority of modern applications concern neural networks, but previous works have used kernels [10, 22], support vector machines [25] and polynomial feature spaces [26, 27J. Indeed, early work also considered invariant neural networks [33], using methods that seem to have been rediscovered in [23]. Modern implementations include invariant/equivariia convolutional architectures [4, 6] that are inspired by concepts from mathematical physics and harmonic analysis [13, 5]. Some of these models even enjoy universal approximation properties [19, 35].
The earliest attempt at theoretical justification for invariance of which we are aware is [1], which roughly states that enforcing invariance cannot increase the VC dimension of a model. Anselmi et al. [2] and Mrouch, Voinea, and Poggio [21] propose heuristic arguments for improved sample complexity of invariant models. Sokolic et al. [28] build on the work of Xu and Mannor [34] obtain a generalisation bound for certain types of classifiers that are invariant to a finite set of transformations, while Sannai and Imaizumi [24] obtain bound for models that are invariant to finite permutation groups. The PAC Bayes formulation is considered in [16, 17].
The above works guarantee only a worst-case improvement and it was not until very recently that Elesedy and Zaidi [8] derived strict benefit for invariant/equivariant models. Our work is similar to [8] in that we provide a provably strict benefit, but differs in its application to kernels and RKHSs as opposed to linear models. We are careful to state that our setting does not directly reduce to that of [8. Theorem 6] for two reasons. First, [8. Theorem 6] considers G invariant linear models without regularisation. This may turn out to be accessible by a p + 0+ limit (the so called ridgeless limit) of Theorem 5. More importantly, linear regression is equivalent to kernel regression with the linear kernel. However, the linear kernel can be unbounded (e.g. on I), so does not meet our technical conditions in Section 2.2. We conjecture that the boundedness assumption on & can be removed, or at least with mild care weakened to hold p-almost-surely,
Also very recently, Mei, Misiakiewicz, and Montanari [20] analyse the generalisation benefit of invariance in kernels and random feature models. Our results differ from [20] some key aspects. First, Mei, Misiakiewicz, and Montanari [20] focus on kernel ridge regression with an invariant inner product kernel whereas we study symmetrised predictors from more general kernels. Second, they obtain expression for the generalisation error that is conditional on the training data and in terms of the projection of the predictor onto a space high degree polynomials, while we are able to integrate against the training data and express the generalisation benefit directly in terms of properties of the kernel and the group
6 Discussion
We have demonstrated a provably strict generalisation benefit for feature averaging in kernel ridge regression. In doing this we have leveraged an observation the structure of RKHSs under the action of compact groups. We believe that this observation is applicable to other kernel methods too.
There are many possibilities for future work. As we remarked in the introduction, there is an established connection between kernels and wide neural networks via the neural tangent kernel. Using this connection, generalisation properties of wide, invariant neural networks might be accessible
8

---

through the techniques of this paper. Another natural extension of this paper is to equivariant (sometimes called steerable) matrix valued kernels. Approximate invariance may be handled by adding an approximation term to the bound in our main result. Finally, the ideas of this paper should also be applicable to Gaussian processes.
A Acknowledgments and Disclosure of Funding
We thank Sheheryar Zaidi for many helpful discussions in the early stages of this project and Yee Whye Tch for suggesting the application of [8] to kernels. Additionally, thank Varun Kanade and Yee Whye Teh for advice and support throughout this and other projects. This work was supported in part by the UK EPSRC CDT in Autonomous Intelligent Machines and Systems (grant reference 5P/L015897/11.
References
[1] Yaser S Abu-Mostafa. "Hints and the VC dimension". In: Neural Computation 5.2 (1993).
pp. 278-288 (page 8).
[2] Fabio Anselmi et Unsupervised Learning of Invariant Representations Hierarchical Architectures. 2014. arXiv: 1311.4158 [cs. CV] (page 8).
[3] Sanjeev Arora al. Frinn-Gr Analysis of Optimization and Generalization for Overpa- rameterized Two-Layer Neural Networks". In: Proceedings of the 36th International Confer- ence on Machine Learming. Ed. by Kamalika Chaudhuri and Ruslan Salakhutdinov. Vol. 97. Proceedings of Machine Learning Research. PMLR, 2019, pp. 322-332. URL: http // proceedings. mlr. arres/v99/aroral//
html (page 2).
[4] Taco Cohen and Max Welling. "Group equivariant convolutional networks". In: International conference on machine learning. 2016, pp. 2990-2999 (page 8).
[5] Taco S Cohen, Mario Geiger, and Maurice Weiler. "A general theory of equivariant cnns on homogeneous spaces". In: Advances in Neural Information Processing Systems. 2019, pp. 9145-9155 (page 8).
[6]
Taco S Cohen et al. "Spherical enns". In: arXiv preprint arXiv:/801.10133 (2018) (page 8).
[7]
Donald L Cohn. Measure Theory. 2nd ed. Springer, 2013 (page 5).
[8] Bryn Elesedy and Sheheryar Zaidi. "Provably Strict Generalisation Benefit for Equivari- ant Models". In: Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 202 Virtual Event. Ed. by Marina Meila and Tong Zhang. Vol. 139.
Proceedings of Machine Learning Research. PMLR, 2021, pp. 2959-2969, URL: http / //proceedings... mlr. press/v139 //1///13/////// elesedy21a. html (pages 1, 2. 4, 7-9).
[9] Adam Foster, Rattana Pukdee, and Tom Rainforth. "Improving Transformation Invariance in Contrastive Representation Learning". In: arXiv preprint arXiv:2010.09::
(2020) (page 1).
[10] B. Haasdonk, A. Vossen, and H. Burkhardt. "Invariance in Kernel Methods by Haar Integration Kernels". In: SCIA 2005, Scandinavian Conference on Image Analysis. Springer-Vette 2005, pp. 841-851 (pages 4, 8).
[11] Arthur Jacot, Franck Gabriel, and Clément Hongler. "Neural tangent kernel: Convergence and generalization neural networks". In: Advances in neural information processing systems.
2018. pp. 8571-8580 (page 2).
[12] Olav Kallenberg. Foundations of modern probability. Springer Science & Business Media, 2006 (page 3).
[13] Risi Kondor and Shubhendu Trivedi. "On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups". In: International Conference Machine Learning. 2018, pp. 2747-2755 (page 8).
[14] Jaehoon Lee al. "Wide neural networks of any depth evolve as linear models under gradi- ent descent". In: Advances in neural information processing systems. 2019, pp. 8572-8583 (page 2).
[15] Juho Lee et al. "Set Transformer: A Framework for Attention-basel Neural Networks". In: Proceedings of the 36th International Conference on Machine Learning. Ed. by Kamalika Chaudhuri and Ruslan Salakhutdinov. Vol. 97. Proceedings of Machine Learning Research. PMLR, 2019, pp. 3744-3753. URL: http: httt:::/ppooceeinnngeeee mlr, press/ v97 #97/lee10 19d. html (page 1).
InriuutationIInvariin
[16] Clare Lyle, Marta Kwiatkowksa, and Yarin Gal. "An analysis of the effect of invariance on generalization in neural networks". In: International conference on machine learning Workshop on Understanding and Improving Generalization in Deep Learning. 2019 (page 8).

---

[17] Clare Lyle et al. On the Benefits of Invariance in Neural Networks. 2020. arXiv: 2017.
[cs. LG]] (pages 1. 8).
[18] Jonathan H Manton and Pierre-Olivier Amblard. "A primer on reproducing kernel hilbert spaces". In: arXiv preprint arXiv: 0952 (2014) (page 6).
[19] Haggai Maron et al. "On the Universality of Invariant Networks". In: International Conference
on Machine Learning. 2019, pp. 4363-4371 (page 8).
[20] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. "Learning with invariances in random features and kernel models". In: arXiv preprint arXiv:2102.13221 (2021) (pages 1, 8).
[21] Youssef Mroueh, Stephen Voinea, and Tomaso A Poggio. "Learning with Group Invariant Features: A Kernel Perspective." " In: Advances in Neural Information Processing Systems. 2015. pp. 1558-155855 1566 (page 8).
[22] Anant Raj et al. "Local group invariant representations via orbit embeddings". In: Artificial Intelligence and Statistics. PMLR. 2017, pp. 1225-1235 (page 8).
[23] Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. "Fquivariance through parameter- sharing". In: International Conference on Machine Learning. PMLR. 2017, pp. 2892-2900 (page 8).
[24] Akiyoshi Sannai and Masaaki Imaizumi. Improved Generalization Bound of Group Invari- ant / Equivariant Deep Networks via Quotient Feature Space. 2019. arXiv: 1910. 06552 [stat.Mi] [LL] (pages 8).
[25] Bernhard Schölkopf, Chris Burges, and Vladimir Vapnik. "Incorporating Invariances in Support Vector Learning Machines". In: Springer, 1996, pp. 47-52 (page 8).
[26] H. Schulz-Mirbach. "Constructing invariant features by averaging techniques". In: Proceedings of the 12th IAPR International Conference on Pattern Recognition, Vol. 3 Conference C: Signal Processing (Cat. No. No.94CC3440-5) Vol, 2. 1994, 387-390 vol.2 (page 8).
[27] Hanns Schulz-Mirbach. "On the existence of complete invariant feature spaces in pattern recognition". In: International Conference On Pattern Recognition. Citeseer. 1992 pp. 178- 178 (page 8).
[28] Jure Sokolic et al. "Generalization emror of invariant classifiers". In: Artificial Intelligence and Statistics. 2017, pp. 1094-1103 (pages 1, 8).
[29] James S Spencer et al. "Better, Faster Fermionic Neural Networks". In: arXiv preprint arXiv:2011.07125 (2020) (page 1).
[30] Ingo Steinwart and Andreas Christmann. Support Vector Machines. Information science and statistics. Springer, 2008. ISBN: 978-0-387-77241-7 (pages 3, 5).
[31] Ingo Steinwart and Clint Scovel. "Mercer's theorem on general domains: On the interaction between measures, kernels, and RKHSs". In: Constructive Approximation 35.3 (2012), pp. 363- 417 (page 5).
[32] Marysia Winkels and Taco S Cohen. "3D G-CNNs for pulmonary nodule detection". In: arXiv preprint / 04656 (2018) (page 1).
[33] Jeffrey Wood and John Shawe-Tay
"Representation theory and invariant neural networks". In: Discrete applied mathematics 69.1-2 (1996). pp. 33-60 (pages 1, 8).
[34] Huan Xu and Shic Mannor. "Robustness and generalization" In: Machine learning 86.3
(2012), pp. 391-423 (page 8).
[35] Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. 2018. arXiv:
1804. 10306 [cs. [NS (page 8).
[36] Manzil Zaheer et al. "Deep sets".. In: Advances in neural information processing systems. 2017,
pp. 3391-3401 (page l).
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 2.2 which describes our assumptions.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
10

---

2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See Section 2.2 for general technical conditions not given in statements of results.
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs are given in the supplementary material
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating?
[N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]


Reviews:
[{"review_id": "x5qbPH25vIU", "reviewer": "Reviewer_uJHC", "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. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 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.\nMy 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. \nFor 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.\nAlso, the way to calculate the effective dimensionality in real problems is unclear. Given a kernel with invariance G, can the effective dimensionality be obtained?\nAll 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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. Invariances in many real problems depend on a particular datum, and they do not apply globally.\n\n2. The target function f* is often outside the invariant function set.\n\n3. The example should be provided for the calculation of the effective dimensionality for a given kernel and a invariance set.\n\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "XCMRoepdI8M", "reviewer": "Reviewer_Tnf7", "summary": "The paper considers kernel ridge regression (KRR) where the target is assumed to be invariant with the actions of a compact group. \nThe authors show a reduced generalisation error for the feature-averaged version of the KRR estimator, proving the benefit of incorporating invariant features. \n", "questions": "", "limitations": "", "rating": 7, "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": "To my knowledge, this is a novel quantitative result on KRR with invariant features. \nThe 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. \nThe 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. \n\nThere is one minor negative point that contributes to my score: the use of Fubini's theorem in Theorem 5 (L247). \nThe 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. \n\n\n### Minor comments:\n* Typos: RHKS, Reisz \n* Reference for Lemma 2. The result in the cited paper concerns equivariant functions. Is this reference okay?\n* L232: Typo, $\\mathbb{E}[\\xi_i^2]=0$. \n* You might want to replace the symbol for the operator norm in the supplementary, as it can be read as the Frobenius norm. \n* It might be good if some properties of $j(x, y)$ such as the boundedness are mentioned for later results.\n* 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. \n* 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}, {"review_id": "HDQdFh-SkZ1", "reviewer": "Reviewer_6ik1", "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.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "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": "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.  \n\nIdea 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.\n\nPaper seems to be technically sounds with ideas very well laid out leading to the final results Theorem 8.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Paper addresses limitations of the proposed results clearly in Section 2. There is no analysis needed for societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No related ethical concerns are results are theoretical.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6PUACeTl8c6", "reviewer": "Reviewer_xasM", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "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. \n\nMy 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. \n\n[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. \n\nI 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. \n\nSome additional points / questions:\n\n1) 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. \n2) Just a matter of exposition - it would be good if the displayed equation after line 105 had a full stop. \n3) 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. \n4) Lines 259-260 need to be re-written. \n5) In the displayed equations after lines 261 and 262, M needs to be M_k. \n6) In the displayed equations after line 290, the first and second lines on the right-hand side seem identical. \n7) 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. \nFrom 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. \n8) 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed some limitations of their work, and possible directions for future research. \nThe authors did not discuss societal impact, but I do not deem it necessary, given the theoretical nature of the work. ", "review_text": "", "extra_scores": {"ethical_concerns": "I have no ethical concerns about this paper. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}]

Author rebuttal:

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)