summaries: 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. 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. Especially, 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. Some 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.  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. 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.  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. 
abstractText: 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.
authors.name: Bryn Elesedy
references.authors: Yaser S Abu-Mostafa
references.title: Hints and the VC dimension
references.venue: Neural Computation
references.authors: Fabio Anselmi
references.title: Unsupervised Learning of Invariant Representations in Hierarchical Architectures
references.authors: Sanjeev Arora
references.title: Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
references.venue: Proceedings of the 36th International Conference on Machine Learning. Ed. by Kamalika Chaudhuri and Ruslan Salakhutdinov
references.authors: Taco Cohen Max Welling
references.title: Group equivariant convolutional networks
references.venue: In: International conference on machine learning
references.authors: Taco S Cohen Mario Geiger Maurice Weiler
references.title: A general theory of equivariant cnns on homogeneous spaces
references.venue: Advances in Neural Information Processing Systems
references.authors: Taco S Cohen
references.title: Spherical cnns
references.venue: arXiv preprint arXiv:1801.10130
references.authors: Bryn Elesedy Sheheryar Zaidi
references.title: Provably Strict Generalisation Benefit for Equivariant Models
references.venue: Proceedings of the 38th International Conference on Machine Learning,
references.authors: Adam Foster Rattana Pukdee Tom Rainforth
references.title: Improving Transformation Invariance in Contrastive Representation Learning
references.venue: arXiv preprint arXiv:2010.09515
references.authors: B. Haasdonk A. Vossen H. Burkhardt
references.title: Invariance in Kernel Methods by Haar Integration Kernels
references.venue: SCIA
references.authors: Arthur Jacot Franck Gabriel Clément Hongler
references.title: Neural tangent kernel: Convergence and generalization in neural networks
references.venue: Advances in neural information processing systems
references.authors: Risi Kondor Shubhendu Trivedi
references.title: On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups
references.venue: In: International Conference on Machine Learning
references.authors: Jaehoon Lee
references.title: Wide neural networks of any depth evolve as linear models under gradient descent
references.venue: Advances in neural information processing systems
references.authors: Juho Lee
references.title: Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks
references.venue: Proceedings of the 36th International Conference on Machine Learning. Ed. by Kamalika Chaudhuri and Ruslan Salakhutdinov
references.authors: Clare Lyle Marta Kwiatkowksa Yarin Gal
references.title: An analysis of the effect of invariance on generalization in neural networks
references.venue: In: International conference on machine learning Workshop on Understanding and Improving Generalization in Deep Learning
references.authors: Clare Lyle
references.title: On the Benefits of Invariance in Neural Networks
references.venue: [cs.LG] (pages
references.authors: Jonathan H Manton Pierre-Olivier Amblard
references.title: A primer on reproducing kernel hilbert spaces
references.venue: arXiv preprint arXiv:1408.0952
references.authors: Haggai Maron
references.title: On the Universality of Invariant Networks
references.venue: In: International Conference on Machine Learning
references.authors: Song Mei Theodor Misiakiewicz Andrea Montanari
references.title: Learning with invariances in random features and kernel models
references.venue: arXiv preprint arXiv:2102.13219
references.authors: Youssef Mroueh Stephen Voinea Tomaso A Poggio
references.title: Learning with Group Invariant Features: A Kernel Perspective.
references.venue: Advances in Neural Information Processing Systems
references.authors: Anant Raj
references.title: Local group invariant representations via orbit embeddings
references.venue: Artificial Intelligence and Statistics. PMLR
references.authors: Siamak Ravanbakhsh Jeff Schneider Barnabas Poczos
references.title: Equivariance through parametersharing
references.venue: In: International Conference on Machine Learning. PMLR
references.authors: Akiyoshi Sannai Masaaki Imaizumi
references.title: Improved Generalization Bound of Group Invariant / Equivariant Deep Networks via Quotient
references.venue: Feature Space
references.authors: Bernhard Schölkopf Chris Burges Vladimir Vapnik
references.title: Incorporating Invariances in Support Vector Learning Machines
references.authors: H. Schulz-Mirbach
references.title: Constructing invariant features by averaging techniques
references.venue: Proceedings of the 12th IAPR International Conference on Pattern Recognition,
references.authors: Hanns Schulz-Mirbach
references.title: On the existence of complete invariant feature spaces in pattern recognition
references.venue: In: International Conference On Pattern Recognition. Citeseer
references.authors: Jure Sokolic
references.title: Generalization error of invariant classifiers
references.venue: Artificial Intelligence and Statistics
references.authors: James S Spencer
references.title: Better, Faster Fermionic Neural Networks
references.venue: arXiv preprint arXiv:2011.07125
references.authors: Ingo Steinwart Andreas Christmann
references.title: Support Vector Machines
references.venue: Information science and statistics. Springer,
references.authors: Ingo Steinwart Clint Scovel
references.title: Mercer’s theorem on general domains: On the interaction between measures, kernels, and RKHSs
references.venue: Constructive Approximation
references.authors: Marysia Winkels Taco S Cohen
references.title: 3D G-CNNs for pulmonary nodule detection
references.authors: Jeffrey Wood John Shawe-Taylor
references.title: Representation theory and invariant neural networks
references.venue: Discrete applied mathematics
references.authors: Huan Xu Shie Mannor
references.title: Robustness and generalization
references.venue: Machine learning
references.authors: Dmitry Yarotsky
references.title: Universal approximations of invariant maps by neural networks. 2018
sections.heading: 1 Introduction
sections.text: Recently, there has been significant interest in models that are 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, if a task has an invariance, then a model that is constructed to 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 physics or medical imaging, in which the invariance is known a priori [29, 32]. Although this intuition is certainly not new (e.g. [33]), it 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 out 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 a 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. In 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 a 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 on the space of invariant functions using the operator O introduced in Section 2.3. Kernel methods have a long been a mainstay of machine learning (see [30, Section 4.7] for a brief historical overview). Kernels can be viewed as mapping the input data into a potentially infinite
  35th Conference on Neural Information Processing Systems (NeurIPS 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 a 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, 3]). In the same vein, via the NTK, we believe the results of this paper can be extended to study wide, invariant neural networks.
