# Kernel interpolation generalizes poorly

Yicheng Li, Haobo Zhang
Center for Statistical Science, Department of Industrial Engineering, Tsinghua
University,
100084, Beijing, China
{liyc22<EMAIL_ADDRESS>
&Qian Lin
Center for Statistical Science, Department of Industrial Engineering, Tsinghua
University,
100084, Beijing, China
<EMAIL_ADDRESS>

###### Abstract

One of the most interesting problems in the recent renaissance of the studies
in kernel regression might be whether kernel interpolation can generalize
well, since it may help us understand the ‘benign overfitting phenomenon’
reported in the literature on deep networks. In this paper, under mild
conditions, we show that for any $\varepsilon>0$, the generalization error of
kernel interpolation is lower bounded by $\Omega(n^{-\varepsilon})$. In other
words, the kernel interpolation generalizes poorly for a large class of
kernels. As a direct corollary, we can show that overfitted wide neural
networks defined on the sphere generalize poorly.

_K_ eywords Kernel interpolation $\cdot$ Kernel ridge regression $\cdot$
Generalization $\cdot$ Neural network.

##  1 Introduction

The ‘benign overfitting phenomenon’ that over-parametrized neural networks can
interpolate noisy data but also generalize well is widely observed in the
literature on neural networks [1, 2, 3]. This observation challenges the
traditional ‘bias-variance trade-off’ doctrine in statistical learning theory
[4] where models interpolating noisy data are supposed to generalize poorly.
Since Jacot et al. [5] illustrated that when the width of neural network tends
to infinity, the dynamics of the gradient flow when training the neural
network can be approximated by the gradient flow of a kernel regression with
respect to the time-invariant neural tangent kernel, we have experienced a
renaissance of studies of kernel regression. For example, since a number of
works [6, 7] have shown that a wide neural network can overfit any data,
whether neural kernel interpolation can generalize might be one of the most
important questions towards a theoretical explanation of the ‘benign
overfitting phenomenon’.

Suppose that we have observed the given samples
$(x_{1},y_{1}),\dots,(x_{n},y_{n})$ and perform regression on $\mathcal{H}$, a
reproducing kernel Hilbert space (RKHS) associated with some kernel $k$.
Traditional results [8, 9] in regularized kernel regression, namely kernel
ridge regression, showed that

$\displaystyle\hat{f}_{\lambda}$
$\displaystyle=\operatorname*{arg\,min}_{f\in\mathcal{H}}\left[\frac{1}{n}\sum_{i=1}^{n}\\{y_{i}-f(x_{i})\\}^{2}+\lambda\norm{f}_{\mathcal{H}}^{2}\right],$
(1)

where $\norm{\cdot}_{\mathcal{H}}$ is the corresponding norm, is minimax
optimal if $\lambda$ is chosen properly according to the sample size;
subsequent works [10, 11] have also extended the optimality results to more
general settings. In the limiting case where $\lambda\to 0$, we obtain the
kernel minimum-norm interpolation [12, Section 12.5]

$\displaystyle\hat{f}_{\mathrm{inter}}=\hat{f}_{0}=\operatorname*{arg\,min}_{f\in\mathcal{H}}\norm{f}_{\mathcal{H}}\mbox{\quad
subject to\quad}f(x_{i})=y_{i}\quad(i=1,\dots,n).$ (2)

However, there has been little discussion about the generalization performance
of $\hat{f}_{\mathrm{inter}}$.

Recently, many papers have considered the generalization ability of kernel
regression in the high dimensional regime where the dimension $d$ of the
inputs grows with the sample size $n$. In this regime, the so-called ‘benign
overfitting phenomenon’ has been reported and generalization error bounds are
provided under certain additional assumptions. Liang and Rakhlin [13] proved
that kernel interpolation can generalize when $n\asymp d$ and the data have a
low-dimensional structure; Liang et al. [14] showed similar results when
$n=d^{l}$ and $l>1$ is not an integer. Considering a square-integrable
regression function, Ghorbani et al. [15] and its follow-up work Mei and
Montanari [16] showed that kernel methods can fit at most a degree-$l$
polynomial if $n=d^{l}$ for $l>1$; Ghosh et al. [17] proved similar results
for the gradient flow with early-stopping.

On the other hand, under the traditional fixed dimension setting, the
inconsistency of interpolation has been widely observed and believed [18].
Recently, several works claimed the inconsistency of kernel interpolation.
Rakhlin and Zhai [19] showed that the kernel interpolation
$\hat{f}_{\mathrm{inter}}$ with Laplace kernel is not consistent in odd
dimensions; Buchholz [20] then extended the result to kernels associated with
the Sobolev space $H^{s}$ for $d/2<s<3d/4$ and all (fixed) dimensions;
assuming that data are located in uniformly spaced grids, Beaglehole et al.
[21] established inconsistency results for a class of shift-invariant periodic
kernels with mild spectral assumptions. Since the neural tangent kernels are
not included in all the aforementioned situations, it is unclear if these
works can help us understand the ‘benign overfitting phenomenon’ in neural
network.

In this paper, we show that under mild assumptions, the kernel interpolation
$\hat{f}_{\mathrm{inter}}$ generalizes poorly in fixed dimensions. To be
precise, we prove that for any $\varepsilon>0$, the generalization error

$\displaystyle\norm{\hat{f}_{\mathrm{inter}}-f^{*}}^{2}_{L^{2}}=\Omega(n^{-\varepsilon})$

holds with high probability, where $f^{*}$ is the underlying regression
function. In subsection 2.2, we further illustrate that our class of kernels
not only include the aforementioned kernels but also include the neural
tangent kernels. In particular, we rigorously show that overfitted wide neural
networks on spheres generalize poorly.

Throughout this paper, we use $L^{p}(\mathcal{X},\differential\mu)$ to
represent the Lebesgue $L^{p}$ spaces, where the corresponding norm is denoted
by $\norm{\cdot}_{L^{p}}$. For a function $f$ on $\mathcal{X}$, we also define
the sup-norm $\norm{f}_{\infty}=\sup_{x\in\mathcal{X}}\absolutevalue{f(x)}$,
which should be distinguished from the $L^{\infty}$-norm. We use the
asymptotic notations $O(\cdot)$, $o(\cdot)$, and $\Omega(\cdot)$. We also
denote $a_{n}\asymp b_{n}$ iff $a_{n}=O(b_{n})$ and $a_{n}=\Omega(b_{n})$.

##  2 Preliminaries

###  2.1 Reproducing kernel Hilbert space

Let a compact set $\mathcal{X}\subset\mathbb{R}^{d}$ be the input space. We
fix a continuous positive definite kernel $k$ over $\mathcal{X}$ and denote by
$\mathcal{H}$ the separable reproducing kernel Hilbert space associated with
$k$. Let $\rho$ be a probability measure on $\mathcal{X}\times\mathbb{R}$ and
$\mu$ be the marginal probability measure of $\rho$ on $\mathcal{X}$. We
denote by $L^{2}=L^{2}(\mathcal{X},\differential\mu)$ the Lebesgue space for
short. Then, it is known [9, 22] that the natural embedding
$S_{\mu}:\mathcal{H}\to L^{2}$ is a Hilbert-Schmidt operator with the Hilbert-
Schmidt norm
$\norm{S_{\mu}}_{\mathrm{HS}}^{2}\leq\kappa^{2}=\sup_{x\in\mathcal{X}}k(x,x)$.
Moreover, denoting by $S_{\mu}^{*}:L^{2}\to\mathcal{H}$ the adjoint operator
of $S_{\mu}$, the operator $T=S_{\mu}S_{\mu}^{*}:L^{2}\to L^{2}$ is an
integral operator given by

$\displaystyle(Tf)(x)=\int_{\mathcal{X}}k(x,y)f(y)\differential\mu(y).$ (3)

Then, it is well known [8, 22] that $T$ is self-adjoint, positive and trace-
class (thus compact) with trace norm $\norm{T}_{1}\leq\kappa^{2}$. Thus, the
spectral theorem of compact self-adjoint operators and Mercer’s theorem [22]
yield that

$\displaystyle T=\sum_{i\in
N}\lambda_{i}\left\langle{\cdot,e_{i}}\right\rangle_{L^{2}}e_{i},\quad\quad
k(x,y)=\sum_{i\in N}\lambda_{i}e_{i}(x)e_{i}(y),$ (4)

where $N\subseteq\mathbb{N}$ is an index set,
$\left\\{\lambda_{i}\right\\}_{i\in N}$ is the set of positive eigenvalues of
$T$ in descending order, $e_{i}$ is the corresponding eigenfunction which is
chosen to be continuous, and the convergence of the kernel expansion is
absolute and uniform. In addition, $\left\\{e_{i}\right\\}_{i\in N}$ forms an
orthonormal basis of $\overline{\operatorname{Ran}S_{\mu}}\subseteq L^{2}$ and
$\left\\{\lambda_{i}^{1/2}e_{i}\right\\}_{i\in N}$ forms an orthonormal basis
of $\overline{\operatorname{Ran}S_{\mu}^{*}}\subseteq\mathcal{H}$.

The eigenvalues $\lambda_{i}$ characterize the span of the reproducing kernel
Hilbert space and the interplay between $\mathcal{H}$ and $\mu$. We will
assume $N=\mathbb{N}$ and impose the following polynomial eigenvalue decay
condition:

######  Assumption 1 (Eigenvalue decay).

There are some $\beta>1$ and constants $c_{1},c_{2}>0$ such that

$\displaystyle c_{1}i^{-\beta}\leq\lambda_{i}\leq
c_{2}i^{-\beta}\quad(i=1,2,\dots),$ (5)

where $\lambda_{i}$ is the eigenvalue of $T$ defined in (4).

This assumption is quite standard in the literature [8, 10, 23, 11, 24]. We
also remark that the upper bound in (5) enables us to provide upper bounds for
the convergence rate, while the lower bound is essential for the minimax lower
bound [8] and also for our lower bound. This assumption is satisfied by
commonly considered kernels including kernels associated with Sobolev RKHS
(see Example 2.1) and neural tangent kernels on spheres [25].

###  2.2 The embedding index $\alpha_{0}$ of an RKHS

The decomposition (4) also allows us to introduce the following interpolation
spaces [22, 11, 24]. For $s\geq 0$, we define the fractional power
$T^{s}:L^{2}\to L^{2}$ by

$\displaystyle T^{s}(f)$ $\displaystyle=\sum_{i\in
N}\lambda_{i}^{s}\left\langle{f,e_{i}}\right\rangle_{L^{2}}e_{i}$ (6)

and define the interpolation space $[\mathcal{H}]^{s}$ by

$\displaystyle[\mathcal{H}]^{s}=\operatorname{Ran}T^{s/2}=\left\\{\sum_{i\in
N}a_{i}\lambda_{i}^{s/2}e_{i}~{}\Big{|}~{}\sum_{i\in
N}a_{i}^{2}<\infty\right\\}\subseteq L^{2},$ (7)

which is equipped with the norm

$\displaystyle\norm{\sum_{i\in
N}a_{i}\lambda_{i}^{s/2}e_{i}}_{[\mathcal{H}]^{s}}=\left(\sum_{i\in
N}a_{i}^{2}\right)^{1/2}.$ (8)

One may easily verify that $[\mathcal{H}]^{s}$ is also a separable Hilbert
space and $\left\\{\lambda_{i}^{s/2}e_{i}\right\\}_{i\in N}$ forms an
orthonormal basis of it. It is clear that we have
$[\mathcal{H}]^{0}=\overline{\operatorname{Ran}S_{\mu}}\subseteq L^{2}$ and
$[\mathcal{H}]^{1}=\overline{\operatorname{Ran}S_{\mu}^{*}}\subseteq\mathcal{H}$.
There are also compact inclusions
$[\mathcal{H}]^{s_{1}}\hookrightarrow[\mathcal{H}]^{s_{2}}$ for
$s_{1}>s_{2}\geq 0$.

Furthermore, we say $\mathcal{H}$ has an embedding property of order
$\alpha\in(0,1]$ if $[\mathcal{H}]^{\alpha}$ can be continuously embedded into
$L^{\infty}(\mathcal{X},\differential\mu)$, that is, the operator norm

$\norm{[\mathcal{H}]^{\alpha}\hookrightarrow
L^{\infty}(\mathcal{X},\mu)}=M_{\alpha}<\infty.$ (9)

Fischer and Steinwart [11, Theorem 9] shows that

$\displaystyle\norm{[\mathcal{H}]^{\alpha}\hookrightarrow
L^{\infty}(\mathcal{X},\mu)}=\norm{k^{\alpha}_{\mu}}_{L^{\infty}},$ (10)

where $\norm{k^{\alpha}_{\mu}}_{L^{\infty}}$ is the $L^{\infty}$-norm of the
$\alpha$-power of $k$ given by

$\displaystyle\norm{k^{\alpha}_{\mu}}_{L^{\infty}}^{2}=\operatorname*{ess~{}sup}_{x\in\mathcal{X},~{}\mu}\sum_{i\in
N}\lambda_{i}^{\alpha}e_{i}(x)^{2}.$ (11)

Since we have assumed that $\sup_{x\in\mathcal{X}}k(x,x)\leq\kappa^{2}$, we
know that (9) holds for $\alpha=1$, i.e., any $\mathcal{H}$ associated with a
bounded kernel function has the embedding property of order $1$. By the
inclusion relation of interpolation spaces, it is clear that if $\mathcal{H}$
has the embedding property of order $\alpha$, then it has the embedding
properties of order $\alpha^{\prime}$ for any $\alpha^{\prime}\geq\alpha$.
Thus, we may introduce the following definition

######  Definition 2.1.

The embedding index $\alpha_{0}$ of an RKHS $\mathcal{H}$ is defined by

$\displaystyle\alpha_{0}=\inf\left\\{\alpha:\norm{[\mathcal{H}]^{\alpha}\hookrightarrow
L^{\infty}(\mathcal{X},\mu)}<\infty\right\\}.$ (12)

It is shown in Steinwart et al. [10] and Fischer and Steinwart [11, Lemma 10]
that $\alpha_{0}\geq\beta$ and the equality holds if the eigenfunctions are
uniformly bounded ( i.e. $\sup_{i\in N}\norm{e_{i}}_{L^{\infty}}<\infty$).
Throughout this paper, we make the following assumption.

######  Assumption 2 (Embedding index).

The embedding index $\alpha_{0}=1/\beta$, where $\beta$ is the eigenvalue
decay in (5).

######  Remark 2.2.

Many RKHSs satisfy the embedding index condition. We list several examples
below:

######  Example 2.1 (Sobolev spaces).

Let $\mathcal{X}\subset\mathbb{R}^{d}$ be a bounded domain with smooth
boundary and suppose $\mu$ is induced by the Lebesgue measure. The Sobolev
space $H^{s}(\mathcal{X})$ (for a definition, see e.g., Adams and Fournier
[26]) is a reproducing kernel Hilbert space if $s>d/2$. Moreover, it can be
shown [11] that $H^{s}(\mathcal{X})$ satisfies Assumption 1 with $\beta=2s/d$,
and the interpolation space $[H^{s}(\mathcal{X})]^{\alpha}\cong H^{\alpha
s}(\mathcal{X})$. By the Sobolev embedding theorem [26], if $\alpha s>d/2$,
i.e., $\alpha>d/(2s)=\beta^{-1}$, we have

$\displaystyle H^{s\alpha}\hookrightarrow
C^{0,\theta}(\mathcal{X})\hookrightarrow
L^{\infty}(\mathcal{X},\differential\mu),$ (13)

where $C^{0,\theta}(\mathcal{X})$ is the Hölder space and $0<\theta<2\alpha
s/d$. It shows that Assumption 2 is satisfied.

######  Example 2.2 (Translation invariant periodic kernel).

Let $\mathcal{X}=[-\pi,\pi)^{d}$ and $\mu$ be the uniform distribution on
$\mathcal{X}$. Suppose that the kernel satisfies
$k(x,y)=f(x-y\bmod[-\pi,\pi)^{d})$, where we denote
$a\bmod[-\pi,\pi)=\left\\{(a+\pi)\bmod 2\pi\right\\}-\pi\in[-\pi,\pi)$ and
$x-y\bmod[-\pi,\pi)^{d}$ is understood to be element-wise. Then, it is shown
in Beaglehole et al. [21] that the Fourier basis
$\phi_{m}(x)=e^{i\left\langle{m,x}\right\rangle},~{}m\in\mathbb{Z}^{d}$ are
eigenfunctions of $T$. Since $\\{\phi_{m}\\}$ are uniformly bounded,
Assumption 2 is satisfied.

######  Example 2.3 (Dot-product kernel on spheres).

Let $\mathcal{X}=\mathbb{S}^{d-1}\subset\mathbb{R}^{d}$ be the unit sphere and
assume that $\mu$ is the uniform distribution on $\mathbb{S}^{d-1}$. Let $k$
be a dot-product kernel, that is, $k(x,y)=f(\left\langle{x,y}\right\rangle)$
for some function $f$. Then, it is well known [27] that $k$ can be decomposed
using the spherical harmonics $Y_{n,l}$ by

$\displaystyle
k(x,y)=\sum_{n=0}^{\infty}\mu_{n}\sum_{l=1}^{a_{n}}Y_{n,l}(x)Y_{n,l}(y),$ (14)

where $a_{n}$ is the dimension of order-$n$ homogeneous harmonic polynomials
and $\mu_{n}$ is an eigenvalue of $T$ with multiplicity $a_{n}$. Assuming the
polynomial eigenvalue decay $\mu_{n}\asymp n^{-(d-1)\beta}$, it is shown in
Zhang et al. [28] that the embedding index $\alpha_{0}=1/\beta$ and thus
Assumption 2 holds.

###  2.3 Kernel ridge regression

Suppose that we have observed $n$ i.i.d. samples
$(x_{1},y_{1}),\dots,(x_{n},y_{n})$ from $\rho$. We denote by
$X=(x_{1},\dots,x_{n})$ the sample inputs and
$Y=(y_{1},\dots,y_{n})^{\mathrm{\scriptscriptstyle T}}$. Thanks to the
representer theorem (see e.g., Andreas Christmann [9]), we could solve the
optimization problem (1) explicitly:

$\displaystyle\hat{f}_{\lambda}(x)$
$\displaystyle=\mathbb{K}(x,X)\left\\{\mathbb{K}(X,X)+n\lambda\right\\}^{-1}Y=\frac{1}{n}\mathbb{K}(x,X)(K+\lambda)^{-1}Y$
(15)

where $\mathbb{K}(x,X)=\left(k(x,x_{1}),\dots,k(x,x_{n})\right)$,
$\mathbb{K}(X,X)=\big{(}k(x_{i},x_{j})\big{)}_{n\times n}$ and
$K=\mathbb{K}(X,X)/n$ is the normalized kernel matrix. Similarly, we also have
an explicit formula for the kernel interpolation [12, Section 12.5]:

$\displaystyle\hat{f}_{\mathrm{inter}}(x)$
$\displaystyle=\mathbb{K}(x,X)\mathbb{K}(X,X)^{-1}Y=\frac{1}{n}\mathbb{K}(x,X)K^{-1}Y.$
(16)

Here we notice that (16) is well-defined since we have assumed that $k$ is
positive definite and thus $K$ is invertible. For conditions and examples of
positive definite kernels, we refer to e.g., Wendland [29].

In the last two decades, the theories of integral operators and empirical
processes are utilized to understand the generalization ability of
$\hat{f}_{\lambda}(x)$ from various aspects (e.g., Caponnetto and De Vito [8],
Fischer and Steinwart [11], Li et al. [24]). One of the essential steps in
these works is an integral operator interpretation of the formula (15). More
precisely, they introduced the sampling operator
$K_{x}:\mathbb{R}\to\mathcal{H}$ given by $K_{x}y=yk(x,\cdot)$, their adjoint
operator $K_{x}^{*}:\mathcal{H}\to\mathbb{R}$ given by $K_{x}^{*}f=f(x)$ and
the sample covariance operator $T_{X}:\mathcal{H}\to\mathcal{H}$ given by

$\displaystyle T_{X}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}K_{x_{i}}K_{x_{i}}^{*}.$ (17)

