# Provably Strict Generalisation Benefit for Invariance in Kernel Methods

Bryn Elesedy
University of Oxford
<EMAIL_ADDRESS>

###### 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 [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.

##  1 Introduction

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 [30, 32]. Although this intuition is certainly not new (e.g. [33]), it
has inspired much recent work (for instance, see [36, 16]).

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 [29, 25] 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, 21] 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 [29, 25],
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 [18, 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 $\mathcal{O}$
introduced in Section 2.3.

Kernel methods have a long been a mainstay of machine learning (see [31,
Section 4.7] for a brief historical overview). Kernels can be viewed as
mapping the input data into a potentially infinite 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_ [12], 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. [15, 3]). 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 a precise characterisation of the benefit of
incorporating invariance in kernel ridge regression by feature averaging.

Lemma 1, given in Section 3, forms the basis of our work, showing that the
action of the group $\mathcal{G}$ on the input space induces an orthogonal
decomposition of the RKHS $\mathcal{H}$ as

$\mathcal{H}=\overline{\mathcal{H}}\oplus\mathcal{H}_{\scaleobj{0.75}{\perp}}$

where each term is an RKHS and $\overline{\mathcal{H}}$ consists of all of the
invariant functions in $\mathcal{H}$. We stress that, while the main results
of this paper concern kernel ridge regression, Lemma 1 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 $\Delta(f,f^{\prime})$ for two predictors
$f,f^{\prime}$ as the difference in their test errors. If
$\Delta(f,f^{\prime})>0$ then $f$ has _strictly better test performance_ than
$f^{\prime}$. Theorem 1 describes $\Delta(f,f^{\prime})$ for $f$ being the
solution to kernel ridge regression and $f^{\prime}$ its invariant (feature
averaged) version and shows that it is positive when the target is invariant.

More specifically, let $X\sim\mu$ where $\mu$ is $\mathcal{G}$-invariant and
$Y=f^{*}(X)+\xi$ with $f^{*}$ $\mathcal{G}$-invariant and
$\operatorname{\mathbb{E}}[\xi]=0$,
$\operatorname{\mathbb{E}}[\xi^{2}]=\sigma^{2}<\infty$. Let $f$ be the
solution to kernel ridge regression with kernel $k$ and regularisation
parameter $\rho>0$ on $n$ i.i.d. training examples
$\\{(X_{i},Y_{i})\sim(X,Y):i=1,\dots,n\\}$ and let $f^{\prime}$ be its feature
averaged version. Our main result, Theorem 1, says that

$\operatorname{\mathbb{E}}[\Delta(f,f^{\prime})]\geq\frac{\sigma^{2}\dim_{\text{eff}}(\mathcal{H}_{\scaleobj{0.75}{\perp}})+\mathcal{E}}{(\sqrt{n}M_{k}+\rho/\sqrt{n})^{2}}$

where $M_{k}=\sup_{x}k(x,x)<\infty$, $\mathcal{E}\geq 0$ describes the
approximation errors and
$\dim_{\text{eff}}(\mathcal{H}_{\scaleobj{0.75}{\perp}})$ is the effective
dimension of the RHKS $\mathcal{H}_{\scaleobj{0.75}{\perp}}$. For an RKHS
$\mathcal{H}$ with kernel $k$ the effective dimension is defined by

$\dim_{\text{eff}}(\mathcal{H})=\int_{\mathcal{X}}k(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y).$