sections.heading: 1.1 Summary of Contributions
sections.text: This paper builds towards a 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 our work, showing that the action of the group G on the input space induces an orthogonal decomposition of the RKHS H as
  H = H⊕H⊥ 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 we outline them here. We define the generalisation gap ∆(f, f ′) for two predictors f, f ′ as the difference in their test errors. If ∆(f, f ′) > 0 then f ′ has strictly better test performance than f . Theorem 5 describes ∆(f, f ′) for f 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, let X ∼ µ where µ is G-invariant and Y = f∗(X) + ξ with f∗ G-invariant and E[ξ] = 0, E[ξ2] = σ2 < ∞. Let f be the solution to kernel ridge regression with kernel k and regularisation parameter ρ > 0 on n i.i.d. training examples {(Xi, Yi) ∼ (X,Y ) : i = 1, . . . , n} and let f ′ be its feature averaged version. Our main result, Theorem 5, says that
  E[∆(f, f ′)] ≥ σ 2 dimeff(H⊥) + E
  ( √ nMk + ρ/ √ n)2
  where Mk = supx k(x, x) < ∞, E ≥ 0 describes the approximation errors and dimeff(H⊥) is the effective dimension of the RKHS H⊥. For an RKHS H with kernel k the effective dimension is defined by
  dimeff(H) = ∫ X k(x, y)2 dµ(x) dµ(y).
  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 a 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 ∆(f ′, f ′′) ≥ 0 so ∆(f, f ′′) = ∆(f, f ′)+∆(f ′, f ′′) ≥ ∆(f, f ′).1
  Finally, for intuition, in Theorem 7 we specialise Theorem 5 to the linear setting and compute the bound exactly. Assumptions and technical conditions are given in Section 2 along with an outline of the ideas of Elesedy and Zaidi [8] on which we build. Related works are discussed in Section 5.
sections.heading: 2 Background and Preliminaries
sections.text: In this section we provide a brief introduction to reproducing kernel Hilbert spaces (RKHS) and the ideas we borrow from Elesedy and Zaidi [8]. Throughout this paper, H with be an 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.
  1To be completely clear: if, for instance, it so happens that projecting the RKHS onto a space of invariant predictors before doing KRR gives lower test risk than projecting afterwards (what we are calling feature averaging), then our result applies in that case too.