With these operators, there is an alternative expression of
$\hat{f}_{\lambda}(x)$:

$\displaystyle\hat{f}_{\lambda}=(T_{X}+\lambda)^{-1}g_{Z},$ (18)

where $g_{Z}=n^{-1}(\sum_{i=1}^{n}K_{x_{i}}y_{i})\in\mathcal{H}$.

##  3 Theoretical Results

###  3.1 Main theorem

To state the main theorem, we need two more mild conditions on the kernel $k$
and the noise $y-f_{\rho}^{*}(x)$.

######  Assumption 3.

The kernel $k$ is Hölder-continuous, that is, there exists some $s\in(0,1]$
and $L>0$ such that

$\displaystyle\absolutevalue{k(x_{1},x_{2})-k(y_{1},y_{2})}\leq
L\norm{(x_{1},x_{2})-(y_{1},y_{2})}_{\mathbb{R}^{d\times d}}^{s},\quad\forall
x_{1},x_{2},y_{1},y_{2}\in\mathcal{X}.$ (19)

######  Assumption 4 (Noise).

The conditional variance of the noise satisfies that

$\displaystyle
E_{(x,y)\sim\rho}\left[\left\\{y-f^{*}_{\rho}(x)\right\\}^{2}\mid
x\right]\geq\sigma^{2}>0,\quad\mu\text{-a.e. }x\in\mathcal{X}.$ (20)

Assumption 3 requires that $k$ is Hölder continuous and Assumption 4 simply
requires that the noise is non-vanishing. It is clear that both these
assumptions are quite mild. For example, Assumption 3 holds for the Laplacian
kernels, RBF kernels, neural tangent kernels, etc.; Assumption 4 holds for the
usual regression models $y=f^{*}(x)+\epsilon$ where $\epsilon$ is an
independent non-zero noise.

######  Theorem 3.1.

Suppose that the Assumptions 1,2,3 and 4 hold. There is an absolute constant
$c>0$ such that for any $\varepsilon>0$ and any $\delta\in(0,1)$, when $n$ is
sufficiently large (depending on $\varepsilon$ and $\delta$), one has that

$\displaystyle
E\left(\norm{\hat{f}_{\mathrm{inter}}-f^{*}_{\rho}}_{L^{2}}^{2}\mid
X\right)\geq c\sigma^{2}n^{-\varepsilon}$

holds with probability at least $1-\delta$ with respect to the random samples.

######  Remark 3.2.

In Theorem 3.1, since the sufficiently large $n$ depends on $\varepsilon$ and
$\delta$, the statement can not imply the inconsistency of kernel
interpolation. Nevertheless, this theorem actually suggests that for a fairly
large class of positive definite kernels, one can not expect that the kernel
interpolation can generalize well.

###  3.2 Discussion

The ‘benign overfitting phenomenon’ might be one of the most puzzling
observations reported in the literature on neural networks. Since Jacot et al.
[5] introduced the neural tangent kernel, it has become a common strategy to
study the wide neural network through analyzing the kernel regression. Thus,
the ‘benign overfitting phenomenon’ raised a natural question that whether the
kernel interpolations, especially the neural tangent kernel interpolation, can
generalize well?

There are few works [19, 20, 21] showed that the kernel interpolation
generalized poorly in various settings. For example, Rakhlin and Zhai [19]
showed that when the dimension $d$ is a fixed odd number, the Laplace kernel
interpolation generalizes poorly for random observation with Rademacher noise;
Buchholz [20] considered the regression with respect to the kernel associated
with the Sobolev space $H^{s}$ and showed that the corresponding kernel
interpolation generalizes poorly if $d/2<s<3d/4$; Beaglehole et al. [21]
further showed that the kernel interpolation with respect to the periodical
translation invariant kernel generalizes poorly for the grid data. However, to
the best of our knowledge, the poor generalization ability of the NTK
interpolation has been only obtained for one dimensional grid data in Lai et
al. [30].

Theorem 3.1 states that for any kernel $k$ satisfying that the embedding index
$\alpha_{0}$ of the RKHS associated to $k$ equals to $1/\beta$, the inverse of
the eigen-decay rate, the corresponding kernel interpolation generalized
poorly. Note that the listed examples in Section 2.2 clearly contains all the
kernels appeared in Buchholz [20], Beaglehole et al. [21], Rakhlin and Zhai
[19]. Thus, it is clear that our result is more general. Moreover, our result
also applies to the neural tangent kernel (NTK) on spheres [25, 31], which is
not covered in either of the previous works. Consequently, we could assert
that the neural tangent kernel interpolation and the overfitted wide neural
network generalized poorly, a statement contradicts to the widely observed
‘benign overfitting phenomenon’. Thus, our result suggests that we may need to
explain the ‘benign overfitting phenomenon’ from other perspective.

###  3.3 Proof sketch

It is clear that the generalization error of kernel ridge regression
(including the interpolation case of $\lambda=0$) is lower bounded by the
variance term $V(\lambda)$, i.e.,

$\displaystyle E\left(\norm{\hat{f}_{\lambda}-f^{*}_{\rho}}^{2}_{L^{2}}\mid
X\right)\geq
V(\lambda)=\frac{\sigma^{2}}{n^{2}}\int_{\mathcal{X}}\mathbb{K}(x,X)(K+\lambda)^{-2}\mathbb{K}(X,x)\differential\mu(x).$

Let us rewrite $V(\lambda)$ in the following operator form:

$\displaystyle
V(\lambda)=\frac{\sigma^{2}}{n}\int_{\mathcal{X}}\norm{(T_{X}+\lambda)^{-1}k(x,\cdot)}_{L^{2},n}^{2}\differential\mu(x),$
(21)

where $\norm{f}_{L^{2},n}^{2}=n^{-1}\\{\sum_{i=1}^{n}f(x_{i})^{2}\\}$. We then
invoke an important observation appeared in Li et al. [24] which claims that
for $\lambda=\Omega(n^{-1/2})$,

$\displaystyle
V(\lambda)\approx\frac{\sigma^{2}}{n}\int_{\mathcal{X}}\norm{(T+\lambda)^{-1}k(x,\cdot)}_{L^{2},n}^{2}\differential\mu(x)\approx\frac{\sigma^{2}}{n}\int_{\mathcal{X}}\norm{(T+\lambda)^{-1}k(x,\cdot)}_{L^{2}}^{2}\differential\mu(x)\asymp\frac{\sigma^{2}\lambda^{-1/\beta}}{n}.$
(22)

However, the requirement that $\lambda=\Omega(n^{-1/2})$ is far from enough to
show the nearly constant lower bound. As one of our major technical
contributions in this paper, we sharpen the estimation by the embedding index
assumption and prove the approximation (22) actually holds for $\lambda\asymp
n^{-\beta+\epsilon}$ for any $\epsilon>0$. Combining with the elementary
observation $V(0)\geq V(\lambda)$, we get the desired claim. We refer to the
supplementary material for a complete proof.

##  4 Application to neural networks

Suppose that we have observed $n$ i.i.d. samples
$(x_{1},y_{1}),\dots,(x_{n},y_{n})$ from $\rho$. For simplicity, we further
assume that the marginal distribution $\mu$ of $\rho$ is the uniform
distribution on the unit sphere $\mathbb{S}^{d-1}$. We use a two-layer neural
network of width $m$ to perform the regression on $(x_{i},y_{i})$’s. More
precisely, we consider the following two-layer neural network:

$\displaystyle
f(x;\theta)=\sqrt{\frac{2}{m}}\sum_{r=1}^{m}a_{r}\sigma\left(w_{r}^{\mathrm{\scriptscriptstyle
T}}x\right),$ (23)

where $\sigma(x)=\max(x,0)$ is the ReLU activation and
$\theta=(w_{1},\dots,w_{m},a_{1},\dots,a_{m})$ are the parameters. With
$\theta$ randomly initialized as $\theta(0)$, we consider the training process
given by the gradient flow $\dot{\theta}(t)=-\partial L/\partial\theta$, where
the loss function is

$\displaystyle
L(\theta)=\frac{1}{2n}\sum_{i=1}^{n}\left\\{y_{i}-f(x_{i};\theta)\right\\}^{2}.$
(24)

Then, when the network is over-parametrized, namely $m$ is large, the theory
of lazy training (see e.g., Lai et al. [30], Lee et al. [32]) shows that the
trained network $\hat{f}^{\mathrm{NN}}_{t}(x)=f(x;\theta(t))$ can be
approximated by a kernel gradient method with respect the following neural
tangent kernel

$\displaystyle
k_{\mathrm{NT}}(x,y)=\frac{2}{\pi}\left(\pi-\arccos\left\langle{x,y}\right\rangle\right)\left\langle{x,y}\right\rangle+\frac{1}{\pi}(1-\left\langle{x,y}\right\rangle^{2})^{1/2}.$
(25)

Particularly, as $t\to\infty$, the network output can be approximated by
kernel interpolation. The following result is a corollary of Lai et al. [30,
Proposition 3.2].

######  Proposition 4.1.

Suppose that we initialize the neural network symmetrically, i.e., the width
$m=2l$ and independently initialize $a_{r}(0),~{}w_{r}(0)\sim N(0,1)$ and
$a_{l+r}(0)=-a_{r}(0)$, $w_{l+r}(0)=w_{r}(0)$ for $r=1,\dots,l$. Then, for any
$\delta\in(0,1)$, when $m$ is sufficiently large, with probability at least
$1-\delta$ one has

$\displaystyle\limsup_{t\to\infty}\sup_{x\in\mathbb{S}^{d-1}}\absolutevalue{\hat{f}^{\mathrm{NN}}_{t}(x)-\hat{f}_{\mathrm{inter}}^{\mathrm{NTK}}(x)}=o_{m}(1),$
(26)

where $\hat{f}_{\mathrm{inter}}^{\mathrm{NTK}}$ is the kernel interpolation
with respect to $k_{\mathrm{NT}}$.

Moreover, since $k_{\mathrm{NT}}$ is a dot-product kernel satisfying a
polynomial eigenvalue decay of $\beta=d/(d-1)$ [25], our assumptions are
satisfied as discussed in Example 2.3.