where $\mathcal{X}=\operatorname{\text{supp}}\mu$. We return to this quantity
at various points in the paper. Finally, for intuition, in Theorem 3 we
specialise Theorem 1 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 [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 [8]. Throughout this paper,
$\mathcal{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 $\mu$ is $\mathcal{G}$-invariant and that
the kernel $k$ is bounded and satisfies Eq. 1. We defer some background and
technical results to Appendices C and B respectively.

###  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) $\mathcal{H}$ is Hilbert space of real functions
$f:\mathcal{X}\to\mathbb{R}$ on which the evaluation functional
$\delta_{x}:\mathcal{H}\to\mathbb{R}$ with $\delta_{x}[f]=f(x)$ is continuous
$\forall x\in\mathcal{X}$, or, equivalently is a bounded operator. The Reisz
Representation Theorem tells us that there is a unique function
$k_{x}\in\mathcal{H}$ such that $\delta_{x}[f]=\langle
k_{x},f\rangle_{\mathcal{H}}$ for any $f\in\mathcal{H}$, where
$\langle\cdot,\cdot\rangle_{\mathcal{H}}:\mathcal{H}\times\mathcal{H}\to\mathbb{R}$
is the inner product on $\mathcal{H}$. We identify the function
$k:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$ with $k(x,y)=\langle
k_{x},k_{y}\rangle_{\mathcal{H}}$ as the _reproducing kernel_ of
$\mathcal{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
$\mathcal{H}$ is as the completion of the set of linear combinations of the
form $f_{c}(x)=\sum_{i=1}^{n}c_{i}k(x,x_{i})$ for
$c_{1},\dots,c_{n}\in\mathbb{R}$ and $x_{1},\dots,x_{n}\in\mathcal{X}$. For
(many) more details, see [31, Chapter 4].

###  2.2 Technical Setup and Assumptions

#### Input Space, Group and Measures

Let $\mathcal{G}$ be a compact, second countable, Hausdorff topological group
with Haar measure $\lambda$ (see [13, Theorem 2.27]). Let $\mathcal{X}$ be a
non-empty Polish space admitting a finite, $\mathcal{G}$-invariant Borel
measure $\mu$, with $\operatorname{\text{supp}}\mu=\mathcal{X}$. We normalise
$\mu(\mathcal{X})=\lambda(\mathcal{G})=1$, the latter is possible because
$\lambda$ is a Radon measure. We assume that $\mathcal{G}$ has a measurable
action on $\mathcal{X}$ that we will write as $gx$ for $g\in\mathcal{G}$,
$x\in\mathcal{X}$. A measurable action is one such that the map
$g:\mathcal{G}\times\mathcal{X}\to\mathcal{X}$ is
$(\lambda\otimes\mu)$-measurable. A function $f:\mathcal{X}\to\mathbb{R}$ is
$\mathcal{G}$-invariant if $f(gx)=f(x)$ $\forall x\in\mathcal{X}$ $\forall
g\in\mathcal{G}$. Similarly, a measure $\mu$ on $\mathcal{X}$ is
$\mathcal{G}$-invariant if $\forall g\in\mathcal{G}$ and any $\mu$-measurable
$B\subset\mathcal{X}$ the pushforward of $\mu$ by the action of $\mathcal{G}$
equals $\mu$, i.e. $(g_{*}\mu)(B)=\mu(B)$. This means that if $X\sim\mu$ then
$gX\sim\mu$ $\forall g\in\mathcal{G}$. We will make use of the fact that the
Haar measure is $\mathcal{G}$-invariant when $\mathcal{G}$ acts on itself by
either left or right multiplication, the latter holding because $\mathcal{G}$
is compact. Up to normalisation, $\lambda$ is the unique measure on
$\mathcal{G}$ with this property.

#### The Kernel and the RKHS

Let $k:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$ be a measurable kernel with
RKHS $\mathcal{H}$ such that $k(\cdot,x):\mathcal{X}\to\mathbb{R}$ is
continuous for any $x\in\mathcal{X}$. Assume that
$\sup_{x\in\mathcal{X}}{k(x,x)}=M_{k}<\infty$ and note that this implies that
$k$ is bounded since

$k(x,x^{\prime})=\langle k_{x},k_{x^{\prime}}\rangle_{\mathcal{H}}\leq\lVert
k_{x}\rVert_{\mathcal{H}}\lVert
k_{x^{\prime}}\rVert_{\mathcal{H}}=\sqrt{k(x,x)}\sqrt{k(x^{\prime},x^{\prime})}\leq
M_{k}$

Every $f\in\mathcal{H}$ is $\mu$-measurable, bounded and continuous by [31,
Lemmas 4.24 and 4.28] and in addition $\mathcal{H}$ is separable using [31,
Lemma 4.33]. These conditions allow the application of [31, Theorem 4.26] to
relate $\mathcal{H}$ to ${L_{2}(\mathcal{X},\mu)}$ in the proofs building
towards Lemma 1, given in Appendix C. We assume that the kernel satisfies, for
all $x,y\in\mathcal{X}$,

$\int_{\mathcal{G}}k(gx,y)\mathop{}\\!\mathrm{d}\lambda(g)=\int_{\mathcal{G}}k(x,gy)\mathop{}\\!\mathrm{d}\lambda(g).$
(1)

For this it is sufficient to have $k(gx,y)$ equal to $k(x,gy)$ or
$k(x,g^{-1}y)$, the latter uses compactness (hence unimodularity) of
$\mathcal{G}$ to change variables $g\leftrightarrow g^{-1}$. Highlighting two
special cases: any inner product kernel $k(x,x^{\prime})=\kappa(\langle
x,x^{\prime}\rangle)$ such that the action of $\mathcal{G}$ is unitary with
respect to $\langle\cdot,\cdot\rangle$ satisfies Eq. 1, as does any stationary
kernel $k(x,x^{\prime})=\kappa(\lVert x-x^{\prime}\rVert)$ with norm that is
preserved by $\mathcal{G}$ in the sense that $\lVert gx-
gx^{\prime}\rVert=\lVert x-x^{\prime}\rVert$ for any $g\in\mathcal{G}$,
$x,x^{\prime}\in\mathcal{X}$.

###  2.3 Invariance from a Function Space Perspective

Given a function $f:\mathcal{X}\to\mathbb{R}$ we can define a corresponding
orbit-averaged function $\mathcal{O}f:\mathcal{X}\to\mathbb{R}$ with values

$\mathcal{O}f(x)=\int_{\mathcal{G}}f(gx)\mathop{}\\!\mathrm{d}\lambda(g).$

$\mathcal{O}f$ will exist whenever $f$ is $\mu$-measurable. Note that
$\mathcal{O}$ is a linear operator and, from the invariance of $\lambda$,
$\mathcal{O}f$ is always $\mathcal{G}$-invariant. Interestingly, $f$ is
$\mathcal{G}$-invariant _only_ if $f=\mathcal{O}f$. [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
$\mathcal{O}$.

######  Lemma 1 ([8, Propositions 23 and 24]).

A function $f$ is $\mathcal{G}$-invariant if and only if $\mathcal{O}f=f$.
This implies that $\mathcal{O}$ is a projection operator, so can have only two
eigenvalues $0$ and $1$.

######  Lemma 2 ([8, Lemma 1]).

$\mathcal{O}:{L_{2}(\mathcal{X},\mu)}\to{L_{2}(\mathcal{X},\mu)}$ is well-
defined and self-adjoint. Hence, ${L_{2}(\mathcal{X},\mu)}$ has the orthogonal
decomposition

${L_{2}(\mathcal{X},\mu)}=S\oplus A$

where $S=\\{f\in{L_{2}(\mathcal{X},\mu)}:f\text{ is $\mathcal{G}$
invariant}\\}$ and $A=\\{f\in{L_{2}(\mathcal{X},\mu)}:\mathcal{O}f=0\\}$.

The meaning of Lemma 2 is that any $f\in{L_{2}(\mathcal{X},\mu)}$ has a
(unique) decomposition $f=\bar{f}+f^{\scaleobj{0.75}{\perp}}$ where
$\bar{f}=\mathcal{O}f$ is $\mathcal{G}$-invariant and
$\mathcal{O}f^{\scaleobj{0.75}{\perp}}=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\in{L_{2}(\mathcal{X},\mu)}$, if the target
$f^{*}\in{L_{2}(\mathcal{X},\mu)}$ is $\mathcal{G}$-invariant then the test
error $R(f)=\operatorname{\mathbb{E}}_{X\sim\mu}[(f(X)-f^{*}(X))^{2}]$
satisfies

$R(f)-R(\bar{f})=\lVert
f^{\scaleobj{0.75}{\perp}}\rVert_{L_{2}(\mathcal{X},\mu)}^{2}\geq 0.$

The same holds if the target is corrupted by independent, zero mean (additive)
noise.

##  3 Induced Structure of $\mathcal{H}$

In this section we present Lemma 1, which is an analog of Lemma 2 for RKHSs.
Lemma 1 shows that for any compact group $\mathcal{G}$ and RKHS $\mathcal{H}$,
if the kernel for $\mathcal{H}$ satisfies the assumptions in Section 2.2, then
$\mathcal{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 $\mathcal{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 1 should follow immediately from Lemma
2, but this is not the case. First, it is not obvious that for any
$f\in\mathcal{H}$, its orbit averaged version $\mathcal{O}f$ is also in
$\mathcal{H}$. Moreover, in contrast with ${L_{2}(\mathcal{X},\mu)}$, an
explicit form for the inner product on $\mathcal{H}$ is not immediate, which
means that some work is needed to check that $\mathcal{O}$ is self-adjoint on
$\mathcal{H}$. These are important requirements for the proofs of both Lemmas
2 and 1 and we establish them, along with $\mathcal{O}$ being continuous on
$\mathcal{H}$, in Lemmas 6, 7 and 8 respectively. The assumption that the
kernel satisfies Eq. 1 plays a central role.

######  Lemma 1.

$\mathcal{H}$ admits the orthogonal decomposition

$\mathcal{H}=\overline{\mathcal{H}}\oplus\mathcal{H}_{\scaleobj{0.75}{\perp}}$

where $\overline{\mathcal{H}}=\\{f\in\mathcal{H}:f\text{ is
$\mathcal{G}$-invariant}\\}$ and
$\mathcal{H}_{\scaleobj{0.75}{\perp}}=\\{f\in\mathcal{H}:\mathcal{O}f=0\\}$.
Moreover, $\overline{\mathcal{H}}$ is an RKHS with kernel

$\bar{k}(x,y)=\int_{\mathcal{G}}k(x,gy)\mathop{}\\!\mathrm{d}\lambda(g)$

and $\mathcal{H}_{\scaleobj{0.75}{\perp}}$ is an RKHS with kernel

$k^{\scaleobj{0.75}{\perp}}(x,y)=k(x,y)-\bar{k}(x,y).$

Finally, $\bar{k}$ is $\mathcal{G}$-invariant in both arguments.

###### Proof.

From Lemma 1 we know that $\mathcal{O}$ is a projection operator. Since it is
self-adjoint, $\mathcal{O}$ is even an orthogonal projection on $\mathcal{H}$:
let $h_{S}$ have eigenvalue $1$ and $h_{A}$ have eigenvalue $0$ under
$\mathcal{O}$, then

$\langle
h_{S},h_{A}\rangle_{\mathcal{H}}=\langle\mathcal{O}h_{S},h_{A}\rangle_{\mathcal{H}}=\langle
h_{S},\mathcal{O}h_{A}\rangle_{\mathcal{H}}=0.$

Therefore, by linearity, for any $f\in\mathcal{H}$ we can write
$f=\bar{f}+f^{\scaleobj{0.75}{\perp}}$ where
$\bar{f}=\mathcal{O}f\in\overline{\mathcal{H}}$ is $\mathcal{G}$-invariant and
$f^{\scaleobj{0.75}{\perp}}=f-\mathcal{O}f\in\mathcal{H}_{\scaleobj{0.75}{\perp}}$
and these terms are mutually orthogonal.

By the linearity of $\mathcal{O}$, it is clear that
$\overline{\mathcal{H}}=\mathcal{O}\mathcal{H}$ is an inner product space. It
is easy to show that $\mathcal{O}$ being continuous implies
$\overline{\mathcal{H}}$ is complete. Thus $\overline{\mathcal{H}}$ is a
Hilbert space, and an RKHS since the evaluation functional is clearly
continuous on $\overline{\mathcal{H}}\subset\mathcal{H}$. For any
$h_{S}\in\overline{\mathcal{H}}$ we have

$h_{S}(x)=\langle h_{S},k_{x}\rangle_{\mathcal{H}}=\langle
h_{S},\mathcal{O}k_{x}\rangle_{\mathcal{H}}=\langle
h_{S},\bar{k}_{x}\rangle_{\mathcal{H}}$

and the uniqueness afforded by the Reisz representation theorem tells us that
the reproducing kernel for $\overline{\mathcal{H}}$ is
$\bar{k}(x,y)=\int_{\mathcal{G}}k(x,gy)\mathop{}\\!\mathrm{d}\lambda(g)$. We
have $\lVert\text{id}-\mathcal{O}\rVert\leq 2$ and we can do the same argument
to show that $\mathcal{H}_{\scaleobj{0.75}{\perp}}$ is an RKHS with
reproducing kernel $k^{\scaleobj{0.75}{\perp}}$ as claimed. Note that one can
write $k^{\scaleobj{0.75}{\perp}}(x,y)=\langle
k^{\scaleobj{0.75}{\perp}}_{x},k^{\scaleobj{0.75}{\perp}}_{y}\rangle_{\mathcal{H}}$
so it must be positive-definite. The $\mathcal{G}$-invariance of
$\bar{k}(x,y)$ in both arguments is immediate from Eq. 1 and Lemma 1. ∎

As stated earlier, the perspective provided by Lemma 1 will support our
analysis of generalisation. Just as with Lemma 2, Lemma 1 says that any
$f\in\mathcal{H}$ can be written as $f=\bar{f}+f^{\scaleobj{0.75}{\perp}}$
where $\bar{f}$ is $\mathcal{G}$-invariant and
$\mathcal{O}f^{\scaleobj{0.75}{\perp}}=0$ with
$\langle\bar{f},f^{\scaleobj{0.75}{\perp}}\rangle_{\mathcal{H}}=0$. As an
aside, $\bar{k}$ happens to qualify as a _Haar Integration Kernel_ , a concept
introduced by [10]. We will see that a notion of effective dimension of the
RKHS $\mathcal{H}_{\scaleobj{0.75}{\perp}}$ with kernel
$k^{\scaleobj{0.75}{\perp}}$ governs the generalisation gap between an
arbitrary predictor $f$ and its invariant version $\mathcal{O}f$. This
effective dimension arises from the spectral theory of an integral operator
related to $k$, which we develop in the next section.

###  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 us to define a notion of
effective dimension of $\mathcal{H}_{\scaleobj{0.75}{\perp}}$ 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 $\mathcal{H}_{\scaleobj{0.75}{\perp}}$ is novel.

Define the integral operator $S_{k}:{L_{2}(\mathcal{X},\mu)}\to\mathcal{H}$ by

$S_{k}f(x)=\int_{\mathcal{X}}k(x,x^{\prime})f(x^{\prime})\mathop{}\\!\mathrm{d}\mu(x^{\prime}).$

One way of viewing things is that $S_{k}$ assigns to every element in
${L_{2}(\mathcal{X},\mu)}$ a function in $\mathcal{H}$. On the other hand,
every $f\in\mathcal{H}$ is bounded so has $\lVert
f\rVert_{L_{2}(\mathcal{X},\mu)}<\infty$ and belongs to some element of
${L_{2}(\mathcal{X},\mu)}$. We write
$\iota:\mathcal{H}\to{L_{2}(\mathcal{X},\mu)}$ for the _inclusion map_ that
sends $f$ to the element of ${L_{2}(\mathcal{X},\mu)}$ that contains $f$. In
Lemma 1 we show that $\iota$ is injective, so any element of
${L_{2}(\mathcal{X},\mu)}$ contains at most one $f\in\mathcal{H}$.

One can define $T_{k}:{L_{2}(\mathcal{X},\mu)}\to{L_{2}(\mathcal{X},\mu)}$ by
$T_{k}=\iota\circ S_{k}$, and [31, Theorem 4.27] says that $T_{k}$ is compact,
positive, self-adjoint and trace-class. In addition,
${L_{2}(\mathcal{X},\mu)}$ is separable by [7, Proposition 3.4.5], because
$\mathcal{X}$ is Polish and $\mu$ is a Borel measure, so has a countable
orthonormal basis. Hence, by the Spectral Theorem, there exists a countable
orthonormal basis $\\{\tilde{e}_{i}\\}$ for ${L_{2}(\mathcal{X},\mu)}$ such
that $T_{k}\tilde{e}_{i}=\lambda_{i}\tilde{e}_{i}$ where
$\lambda_{1}\geq\lambda_{2}\geq\dots\geq 0$ are the eigenvalues of $T_{k}$.
Moreover, since $\iota$ is injective, for each of the $\tilde{e}_{i}$ for
which $\lambda_{i}>0$ there is a unique $e_{i}\in\mathcal{H}$ such that $\iota
e_{i}=\tilde{e}_{i}$ and $S_{k}\tilde{e}_{i}=\lambda_{i}e_{i}$.

Now, since $\iota k_{x}\in{L_{2}(\mathcal{X},\mu)}$ we have

$\iota k_{x}=\sum_{i}\langle\iota
k_{x},\tilde{e}_{i}\rangle_{L_{2}(\mathcal{X},\mu)}\tilde{e}_{i}=\sum_{i}(S_{k}\tilde{e}_{i})(x)\tilde{e}_{i}=\sum_{i}\lambda_{i}e_{i}(x)\tilde{e}_{i}.$
(2)

From now on we permit ourself to drop the $\iota$ to reduce clutter. We use
the above to define

$j(x,y)=\langle
k_{x},k_{y}\rangle_{L_{2}(\mathcal{X},\mu)},\quad\bar{j}(x,y)=\langle\bar{k}_{x},\bar{k}_{y}\rangle_{L_{2}(\mathcal{X},\mu)}\quad\text{and}\quad
j^{\scaleobj{0.75}{\perp}}(x,y)=\langle
k^{\scaleobj{0.75}{\perp}}_{x},k^{\scaleobj{0.75}{\perp}}_{y}\rangle_{L_{2}(\mathcal{X},\mu)}.$

These quantities will appear again in our analysis of the generalisation of
invariant kernel methods. Indeed, we will see later in this section that
$\operatorname{\mathbb{E}}[j^{\scaleobj{0.75}{\perp}}(X,X)]$ is a type of
effective dimension of $\mathcal{H}_{\scaleobj{0.75}{\perp}}$. Following Eq.
2, one finds the series representations given below in Lemma 2.

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 $\mathcal{X}$
and so (the classical form of) Mercer’s Theorem does not apply. In particular,
the set $\\{e_{i}\\}$ (even when scaled appropriately) need not form an
orthonormal basis in $\mathcal{H}$. 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 $\mathcal{X}=\mathbb{R}^{n}$.

######  Lemma 2.

We have

$j=\bar{j}+j^{\scaleobj{0.75}{\perp}}.$

Furthermore, let $\bar{e}_{i}=\mathcal{O}e_{i}$ and
$e^{\scaleobj{0.75}{\perp}}_{i}=e_{i}-\bar{e}_{i}$ then

$j(x,y)=\sum_{i}\lambda_{i}^{2}e_{i}(x)e_{i}(y),\quad\bar{j}(x,y)=\sum_{i}\lambda_{i}^{2}\bar{e}_{i}(x)\bar{e}_{i}(y),\quad\text{and}\quad
j^{\scaleobj{0.75}{\perp}}(x,y)=\sum_{i}\lambda_{i}^{2}e^{\scaleobj{0.75}{\perp}}_{i}(x)e^{\scaleobj{0.75}{\perp}}_{j}(y).$

Finally, the function $\sum_{i}\lambda_{i}^{2}\bar{e}_{i}\otimes
e^{\scaleobj{0.75}{\perp}}_{i}:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$
vanishes everywhere.

###### Proof.

We show in Lemma 2 that $\mathcal{O}$ and $S_{k}$ commute on
${L_{2}(\mathcal{X},\mu)}$ and $\mathcal{O}$ is self-adjoint on
${L_{2}(\mathcal{X},\mu)}$ by Lemma 1, so $\mathcal{O}$ and $\iota$ (the
adjoint of $S_{k}$ by [31, Theorem 4.26]) must also commute. The first comment
is then immediate from the observation that if $a\in\overline{\mathcal{H}}$
and $b\in\mathcal{H}_{\scaleobj{0.75}{\perp}}$ one has

$\langle\iota a,\iota
b\rangle_{L_{2}(\mathcal{X},\mu)}=\langle\iota\mathcal{O}a,\iota
b\rangle_{L_{2}(\mathcal{X},\mu)}=\langle\mathcal{O}\iota a,\iota
b\rangle_{L_{2}(\mathcal{X},\mu)}=\langle\iota
a,\iota\mathcal{O}b\rangle_{L_{2}(\mathcal{X},\mu)}=0.$

We also have both of

$\langle\iota\bar{k}_{x},\tilde{e}_{i}\rangle_{L_{2}(\mathcal{X},\mu)}=\langle\iota
k_{x},\mathcal{O}\tilde{e}_{i}\rangle_{L_{2}(\mathcal{X},\mu)}=S_{k}\mathcal{O}\tilde{e}_{i}=\mathcal{O}S_{k}\tilde{e}_{i}=\lambda_{i}\bar{e}_{i}$

and

$\langle\iota
k^{\scaleobj{0.75}{\perp}}_{x},\tilde{e}_{i}\rangle_{L_{2}(\mathcal{X},\mu)}=\langle\iota
k_{x},(\operatorname{\text{id}}-\mathcal{O})\tilde{e}_{i}\rangle_{L_{2}(\mathcal{X},\mu)}=S_{k}(\operatorname{\text{id}}-\mathcal{O})\tilde{e}_{i}=(\operatorname{\text{id}}-\mathcal{O})S_{k}\tilde{e}_{i}=\lambda_{i}e^{\scaleobj{0.75}{\perp}}_{i}.$

Therefore $\iota\bar{k}_{x}=\sum_{i}\lambda_{i}\bar{e}_{i}(x)\tilde{e}_{i}$
and $\iota
k^{\scaleobj{0.75}{\perp}}_{x}=\sum_{i}\lambda_{i}e^{\scaleobj{0.75}{\perp}}_{i}(x)\tilde{e}_{i}$.
Taking inner products on ${L_{2}(\mathcal{X},\mu)}$ gives the remaining
results. ∎

Before turning to generalisation, we describe how the above quantities can be
used to define a measure effective dimension. We define

$\dim_{\text{eff}}(\mathcal{H})=\operatorname{\mathbb{E}}[j(X,X)]$

where $X\sim\mu$. Applying Fubini’s theorem, we find

$\dim_{\text{eff}}(\mathcal{H})=\sum_{i}\lambda_{i}^{2}\operatorname{\mathbb{E}}[e_{i}(X)^{2}]=\sum_{i}\lambda_{i}^{2}\lVert\tilde{e}_{i}\rVert_{L_{2}(\mathcal{X},\mu)}^{2}=\sum_{i}\lambda_{i}^{2}.$

The series converges by the comparison test because $\lambda_{i}\geq 0$ and
$\sum_{i}\lambda_{i}=\operatorname{Tr}(T_{k})<\infty$. We have
$\dim_{\text{eff}}(\mathcal{H})=\operatorname{Tr}(T_{k}^{2})$ and we can think
of this (very informally) as taking ${L_{2}(\mathcal{X},\mu)}$, pushing it
through $\mathcal{H}$ twice using $T_{k}$ and then measuring its size. Now
because $j=\bar{j}+j^{\scaleobj{0.75}{\perp}}$ we get

$\dim_{\text{eff}}(\mathcal{H})=\dim_{\text{eff}}(\overline{\mathcal{H}})+\dim_{\text{eff}}(\mathcal{H}_{\scaleobj{0.75}{\perp}})$

with

$\dim_{\text{eff}}(\mathcal{H}_{\scaleobj{0.75}{\perp}})=\sum_{i}\lambda_{i}^{2}\lVert\tilde{e}_{i}^{\scaleobj{0.75}{\perp}}\rVert_{L_{2}(\mathcal{X},\mu)}^{2}=\operatorname{Tr}(T_{k}^{2})-\operatorname{Tr}((\mathcal{O}T_{k})^{2})$

where $\tilde{e}_{i}^{\scaleobj{0.75}{\perp}}=\iota
e^{\scaleobj{0.75}{\perp}}_{i}$. Again, very informally, this can be thought
of as pushing ${L_{2}(\mathcal{X},\mu)}$ through
$\mathcal{H}_{\scaleobj{0.75}{\perp}}$ twice and measuring the size of the
output. In the next section we will consider the generalisation of kernel
ridge regression and find that
$\dim_{\text{eff}}(\mathcal{H}_{\scaleobj{0.75}{\perp}})$ plays a 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 of feature averaging, finding a strict benefit when
the target is $\mathcal{G}$-invariant.

###  4.1 Kernel Ridge Regression

Given input/output pairs $\\{(x_{i},y_{i}):i=1,\dots,n\\}$ where
$x_{i}\in\mathcal{X}$ and $y_{i}\in\mathbb{R}$, kernel ridge regression (KRR)
returns a predictor that solves the optimisation problem

$\operatorname*{argmin}_{f\in\mathcal{H}}C(f)\quad\text{ where }\quad
C(f)=\sum_{i=1}^{n}(f(x_{i})-y_{i})^{2}+\rho\lVert f\rVert_{\mathcal{H}}^{2}$
(3)

and $\rho>0$ is the regularisation parameter. KRR can be thought of as
performing ridge regression in a possibly infinite dimensional feature space
$\mathcal{H}$. The representer theorem tells us that the solution to this
problem is of the form $f(x)=\sum_{i=1}^{n}\alpha_{i}k_{x_{i}}(x)$ where
$\alpha\in\mathbb{R}^{n}$ solves

$\operatorname*{argmin}_{\alpha\in\mathbb{R}^{n}}\left\\{\lVert\bm{Y}-K\alpha\rVert_{2}^{2}+\rho\alpha^{\top}K\alpha\right\\},$
(4)

$\bm{Y}\in\mathbb{R}^{n}$ is the standard row-stacking of the training outputs
with $\bm{Y}_{i}=y_{i}$ and $K$ is the kernel Gram matrix with
$K_{ij}=k(x_{i},x_{j})$. We consider solutions of the form111When $K$ is a
positive definite matrix this will be the _only_ solution. If $K$ is singular
then $\exists c\in\mathbb{R}^{n}$ with
$\sum_{ij}K_{ij}c_{i}c_{j}=\lVert\sum_{i}c_{i}k_{x_{i}}\rVert_{\mathcal{H}}^{2}=0$
so $\sum_{i}c_{i}k_{x_{i}}$ is identically $0$ and $\forall f\in\mathcal{H}$
we get $\sum_{i}c_{i}f(x_{i})=0$ (see [19, Section 4.6.2]). Clearly, this
can’t happen if $\mathcal{H}$ is sufficiently expressive. In any case, the
chosen $\alpha$ is the minimum in Euclidean norm of all possible solutions.
$\alpha=(K+\rho I)^{-1}\bm{Y}$ which results in the predictor

$f(x)=k_{x}(\bm{X})^{\top}(K+\rho I)^{-1}\bm{Y}$

where $k_{x}(\bm{X})\in\mathbb{R}^{n}$ is the vector with components
$k_{x}(\bm{X})_{i}=k_{x}(x_{i})$. We will compare the generalisation
performance of this predictor with that of its averaged version

$\bar{f}=\bar{k}_{x}(\bm{X})^{\top}(K+\rho
I)^{-1}\bm{Y}\in\overline{\mathcal{H}}.$

To do this we look at the generalisation gap.

###  4.2 Generalisation Gap

The generalisation gap is a quantity that compares the expected test
performances of two predictors on a given task. Given a probability
distribution $\operatorname{\mathbb{P}}$, data
$(X,Y)\sim\operatorname{\mathbb{P}}$ and loss function $l$ defining a
supervised learning task, we define the generalisation gap between two
predictors $f$ and $f^{\prime}$ to be

$\Delta(f,f^{\prime})=\operatorname{\mathbb{E}}[l(f(X),Y)]-\operatorname{\mathbb{E}}[l(f^{\prime}(X),Y)]$

where the expectations are conditional on the given realisations of
$f,f^{\prime}$ 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)+\xi$
for some target function $f^{*}$ where $\xi$ is has mean $0$, finite variance
and is independent of $X$. In this case, the generalisation gap reduces to

$\Delta(f,f^{\prime})=\operatorname{\mathbb{E}}[(f(X)-f^{*}(X))^{2}]-\operatorname{\mathbb{E}}[(f^{\prime}(X)-f^{*}(X))^{2}].$

Clearly, if $\Delta(f,f^{\prime})>0$ then we expect strictly better test
performance from $f^{\prime}$ than $f$.

###  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 a generalisation of [8, Theorem 6] and we will return to this comparison
later. We emphasise that Theorem 1 holds under quite general conditions that
cover many practical applications.

######  Theorem 1.

Let the training data be $\\{(X_{i},Y_{i}):i=1,\dots,n\\}$ i.i.d. with
$Y_{i}=f^{*}(X_{i})+\xi_{i}$ where $X_{i}\sim\mu$,
$f^{*}\in{L_{2}(\mathcal{X},\mu)}$ is $\mathcal{G}$-invariant and
$\\{\xi_{i}:i=1,\dots,n\\}$ are independent of each other and the
$\\{X_{i}\\}$, with $\operatorname{\mathbb{E}}[\xi_{i}]=0$ and
$\operatorname{\mathbb{E}}[\xi_{i}^{2}]=\sigma^{2}<\infty$. Let
$f=\operatorname*{argmin}_{f\in\mathcal{H}}C(f)$ be the solution to Eq. 3 and
let $\bar{f}=\mathcal{O}f\in\overline{\mathcal{H}}$ be the result of applying
feature averaging to $f$, then the generalisation gap with the squared-error
loss satisfies

$\operatorname{\mathbb{E}}[\Delta(f,\bar{f})]\geq\frac{\sigma^{2}\dim_{\text{eff}}(\mathcal{H}_{\scaleobj{0.75}{\perp}})+\operatorname{\mathbb{E}}[f^{*}(X)^{2}j^{\scaleobj{0.75}{\perp}}(X,X)]}{(\sqrt{n}M_{k}+\rho/\sqrt{n})^{2}}$

where each term is non-negative and

$\dim_{\text{eff}}(\mathcal{H}_{\scaleobj{0.75}{\perp}})\coloneqq\operatorname{Tr}(T_{k}^{2})-\operatorname{Tr}((\mathcal{O}T_{k})^{2})=\operatorname{\mathbb{E}}[j^{\scaleobj{0.75}{\perp}}(X,X)]=\sum_{\alpha}\lambda^{2}_{\alpha}\lVert\tilde{e}_{\alpha}^{\scaleobj{0.75}{\perp}}\rVert_{L_{2}(\mathcal{X},\mu)}^{2}\geq
0$

is the _effective dimension_ of $\mathcal{H}_{\scaleobj{0.75}{\perp}}$.

###### Proof.

Let $J^{\scaleobj{0.75}{\perp}}$ be the Gram matrix with components
$J^{\scaleobj{0.75}{\perp}}_{ij}=j^{\scaleobj{0.75}{\perp}}(X_{i},X_{j})$ let
$u\in\mathbb{R}^{n}$ have components $u_{i}=f^{*}(x_{i})$. We can use Lemma 2
to get

$\Delta(f,\bar{f})=\operatorname{\mathbb{E}}[(k_{X}^{\scaleobj{0.75}{\perp}}(\bm{X})^{\top}(K+\rho
I)^{-1}\bm{Y})^{2}|\bm{X},\bm{Y}]$

where $k_{x}^{\scaleobj{0.75}{\perp}}(\bm{X})\in\mathbb{R}^{n}$ with
$k_{x}^{\scaleobj{0.75}{\perp}}(\bm{X})_{i}=k_{x}^{\scaleobj{0.75}{\perp}}(X_{i})$.
Let $\bm{\xi}\in\mathbb{R}^{n}$ have components $\bm{\xi}_{i}=\xi_{i}$ then
one finds

$\displaystyle\operatorname{\mathbb{E}}[\Delta(f,\bar{f})|{}\bm{X}]$
$\displaystyle=\operatorname{\mathbb{E}}[(k_{X}^{\scaleobj{0.75}{\perp}}(\bm{X})^{\top}(K+\rho
I)^{-1}u)^{2}|{}\bm{X}]+\operatorname{\mathbb{E}}[(k_{X}^{\scaleobj{0.75}{\perp}}(\bm{X})^{\top}(K+\rho
I)^{-1}\bm{\xi})^{2}|{}\bm{X}]$ $\displaystyle=u^{\top}(K+\rho
I)^{-1}J^{\scaleobj{0.75}{\perp}}(K+\rho
I)^{-1}u+\sigma^{2}\operatorname{Tr}\left(J^{\scaleobj{0.75}{\perp}}(K+\rho
I)^{-2}\right)$

where the first equality follows because $\bm{\xi}$ has mean 0 and the second
comes from the trace trick.

The first term vanishes in expectation. To see this, first note that it is
non-negative because $J^{\scaleobj{0.75}{\perp}}$ is positive semi-definite,
while at the same time Consider the first term. We have

$u^{\top}(K+\rho I)^{-1}J^{\scaleobj{0.75}{\perp}}(K+\rho
I)^{-1}u=\operatorname{Tr}((K+\rho I)^{-1}J^{\scaleobj{0.75}{\perp}}(K+\rho
I)^{-1}uu^{\top})$

applying Corollary 2 twice and using Lemma 3 with boundedness of the kernel
gives

$u^{\top}(K+\rho I)^{-1}J^{\scaleobj{0.75}{\perp}}(K+\rho
I)^{-1}u\geq\lambda_{\text{min}}((K+\rho
I)^{-1})^{2}\operatorname{Tr}(J^{\scaleobj{0.75}{\perp}}uu^{\top})\geq\frac{u^{\top}J^{\scaleobj{0.75}{\perp}}u}{(Mn+\rho)^{2}}$

so

$\operatorname{\mathbb{E}}[u^{\top}(K+\rho
I)^{-1}J^{\scaleobj{0.75}{\perp}}(K+\rho
I)^{-1}u]\geq\frac{\operatorname{\mathbb{E}}[u^{\top}J^{\scaleobj{0.75}{\perp}}u]}{(Mn+\rho)^{2}}=\frac{\sum_{ij}\operatorname{\mathbb{E}}[f^{*}(X_{i})f^{*}(X_{j})j^{\scaleobj{0.75}{\perp}}(X_{i},X_{j})]}{(Mn+\rho)^{2}}.$

It remains to show that the above vanishes when $i\neq j$. Using Lemma 2 we
have

$\operatorname{\mathbb{E}}[f^{*}(X_{i})f^{*}(X_{j})j^{\scaleobj{0.75}{\perp}}(X_{i},X_{j})]=\operatorname{\mathbb{E}}[f^{*}(X_{i})f^{*}(X_{j})\sum_{\alpha}\lambda_{\alpha}^{2}e^{\scaleobj{0.75}{\perp}}_{\alpha}(X_{i})e^{\scaleobj{0.75}{\perp}}_{\alpha}(X_{j})].$

By Fubini’s theorem, since the counting measure on $\alpha$ is
$\sigma$-finite, we can exchange the expectation and the sum as long as

$\sum_{\alpha}\lambda_{\alpha}^{2}\operatorname{\mathbb{E}}[f^{*}(X_{i})f^{*}(X_{j})e^{\scaleobj{0.75}{\perp}}_{\alpha}(X_{i})e^{\scaleobj{0.75}{\perp}}_{\alpha}(X_{j})]<\infty.$

On the other hand, since $i\neq j$ each term is just
$\operatorname{\mathbb{E}}[f^{*}(X)e^{\scaleobj{0.75}{\perp}}_{\alpha}(X)]^{2}=\langle\iota
f^{*},\tilde{e}_{\alpha}^{\scaleobj{0.75}{\perp}}\rangle_{L_{2}(\mathcal{X},\mu)}^{2}=0$
by the $\mathcal{G}$-invariance of $f^{*}$ and the orthogonality in Lemma 2.

Moving to the second term, we have again by two applications of Corollary 2
and then Lemma 3 with boundedness of the kernel that

$\operatorname{Tr}\left(J^{\scaleobj{0.75}{\perp}}(K+\rho
I)^{-2}\right)\geq\lambda_{\text{min}}\left((K+\rho
I)^{-2}\right)\operatorname{Tr}(J^{\scaleobj{0.75}{\perp}})\geq\frac{\operatorname{Tr}(J^{\scaleobj{0.75}{\perp}})}{(M_{k}n+\rho)^{2}}$

and then

$\displaystyle\frac{1}{n}\operatorname{\mathbb{E}}[\operatorname{Tr}(J^{\scaleobj{0.75}{\perp}})]$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}\left[\sum_{\alpha}\lambda^{2}_{\alpha}e^{\scaleobj{0.75}{\perp}}_{\alpha}(X_{i})e^{\scaleobj{0.75}{\perp}}_{\alpha}(X_{i})\right]$
$\displaystyle=\sum_{\alpha}\lambda^{2}_{\alpha}\lVert\tilde{e}_{\alpha}^{\scaleobj{0.75}{\perp}}\rVert_{L_{2}(\mathcal{X},\mu)}^{2}$
$\displaystyle=\sum_{\alpha}\lambda^{2}_{\alpha}-\sum_{\alpha}\lambda^{2}_{\alpha}\lVert\mathcal{O}\tilde{e}_{\alpha}\rVert_{L_{2}(\mathcal{X},\mu)}^{2}$
$\displaystyle=\operatorname{Tr}(T_{k}^{2})-\operatorname{Tr}(T_{k}^{2}\mathcal{O})$

where we exchange the expectation and sum again using Fubini’s theorem as we
will justify now. Considering the sum in the second line, note that
$\lVert\tilde{e}_{\alpha}\rVert_{L_{2}(\mathcal{X},\mu)}^{2}=1=\lVert\mathcal{O}\tilde{e}_{\alpha}\rVert_{L_{2}(\mathcal{X},\mu)}^{2}+\lVert\tilde{e}_{\alpha}^{\scaleobj{0.75}{\perp}}\rVert_{L_{2}(\mathcal{X},\mu)}^{2}$
by Lemma 2 so the sum converges if $\sum_{i}\lambda_{i}^{2}$ converges.
However, $T_{k}$ is both positive and trace-class from Section 3.1 so
$\lambda_{i}\geq 0$ and $\sum_{i}\lambda_{i}<\infty$ (using Lidskii’s theorem)
so $\sum_{i}\lambda_{i}^{2}$ converges by the comparison test. ∎

Theorem 1 shows that feature averaging is provably beneficial in terms of
generalisation if the mean of the target distribution is invariant. If
$\mathcal{H}$ contains any functions that are not $\mathcal{G}$-invariant then
the lower bound is strictly positive. One might think that, given enough
training examples, the solution $f$ to Eq. 3 would _learn_ to be
$\mathcal{G}$-invariant. Theorem 1 shows that this cannot happen unless the
number of examples dominates the effective dimension of
$\mathcal{H}_{\scaleobj{0.75}{\perp}}$.

Recall the subspace $A$ in Lemma 2. The role of
$\dim_{\text{eff}}(\mathcal{H}_{\scaleobj{0.75}{\perp}})$ mirrors that of
$\dim A$ in [8, Theorem 6] and in the context of the theorem (linear models)
$A$ can be thought of as $\mathcal{H}_{\scaleobj{0.75}{\perp}}$ when $k$ is
the linear kernel. In this sense Theorem 1 is a generalisation of [8, Theorem
6]. It is for this reason that we believe that, although the constant $M_{k}$
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^{\scaleobj{0.75}{\perp}}$, that

$\operatorname{\mathbb{E}}[f^{*}(X)^{2}j^{\scaleobj{0.75}{\perp}}(X,X)]=\int_{\mathcal{X}}f^{*}(y)^{2}k^{\scaleobj{0.75}{\perp}}(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
(5)

and we also have the following.

######  Proposition 2.

$\int_{\mathcal{X}}f^{*}(y)^{2}k^{\scaleobj{0.75}{\perp}}(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)=\int_{\mathcal{X}}f^{*}(y)^{2}\left(k(x,y)^{2}-\bar{k}(x,y)^{2}\right)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$

###### Proof.

Using $k^{\scaleobj{0.75}{\perp}}=k-\bar{k}$

$\displaystyle\int_{\mathcal{X}}f^{*}(y)^{2}k^{\scaleobj{0.75}{\perp}}(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{X}}f^{*}(y)^{2}k(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle\phantom{=}-2\int_{\mathcal{X}}f^{*}(y)^{2}\bar{k}(x,y)k(x,y)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle\phantom{=}+\int_{\mathcal{X}}f^{*}(y)^{2}\bar{k}(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$

while, since $f^{*}$ is $\mathcal{G}$-invariant, $\mu$ is
$\mathcal{G}$-invariant and $\mathcal{G}$ is unimodular (because it is
compact),

$\displaystyle\int_{\mathcal{X}}f^{*}(y)^{2}\bar{k}(x,y)k(x,y)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{X}}\int_{\mathcal{G}}f^{*}(gy)^{2}\mathop{}\\!\mathrm{d}\lambda(g)\bar{k}(x,y)k(x,y)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{X}}\int_{\mathcal{G}}f^{*}(gy)^{2}\mathop{}\\!\mathrm{d}\lambda(g)\bar{k}(x,y)k(x,y)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{X}}f^{*}(y)^{2}\int_{\mathcal{G}}\bar{k}(x,gy)k(x,gy)\mathop{}\\!\mathrm{d}\lambda(g)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{X}}f^{*}(y)^{2}\bar{k}(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$

where the final line follows because $\bar{k}$ is $\mathcal{G}$-invariant. ∎

For intuition, we present a simple special case of Theorem 1. In particular,
the next result shows that Eq. 5 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 $\phi$ of $\mathcal{G}$
explicitly, writing $\phi(g)x$ instead of $gx$.

######  Theorem 3.

Assume the setting and notation of Theorem 1. In addition, let
$\mathcal{X}=\mathbb{S}_{d-1}$ be the unit $d-1$ sphere and let
$\mu=\operatorname{\text{Unif}}(\mathcal{X})$. Let $\mathcal{G}$ act via an
orthogonal representation $\phi$ on $\mathcal{X}$ and define the matrix
$\Phi=\int_{\mathcal{G}}\phi(g)\mathop{}\\!\mathrm{d}\lambda(g)$. Let
$k(x,y)=x^{\top}y$ be the linear kernel and suppose $f^{*}(x)=\theta^{\top}x$
for some $\theta\in\mathbb{R}^{d}$. Then the bound in Theorem 1 becomes

$\operatorname{\mathbb{E}}[\Delta(f,\bar{f})]\geq\frac{1}{(\sqrt{n}+\rho/\sqrt{n})^{2}}\left(\frac{d-\lVert\Phi\rVert_{\text{F}}^{2}}{d^{2}}+\frac{(d-\lVert\Phi\rVert_{\text{F}}^{2})\lVert\theta\rVert_{2}^{2}}{d^{2}(d+2)}\right)$

where $\lVert\cdot\rVert_{\text{F}}$ is the Frobenius norm. The first term in
the parenthesis is exactly
$\dim_{\text{eff}}(\mathcal{H}_{\scaleobj{0.75}{\perp}})$ and the second term
is exactly
$\operatorname{\mathbb{E}}[f^{*}(X)^{2}j^{\scaleobj{0.75}{\perp}}(X,X)]$.

###### Proof.

We will make use of the Einstein convention of summing repeated indices. Since
$\mu$ is finite, by Fubini’s theorem we are free to integrate in any order
throughout the proof. First of all notice that $\sup_{x}k(x,x)=1$ so
$M_{k}=1$. Now observe that

$\bar{k}(x,y)=x^{\top}\int_{\mathcal{G}}\phi(g)y\mathop{}\\!\mathrm{d}\lambda(g)=x^{\top}\Phi
y.$

Then the first term in the numerator becomes

$\displaystyle\dim_{\text{eff}}(\mathcal{H}_{\scaleobj{0.75}{\perp}})$
$\displaystyle=\operatorname{\mathbb{E}}[j^{\scaleobj{0.75}{\perp}}(X,X)]$
$\displaystyle=\operatorname{\mathbb{E}}[j(X,X)]-\operatorname{\mathbb{E}}[\bar{j}(X,X)]$
$\displaystyle=\int_{X}k(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)-\int_{X}\bar{k}(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{X}}x_{a}x_{b}y_{a}y_{b}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)-\int_{X}x_{a}x_{b}y_{c}y_{e}\Phi_{ac}\Phi_{be}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\frac{1}{d}-\frac{1}{d^{2}}\lVert\Phi\rVert_{\text{F}}^{2}.$

Now for the second term. We calculate each term of the right hand side of
Proposition 2 separately. We know that

$f^{*}(x)^{2}k(x,y)^{2}=(\theta^{\top}x)^{2}(x^{\top}y)^{2}=\theta_{a}\theta_{b}y_{c}y_{e}x_{a}x_{b}x_{c}x_{e}.$

Integrating $y$ first, we get

$\displaystyle\int_{\mathcal{X}}f^{*}(x)^{2}k(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{X}}\theta_{a}\theta_{b}y_{c}y_{e}x_{a}x_{b}x_{c}x_{e}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\frac{1}{d}\int_{\mathcal{X}}\theta_{a}\theta_{b}x_{a}x_{b}\mathop{}\\!\mathrm{d}\mu(x)$
$\displaystyle=\frac{1}{d^{2}}\lVert\theta\rVert_{2}^{2}$

Similarly, we find

$\displaystyle\int_{\mathcal{X}}f^{*}(x)^{2}\bar{k}(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{X}}\theta_{a}\theta_{b}x_{a}x_{b}x_{c}x_{e}y_{f}y_{h}\Phi_{cf}\Phi_{eh}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\frac{1}{d}\theta_{a}\theta_{b}\Phi_{cf}\Phi_{ef}\int_{\mathcal{X}}x_{a}x_{b}x_{c}x_{e}\mathop{}\\!\mathrm{d}\mu(x).$

The 4-tensor
$\int_{\mathcal{X}}x_{a}x_{b}x_{c}x_{e}\mathop{}\\!\mathrm{d}\mu(x)$ is
isotropic, so must have the form

$\int_{\mathcal{X}}x_{a}x_{b}x_{c}x_{e}\mathop{}\\!\mathrm{d}\mu(x)=\alpha\delta_{ab}\delta_{ce}+\beta\delta_{ac}\delta_{be}+\gamma\delta_{ae}\delta_{bc}$

(see, e.g. [11]). By symmetry and exchangeability we have
$\alpha=\beta=\gamma$. Then contracting the first two indices gives

$\int_{\mathcal{X}}x_{a}x_{a}x_{c}x_{e}\mathop{}\\!\mathrm{d}\mu(x)=\frac{1}{d}\delta_{ce}=\alpha(d+2)\delta_{ce}$

so $\alpha=\frac{1}{d(d+2)}$ and we end up with

$\int_{\mathcal{X}}f^{*}(x)^{2}\bar{k}(x,y)^{2}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)=\frac{\lVert\theta\rVert_{2}^{2}\lVert\Phi\rVert_{F}^{2}+2\lVert\Phi\theta\rVert_{2}^{2}}{d^{2}(d+2)}=\frac{\lVert\theta\rVert_{2}^{2}(\lVert\Phi\rVert_{F}^{2}+2)}{d^{2}(d+2)}$

where the second equality comes from

$\theta^{\top}\Phi
x=\int_{\mathcal{G}}\theta^{\top}\phi(g)x\mathop{}\\!\mathrm{d}\lambda(g)=\int_{\mathcal{G}}f^{*}(\phi(g)x)\mathop{}\\!\mathrm{d}\lambda(g)=f^{*}(x)=\theta^{\top}x$

for any $x\in\mathcal{X}$. Putting everything together gives the result. ∎

One can confirm that the generalisation gap cannot be negative in Theorem 3
using Jensen’s inequality

$\lVert\Phi\rVert_{\text{F}}^{2}=\left\lVert\int_{\mathcal{G}}\phi(g)\mathop{}\\!\mathrm{d}\lambda(g)\right\rVert^{2}_{\text{F}}\leq\int_{\mathcal{G}}\lVert\phi(g)\rVert_{\text{F}}^{2}\mathop{}\\!\mathrm{d}\lambda(g)=\int_{\mathcal{G}}\operatorname{Tr}(\phi(g)^{\top}\phi(g))\mathop{}\\!\mathrm{d}\lambda(g)=\operatorname{Tr}(I)=d$

because the representation $\phi$ is orthgonal.

The matrix $\Phi$ in Theorem 3 can be computed analytically for various
$\mathcal{G}$ and in the linear setting describes the importance of the
symmetry to the task. For instance, in the simple case that
$\mathcal{G}=S_{d}$ the permutation group on $d$ elements and $\phi$ is the
natural representation in terms of permutation matrices, we have
$\Phi=\frac{1}{d}\bm{1}\bm{1}^{\top}$ where $\bm{1}\in\mathbb{R}^{d}$ is the
vector of all 1s. In this case, since the target is assumed to be
$\mathcal{G}$-invariant, we must have $\theta=t\bm{1}$ for some
$t\in\mathbb{R}$. Specifically, Theorem 3 then asserts

$\operatorname{\mathbb{E}}[\Delta(f,\bar{f})]\geq\frac{(d-1)(dt^{2}+d+2)}{d^{2}(d+2)(\sqrt{n}+\rho/\sqrt{n})^{2}}.$

##  5 Related Work

Incorporating invariance into machine learning models is not a new idea. The
majority of modern applications concern neural networks, but earlier work has
used kernels [10], support vector machines [26] and polynomial feature spaces
[27, 28]. Indeed, early work also considered invariant neural networks [33],
using methods that seem to have been rediscovered in [24]. Modern
implementations include invariant/equivariant convolutional architectures [4,
6] that are inspired by concepts from mathematical physics and harmonic
analysis [14, 5]. Some of these models even enjoy universal approximation
properties [20, 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. [2, 23] propose heuristic arguments for
improved sample complexity of invariant models. [29] build on the work of [34]
to obtain a generalisation bound for certain types of classifiers that are
invariant to a finite set of transformations, while [25] obtain a bound for
models that are invariant to finite permutation groups. The PAC Bayes
formulation is considered in [17, 18].

The above works guarantee only a worst-case improvement and it was not until
very recently that [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 $\mathcal{G}$ invariant linear models without regularisation. This
may turn out to be accessible by a $\rho\to 0^{+}$ limit (the so called
ridgeless limit) of Theorem 1. More importantly, linear regression is
equivalent to kernel regression with the linear kernel. However, the linear
kernel can be unbounded (e.g. on $\mathbb{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 $\mu$-almost-
surely.

Also very recently, [21] analyse the generalisation benefit of invariance in
kernels and random feature models. Our results differ from [21] in some key
aspects. First, [21] focus 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.

##  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 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. 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, the author thanks 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).

##  Appendix A Notation and Definitions

Trace of a linear operator $A:V\to V$ on a inner product space $V$ is defined
by

$\operatorname{Tr}(A)=\sum_{i}\langle Av_{i},v_{i}\rangle$

where the collection $\\{v_{i}\\}$ forms an orthonormal basis of $V$. In this
paper we will only encounter situations in which the basis is countable. This
expressions is independent of the basis. We say $A$ is _trace-class_ if
$\operatorname{Tr}(A)<\infty$.

For any matrix $A\in\mathbb{R}^{n\times n}$, we define $\lVert
A\rVert_{2}=\sup_{x\in\mathbb{R}^{n}}\frac{\lVert Ax\rVert_{2}}{\lVert
x\rVert}$ which is the operator norm induced by the Euclidean norm. For any
symmetric matrix $A$, we denote by $\lambda_{\text{max}}(A)$ and
$\lambda_{\text{min}}(A)$ the largest and smallest eigenvalues of $A$
respectively.

##  Appendix B Useful Results

This section contains some results that are relied upon elsewhere in the
paper.

######  Lemma 1 ([22]).

Let $A,B\in\mathbb{R}^{n\times n}$ and suppose $B$ is symmetric. Define
$A^{\prime}=\frac{1}{2}(A+A^{\top})$, then

$\lambda_{\text{min}}(A^{\prime})\operatorname{Tr}(B)\leq\operatorname{Tr}(AB)\leq\lambda_{\text{max}}(A^{\prime})\operatorname{Tr}(B),$

where $\lambda_{\text{min}}$ and $\lambda_{\text{max}}$ denote the smallest
and largest eigenvalues respectively.

######  Corollary 2.

Let $A,B\in\mathbb{R}^{n\times n}$ and suppose $A$ is symmetric, then

$\lambda_{\text{min}}(A)\operatorname{Tr}(B)\leq\operatorname{Tr}(AB)\leq\lambda_{\text{max}}(A)\operatorname{Tr}(B).$

###### Proof.

Let $B^{\prime}=\frac{1}{2}(B+B^{\top})$, then using Lemma 1 we have

$\lambda_{\text{min}}(A)\operatorname{Tr}(B^{\prime})\leq\operatorname{Tr}(AB^{\prime})\leq\lambda_{\text{max}}(A)\operatorname{Tr}(B^{\prime}).$

On the other hand, $\operatorname{Tr}(B^{\prime})=\operatorname{Tr}(B)$ and

$2\operatorname{Tr}(AB^{\prime})=\operatorname{Tr}(AB)+\operatorname{Tr}(AB^{\top})=\operatorname{Tr}(AB)+\operatorname{Tr}(BA).$

∎

######  Lemma 3.

Let $A\in\mathbb{R}^{n\times n}$, then

$\lVert A\rVert_{2}\leq n\max_{ij}\left|{}A_{ij}\right|{}.$

###### Proof.

Let $a_{i}\in\mathbb{R}^{n}$ be the $i$th column of $A$, then

$\sup_{\lVert x\rVert_{2}=1}\lVert Ax\rVert_{2}=\sup_{\lVert
x\rVert_{2}=1}\sqrt{\sum_{i}(a_{i}^{\top}x)^{2}}\leq\sup_{\lVert
x\rVert_{2}=1}\sqrt{\sum_{i}\lVert a_{i}\rVert_{2}^{2}\lVert
x\rVert_{2}^{2}}\leq\sqrt{\sum_{i}\lVert
a_{i}\rVert_{2}^{2}}\leq\sqrt{n^{2}\max_{ij}A_{ij}^{2}}.$

∎

##  Appendix C Results leading to Lemma 1

Recall from Section 3 the integral operator
$S_{k}:{L_{2}(\mathcal{X},\mu)}\to\mathcal{H}$ defined by

$S_{k}f(x)=\int_{\mathcal{X}}k(x,y)f(y)\mathop{}\\!\mathrm{d}\mu(y)$

with adjoint $\iota:{L_{2}(\mathcal{X},\mu)}\to\mathcal{H}$.

######  Lemma 1.

The image of ${L_{2}(\mathcal{X},\mu)}$ under $S_{k}$ is dense in
$\mathcal{H}$ and $\iota$ is injective.

###### Proof.

By [31, Theorem 4.26] $\lVert f\rVert_{L_{2}(\mathcal{X},\mu)}<\infty$
$\forall f\in\mathcal{H}$ and $S_{k}({L_{2}(\mathcal{X},\mu)})$ is dense in
$\mathcal{H}$ if and only if the inclusion
$\iota:\mathcal{H}\to{L_{2}(\mathcal{X},\mu)}$ is injective. Injectivity of
the inclusion is equivalent to the statement that for any
$f,f^{\prime}\in\mathcal{H}$ the set

$A(f,f^{\prime})=\\{x\in\mathcal{X}:f(x)\neq f^{\prime}(x)\\}$

has $A\neq\varnothing\implies\mu(A)>0$. Continuity implies that for any
$f,f^{\prime}\in\mathcal{H}$, either $f=f^{\prime}$ pointwise or
$A(f,f^{\prime})$ contains an open set. By the support of $\mu$ this implies
$\mu(A)>0$. Thus, $\iota$ is injective. ∎

From [8, Proposition 22] we know that
$\mathcal{O}:{L_{2}(\mathcal{X},\mu)}\to{L_{2}(\mathcal{X},\mu)}$ is well-
defined and that $\lVert\mathcal{O}\rVert\leq 1$. Let the image of
${L_{2}(\mathcal{X},\mu)}$ under $S_{k}$ be $\mathcal{H}_{2}$, then Lemma 1
states that $\overline{\mathcal{H}_{2}}=\mathcal{H}$.

######  Lemma 2.

For any $f\in{L_{2}(\mathcal{X},\mu)}$,
$\mathcal{O}S_{k}f=S_{k}\mathcal{O}f\in\mathcal{H}_{2}$. This implies
$\mathcal{O}:\mathcal{H}_{2}\to\mathcal{H}_{2}$ is well defined.

###### Proof.

$\lambda$ is a Radon measure [13, Theorem 2.27] so is finite because
$\mathcal{G}$ is compact and all $f\in\mathcal{H}$ are bounded so we can apply
Fubini’s theorem [13, Theorem 1.27] as follows: taking
$f\in{L_{2}(\mathcal{X},\mu)}$

$\displaystyle S_{k}\mathcal{O}f(x)$
$\displaystyle=\int_{\mathcal{X}}\int_{\mathcal{G}}k(x,y)f(gy)\mathop{}\\!\mathrm{d}\lambda(g)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{X}}\int_{\mathcal{G}}k(x,g^{-1}y)f(y)\mathop{}\\!\mathrm{d}\lambda(g)\mathop{}\\!\mathrm{d}\mu(y)\quad\text{invariance
of $\mu$}$
$\displaystyle=\int_{\mathcal{X}}\int_{\mathcal{G}}k(gx,y)\mathop{}\\!\mathrm{d}\lambda(g)f(y)\mathop{}\\!\mathrm{d}\mu(y)\quad\text{\lx@cref{creftype~refnum}{eq:kernel-
switch} then unimodularity of $\mathcal{G}$}$
$\displaystyle=\int_{\mathcal{G}}\int_{\mathcal{X}}k(gx,y)f(y)\mathop{}\\!\mathrm{d}\mu(y)\mathop{}\\!\mathrm{d}\lambda(g)\quad\text{Fubini}$
$\displaystyle=\mathcal{O}S_{k}f(x).$

∎

######  Lemma 3.

Let $a,b\in\mathcal{H}_{2}$ with preimages
$a^{\prime},b^{\prime}\in{L_{2}(\mathcal{X},\mu)}$ such that
$a=S_{k}a^{\prime}$ and $b=S_{k}b^{\prime}$, then

$\langle
a,b\rangle_{\mathcal{H}}=\int_{\mathcal{X}}a^{\prime}(x)b^{\prime}(y)k(x,y)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y).$

###### Proof.

The inner product on $\mathcal{H}$ is a bounded linear functional, hence
commutes with integration. We can thus calculate

$\displaystyle\langle a,b\rangle_{\mathcal{H}}$
$\displaystyle=\langle\int_{\mathcal{X}}a^{\prime}(x)k(x,\cdot)\mathop{}\\!\mathrm{d}\mu(x),\int_{\mathcal{X}}b^{\prime}(y)k(y,\cdot)\mathop{}\\!\mathrm{d}\mu(y)\rangle_{\mathcal{H}}$
$\displaystyle=\int_{\mathcal{X}}a^{\prime}(x)b^{\prime}(y)\langle
k_{x},k_{y}\rangle_{\mathcal{H}}\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{X}}a^{\prime}(x)b^{\prime}(y)k(x,y)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y).$

∎

######  Lemma 4.

For any $f,h\in\mathcal{H}_{2}$,

$\langle\mathcal{O}f,h\rangle_{\mathcal{H}}=\langle
f,\mathcal{O}h\rangle_{\mathcal{H}}.$

###### Proof.

Let $f^{\prime}$ and $h^{\prime}$ be the pre-images of $f$ and $h$
respectively under $S_{k}$. Using Lemma 3, Fubini’s theorem [13, Theorem
1.27], the $\mathcal{G}$-invariance of $\mu$ and Eq. 1 we can calculate

$\displaystyle\langle\mathcal{O}f,h\rangle_{\mathcal{H}}$
$\displaystyle=\int_{\mathcal{X}}\int_{\mathcal{G}}f^{\prime}(gx)h^{\prime}(y)k(x,y)\mathop{}\\!\mathrm{d}\lambda(g)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)$
$\displaystyle=\int_{\mathcal{G}}\int_{\mathcal{X}}f^{\prime}(x)h^{\prime}(y)k(g^{-1}x,y)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)\mathop{}\\!\mathrm{d}\lambda(g)\quad\text{$\mathcal{G}$-invariance
of $\mu$}$
$\displaystyle=\int_{\mathcal{G}}\int_{\mathcal{X}}f^{\prime}(x)h^{\prime}(y)k(x,g^{-1}y)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)\mathop{}\\!\mathrm{d}\lambda(g)\quad\text{\lx@cref{creftype~refnum}{eq:kernel-
switch}}$
$\displaystyle=\int_{\mathcal{G}}\int_{\mathcal{X}}f^{\prime}(x)h^{\prime}(gy)k(x,y)\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)\mathop{}\\!\mathrm{d}\lambda(g)\quad\text{$\mathcal{G}$-invariance
of $\mu$}$ $\displaystyle=\langle f,\mathcal{O}h\rangle_{\mathcal{H}}.$

