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 f() + 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 Vdr 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) meeasuuabee 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 < oo 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 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- w+(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,(XX,, μ)) by to 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, L)) 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)= Σ Xee
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), Σ 2e Σ
(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 a 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 dd((). 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
d dd
(d-
| 12)00 d2
E((f, f) (Vnn + p/vnz
d2
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 = - ( (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/equivarian 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-Vetie 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.13211 (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": "mn30eyUfrIF", "reviewer": "Reviewer_j3tj", "summary": "The paper aims at quantifying the possible benefits of incorporating invariances to kernel methods. The approach takes the hypothesis returned by kernel ridge regression and enforces invariance by orbit averaging relative to actions of a compact group, i.e., the test prediction at a point $x$ is the average of predictions over the orbit set $\\\\{ gx\\ |\\ g \\in G \\\\}$, with $G$ denoting the group defining an invariance principle. The main contribution is a theoretical result showing that for target hypotheses which are G-invariant, i.e., $f(gx)=f(x)$ for all $g \\in G$ and $x \\in X$, the excess risk is strictly positive (relative to kernel ridge regression hypothesis) and the sample complexity when enforcing invariance can be much lower compared to pursuing standard kernel ridge regression learning (Theorem 5). The main idea is to observe that orbit averaging is a linear operator which defines a subspace of the original RKHS and by exploiting this orthogonal decomposition one gets a lower bound on the excess risk, similar to treatments in low-rank approximations via sub-space restricted inner products.", "questions": "", "limitations": "", "rating": 6, "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": "First of all, my comments are based on the version attached as supplementary materials that contains appendix and the main part of the paper in a single file.\n\nMy first observation is that the assumption in Eq. (1) is fundamental to the result and merits a more detailed discussion than the one provided. It might also be good to have this assumption listed just as one would list a definition, lemma, etc. Namely, this restricts the class of kernels to which the main result/contribution applies and, thus, impacts to standardly used kernels should be discussed in details. Furthermore, I do not find sufficiently clear the argument about the inner product kernels. This needs to be formalized and carefully introduced. At the same time, it would be good to improve motivation at this point and give an example of a group that might induce useful invariance in some ML application. \n\nWould it be possible to provide further clarification for Eq. (5) in line 287? It is not obvious how one obtains the kernel square on the right-hand side and double-integral over X.\n\nWhy is measure $\\mu$ G-invariant in the proof of Proposition 6? If this is an implication in line 290, it needs further clarification.\n\nClarity should be improved at several places. For example,\n- what does it mean to act via an orthogonal representation on X in line 298? It is clear to me but this has not been introduced properly.\n- line 305: x_a, x_b, y_a, y_b have not been introduced prior to their use? Impossible to follow after that...\n\nWhen it comes to related work, it feels that the two papers below are related to the overall goal and motivation of this work:\n\n[1] Raj et al. (AISTATS 2017). Local Group Invariant Representations via Orbit Embeddings.\n\n[2] Lyle et al. (2020). On the Benefits of Invariance in Neural Networks.\n\nIn summary, the work provides a bound which indicates that for a certain class of kernels there are clear benefits of enforcing invariance. The paper, however, lacks an instantiation of the problem setting and explicit examples of groups and orbit averaging in action. Related work can also be improved with a more detailed and thorough covering of prior work. The writing is mostly clear and easy to follow, apart from few lines discussed above. Overall, this might be an interesting paper that could trigger some further research along these lines.\n\n### minor comments\n- line 199: index j should be I\n- line 261: M has not been defined (I am assuming it is the max over diagonal entries of K or index k has been omitted)\n- Lemma B.1 and Corollary B.2 appear to be broken (identical statements)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "czhmneYb3iu", "reviewer": "Reviewer_LcrW", "summary": "This article extends to a kernel setting the idea of Elesedy and Zaidi to leverage a decomposition of L^2 into invariant and null-orbit subspaces. The authors claim to prove the benefit for generalisation of projecting the solution of KRR on the invariant subspace. The article mainly consists of the lemmas and proofs to reach the main theorem on generalisation bounds.", "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": "This article suffers from the comparison with Elesedy and Zaidi in terms of clarity and presentation, and its writing denotes a clear sense of haste. The idea is sound, since any extra, non-invariant, term would hamper the generalization. It was already presented almost with the same terms in Elesedy and Zaidi as underlined by the authors. The proofs seem novel but several points during my reading have cast doubt on their rigor (the version reviewed did not have an appendix). The absence of any numerical experiment even though it is only KRR is damaging, but this reviewer could have disconsidered this aspect if the proofs had been soundproof and without so many ellipses. Since the main body of the article is essentially devoted to the proofs, they should be crystal clear.\n\nMajor comments:\n\n182 The tensor product is misleading since it would define an operator over H. As it does not appear in the proof, the meaning could not be clarified and the sentence remains ungrounded.\n\n241 If $J(K+\\rho){-1} u =0$ while $J u \\neq 0$ then the first inequality cannot hold. No argument was provided to avoid this situation (e.g. commutation of matrices) and, even with it, it would require more care.\n\n244 “temporarily suspending suspicion”, this reviewer could have done as asked if the authors had not considered that $f\\in L_2$ implied that $f^2\\in L_2$ as suggested by the inner product they used (this makes the formula in Theorem 5 clearly inconsistent).\n\n249 “we have established”, where?\n\n250 Why would the essential supremum exist? https://mathworld.wolfram.com/EssentialSupremum.html See the counter example with $1/x$.\n\nMinor comments:\n\n67, 141 his name is Riesz\n\n176 Steinwart&Scovel 2012 discussed the question of the extension of Mercer’s theorem and would be worth citing. The reviewer acknowledges the points made by the authors.\n\n212 footnote 1 seems irrelevant since there is a regularisation parameter $\\rho>0$.\n\n257 “being okay” is uncanny in a mathematical text\n\n271 since all that is required is that the functions of $H$ are integrable w.r.t. \\mu, boundedness should indeed be unnecessary, even a quadratic growth could be allowed for the kernel.\n\n292 “focus” *on*\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Three hours"}, "extra_text": {}}, {"review_id": "NOz8yc0PQ9X", "reviewer": "Reviewer_ZLX8", "summary": "The authors prove theoretically that incorporating invariance in kernel ridge regression improves generalization, when the output is invariant to the action of a compact group.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \nFirst of all, I am not an expert in kernel methods, so I cannot judge objectively the novelty of the paper and the related work. The authors extend the function space perspective of [8] to kernel methods. In particular, they prove a strict improvement over the generalization gap. In my opinion, this is a sufficient contribution.\n\n\nQuality: \nThe theoretical part of the paper seems to be solid. However, I think that an experimental section is missing. Even if this is a theoretical work, I believe that at least a demonstration with synthetic data is beneficial.\n\n\nClarity: \nI think that the paper is ok written, taking into account its technical nature. One recommendation is to move proofs in the appendix, and use the saved space to include some concrete examples and discussions, with the goal to make the paper more accessible to a non-expert reader. Also, I believe is better to move the Sec 4.1 in the beginning of the paper, which will enable the reader to conceptualize the practical aspect of the model.\n\n\nSignificance:\nIn my opinion, this line of theoretical works/results are important in order to understand how learning methods work. Also, I think the presented result is rather interesting. Potentially, some experiments are missing to strengthen the paper. However, as a non-expert I cannot criticise its significance thoroughly. \n\n\nComments:\n1) The averaged version presented between lines 215-216 needs only $\\bar{k}_x(\\mathbf{X})$? We should not use the averaged kernel matrix $\\bar{\\mathbf{X}}$?\n2) In line 225 is the relation correct? In particular, it seems that if $\\Delta(f, f') >0$ then the error of $f$ is higher and $f'$ performs better.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a purely theoretical work and the authors do not discuss any potential negative societal impact.\n\nAs regards the limitations, they are actually the assumptions needed to develop the theory.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "7XWLG2tvAoX", "reviewer": "Reviewer_Bqwx", "summary": "This paper proposes a theoretical analysis of the generalization benefit obtained for some classes of problems which exhibit invariance with respect to a group action.\nEspecially, the paper focuses on kernel ridge regression in the statistical model $Y = f^*(X) + \\epsilon$ and shows that using orbit-averaging on the learnt model provide strictly positive benefit whenever $f^\\star$ is invariant with respect to the group action used in avering.\nSome decomposition of the involved RKHSs in terms of invariance is provided, and the generalization benefit is characterized in terms of the number of samples and typical quantities related to the kernel.\n", "questions": "", "limitations": "", "rating": 8, "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": "-Originality:\nThis paper extends the analysis of orbit-averaging to kernel ridge regression, while previous works focused only on linear model. This constitutes a significant leap forward for the analysis of invariant estimators. Original techniques are developed to analyse the generalization benefit,\nand the literature review is furnished and fair.\n\n-Quality:\nThe submission is technically sound. The results are discussed, compared, and explained as exemplified in theorem 7 where a specific case of invariance is considered to put more interpretability to a somewhat abstract bound otherwise.\nPotential research directions are evoked, either on the modeling spaces or on the considered tasks.\nOverall the submission is of high quality.\n\nA few comments:\n- The bound obtained here is typical of the square loss, exploiting the properties of the generalization error specific to it. Would it be possible to extend this analysis to e.g. self concordant losses, for which typical assumptions in the kernel regime include the source and capacity conditions, both complexity measures a bit different from the effective dimension defined in the paper ?\n- Assumption 1 (A1) on the kernel is illustrated on two examples: inner product with unitary action, and stationnary with norm preserving action. Is this assumption hard to work with ? In the context of working with learnable kernels, could some algorithms be put in place to verify such an assumption ?\n\n-Clarity:\nThe submission is very well written and pleasant to read.\n\n-Significance:\nThe results are very important as learning with invariants is of interest in many practical problems, yet few theoretical hindsights can be found.\n\n-Overall strengh:\nVery well written, sound maths.\n-Overall Weakness:\nThe page limit seems largely overstepped.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper aims at quantifying the possible benefits of incorporating invariances to kernel methods. The approach takes the hypothesis returned by kernel ridge regression and enforces invariance by orbit averaging relative to actions of a compact group. The main contribution is a theoretical result showing that for target hypotheses that are G-invariant, the excess risk is strictly positive (relative to kernel ridge regression hypothesis) and the sample complexity, when enforcing invariance, can be much lower compared to pursuing standard kernel ridge regression learning. 

The reviewers recognize the potential impact of the result and appreciate the potential of the work for motivating further research in such direction. However, they are convinced that the paper requires improvements in terms of presentation and technical quality as they pointed out in the reviews and in the subsequent discussion. We strongly invite the authors to implement the comments of the reviewers in the final version of the paper.

Decision: Accept (Poster)