######  Corollary 4.2.

There is a constant $c>0$ such that for any $\varepsilon>0$ and
$\delta\in(0,1)$, when $n$ and $m$ are sufficiently large, one has that

$\displaystyle
E\left(\liminf_{t\to\infty}\norm{\hat{f}^{\mathrm{NN}}_{t}(x)-f^{*}_{\rho}}_{L^{2}}^{2}\mid
X\right)\geq c\sigma^{2}n^{-\varepsilon}$

holds with probability at least $1-\delta$ with respect to the random samples
and initialization.

To the best of our knowledge, such a lower bound for wide neural network has
only been proven in Lai et al. [30] for one-dimensional grid data. Our result
claims that overfitted wide neural network generalizes poorly on the sphere
$\mathbb{S}^{d-1}$, This result shows that overfitted neural networks on the
sphere generalize poorly, which also suggests more efforts are needed to
understand the mystery of generalization of over-parametrized neural networks.

## Acknowledgement

Authors Yicheng Li and Haobo Zhang contributed equally to this work. This work
is supported in part by the National Natural Science Foundation of China
(Grant 11971257) and Beijing Natural Science Foundation (Grant Z190001).

## References

  * Neyshabur et al. [2015] B. Neyshabur, R. Tomioka, and N. Srebro, “In search of the real inductive bias: On the role of implicit regularization in deep learning”, arxiv:1412.6614.
  * Zhang et al. [2017] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals, “Understanding deep learning requires rethinking generalization”, arxiv:1611.03530.
  * Belkin et al. [2019] M. Belkin, D. Hsu, S. Ma, and S. Mandal, “Reconciling modern machine-learning practice and the classical bias–variance trade-off”, Proceedings of the National Academy of Sciences 116 (2019), no. 32, 15849–15854.
  * Vapnik [1999] V. Vapnik, “The nature of statistical learning theory”, Springer science & business media, 1999.
  * Jacot et al. [2018] A. Jacot, F. Gabriel, and C. Hongler, “Neural tangent kernel: Convergence and generalization in neural networks”, in “Advances in Neural Information Processing Systems”, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, eds., vol. 31.  Curran Associates, Inc., 2018.
  * Du et al. [2018] S. S. Du, X. Zhai, B. Poczos, and A. Singh, “Gradient descent provably optimizes over-parameterized neural networks”, in “International Conference on Learning Representations”.  2018\.
  * Allen-Zhu et al. [2019] Z. Allen-Zhu, Y. Li, and Z. Song, “A convergence theory for deep learning via over-parameterization”, 1811.03962.
  * Caponnetto and De Vito [2007] A. Caponnetto and E. De Vito, “Optimal rates for the regularized least-squares algorithm”, Foundations of Computational Mathematics 7 (2007), no. 3, 331–368.
  * Andreas Christmann [2008] I. S. a. Andreas Christmann, “Support vector machines”, Springer-Verlag New York, New York, NY, first ed., 2008.
  * Steinwart et al. [2009] I. Steinwart, D. Hush, and C. Scovel, “Optimal rates for regularized least squares regression”, in “COLT”, pp. 79–93.  2009\.
  * Fischer and Steinwart [2020] S.-R. Fischer and I. Steinwart, “Sobolev norm learning rates for regularized least-squares algorithms”, Journal of Machine Learning Research 21 (2020) 205:1–205:38.
  * Wainwright [2019] M. J. Wainwright, “High-dimensional statistics: A non-asymptotic viewpoint”, Cambridge University Press, 2019.
  * Liang and Rakhlin [2020] T. Liang and A. Rakhlin, “Just interpolate: Kernel "ridgeless" regression can generalize”, The Annals of Statistics 48 (2020), no. 3, arxiv:1808.00387.
  * Liang et al. [2020] T. Liang, A. Rakhlin, and X. Zhai, “On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels”, in “Conference on Learning Theory”, pp. 2683–2711.  PMLR, 2020.
  * Ghorbani et al. [2020] B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari, “Linearized two-layers neural networks in high dimension”, arxiv:1904.12191.
  * Mei and Montanari [2022] S. Mei and A. Montanari, “The generalization error of random features regression: Precise asymptotics and the double descent curve”, Communications on Pure and Applied Mathematics 75 (2022), no. 4, 667–766.
  * Ghosh et al. [2021] N. Ghosh, S. Mei, and B. Yu, “The three stages of learning dynamics in high-dimensional kernel methods”, arxiv:2111.07167.
  * Györfi [2002] L. Györfi, ed., “A distribution-free theory of nonparametric regression”, Springer, New York, 2002.
  * Rakhlin and Zhai [2018] A. Rakhlin and X. Zhai, “Consistency of interpolation with Laplace kernels is a high-dimensional phenomenon”, arxiv:1812.11167.
  * Buchholz [2022] S. Buchholz, “Kernel interpolation in Sobolev spaces is not consistent in low dimensions”, in “Proceedings of Thirty Fifth Conference on Learning Theory”, P.-L. Loh and M. Raginsky, eds., vol. 178 of Proceedings of Machine Learning Research, pp. 3410–3440.  PMLR, 2022.
  * Beaglehole et al. [2022] D. Beaglehole, M. Belkin, and P. Pandit, “Kernel ridgeless regression is inconsistent in low dimensions”, arxiv:2205.13525.
  * Steinwart and Scovel [2012] I. Steinwart and C. Scovel, “Mercer’s theorem on general domains: On the interaction between measures, kernels, and RKHSs”, Constructive Approximation 35 (2012), no. 3, 363–417.
  * Blanchard and Mücke [2018] G. Blanchard and N. Mücke, “Optimal rates for regularization of statistical inverse learning problems”, Foundations of Computational Mathematics 18 (2018) 971–1013.
  * Li et al. [2023] Y. Li, H. Zhang, and Q. Lin, “On the saturation effect of kernel ridge regression”, in “International Conference on Learning Representations”.  2023\.
  * Bietti and Mairal [2019] A. Bietti and J. Mairal, “On the inductive bias of neural tangent kernels”, in “Advances in Neural Information Processing Systems”, vol. 32.  2019\.
  * Adams and Fournier [2003] R. A. Adams and J. J. Fournier, “Sobolev spaces”, Elsevier, 2003.
  * Smola et al. [2000] A. Smola, Z. Ovári, and R. C. Williamson, “Regularization with dot-product kernels”, Advances in neural information processing systems 13 (2000).
  * Zhang et al. [2023] H. Zhang, Y. Li, and Q. Lin, “On the optimality of misspecified spectral algorithms”, arxiv:2303.14942.
  * Wendland [2004] H. Wendland, “Scattered data approximation”, Cambridge University Press, Cambridge, 2004.
  * Lai et al. [2023] J. Lai, M. Xu, R. Chen, and Q. Lin, “Generalization ability of wide neural networks on R”, arxiv:2302.05933.
  * Bietti and Bach [2020] A. Bietti and F. Bach, “Deep equals shallow for ReLU networks in kernel regimes”, arXiv preprint arXiv:2009.14397, 2020 2009.14397.
  * Lee et al. [2019] J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington, “Wide neural networks of any depth evolve as linear models under gradient descent”, in “Advances in Neural Information Processing Systems”, vol. 32.  Curran Associates, Inc., 2019.
  * Caponnetto and Yao [2010] A. Caponnetto and Y. Yao, “Cross-validation based adaptation for regularization operators in learning theory”, Analysis and Applications 08 (2010) 161–183.

##  Appendix A Proofs

###  A.1 More preliminaries

In the following, we will denote $h_{x}=k(x,\cdot)$ for $x\in\mathcal{X}$. For
a function $f$, we use
$f[X]=(f(x_{1}),\dots,f(x_{n}))^{\mathrm{\scriptscriptstyle T}}$. To simplify
the notation, we will use $c,C$ to represent constants, which may change in
the context; we will also abbreviate

$\displaystyle T_{\lambda}=T+\lambda,\quad T_{X\lambda}=T_{X}+\lambda.$

Following Li et al. [24], we consider the sample subspace

$\displaystyle\mathcal{H}_{n}=\operatorname{span}\left\\{k(x_{1},\cdot),\dots,k(x_{n},\cdot)\right\\}\subset\mathcal{H}.$
(27)

Then, it is easy to verify that $\operatorname{Ran}T_{X}=\mathcal{H}_{n}$ and
$K$ is the representation matrix of $T_{X}$ under the natural basis
$\left\\{k(x_{1},\cdot),\dots,k(x_{n},\cdot)\right\\}$. Consequently, for any
continuous function $\varphi$ we have

$\displaystyle\varphi(T_{X})\mathbb{K}(X,\cdot)=\varphi(K)\mathbb{K}(X,\cdot).$
(28)

where the left-hand side is understood by applying the operator elementwise.
Since from the property of reproducing kernel Hilbert space we have
$\left\langle{h_{x},f}\right\rangle_{\mathcal{H}}=f(x)$ for $f\in\mathcal{H}$,
taking inner product elementwise between (28) and $f$, we obtain

$\displaystyle(\varphi(T_{X})f)[X]=\varphi(K)f[X].$ (29)

Moreover, for $f,g\in\mathcal{H}$, we define empirical semi-inner product

$\displaystyle\left\langle{f,g}\right\rangle_{L^{2},n}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}f(x_{i})g(x_{i})=\frac{1}{n}f[X]^{\mathrm{\scriptscriptstyle
T}}g[X],$ (30)

and denote by $\norm{\cdot}_{L^{2},n}^{2}$ the corresponding empirical semi-
norm. Then, Li et al. [24] established the following simple but important
connection.

######  Proposition A.1.

For $f,g\in\mathcal{H}$, we have

$\left\langle{f,g}\right\rangle_{L^{2},n}=\left\langle{T_{X}f,g}\right\rangle_{\mathcal{H}}=\left\langle{T_{X}^{1/2}f,T_{X}^{1/2}g}\right\rangle_{\mathcal{H}}.$
(31)

###### Proof.

Notice that $T_{X}f=\frac{1}{n}\sum_{i=1}^{n}f(x_{i})h_{x_{i}}$, and thus

$\displaystyle\left\langle{T_{X}f,g}\right\rangle_{\mathcal{H}}=\frac{1}{n}\sum_{i=1}^{n}f(x_{i})\left\langle{h_{x_{i}},g}\right\rangle_{\mathcal{H}}=\frac{1}{n}\sum_{i=1}^{n}f(x_{i})g(x_{i})=\left\langle{f,g}\right\rangle_{L^{2},n}.$

The second inequality comes from the definition of $T_{X}^{1/2}$. ∎

###  A.2 The variance term

The first step of the proof is to lower bound the generalization error by the
variance term $V(\lambda)$, whose explicit expression can be derived. This
step is elementary and quite standard in the literature, so we omit the proof
here.

######  Proposition A.2.

Under Assumption 4, for any $\lambda\geq 0$, we have

$\displaystyle E\left(\norm{\hat{f}_{\lambda}-f^{*}_{\rho}}^{2}_{L^{2}}\mid
X\right)\geq
V(\lambda)=\frac{\sigma^{2}}{n^{2}}\int_{\mathcal{X}}\mathbb{K}(x,X)(K+\lambda)^{-2}\mathbb{K}(X,x)\differential\mu(x).$
(32)

###### Proof.

Let us denote $K_{\lambda}=K+\lambda$. Recalling (15), we have

$\displaystyle\hat{f}_{\lambda}-f^{*}_{\rho}$
$\displaystyle=\frac{1}{n}\mathbb{K}(x,X)K_{\lambda}^{-1}Y$
$\displaystyle=\frac{1}{n}\mathbb{K}(x,X)K_{\lambda}^{-1}\left(f^{*}_{\rho}[X]+\bm{\epsilon}\right)-f^{*}_{\rho}(x)$
$\displaystyle=\frac{1}{n}\mathbb{K}(x,X)K_{\lambda}^{-1}\bm{\epsilon}+\mathbb{K}(x,X)K_{\lambda}^{-1}f^{*}_{\rho}[X]-f^{*}_{\rho}(x),$

where $\bm{\epsilon}$ is the column vector of the noises
$\epsilon_{i}=y_{i}-f^{*}_{\rho}(x_{i})$. Since $\epsilon_{i}|X$ are
independent with mean zero and variance $\sigma^{2}_{x_{i}}\geq\sigma^{2}$,
simple calculation shows

$\displaystyle E\left(\norm{\hat{f}_{\lambda}-f^{*}_{\rho}}^{2}_{L^{2}}\mid
X\right)$
$\displaystyle=E\left[\int_{\mathcal{X}}\left\\{\hat{f}_{\lambda}(x)-f^{*}_{\rho}(x)\right\\}^{2}\differential\mu(x)\mid
X\right]$
$\displaystyle=\int_{\mathcal{X}}E\left[\left\\{\hat{f}_{\lambda}(x)-f^{*}_{\rho}(x)\right\\}^{2}\mid
X\right]\differential\mu(x)$
$\displaystyle\geq\int_{\mathcal{X}}\mathrm{var}\left\\{\hat{f}_{\lambda}(x)\mid
X\right\\}\differential\mu(x)$
$\displaystyle=\frac{1}{n^{2}}\int_{\mathcal{X}}\mathbb{K}(x,X)K_{\lambda}^{-1}E\left(\bm{\epsilon}\bm{\epsilon}^{\mathrm{\scriptscriptstyle
T}}\mid X\right)K_{\lambda}^{-1}\mathbb{K}(X,x)\differential\mu(x)$
$\displaystyle\geq\frac{\sigma^{2}}{n^{2}}\int_{\mathcal{X}}\mathbb{K}(x,X)K_{\lambda}^{-2}\mathbb{K}(X,x)\differential\mu(x).$

∎

The simple but critical observation based on the matrix form in (32) is that

$\displaystyle(K+\lambda_{1})^{-2}\succeq(K+\lambda_{2})^{-2}\mbox{\quad
if\quad}\lambda_{1}\leq\lambda_{2},$

where $\succeq$ represents the partial order of positive semi-definite
matrices, and thus we have the following proposition [24].

######  Proposition A.3.

For $\lambda_{1}\geq\lambda_{2}\geq 0$, we have $V(\lambda_{1})\leq
V(\lambda_{2})$. Particularly, for any $\lambda\geq 0$,

$\displaystyle V(0)\geq V(\lambda).$

This proposition allows us to consider the variance term of slightly bigger
$\lambda$’s, where concentration results can be established. However, it is
still difficult to directly analyze the matrix form. The key is to rewrite the
matrix form into the operator form using empirical semi-norm introduced in Li
et al. [24].

######  Lemma A.4.

The variance term in (32) satisfies

$\displaystyle
V(\lambda)=\frac{\sigma^{2}}{n}\int_{\mathcal{X}}\norm{(T_{X}+\lambda)^{-1}k(x,\cdot)}_{L^{2},n}^{2}\differential\mu(x)$
(33)

###### Proof.

By definition it is obvious that $h_{x}[X]=\mathbb{K}(X,x)$. From (29), we
find that

$\displaystyle\left((T_{X}+\lambda)^{-1}h_{x}\right)[X]=(K+\lambda)^{-1}h_{x}[X]=(K+\lambda)^{-1}\mathbb{K}(X,x),$