∎

######  Lemma 5.

$\mathcal{O}:\mathcal{H}_{2}\to\mathcal{H}_{2}$ is bounded and
$\lVert\mathcal{O}\rVert\leq 1$.

###### Proof.

Let $f\in\mathcal{H}_{2}$, then using Lemmas 4 and 1 along with Cauchy-Schwarz

$\lVert\mathcal{O}f\rVert_{\mathcal{H}}^{2}=\langle\mathcal{O}f,\mathcal{O}f\rangle_{\mathcal{H}}=\langle
f,\mathcal{O}f\rangle_{\mathcal{H}}\leq\lVert
f\rVert_{\mathcal{H}}\lVert\mathcal{O}f\rVert_{\mathcal{H}}.$

∎

######  Lemma 6.

$f\in\mathcal{H}\implies\mathcal{O}f\in\mathcal{H}$ so
$\mathcal{O}:\mathcal{H}\to\mathcal{H}$ is well defined.

###### Proof.

By Lemma 1, for any $f\in\mathcal{H}$ there is a sequence
$\\{f_{n}\\}\subset\mathcal{H}_{2}$ converging to $f$ in
$\lVert\cdot\rVert_{\mathcal{H}}$. Lemma 2 shows that
$\mathcal{O}:\mathcal{H}_{2}\to\mathcal{H}_{2}$ is well defined, so the
sequence $\\{\mathcal{O}f_{n}\\}\subset\mathcal{H}_{2}$. By Lemma 5 we have
$\lVert\mathcal{O}f_{n}-\mathcal{O}f_{m}\rVert_{\mathcal{H}}\leq\lVert
f_{n}-f_{m}\rVert_{\mathcal{H}}$ and so $\\{\mathcal{O}f_{n}\\}$ is Cauchy. By
completeness of $\mathcal{H}$,
$\bar{f}\coloneqq\lim_{n\to\infty}\mathcal{O}f_{n}\in\mathcal{H}$. Moreover,
$\mathcal{O}$ bounded so is also continuous and we get
$\bar{f}=\lim_{n\to\infty}\mathcal{O}f_{n}=\mathcal{O}\lim_{n\to\infty}f_{n}=\mathcal{O}f$.
∎