sections.heading: 2.1 RKHS Basics
sections.text: 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 → R on which the evaluation functional δx : H → R with δx[f ] = f(x) is continuous ∀x ∈ X , or, equivalently is a bounded operator. The Riesz Representation Theorem tells us that there is a unique function kx ∈ H such that δx[f ] = ⟨kx, f⟩H for any f ∈ H, where ⟨·, ·⟩H : H×H → R is the inner product on H. We identify the function k : X ×X → R with k(x, y) = ⟨kx, 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-Aronszajn Theorem shows that for any positive-definite 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 fc(x) = ∑n i=1 cik(x, xi) for c1, . . . , cn ∈ R and x1, . . . , xn ∈ X . For (many) more details, see [30, Chapter 4].
sections.heading: 2.2 Technical Setup and Assumptions
sections.text: Input Space, Group and Measure Let G be a compact2, second countable, Hausdorff topological group with Haar measure λ (see [12, Theorem 2.27]). Let X be a non-empty Polish space admitting a finite, G-invariant Borel measure µ, with suppµ = X . We normalise µ(X ) = λ(G) = 1, the latter is possible because λ is a Radon measure. We assume that G has a measurable action on X that we will write as gx for g ∈ G, x ∈ X . A measurable action is one such that the map g : G × X → X is (λ ⊗ µ)-measurable. A function f : X → R is G-invariant if f(gx) = f(x) ∀x ∈ X ∀g ∈ G. Similarly, a measure µ on X is G-invariant if ∀g ∈ G and any µ-measurable B ⊂ X the pushforward of µ by the action of G equals µ, i.e. (g∗µ)(B) = µ(B). This means that if X ∼ µ then gX ∼ µ ∀g ∈ 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 k : X × X → R be a measurable kernel with RKHS H such that k(·, x) : X → R is continuous for any x ∈ X . Assume that supx∈X k(x, x) = Mk < ∞ and note that this implies that k is bounded since
  k(x, x′) = ⟨kx, kx′⟩H ≤ ∥kx∥H∥kx′∥H = √ k(x, x) √ k(x′, x′) ≤ Mk.
  Every f ∈ H is µ-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 , µ) in the proofs building towards Lemma 3, given in the Supplementary Material. We assume that the kernel satisfies, for all x, y ∈ X ,∫
  G k(gx, y) dλ(g) = ∫ G k(x, gy) dλ(g). (1)
  Equation (1) is our main assumption and we will make frequent use of it. For Eq. (1) to hold, it is sufficient to have k(gx, y) equal to k(x, gy) or k(x, g−1y), where the latter uses compactness (hence unimodularity) of G to change variables g ↔ g−1. Highlighting two special cases: any inner product kernel k(x, x′) = κ(⟨x, x′⟩) such that the action of G is unitary with respect to ⟨·, ·⟩ satisfies Eq. (1), as does any stationary kernel k(x, x′) = κ(∥x− x′∥) with norm that is preserved by G in the sense that ∥gx− gx′∥ = ∥x− x′∥ for any g ∈ G, x, x′ ∈ X . If the norm/inner product is Euclidean, then any orthogonal representation of G will have this property.3
sections.heading: 2.3 Invariance from a Function Space Perspective
sections.text: Given a function f : X → R we can define a corresponding orbit-averaged function Of : X → R with values
  Of(x) = ∫ G f(gx) dλ(g).
  2The 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 or translations on a bounded domain (e.g. an image) and combinations thereof.
  3An orthogonal representation of G on Rd is an action of G via orthogonal matrices, i.e. a homomorpishm G → O(d).
  Of will exist whenever f is µ-measurable. Note that O is a linear operator and, from the invariance of λ, Of is always G-invariant. Interestingly, f is 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 a projection operator, so can have only two eigenvalues 0 and 1. Lemma 2 ([8, Lemma 1]). O : L2(X , µ) → L2(X , µ) is well-defined and self-adjoint. Hence, L2(X , µ) has the orthogonal decomposition
  L2(X , µ) = S ⊕A
  where S = {f ∈ L2(X , µ) : f is G invariant} and A = {f ∈ L2(X , µ) : Of = 0}. The meaning of Lemma 2 is that any f ∈ L2(X , µ) has a (unique) decomposition f = f̄ + f⊥ where f̄ = Of 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 ∈ L2(X , µ), if the target f∗ ∈ L2(X , µ) is G-invariant then the test error R(f) = EX∼µ[(f(X)− f∗(X))2] satisfies
  R(f)−R(f̄) = ∥f⊥∥2L2(X ,µ) ≥ 0.
  The same holds if the target is corrupted by independent, zero mean (additive) noise. 4