so

$\displaystyle\frac{1}{n}\mathbb{K}(x,X)(K+\lambda)^{-2}\mathbb{K}(X,x)$
$\displaystyle=\frac{1}{n}\norm{(K+\lambda)^{-1}\mathbb{K}(X,x)}_{\mathbb{R}^{n}}^{2}$
$\displaystyle=\frac{1}{n}\norm{\\{(T_{X}+\lambda)^{-1}h_{x}\\}[X]}_{\mathbb{R}^{n}}^{2}$
$\displaystyle=\norm{(T_{X}+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}.$

from the definition (30) of empirical semi-norm. ∎

The operator form (33) allows us to apply concentration inequalities and
establish the following two-step approximation [24]. The main difference is
that we allow $\lambda$ to be much smaller than in Li et al. [24].

$\displaystyle\norm{(T_{X}+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}\stackrel{{\scriptstyle
A}}{{\approx}}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}\stackrel{{\scriptstyle
B}}{{\approx}}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}.$ (34)

###  A.3 Approximation B

Let us first consider the approximation B in (34). We first provide norm
controls of basis functions $h_{x}=k(x,\cdot)$ using the embedding condition.

######  Lemma A.5.

Suppose $\mathcal{H}$ has embedding index $\alpha_{0}$. Let $p,\gamma\geq 0$,
$\alpha>\alpha_{0}$ such that $0\leq 2-\gamma-\alpha\leq 2p$, then

$\displaystyle\norm{T_{\lambda}^{-p}h_{x}}_{[\mathcal{H}]^{\gamma}}^{2}\leq
M_{\alpha}^{2}\lambda^{2-2p-\gamma-\alpha},\quad\mu\text{-a.e.}~{}x\in\mathcal{X}.$
(35)

###### Proof.

Recalling the definition (8) and using Mercer’s decomposition (4), we have

$\displaystyle\norm{T_{\lambda}^{-p}h_{x}}_{[\mathcal{H}]^{\gamma}}^{2}$
$\displaystyle=\norm{T^{-\gamma/2}T_{\lambda}^{-p}h_{x}}_{L^{2}}^{2}$
$\displaystyle=\norm{\sum_{i\in
N}\lambda_{i}^{-\gamma/2}(\lambda_{i}+\lambda)^{-p}\lambda_{i}e_{i}(x)e_{i}}_{L^{2}}^{2}$
$\displaystyle=\sum_{i\in
N}\lambda_{i}^{2-\gamma}(\lambda_{i}+\lambda)^{-2p}e_{i}(x)^{2}$
$\displaystyle=\sum_{i\in
N}\left\\{\lambda_{i}^{2-\gamma-\alpha}(\lambda_{i}+\lambda)^{-2p}\right\\}\lambda_{i}^{\alpha}e_{i}(x)^{2}$
$\displaystyle\leq\sum_{i\in
N}\lambda^{2-\gamma-\alpha-2p}\lambda_{i}^{\alpha}e_{i}(x)^{2}$
$\displaystyle\leq M_{\alpha}^{2}\lambda^{2-2p-\gamma-\alpha},$

where last but second inequality uses Proposition B.1 and the final inequality
uses that fact that

$\displaystyle\operatorname*{ess~{}sup}_{x\in\mathcal{X},~{}\mu}\sum_{i\in
N}\lambda_{i}^{\alpha}e_{i}(x)^{2}=\norm{[\mathcal{H}]^{\alpha}\hookrightarrow
L^{\infty}(\mathcal{X},\mu)}^{2}=M_{\alpha}^{2},$

which is the consequence of (11) and (10). ∎

Noticing that the $L^{\infty}$-norm of $f\in\mathcal{H}$ can be bounded by

$\displaystyle\norm{f}_{L^{\infty}}^{2}\leq
M_{\alpha}^{2}\norm{f}_{[\mathcal{H}]^{\alpha}}^{2},$

we have the following corollary.

######  Corollary A.6.

Suppose $\mathcal{H}$ has embedding index $\alpha_{0}$ and
$\alpha>\alpha_{0}$. Then the following holds for
$\mu\text{-a.e.}~{}x\in\mathcal{X}$:

$\displaystyle\norm{T_{\lambda}^{-1}h_{x}}_{L^{\infty}}^{2}$
$\displaystyle\leq M_{\alpha}^{4}\lambda^{-2\alpha},$ (36)
$\displaystyle\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}$ $\displaystyle\leq
M_{\alpha}^{2}\lambda^{-\alpha},$ (37)
$\displaystyle\norm{T_{\lambda}^{-1/2}h_{x}}_{\mathcal{H}}^{2}$
$\displaystyle\leq M_{\alpha}^{2}\lambda^{-\alpha}.$ (38)

Now we can provide the following estimation using concentration inequalities
with a covering number argument.

######  Lemma A.7.

Suppose that the embedding index of $\mathcal{H}$ is $\alpha_{0}$ and
Assumption 3 holds. Fix $\alpha>\alpha_{0}$ and suppose $\lambda=\lambda(n)\to
0$ satisfies $\lambda=\Omega\left(n^{-p}\right)$ for some $p<\infty$. Then,
for any $\delta\in(0,1)$, for sufficiently large $n$ (which will depend on
$\delta,p$), with probability at least $1-\delta$, for $\mu$-a.e.
$x\in\mathcal{X}$

$\displaystyle\frac{1}{2}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}-R\leq\norm{T_{\lambda}^{-1}h_{x}}_{L^{2},n}^{2}\leq\frac{3}{2}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}+R,$

where

$\displaystyle
R=R(\lambda,n)=CM_{\alpha}^{4}\frac{\lambda^{-2\alpha}}{n}\ln\frac{n}{\delta}$

and constant $C$ is independent of $\delta,n$.

###### Proof.

Let us denote
$\mathcal{K}_{\lambda}=\left\\{T_{\lambda}^{-1}h_{x}\right\\}_{x\in\mathcal{X}}$.
By Lemma B.8, we can find an $\varepsilon$-net
$\mathcal{F}\subseteq\mathcal{K}_{\lambda}\subseteq\mathcal{H}$ with respect
to sup-norm of $\mathcal{K}_{\lambda}$ such that

$\displaystyle\absolutevalue{\mathcal{F}}\leq
C\left(\lambda\varepsilon\right)^{-\frac{2d}{s}},$ (39)

where $\varepsilon=\varepsilon(n)$ will be determined later.

Then, applying Proposition B.4 to $\mathcal{F}$ with the
$\norm{\cdot}_{L^{\infty}}$-bound (36), with probability at least $1-\delta$
we have

$\displaystyle\frac{1}{2}\norm{f}_{L^{2}}^{2}-R_{1}\leq\norm{f}_{L^{2},n}^{2}\leq\frac{3}{2}\norm{f}_{L^{2}}^{2}+R_{1},\quad\forall
f\in\mathcal{F},$ (40)

where
$R_{1}=CM_{\alpha}^{4}\lambda^{-2\alpha}n^{-1}\ln(2\absolutevalue{\mathcal{F}}/\delta)$.

Now, since $\mathcal{F}$ is an $\varepsilon$-net of $\mathcal{K}_{\lambda}$
with respect to $\norm{\cdot}_{\infty}$, for any $x\in\mathcal{X}$, there
exists some $f\in\mathcal{F}$ such that

$\displaystyle\norm{T_{\lambda}^{-1}h_{x}-f}_{\infty}\leq\varepsilon,$

which implies that

$\displaystyle\absolutevalue{\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}-\norm{f}_{L^{2}}}\leq\varepsilon,\quad\absolutevalue{\norm{T_{\lambda}^{-1}h_{x}}_{L^{2},n}-\norm{f}_{L^{2},n}}\leq\varepsilon.$

Moreover, from (36) again we know that for $\mu$-a.e. $x\in\mathcal{X}$,

$\displaystyle\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}},~{}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2},n}\leq
M_{\alpha}\lambda^{-\alpha},$

which is also true for $f$ since $f\in\mathcal{K}_{\lambda}$. Using
$a^{2}-b^{2}=(a-b)(a+b)$, we get

$\displaystyle\absolutevalue{\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}-\norm{f}_{L^{2}}^{2}}\leq
2M_{\alpha}\varepsilon\lambda^{-\alpha},$ (41)
$\displaystyle\absolutevalue{\norm{T_{\lambda}^{-1}h_{x}}_{L^{2},n}^{2}-\norm{f}_{L^{2},n}^{2}}\leq
2M_{\alpha}\varepsilon\lambda^{-\alpha}.$

Without loss of generality we consider only the upper bound:

$\displaystyle\norm{T_{\lambda}^{-1}h_{x}}_{L^{2},n}^{2}$
$\displaystyle\leq\norm{f}_{L^{2},n}^{2}+2M_{\alpha}\varepsilon\lambda^{-\alpha}\mbox{\quad(by
{(\ref{eq:L2NormEstimation})})\quad}$ (by (40))
$\displaystyle\leq\frac{3}{2}\norm{f}_{L^{2}}^{2}+R_{1}+2M_{\alpha}\varepsilon\lambda^{-\alpha}$
(by (41) again)
$\displaystyle\leq\frac{3}{2}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}+R_{1}+4M_{\alpha}\varepsilon\lambda^{-\alpha}$
$\displaystyle=\frac{3}{2}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}+R_{2},$

where
$R_{2}=CM_{\alpha}^{4}n^{-1}\lambda^{-2\alpha}\ln(2\absolutevalue{\mathcal{F}}/\delta)+4M_{\alpha}\varepsilon\lambda^{-\alpha}$.
Letting $\varepsilon=n^{-1}$ and applying in (39), the second term in $R_{2}$
is infinitesimal to the first one, and we have

$\displaystyle R_{2}\leq
CM_{\alpha}^{4}\frac{\lambda^{-2\alpha}}{n}\left(\ln\lambda+\ln
n+\ln\frac{1}{\delta}\right)\leq
CM_{\alpha}^{4}\frac{\lambda^{-2\alpha}}{n}\ln\frac{n}{\delta},$

since $\lambda=\Omega\left(n^{-p}\right)$. ∎

###  A.4 Approximation A

The following proposition is a slightly modified version of Fischer and
Steinwart [11, Lemma 17]. Compared with Li et al. [24, Lemma C.2], it weakens
the requirement of $\lambda$ using the embedding property.

######  Proposition A.8.

Suppose $\mathcal{H}$ has embedding index $\alpha_{0}$ and Assumption 1 holds.
Let $\lambda=\lambda(n)\to 0$ satisfy
$\lambda=\Omega\left(n^{-1/(\alpha_{0}+p)}\right)$ for some $p>0$ and fix
arbitrary $\alpha\in(\alpha_{0},\alpha_{0}+p)$. Then, for all
$\delta\in(0,1)$, when $n$ is sufficiently large (depending on
$\delta,p,\alpha$), with probability at least $1-\delta$,

$\norm{T_{\lambda}^{-\frac{1}{2}}(T-T_{X})T_{\lambda}^{-\frac{1}{2}}}_{\mathscr{B}(\mathcal{H})}\leq
CM_{\alpha}\left(\frac{\lambda^{-\alpha}}{n}\ln\frac{n}{\delta}\right)^{1/2},$
(42)

where $C>0$ is a constant no depending on $n,\delta,p,\alpha$, and we also
have

$\displaystyle\norm{T_{X\lambda}^{-1/2}T_{\lambda}^{1/2}}_{\mathscr{B}(\mathcal{H})}\leq\sqrt{3}.$
(43)

###### Proof.

We apply Proposition B.6. We use $\norm{\cdot}$ for the operator norm
$\norm{\cdot}_{\mathscr{B}(\mathcal{H})}$ in the proof for simplicity. By
Proposition B.2, $\mathcal{N}(\lambda)\leq C\lambda^{-1/\beta}$. Moreover,
since $\lambda=\Omega\left(n^{-1/(\alpha_{0}+p)}\right)$ for some $p>0$ and
$\alpha\in(\alpha_{0},\alpha_{0}+p)$, we have

$\displaystyle u$
$\displaystyle=\frac{M_{\alpha}^{2}\lambda^{-\alpha}}{n}\ln{\frac{4\mathcal{N}(\lambda)(\norm{T}+\lambda)}{\delta\norm{T}}}$
$\displaystyle\leq
CM_{\alpha}^{2}\frac{\lambda^{-\alpha}}{n}\left(\ln\lambda^{-1/\beta}+\ln\frac{1}{\delta}+C\right)$
$\displaystyle\leq
CM_{\alpha}^{2}\frac{\lambda^{-\alpha}}{n}\left\\{(\alpha_{0}+p)^{-1}\beta^{-1}\ln
n+\ln\frac{1}{\delta}+C\right\\}$ $\displaystyle\leq
CM_{\alpha}^{2}\frac{\lambda^{-\alpha}}{n}(\ln n+\ln\frac{1}{\delta})=o(1),$

and thus

$\displaystyle\norm{T_{\lambda}^{-\frac{1}{2}}(T-T_{X})T_{\lambda}^{-\frac{1}{2}}}\leq\frac{4}{3}u+(2u)^{\frac{1}{2}}\leq
Cu^{\frac{1}{2}}\leq
CM_{\alpha}\left(\frac{\lambda^{-\alpha}}{n}\ln\frac{n}{\delta}\right)^{1/2}.$

For the second part, when $n$ is sufficiently large that $u\leq\frac{1}{8}$,

$\displaystyle\norm{T_{\lambda}^{-\frac{1}{2}}(T-T_{X})T_{\lambda}^{-\frac{1}{2}}}=\frac{4}{3}u+(2u)^{\frac{1}{2}}\leq\frac{2}{3}.$

Noticing that
$\left(T_{X\lambda}^{-1/2}T_{\lambda}^{1/2}\right)^{*}=T_{\lambda}^{1/2}T_{X\lambda}^{-1/2}$,
we have

$\displaystyle\norm{T_{X\lambda}^{-1/2}T_{\lambda}^{1/2}}^{2}$
$\displaystyle=\norm{T_{\lambda}^{1/2}(T_{X}+\lambda)^{-1}T_{\lambda}^{1/2}}$
$\displaystyle=\norm{\left\\{T_{\lambda}^{-1/2}(T_{X}+\lambda)T_{\lambda}^{-1/2}\right\\}^{-1}}$
$\displaystyle=\norm{\left\\{I-T_{\lambda}^{-1/2}(T-T_{X})T_{\lambda}^{-1/2}\right\\}^{-1}}$
$\displaystyle\leq\left(1-\norm{T_{\lambda}^{-\frac{1}{2}}(T-T_{X})T_{\lambda}^{-\frac{1}{2}}}\right)^{-1}\leq
3.$

∎

Then, the following lemma improves Li et al. [24, Lemma C.12] and allows
$\lambda$ to be of the order $n^{-\beta+\varepsilon}$ if Assumption 2 is also
satisfied.

######  Lemma A.9.