######  Lemma 7.

$\mathcal{O}$ is self-adjoint with respect to the inner product on
$\mathcal{H}$.

###### Proof.

We will make use of the continuity of the inner product on $\mathcal{H}$.
First let $h\in\mathcal{H}$, $f\in\mathcal{H}_{2}$. We saw from the proof of
Lemma 6 that $\exists$ sequence $\\{h_{n}\\}\subset\mathcal{H}_{2}$ with limit
$h$ and $\\{\mathcal{O}h_{n}\\}\subset\mathcal{H}_{2}$ with limit
$\mathcal{O}h$. Then
$\langle\mathcal{O}h_{n},f\rangle_{\mathcal{H}}\to\langle\mathcal{O}h,f\rangle_{\mathcal{H}}$
and simultaneously, applying Lemma 4,
$\langle\mathcal{O}h_{n},f\rangle_{\mathcal{H}}=\langle
h_{n},\mathcal{O}f\rangle_{\mathcal{H}}\to\langle
h,\mathcal{O}f\rangle_{\mathcal{H}}$ so the two limits must be equal. Then
assuming instead that $f\in\mathcal{H}$ one can do the same calculation again
arrive at the conclusion. ∎

######  Corollary 8.

$\mathcal{O}:\mathcal{H}\to\mathcal{H}$ is bounded with
$\lVert\mathcal{O}\rVert\leq 1$. Indeed, if $\mathcal{H}$ contains any
$\mathcal{G}$-invariant functions then $\lVert\mathcal{O}\rVert=1$ and if not
then $\lVert\mathcal{O}\rVert=0$.