sections.heading: 3 Induced Structure of H
sections.text: In this section we present Lemma 3, which is an analog of Lemma 2 for RKHSs. Lemma 3 shows that for any compact group G and RKHS H, if the kernel for H satisfies the assumptions in Section 2.2, then H can be viewed as 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 is not obvious that for any f ∈ H, its orbit averaged version Of is also in H. Moreover, in contrast with L2(X , µ), 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⊕H⊥ where H = {f ∈ H : f is G-invariant} and H⊥ = {f ∈ H : Of = 0}. Moreover, H is an RKHS with kernel
  k̄(x, y) = ∫ G k(x, gy) dλ(g)
  and H⊥ is an RKHS with kernel
  k⊥(x, y) = k(x, y)− k̄(x, y).
  Finally, k̄ is G-invariant in both arguments. As stated earlier, the perspective provided by Lemma 3 will support our analysis of generalisation. Just as with Lemma 2, Lemma 3 says that any f ∈ H can be written as f = f̄ + f⊥ where f̄ is G-invariant and Of⊥ = 0 with ⟨f̄ , f⊥⟩H = 0. As an aside, k̄ happens to qualify as a Haar Integration Kernel, a concept introduced by Haasdonk, Vossen, and Burkhardt [10]. We will see that a 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.
  4The result [8, Lemma 1] is given for equivariance, of which invariance is a special case.
sections.heading: 3.1 Spectral Representation and Effective Dimension
sections.text: In this section we consider the spectrum of an integral operator related to the kernel k. This analysis will ultimately allow us to define a 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 an effective dimension of H⊥ is novel. Define the integral operator Sk : L2(X , µ) → H by
  Skf(x) = ∫ X k(x, x′)f(x′) dµ(x′).
  One way of viewing things is that Sk assigns to every element in L2(X , µ) a function in H. On the other hand, every f ∈ H is bounded so has ∥f∥L2(X ,µ) < ∞ and belongs to some element of L2(X , µ). We write ι : H → L2(X , µ) for the inclusion map that sends f to the element of L2(X , µ) that contains f . In the Supplementary Material we show that ι is injective, so any element of L2(X , µ) contains at most one f ∈ H. One can define Tk : L2(X , µ) → L2(X , µ) by Tk = ι ◦ Sk, and [30, Theorem 4.27] says that Tk is compact, positive, self-adjoint and trace-class. In addition, L2(X , µ) 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 a countable orthonormal basis {ẽi} for L2(X , µ) such that Tkẽi = λiẽi where λ1 ≥ λ2 ≥ · · · ≥ 0 are the eigenvalues of Tk. Moreover, since ι is injective, for each of the ẽi for which λi > 0 there is a unique ei ∈ H such that ιei = ẽi and Skẽi = λiei. Now, since ιkx ∈ L2(X , µ) we have
  ιkx = ∑ i ⟨ιkx, ẽi⟩L2(X ,µ)ẽi = ∑ i (Skẽi)(x)ẽi = ∑ i λiei(x)ẽi. (2)
  From now on we permit ourself to drop the ι to reduce clutter. We use the above to define
  j(x, y) = ⟨kx, ky⟩L2(X ,µ), j̄(x, y) = ⟨k̄x, k̄y⟩L2(X ,µ) and j ⊥(x, y) = ⟨k⊥x , k⊥y ⟩L2(X ,µ).
  These quantities will appear again in our analysis of the generalisation of invariant kernel methods. Indeed, we will see later in this section that E[j⊥(X,X)] is a type of effective dimension of H⊥. 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 theorem. However, we do not assume compactness of X and so the classical form of Mercer’s Theorem does not apply. This aspect of our work is a feature, rather than a bug: the loosening of the compactness condition allows application to common settings such as X = Rn. For generalisations of Mercer’s Theorem see [31] and references therein.
  Lemma 4. We have j = j̄ + j⊥.
  Furthermore, let ēi = Oei and e⊥i = ei − ēi then j(x, y) = ∑ i λ2i ei(x)ei(y), j̄(x, y) = ∑ i λ2i ēi(x)ēi(y), and j ⊥(x, y) = ∑ i λ2i e ⊥ i (x)e ⊥ i (y).
  Finally, the function ∑
  i λ 2 i ēi ⊗ e⊥i : X × X → R with values (x, y) 7→ ∑ i λ 2 i ēi(x)e ⊥ i (y) vanishes
  everywhere.
  Before turning to generalisation, we describe how the above quantities can be used to define a measure effective dimension. We define dimeff(H) = E[j(X,X)] where X ∼ µ. Applying Fubini’s theorem, we find
  dimeff(H) = ∑ i λ2i E[ei(X)2] = ∑ i λ2i ∥ẽi∥2L2(X ,µ) = ∑ i λ2i . (3)
  The series converges by the comparison test because λi ≥ 0 and ∑
  i λi = Tr(Tk) < ∞ (using Lidskii’s theorem) because Tk is trace-class. We have dimeff(H) = Tr(T 2k ) and we can think of this
  (very informally) as taking L2(X , µ), pushing it through H twice using Tk and then measuring its size. Now because j = j̄ + j⊥ we get
  dimeff(H) = dimeff(H) + dimeff(H⊥)
  with dimeff(H⊥) = ∑ i λ2i ∥ẽ⊥i ∥2L2(X ,µ) = Tr(T 2 k )− Tr((OTk)2)
  where ẽ⊥i = ιe ⊥ i . Again, very informally, this can be thought of as pushing L2(X , µ) through H⊥ twice and measuring the size of the output. In the next section we will consider the generalisation of kernel ridge regression and find that dimeff(H⊥) plays a critical role.