Suppose $\mathcal{H}$ has embedding index $\alpha_{0}$ and Assumption 1 holds.
Let $\lambda=\lambda(n)\to 0$ satisfy
$\lambda=\Omega\left(n^{-1/(\alpha_{0}+p)}\right)$ for some $p>0$ and fix
arbitrary $\alpha\in(\alpha_{0},\alpha_{0}+p)$. Then, for sufficiently large
$n$ (depending on $\delta,p,\alpha$), with probability at least $1-\delta$ it
is satisfied that for $\mu$-a.e. $x\in\mathcal{X}$,

$\displaystyle\absolutevalue{\norm{T_{X}^{1/2}T_{X\lambda}^{-1}h_{x}}_{\mathcal{H}}-\norm{T_{X}^{1/2}T_{\lambda}^{-1}h_{x}}_{\mathcal{H}}}\leq
CM_{\alpha}^{2}\left(\frac{\lambda^{-2\alpha}}{n}\ln\frac{n}{\delta}\right)^{1/2},$

where the constant $C>0$ do not depend on $n,\delta,p,\alpha$.

###### Proof.

We begin with

$\displaystyle\absolutevalue{\norm{T_{X}^{1/2}T_{X\lambda}^{-1}h_{x}}_{\mathcal{H}}-\norm{T_{X}^{1/2}T_{\lambda}^{-1}h_{x}}_{\mathcal{H}}}$
$\displaystyle\leq\norm{T_{X}^{1/2}\left(T_{X\lambda}^{-1}-T_{\lambda}^{-1}\right)h_{x}}_{\mathcal{H}}$
$\displaystyle=\norm{T_{X}^{1/2}T_{X\lambda}^{-1}\left(T-T_{X}\right)T_{\lambda}^{-1}h_{x}}_{\mathcal{H}},$

where we notice that

$\displaystyle
T_{X\lambda}^{-1}-T_{\lambda}^{-1}=(T_{X}+\lambda)^{-1}-(T+\lambda)^{-1}=T_{X\lambda}^{-1}\left(T-T_{X}\right)T_{\lambda}^{-1}.$

Now let us decompose

$\displaystyle\quad\norm{T_{X}^{1/2}T_{X\lambda}^{-1}\left(T-T_{X}\right)T_{\lambda}^{-1}h_{x}}_{\mathcal{H}}$
$\displaystyle=\norm{T_{X}^{1/2}T_{X\lambda}^{-1/2}\cdot
T_{X\lambda}^{-1/2}T_{\lambda}^{1/2}\cdot
T_{\lambda}^{-1/2}\left(T-T_{X}\right)T_{\lambda}^{-1/2}\cdot
T_{\lambda}^{-1/2}h_{x}}_{\mathcal{H}}$
$\displaystyle\leq\norm{T_{X}^{1/2}T_{X\lambda}^{-1/2}}_{\mathscr{B}(\mathcal{H})}\cdot\norm{T_{X\lambda}^{-1/2}T_{\lambda}^{1/2}}_{\mathscr{B}(\mathcal{H})}\cdot\norm{T_{\lambda}^{-1/2}\left(T-T_{X}\right)T_{\lambda}^{-1/2}}_{\mathscr{B}(\mathcal{H})}\cdot\norm{T_{\lambda}^{-1/2}h_{x}}_{\mathcal{H}}$
$\displaystyle\leq 1\cdot\sqrt{3}\cdot
CM_{\alpha}\left(\frac{\lambda^{-\alpha}}{n}\ln\frac{n}{\delta}\right)^{1/2}\cdot
M_{\alpha}\lambda^{-\alpha/2}$
$\displaystyle=CM_{\alpha}^{2}\left(\frac{\lambda^{-2\alpha}}{n}\ln\frac{n}{\delta}\right)^{1/2},$

where the four terms in the last inequality are: (1) from operator calculus
and Proposition B.1; (2) and (3) from Proposition A.8; (4) from (38).

∎

###  A.5 Final proof

######  Theorem A.10.

Under Assumptions 1,2,3 and 4, suppose that $\lambda=\lambda(n)\to 0$ satisfy
$\lambda=\Omega\left(n^{-\beta+p}\right)$ for some $p>0$. Then, for any
$\delta\in(0,1)$, when $n$ is sufficiently large (depending on $\delta,p$),
the following holds with probability at least $1-\delta$:

$\displaystyle\sigma^{2}c\frac{\lambda^{-1/\beta}}{n}\leq
V(\lambda)\leq\sigma^{2}C\frac{\lambda^{-1/\beta}}{n},$ (44)

where $c,C>0$ are absolute constants no depending on $\delta,n,\lambda$.

###### Proof.

We only prove the lower bound and the upper bound is similar. First, we assert
that

$\displaystyle\norm{T_{X\lambda}^{-1}h_{x}}_{L^{2},n}^{2}\geq\frac{1}{2}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}-o(\lambda^{-1/\beta})$
(45)

holds with probability at least $1-\delta$ for large $n$. Then, we have

$\displaystyle
V(\lambda)=\frac{\sigma^{2}}{n}\int_{\mathcal{X}}\norm{T_{X\lambda}^{-1}h_{x}}_{L^{2},n}^{2}\differential\mu(x)\geq\frac{\sigma^{2}}{2n}\int_{\mathcal{X}}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}\differential\mu(x)-o(\frac{\lambda^{-1/\beta}}{n}).$

For the integral, applying Mercer’s theorem, we get

$\displaystyle\int_{\mathcal{X}}$
$\displaystyle\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}\differential\mu(x)=\int_{\mathcal{X}}\sum_{i=1}^{\infty}\left(\frac{\lambda_{i}}{\lambda+\lambda_{i}}\right)^{2}e_{i}(x)^{2}\differential\mu(x)$
(46)
$\displaystyle=\sum_{i=1}^{\infty}\left(\frac{\lambda_{i}}{\lambda+\lambda_{i}}\right)^{2}=\mathcal{N}_{2}(\lambda)\geq
c\lambda^{-1/\beta},$

where the last inequality comes from Proposition B.2. Therefore, we conclude
that

$\displaystyle V(\lambda)$
$\displaystyle\geq\frac{c\sigma^{2}}{2n}\lambda^{-1/\beta}-o(\frac{\lambda^{-1/\beta}}{n})\geq
c_{1}\frac{\lambda^{-1/\beta}}{n}.$

Now we prove (45). Let us choose $\alpha>\alpha_{0}=1/\beta$ sufficiently
close but fixed. The requirement of $\alpha$ will be seen in the following
proof. Then, Lemma A.7 and Lemma A.9 yield that

$\displaystyle\frac{1}{2}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}-R\leq\norm{T_{\lambda}^{-1}h_{x}}_{L^{2},n}^{2}\leq\frac{3}{2}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}+R,$
(47)
$\displaystyle\absolutevalue{\norm{T_{X}^{1/2}T_{X\lambda}^{-1}h_{x}}_{\mathcal{H}}-\norm{T_{X}^{1/2}T_{\lambda}^{-1}h_{x}}_{\mathcal{H}}}\leq
R^{1/2},\quad\forall x\in\mathcal{X},$ (48)

with probability at least $1-\delta$ for large $n$, where

$\displaystyle
R=CM_{\alpha}^{4}\frac{\lambda^{-2\alpha}}{n}\ln\frac{n}{\delta}$

for some constant $C$ not depending on $n,\delta,p,\alpha$. Consequently, the
$L^{2}$-norm bound in (37) and (47) yield

$\displaystyle\norm{T_{X}^{1/2}T_{\lambda}^{-1}h_{x}}_{\mathcal{H}}$
$\displaystyle=\norm{T_{\lambda}^{-1}h_{x}}_{L^{2},n}\leq
C\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}+R^{1/2}\leq
C\lambda^{-\alpha/2}+R^{1/2}$

which, together with (48), implies

$\displaystyle\norm{T_{X}^{1/2}T_{X\lambda}^{-1}h_{x}}_{\mathcal{H}}+\norm{T_{X}^{1/2}T_{\lambda}^{-1}h_{x}}_{\mathcal{H}}\leq
2\norm{T_{X}^{1/2}T_{\lambda}^{-1}h_{x}}_{\mathcal{H}}+R^{1/2}\leq
C(\lambda^{-\alpha/2}+R^{1/2})$

Then, we obtain the approximation of the squared norm

$\displaystyle\absolutevalue{\norm{T_{X}^{1/2}T_{X\lambda}^{-1}h_{x}}_{\mathcal{H}}^{2}-\norm{T_{X}^{1/2}T_{\lambda}^{-1}h_{x}}_{\mathcal{H}}^{2}}\leq
CR^{1/2}(\lambda^{-\alpha/2}+R^{1/2}).$ (49)

Combining (49) and (47), we get

$\displaystyle\norm{T_{X\lambda}^{-1}h_{x}}_{L^{2},n}^{2}$
$\displaystyle=\norm{T_{X}^{1/2}T_{X\lambda}^{-1}h_{x}}_{\mathcal{H}}^{2}$
$\displaystyle\geq\norm{T_{X}^{1/2}T_{\lambda}^{-1}h_{x}}_{\mathcal{H}}^{2}-CR^{1/2}(\lambda^{-\alpha/2}+R^{1/2})$
$\displaystyle=\norm{T_{\lambda}^{-1}h_{x}}_{L^{2},n}^{2}-CR^{1/2}(\lambda^{-\alpha/2}+R^{1/2})$
$\displaystyle\geq\frac{1}{2}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}-R-CR^{1/2}(\lambda^{-\alpha/2}+R^{1/2})$
$\displaystyle=\frac{1}{2}\norm{T_{\lambda}^{-1}h_{x}}_{L^{2}}^{2}-CR^{1/2}(R^{1/2}+\lambda^{-\alpha/2}).$
(50)

Finally, we show that the error terms in (50) are infinitesimal with respect
to the main term $\lambda^{-1/\beta}$. We recall that
$\lambda=\Omega(n^{-\beta+p})$ and $\alpha_{0}=1/\beta$, so

$\displaystyle
R^{1/2}=CM_{\alpha}^{2}\left(\frac{\lambda^{-\alpha}}{n}\right)^{1/2}\lambda^{-\alpha/2}\left(\ln\frac{n}{\delta}\right)^{1/2}\leq
CM_{\alpha}^{2}\lambda^{-\alpha/2}$

if $1/\beta<\alpha<1/(\beta-p)$. Therefore,

$\displaystyle\lambda^{1/\beta}R^{1/2}(R^{1/2}+\lambda^{-\alpha/2})$
$\displaystyle\leq C\lambda^{1/\beta}R^{1/2}\cdot
M_{\alpha}^{2}\lambda^{-\alpha/2}$ $\displaystyle\leq
CM_{\alpha}^{4}n^{-1/2}\lambda^{1/\beta-3\alpha/2}\left(\ln\frac{n}{\delta}\right)^{1/2},$

and thus $R^{1/2}(R^{1/2}+\lambda^{-\alpha/2})=o(\lambda^{-1/\beta})$ if we
further set $\beta^{-1}<\alpha<\beta^{-1}\cdot(3\beta-2p)/(3\beta-3p)$. ∎

###### Proof of Theorem 3.1.

Let us choose $\lambda=n^{-\beta+p}$ for some $p>0$. Then, from Proposition
A.2 and Proposition A.3, we have

$\displaystyle
E\left(\norm{\hat{f}_{\mathrm{inter}}-f^{*}_{\rho}}^{2}_{L^{2}}\mid
X\right)\geq V(0)\geq V(\lambda).$

Moreover, Theorem A.10 yields

$\displaystyle V(\lambda)\geq
c\frac{\lambda^{-1/\beta}}{n}=c\sigma^{2}n^{-p/\beta}$

with high probability when $n$ is large. Since $p>0$ can be arbitrary, we
finish the proof. ∎

##  Appendix B Auxiliary results

### Inequalities

######  Proposition B.1.

For $\lambda>0$ and $s\in[0,1]$, we have

$\displaystyle\sup_{t\geq 0}\frac{t^{s}}{t+\lambda}\leq\lambda^{s-1}.$

######  Proposition B.2.

Under Assumption 1, for any $p\geq 1$, we have

$\displaystyle\mathcal{N}_{p}(\lambda)=\tr\left(TT_{\lambda}^{-1}\right)^{p}=\sum_{i=1}^{\infty}\left(\frac{\lambda_{i}}{\lambda+\lambda_{i}}\right)^{p}\asymp\lambda^{-1/\beta}.$
(51)

###### Proof.

Since $c~{}i^{-\beta}\leq\lambda_{i}\leq Ci^{-\beta}$, we have

$\displaystyle\mathcal{N}_{p}(\lambda)$
$\displaystyle=\sum_{i=1}^{\infty}\left(\frac{\lambda_{i}}{\lambda_{i}+\lambda}\right)^{p}\leq\sum_{i=1}^{\infty}\left(\frac{Ci^{-\beta}}{Ci^{-\beta}+\lambda}\right)^{p}=\sum_{i=1}^{\infty}\left(\frac{C}{C+\lambda
i^{\beta}}\right)^{p}$
$\displaystyle\leq\int_{0}^{\infty}\left(\frac{C}{\lambda
x^{\beta}+C}\right)^{p}\differential
x=\lambda^{-1/\beta}\int_{0}^{\infty}\left(\frac{C}{y^{\beta}+C}\right)^{p}\differential
y\leq\tilde{C}\lambda^{-1/\beta}.$

for some constant $C$. The lower bound is similar. ∎

The following concentration inequality is introduced in Caponnetto and Yao
[33].

######  Lemma B.3.

Let $\xi_{1},\dots,\xi_{n}$ be $n$ i.i.d. bounded random variables such that
$\absolutevalue{\xi_{i}}\leq B$ almost surely, $E(\xi_{i})=\mu$, and
$E(\xi_{i}-\mu)^{2}\leq\sigma^{2}$. Then for any $\alpha>0$, any
$\delta\in(0,1)$, we have

$\displaystyle\absolutevalue{\frac{1}{n}\sum_{i=1}^{n}\xi_{i}-\mu}\leq\alpha\sigma^{2}+\frac{3+4\alpha
B}{6\alpha n}\ln\frac{2}{\delta}$ (52)

holds with probability at least $1-\delta$.

Basing on Lemma B.3, we can obtain the following concentration about $L^{2}$
norm [24, Proposition C.9].

######  Proposition B.4.

Let $\mu$ be a probability measure on $\mathcal{X}$, $f\in
L^{2}(\mathcal{X},\differential\mu)$ and $\norm{f}_{L^{\infty}}\leq M$.
Suppose we have $x_{1},\dots,x_{n}$ sampled i.i.d. from $\mu$. Then, the
following holds with probability at least $1-\delta$:

$\displaystyle\frac{1}{2}\norm{f}_{L^{2}}^{2}-\frac{5M^{2}}{3n}\ln\frac{2}{\delta}\leq\norm{f}_{L^{2},n}^{2}\leq\frac{3}{2}\norm{f}_{L^{2}}^{2}+\frac{5M^{2}}{3n}\ln\frac{2}{\delta}.$
(53)

###### Proof.

Defining $\xi_{i}=f(x_{i})^{2}$, we have

$\displaystyle E(\xi_{i})$ $\displaystyle=\norm{f}_{L^{2}}^{2},$
$\displaystyle E(\xi_{i}^{2})$
$\displaystyle=E_{x\sim\mu}\left(f(x)^{4}\right)\leq\norm{f}_{L^{\infty}}^{2}\norm{f}_{L^{2}}^{2}.$