###### Proof.

Using Lemma 7 we can repeat the calculation in Lemma 4. The second claim
follows from Lemma 1 and the variational representation of the operator norm.
∎

## References

  * [1] Yaser S Abu-Mostafa  “Hints and the VC dimension”  In _Neural Computation_ 5.2 MIT Press, 1993, pp. 278–288
  * [2] Fabio Anselmi et al.  “Unsupervised Learning of Invariant Representations in Hierarchical Architectures”, 2014  arXiv:1311.4158 [cs.CV]
  * [3] Sanjeev Arora et al.  “Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks”  In _Proceedings of the 36th International Conference on Machine Learning_ 97, Proceedings of Machine Learning Research  PMLR, 2019, pp. 322–332  URL: http://proceedings.mlr.press/v97/arora19a.html
  * [4] Taco Cohen and Max Welling  “Group equivariant convolutional networks”  In _International conference on machine learning_ , 2016, pp. 2990–2999
  * [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–9156
  * [6] Taco S Cohen, Mario Geiger, Jonas Köhler and Max Welling  “Spherical cnns”  In _arXiv preprint arXiv:1801.10130_ , 2018
  * [7] Cohn, Donald L  “Measure Theory”  Springer, 2013
  * [8] Bryn Elesedy and Sheheryar Zaidi  “Provably Strict Generalisation Benefit for Equivariant Models”, 2021  arXiv:2102.10333 [stat.ML]
  * [9] Adam Foster, Rattana Pukdee and Tom Rainforth  “Improving Transformation Invariance in Contrastive Representation Learning”  In _arXiv preprint arXiv:2010.09515_ , 2020
  * [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-Verlag, 2005, pp. 841–851
  * [11] Philip G. Hodge  “On Isotropic Cartesian Tensors”  In _The American Mathematical Monthly_ 68.8 Mathematical Association of America, 1961, pp. 793–795
  * [12] Arthur Jacot, Franck Gabriel and Clément Hongler  “Neural tangent kernel: Convergence and generalization in neural networks”  In _Advances in neural information processing systems_ , 2018, pp. 8571–8580
  * [13] Olav Kallenberg  “Foundations of modern probability”  Springer Science & Business Media, 2006
  * [14] Risi Kondor and Shubhendu Trivedi  “On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups”  In _International Conference on Machine Learning_ , 2018, pp. 2747–2755
  * [15] Jaehoon Lee et al.  “Wide neural networks of any depth evolve as linear models under gradient descent”  In _Advances in neural information processing systems_ , 2019, pp. 8572–8583
  * [16] Juho Lee et al.  “Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks”  In _Proceedings of the 36th International Conference on Machine Learning_ 97, Proceedings of Machine Learning Research  PMLR, 2019, pp. 3744–3753  URL: http://proceedings.mlr.press/v97/lee19d.html
  * [17] 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
  * [18] Clare Lyle et al.  “On the Benefits of Invariance in Neural Networks”, 2020  arXiv:2005.00178 [cs.LG]
  * [19] Jonathan H Manton and Pierre-Olivier Amblard  “A primer on reproducing kernel hilbert spaces”  In _arXiv preprint arXiv:1408.0952_ , 2014
  * [20] Haggai Maron, Ethan Fetaya, Nimrod Segol and Yaron Lipman  “On the Universality of Invariant Networks”  In _International Conference on Machine Learning_ , 2019, pp. 4363–4371
  * [21] Song Mei, Theodor Misiakiewicz and Andrea Montanari  “Learning with invariances in random features and kernel models”  In _arXiv preprint arXiv:2102.13219_ , 2021
  * [22] T. Mori  “Comments on "A matrix inequality associated with bounds on solutions of algebraic Riccati and Lyapunov equation" by J.M. Saniuk and I.B. Rhodes”  In _IEEE Transactions on Automatic Control_ 33.11, 1988, pp. 1088–  DOI: 10.1109/9.14428
  * [23] 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–1566
  * [24] Siamak Ravanbakhsh, Jeff Schneider and Barnabas Poczos  “Equivariance through parameter-sharing”  In _International Conference on Machine Learning_ , 2017, pp. 2892–2901  PMLR
  * [25] Akiyoshi Sannai and Masaaki Imaizumi  “Improved Generalization Bound of Group Invariant / Equivariant Deep Networks via Quotient Feature Space”, 2019  arXiv:1910.06552 [stat.ML]
  * [26] Bernhard Schölkopf, Chris Burges and Vladimir Vapnik  “Incorporating Invariances in Support Vector Learning Machines”  Springer, 1996, pp. 47–52
  * [27] 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.94CH3440-5)_ 2, 1994, pp. 387–390 vol.2
  * [28] Hanns Schulz-Mirbach  “On the existence of complete invariant feature spaces in pattern recognition”  In _International Conference On Pattern Recognition_ , 1992, pp. 178–178  Citeseer
  * [29] Jure Sokolic, Raja Giryes, Guillermo Sapiro and Miguel Rodrigues  “Generalization error of invariant classifiers”  In _Artificial Intelligence and Statistics_ , 2017, pp. 1094–1103
  * [30] James S Spencer, David Pfau, Aleksandar Botev and WMC Foulkes  “Better, Faster Fermionic Neural Networks”  In _arXiv preprint arXiv:2011.07125_ , 2020
  * [31] Ingo Steinwart and Andreas Christmann  “Support Vector Machines”, Information science and statistics  Springer, 2008
  * [32] Marysia Winkels and Taco S Cohen  “3D G-CNNs for pulmonary nodule detection”  In _arXiv preprint arXiv:1804.04656_ , 2018
  * [33] Jeffrey Wood and John Shawe-Taylor  “Representation theory and invariant neural networks”  In _Discrete applied mathematics_ 69.1-2 Elsevier, 1996, pp. 33–60
  * [34] Huan Xu and Shie Mannor  “Robustness and generalization”  In _Machine learning_ 86.3 Springer, 2012, pp. 391–423
  * [35] Dmitry Yarotsky  “Universal approximations of invariant maps by neural networks”, 2018  arXiv:1804.10306 [cs.NE]
  * [36] Manzil Zaheer et al.  “Deep sets”  In _Advances in neural information processing systems_ , 2017, pp. 3391–3401