sections.heading: 4 Generalisation
sections.text: 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 of feature averaging, finding a strict benefit when the target is G-invariant.
sections.heading: 4.1 Kernel Ridge Regression
sections.text: Given input/output pairs {(xi, yi) : i = 1, . . . , n} where xi ∈ X and yi ∈ R, kernel ridge regression (KRR) returns a predictor that solves the optimisation problem
  argmin f∈H
  C(f) where C(f) = n∑
  i=1
  (f(xi)− yi)2 + ρ∥f∥2H (4)
  and ρ > 0 is the regularisation parameter. KRR can be thought of as performing ridge regression in a possibly infinite dimensional feature space H. The representer theorem tells us that the solution to this problem is of the form f(x) = ∑n i=1 αikxi(x) where α ∈ Rn solves
  argmin α∈Rn
  { ∥Y −Kα∥22 + ρα⊤Kα } , (5)
  Y ∈ Rn is the standard row-stacking of the training outputs with Yi = yi and K is the kernel Gram matrix with Kij = k(xi, xj). We consider solutions of the form5 α = (K + ρI)−1Y which results in the predictor
  f(x) = kx(X) ⊤(K + ρI)−1Y
  where kx(X) ∈ Rn is the vector with components kx(X)i = kx(xi). We will compare the generalisation performance of this predictor with that of its averaged version
  f̄ = k̄x(X) ⊤(K + ρI)−1Y ∈ H.
  To do this we look at the generalisation gap.
sections.heading: 4.2 Generalisation Gap
sections.text: The generalisation gap is a quantity that compares the expected test performances of two predictors on a given task. Given a probability distribution P, data (X,Y ) ∼ P and loss function l defining a supervised learning task, we define the generalisation gap between two predictors f and f ′ to be
  ∆(f, f ′) = E[l(f(X), Y )]− E[l(f ′(X), Y )]
  where the expectations are conditional on the given realisations of f, f ′ if the predictors are random. In this paper we consider l(a, b) = (a−b)2 the squared-error loss and we will assume Y = 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 to
  ∆(f, f ′) = E[(f(X)− f∗(X))2]− E[(f ′(X)− f∗(X))2].
  Clearly, if ∆(f, f ′) > 0 then we expect strictly better test performance from f ′ than f .
  5When K is a positive definite matrix this will be the only solution. If K is singular then ∃c ∈ Rn with∑ ij Kijcicj = ∥ ∑ i cikxi∥ 2 H = 0 so ∑ i cikxi is identically 0 and ∀f ∈ H we get ∑ i cif(xi) = 0 (see [18, Section 4.6.2]). Clearly, this can’t happen if H is sufficiently expressive. In any case, the chosen α is the minimum in Euclidean norm of all possible solutions.