Therefore, applying Lemma B.3, we get

$\displaystyle\absolutevalue{\norm{f}_{L^{2},n}^{2}-\norm{f}_{L^{2}}^{2}}\leq\alpha\norm{f}_{L^{\infty}}^{2}\norm{f}_{L^{2}}^{2}+\frac{3+4\alpha
M^{2}}{6\alpha n}\ln\frac{2}{\delta}.$

The final result comes from choosing $\alpha=(2M^{2})^{-1}$. ∎

The following Bernstein type concentration inequality about self-adjoint
Hilbert-Schmidt operator valued random variable is commonly used in the
related literature [11, 24].

######  Lemma B.5.

Let $H$ be a separable Hilbert space. Let $A_{1},\dots,A_{n}$ be i.i.d. random
variables taking values of self-adjoint Hilbert-Schmidt operators such that
$E(A_{1})=0$, $\norm{A_{1}}\leq L$ almost surely for some $L>0$ and
$E(A_{1}^{2})\preceq V$ for some positive trace-class operator $V$. Then, for
any $\delta\in(0,1)$, with probability at least $1-\delta$ we have

$\displaystyle\norm{\frac{1}{n}\sum_{i=1}^{n}A_{i}}\leq\frac{2LB}{3n}+\left(\frac{2\norm{V}B}{n}\right)^{1/2},\quad
B=\ln\frac{4\tr V}{\delta\norm{V}}.$

A application of Lemma B.5 is the following [11, Lemma 17] and we provide the
proof for completeness. For simplicity, we use $\norm{\cdot}$ for the operator
norm $\norm{\cdot}_{\mathscr{B}(\mathcal{H})}$.

######  Proposition B.6.

Suppose $\mathcal{H}$ has embedding index $\alpha_{0}$ and let
$\alpha>\alpha_{0}$. Then, for all $\delta\in(0,1)$, when $n$ is sufficiently
large, with probability at least $1-\delta$,

$\norm{T_{\lambda}^{-\frac{1}{2}}(T-T_{X})T_{\lambda}^{-\frac{1}{2}}}\leq\frac{4}{3}u+(2u)^{\frac{1}{2}},$
(54)

where

$u=\frac{M_{\alpha}^{2}\lambda^{-\alpha}}{n}\ln{\frac{4\mathcal{N}(\lambda)(\norm{T}+\lambda)}{\delta\norm{T}}},$
(55)

and $\mathcal{N}(\lambda)=\mathcal{N}_{1}(\lambda)=\tr(TT_{\lambda}^{-1})$.

###### Proof.

We will prove by Lemma B.5. Let

$\displaystyle
A(x)=T_{\lambda}^{-\frac{1}{2}}(T_{x}-T)T_{\lambda}^{-\frac{1}{2}}$

and $A_{i}=A(x_{i})$. Then, $E(A_{i})=0$ and

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}A_{i}=T_{\lambda}^{-\frac{1}{2}}(T_{x}-T)T_{\lambda}^{-\frac{1}{2}}.$

Moreover, since

$\displaystyle
T_{\lambda}^{-\frac{1}{2}}T_{x}T_{\lambda}^{-\frac{1}{2}}=T_{\lambda}^{-\frac{1}{2}}K_{x}K_{x}^{*}T_{\lambda}^{-\frac{1}{2}}=T_{\lambda}^{-\frac{1}{2}}K_{x}\left[T_{\lambda}^{-\frac{1}{2}}K_{x}\right]^{*},$

from (38) we have

$\displaystyle\norm{T_{\lambda}^{-\frac{1}{2}}T_{x}T_{\lambda}^{-\frac{1}{2}}}=\norm{T_{\lambda}^{-\frac{1}{2}}K_{x}}_{\mathscr{B}(\mathbb{R},\mathcal{H})}^{2}=\norm{T_{\lambda}^{-\frac{1}{2}}h_{x}}_{\mathcal{H}}^{2}\leq
M_{\alpha}^{2}\lambda^{-\alpha}.$ (56)

By taking expectation, we also have
$\norm{T_{\lambda}^{-\frac{1}{2}}TT_{\lambda}^{-\frac{1}{2}}}\leq
M_{\alpha}^{2}\lambda^{-\alpha}$. Therefore, we get

$\displaystyle\norm{A}\leq\norm{T_{\lambda}^{-\frac{1}{2}}TT_{\lambda}^{-\frac{1}{2}}}+\norm{T_{\lambda}^{-\frac{1}{2}}T_{x}T_{\lambda}^{-\frac{1}{2}}}\leq
2M_{\alpha}^{2}\lambda^{-\alpha}=L.$

For the second part of the condition, using the fact that
$E(B-E(B))^{2}\preceq E(B^{2})$ for a self-adjoint operator $B$, where
$\preceq$ denotes the partial order induced by positive operators, we have

$\displaystyle E(A^{2})\preceq
E\left(T_{\lambda}^{-\frac{1}{2}}T_{x}T_{\lambda}^{-\frac{1}{2}}\right)^{2}\preceq
M_{\alpha}^{2}\lambda^{-\alpha}E\left(T_{\lambda}^{-\frac{1}{2}}T_{x}T_{\lambda}^{-\frac{1}{2}}\right)=M_{\alpha}^{2}\lambda^{-\alpha}TT_{\lambda}^{-1}=V,$

where the second $\preceq$ comes from (56) Finally,

$\displaystyle\norm{V}$
$\displaystyle=M_{\alpha}^{2}\lambda^{-\alpha}\norm{TT_{\lambda}^{-1}}=M_{\alpha}^{2}\lambda^{-\alpha}\frac{\lambda_{1}}{\lambda+\lambda_{1}}=M_{\alpha}^{2}\lambda^{-\alpha}\frac{\norm{T}}{\norm{T}+\lambda}\leq
M_{\alpha}^{2}\lambda^{-\alpha},$ $\displaystyle\tr V$
$\displaystyle=M_{\alpha}^{2}\lambda^{-\alpha}\tr\left[TT_{\lambda}^{-1}\right]=M_{\alpha}^{2}\lambda^{-\alpha}\mathcal{N}(\lambda),$
$\displaystyle B$ $\displaystyle=\ln\frac{4\tr
V}{\delta\norm{V}}=\ln\frac{4(\norm{T}+\lambda)\mathcal{N}(\lambda)}{\delta\norm{T}}.$

∎

### Covering number in reproducing kernel Hilbert space

Let us first recall the definition of covering numbers.

######  Definition B.7.

Let $(E,\norm{\cdot}_{E})$ be a normed space and $A\subset E$ be a subset. For
$\varepsilon>0$, we say $S\subseteq A$ is an $\varepsilon$-net of $A$ if for
any $a\in A$, there exists $s\in S$ such that $\norm{a-s}_{E}\leq\varepsilon$.
Moreover, we define the $\varepsilon$-covering number of $A$ to be

$\displaystyle\mathcal{N}(A,\norm{\cdot}_{E},\varepsilon)$
$\displaystyle=\inf\left\\{\absolutevalue{S}:S\text{ is an $\varepsilon$-net
of }A\right\\}.$ (57)

Li et al. [24, Lemma C.10] shows the following upper bound of covering numbers
of
$\mathcal{K}_{\lambda}=\left\\{T_{\lambda}^{-1}h_{x}\right\\}_{x\in\mathcal{X}}$.

######  Lemma B.8.

Assuming that $\mathcal{X}\subseteq\mathbb{R}^{d}$ is bounded and $k\in
C^{0,s}(\mathcal{X}\times\mathcal{X})$ for some $s\in(0,1]$. Then, we have

$\displaystyle\mathcal{N}\left(\mathcal{K}_{\lambda},\norm{\cdot}_{\infty},\varepsilon\right)$
$\displaystyle\leq C\left(\lambda\varepsilon\right)^{-\frac{2d}{s}},$ (58)

where $C$ is a positive constant not depending on $\lambda$ or $\varepsilon$.


# How to Mask in Error Correction Code Transformer: Systematic and Double
Masking

Seong-Joon Park1, Hee-Youl Kwak2, Sang-Hyo Kim3, Sunghwan Kim2, Yongjune Kim4,
Jong-Seon No1 Corresponding author.

###### Abstract

In communication and storage systems, error correction codes (ECCs) are
pivotal in ensuring data reliability. As deep learning’s applicability has
broadened across diverse domains, there is a growing research focus on neural
network-based decoders that outperform traditional decoding algorithms. Among
these neural decoders, Error Correction Code Transformer (ECCT) has achieved
the state-of-the-art performance among neural network-based decoders,
outperforming other methods by large margins. To further enhance the
performance of ECCT, we propose two novel methods. First, leveraging the
systematic encoding technique of ECCs, we introduce a new masking matrix for
ECCT, aiming to improve the performance and reduce the computational
complexity. Second, we propose a novel transformer architecture of ECCT called
a double-masked ECCT. This architecture employs two different mask matrices in
a parallel manner to learn more diverse features of the relationship between
codeword bits in the masked self-attention blocks. Extensive simulation
results show that the proposed double-masked ECCT outperforms the conventional
ECCT, achieving the state-of-the-art decoding performance among neural
network-based decoders with significant margins.

## Introduction

Over recent years, deep learning methods have experienced rapid advancements
and achieved phenomenal success in various tasks, such as natural language
processing (NLP), image classification, object detection, semantic
segmentation, etc. Among the various deep learning architectures available,
the transformer architecture (Vaswani et al. 2017) has consistently
demonstrated the state-of-the-art results in most tasks. After breaking
through in NLP, the application of transformer has expanded to include
computer vision tasks (Dosovitskiy et al. 2021; Liu et al. 2021), and again
demonstrated outstanding performances compared to the conventional neural
network architecture. The versatility of transformer has now extended to the
field of error correction codes (ECCs) (Choukroun and Wolf 2022a).

ECCs have played a pivotal role in ensuring reliability in wireless
communication and storage systems by serving as a key technology to correct
errors in noisy environments. The ECC research based on deep learning
architectures has primarily focused on decoders that offer superior error
correction performance. Stimulated by the advancement of deep learning
techniques, a new type of decoders based on neural networks has emerged (Kim
et al. 2018; Kim, Oh, and Viswanath 2020; Nachmani, Beery, and Burshtein 2016;
Dorner et al. 2018). These neural network-based decoders have overcome the
limitations of traditional algorithm-based decoders. Notably, among them, the
transformer-based ECC decoder achieves the state-of-the-art performance.

The transformer based ECC decoder, also called Error correction Code
Transformer (ECCT) (Choukroun and Wolf 2022a), applied a mask matrix in the
self-attention block to learn the noise in the communication channel. Since
not all bits in a codeword are equally related, ECCT can improve the
performance by using a mask matrix that facilitates learning of the relevance
between codeword bits. In the conventional ECCT work, the mask matrix is
derived from the parity check matrix (PCM) whose parity check equations
determine a direct relationship between codeword bits.

However, the problem is that numerous PCMs exist for the same codebook, which
raises the following question:
Which one of those PCMs is optimal to aid the self-attention mechanism in
ECCT?
We find that selecting a different PCM (i.e., different mask matrix) has a
crucial impact on the performance of ECCT. Hence, identifying the optimal PCM
for constructing a mask matrix is an important problem of ECCT, which has not
investigated yet.

In this work, we first introduce a novel mask matrix specifically tailored for
ECCT, which we term a _systematic mask matrix_ due to its construction based
on a systematic PCM. The systematic mask matrix has more masking positions
than the mask matrix used in the conventional ECCT. This property of the
systematic mask matrix makes the self-attention map _sparser_ , and enables
more compact and concentrated learning of the relationship between codeword
bits. It is a surprising observation given that systematic form of the matrix
is typically utilized for efficient encoding rather than decoding (Richardson
and Urbanke 2008). Yet, in ECCT, they play a pivotal role in enhancing
decoding performance, which is an interesting finding.

Next, we propose a novel transformer architecture called a double-masked (DM)
ECCT. This architecture consists of two parallel masked self-attention blocks,
each employing a distinct mask matrix. Utilizing two different mask matrices
enables the DM ECCT to capture diverse features of the bit relationship.

We apply the proposed methods to two representative ECCs:
Bose–Chaudhuri–Hocquenghem (BCH) and polar codes as in (Choukroun and Wolf
2022a). Through extensive simulations across diverse code parameters, we
demonstrate that _systematic mask matrices_ improve decoding performance,
while reducing decoding complexity. Furthermore, our DM ECCT, integrating both
systematic and conventional mask matrices, achieves the state-of-the-art
performance among neural network-based decoders for both BCH and polar codes.
To the best of our knowledge, this is the first work to propose a new mask
matrix structure tailored for ECCT. Additionally, our proposed DM ECCT is a
novel transformer architecture for ECC to utilize multiple mask matrices,
adding diversity to the ECCT architecture.

## Related Works

In this section, we briefly review the deep learning approaches to ECC
applications, such as the neural network-based ECC decoders. There are mainly
two approaches: The model-based approach and the model-free approach.

### Model-Based Approach

The first approach is to implement a conventional decoding methods (e.g.,
belief propagation (BP) decoder and min-sum (MS) decoder) on a neural network.
These neural decoders unfold the iterative decoding operation on the Tanner
graph into a deep neural network. Nachmani et al. (Nachmani et al. 2018)
proposed a neural decoder based on the recurrent neural network for BCH codes
and achieved the performance improvement over the standard BP decoder. Dai et
al. (Dai et al. 2021) modified the neural MS decoder for protograph low-
density parity-check (LDPC) codes. A parameter sharing mechanism was proposed
for training scalability to long codes, which also reduces the training
complexity and memory cost. Furthermore, a number of studies exhibited that
neural network-based BP and MS decoders outperform the traditional decoders
(Nachmani and Wolf 2019, 2021; Kwak et al. 2022; Buchberger et al. 2021;
Lugosch and Gross 2017). However, these model-based neural decoders might face
restrictive performance limits due to architectural constraints.

### Model-Free Approach

The second approach is a model-free approach, which employs neural network
architectures with no prior knowledge of decoding algorithms. This approach is
not restricted to the conventional decoding models but encounters a
significant challenge initially. The model-free approach faces the overfitting
problem since it is impractical to train all codewords in a codebook. However,
Bennatan et al. (Bennatan, Choukroun, and Kisilev 2018) proposed a
preprocessing that enables the black box model decoder to overcome the
overfitting problem. They utilized the syndrome to learn noise only with the
all-zero codeword. Also, they combined recurrent neural network architecture
with the preprocessing. ECCT is another work that implemented the transformer
without the overfitting problem using the same preprocessing and achieved
excellent decoding performance through the masked self-attention mechanism.
However, in the previous ECCT research, the mask matrix was directly derived
from the PCM of the conventional decoding algorithm, rather than being
adjusted for ECCT.

## Background

In this section, we briefly summarize some background on the ECCs and the
preprocessing and postprocessing of the conventional ECCT (Choukroun and Wolf
2022a).

### Error Correction Codes

Let $C$ be a linear code. A codeword $x\in C\subset\\{0,1\\}^{n}$ can be
defined by a generator matrix $G$ of size $k\times n$ and a PCM $H$ of size
$(n-k)\times n$, which satisfies $GH^{T}=0$ over $\\{0,1\\}$ with modulo $2$
addition. In other words, a codeword $x$ can be determined by the constraint
$Hx=0$. Let $x_{s}$ be a binary phase shift keying modulation of $x$ (i.e.,
$x_{s}=+1$ if $x=0$ and $x_{s}=-1$ if $x=1$) and let $y$ be a channel output
of $x_{s}$ after passing the additive white Gaussian noise channel
($y=x_{s}+z$, where $z$ denotes Gaussian random noise, i.e., $z\sim
N(0,\sigma^{2})$).

The objective of the decoder ($f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$) is
to recover the original transmitted codeword $x$ by correcting errors. When
$y$ is received, the decoder first determines if the received signal is
corrupted by checking the syndrome $s(y)=Hy_{b}$, where
$y_{b}=\text{bin}(\text{sign}(y))$. Here, $\text{sign}(a)$ represents $+1$ if
$a\geq 0$ and $-1$ otherwise and $\text{bin}(-1)=1$, $\text{bin}(+1)=0$. If
$s(y)$ is non-zero vector, it is detected that $y$ is distorted during the
transmission, and the decoder initiates the error correction process. ECCT
(Choukroun and Wolf 2022a) employs the transformer architecture to approximate
the role of the ECC decoder.

### Preprocessing and Postprocessing

By employing the preprocessing method in (Bennatan, Choukroun, and Kisilev
2018), the all-zero codeword is enough for training, which makes the ECCT
robust to overfitting problems. The preprocessing conducts input embedding as
$\tilde{y}=[|y|,s(y)]$, where $|y|$ is the magnitude of $y$, and
$[\cdot,\cdot]$ denotes the concatenation of two vectors. The objective of the
ECCT is to estimate the multiplicative noise $\tilde{z}_{s}$, which is defined
by

$y=x_{s}+z=x_{s}\tilde{z}_{s}.$ (1)

Since the ECCT estimates the multiplicative noise, $f(y)=\hat{z}_{s}$ and the
estimation of $x$ is $\hat{x}=\text{bin}(\text{sign}(yf(y)))$. If the
multiplicative noise is correctly estimated, then
$\text{sign}(\tilde{z}_{s})=\text{sign}(\hat{z}_{s})$ and
$\text{sign}(\tilde{z_{s}}\hat{z}_{s})=1$. In this case, $\hat{x}$ is obtained
by

$\displaystyle\hat{x}$
$\displaystyle=\text{bin}(\text{sign}(yf(y)))=\text{bin}(\text{sign}(x_{s}\tilde{z_{s}}\hat{{z}_{s}}))$
$\displaystyle=\text{bin}(\text{sign}(x_{s}))$ $\displaystyle=x.$

(a) Conventional mask matrix

(b) Systematic mask matrix

Figure 1: Two different types of mask matrices: (a) The conventional mask is
determined by the conventional PCM (Choukroun and Wolf 2022a), (b) the
systematic mask matrix is determined by the systematically transformed PCM.
The non-zero entries in PCMs and masking positions in the mask matrix are
depicted in colored boxes. The proposed systematic mask matrix masks more
values than the conventional mask matrix, resulting in sparser self-attention
maps.

## Proposed Methods

We propose the systematic mask matrix for the ECCT architecture and the DM
ECCT with two different mask matrices. The proposed systematic mask matrix and
DM ECCT architecture are shown in Figures 1 and 2, respectively.

### Systematic Mask

In the ECCT, the mask matrix constructed by the PCM $H$ facilitates the
learning. Since the mask matrix is uniquely determined by the PCM. There is
one-to-one correspondence between the PCM and the mask matrix. Unlike the ECCT
in (Choukroun and Wolf 2022a), we construct the systematic mask matrix from a
specific PCM, which is defined as systematic PCM. To construct the systematic
mask matrix, we first transform the PCM as a systematic form (i.e., reduced
row echelon form) by Gaussian elimination technique. The systematically formed
PCM $H_{\rm sys}$ is expressed as $H_{\rm sys}=[I_{n-k}~{}P]$, where $I_{n-k}$
is the identity matrix of size $(n-k)\times(n-k)$ and $P$ is a matrix of size
$(n-k)\times k$. Then, we can construct the systematic mask matrix from
$H_{\rm sys}$ by Algorithm 1, which is slightly modified from (Choukroun and
Wolf 2022a). The conventional mask matrix (Choukroun and Wolf 2022a) and the
proposed systematic mask matrix for the BCH code $(31,11)$ are compared in
Figure 1.

Algorithm 1 Mask matrix construction

⬇

1def g(systematic, conv_PCM):

2 if systematic is True:

3 PCM = make_sys(conv_PCM)

4 else:

5 PCM = conv_PCM

6 nrow, ncol = PCM.size

7 mask_size = ncol + nrow

8 mask = eye(mask_size, mask_size)

9 for ii in range(nrow):

10 idx = where(PCM[ii] > 0)[0]

11 for jj in idx:

12 for kk in idx:

13 mask[jj, kk] += 1

14 mask[kk, jj] += 1

15 mask[N + ii, jj] += 1

16 mask[jj, N + ii] += 1

17 return $-\infty$ ($\neg$ mask)

Figure 2: Architecture of the DM ECCT.

As shown in Figure 1(b), the first $(n-k)\times(n-k)$ submatrix of the
systematic mask matrix is the identity matrix $I_{n-k}$ of $H_{\rm sys}$,
which is for efficient encoding. Also, the systematic mask matrix has more
masking positions compared to the conventional mask matrix. In other words,
employing the systematic mask matrix makes the masked self-attention map
sparser than the conventional mask matrix. As the masked self-attention map
becomes sparse, the model tends to focus more on the unmasked locations. Since
not all positions in the codeword are equally related, it is important to
focus on the highly related positions in the codeword during the self-
attention mechanism. Therefore, employing an “appropriate” mask matrix leads
to better training and decoding for ECCT. Furthermore, since only unmasking
positions in the self-attention map participate in the training, the mask
matrix with a large portion of masking positions leads to a lower training
complexity. Due to these reasons, the proposed ECCT using a systematic mask
matrix, which we call a systematic-masked (SM) ECCT from now on, is expected
to have a better complexity-decoding performance tradeoff than the
conventional ECCT.

We propose to use the systematic mask matrix for the masked self-attention
mechanism instead of the conventional mask matrix. Changing the conventional
mask matrix to the systematic mask matrix leads to the enhancement in both
error correction performance and computational complexity of ECCT. This
improvement is not limited to specific code lengths or code rates but to a
wide range of coding parameters for various ECCs.

### Double-Masked ECCT

To further improve the decoding performance, we propose a novel architecture
called a DM ECCT. In the DM ECCT, we utilize the two different mask matrices
for two input embedded vectors in the masked self-attention module. The
overall architecture of the DM ECCT is illustrated in Figure 2.

During the initial embedding of the DM ECCT, the received codeword $y$ is
converted to $\tilde{y}_{1}=[|y|,s_{1}(y)]$ and
$\tilde{y}_{2}=[|y|,s_{2}(y)]$, where $s_{1}(y)=H_{1}y_{b}$ and
$s_{2}(y)=H_{2}y_{b}$. $H_{1}$ and $H_{2}$ can be any PCMs that have the same
codebook. Then, $\tilde{y}_{1}$ and $\tilde{y}_{2}$ with $2n-k$ bits are
projected to $d$ dimensional embedding. After passing the initial embedding
layer, the decoder is defined as a concatenation of $N$ decoder layers. The
decoder layer consists of one masked self-attention, followed by one feed-
forward neural network (FFNN). For each step, a normalization layer precedes
and a residual connection is established. Finally, the output layer takes the
concatenated vector of two output vectors of the decoder layer. It consists of
three fully connected (FC) layers, applied after a normalization layer. The
first FC layer reduces $2\times(2n-k)$ dimension vector to $2n-k$ dimension,
the second reduces $d$ dimensional embedding to a one-dimensional $2n-k$
vector, and the third reduces $2n-k$ to an $n$ dimensional vector. The output
represents an estimate of soft multiplicative noise $f(y)=\hat{z}_{s}$ with
which the decoding is completed by bit flipping.

A key structure of a DM ECCT is that we employ two different mask matrices for
two input vectors. The input vector determined by $\tilde{y_{i}}$ is masked
with $M_{i}$, since both $\tilde{y_{i}}$ and $M_{i}$ are determined by
$H_{i}$, for $i=1,2$. As mentioned above, the relevance between codeword bits
are associated in the PCM, and numerous PCMs exist for the same codebook.
Rather than utilizing a single PCM (or a single mask matrix), utilizing a pair
of PCMs can provide a diversity to the decoder. In the decoder layer, the
proposed DM ECCT architecture captures distinct features generated by two
different PCMs. These features are subsequently fused using concatenation and
processed by the FC layers in the output layer. Such a design allows the DM
ECCT to adeptly discern the relationship between codeword bits, ultimately
achieving state-of-the-art decoding performance among neural network-based
decoders.

$N=2$
---
$d$ | $32$ | $64$ | $128$
Code | SNR | ECCT |  | SM
---
ECCT
ECCT |  | SM
---
ECCT
ECCT |  | SM
---
ECCT
| DM
---
ECCT
BCH $(31,11)$ |  $4$ dB | $3.43e-2$ | $1.77e-2$ | $2.74e-2$ | $1.17e-2$ | $1.97e-2$ | $9.06e-3$ | $\mathbf{6.11e-3}$
$5$ dB | $1.47e-2$ | $6.12e-3$ | $1.06e-2$ | $3.46e-3$ | $6.60e-3$ | $2.36e-3$ | $\mathbf{1.38e-3}$
$6$ dB | $5.02e-3$ | $1.70e-3$ | $3.05e-3$ | $7.12e-4$ | $1.66e-3$ | $4.43e-4$ | $\mathbf{1.78e-4}$
BCH $(31,16)$ |  $4$ dB | $1.46e-2$ | $1.06e-2$ | $1.20e-2$ | $8.22e-3$ | $8.38e-3$ | $5.63e-3$ | $\mathbf{4.07e-3}$
$5$ dB | $4.40e-3$ | $3.05e-3$ | $3.39e-3$ | $2.09e-3$ | $1.95e-3$ | $1.17e-3$ | $\mathbf{7.38e-4}$
$6$ dB | $9.17e-4$ | $6.20e-4$ | $6.32e-4$ | $3.32e-4$ | $2.99e-4$ | $1.72e-4$ | $\mathbf{7.65e-5}$
BCH $(63,30)$ |  $4$ dB | $4.32e-2$ | $3.23e-2$ | $4.07e-2$ | $2.49e-2$ | $3.63e-2$ | $2.15e-2$ | $\mathbf{1.81e-2}$
$5$ dB | $1.88e-2$ | $1.28e-2$ | $1.72e-2$ | $8.60e-3$ | $1.41e-2$ | $6.99e-3$ | $\mathbf{4.80e-3}$
$6$ dB | $5.70e-3$ | $3.72e-3$ | $4.96e-3$ | $2.11e-3$ | $3.53e-3$ | $1.45e-3$ | $\mathbf{8.61e-4}$
BCH $(63,45)$ |  $4$ dB | $1.58e-2$ | $1.16e-2$ | $1.27e-2$ | $9.63e-3$ | $1.14e-2$ | $8.34e-3$ | $\mathbf{6.41e-3}$
$5$ dB | $4.41e-3$ | $2.87e-3$ | $3.16e-3$ | $2.21e-3$ | $2.64e-3$ | $1.72e-3$ | $\mathbf{1.05e-3}$
$6$ dB | $7.57e-4$ | $4.13e-4$ | $4.35e-4$ | $2.97e-4$ | $3.38e-4$ | $2.00e-4$ | $\mathbf{1.02e-4}$
Polar $(64,22)$ |  $4$ dB | $4.03e-2$ | $3.50e-2$ | $2.76e-2$ | $1.74e-2$ | $1.44e-2$ | $1.11e-2$ | $\mathbf{8.59e-3}$
$5$ dB | $1.66e-2$ | $1.33e-2$ | $9.34e-3$ | $4.51e-3$ | $3.91e-3$ | $2.30e-3$ | $\mathbf{1.66e-3}$
$6$ dB | $5.17e-3$ | $3.42e-3$ | $2.34e-3$ | $7.05e-4$ | $1.08e-3$ | $2.73e-4$ | $\mathbf{1.52e-4}$
Polar $(64,32)$ |  $4$ dB | $1.74e-2$ | $1.29e-2$ | $1.20e-2$ | $1.01e-2$ | $9.04e-3$ | $7.84e-3$ | $\mathbf{5.62e-3}$
$5$ dB | $5.84e-3$ | $3.99e-3$ | $3.33e-3$ | $2.79e-3$ | $2.39e-3$ | $1.97e-3$ | $\mathbf{1.23e-3}$
$6$ dB | $1.39e-3$ | $8.63e-4$ | $6.22e-4$ | $5.17e-4$ | $4.35e-4$ | $3.48e-4$ | $\mathbf{1.60e-4}$
Polar $(64,48)$ |  $4$ dB | $6.75e-3$ | $7.44e-3$ | $5.37e-3$ | $1.69e-1$ | $4.17e-3$ | $4.77e-3$ | $\mathbf{3.43e-3}$
$5$ dB | $1.42e-3$ | $1.62e-3$ | $1.02e-3$ | $1.13e-3$ | $6.95e-4$ | $8.04e-4$ | $\mathbf{4.95e-4}$
$6$ dB | $1.83e-4$ | $2.15e-4$ | $1.24e-4$ | $1.42e-4$ | $7.47e-5$ | $8.58e-5$ | $\mathbf{4.27e-5}$
Table 1: A comparison of BER for three different methods at three different
SNR values ($4$ dB, $5$ dB, $6$ dB). This table shows the BER performance for
$N=2$ and $d=\\{32,64,128\\}$. Best results are in bold.

(a) BCH $(31,11)$

(b) BCH $(31,16)$

(c) BCH $(63,30)$

(d) Polar $(64,22)$