sections.heading: 4.3 Generalisation Benefit of Feature Averaging
sections.text: 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 a 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 {(Xi, Yi) : i = 1, . . . , n} i.i.d. with Yi = f∗(Xi) + ξi where Xi ∼ µ, f∗ ∈ L2(X , µ) is G-invariant and bounded, and {ξi : i = 1, . . . , n} are independent of each other and the {Xi}, with E[ξi] = 0 and E[ξ2i ] = σ2 < ∞. Let f = argminf∈H C(f) 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
  E[∆(f, f̄)] ≥ E[f ∗(X)2j⊥(X,X)] + σ2 dimeff(H⊥)
  ( √ nMk + ρ/ √ n)2
  where each term is non-negative and dimeff(H⊥) := Tr(T 2k )− Tr((OTk)2) = E[j⊥(X,X)] = ∑ α λ2α∥ẽ⊥α∥2L2(X ,µ) ≥ 0
  is the effective dimension of H⊥.
  Theorem 5 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⊥.
  Recall the subspace A in Lemma 2. The role of dimeff(H⊥) mirrors that of dimA 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 5 is a generalisation of [8, Theorem 6]. It is for this reason that we believe that, although the constant Mk in the denominator is likely not optimal, the O(1/n) rate that matches [8] is tight. We leave a more precise analysis of the constants to 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
  E[f∗(X)2j⊥(X,X)] = ∫ X f∗(y)2k⊥(x, y)2 dµ(x) dµ(y) (6)
  using j⊥(x, y) = ∫ X k ⊥(t, x)k⊥(t, y) dµ(t). We also have the following proposition.
  Proposition 6.∫ X f∗(y)2k⊥(x, y)2 dµ(x) dµ(y) = ∫ X f∗(y)2 ( k(x, y)2 − k̄(x, y)2 ) dµ(x) dµ(y)
  For intuition, we present a 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 ϕ(g)x instead of gx.
  Theorem 7. Assume the setting and notation of Theorem 5. In addition, let X = Sd−1 be the unit d− 1 sphere and let µ = Unif(X ). Let G act via an orthogonal representation ϕ on X and define the matrix Φ = ∫ G ϕ(g) dλ(g). Let k(x, y) = x
  ⊤y be the linear kernel and suppose f∗(x) = θ⊤x for some θ ∈ Rd. Then the bound in Theorem 5 becomes
  E[∆(f, f̄)] ≥ 1 ( √ n+ ρ/ √ n)2
  ( d− ∥Φ∥2F
  d2 + (d− ∥Φ∥2F)∥θ∥22 d2(d+ 2) ) where ∥·∥F is the Frobenius norm. The first term in the parentheses is exactly dimeff(H⊥) and the second term is exactly E[f∗(X)2j⊥(X,X)].
  One can confirm that the generalisation gap cannot be negative in Theorem 7 using Jensen’s inequality ∥Φ∥2F = ∥∥∥∥∫
  G ϕ(g) dλ(g) ∥∥∥∥2 F ≤ ∫ G ∥ϕ(g)∥2F dλ(g) = ∫ G Tr(ϕ(g)⊤ϕ(g)) dλ(g) = Tr(I) = d
  because the representation ϕ is orthgonal.
  The matrix Φ in Theorem 7 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 G = Sd the permutation group on d elements and ϕ is the natural representation in terms of permutation matrices, we have Φ = 1d11
  ⊤ where 1 ∈ Rd is the vector of all 1s. In this case, since the target is assumed to be G-invariant, we must have θ = t1 for some t ∈ R. Specifically, Theorem 7 then asserts
  E[∆(f, f̄)] ≥ (d− 1)(dt 2 + d+ 2)
  d2(d+ 2)( √ n+ ρ/ √ n)2 .
sections.heading: 5 Related Work
sections.text: Incorporating invariance into machine learning models is not a 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, 27]. Indeed, early work also considered invariant neural networks [33], using methods that seem to have been rediscovered in [23]. Modern implementations include invariant/equivariant 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 Mroueh, 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] to obtain a generalisation bound for certain types of classifiers that are invariant to a finite set of transformations, while Sannai and Imaizumi [24] obtain a 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 a 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 ρ → 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 R), so does not meet our technical conditions in Section 2.2. We conjecture that the boundedness assumption on k can be removed, or at least with mild care weakened to hold µ-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] in 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 an expression for the generalisation error that is conditional on the training data and in terms of the projection of the predictor onto a space of 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.
sections.heading: 6 Discussion
sections.text: We have demonstrated a provably strict generalisation benefit for feature averaging in kernel ridge regression. In doing this we have leveraged an observation on 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
  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.
  Acknowledgments and Disclosure of Funding We thank Sheheryar Zaidi for many helpful discussions in the early stages of this project and Yee Whye Teh for suggesting the application of [8] to kernels. Additionally, we 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 EP/L015897/1).
title: Provably Strict Generalisation Benefit for Invariance in Kernel Methods