Figure 3: The BER performance of BCH and polar codes for $N=2$ and $d=128$.
$N=6$
---
$d$ | 32 | 64 | 128
Code | SNR | ECCT |  | SM
---
ECCT
ECCT |  | SM
---
ECCT
ECCT |  | SM
---
ECCT
| DM
---
ECCT
BCH $(31,11)$ |  $4$ dB | $1.22e-2$ | $5.22e-3$ | $8.35e-3$ | $2.48e-3$ | $4.37e-3$ | $1.72e-3$ | $\mathbf{8.70e-4}$
$5$ dB | $3.28e-3$ | $1.27e-3$ | $1.92e-3$ | $5.91e-4$ | $9.69e-4$ | $3.22e-4$ | $\mathbf{8.57e-5}$
$6$ dB | $4.94e-4$ | $2.10e-4$ | $2.37e-4$ | $8.23e-5$ | $1.10e-4$ | $4.89e-5$ | $\mathbf{6.70e-6}$
BCH $(31,16)$ |  $4$ dB | $5.55e-3$ | $2.79e-3$ | $3.50e-3$ | $3.11e-3$ | $2.97e-3$ | $1.71e-3$ | $\mathbf{1.07e-3}$
$5$ dB | $1.02e-3$ | $4.43e-4$ | $6.50e-4$ | $5.24e-4$ | $4.66e-4$ | $2.52e-4$ | $\mathbf{8.35e-5}$
$6$ dB | $1.12e-4$ | $3.11e-5$ | $6.65e-5$ | $5.66e-5$ | $4.76e-5$ | $2.35e-5$ | $\mathbf{5.75e-6}$
BCH $(63,30)$ |  $4$ dB | $8.41e-3$ | $5.63e-3$ | $7.36e-3$ | $4.41e-3$ | $1.87e-2$ | ${9.00e-3}$ | $\mathbf{8.04e-3}$
$5$ dB | $1.37e-3$ | $8.33e-4$ | $1.06e-3$ | $5.24e-4$ | $4.41e-3$ | ${1.96e-3}$ | $\mathbf{1.18e-3}$
$6$ dB | $1.10e-4$ | $5.09e-5$ | $7.02e-5$ | $2.68e-5$ | $5.28e-4$ | ${2.51e-4}$ | $\mathbf{7.61e-5}$
BCH $(63,45)$ |  $4$ dB | $1.00e-2$ | $5.03e-3$ | $6.12e-3$ | $2.05e-3$ | $4.53e-3$ | $3.76e-3$ | $\mathbf{2.74e-3}$
$5$ dB | $2.49e-3$ | $8.95e-4$ | $1.59e-3$ | $2.49e-4$ | $5.58e-4$ | $4.32e-4$ | $\mathbf{2.62e-4}$
$6$ dB | $6.83e-4$ | $1.07e-4$ | $5.42e-4$ | $1.82e-5$ | $3.15e-5$ | $1.61e-5$ | $\mathbf{9.31e-6}$
Polar $(64,22)$ |  $4$ dB | $5.22e-3$ | $3.32e-3$ | $2.52e-3$ | $1.59e-3$ | $2.16e-3$ | $5.84e-4$ | $\mathbf{4.82e-4}$
$5$ dB | $9.64e-4$ | $5.01e-4$ | $3.50e-4$ | $1.76e-4$ | $1.76e-4$ | $3.28e-5$ | $\mathbf{2.94e-5}$
$6$ dB | $1.01e-4$ | $4.44e-5$ | $2.66e-5$ | $1.39e-5$ | $1.22e-5$ | $1.37e-6$ | $\mathbf{6.39e-7}$
Polar $(64,32)$ |  $4$ dB | $3.59e-3$ | $3.06e-3$ | $2.30e-3$ | $2.09e-3$ | $1.25e-3$ | $9.10e-4$ | $\mathbf{9.03e-4}$
$5$ dB | $5.21e-4$ | $4.22e-4$ | $2.94e-4$ | $2.66e-4$ | $1.25e-4$ | $8.28e-5$ | $\mathbf{8.07e-5}$
$6$ dB | $4.56e-5$ | $3.10e-5$ | $1.98e-5$ | $1.46e-5$ | $6.57e-6$ | $4.47e-6$ | $\mathbf{3.70e-6}$
Polar $(64,48)$ |  $4$ dB | $6.75e-3$ | $7.44e-3$ | $5.37e-3$ | $1.69e-1$ | $2.05e-3$ | $\mathbf{1.68e-3}$ | ${1.70e-3}$
$5$ dB | $1.42e-3$ | $1.62e-3$ | $1.02e-3$ | $1.13e-3$ | $2.50e-4$ | $2.12e-4$ | $\mathbf{2.11e-4}$
$6$ dB | $1.83e-4$ | $2.15e-4$ | $1.24e-4$ | $1.42e-4$ | $1.77e-5$ | $1.83e-5$ | $\mathbf{1.73e-5}$
Table 2: A comparison of BER for three different methods at three different
SNR values ($4$ dB, $5$ dB, $6$ dB). This table shows the BER performance for
$N=6$ and $d=\\{32,64,128\\}$. Best results are in bold.

(a) BCH $(31,11)$

(b) BCH $(31,16)$

(c) BCH $(63,30)$

(d) Polar $(64,22)$

Figure 4: The BER performance of BCH and polar codes for $N=6$ and $d=128$.

## Training

The goal of the proposed decoder is to learn the multiplicative noise
$\tilde{z}_{s}$ in (1) and recover an original transmitted signal $x$. We can
obtain the multiplicative noise by
$\tilde{z}_{s}=\tilde{z}_{s}x^{2}_{s}=yx_{s}$. Then, the target multiplicative
noise for binary cross-entropy loss function is defined by
$\tilde{z}=\text{bin}(\text{sign}(yx_{s}))$. Finally, the cross-entropy loss
function for a received codeword $y$ is defined as

$\mathcal{L}=-\sum^{n}_{i=1}\tilde{z}_{i}\log(\sigma(f(y)))+(1-\tilde{z}_{i})\log(1-\sigma(f(y))).$

To compare with the conventional ECCT fairly, we adopt the same training setup
as used in the previous work. We use the Adam optimizer (Kingma and Ba 2014)
and conduct 1000 epochs. Each epoch consists of 1000 minibatches, where each
minibatch is composed of 128 samples.

(a) Sparsity

(b) Conventional ECCT

(c) Proposed ECCT

Figure 5: (a) Sparsity comparison of the self-attention map employing non-
systematic and systematic mask matrices for different codes. (b) The PCM and
mask matrix of polar code $(64,22)$, which is utilized in the conventional
ECCT. (c) The PCM and mask matrix of polar code $(64,22)$, which is utilized
in our work.

## Experiments

To evaluate the efficacy of our proposed methods, we assess the bit error rate
(BER) performance of both SM ECCT and DM ECCT for BCH codes and polar codes,
and then compare with the conventional ECCT (Choukroun and Wolf 2022a). The
implementation of the conventional ECCT is taken from (Choukroun and Wolf
2022b). For the testing, we collect at least 500 frame errors at each signal-
to-noise ratio (SNR) value for at least $10^{5}$ random codewords.

The DM ECCT utilizes the systematic and conventional mask matrices for two
self-attention blocks. For polar codes, however, we utilize the systematic
mask matrix and the mask matrix constructed based on the modified conventional
PCM. In the following section, it will be mentioned that the upper $n\times n$
submatrix in the conventional mask matrix of polar code is always unmasked and
the DM ECCT obtains the dense self-attention map. The dense self-attention map
hinders the ECCT from effectively learning the relationship between codeword
bits. Thus, we modify the conventional PCM of the polar codes by the row
reduction. Starting from the first row, when the row contains all positions of
one’s of the next row, we eliminate the ones in the row. Utilizing both
systematic and modified conventional mask matrices provides diversity gains to
the DM ECCT.

Tables 1 and 2 show the BER performances of the conventional ECCT, the
proposed SM ECCT, and the proposed DM ECCT for $N=\\{2,6\\}$ and
$d=\\{32,64,128\\}$. The first, second, and the third rows of each codes
correspond to the BER performances at SNR $4$ dB, $5$ dB, and $6$ dB,
respectively. For the same $N$ and SNR, the proposed DM ECCT achieves the best
BER in most cases, except for BCH code $(63,30)$ when $N=6$ and $d=128$. The
SM ECCT outperforms the conventional ECCT despite its lower computational
complexity. Figures 3 and 4 show the decoding performance of BCH codes and
polar codes for $N=2$, $d=128$ and $N=6$, $d=128$, respectively. The DM ECCT,
notably at a low code rate, significantly outperforms the conventional ECCT by
more than 1 dB for high SNR. Furthermore, the decoding performance for both SM
ECCT and DM ECCT continues to decrease, even when the ECCT curve starts to
flatten, indicating the potential of the proposed ECCTs to perform well at
high SNR points. Given that the conventional ECCT outperforms previous neural
network-based decoding algorithms as noted by Choukroun and Wolf (Choukroun
and Wolf 2022a), our work can be recognized as the new state-of-the art
solution for ECC decoding.

## Discussion

### Complexity Analysis

Figure 5(a) shows the sparsity of the self-attention map employing
conventional and systematic masks with respect to the full self-attention map
without masking. Utilizing the systematic mask, sparsity levels rise from 72%
to 74% for BCH code $(31,11)$, from 56% to 67% for BCH code $(63,30)$, and
dramatically from 52% to 82% for polar code $(64,22)$. As depicted in Figures
5(b) and 5(c), the systematic mask matrix shows a notably larger portion of
masking positions than the conventional mask matrix, especially for polar
codes. This is attributed to the fact that the first row in the conventional
PCM of the polar codes is the all-ones vector. In such case, the upper
$n\times n$ submatrix of the conventional mask matrix is always unmasked
according to the Algorithm 1. However, the first row of the systematic PCM is
not the all-ones vector and a large portion of the upper $n\times n$ submatrix
is masked. This sparsity improvement in the self-attention maps leads to a
reduction in computational complexity.

In terms of the computational complexity, the use of the proposed systematic
mask matrix contributes to reducing the computational complexity. For the DM
ECCT, it requires twice of a complexity in the decoder layer, as it has two
input embedded vectors that pass through all blocks in the decoder layer.
However, the architecture of DM ECCT facilitates the parallel operations in
the decoder layers; hence, DM ECCT can improve decoding performance while
maintaining the decoding latency.

## Conclusion

In this paper, we aimed to improve the performance of ECC decoding using a
novel architecture of the ECCT. We first proposed the systematic mask matrix,
which is more suitable for the ECCT than the conventional mask matrix.
Additionally, we proposed the novel architecture of DM ECCT by employing two
mutually complementary mask matrices.

Through extensive simulations, we demonstrated that the proposed methods
outperform the conventional ECCT. We first achieved performance and
computational complexity enhancements by the systematic mask matrix. The
sparsity incurred by the systematic mask prompts the ECCT to focus on more
important positions, enhancing decoding performance. In particular, more
pronounced improvements are observed in low-rate codes. Traditionally, the
systematic form of the matrix has been employed for efficient encoding in
conventional decoders (e.g., BP, MS decoders). However, our results highlight
its critical importance in the decoding process of ECCT as well.

Also, we showed that the proposed DM ECCT architecture contributes to decoding
performance improvement. We utilized two different mask matrices, systematic
and conventional masks, in a parallel manner, which provided diversity gains
to the decoder. The DM ECCT notably enhances decoding performance over the
conventional ECCT for both BCH codes and polar codes, achieving the state-of-
the-art decoding performance among neural network-based decoders with
considerable margins.

## References

  * Bennatan, Choukroun, and Kisilev (2018) Bennatan, A.; Choukroun, Y.; and Kisilev, P. 2018.  Deep learning for decoding of linear codes-a syndrome-based approach.  In _Proceedings of 2018 IEEE International Symposium on Information Theory (ISIT)_ , 1595–1599. IEEE.
  * Buchberger et al. (2021) Buchberger, A.; Hager, C.; Pfister, H. D.; Schmalen, L.; and Amat, A. G. I. 2021\.  Pruning and quantizing neural belief propagation decoders.  _IEEE Journal of Selected Areas in Communications_ , 39(7): 1957–1966.
  * Choukroun and Wolf (2022a) Choukroun, Y.; and Wolf, L. 2022a.  Error correction code transformer.  In _Advances in Neural Information Processing Systems_.
  * Choukroun and Wolf (2022b) Choukroun, Y.; and Wolf, L. 2022b.  Error correction code transformer.  https://github.com/yoniLc/ECCT.  Accessed: 2023-05-22.
  * Dai et al. (2021) Dai, J.; Tan, K.; Si, Z.; Niu, K.; Chen, M.; Poor, H. V.; and Cui, S. 2021.  Learning to decode protograph LDPC codes.  _IEEE Journal of Selected Areas in Communications_ , 39(7): 1983–1999.
  * Dorner et al. (2018) Dorner, S.; Cammerer, S.; Hoydis, J.; and Brink, S. 2018.  Deep learning based communication over the air.  _IEEE Journal of Selected Topics in Signal Processing_ , 12(1): 132–143.
  * Dosovitskiy et al. (2021) Dosovitskiy, A.; Beyer, L.; Kolesnikov, A.; Weissenborn, D.; Zhai, X.; Unterthiner, T.; Dehghani, M.; Minderer, M.; Heigold, G.; Gelly, S.; Uszkoreit, J.; and Houlsby, N. 2021.  An image is worth $16\times 16$ words: Transformers for image recognition at scale.  In _International Conference on Learning Representations (ICLR)_.
  * Kim et al. (2018) Kim, H.; Jiang, Y.; Rana, R.; Kannan, S.; Oh, S.; and Viswanath, P. 2018.  Communication algorithms via deep learning.  In _International Conference on Learning Representations (ICLR)_.
  * Kim, Oh, and Viswanath (2020) Kim, H.; Oh, S.; and Viswanath, P. 2020.  Physical layer communication via deep learning.  _IEEE Journal of Selected Topics in Information Theory_ , 1(1): 5–18.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A method for stochastic optimization.  In _arXiv preprint arXiv:1412.6980_.
  * Kwak et al. (2022) Kwak, H.-Y.; Kim, J.-W.; Kim, Y.; Kim, S.-H.; and No, J.-S. 2022.  Neural min-sum decoding for generalized LDPC codes.  _IEEE Communications Letters_ , 26(12): 2841–2845.
  * Liu et al. (2021) Liu, Z.; Lin, Y.; Cao, Y.; Hu, H.; Wei, Y.; Zhang, Z.; Lin, S.; and Guo, B. 2021\.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _IEEE/CVF International Conference on Computer Vision (ICCV)_.
  * Lugosch and Gross (2017) Lugosch, L.; and Gross, W. J. 2017.  Neural offset min-sum decoding.  In _Proceedings of 2017 IEEE International Symposium on Information Theory (ISIT)_ , 1316–1365. IEEE.
  * Nachmani, Beery, and Burshtein (2016) Nachmani, E.; Beery, Y.; and Burshtein, D. 2016.  Learning to decode linear codes using deep learning.  In _2016 54th Annual Allerton Conference on Communications, Control, and Computing (Allerton)_ , 341–346. IEEE.
  * Nachmani et al. (2018) Nachmani, E.; Marciano, E.; Lugosch, L.; Gross, W. J.; Burshtein, D.; and Beery, Y. 2018.  Deep learning methods for improved decoding of linear codes.  _IEEE Journal of Selected Topics in Signal Processing_ , 12(1): 119–131.
  * Nachmani and Wolf (2019) Nachmani, E.; and Wolf, L. 2019.  Hyper-graph-network decoders for block codes.  In _Advances in Neural Information Processing Systems_ , 2326–2336.
  * Nachmani and Wolf (2021) Nachmani, E.; and Wolf, L. 2021.  Autoregressive belief propagation for decoding block codes.  In _arXiv preprint arXiv:2103.11780_.
  * Richardson and Urbanke (2008) Richardson, T. J.; and Urbanke, R. 2008.  _Modern coding theory_.  Cambridge Univ. Press.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , 5998–6008.