# Spectrally Transformed Kernel Regression

Runtian Zhai, Rattana Pukdee, Roger Jin, Maria-Florina Balcan, Pradeep
Ravikumar
Carnegie Mellon University
<EMAIL_ADDRESS>
###### Abstract

Unlabeled data is a key component of modern machine learning. In general, the
role of unlabeled data is to impose a form of smoothness, usually from the
similarity information encoded in a base kernel, such as the
$\epsilon$-neighbor kernel or the adjacency matrix of a graph. This work
revisits the classical idea of spectrally transformed kernel regression
(STKR), and provides a new class of general and scalable STKR estimators able
to leverage unlabeled data. Intuitively, via spectral transformation, STKR
exploits the data distribution for which unlabeled data can provide additional
information. First, we show that STKR is a principled and general approach, by
characterizing a universal type of “target smoothness”, and proving that any
sufficiently smooth function can be learned by STKR. Second, we provide
scalable STKR implementations for the inductive setting and a general
transformation function, while prior work is mostly limited to the
transductive setting. Third, we derive statistical guarantees for two
scenarios: STKR with a known polynomial transformation, and STKR with kernel
PCA when the transformation is unknown. Overall, we believe that this work
helps deepen our understanding of how to work with unlabeled data, and its
generality makes it easier to inspire new methods.

##  1 Introduction

The past decade has witnessed a surge of new and powerful algorithms and
architectures for learning representations (Vaswani et al., 2017; Devlin et
al., 2019; Chen et al., 2020; He et al., 2022); spurred in part by a boost in
computational power as well as increasing sizes of datasets. Due to their
empirical successes, providing an improved theoretical understanding of such
representation learning methods has become an important open problem. Towards
this, a big advance was made recently by HaoChen et al. (2021), who showed
that when using a slight variant of popular contrastive learning approaches,
termed spectral contrastive learning, the optimal learnt features are the
top-$d$ eigenfunctions of a population augmentation graph. This was further
extended to other contrastive learning approaches (Johnson et al., 2023;
Cabannes et al., 2023), as well as more generally to all augmentation-based
self-supervised learning methods (Zhai et al., 2024).

A high-level summary of this recent line of work is as follows: The self-
supervised learning approaches implicitly specify inter-sample similarity
encoded via a Mercer base kernel. Suppose this kernel has the spectral
decomposition
$K(x,x^{\prime})=\sum_{i=1}^{\infty}\lambda_{i}\psi_{i}(x)\psi_{i}(x^{\prime})$,
where $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq 0$. The above line of work
then showed that recent representation learning objectives can learn the
optimal $d$ features, which are simply the top-$d$ eigenfunctions
$[\psi_{1},\cdots,\psi_{d}]$ of this base kernel. Given these $d$ features, a
“linear probe” is learned atop via regression. It can be seen that this
procedure is equivalent to kernel regression with the truncated kernel
$K_{d}(x,x^{\prime})=\sum_{i=1}^{d}\lambda_{i}\psi_{i}(x)\psi_{i}(x^{\prime})$.
More generally, one can extend this to regression with a spectrally
transformed kernel (STK)
$K_{s}(x,x^{\prime})=\sum_{i=1}^{\infty}s(\lambda_{i})\psi_{i}(x)\psi_{i}(x^{\prime})$,
where $s:[0,+\infty)\rightarrow[0,+\infty)$ is a general transformation
function. We call this generalized method spectrally transformed kernel
regression (STKR). Then, $K_{d}$ amounts to an STK with the “truncation
function” $s(\lambda_{i})=\lambda_{i}\bm{1}_{\\{i\leq d\\}}$.

In fact, STK and STKR were quite popular two decades ago in the context of
semi-supervised learning, which similar to more recent representation learning
approaches, aims to leverage unlabeled data. Their starting point again was a
base kernel encoding inter-sample similarity, but unlike recent representation
learning approaches, at that period this base kernel was often explicitly
rather than implicitly specified. For manifold learning this was typically the
$\epsilon$-neighbor or the heat kernel (Belkin & Niyogi, 2003). For unlabeled
data with clusters, this was the cluster kernel (Chapelle et al., 2002). And
for graph structured data, this was typically the (normalized) adjacency or
Laplacian matrix of an explicitly specified adjacency graph (Chung, 1997;
Belkin & Niyogi, 2003). A range of popular approaches then either extracted
top eigenfunctions, or learned kernel machines. These methods include LLE
(Roweis & Saul, 2000), Isomap (Tenenbaum et al., 2000), Laplacian eigenmap
(Belkin & Niyogi, 2003) for manifold learning; spectral clustering (Ng et al.,
2001) for clustered data; and label propagation (Zhu & Ghahramani, 2002; Zhou
et al., 2003) for graph structured data. With respect to kernel machines,
Bengio et al. (2004) linked these approaches to kernel PCA, and Chapelle et
al. (2002); Smola & Kondor (2003); Zhu et al. (2006) proposed various types of
STK.

In this work, we revisit STK and STKR, and provide three sets of novel
results. Our first contribution is elevating STKR to be a principled and
general way of using unlabeled data. Unlabeled data is useful as it provides
additional information about the data distribution ${P_{\mathcal{X}}}$, but
the kernel could be independent of ${P_{\mathcal{X}}}$. STKR implicitly mixes
the information of ${P_{\mathcal{X}}}$ and the kernel in the process of
constructing the STK. We then prove the generality of STKR via an existence
result (Theorem 1): Suppose the target function satisfies a certain unknown
“target smoothness” that preserves the relative smoothness at multiple scales,
then there must exist an STK that describes this target smoothness.

Our second contribution is implementing STKR with general transformations for
the _inductive setting_. Most prior work is limited to the transductive
setting where test samples are known at train time (Zhou et al., 2003; Johnson
& Zhang, 2008), in large part because it is easier to carry out spectral
transformation of the finite-dimensional Gram matrix than the entire kernel
function itself. But for practical use and a comprehensive analysis of STKR,
we need inductive approaches as well. Towards this, Chapelle et al. (2002)
solved an optimization problem for each test point, which is not scalable;
Chapelle et al. (2006, Chapter 11.4) provided a more scalable extension that
“propagates” the labels to unseen test points after transductive learning, but
they still needed to implicitly solve a quadratic optimization program for
each set of test points. These approaches moreover do not come with strong
guarantees. Modern representation learning approaches that use deep neural
networks to represent the STK eigenfunctions inductively do provide scalable
approaches, but no longer have rigorous guarantees. To the best of our
knowledge, this work develops the first inductive STKR implementation that (a)
has closed-form formulas for the predictor, (b) works for very general STKs,
(c) is scalable, and importantly, (d) comes with strong statistical
guarantees. We offer detailed implementations with complexity analysis, and
verify their efficiency with experiments on real tasks in Section 5.

Our third contribution is developing rigorous theory for this general
inductive STKR, and proving nonparametric statistical learning bounds. Suppose
the target function $f^{*}$ is smooth w.r.t. an STK ${K_{s}}$, and there are
$n$ labeled and $m$ unlabeled samples both i.i.d.. We prove estimation and
approximation error bounds for the STKR predictor (in $L^{2}$ norm) when
$s(\lambda)$ is known or completely unknown. By incorporating recent
theoretical progress, three of our four bounds have tightness results.

In a nutshell, this work conceptually establishes STKR as a general and
principled way of learning with labeled and unlabeled data together with a
similarity base kernel; algorithmically we provide scalable implementations
for general inductive STKR, and verify them on real datasets; statistically we
prove statistical guarantees, with technical improvements over prior work.
Limitations and open problems are discussed in Section 6, and more related
work can be found in Appendix A. We also provide a table of notations at the
beginning of the Appendix for the convenience of our readers.

##  2 Deriving STKR from Diffusion Induced Multiscale Smoothness

Let the input space ${\mathcal{X}}$ be a compact Hausdorff space,
${\mathcal{Y}}=\mathbb{R}$ be the label space, and
$P_{{\mathcal{X}}{\mathcal{Y}}}$ be the underlying data distribution over
${\mathcal{X}}\times{\mathcal{Y}}$, whose marginal distribution
${P_{\mathcal{X}}}$ is a Borel measure with support ${\mathcal{X}}$. We will
use the shorthand $dp(x)$ to denote $d{P_{\mathcal{X}}}(x)$. Let
${L^{2}(P_{\mathcal{X}})}$ be the Hilbert space of $L^{2}$ functions w.r.t.
${P_{\mathcal{X}}}$ that satisfy $\int f(x)^{2}dp(x)<+\infty$, with $\langle
f_{1},f_{2}\rangle_{P_{\mathcal{X}}}=\int f_{1}(x)f_{2}(x)dp(x)$ and
$\|f\|_{P_{\mathcal{X}}}=\sqrt{\langle f,f\rangle_{P_{\mathcal{X}}}}$.
$f\in{L^{2}(P_{\mathcal{X}})}$ also implies $f\in L^{1}({P_{\mathcal{X}}})$,
which guarantees that $\mathbb{E}_{X\sim{P_{\mathcal{X}}}}[f(X)]$ exists and
is finite. Let a base kernel $K(x,x^{\prime})$ encode inter-sample similarity
information over ${\mathcal{X}}$. We assume full access to $K$ (i.e. we can
compute $K(x,x^{\prime})$ for all $x,x^{\prime}$), and that $K$ satisfies:

  1. (i)

$K$ is a Mercer kernel, so it has the spectral decomposition:
$K(x,x^{\prime})=\sum_{i=1}^{\infty}\lambda_{i}\psi_{i}(x)\psi_{i}(x^{\prime})$,
where the convergence is absolute and uniform. Here $\lambda_{i},\psi_{i}$ are
the eigenvalues and orthonormal eigenfunctions of the integral operator
$T_{K}:{L^{2}(P_{\mathcal{X}})}\rightarrow{L^{2}(P_{\mathcal{X}})}$ defined as
$(T_{K}f)(x)=\int f(x^{\prime})K(x,x^{\prime})dp(x^{\prime})$, such that
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq 0$, and
$\langle\psi_{i},\psi_{j}\rangle_{P_{\mathcal{X}}}=\delta_{i,j}=\bm{1}_{\\{i=j\\}}$.

  2. (ii)

$K$ is centered: Defined as $T_{K}\bm{1}={\bm{0}}$, where $\bm{1}(x)\equiv 1$
and ${\bm{0}}(x)\equiv 0$. One can center any $K$ by
$\tilde{K}(x_{0},y_{0})=K(x_{0},y_{0})-\int K(x,y_{0})dp(x)-\int
K(x_{0},y)dp(y)+\iint K(x,y)dp(x)dp(y)$.

Why assuming centeredness? In this work, we view the smoothness and scale of a
function $f$ as two orthogonal axes, since our smoothness pertains to the
inter-sample similarity. Thus, we view $f_{1}$ and $f_{2}$ as equally smooth
if they differ by a constant a.e.. If $K$ is not centered, then this will not
be true under the RKHS norm (see Section 2.1). In practice centering is not a
necessary step, though often recommended in kernel PCA.

This work investigates the regression function estimation problem in
nonparametric regression, with error measured in $L^{2}$ norm (see Györfi et
al. (2002) for an introduction of regression problems):

Problem. Let $f^{*}(x):=\int
y\;dP_{{\mathcal{X}}{\mathcal{Y}}}(y|x)\in{L^{2}(P_{\mathcal{X}})}$ be the
target regression function. Given $n$ labeled samples
$(x_{1},y_{1}),\cdots,(x_{n},y_{n})\overset{\textit{i.i.d.}}{\sim}P_{{\mathcal{X}}{\mathcal{Y}}}$,
$m$ unlabeled samples
$x_{n+1},\cdots,x_{n+m}\overset{\textit{i.i.d.}}{\sim}{P_{\mathcal{X}}}$, and
access to $K(x,x^{\prime})$ for any $x,x^{\prime}\in{\mathcal{X}}$, find a
predictor $\hat{f}\in{L^{2}(P_{\mathcal{X}})}$ with low prediction error:
$\textnormal{err}(\hat{f},f^{*}):=\mathbb{E}_{X\sim{P_{\mathcal{X}}}}{\left[{\left(\hat{f}(X)-f^{*}(X)\right)}^{2}\right]}={\left\|\hat{f}-f^{*}\right\|}_{P_{\mathcal{X}}}^{2}.$

One can also think of $f^{*}$ as the target function, and
$y=f^{*}(x)+\epsilon$, where $\epsilon$ is random noise with zero mean. Let
$\\{\lambda_{i}:i\in{\mathbb{I}}\\}$ be the set of non-zero eigenvalues of
$T_{K}$, then define
$K^{p}(x,x^{\prime}):=\sum_{i\in{\mathbb{I}}}\lambda_{i}^{p}\psi_{i}(x)\psi_{i}(x^{\prime})$
for all $p\in\mathbb{R}$, which corresponds to an STK with
$s(\lambda)=\lambda^{p}$. The set $\\{K^{p}\\}$ delineates a _diffusion
process_ w.r.t. $K$, because $K^{p+1}(x,x^{\prime})=\int
K^{p}(x,x_{0})K(x^{\prime},x_{0})dp(x_{0})$, so that $K^{p+1}$ captures
similarity with one additional hop to $K^{p}$. For continuous diffusion, $p$
can be real-valued. Then, the reproducing kernel Hilbert space (RKHS)
associated with $K^{p}$ for any $p\geq 1$ is:

${\mathcal{H}}_{K^{p}}:={\left\\{f=\sum_{i\in{\mathbb{I}}}u_{i}\psi_{i}\;\middle|\;\sum_{i}\frac{u_{i}^{2}}{\lambda_{i}^{p}}<\infty\right\\}},\quad{\left\langle\sum_{i}u_{i}\psi_{i},\sum_{i}v_{i}\psi_{i}\right\rangle}_{{\mathcal{H}}_{K^{p}}}=\sum_{i}\frac{u_{i}v_{i}}{\lambda_{i}^{p}},\vspace{-.1
in}$ (1)

and $\|f\|_{{\mathcal{H}}_{K^{p}}}^{2}=\langle
f,f\rangle_{{\mathcal{H}}_{K^{p}}}$. $K^{p}$ is the reproducing kernel of
${\mathcal{H}}_{K^{p}}$, as one can verify for all $f\in{\mathcal{H}}_{K^{p}}$
and $x$ that $\langle f,K^{p}_{x}\rangle_{{\mathcal{H}}_{K^{p}}}=f(x)$, for
$K^{p}_{x}(z):=K^{p}(x,z)$. ${\mathcal{H}}_{K^{1}}$ is also denoted by
${{\mathcal{H}}_{K}}$. ${\mathcal{H}}_{K^{p}}$ are called power spaces
(Fischer & Steinwart, 2020) or interpolation Sobolev spaces (Jin et al.,
2023). Kernel ridge regression (KRR) is a classical least-squares algorithm.
KRR with $K$ is given by:

$\hat{f}\in\operatorname*{arg\,min}_{f\in{{\mathcal{H}}_{K}}}{\left\\{\frac{1}{n}\sum_{i=1}^{n}(f(x_{i})-y_{i})^{2}+\beta_{n}\|f\|_{{\mathcal{H}}_{K}}^{2}\right\\}}\vspace{-.08
in}$

for some $\beta_{n}>0$. Although KRR is very widely used, the problem is that
it does not leverage the unlabeled data, because the optimal solution of KRR
only depends on $x_{1},\cdots,x_{n}$ but not $x_{n+1},\cdots,x_{n+m}$, as is
explicitly shown by the Representer Theorem (Schölkopf & Smola, 2002, Theorem
4.2): All minimizers of KRR admit the form
$\hat{f}^{*}(x)=\sum_{j=1}^{n}\alpha^{*}_{j}K(x,x_{j})$, where

${\bm{\alpha}}^{*}\in\operatorname*{arg\,inf}_{{\bm{\alpha}}\in\mathbb{R}^{n}}{\left\\{\frac{1}{n}\sum_{i=1}^{n}{\left[\sum_{j=1}^{n}\alpha_{j}K(x_{i},x_{j})-y_{i}\right]}^{2}+\beta_{n}\sum_{i,j=1}^{n}\alpha_{i}\alpha_{j}K(x_{i},x_{j})\right\\}}.\vspace{-.1
in}$ (2)

$x_{1}$$x_{4}$$x_{2}$$x_{5}$$x_{6}$$x_{3}$ Figure 1: Sample graph.

One consequence is that for KRR, the whole base kernel could be useless.
Consider the graph example on the right, where only the three shaded nodes are
labeled, and $K$ is the adjacency matrix. With KRR, the unlabeled nodes are
useless and can be removed. Then, the graph becomes three isolated nodes, so
it has zero impact on the learned predictor.

###  2.1 Diffusion Induced Multiscale Smoothness

Let us use this graph example to motivate STKR. Unlabeled samples are useful
as they offer more information about the marginal distribution
${P_{\mathcal{X}}}$. The problem is that we don’t know the connection between
$K$ and ${P_{\mathcal{X}}}$. So while KRR can leverage $K$, it does not
necessarily exploit more information about ${P_{\mathcal{X}}}$ than supervised
learning over the $n$ labeled samples, which is why the unlabeled samples are
useless in our graph example. To address this, the seminal work Belkin et al.
(2006) proposed this elegant idea of explicitly including another regularizer
$\|f\|_{{\mathcal{I}}}^{2}$ that reflects the intrinsic structure of
${P_{\mathcal{X}}}$. For instance, $\|f\|_{{\mathcal{I}}}^{2}$ can be defined
with the Laplace-Beltrami operator in manifold learning, or the graph
Laplacian for graphs. In comparison, STKR also exploits ${P_{\mathcal{X}}}$,
but in an implicit way—the construction of the STK mixes $K$ with
${P_{\mathcal{X}}}$. To see this: In our graph example, suppose we were to use
the STK $K^{2}$, i.e. a two-step random walk. Then, (a) the graph would be
useful again because the three labeled nodes were connected in $K^{2}$, and
(b) we mixed $K$ with ${P_{\mathcal{X}}}$ since $K^{2}$ is essentially an
integral of $K\times K$ over ${P_{\mathcal{X}}}$. The main takeaway from the
above analysis is: With STKR, we impose another kind of smoothness we call the
target smoothness, and it mixes the information of $K$ with the information of
${P_{\mathcal{X}}}$. In the rest of this section, we formally characterize
this target smoothness.

We start with formally defining “smoothness”. Suppose the inter-sample
similarity is characterized by a metric $d(x,x^{\prime})$ over the input space
${\mathcal{X}}$, then one can naturally measure the smoothness of $f$ by its
Lipschitz constant $\text{Lip}_{d}(f)=\sup_{x,x^{\prime}\in{\mathcal{X}},x\neq
x^{\prime}}\frac{|f(x)-f(x^{\prime})|}{d(x,x^{\prime})}$. So it suffices to
specify $d(x,x^{\prime})$. If ${\mathcal{X}}$ is an Euclidean space, then one
can choose $d$ to be the Euclidean distance, which is used in lots of prior
work (Tenenbaum et al., 2000; Belkin & Niyogi, 2003). The caveat is that the
Euclidean distance is not guaranteed to be correlated with similarity, and
${\mathcal{X}}$ is not necessarily Euclidean in the first place.

Instead, one can use $K$ to define the metric, which should align better with
inter-sample similarity by the definition of $K$. And if one further assumes
transitivity of similarity, i.e. $(a,b)$ and $(b,c)$ being similar implies
that $(a,c)$ are similar, then $K^{p}$ also aligns with similarity. The kernel
metric of $K^{p}$ is given by
$d_{K^{p}}(x,x^{\prime}):=\|K^{p}_{x}-K^{p}_{x^{\prime}}\|_{{\mathcal{H}}_{K^{p}}}=\sum_{i}\lambda_{i}^{p}(\psi_{i}(x)-\psi_{i}(x^{\prime}))^{2}$,
which is equivalent to the diffusion distance defined in Coifman & Lafon
(2006), and $p$ can be real-valued. Thus, kernel diffusion $\\{K^{p}\\}$
induces a multiscale metric geometry over ${\mathcal{X}}$, where a larger $p$
induces a weaker metric. Here “weaker” means $d_{K^{p}}=O(d_{K^{q}})$ if
$p>q$. One can also think of $\\{K^{p}\\}_{p\geq 1}$ as forming a chain of
smooth function classes:
${L^{2}(P_{\mathcal{X}})}\supset{\mathcal{H}}_{K^{1}}\supset{\mathcal{H}}_{K^{2}}\supset\cdots$,
and for continuous diffusion we can also have sets like
${\mathcal{H}}_{K^{1.5}}$. A larger $p$ imposes a stronger constraint since
${\mathcal{H}}_{K^{p}}$ is smaller.

Now we show: $\|f\|_{{\mathcal{H}}_{K^{p}}}$ is equal to its Lipschitz
constant. But this is not true for $\text{Lip}_{d}(f)$, which is not very
tractable under the topological structure of ${\mathcal{X}}$. Thus, we
consider the space of finite signed measures over ${\mathcal{X}}$, denoted by
$\bar{{\mathcal{X}}}$. For any function $f$ on ${\mathcal{X}}$, define its
mean $\bar{f}$ as a linear functional over $\bar{{\mathcal{X}}}$, such that
$\bar{f}(\mu)=\int_{{\mathcal{X}}}f(x)\mu(x)$. Then, define
$d_{K^{p}}(\mu,\nu):=\|\int K_{x}^{p}\mu(x)-\int
K_{x}^{p}\nu(x)\|_{{\mathcal{H}}_{K^{p}}}$ for
$\mu,\nu\in\bar{{\mathcal{X}}}$, and
$\overline{\text{Lip}}_{d_{K^{p}}}(f):=\sup_{\mu,\nu\in\overline{{\mathcal{X}}},\mu\neq\nu}\frac{|\bar{f}(\mu)-\bar{f}(\nu)|}{d_{K^{p}}(\mu,\nu)}$.
In other words, $f$ is smooth if its mean w.r.t. $\mu$ does not change too
much when the measure $\mu$ over ${\mathcal{X}}$ changes by a little bit.
Then, we have:

######  Proposition 1 (Proofs in Appendix B).

This $\overline{\textnormal{Lip}}_{d_{K^{p}}}(f)$ satisfies:
$\overline{\textnormal{Lip}}_{d_{K^{p}}}(f)=\|f\|_{{\mathcal{H}}_{K^{p}}}$,
$\forall f\in{\mathcal{H}}_{K^{p}}$.

We define
$r_{K^{p}}(f):=\|f-\mathbb{E}_{{P_{\mathcal{X}}}}[f]\|_{{P_{\mathcal{X}}}}^{2}/\;\overline{\text{Lip}}_{d_{K^{p}}}(f)^{2}=\|f-\mathbb{E}_{{P_{\mathcal{X}}}}[f]\|_{{P_{\mathcal{X}}}}^{2}/\|f\|_{{\mathcal{H}}_{K^{p}}}^{2}$,
and use it to measure the smoothness of any $f\in{L^{2}(P_{\mathcal{X}})}$ at
scale $p\geq 1$. Here $\|f\|_{{\mathcal{H}}_{K^{p}}}$ is extended to all
$f\in{L^{2}(P_{\mathcal{X}})}$: If $\exists f_{p}\in{\mathcal{H}}_{K^{p}}$
such that $f-\mathbb{E}_{P_{\mathcal{X}}}[f]=f_{p}$
(${P_{\mathcal{X}}}$-a.e.), then
$\|f\|_{{\mathcal{H}}_{K^{p}}}:=\|f_{p}\|_{{\mathcal{H}}_{K^{p}}}$; If there
is no such $f_{p}$, then $\|f\|_{{\mathcal{H}}_{K^{p}}}:=+\infty$. Since $K$
is centered, for any $f_{1}$ and $f_{2}$ that differ by a constant
${P_{\mathcal{X}}}$-a.e., there is $r_{K^{p}}(f_{1})=r_{K^{p}}(f_{2})$. This
would not be true without the centeredness assumption. We define
$r_{K^{p}}(f)$ as a ratio to make it scale-invariant, i.e. $f$ and $2f$ are
equally smooth, for the same purpose of decoupling smoothness and scale. And
in Section B.2, we will discuss the connection between $r_{K^{p}}(f)$ and
discriminant analysis, as well as the Poincaré constant.

Now we characterize “target smoothness”, an unknown property that the target
$f^{*}$ possesses. We assume that it has the same form
$r_{t}(f):=\|f-\mathbb{E}_{{P_{\mathcal{X}}}}[f]\|_{{P_{\mathcal{X}}}}^{2}/\overline{\text{Lip}}_{d_{t}}(f)^{2}$,
for some metric $d_{t}$ over $\bar{{\mathcal{X}}}$. Then, we assume all
functions with “target smoothness” belong to a Hilbert space
${\mathcal{H}}_{t}$, and $x,x^{\prime}$ are similar if all functions in
${\mathcal{H}}_{t}$ give them similar predictions, i.e.
$d_{t}(\mu,\nu)=\sup_{\|f\|_{{\mathcal{H}}_{t}}=1}|\bar{f}(\mu)-\bar{f}(\nu)|$.
We also assume that target smoothness implies base smoothness, i.e.
${\mathcal{H}}_{t}\subset{{\mathcal{H}}_{K}}$ (this is relaxable).

###  2.2 Target Smoothness can Always be Obtained from STK: Sufficient
Condition

Let $r_{t}(f)$ be defined as above. Our first theorem gives the following
sufficient condition: If the target smoothness preserves relative multiscale
smoothness, then it must be attainable with an STK.

######  Theorem 1.

If $r_{t}(f)$ preserves relative smoothness: “$\forall
f_{1},f_{2}\in{L^{2}(P_{\mathcal{X}})}$, if $r_{K^{p}}(f_{1})\geq
r_{K^{p}}(f_{2})$ for all $p\geq 1$, then $r_{t}(f_{1})\geq r_{t}(f_{2})$”,
and ${\mathcal{H}}_{t}\subset{{\mathcal{H}}_{K}}$, then
$r_{t}(f)=\|f-\mathbb{E}_{{P_{\mathcal{X}}}}[f]\|_{{P_{\mathcal{X}}}}^{2}/\|f\|_{{\mathcal{H}}_{t}}^{2}$,
and ${\mathcal{H}}_{t}$ must be an RKHS, whose reproducing kernel is an STK
that admits the following form:
${K_{s}}(x,x^{\prime})=\sum\nolimits_{i:\lambda_{i}>0}s(\lambda_{i})\psi_{i}(x)\psi_{i}(x^{\prime}),\vspace{-.06
in}$ (3) for a transformation function $s:[0,+\infty)\rightarrow[0,+\infty)$
that is: (i) monotonically non-decreasing, (ii) $s(\lambda)\leq M\lambda$ for
some constant $M>0$, (iii) continuous on $[0,+\infty)$, and (iv) $C^{\infty}$
on $(0,+\infty)$.

The proof is done by sequentially showing that (i) ${\mathcal{H}}_{t}$ is an
RKHS; (ii) Its reproducing kernel is
${K_{s}}(x,x^{\prime}):=\sum_{i}s_{i}\psi_{i}(x)\psi_{i}(x^{\prime})$, with
$s_{1}\geq s_{2}\geq\cdots\geq 0$; (iii) $s_{i}=O(\lambda_{i})$; (iv) There
exists such a function $s(\lambda)$ that interpolates all $s_{i}$. From now
on, we will use ${{\mathcal{H}}_{{K_{s}}}}$ to denote ${\mathcal{H}}_{t}$.
This theorem implies that $s(\lambda)$ makes the eigenvalues decay faster than
the base kernel, but it does not imply that ${K_{s}}$ is a linear combination
of $\\{K^{p}\\}_{p\geq 1}$. This result naturally leads to KRR with
$\|f\|_{{{\mathcal{H}}_{{K_{s}}}}}^{2}=\|f\|_{{\mathcal{H}}_{t}}^{2}$:

$\tilde{f}\in\operatorname*{arg\,min}_{f-\mathbb{E}_{P_{\mathcal{X}}}[f]\in{{\mathcal{H}}_{{K_{s}}}}}{\left\\{\frac{1}{n}\sum_{i=1}^{n}{\left(f(x_{i})-y_{i}\right)}^{2}+\beta_{n}{\left\|f-\mathbb{E}_{X\sim{P_{\mathcal{X}}}}[f(X)]\right\|}_{{\mathcal{H}}_{{K_{s}}}}^{2}\right\\}},$
(4)

which we term spectrally transformed kernel regression (STKR). One could also
relax the assumption ${\mathcal{H}}_{t}\subset{\mathcal{H}}_{K}$ by
considering ${\mathcal{H}}_{K^{p}}$ for $p\geq p_{0}$ where $p_{0}<1$.
Assuming that ${\mathcal{H}}_{K^{p_{0}}}$ is still an RKHS and
${\mathcal{H}}_{t}\subset{\mathcal{H}}_{K^{p_{0}}}$, one can prove the same
result as Theorem 1, with (ii) changed to $s(\lambda)\leq M\lambda^{p_{0}}$.

Now we develop theory for STKR, and show how it exploits the unlabeled data.
Here is a road map:

  1. (a)

We first study the easier transform-aware setting in Section 3, where a good
$s(\lambda)$ is given by an oracle. But even though $s(\lambda)$ is known,
${K_{s}}$ is inaccessible as one cannot obtain $\psi_{i}$ with finite samples.
Unlabeled data becomes useful when one constructs a kernel ${\hat{K}_{s}}$ to
approximate ${K_{s}}$.

  2. (b)

In reality, such an oracle need not exist. So in Section 4, we study the
harder transform-agnostic setting where we have no knowledge of $s(\lambda)$
apart from Theorem 1. We examine two methods:

    1. (i)

STKR with inverse Laplacian (Example 1), which is popular in semi-supervised
learning and empirically works well on lots of tasks though the real $s$ might
not be inverse Laplacian.

    2. (ii)

STKR with kernel PCA, which extracts the top-$d$ eigenfunctions to be an
encoder and then learns a linear probe atop. This is used in many manifold and
representation learning methods. Here, unlabeled data is useful when
approximating $\psi_{1},\cdots,\psi_{d}$ in kernel PCA.

Notation: For any kernel $K$, we use
${\bm{G}}_{K}\in\mathbb{R}^{(n+m)\times(n+m)},{\bm{G}}_{K,n}\in\mathbb{R}^{n\times
n},{\bm{G}}_{K,m}\in\mathbb{R}^{m\times m}$ to respectively denote its Gram
matrix on all, labeled and unlabeled samples, i.e.
${\bm{G}}_{K}[i,j]=K(x_{i},x_{j})$.

##  3 Transform-aware: STKR with Known Polynomial Transform

Let the scale of $f^{*}$ be measured by $B$. This section supposes that
$s(\lambda)$ is known, and the following:

######  Assumption 1.

$s(\lambda)=\sum_{p=1}^{\infty}\pi_{p}\lambda^{p}$ is a polynomial, with
$\pi_{p}\geq 0$.

######  Assumption 2.

There exists a constant $\kappa>0$ such that $K(x,x)\leq\kappa^{2}$ for
${P_{\mathcal{X}}}$-almost all $x$.

######  Assumption 3.

$\mathbb{E}_{P_{\mathcal{X}}}[f^{*}]=0$, and there exist constants
$B,\epsilon>0$ such that: $\|f^{*}\|_{P_{\mathcal{X}}}\leq B$,
$f^{*}\in{{\mathcal{H}}_{{K_{s}}}}$, and
$\|f^{*}\|_{{\mathcal{H}}_{{K_{s}}}}^{2}\leq\epsilon\|f^{*}\|_{P_{\mathcal{X}}}^{2}$
(i.e. $r_{t}(f^{*})\geq\epsilon^{-1}$). (cf. the isometry property in Zhai et
al. (2024))

######  Assumption 4.

$P_{{\mathcal{X}}{\mathcal{Y}}}$ satisfies the moment condition for
$\sigma,L>0$: $\mathbb{E}[|y-f^{*}(x)|^{r}]\leq\frac{1}{2}r!\sigma^{2}L^{r-2}$
for all $r\geq 2$ and ${P_{\mathcal{X}}}$-almost all $x$. (e.g. For
$y-f^{*}(x)\sim{\mathcal{N}}(0,\sigma^{2})$, this holds with $L=\sigma$.)

Assumption 1 is a natural condition for discrete diffusion, such as a multi-
step random walk on a graph, and $p$ starts from $1$ because $s(0)=0$. The
assumption $\mathbb{E}_{P_{\mathcal{X}}}[f^{*}]=0$ in Assumption 3 is solely
for the simplicity of the results, without which one can prove the same but
more verbose bounds. The moment condition Assumption 4 is essentially used to
control the size of the label noise.

➢ Method: We implement inductive STKR by constructing a computable kernel
${\hat{K}_{s}}(x,x^{\prime})$ to approximate the inaccessible ${K_{s}}$. For
example, if ${K_{s}}(x,x^{\prime})=K^{2}(x,x^{\prime})=\int
K(x,x_{0})K(x^{\prime},x_{0})dp(x_{0})$, then a Monte-Carlo approximation can
be done by replacing the integral over $x_{0}$ with an average over
$x_{1},\cdots,x_{n+m}$. Computing this average leverages the unlabeled data.
Specifically, we define:

$\displaystyle\hat{f}\in\operatorname*{arg\,min}_{f\in{{\mathcal{H}}_{{\hat{K}_{s}}}}}{\left\\{\frac{1}{n}\sum_{i=1}^{n}{\left(f(x_{i})-y_{i}\right)}^{2}+\beta_{n}\|f\|_{{\mathcal{H}}_{{\hat{K}_{s}}}}^{2}\right\\}},$
(5) where
$\displaystyle{\hat{K}_{s}}(x,x^{\prime}):=\sum_{p=1}^{\infty}\pi_{p}\hat{K}^{p}(x,x^{\prime});\;\hat{K}^{1}=K;\;\forall
p\geq
2,\hat{K}^{p}(x,x^{\prime})=\frac{{\bm{v}}_{K}(x)^{\top}{\bm{G}}_{K}^{p-2}{\bm{v}}_{K}(x^{\prime})}{(n+m)^{p-1}}.$

Here, ${\bm{v}}_{K}(x)\in\mathbb{R}^{n+m}$ such that
${\bm{v}}_{K}(x)[i]=K(x,x_{i})$, $i\in[n+m]$. One can compute
${\hat{K}_{s}}(x,x^{\prime})$ for any $x,x^{\prime}$ with full access to
$K(x,x^{\prime})$. Let ${\bm{y}}=[y_{1},\cdots,y_{n}]\in\mathbb{R}^{n}$, and
${\bm{v}}_{{K_{s}},n}(x)\in\mathbb{R}^{n}$ be defined as
${\bm{v}}_{{K_{s}},n}(x)[i]={K_{s}}(x,x_{i})$ for $i\in[n]$. The following
closed-form solutions can be derived from the Representer Theorem. While they
are not necessarily unique, we will use them throughout this work:

$\displaystyle\tilde{f}(x)={\bm{v}}_{{K_{s}},n}(x)^{\top}\tilde{{\bm{\alpha}}},\qquad\tilde{{\bm{\alpha}}}=({\bm{G}}_{{K_{s}},n}+n\beta_{n}{\bm{I}}_{n})^{-1}{\bm{y}};$
(6)
$\displaystyle\hat{f}(x)={\bm{v}}_{{\hat{K}_{s}},n}(x)^{\top}\hat{{\bm{\alpha}}},\qquad\hat{{\bm{\alpha}}}=({\bm{G}}_{{\hat{K}_{s}},n}+n\beta_{n}{\bm{I}}_{n})^{-1}{\bm{y}}.$
(7)

➢ Results overview: Now, for all $s$ and $f^{*}$ that satisfy the above
assumptions, we bound the prediction error
$\|\hat{f}-f^{*}\|_{P_{\mathcal{X}}}^{2}$. The bound has two parts and here is
a synopsis: In Part 1 (Theorem 2), we assume access to ${K_{s}}$, and use the
general results in Fischer & Steinwart (2020) to bound the estimation error
entailed by KRR with finite samples and label noise; In Part 2 (Theorem 3), we
bound the approximation error entailed by using ${\hat{K}_{s}}$ to approximate
the inaccessible ${K_{s}}$.

######  Theorem 2.

Let $M$ be given by Theorem 1. If eigenvalues of ${K_{s}}$ decay by order
$p^{-1}$ for $p\in(0,1]$, i.e. $s(\lambda_{i})=O(i^{-\frac{1}{p}})$ for all
$i$, then under Assumptions 2 and 4, for a sequence of
${\left\\{\beta_{n}\right\\}}_{n\geq 1}$ with
$\beta_{n}=\Theta(n^{-\frac{1}{1+p}})$, there is a constant $c_{0}>0$
independent of $n\geq 1$ and $\tau\geq\kappa^{-1}M^{-\frac{1}{2}}$ such that
${\left\|\tilde{f}-f^{*}\right\|}_{P_{\mathcal{X}}}^{2}\leq
c_{0}\tau^{2}\kappa^{2}M{\left[{\left(\epsilon
B^{2}+\sigma^{2}\right)}n^{-\frac{1}{1+p}}+\max{\left\\{L^{2},\kappa^{2}M\epsilon
B^{2}\right\\}}n^{-\frac{1+2p}{1+p}}\right]}\vspace{-.08 in}$ holds for all
$f^{*}$ satisfying Assumption 3 and sufficiently large $n$ with probability at
least $1-4e^{-\tau}$.

######  Remark.

The $O(n^{-\frac{1}{1+p}})$ learning rate is minimax optimal as shown in
Fischer & Steinwart (2020), i.e. one can construct an example where the
learning rate is at most $\Omega(n^{-\frac{1}{1+p}})$. And under Assumption 2,
one can always choose $p=1$ since $i\cdot
s(\lambda_{i})\leq\sum_{j=1}^{i}s(\lambda_{j})\leq
M\sum\lambda_{j}=M\operatorname{Tr}(T_{K})\leq M\kappa^{2}$. So one
statistical benefit of using an appropriate $s$ is to make the eigenvalues
decay faster (i.e. make $p$ smaller). Also note that the random noise should
scale with $f^{*}$, which means that $\sigma,L=\Theta(B)$.

######  Theorem 3.

Let $\hat{\lambda}_{1}$ be the largest eigenvalue of
$\frac{{\bm{G}}_{K}}{n+m}$, and denote
$\lambda_{\max}:=\max{\left\\{\lambda_{1},\hat{\lambda}_{1}\right\\}}$. Then,
under Assumptions 1 and 2, for any $\delta>0$, it holds with probability at
least $1-\delta$ that:
${\left\|\hat{f}-\tilde{f}\right\|}_{P_{\mathcal{X}}}^{2}\leq
8s(\lambda_{\max})\left.\nabla_{\lambda}{\left(\frac{s(\lambda)}{\lambda}\right)}\right|_{\lambda=\lambda_{\max}}\frac{\beta_{n}^{-2}\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}\frac{\|{\bm{y}}\|_{2}^{2}}{n}.$

######  Remark.

The key to prove this is to first prove a uniform bound for
$|{\hat{K}_{s}}(x,x_{j})-{K_{s}}(x,x_{j})|$ over all $x$ and $j$. With
Assumptions 3 and 4, an $O(B^{2}+\sigma^{2}+L^{2})$ bound for
$\frac{\|{\bm{y}}\|_{2}^{2}}{n}$ can be easily obtained. If
$\beta_{n}=\Theta(n^{-\frac{1}{1+p}})$ as in Theorem 2, then with
$m=\omega(n^{\frac{4}{1+p}})$ this bound vanishes, so more unlabeled samples
than labeled ones are needed. Moreover, $\hat{\lambda}_{1}$ is known to be
close to $\lambda_{1}$ when $n+m$ is large:

######  Lemma 2.

(Shawe-Taylor et al., 2005, Theorem 2) For any $\delta>0$, with probability at
least $1-\delta$,

$\hat{\lambda}_{1}\leq\lambda_{1}+\frac{\kappa^{2}}{\sqrt{n+m}}{\left[2\sqrt{2}+\sqrt{19\log\frac{2(n+m+1)}{\delta}}\right]}.$

➢ Implementation: STKR amounts to solving
${\bm{A}}\hat{{\bm{\alpha}}}={\bm{y}}$ for
${\bm{A}}={\bm{G}}_{{\hat{K}_{s}},n}+n\beta_{n}{\bm{I}}_{n}$ by Eqn. 7. There
are two approaches: (i) Directly computing ${\bm{A}}$ (Algorithm 3 in Appendix
C) can be slow due to costly matrix multiplication; (ii) Iterative methods are
faster by only performing matrix-vector multiplication. Algorithm 1 solves
${\bm{A}}\hat{{\bm{\alpha}}}={\bm{y}}$ via Richardson iteration. We name it
STKR-Prop as it is very similar to label propagation (Label-Prop) (Zhou et
al., 2003). If $s(\lambda)=\sum_{p=1}^{q}\pi_{p}\lambda^{p}$ and $q<\infty$,
and computing $K(x,x^{\prime})$ for any $x,x^{\prime}$ takes $O(1)$ time, then
Algorithm 1 has a time complexity of
$O(q(n+m)^{2}\beta_{n}^{-1}s(\lambda)\log\frac{1}{\epsilon})$ for achieving
error less than $\epsilon$, where $\lambda$ is a known upper bound of
$\lambda_{1}$ (see derivation in Appendix C). Besides, STKR-Prop is much
faster when $K$ is sparse. In particular, for a graph with $|E|$ edges, STKR-
Prop runs in $\tilde{O}(q|E|\beta_{n}^{-1})$ time, which is as fast as Label-
Prop.

At inference time, one can store ${\bm{v}}$ computed in line 4 of Algorithm 1
in the memory. Then for any $x$, there is
$\hat{f}(x)=\sum_{i=1}^{n+m}K(x_{i},x)v_{i}+\pi_{1}\sum_{j=1}^{n}K(x_{j},x)\hat{\alpha}_{j}$,
which takes $O(n+m)$ time to compute. This is much faster than Chapelle et al.
(2002) who solved an optimization problem for each new $x$.

For some other transformations, including the inverse Laplacian we are about
to discuss, $s$ is complex, but
$s^{-1}(\lambda)=\sum_{p=0}^{q-1}\xi_{p}\lambda^{p-r}$ is simple. For this
type of $s(\lambda)$, Algorithm 1 is infeasible, but there is a viable method
in Algorithm 2: It finds ${\bm{\theta}}\in\mathbb{R}^{n+m}$ such that
${\bm{Q}}{\bm{\theta}}=[\hat{{\bm{\alpha}}},{\bm{0}}_{m}]^{\top}$ and
${\bm{M}}{\bm{\theta}}=\tilde{{\bm{y}}}$, where
${\bm{Q}}:=\sum_{p=0}^{q-1}\xi_{p}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p}$,
${\bm{M}}:=(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}+n\beta_{n}{\bm{Q}}$,
$\tilde{{\bm{I}}}_{n}:={\textnormal{diag}}\\{1,\cdots,1,0,\cdots,0\\}$ with
$n$ ones and $m$ zeros, and
$\tilde{{\bm{y}}}:=[{\bm{y}},{\bm{0}}_{m}]^{\top}$. In Appendix C we will
derive these formulas step by step, and prove its time complexity to be
$\tilde{O}(\max\\{q,r\\}(n+m)^{2}\beta_{n}^{-1})$. And at inference time, one
can compute
$\hat{f}(x)={\bm{v}}_{K}(x)^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r-1}{\bm{\theta}}$
in $O(n+m)$ time for any $x$ by storing
${\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r-1}{\bm{\theta}}$ in the memory,
where ${\bm{v}}_{K}$ is defined as in Eqn. 5. Once again, for a graph with
$|E|$ edges, STKR-Prop has a time complexity of
$\tilde{O}(\max\\{q,r\\}|E|\beta_{n}^{-1})$, which is as fast as Label-Prop.
Finally, here we showed the existence of a good solver (Richardson), but
practitioners could surely use other linear solvers.

Algorithm 1 STKR-Prop for simple $s^{\phantom{0}}$

1:${\bm{G}}_{K}$, $s(\lambda)$, $\beta_{n}$, ${\bm{y}}$, $\gamma$, $\epsilon$

2:Initialize: $\hat{{\bm{\alpha}}}\leftarrow{\bm{0}}\in\mathbb{R}^{n}$

3:while True do

4:# Compute
${\bm{u}}=({\bm{G}}_{{\hat{K}_{s}},n}+n\beta_{n}{\bm{I}}_{n})\hat{{\bm{\alpha}}}$

5:
$\tilde{{\bm{\alpha}}}\leftarrow\frac{1}{n+m}{\bm{G}}_{K,n+m,n}\hat{{\bm{\alpha}}}$,
${\bm{v}}\leftarrow{\bm{0}}\in\mathbb{R}^{n+m}$

6: for $p=q,\cdots,2$ do
${\bm{v}}\leftarrow\frac{{\bm{G}}_{K}{\bm{v}}}{n+m}+\pi_{p}\tilde{{\bm{\alpha}}}$

7:
${\bm{u}}\leftarrow{\bm{G}}_{K,n+m,n}^{\top}{\bm{v}}+\pi_{1}{\bm{G}}_{K,n}\hat{{\bm{\alpha}}}+n\beta_{n}\hat{{\bm{\alpha}}}$

8: if $\|{\bm{u}}-{\bm{y}}\|_{2}<\epsilon\|{\bm{y}}\|_{2}$ then return
$\hat{{\bm{\alpha}}}$

9:
$\hat{{\bm{\alpha}}}\leftarrow\hat{{\bm{\alpha}}}-\gamma({\bm{u}}-{\bm{y}})$

Algorithm 2 STKR-Prop for simple $s^{-1}$

1:${\bm{G}}_{K}$, $s^{-1}(\lambda)$, $\beta_{n}$, ${\bm{y}}$, $\gamma$,
$\epsilon$

2:Initialize: ${\bm{\theta}}\leftarrow{\bm{0}}\in\mathbb{R}^{n+m}$,
$\tilde{{\bm{y}}}\leftarrow[{\bm{y}},{\bm{0}}_{m}]^{\top}$

3:while True do

4:# Compute ${\bm{u}}={\bm{M}}{\bm{\theta}}$

5: ${\bm{v}}\leftarrow{\bm{0}}\in\mathbb{R}^{n+m}$

6: for $p=q-1,\cdots,0$ do
${\bm{v}}\leftarrow\frac{{\bm{G}}_{K}{\bm{v}}}{n+m}+\xi_{p}{\bm{\theta}}$

7:
${\bm{u}}\leftarrow{\left[{\left(\frac{{\bm{G}}_{K}^{r}}{(n+m)^{r-1}}{\bm{\theta}}\right)}[1:n],{\bm{0}}_{m}\right]}^{\top}+n\beta_{n}{\bm{v}}$

8: ${\bm{a}}\leftarrow{\bm{u}}-\tilde{{\bm{y}}}$,
${\bm{\theta}}\leftarrow{\bm{\theta}}-\gamma{\bm{a}}$

9: if $\|{\bm{a}}\|_{2}<\epsilon\|{\bm{y}}\|_{2}$ then return ${\bm{\theta}}$

##  4 Transform-agnostic: Inverse Laplacian and Kernel PCA

We have derived learning guarantees for general inductive STKR when $s$ is
known. This is useful, but in reality, it is unreasonable to presume that such
an oracle $s$ will be given. What should one do if one has zero knowledge of
$s(\lambda)$ but still want to enforce target smoothness? Here we provide two
parallel methods. The first option one can try is STKR with the canonical
inverse Laplacian transformation. Laplacian as a regularizer has been widely
used in various context (Zhou et al., 2003; Johnson & Zhang, 2008; HaoChen et
al., 2021; Zhai et al., 2024). For our problem, we want
$\|f\|_{{\mathcal{H}}_{{K_{s}}}}^{2}=f^{\top}{K_{s}}^{-1}f$ to be the
Laplacian, so the kernel ${K_{s}}$ should be the inverse Laplacian:

######  Example 1 (Inverse Laplacian for the inductive setting).

For $\eta\in(0,\lambda_{1}^{-1})$, define $K_{s}$ such that
$K_{s}^{-1}(x,x^{\prime})=K^{-1}(x,x^{\prime})-\eta K^{0}(x,x^{\prime})$.
$K^{-1}$ and $K^{0}$ are STKs with $s(\lambda)=\lambda^{-1}$ and
$s(\lambda)=\lambda^{0}$. Then, $s^{-1}(\lambda)=\lambda^{-1}-\eta>0$ for
$\lambda\in(0,\lambda_{1}]$ ($s^{-1}$ is the reciprocal, not inverse),
$s(\lambda)=\frac{\lambda}{1-\eta\lambda}=\sum_{p=1}^{\infty}\eta^{p-1}\lambda^{p}$,
and
$\|f\|_{{\mathcal{H}}_{{K_{s}}}}^{2}=\|f\|_{{\mathcal{H}}_{K}}^{2}-\eta\|f\|_{P_{\mathcal{X}}}^{2}$.
Classical Laplacian has $\eta=1$ and $\lambda_{1}<1$. For the connection
between transductive and inductive versions of Laplacian, see Section B.3.

This canonical transformation empirically works well on lots of tasks, and
also have this guarantee:

######  Proposition 3.

Let $s$ be the inverse Laplacian (Example 1), and $s^{*}$ be an arbitrary
oracle satisfying Theorem 1. Suppose $f^{*}$ satisfies Assumption 3 w.r.t.
$s^{*}$, but STKR (Eqn. 7) is performed with $s$. Then, Theorem 3 still holds
for $\tilde{f}$ given by Eqn. 6, and Theorem 2 holds by replacing $\epsilon$
with $M\epsilon$ .

Note that this result does not explain why inverse Laplacian is so good — its
superiority is mainly an empirical observation, so it could still be bad on
some tasks, for which there is the second option. The key observation here is
that since $s$ is proved in Theorem 1 to be monotonic, the order of
$\psi_{1},\psi_{2},\cdots$ must remain unchanged. So if one is asked to choose
$d$ functions to represent the target function, regardless of $s$ the best
choice with the lowest worst-case approximation error must be
$\psi_{1},\cdots,\psi_{d}$:

######  Proposition 4.

Let $s$ be any transformation function that satisfies Theorem 1. Let
${\mathcal{F}}_{s}$ be the set of functions that satisfy Assumption 3 for this
$s$. Then, the following holds for all
$\hat{\Psi}=[\hat{\psi}_{1},\cdots,\hat{\psi}_{d}]$ such that
$\hat{\psi}_{i}\in{L^{2}(P_{\mathcal{X}})}$, as long as
$s(\lambda_{1})\epsilon>1$ and
$\frac{s(\lambda_{d+1})}{s(\lambda_{1})-s(\lambda_{d+1})}{\left[s(\lambda_{1})\epsilon-1\right]}\leq\frac{1}{2}$:

$\max_{f\in{\mathcal{F}}_{s}}\;\min_{{\bm{w}}\in\mathbb{R}^{d}}\;{\left\|{\bm{w}}^{\top}\hat{\Psi}-f\right\|}_{P_{\mathcal{X}}}^{2}\geq\frac{s(\lambda_{d+1})}{s(\lambda_{1})-s(\lambda_{d+1})}{\left[s(\lambda_{1})\epsilon-1\right]}B^{2}.$

To attain equality, it is sufficient for $\hat{\Psi}$ to span
${\textnormal{span}}{\left\\{\psi_{1},\cdots,\psi_{d}\right\\}}$, and
necessary if $s(\lambda_{d})>s(\lambda_{d+1})$.

➢ Method: This result motivates using representation learning with two stages:
A self-supervised pretraining stage that learns a $d$-dimensional encoder
$\hat{\Psi}=[\hat{\psi}_{1},\cdots,\hat{\psi}_{d}]$ with the unlabeled
samples, and a supervised fitting stage that fits a linear probe on
$\hat{\Psi}$ with the labeled samples. The final predictor is
$\hat{f}_{d}(x)=\hat{{\bm{w}}}^{\top}\hat{\Psi}(x)$, for which we do not
include a bias term since $f^{*}$ is assumed to be centered.

For pretraining, the problem boils down to extracting the top-$d$
eigenfunctions of $T_{K}$, for which a classical method is kernel PCA
(Schölkopf & Smola, 2002, Chapter 14). Indeed, kernel PCA has been widely
applied in manifold learning (Belkin & Niyogi, 2003; Bengio et al., 2004), and
more recently self-supervised pretraining (Johnson et al., 2023). Suppose that
${\bm{G}}_{K,m}\in\mathbb{R}^{m\times m}$, the Gram matrix of $K$ over
$x_{n+1},\cdots,x_{n+m}$, is at least rank-$d$. Then, kernel PCA can be
formulated as:

$\displaystyle\hat{\psi}_{i}(x)=\sum_{j=1}^{m}{\bm{v}}_{i}[j]K(x_{n+j},x),$
(8) where
$\displaystyle{\bm{G}}_{K,m}{\bm{v}}_{i}=m\tilde{\lambda}_{i}{\bm{v}}_{i};\;\tilde{\lambda}_{1}\geq\cdots\geq\tilde{\lambda}_{d}>0;\;{\bm{v}}_{i}\in\mathbb{R}^{m};\;\forall
i,j\in[d],{\left\langle{\bm{v}}_{i},{\bm{v}}_{j}\right\rangle}=\frac{\delta_{i,j}}{m\tilde{\lambda}_{i}}.$

For any $i,j\in[d]$, there is
$\langle\hat{\psi}_{i},\hat{\psi}_{j}\rangle_{{\mathcal{H}}_{K}}={\bm{v}}_{i}^{\top}{\bm{G}}_{K,m}{\bm{v}}_{j}=\delta_{i,j}$.
Consider running KRR w.r.t. $K$ over all $f={\bm{w}}^{\top}\hat{\Psi}$. For
$\hat{f}=\hat{{\bm{w}}}^{\top}\hat{\Psi}$, there is
$\|\hat{f}\|_{{\mathcal{H}}_{K}}^{2}=\sum_{i,j=1}^{d}\hat{w}_{i}\hat{w}_{j}\langle\hat{\psi}_{i},\hat{\psi}_{j}\rangle_{{\mathcal{H}}_{K}}=\|\hat{{\bm{w}}}\|_{2}^{2}$.
So it amounts to minimize
$\frac{1}{n}\sum_{i=1}^{n}(\hat{{\bm{w}}}^{\top}\hat{\Psi}(x_{i})-y_{i})^{2}+\beta_{n}\|\hat{{\bm{w}}}\|_{2}^{2}$
as in ridge regression, which is an approximation of STKR with a “truncation
function” $s(\lambda_{i})=\lambda_{i}$ if $i\leq d$, and $0$ otherwise (not a
real function if $\lambda_{d}=\lambda_{d+1}$). Denote
$\hat{\Psi}({\bm{X}}_{n})=[\hat{\Psi}(x_{1}),\cdots,\hat{\Psi}(x_{n})]\in\mathbb{R}^{d\times
n}$. Then, the final predictor is given by:

$\hat{f}_{d}=\hat{{\bm{w}}}^{*\top}\hat{\Psi},\quad\hat{{\bm{w}}}^{*}={\left(\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}+n\beta_{n}{\bm{I}}_{d}\right)}^{-1}\hat{\Psi}({\bm{X}}_{n}){\bm{y}}.\vspace{-.05
in}$ (9)

➢ Results overview: We now bound the prediction error of $\hat{f}_{d}$ for all
$f^{*}$ satisfying Assumption 3, with no extra knowledge about $s(\lambda)$.
The bound also has two parts. In Part 1 (Theorem 4), we bound the estimation
error entailed by KRR over ${\mathcal{H}}_{\hat{\Psi}}$ given by Eqn. 9, where
${\mathcal{H}}_{\hat{\Psi}}$ is the RKHS spanned by
$\hat{\Psi}=[\hat{\psi}_{1},\cdots,\hat{\psi}_{d}]$, which is a subspace of
${{\mathcal{H}}_{K}}$; In Part 2 (Theorem 5), we bound the approximation
error, which is the distance from $f^{*}$ to this subspace $\hat{\Psi}$. Note
that if $\hat{\Psi}$ has insufficient representation capacity (e.g. $d$ is
small), then the approximation error will not vanish. Specifically, let
$\tilde{f}_{d}$ be the projection of $f^{*}$ onto
${\mathcal{H}}_{\hat{\Psi}}$, i.e.
$\tilde{f}_{d}=\tilde{{\bm{w}}}^{\top}\hat{\Psi}$, and
$\langle\tilde{f}_{d},f^{*}-\tilde{f}_{d}\rangle_{{\mathcal{H}}_{K}}=0$. Then,
Part 1 bounds the KRR estimation error with $\tilde{f}_{d}$ being the target
function, and Part 2 bounds $\|f^{*}-\tilde{f}_{d}\|^{2}$.

######  Theorem 4.

Let $M$ be given by Theorem 1. Then, under Assumptions 2 and 4, for Eqn. 9
with a sequence of $\\{\beta_{n}\\}_{n\geq 1}$ with
$\beta_{n}=\Theta(n^{-\frac{1}{1+p}})$ for any $p\in(0,1]$, and any $\delta>0$
and $\tau\geq\kappa^{-1}$, if $n\geq
16\kappa^{4}\tilde{\lambda}_{d}^{-2}{\left(2+\sqrt{2\log\frac{2}{\delta}}\right)}^{2}$,
then there is a constant $c_{0}>0$ independent of $n,\tau$ such that:
$\displaystyle{\left\|\hat{f}_{d}-\tilde{f}_{d}\right\|}_{P_{\mathcal{X}}}^{2}$
$\displaystyle\leq
3{\left({\left\|f^{*}-\tilde{f}_{d}\right\|}_{P_{\mathcal{X}}}^{2}+\frac{\tilde{\lambda}_{d}}{4}{\left\|f^{*}-\tilde{f}_{d}\right\|}_{{\mathcal{H}}_{K}}^{2}\right)}$
$\displaystyle+c_{0}\tau^{2}{\left[{\left(\kappa^{2}M\epsilon
B^{2}+\kappa^{2}\sigma^{2}\right)}n^{-\frac{1}{1+p}}+\kappa^{2}\max{\left\\{L^{2},\kappa^{2}M\epsilon
B^{2}\right\\}}n^{-\frac{1+2p}{1+p}}\right]}$ holds for all $f^{*}$ under
Assumption 3 and sufficiently large $n$ with probability at least
$1-4e^{-\tau}-\delta$.

######  Remark.

This bound has two terms. The first term bounds the gap between ${\bm{y}}$ and
new labels $\tilde{{\bm{y}}}$, where
$\tilde{y}_{i}=y_{i}-f^{*}(x_{i})+\tilde{f}_{d}(x_{i})$. The second term again
comes from the results in Fischer & Steinwart (2020). Comparing the second
term to Theorem 2, we can see that it achieves the fastest minimax optimal
learning rate (i.e. $p$ can be arbitrarily close to 0), as the eigenvalues
decay the fastest with $s$ being the “truncation function”. But the side
effect of this statistical benefit is the first term, as the $d$-dimensional
$\hat{\Psi}$ has limited capacity. The coefficient $3$ can be arbitrarily
close to $1$ with larger $n,c_{0}$.

Our astute readers might ask why $\hat{\Psi}$ is learned only with the
unlabeled samples, while in the last section STKR was done with both labeled
and unlabeled samples. This is because in the supervised fitting stage, the
function class is the subspace spanned by $\hat{\Psi}$. To apply uniform
deviation bounds in Theorem 4, this function class, and therefore
$\hat{\Psi}$, must not see $x_{1},\cdots,x_{n}$ during pretraining. On the
contrary, the function class in Theorem 2 is ${{\mathcal{H}}_{{K_{s}}}}$,
which is independent of $x_{1},\cdots,x_{n}$ by definition.

######  Theorem 5.

Let $M$ be given by Theorem 1. Let $f^{*}-\tilde{f}_{d}=bg$, where
$b\in\mathbb{R}$, and $g\in{{\mathcal{H}}_{K}}$ such that
$\|g\|_{{\mathcal{H}}_{K}}=1$ and $\langle
g,\hat{\psi}_{i}\rangle_{{\mathcal{H}}_{K}}=0$ for $i\in[d]$. Then,
$\|f^{*}-\tilde{f}_{d}\|_{P_{\mathcal{X}}}^{2}=b^{2}\|g\|_{P_{\mathcal{X}}}^{2}$,
and $\|f^{*}-\tilde{f}_{d}\|_{{\mathcal{H}}_{K}}^{2}=b^{2}\leq\frac{\epsilon
M\lambda_{1}-\frac{1}{2}}{\lambda_{1}-\|g\|_{P_{\mathcal{X}}}^{2}}B^{2}\qquad\text{for
all }f^{*}\text{ satisfying
\lx@cref{creftype~refnum}{ass:target}}.\vspace{-.05 in}$ (10) And if
Assumption 2 holds, then for any $\delta>0$, it holds with probability at
least $1-\delta$ that:
$\lambda_{d+1}\leq\|g\|_{P_{\mathcal{X}}}^{2}\leq\lambda_{d+1}+\frac{\kappa^{2}}{\sqrt{m}}{\left(2\sqrt{d}+3\sqrt{\log\frac{6}{\delta}}\right)}.$

######  Remark.

When $m$ is sufficiently large, $\|g\|_{P_{\mathcal{X}}}^{2}$ can be very
close to $\lambda_{d+1}$. Compared to 4, one can see that the bound for
$\|f^{*}-\tilde{f}_{d}\|_{P_{\mathcal{X}}}^{2}=b^{2}\|g\|_{P_{\mathcal{X}}}^{2}$
given by this result is near tight provided that
$\frac{s(\lambda_{1})}{\lambda_{1}}=\frac{s(\lambda_{d+1})}{\lambda_{d+1}}=M$:
The only difference is that Eqn. 10 has $\epsilon M\lambda_{1}-\frac{1}{2}$
instead of $\epsilon M\lambda_{1}-1$.

Our analysis in this section follows the framework of Zhai et al. (2024), but
we have the following technical improvements: (a) Estimation error: They bound
with classical local Gaussian and localized Rademacher complexity, while we
use the tighter bound in Fischer & Steinwart (2020) that is minimax optimal;
(b) Approximation error: Our Theorem 5 has three improvements. (i)
$\|g\|_{P_{\mathcal{X}}}^{2}-\lambda_{d+1}$ is $O(\sqrt{d})$ instead of
$O(d)$; (ii) It does not require delocalization of the top-$d$ eigenfunctions,
thereby removing the dependence on the covariance matrix; (iii) Our bound does
not depend on $\lambda_{d}^{-1}$.

Eigen-decomposition of ${\bm{G}}_{k,m}$ takes $O(m^{3})$ time in general,
though as of today the fastest algorithm takes $O(m^{\omega})$ time with
$\omega<2.38$ (Demmel et al., 2007), and could be faster if the kernel is
sparse.

##  5 Experiments

Table 1: Experiment results. We compare Label-Prop (LP) to STKR-Prop (SP) with
inverse Laplacian (Lap), with polynomial $s(\lambda)=\lambda^{8}$ (poly), with
kernel PCA (topd), and with $s(\lambda)=\lambda$ (KRR) (i.e. KRR with base
kernel). (t) and (i) indicate transductive and inductive settings. Test
samples account for 1% of all samples. We report the accuracies of the argmax
prediction of the estimators (%). Optimal hyperparameters are selected using a
validation set (see Appendix D for details). Standard deviations are given
across ten random seeds.

Dataset | LP (t) | SP-Lap (t) | SP-poly (t) | SP-topd (t) | SP-Lap (i) | SP-poly (i) | SP-topd (i) | KRR (i)
---|---|---|---|---|---|---|---|---
Computers | $77.30_{3.05}$ | $77.81_{3.94}$ | $76.72_{4.12}$ | $80.80_{3.06}$ | $77.15_{2.64}$ | ${71.91}_{4.13}$ | $80.80_{3.28}$ | $26.35_{4.34}$
Cora | $73.33_{6.00}$ | $77.04_{5.74}$ | $71.48_{5.80}$ | $69.26_{7.82}$ | $67.78_{7.62}$ | ${65.19}_{9.11}$ | $63.70_{6.00}$ | $28.52_{8.56}$
DBLP | $66.44_{3.78}$ | $65.42_{5.02}$ | $64.52_{4.20}$ | $64.86_{4.60}$ | $65.20_{4.92}$ | ${64.51}_{4.05}$ | $63.16_{3.41}$ | $44.80_{3.86}$

We implement STKR-Prop (SP) with inverse Laplacian (Lap), polynomial (poly)
$s(\lambda)=\lambda^{p}$, and kernel PCA (topd). We run them on several node
classification tasks, and compare them to Label-Prop (LP) and KRR with the
base kernel (i.e. STKR with $s(\lambda)=\lambda$). Details and full results
are deferred to Appendix D, and here we report a portion of the results in
Table 1, in which the best and second-best performances for each dataset are
marked in red and blue. We make the following observations:

  1. (a)

STKR works pretty well with general polynomial $s(\lambda)$ in the inductive
setting. In the transductive setting, the performance of SP-Lap is similar to
LP, and SP-poly is slightly worse. The inductive performance is slightly worse
than transductive, which is reasonable since there is less information at
train time for the inductive setting. Note that LP does not work in the
inductive setting.

  2. (b)

STKR with $s(\lambda)=\lambda^{p}$ for $p>1$ is much better than KRR (i.e.
$p=1$). In fact, we observe that for STKR with $s(\lambda)=\lambda^{p}$, a
larger $p$ performs better (see Figure 2 in Appendix D). This suggests one
possible reason why inverse Laplacian works so well empirically: It contains
$K^{p}$ for $p=1,2,\cdots$, so it can use multi-step similarity information up
to infinitely many steps.

  3. (c)

STKR also works pretty well with kernel PCA. Specifically, on 3 of the 9
datasets we use, such as Computers, kernel PCA is better than LP and STKR with
inverse Laplacian. This shows that inverse Laplacian and kernel PCA are two
parallel methods — neither is superior.

##  6 Conclusion

This work revisited the classical idea of STKR, and proposed a new class of
general and scalable STKR estimators able to leverage unlabeled data with a
base kernel. We established STKR as a general and principled approach,
provided scalable implementations for general transformation and inductive
settings, and proved statistical bounds with technical improvements over prior
work.

##### Limitations and open problems.

This work assumes full access to $K(x,x^{\prime})$, but in some cases
computing $K(x,x^{\prime})$ might be slow or impossible. The positive-pair
kernel in contrastive learning (Johnson et al., 2023) is such an example, for
which computing $K$ is hard but computing $\|f\|_{{{\mathcal{H}}_{K}}}^{2}$ is
easy, so our methods need to be modified accordingly. Also, this work does not
talk about how to choose the right base kernel $K$, which is a critical yet
difficult open problem. For graph tasks, STKR like label propagation only
leverages the graph, but it does not utilize the node features that are
usually provided, which are important for achieving high performances in
practice. Finally, this work focuses on the theoretical part, and a more
extensive empirical study on STKR is desired, especially within the context of
manifold learning, and modern self-supervised and semi-supervised learning.

There are three open problems from this work. (i) Improving the minimax
optimal learning rate: In this work, we provided statistical bounds w.r.t.
$n,m$ jointly, but one question we did not answer is: If $m$ is sufficiently
large, can we improve the minimax optimal learning rate w.r.t. $n$ proved in
prior work on supervised learning? (ii) Distribution shift: Diffusion induces
a chain of smooth function classes
${L^{2}(P_{\mathcal{X}})}\supset{\mathcal{H}}_{K^{1}}\supset{\mathcal{H}}_{K^{2}}\supset\cdots$,
but this chain will collapse if ${P_{\mathcal{X}}}$ changes. Can one learn
predictors or encoders that are robust to the shift in ${P_{\mathcal{X}}}$?
(iii) Combining multiple kernels: In practice, usually the predictor is
expected to satisfy multiple constraints. For example, an image classifier
should be invariant to small rotation, translation, perturbation, etc. When
each constraint induces a kernel, how should a predictor or encoder be
learned? We leave these problems to future work.

#### Code

The code of Section 5 can be found at
https://colab.research.google.com/drive/1m8OENF2lvxW3BB6CVEu45SGeK9IoYpd1?usp=sharing.

#### Acknowledgments

We would like to thank Zico Kolter, Andrej Risteski, Bingbin Liu, Elan
Rosenfeld, Shanda Li, Yuchen Li, Tanya Marwah, Ashwini Pokle, Amrith Setlur
and Xiaoyu Huang for their feedback on the early draft of this work, and
Yiping Lu and Fanghui Liu for their useful discussions. We are grateful to our
anonymous ICLR reviewers, with whose help this work has been greatly improved.
We acknowledge the support of NSF via IIS-1909816, IIS-2211907, ONR via
N00014-23-1-2368, DARPA under cooperative agreement HR00112020003, and
Bloomberg Data Science PhD fellowship.

## References

  * Belkin & Niyogi (2003) Mikhail Belkin and Partha Niyogi.  Laplacian eigenmaps for dimensionality reduction and data representation.  _Neural computation_ , 15(6):1373–1396, 2003.
  * Belkin et al. (2006) Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani.  Manifold regularization: A geometric framework for learning from labeled and unlabeled examples.  _Journal of machine learning research_ , 7(11), 2006.
  * Belkin et al. (2018) Mikhail Belkin, Siyuan Ma, and Soumik Mandal.  To understand deep learning we need to understand kernel learning.  In _International Conference on Machine Learning_ , pp. 541–549. PMLR, 2018.
  * Bengio et al. (2004) Yoshua Bengio, Olivier Delalleau, Nicolas Le Roux, Jean-François Paiement, Pascal Vincent, and Marie Ouimet.  Learning eigenfunctions links spectral embedding and kernel pca.  _Neural computation_ , 16(10):2197–2219, 2004.
  * Bengio et al. (2013) Yoshua Bengio, Aaron Courville, and Pascal Vincent.  Representation learning: A review and new perspectives.  _IEEE transactions on pattern analysis and machine intelligence_ , 35(8):1798–1828, 2013.
  * Berthelot et al. (2019) David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel.  Mixmatch: A holistic approach to semi-supervised learning.  _Advances in neural information processing systems_ , 32, 2019.
  * Berthelot et al. (2020) David Berthelot, Nicholas Carlini, Ekin D. Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel.  Remixmatch: Semi-supervised learning with distribution matching and augmentation anchoring.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=HklkeR4KPB.
  * Blanchard et al. (2007) Gilles Blanchard, Olivier Bousquet, and Laurent Zwald.  Statistical properties of Kernel Prinicipal Component Analysis.  _Machine Learning_ , 66(2-3):259–294, March 2007.  doi: 10.1007/s10994-006-6895-9.  URL https://hal.science/hal-00373789.
  * Bojchevski & Günnemann (2018) Aleksandar Bojchevski and Stephan Günnemann.  Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking.  In _International Conference on Learning Representations_ , 2018.
  * Brezis (2011) Haim Brezis.  _Functional analysis, Sobolev spaces and partial differential equations_.  Springer, 2011.
  * Buchholz (2022) Simon Buchholz.  Kernel interpolation in sobolev spaces is not consistent in low dimensions.  In _Conference on Learning Theory_ , pp. 3410–3440. PMLR, 2022.
  * Cabannes et al. (2023) Vivien Cabannes, Bobak Kiani, Randall Balestriero, Yann Lecun, and Alberto Bietti.  The SSL interplay: Augmentations, inductive bias, and generalization.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 3252–3298. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/cabannes23a.html.
  * Chapelle et al. (2002) Olivier Chapelle, Jason Weston, and Bernhard Schölkopf.  Cluster kernels for semi-supervised learning.  _Advances in neural information processing systems_ , 15, 2002.
  * Chapelle et al. (2006) Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien.  Semi-supervised learning.  _MIT Press_ , 2, 2006.
  * Chen et al. (2020) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _International conference on machine learning_ , pp. 1597–1607. PMLR, 2020.
  * Chung (1997) Fan RK Chung.  _Spectral graph theory_ , volume 92.  American Mathematical Soc., 1997.
  * Coifman & Lafon (2006) Ronald R Coifman and Stéphane Lafon.  Diffusion maps.  _Applied and computational harmonic analysis_ , 21(1):5–30, 2006.
  * Cubuk et al. (2019) Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le.  Autoaugment: Learning augmentation strategies from data.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 113–123, 2019.
  * Cubuk et al. (2020) Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le.  Randaugment: Practical automated data augmentation with a reduced search space.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops_ , pp. 702–703, 2020.
  * Cui et al. (2021) Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová.  Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime.  _Advances in Neural Information Processing Systems_ , 34:10131–10143, 2021.
  * de Hoop et al. (2023) Maarten V de Hoop, Nikola B Kovachki, Nicholas H Nelsen, and Andrew M Stuart.  Convergence rates for learning linear operators from noisy data.  _SIAM/ASA Journal on Uncertainty Quantification_ , 11(2):480–513, 2023.
  * Demmel et al. (2007) James Demmel, Ioana Dumitriu, and Olga Holtz.  Fast linear algebra is stable.  _Numerische Mathematik_ , 108(1):59–91, 2007.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1423.  URL https://aclanthology.org/N19-1423.
  * DeVries & Taylor (2017) Terrance DeVries and Graham W Taylor.  Improved regularization of convolutional neural networks with cutout.  _arXiv preprint arXiv:1708.04552_ , 2017.
  * Elworthy (1994) David Elworthy.  Does baum-welch re-estimation help taggers?  _CoRR_ , abs/cmp-lg/9410012, 1994.  URL http://arxiv.org/abs/cmp-lg/9410012.
  * Fey & Lenssen (2019) Matthias Fey and Jan E. Lenssen.  Fast graph representation learning with PyTorch Geometric.  In _ICLR Workshop on Representation Learning on Graphs and Manifolds_ , 2019.
  * Fischer & Steinwart (2020) Simon Fischer and Ingo Steinwart.  Sobolev norm learning rates for regularized least-squares algorithms.  _The Journal of Machine Learning Research_ , 21(1):8464–8501, 2020.
  * Gasteiger et al. (2019) Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann.  Diffusion improves graph learning.  _Advances in neural information processing systems_ , 32, 2019.
  * Goodfellow et al. (2013) Ian Goodfellow, Mehdi Mirza, Aaron Courville, and Yoshua Bengio.  Multi-prediction deep boltzmann machines.  In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (eds.), _Advances in Neural Information Processing Systems_ , volume 26. Curran Associates, Inc., 2013.  URL https://proceedings.neurips.cc/paper_files/paper/2013/file/0bb4aec1710521c12ee76289d9440817-Paper.pdf.
  * Györfi et al. (2002) László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk.  _A distribution-free theory of nonparametric regression_ , volume 1.  Springer, 2002.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30, 2017.
  * HaoChen et al. (2021) Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma.  Provable guarantees for self-supervised deep learning with spectral contrastive loss.  _Advances in Neural Information Processing Systems_ , 34:5000–5011, 2021.
  * Hassani & Khasahmadi (2020) Kaveh Hassani and Amir Hosein Khasahmadi.  Contrastive multi-view representation learning on graphs.  In _International conference on machine learning_ , pp. 4116–4126. PMLR, 2020.
  * He et al. (2022) Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 16000–16009, 2022.
  * Hjelm et al. (2019) R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio.  Learning deep representations by mutual information estimation and maximization.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=Bklr3j0cKX.
  * Huberty & Olejnik (2006) Carl J Huberty and Stephen Olejnik.  _Applied MANOVA and discriminant analysis_.  John Wiley & Sons, 2006.
  * Jin et al. (2023) Jikai Jin, Yiping Lu, Jose Blanchet, and Lexing Ying.  Minimax optimal kernel operator learning via multilevel training.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=zEn1BhaNYsC.
  * Johnson et al. (2023) Daniel D. Johnson, Ayoub El Hanchi, and Chris J. Maddison.  Contrastive learning can find an optimal basis for approximately view-invariant functions.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=AjC0KBjiMu.
  * Johnson & Zhang (2008) Rie Johnson and Tong Zhang.  Graph-based semi-supervised learning and spectral kernel design.  _IEEE Transactions on Information Theory_ , 54(1):275–288, 2008.
  * Jun et al. (2019) Kwang-Sung Jun, Ashok Cutkosky, and Francesco Orabona.  Kernel truncated randomized ridge regression: Optimal rates and low noise acceleration.  _Advances in neural information processing systems_ , 32, 2019.
  * Kipf & Welling (2016) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations_ , 2016.
  * Kondor & Lafferty (2002) Risi Imre Kondor and John Lafferty.  Diffusion kernels on graphs and other discrete structures.  In _Proceedings of the 19th international conference on machine learning_ , volume 2002, pp. 315–322, 2002.
  * Laine & Aila (2017) Samuli Laine and Timo Aila.  Temporal ensembling for semi-supervised learning.  In _International Conference on Learning Representations_ , 2017.  URL https://openreview.net/forum?id=BJ6oOfqge.
  * Lee (2013) Dong-Hyun Lee.  Pseudo-label : The simple and efficient semi-supervised learning method for deep neural networks.  In _ICML 2013 Workshop on Challenges in Representation Learning_ , 2013.
  * Li et al. (2022) Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton.  Optimal rates for regularized conditional mean embedding learning.  _Advances in Neural Information Processing Systems_ , 35:4433–4445, 2022.
  * Liang & Rakhlin (2020) Tengyuan Liang and Alexander Rakhlin.  Just interpolate: Kernel “Ridgeless” regression can generalize.  _The Annals of Statistics_ , 48(3):1329 – 1347, 2020.  doi: 10.1214/19-AOS1849.  URL https://doi.org/10.1214/19-AOS1849.
  * Lin et al. (2020) Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher.  Optimal rates for spectral algorithms with least-squares regression over hilbert spaces.  _Applied and Computational Harmonic Analysis_ , 48(3):868–890, 2020.
  * Liu et al. (2021) Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens.  Random features for kernel approximation: A survey on algorithms, theory, and beyond.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 44(10):7128–7148, 2021.
  * Mei et al. (2022) Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration.  _Applied and Computational Harmonic Analysis_ , 59:3–84, 2022.
  * Miyato et al. (2018) Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii.  Virtual adversarial training: a regularization method for supervised and semi-supervised learning.  _IEEE transactions on pattern analysis and machine intelligence_ , 41(8):1979–1993, 2018.
  * Ng et al. (2001) Andrew Ng, Michael Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  In T. Dietterich, S. Becker, and Z. Ghahramani (eds.), _Advances in Neural Information Processing Systems_ , volume 14. MIT Press, 2001.  URL https://proceedings.neurips.cc/paper_files/paper/2001/file/801272ee79cfde7fa5960571fee36b9b-Paper.pdf.
  * Oord et al. (2018) Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ , 2018.
  * Page et al. (1999) Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd.  The pagerank citation ranking : Bringing order to the web.  In _The Web Conference_ , 1999.  URL https://api.semanticscholar.org/CorpusID:1508503.
  * Papyan et al. (2020) Vardan Papyan, XY Han, and David L Donoho.  Prevalence of neural collapse during the terminal phase of deep learning training.  _Proceedings of the National Academy of Sciences_ , 117(40):24652–24663, 2020.
  * Rahimi & Recht (2007) Ali Rahimi and Benjamin Recht.  Random features for large-scale kernel machines.  _Advances in neural information processing systems_ , 20, 2007.
  * Rakhlin & Zhai (2019) Alexander Rakhlin and Xiyu Zhai.  Consistency of interpolation with laplace kernels is a high-dimensional phenomenon.  In _Conference on Learning Theory_ , pp. 2595–2623. PMLR, 2019.
  * Ranzato & Szummer (2008) Marc’Aurelio Ranzato and Martin Szummer.  Semi-supervised learning of compact document representations with deep networks.  In _Proceedings of the 25th international conference on Machine learning_ , pp. 792–799, 2008.
  * Rasmus et al. (2015) Antti Rasmus, Mathias Berglund, Mikko Honkala, Harri Valpola, and Tapani Raiko.  Semi-supervised learning with ladder networks.  _Advances in neural information processing systems_ , 28, 2015.
  * Roweis & Saul (2000) Sam T Roweis and Lawrence K Saul.  Nonlinear dimensionality reduction by locally linear embedding.  _science_ , 290(5500):2323–2326, 2000.
  * Schölkopf & Smola (2002) Bernhard Schölkopf and Alexander J Smola.  _Learning with kernels: support vector machines, regularization, optimization, and beyond_.  MIT press, 2002.
  * Shawe-Taylor et al. (2005) John Shawe-Taylor, Christopher KI Williams, Nello Cristianini, and Jaz Kandola.  On the eigenspectrum of the gram matrix and the generalization error of kernel-pca.  _IEEE Transactions on Information Theory_ , 51(7):2510–2522, 2005.
  * Shchur et al. (2018) Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann.  Pitfalls of graph neural network evaluation.  _Relational Representation Learning Workshop @ NeurIPS_ , 2018.
  * Shi & Zhang (2011) Mingguang Shi and Bing Zhang.  Semi-supervised learning improves gene expression-based prediction of cancer recurrence.  _Bioinformatics_ , 27(21):3017–3023, 2011.
  * Sinha & Duchi (2016) Aman Sinha and John C Duchi.  Learning kernels with random features.  _Advances in neural information processing systems_ , 29, 2016.
  * Smola & Kondor (2003) Alexander J Smola and Risi Kondor.  Kernels and regularization on graphs.  In _Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings_ , pp. 144–158. Springer, 2003.
  * Sohn et al. (2020) Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li.  Fixmatch: Simplifying semi-supervised learning with consistency and confidence.  _Advances in neural information processing systems_ , 33:596–608, 2020.
  * Steinwart & Christmann (2008) Ingo Steinwart and Andreas Christmann.  _Support vector machines_.  Springer Science & Business Media, 2008.
  * Steinwart et al. (2009) Ingo Steinwart, Don R Hush, and Clint Scovel.  Optimal rates for regularized least squares regression.  In _The 22nd Conference on Learning Theory_ , pp. 79–93, 2009.
  * Talwai et al. (2022) Prem Talwai, Ali Shameli, and David Simchi-Levi.  Sobolev norm learning rates for conditional mean embeddings.  In _International conference on artificial intelligence and statistics_ , pp. 10422–10447. PMLR, 2022.
  * Tarvainen & Valpola (2017) Antti Tarvainen and Harri Valpola.  Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results.  _Advances in neural information processing systems_ , 30, 2017.
  * Tenenbaum et al. (2000) Joshua B Tenenbaum, Vin de Silva, and John C Langford.  A global geometric framework for nonlinear dimensionality reduction.  _science_ , 290(5500):2319–2323, 2000.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  In _International Conference on Learning Representations_ , 2018.
  * Wainwright (2019) Martin J Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge university press, 2019.
  * Xie et al. (2020a) Qizhe Xie, Zihang Dai, Eduard Hovy, Thang Luong, and Quoc Le.  Unsupervised data augmentation for consistency training.  _Advances in neural information processing systems_ , 33:6256–6268, 2020a.
  * Xie et al. (2020b) Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoc V Le.  Self-training with noisy student improves imagenet classification.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 10687–10698, 2020b.
  * Yang et al. (2016) Zhilin Yang, William Cohen, and Ruslan Salakhudinov.  Revisiting semi-supervised learning with graph embeddings.  In _International conference on machine learning_ , pp. 40–48. PMLR, 2016.
  * Zhai et al. (2024) Runtian Zhai, Bingbin Liu, Andrej Risteski, Zico Kolter, and Pradeep Ravikumar.  Understanding augmentation-based self-supervised representation learning via rkhs approximation and regression.  In _International Conference on Learning Representations_ , 2024.  URL https://openreview.net/forum?id=Ax2yRhCQr1.
  * Zhang et al. (2017) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  In _International Conference on Learning Representations_ , 2017.  URL https://openreview.net/forum?id=Sy8gdB9xx.
  * Zhang et al. (2018) Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=r1Ddp1-Rb.
  * Zhou et al. (2003) Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf.  Learning with local and global consistency.  _Advances in neural information processing systems_ , 16, 2003.
  * Zhu & Ghahramani (2002) Xiaojin Zhu and Zoubin Ghahramani.  Learning from labeled and unlabeled data with label propagation.  In _CMU CALD tech report CMU-CALD-02-107_ , 2002.
  * Zhu et al. (2006) Xiaojin Zhu, Jaz S Kandola, John Lafferty, and Zoubin Ghahramani.  Graph kernels by spectral transforms.  In Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien (eds.), _Semi-supervised learning_ , chapter 15. MIT Press, 2006.

## Appendix

Table 2: Table of notations. Notation | Description
---|---
$\delta_{i,j}$ | Kronecker delta. Equal to 1 if $i=j$, and 0 otherwise
${\mathcal{X}}$ | Input space, assumed to be a compact Hausdorff space
${\mathcal{Y}}$ | Label space, assumed to be $\mathbb{R}$
$P_{{\mathcal{X}}{\mathcal{Y}}}$ | Underlying data distribution over ${\mathcal{X}}\times{\mathcal{Y}}$
${P_{\mathcal{X}}},{P_{\mathcal{Y}}}$ | Marginal distributions of $P_{{\mathcal{X}}{\mathcal{Y}}}$
$dp(x)$ | A shorthand of $d{P_{\mathcal{X}}}(x)$
$n,m$ | Numbers of labeled and unlabeled i.i.d. samples from $P_{{\mathcal{X}}{\mathcal{Y}}}$ and ${P_{\mathcal{X}}}$, respectively
$x_{1},\cdots,x_{n+m}$ |  $x_{1},\cdots,x_{n}$ are the labeled samples, and $x_{n+1},\cdots,x_{n+m}$ are unlabeled
$y_{1},\cdots,y_{n}$ | The observed labels. Also define ${\bm{y}}=[y_{1},\cdots,y_{n}]\in\mathbb{R}^{n}$
${L^{2}(P_{\mathcal{X}})}$ |  $L^{2}$ function space w.r.t. ${P_{\mathcal{X}}}$, with inner product $\langle\cdot,\cdot\rangle_{P_{\mathcal{X}}}$ and norm $\|\cdot\|_{P_{\mathcal{X}}}$
$K(x,x^{\prime})$ | A Mercer base kernel that encodes inter-sample similarity information
${\bm{G}}_{K}$ |  $(n+m)\times(n+m)$ Gram matrix over all samples. ${\bm{G}}_{K}[i,j]=K(x_{i},x_{j})$
${\bm{G}}_{K,n}$ |  $n\times n$ Gram matrix over the $n$ labeled samples
${\bm{G}}_{K,m}$ |  $m\times m$ Gram matrix over the $m$ unlabeled samples
$T_{K}$ | An integral operator w.r.t. $K$, $(T_{K}f)(x)=\int f(x^{\prime})K(x,x^{\prime})dp(x)$
$(\lambda_{i},\psi_{i})$ | Eigenvalue and eigenfunction of $T_{K}$ such that $T_{K}\psi_{i}=\lambda_{i}\psi_{i}$. $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq 0$
${\mathbb{I}}$ | The set ${\left\\{i\in\mathbb{N}:\lambda_{i}>0\right\\}}$
$K_{s}(x,x^{\prime})$ | A spectrally transformed kernel of $K$, whose formula is given by Eqn. 3
$s(\lambda)$ | The transformation function of $K_{s}(x,x^{\prime})$
$M$ |  $s(\lambda)\leq M\lambda$ as proved in Theorem 1. Frequently used in other theorems
$K^{p}(x,x^{\prime})$ | Equivalent to $K_{s}(x,x^{\prime})$ with $s(\lambda)=\lambda^{p}$, for all $p\in\mathbb{R}$
${\mathcal{H}}_{K^{p}}$ | The RKHS associated with $K^{p}(x,x^{\prime})$ when $p\geq 1$. ${\mathcal{H}}_{K^{1}}$ is also denoted by ${\mathcal{H}}_{K}$
${\mathcal{H}}_{K_{s}}$ | The RKHS associated with $K_{s}(x,x^{\prime})$ that encodes target smoothness
$d_{K^{p}}$ | The kernel metric of $K^{p}$, defined as $d_{K^{p}}(x,x^{\prime})=\sum_{i}\lambda_{i}^{p}(\psi_{i}(x)-\psi_{i}(x^{\prime}))$
$\overline{\text{Lip}}_{d_{K^{p}}}(f)$ | The Lipschitz constant of $f$ w.r.t. metric $d_{K^{p}}$ over $\bar{{\mathcal{X}}}$ defined in Section 2.1
$r_{K^{p}}(f)$ | Defined as $\|f-\mathbb{E}_{{P_{\mathcal{X}}}}[f]\|_{{P_{\mathcal{X}}}}^{2}/\;\overline{\text{Lip}}_{d_{K^{p}}}(f)^{2}$, similar to the discriminant function
$r_{t}(f)$ | Defined as $\|f-\mathbb{E}_{{P_{\mathcal{X}}}}[f]\|_{{P_{\mathcal{X}}}}^{2}/\overline{\text{Lip}}_{d_{t}}(f)^{2}$. $d_{t}$ is defined in Section 2.1
$f^{*}$ | Regression function defined as $f^{*}(x):=\int y\;dP_{{\mathcal{X}}{\mathcal{Y}}}(y|x)\in{L^{2}(P_{\mathcal{X}})}$
$\hat{f}$ | A predictor that approximates $f^{*}$. For STKR, its formula is given by Eqn. 4
$B$ | The scale of $f^{*}$, defined as $\|f^{*}\|_{P_{\mathcal{X}}}\leq B$
$\pi_{p}$ | The coefficient of $K_{s}$ when it is assumed to be polynomial in Assumption 1
$\kappa^{2}$ | The upper bound of $K(x,x)$ for ${P_{\mathcal{X}}}$-a.e. $x\in{\mathcal{X}}$. See Assumption 2
$\epsilon$ |  $f^{*}$ is assumed to satisfy $r_{t}(f^{*})\geq\epsilon^{-1}$ in Assumption 3
$\sigma,L$ | Used in the moment condition in Assumption 4
$\beta_{n}$ | The regularization coefficient in KRR and STKR. Can change with $n$
${\hat{K}_{s}}$ | A computable kernel used to approximate $K_{s}$, defined in Eqn. 5
${\bm{v}}_{K}(x)$ | An $\mathbb{R}^{n+m}$ vector. An important component of ${\hat{K}_{s}}$ defined after Eqn. 5
$\tilde{f}$ | A predictor defined in Eqn. 6 that is inaccessible, but important in our analysis
$\tilde{{\bm{\alpha}}},\hat{{\bm{\alpha}}}$ | Defined in Eqns. 6 and 7
$\hat{\lambda}_{1}$ | The largest eigenvalue of $\frac{{\bm{G}}_{K}}{n+m}$
$\gamma$ | The “step size” in STKR-Prop implemented with Richardson iteration
$\eta$ | A hyperparameter of inverse Laplacian, which is defined with $s^{-1}(\lambda)=\lambda^{-1}-\eta$
$\hat{\Psi}$ | A pretrained $d$-dimensional representation $[\hat{\psi}_{1},\cdots,\hat{\psi}_{d}]$ in representation learning
$\hat{{\bm{w}}}$ | A linear probe on top of $\hat{\Psi}$ trained during downstream, and $\hat{f}_{d}(x)=\hat{{\bm{w}}}^{\top}\hat{\Psi}(x)$
${\mathcal{H}}_{\hat{\Psi}}$ | A $d$-dimensional RKHS spanned by $\hat{\Psi}$, and it is a subspace of ${\mathcal{H}}_{K}$
$\tilde{f}_{d}$ | Projection of $f^{*}$ onto ${\mathcal{H}}_{\hat{\Psi}}$

##  Appendix A Related Work

###  A.1 Learning with Unlabeled Data

There are two broad classes of methods of learning with unlabeled data, namely
semi-supervised learning and representation learning. Semi-supervised learning
focuses on how to improve supervised learning by incorporating unlabeled
samples, while representation learning focuses on how to extract a low-
dimensional representation of data using huge unlabeled data.

Semi-supervised learning has long been used in different domains to enhance
the performance of machine learning (Elworthy, 1994; Ranzato & Szummer, 2008;
Shi & Zhang, 2011). While there are a wide variety of semi-supervised learning
algorithms, the main differences between them lie in their way of realizing
the assumption of consistency (Zhou et al., 2003), i.e. soft constraints that
the predictor is expected to satisfy by prior knowledge. Enforcing consistency
can be viewed as an auxiliary task (Goodfellow et al., 2013; Rasmus et al.,
2015), since the unlabeled samples cannot be used in the “main task” involving
the labels. The smoothness studied in this work can be regarded as one type of
consistency.

While there are various types of consistency, most of them can be put into one
of three categories: Euclidean-based consistency, prediction-based consistency
and similarity-based consistency.

Euclidean-based consistency supposes ${\mathcal{X}}$ to be an Euclidean space,
and relies on the assumption that $x,x^{\prime}$ have the same label with high
probability if they are close in the Euclidean distance, which is the
foundation of many classical methods including nearest neighbor, clustering
and RBF kernels. In the context of semi-supervised learning, virtual
adversarial training (VAT) learns with unlabeled samples by perturbing them
with little noise and forcing the model to give consistent outputs (Miyato et
al., 2018). Mixup (Zhang et al., 2018) uses a variant of Euclidean-based
consistency, which assumes that for two samples $(x_{1},y_{1})$ and
$(x_{2},y_{2})$ and any $\theta\in(0,1)$, the label of $\theta
x_{1}+(1-\theta)x_{2}$ should be close to $\theta y_{1}+(1-\theta)y_{2}$.
Mixup has been proved to be empirically successful, and was later further
improved by Mixmatch (Berthelot et al., 2019).

Prediction-based consistency assumes that deep learning models enjoy good
generalization: When a deep model is well trained on a small set of labeled
samples, it should be able to achieve fairly good accuracy on the much larger
set of unlabeled samples. The most simple method is pseudo labeling (Lee,
2013), which first trains a model only on the labeled samples, then uses it to
label the unlabeled samples, and finally trains a second label on all samples.
There are a large number of variants of pseudo labeling, also known as self-
training. For instance, temporal ensembling (Laine & Aila, 2017) pseudo labels
the unlabeled samples with models from previous epochs; Mean teacher
(Tarvainen & Valpola, 2017) improves temporal ensembling for large datasets by
using a model that averages the weights of previous models to generate pseudo
labels; And NoisyStudent (Xie et al., 2020b), which does self-training
iteratively with noise added at each iteration, reportedly achieves as high as
88.4% top-1 accuracy on ImageNet.

Finally, similarity-based consistency assumes prior knowledge about some kind
of similarity over samples or transformations of the samples. A classical type
of similarity-based consistency is based on graphs, and there is a rich body
of literature on semi-supervised learning on graphs (Zhou et al., 2003;
Johnson & Zhang, 2008) and GNNs (Kipf & Welling, 2016; Hamilton et al., 2017;
Veličković et al., 2018). The most popular type of similarity-based
consistency in deep learning is based on random data augmentation, also known
as invariance-based consistency, where all augmentations of the same sample
are assumed to be similar and thus should share the same label. This simple
idea has been reported to achieve good performances by a lot of work,
including UDA (Xie et al., 2020a), ReMixMatch (Berthelot et al., 2020) and
FixMatch (Sohn et al., 2020). People have also experimented a variety of
augmentation techniques, ranging from simple ones like image translation,
flipping and rotation to more complicated ones like Cutout (DeVries & Taylor,
2017), AutoAugment (Cubuk et al., 2019) and RandAugment (Cubuk et al., 2020).

Representation learning aims to learn low-dimensional representations of data
that concisely encodes relevant information useful for building classifiers or
other predictors (Bengio et al., 2013). By this definition, in order to learn
a good representation, we need to have information about what classifiers or
predictors we want to build, for which consistency also plays a very important
role. Popular representation learning algorithms based on consistency can be
roughly classified into Euclidean-based or similarity-based consistency. There
is no prediction-based consistency for unsupervised representation learning
because there is nothing to “predict” in the first place.

Euclidean-based consistency has been widely applied in manifold learning, such
as LLE (Roweis & Saul, 2000), Isomap (Tenenbaum et al., 2000) and Laplacian
eigenmaps (Belkin & Niyogi, 2003), whose goal is to determine the low-
dimensional manifold on which the observed high-dimensional data resides. See
Bengio et al. (2004) for descriptions of these methods.

Similarity-based consistency is the basis of most deep representation learning
algorithms. In fact, Euclidean-based consistency can be viewed as a special
case of similarity-based consistency, which assumes near samples under the
Euclidean distance to be similar. The most obvious similarity-based method is
contrastive learning (Oord et al., 2018; Hjelm et al., 2019; Chen et al.,
2020), which requires the model to assign similar representations to
augmentations of the same sample. But in fact, lots of representation learning
methods that make use of certain auxiliary tasks can be viewed as enforcing
similarity-based consistency. If the auxiliary task is to learn a certain
multi-dimensional target function $g(x)$, then by defining kernel
$K_{g}(x,x^{\prime}):=\langle g(x),g(x^{\prime})\rangle$, the task can also be
seen as approximating $K_{g}$, and $K_{g}$ encodes some kind of inter-sample
similarity. For example, even supervised pretraining such as ImageNet
pretraining, can be viewed as enforcing similarity-based consistency (defined
by the ImageNet labels) over the data. In fact, Papyan et al. (2020) showed
that if supervised pretraining with cross entropy loss is run for sufficiently
long time, then the representations will neural collapse to the class labels
(i.e. samples of the same class share exactly the same representation), which
is a natural consequence of enforcing class-based similarity. Zhai et al.
(2024) also showed that mask-based auxiliary tasks such as BERT (Devlin et
al., 2019) and MAE (He et al., 2022) can also be viewed as approximating a
similarity kernel.

Finally, for semi-supervised and self-supervised learning on graphs, diffusion
has been widely used, from the classical works of Page et al. (1999); Kondor &
Lafferty (2002) to more recent papers such as Gasteiger et al. (2019); Hassani
& Khasahmadi (2020). For graph tasks, STKR can be viewed as a generalization
of these diffusion-based methods.

###  A.2 Statistical Learning Theory on Kernel Methods

Kernel methods have a very long history and there is a very rich body of
literature on theory pertaining to kernels, which we shall not make an
exhaustive list here. We point our readers who want to learn more about
kernels to two books that are referred to a lot in this work: Schölkopf &
Smola (2002); Steinwart & Christmann (2008). Also, Chapters 12-14 of
Wainwright (2019) can be more helpful and easier to read for elementary
readers.

Here we would like to briefly talk about recent theoretical progress on kernel
methods, especially on interpolation Sobolev spaces. This work uses the
results in Fischer & Steinwart (2020), in which minimax optimal learning rates
for regularized least-squares regression under Sobolev norms were proved.
Meanwhile, Lin et al. (2020) proved that KRR converges to the Bayes risk at
the best known rate among kernel-based algorithms. Addition follow-up work
includes Jun et al. (2019); Cui et al. (2021); Talwai et al. (2022); Li et al.
(2022); de Hoop et al. (2023); Jin et al. (2023).

However, there are also counter arguments to this line of work, and kernel-
based learning is by no means a solved problem. As Jun et al. (2019) pointed
out, these optimal rates only match the lower bounds under certain assumptions
(Steinwart et al., 2009). Besides, most of these minimax optimal learning
rates are for KRR, which requires a greater-than-zero regularization term, but
empirical observations suggest that kernel regression with regularization can
perform equally well, if not better (Zhang et al., 2017; Belkin et al., 2018;
Liang & Rakhlin, 2020). What makes things even more complicated is that kernel
“ridgeless” regression seems to only work for high-dimensional data under some
conditions, as argued in Rakhlin & Zhai (2019); Buchholz (2022) who showed
that minimum-norm interpolation in the RKHS w.r.t. Laplace kernel is not
consistent if the input dimension is constant. Overall, while kernel methods
have a very long history, they still have lots of mysteries, which we hope
that future work can shed light on.

Another class of methods in parallel with STKR is random features, first
introduced in the seminal work Rahimi & Recht (2007). We refer our readers to
Liu et al. (2021) for a survey on random features. The high-level idea of
random features is the following: One first constructs a class of features
$\\{\varphi(x,\theta)\\}$ parameterized by $\theta$, e.g. Fourier features.
Then, randomly sample $D$ features from this class, and perform KRR or other
learning algorithms on this set of random features. Now, why would such method
have good generalization? As explained in Mei et al. (2022), if $D$ is very
large (overparameterized regime), then the approximation error is small since
$f^{*}$ should be well represented by the $D$ features, but the estimation
error is large because more features means more complexity; If $D$ is very
small (underparameterized regime), then the model is simple so the estimation
error is small, but the approximation error could be large because the $D$
features might be unable to represent $f^{*}$. However, since the class of
features $\\{\varphi(x,\theta)\\}$ is of our choice, we can choose them to be
“good” features (e.g. with low variance) so that the estimation error will not
be very large even if $D$ is big. Rahimi & Recht (2007) used Fourier features
that are good, and there are lots of other good features we could use. One can
even try to learn the random features: For example, Sinha & Duchi (2016)
proposed to learn a distribution over a pre-defined class of random features
such that the resulting kernel aligns with the labels.

##  Appendix B Proofs

###  B.1 Proof of Proposition 1

###### Proof.

First, for all $f\in{\mathcal{H}}_{K^{p}}$, and
$\mu,\nu\in\bar{{\mathcal{X}}}$ we have

$\displaystyle\left|\bar{f}(\mu)-\bar{f}(\nu)\right|$
$\displaystyle=\left|\int_{{\mathcal{X}}}f(x)d\mu(x)-\int_{{\mathcal{X}}}f(x)d\nu(x)\right|=\left|{\left\langle
f,\int_{{\mathcal{X}}}K_{x}^{p}d\mu(x)-\int_{{\mathcal{X}}}K_{x}^{p}d\nu(x)\right\rangle}_{{\mathcal{H}}_{K^{p}}}\right|$
$\displaystyle\leq\|f\|_{{\mathcal{H}}_{K^{p}}}{\left\|\int_{{\mathcal{X}}}K_{x}^{p}d\mu(x)-\int_{{\mathcal{X}}}K_{x}^{p}d\nu(x)\right\|}_{{\mathcal{H}}_{K^{p}}}=\|f\|_{{\mathcal{H}}_{K^{p}}}d_{K^{p}}(\mu,\nu),$

which means that
$\overline{\text{Lip}}_{d_{K^{p}}}(f)\leq\|f\|_{{\mathcal{H}}_{K^{p}}}$.

Second, $\\{K_{x}^{p}-K_{x^{\prime}}^{p}\\}_{x,x^{\prime}\in{\mathcal{X}}}$
span the entire ${\mathcal{H}}_{K^{p}}$, because if
$f\in{\mathcal{H}}_{K^{p}}$ satisfies $\langle
f,K_{x}^{p}-K_{x^{\prime}}^{p}\rangle_{{\mathcal{H}}_{K^{p}}}=0$ for all
$x,x^{\prime}$, then $f\equiv c$ for some $c$, which means that $f\equiv 0$
since ${\bm{0}}$ is the only constant function in ${\mathcal{H}}_{K^{p}}$
(because $K$ is centered). Thus, any $f\in{\mathcal{H}}_{K^{p}}$ can be
written as
$f=\iint{\left(K_{x}^{p}-K_{x^{\prime}}^{p}\right)}d\xi(x,x^{\prime})$ for
some finite signed measure $\xi$ over ${\mathcal{X}}\times{\mathcal{X}}$, and
thus
$f=\int_{{\mathcal{X}}}K_{x}^{p}d\mu(x)-\int_{{\mathcal{X}}}K_{x}^{p}d\nu(x)$,
where $\mu,\nu$ are the marginal measures of $\xi$. By using such defined
$\mu,\nu$ in the above formula, we can see that
$\overline{\text{Lip}}_{d_{K^{p}}}(f)=\|f\|_{{\mathcal{H}}_{K^{p}}}$. ∎

###  B.2 Proof of Theorem 1

First, we show that ${\mathcal{H}}_{t}$ must be an RKHS. Since $\psi_{1}$ is
the top-1 eigenfunction of $K^{p}$ for all $p\geq 1$, we have
$r_{K^{p}}(\psi_{1})\geq r_{K^{p}}(f)$ for all $f\in{{\mathcal{H}}_{K}}$,
which implies that $r_{t}(\psi_{1})\geq r_{t}(f)$ for all
$f\in{\mathcal{H}}_{t}\subset{{\mathcal{H}}_{K}}$. Let
$C_{0}:=r_{t}(\psi_{1})$. Then, for all $f\in{\mathcal{H}}_{t}$, since $f$
must be centered, we have $\|f\|_{{P_{\mathcal{X}}}}^{2}\leq
C_{0}\cdot\overline{\text{Lip}}_{d_{t}}(f)^{2}$. Let
$\tilde{f}=f/\|f\|_{{\mathcal{H}}_{t}}$, then:

$\displaystyle\|f\|_{{P_{\mathcal{X}}}}$
$\displaystyle\leq\sqrt{C_{0}}\cdot\sup_{x,x^{\prime}\in\overline{{\mathcal{X}}},x\neq
x^{\prime}}\;\inf_{\|f_{1}\|_{{\mathcal{H}}_{t}}=1}\frac{|f(x)-f(x^{\prime})|}{|f_{1}(x)-f_{1}(x^{\prime})|}$
$\displaystyle\leq\sqrt{C_{0}}\cdot\sup_{x,x^{\prime}\in\overline{{\mathcal{X}}},x\neq
x^{\prime}}\frac{|f(x)-f(x^{\prime})|}{|\tilde{f}(x)-\tilde{f}(x^{\prime})|}=\sqrt{C_{0}}\|f\|_{{\mathcal{H}}_{t}}.$

This implies that $\|\cdot\|_{{\mathcal{H}}_{t}}$ is stronger than
$\|\cdot\|_{{P_{\mathcal{X}}}}$. Thus, if there is a sequence of points
$\\{x_{i}\\}$ such that $x_{i}\rightarrow x$ w.r.t.
$\|\cdot\|_{{\mathcal{H}}_{t}}$, then (a) $x\in{\mathcal{H}}_{t}$ because
${\mathcal{H}}_{t}$ is a Hilbert space, and (b) $x_{i}\rightarrow x$ w.r.t.
$\|\cdot\|_{{P_{\mathcal{X}}}}$. Meanwhile, we know that
$\|\cdot\|_{{{\mathcal{H}}_{K}}}$ is stronger than
$\|\cdot\|_{{P_{\mathcal{X}}}}$, so $x_{i}\rightarrow x$ w.r.t.
$\|\cdot\|_{{{\mathcal{H}}_{K}}}$ also implies $x_{i}\rightarrow x$ w.r.t.
$\|\cdot\|_{{P_{\mathcal{X}}}}$.

Now, consider the inclusion map
$I:{\mathcal{H}}_{t}\rightarrow{{\mathcal{H}}_{K}}$, such that $Ix=x$. For any
sequence $\\{x_{i}\\}\subset{\mathcal{H}}_{t}$ such that $x_{i}\rightarrow x$
w.r.t. $\|\cdot\|_{{\mathcal{H}}_{t}}$ and $Ix_{i}\rightarrow y$ w.r.t.
$\|\cdot\|_{{{\mathcal{H}}_{K}}}$, we have $x_{i}\rightarrow x$ w.r.t.
$\|\cdot\|_{{P_{\mathcal{X}}}}$, and $x_{i}\rightarrow y$ w.r.t.
$\|\cdot\|_{{P_{\mathcal{X}}}}$. Thus, we must have $y=x=Ix$, meaning that the
graph of $I$ is closed. So the closed graph theorem says that $I$ must be a
bounded operator, meaning that there exists a constant $C>0$ such that
$\|f\|_{{\mathcal{H}}_{K}}\leq C\|f\|_{{\mathcal{H}}_{t}}$ for all
$f\in{\mathcal{H}}_{t}$. (For an introduction of the closed graph theorem, see
Chapter 2 of Brezis (2011).)

For all $f\in{{\mathcal{H}}_{K}}$, let $\delta_{x}:f\mapsto f(x)$ be the
evaluation functional at point $x$. Since ${{\mathcal{H}}_{K}}$ is an RKHS,
for any $x\in{\mathcal{X}}$, $\delta_{x}$ is a bounded functional on
${{\mathcal{H}}_{K}}$, which means that there exists a constant $M_{x}>0$ such
that $|f(x)|\leq M_{x}\|f\|_{{{\mathcal{H}}_{K}}}$ for all
$f\in{{\mathcal{H}}_{K}}$. So for any
$f\in{\mathcal{H}}_{t}\subset{{\mathcal{H}}_{K}}$, there is $|f(x)|\leq
M_{x}\|f\|_{{{\mathcal{H}}_{K}}}\leq M_{x}C\|f\|_{{\mathcal{H}}_{t}}$, which
means that $\delta_{x}$ is also a bounded functional on ${\mathcal{H}}_{t}$.
Thus, ${\mathcal{H}}_{t}$ must be an RKHS. Let ${K_{s}}$ be the reproducing
kernel of ${\mathcal{H}}_{t}$. From now on, we will use
${{\mathcal{H}}_{{K_{s}}}}$ to denote ${\mathcal{H}}_{t}$. Now that
${{\mathcal{H}}_{{K_{s}}}}$ is an RKHS, we can use the proof of 1 to show that
$\overline{\text{Lip}}_{d_{t}}(f)=\|f\|_{{{\mathcal{H}}_{{K_{s}}}}}$, which
implies that
$r_{t}(f)=\|f-\mathbb{E}_{{P_{\mathcal{X}}}}[f]\|_{{P_{\mathcal{X}}}}^{2}/\|f\|_{{{\mathcal{H}}_{{K_{s}}}}}^{2}$.

Second, we prove by induction that $\psi_{1},\cdots,\psi_{d}$ are the top-$d$
eigenfunctions of ${K_{s}}$, and they are pairwise orthogonal w.r.t.
${{\mathcal{H}}_{{K_{s}}}}$. When $d=1$, $\psi_{1}$ is the top-1 eigenfunction
of $K^{p}$ for all $p\geq 1$, so
$\psi_{1}\in\operatorname*{arg\,max}_{f\in{L^{2}(P_{\mathcal{X}})}}r_{K^{p}}(f)$.
By the relative smoothness preserving assumption, this implies that
$\psi_{1}\in\operatorname*{arg\,max}_{f\in{L^{2}(P_{\mathcal{X}})}}r_{t}(f)$.
Therefore, $\psi_{1}$ must be the top-1 eigenfunction of ${K_{s}}$. Now for
$d\geq 2$, suppose $\psi_{1},\cdots,\psi_{d-1}$ are the top-$(d-1)$
eigenfunctions of ${K_{s}}$ with eigenvalues $s_{1},\cdots,s_{d-1}$, and they
are pairwise orthogonal w.r.t. ${{\mathcal{H}}_{{K_{s}}}}$. Let
${\mathcal{H}}_{0}=\\{f:\langle f,\psi_{i}\rangle_{P_{\mathcal{X}}}=0,\forall
i\in[d-1]\\}$. Obviously, ${\mathcal{H}}_{0}\cap{\mathcal{H}}_{K^{p}}$ is a
closed subspace of ${\mathcal{H}}_{K^{p}}$ for all $p\geq 1$. And for any
$f\in{\mathcal{H}}_{0}\cap{{\mathcal{H}}_{{K_{s}}}}$ and any $i\in[d-1]$, we
have $\langle
f,\psi_{i}\rangle_{{\mathcal{H}}_{{K_{s}}}}=f^{\top}(K_{s}^{-1}\psi_{i})=f^{\top}s_{i}^{-1}\psi_{i}=0$,
so ${{\mathcal{H}}_{{K_{s}}}}\cap{\mathcal{H}}$ is a closed subspace of
${{\mathcal{H}}_{{K_{s}}}}$. Applying the assumption with this
${\mathcal{H}}_{0}$, we can see that $\psi_{d}$ is the top-$d$ eigenfunction
of ${K_{s}}$, and is orthogonal to $\psi_{1},\cdots,\psi_{d-1}$ w.r.t. both
${{\mathcal{H}}_{{K_{s}}}}$. Thus, we complete our proof by induction. And if
$\lambda_{d}=\lambda_{d+1}$, then we can show that both
$\psi_{1},\cdots,\psi_{d-1},\psi_{d}$ and
$\psi_{1},\cdots,\psi_{d-1},\psi_{d+1}$ are the top-$d$ eigenfunctions of
${K_{s}}$, meaning that $s_{d}=s_{d+1}$. Thus, ${K_{s}}$ can be written as
${K_{s}}(x,x^{\prime})=\sum_{i}s_{i}\psi_{i}(x)\psi_{i}(x^{\prime})$, where
$s_{1}\geq s_{2}\geq\cdots\geq 0$, and $s_{i}=s_{i+1}$ if
$\lambda_{i}=\lambda_{i+1}$. Moreover, by
${{\mathcal{H}}_{{K_{s}}}}\subset{{\mathcal{H}}_{K}}$, it is obviously true
that $\lambda_{i}=0$ implies $s_{i}=0$.

Third, we prove by contradiction that $s_{i}\leq M\lambda_{i}$ for all $i$. If
this statement is false, then obviously one can find $t_{1}<t_{2}<\cdots$ such
that $s_{t_{i}}\geq i\cdot\lambda_{t_{i}}$ for all $i$. Consider
$f=\sum_{i}\sqrt{i^{-1}\lambda_{t_{i}}}\psi_{i}$, for which
$\|f\|_{{\mathcal{H}}_{K}}^{2}=\sum_{i}i^{-1}=+\infty$. Since
${{\mathcal{H}}_{{K_{s}}}}\subset{{\mathcal{H}}_{K}}$, this implies that
$\|f\|_{{\mathcal{H}}_{{K_{s}}}}^{2}=+\infty$, so we have
$+\infty=\sum_{i}\frac{\lambda_{t_{i}}}{i\cdot
s_{t_{i}}}\leq\sum_{i}\frac{\lambda_{t_{i}}}{i^{2}\lambda_{t_{i}}}=\sum_{i}\frac{1}{i^{2}}<+\infty$,
which gives a contradiction and proves the claim.

Fourth, we find a function $s(\lambda)$ that satisfies the conditions in the
theorem to interpolate those points. Before interpolation, we first point out
that we can WLOG assume that $\lambda_{i}<2\lambda_{i+1}$ for all $i$: If
there is an $i$ that does not satisfy this condition, we simply insert some
new $\lambda$’s between $\lambda_{i}$ and $\lambda_{i+1}$, whose corresponding
$s$’s are the linear interpolations between $s_{i}$ and $s_{i+1}$, so that
$s_{i}\leq M\lambda_{i}$ still holds. With this assumption, it suffices to
construct a series of bump functions $\\{f_{i}\\}_{i=1}^{\infty}$, where
$f_{i}\equiv 0$ if $\lambda_{i}=\lambda_{i+1}$; otherwise,
$f_{i}(\lambda)=s_{i}-s_{i+1}$ for $\lambda\geq\lambda_{i}$ and
$f_{i}(\lambda)=0$ for $\lambda\leq\lambda_{i+1}$. Such bump functions are
$C^{\infty}$ and monotonically non-decreasing. Then, define
$s(\lambda)=\sum_{i}f_{i}(\lambda)$ for $\lambda>0$, and $s(0)=0$. This sum of
bump functions converges everywhere on $(0,+\infty)$, since it is a finite sum
locally everywhere. Clearly this $s$ is monotonic, interpolates all the
points, continuous on $[0,+\infty)$ and $C^{\infty}$ on $(0,+\infty)$. And for
all $\lambda$ that is not $\lambda_{i}$, for instance
$\lambda\in(\lambda_{i+1},\lambda_{i})$, there is $s(\lambda)\leq
s(\lambda_{i})\leq M\lambda_{i}\leq 2M\lambda_{i+1}\leq 2M\lambda$. Thus,
$s(\lambda)=O(\lambda)$ for $\lambda\in[0,+\infty)$. ∎

######  Remark.

In general, we cannot guarantee that $s(\lambda)$ is differentiable at
$\lambda=0$. Here is a counterexample: $\lambda_{i}=3^{-i}$, and
$s_{i}=3^{-i}$ if $i$ is odd and $2\cdot 3^{-i}$ if $i$ is even. Were
$s(\lambda)$ to be differentiable at $\lambda=0$, its derivative would be $1$
and also would be $2$, which leads to a contradiction. Nevertheless, if the
target smoothness is strictly stronger than base smoothness, i.e.
$\overline{\text{Lip}}_{d_{K}}(f)=o(\overline{\text{Lip}}_{d_{t}}(f))$, then
$s$ can be differentiable at $\lambda=0$ but still not $C^{\infty}$.

##### Link with discriminant analysis and the Poincaré constant.

First, we point out the connection between $r_{K^{p}}(f)$ and the discriminant
function in discriminant analysis (see Chapters 3-4 of Huberty & Olejnik
(2006)). We can see that $r_{K^{p}}(f)$ is defined as the proportion of
variance of $f$ w.r.t. ${L^{2}(P_{\mathcal{X}})}$ and w.r.t.
${\mathcal{H}}_{K^{p}}$, so essentially $r_{K^{p}}(f)$ measures how much
variance of $f$ is kept by the inclusion map
${\mathcal{H}}_{K^{p}}\hookrightarrow{L^{2}(P_{\mathcal{X}})}$. Meanwhile, the
discriminant function is the proportion of variance of $f$ in the grouping
variable and in total. Thus, similar to PCA which extracts the $d$ features
that keep the most variance (i.e. the top-$d$ singular vectors), kernel PCA
also extracts the $d$ features that keep the most variance (i.e. the top-$d$
eigenfunctions). This is also closely related to the ratio trace defined in
Zhai et al. (2024), whose Appendix C showed that lots of existing contrastive
learning methods can be viewed as maximizing the ratio trace, i.e. maximizing
the variance kept. Zhai et al. (2024) also showed that for supervised
pretraining with multi-class classification, we can also define an
“augmentation kernel”, and then $r_{K^{p}}(f)$ is equivalent to the
discriminant function (i.e. the $\eta^{2}$ defined in Section 4.2.1 of Huberty
& Olejnik (2006)).

Moreover, $r_{K^{p}}(f)$ defined for the interpolation Sobolev space
${\mathcal{H}}_{K^{p}}$ is analogous to the Poincaré constant for the Sobolev
space. Specifically, the Poincaré-Wirtinger inequality states that for any
$1\leq p<\infty$ and any bounded connected open set of $C^{1}$ functions
$\Omega$ , there exists a constant $C$ depending on $p$ and $\Omega$ such that
for all $u$ in the Sobolev space $W^{1,p}(\Omega)$, there is
$\|u-\bar{u}\|_{L^{p}(\Omega)}\leq C\|\nabla u\|_{L^{p}(\Omega)}$ where
$\bar{u}=\frac{1}{|\Omega|}\int_{\Omega}u$ is the mean, and the smallest value
of such $C$ is called the Poincaré constant (see Chapter 9.4, Brezis (2011)).
Consider the special case $p=2$, and replace $L^{2}(\Omega)$ with $L^{2}(\mu)$
for a probability measure $d\mu$ such that $d\mu(x)=\exp(-V(x))dx$, where $V$
is called the potential function. Then, with proper boundary conditions, we
can show with integration by parts that $\|\nabla u\|^{2}_{L^{2}(\mu)}=\langle
u,{\mathcal{L}}u\rangle_{L^{2}(\mu)}$, where ${\mathcal{L}}$ is the diffusion
operator defined as ${\mathcal{L}}f=-\Delta f+\nabla V\cdot\nabla f$ for all
$f$. Here, $\Delta=\sum_{j}\frac{\partial^{2}}{\partial x_{j}^{2}}$ is the
Laplace-Beltrami operator. Now, by replacing ${\mathcal{L}}$ with the integral
operator $T_{K^{p}}$, we can see that $C^{2}$ is equivalent to
$\sup_{f}r_{K^{p}}(f)$ for the interpolation Sobolev space
${\mathcal{H}}_{K^{p}}$, which is known to be
$r_{K^{p}}(\psi_{1})=\lambda_{1}$ if $f\in{L^{2}(P_{\mathcal{X}})}$, and
$r_{K^{p}}(\psi_{j})=\lambda_{j}$ if $f$ is orthogonal to
$\psi_{1},\cdots,\psi_{j-1}$ (i.e. ${\mathcal{H}}_{0}$ defined in the proof
above).

###  B.3 Connection Between Transductive and Inductive for Inverse Laplacian

######  Proposition 5.

Let ${\mathcal{X}}={\left\\{x_{1},\cdots,x_{n+m}\right\\}}$, and
${\mathcal{G}}$ be a graph with node set ${\mathcal{X}}$ and edge weights
$w_{ij}$. Define ${\bm{W}},{\bm{D}}\in\mathbb{R}^{(n+m)\times(n+m)}$ as
${\bm{W}}[i,j]=w_{ij}$, and ${\bm{D}}$ be a diagonal matrix such that
${\bm{D}}[i,i]=\sum_{j}w_{ij}$. Suppose ${\bm{W}}$ is p.s.d., and
${\bm{D}}[i,i]>0$ for all $i$. Let
${\bm{L}}:={\bm{I}}_{n+m}-\eta{\bm{D}}^{-1/2}{\bm{W}}{\bm{D}}^{-1/2}$ for a
constant $\eta$. Let ${P_{\mathcal{X}}}$ be a distribution over
${\mathcal{X}}$ such that
$p(x_{i})=\frac{{\bm{D}}[i,i]}{\operatorname{Tr}({\bm{D}})}$. Define a kernel
$K:{\mathcal{X}}\times{\mathcal{X}}\rightarrow\mathbb{R}$ as
$K(x_{i},x_{j})=\operatorname{Tr}({\bm{D}})({\bm{D}}^{-1}{\bm{W}}{\bm{D}}^{-1})[i,j]$.
For any ${\bm{u}}\in\mathbb{R}^{n+m}$ and
${\hat{{\bm{y}}}}={\left({\bm{D}}^{-\frac{1}{2}}{\bm{W}}{\bm{D}}^{-\frac{1}{2}}\right)}^{\frac{1}{2}}{\bm{u}}$,
define $f:{\mathcal{X}}\rightarrow\mathbb{R}$ as:
$[f(x_{1}),\cdots,f(x_{n+m})]=\sqrt{\operatorname{Tr}({\bm{D}})}{\bm{D}}^{-\frac{1}{2}}{\left({\bm{D}}^{-\frac{1}{2}}{\bm{W}}{\bm{D}}^{-\frac{1}{2}}\right)}^{\frac{1}{2}}{\hat{{\bm{y}}}}$.
Then, we have

${\hat{{\bm{y}}}}^{\top}{\bm{L}}{\hat{{\bm{y}}}}=\|f\|_{{\mathcal{H}}_{K}}^{2}-\eta\|f\|_{P_{\mathcal{X}}}^{2}=\sum_{i,j}f(x_{i})f(x_{j})K^{-1}(x_{i},x_{j})p(x_{i})p(x_{j})-\eta\sum_{i}f(x_{i})^{2}p(x_{i}).$

###### Proof.

Denote ${\bm{f}}:=[f(x_{1}),\cdots,f(x_{n+m})]$. Let
${\bm{G}}_{K^{-1}}[i,j]=K^{-1}(x_{i},x_{j})$, i.e. ${\bm{G}}_{K^{-1}}$ is the
Gram matrix of $K^{-1}$. Let
${\bm{P}}={\bm{D}}/\operatorname{Tr}({\bm{D}})={\textnormal{diag}}{\left\\{p(x_{1}),\cdots,p(x_{n+m})\right\\}}$.
Then, we have

$\|f\|_{{\mathcal{H}}_{K}}^{2}-\eta\|f\|_{P_{\mathcal{X}}}^{2}={\bm{f}}^{\top}{\bm{P}}{\bm{G}}_{K^{-1}}{\bm{P}}{\bm{f}}-\eta{\bm{f}}^{\top}{\bm{P}}{\bm{f}}.$

Let us first characterize ${\bm{G}}_{K^{-1}}$. For any
$f\in{{\mathcal{H}}_{K}}$, there is

$\displaystyle({\bm{G}}_{K}{\bm{P}}{\bm{G}}_{K^{-1}}{\bm{P}}{\bm{f}})[t]$
$\displaystyle=\sum_{i,j}f(x_{i})K^{-1}(x_{i},x_{j})K(x_{j},x_{t})p(x_{i})p(x_{j})$
$\displaystyle=\sum_{i}f(x_{i})K^{0}(x_{i},x_{t})p(x_{i})=f(x_{t}),$

meaning that ${\bm{G}}_{K}{\bm{P}}{\bm{G}}_{K^{-1}}{\bm{P}}{\bm{f}}={\bm{f}}$.
Moreover, let ${\bm{w}}={\bm{D}}^{\frac{1}{2}}{\bm{u}}$, then
${\bm{f}}=\sqrt{\operatorname{Tr}({\bm{D}})}{\bm{D}}^{-1}{\bm{W}}{\bm{D}}^{-1}{\bm{w}}=\operatorname{Tr}({\bm{D}})^{-\frac{1}{2}}{\bm{G}}_{K}{\bm{w}}$,
so we have

${\bm{f}}^{\top}{\bm{P}}{\bm{G}}_{K^{-1}}{\bm{P}}{\bm{f}}=\operatorname{Tr}({\bm{D}})^{-\frac{1}{2}}{\bm{w}}^{\top}{\bm{G}}_{K}{\bm{P}}{\bm{G}}_{K^{-1}}{\bm{P}}{\bm{f}}=\operatorname{Tr}({\bm{D}})^{-\frac{1}{2}}{\bm{w}}^{\top}{\bm{f}}={\bm{u}}^{\top}{\left({\bm{D}}^{-\frac{1}{2}}{\bm{W}}{\bm{D}}^{-\frac{1}{2}}\right)}^{\frac{1}{2}}{\hat{{\bm{y}}}}=\|{\hat{{\bm{y}}}}\|_{2}^{2}.$

Besides,
${\bm{f}}^{\top}{\bm{P}}{\bm{f}}={\bm{f}}^{\top}{\bm{D}}\operatorname{Tr}({\bm{D}})^{-1}{\bm{f}}={\hat{{\bm{y}}}}^{\top}{\bm{D}}^{-\frac{1}{2}}{\bm{W}}{\bm{D}}^{-\frac{1}{2}}{\hat{{\bm{y}}}}$.
So
$\|f\|_{{\mathcal{H}}_{K}}^{2}-\eta\|f\|_{P_{\mathcal{X}}}^{2}={\hat{{\bm{y}}}}^{\top}{\bm{L}}{\hat{{\bm{y}}}}$.
∎

######  Remark.

The definition of $K$, i.e.
${\bm{G}}_{K}=\operatorname{Tr}({\bm{D}}){\bm{D}}^{-1}{\bm{W}}{\bm{D}}^{-1}$,
has a similar form as the positive-pair kernel in Johnson et al. (2023), Eqn.
(1). The important difference between this and the normalized adjacency matrix
${\bm{D}}^{-\frac{1}{2}}{\bm{W}}{\bm{D}}^{-\frac{1}{2}}$ is that it has
${\bm{D}}^{-1}$ instead of ${\bm{D}}^{-\frac{1}{2}}$. However, the above
result says that using a kernel with Gram matrix
${\bm{D}}^{-1}{\bm{W}}{\bm{D}}^{-1}$ in the inductive setting is equivalent to
using the matrix ${\bm{D}}^{-\frac{1}{2}}{\bm{W}}{\bm{D}}^{-\frac{1}{2}}$ in
the transductive setting. Moreover, this result assumes that
${\hat{{\bm{y}}}}$ belongs to the column space of
${\bm{D}}^{-\frac{1}{2}}{\bm{W}}{\bm{D}}^{-\frac{1}{2}}$ (which is what
${\bm{u}}$ is used for). This is necessary for ${\hat{{\bm{y}}}}$ to be
representable by an $f\in{{\mathcal{H}}_{K}}$; otherwise,
${\hat{{\bm{y}}}}^{\top}{\hat{{\bm{y}}}}$ cannot be expressed by any
$f\in{{\mathcal{H}}_{K}}$.

###  B.4 Proof of Theorem 2

First of all, note that for any
$f=\sum_{i}u_{i}\psi_{i}\in{{\mathcal{H}}_{K}}$ such that
$\|f\|_{{\mathcal{H}}_{K}}\leq T$, there is
$f(x)^{2}={\left(\sum_{i}u_{i}\psi_{i}(x)\right)}^{2}\leq{\left(\sum_{i}\frac{u_{i}^{2}}{\lambda_{i}}\right)}{\left(\sum_{i}\lambda_{i}\psi_{i}(x)^{2}\right)}\leq
T^{2}\kappa^{2}$, i.e. $|f(x)|\leq\kappa T$ for ${P_{\mathcal{X}}}$-almost all
$x$. And for any $f\in{{\mathcal{H}}_{{K_{s}}}}$ such that
$\|f\|_{{\mathcal{H}}_{{K_{s}}}}\leq T$, by Theorem 1 we have
$\|f\|_{{\mathcal{H}}_{K}}\leq\sqrt{M}T$, so there is
$|f(x)|\leq\kappa\sqrt{M}T$ for ${P_{\mathcal{X}}}$-almost all $x$.

The main tool to prove this result is Theorem 3.1 in Fischer & Steinwart
(2020), stated below:

######  Theorem 6 (Theorem 3.1, Fischer & Steinwart (2020)).

Let $P_{{\mathcal{X}}{\mathcal{Y}}},{P_{\mathcal{X}}}$ and the regression
function $f^{*}$ be defined as in Section 2. Let ${{\mathcal{H}}_{K}}$ be a
separable RKHS on ${\mathcal{X}}$ with respect to a measurable and bounded
kernel $K$, and $K(x,x)\leq\kappa^{2}$ for ${P_{\mathcal{X}}}$-almost all $x$.
Define the integral operator
$T_{K}:{L^{2}(P_{\mathcal{X}})}\rightarrow{L^{2}(P_{\mathcal{X}})}$ as
$(T_{K}f)(x)=\int f(x^{\prime})K(x,x^{\prime})dp(x^{\prime})$. Let the
eigenvalues/functions of $T_{K}$ be $\lambda_{i},\psi_{i}$, with
$\lambda_{1}\geq\lambda_{2}\geq\cdots$. Let ${\mathcal{H}}_{K^{p}}$ be defined
as Eqn. 1. Assume that there exists a constant $B_{\infty}>0$ such that
$\|f^{*}\|_{L^{\infty}({P_{\mathcal{X}}})}\leq B_{\infty}$, and the following
four conditions holds:

  * •

Eigenvalue decay (EVD): $\lambda_{i}\leq c_{1}i^{-\frac{1}{p}}$ for some
constant $c_{1}>0$ and $p\in(0,1]$.

  * •

Embedding condition (EMB) for $\alpha\in(0,1]$: The inclusion map
${\mathcal{H}}_{K^{\alpha}}\hookrightarrow L^{\infty}({P_{\mathcal{X}}})$ is
bounded, with $\|{\mathcal{H}}_{K^{\alpha}}\hookrightarrow
L^{\infty}({P_{\mathcal{X}}})\|\leq c_{2}$ for some constant $c_{2}>0$.

  * •

Source condition (SRC) for $\beta\in(0,2]$:
$\|f^{*}\|_{{\mathcal{H}}_{K^{\beta}}}\leq c_{3}$ for some constant $c_{3}>0$.

  * •

Moment condition (MOM): There exist constants $\sigma,L>0$ such that for
${P_{\mathcal{X}}}$-almost all $x\in{\mathcal{X}}$ and all $r\geq 2$,
$\int|y-f^{*}(x)|^{r}p(dy|x)\leq\frac{1}{2}r!\sigma^{2}L^{r-2}$.

Let $\tilde{f}$ be the KRR predictor with $\beta_{n}>0$. Let $\gamma$ be any
constant such that $\gamma\in[0,1]$ and $\gamma<\beta$. If $\beta+p>\alpha$,
and $\beta_{n}=\Theta(n^{-\frac{1}{\beta+p}})$, then there is a constant $A>0$
independent of $n\geq 1$ and $\tau>0$ such that:

${\left\|\tilde{f}-f^{*}\right\|}_{{\mathcal{H}}_{K^{\gamma}}}\leq
2c_{3}^{2}\beta_{n}^{\beta-\gamma}+A\tau^{2}{\left[\frac{{\left(\sigma^{2}\kappa^{2}+c_{2}^{2}c_{3}^{2}\right)}}{n\beta_{n}^{\gamma+p}}+\frac{c_{2}^{2}\max{\left\\{L^{2},{\left(B_{\infty}+c_{2}c_{3}\right)}^{2}\right\\}}}{n^{2}\beta_{n}^{\alpha+\gamma+(\alpha-\beta)_{+}}}\right]}$
(11)

holds for sufficiently large $n$ with ${P_{\mathcal{X}}}^{n}$-probability at
least $1-4e^{-\tau}$.

This exact bound can be derived from the proof in Sections 6.1-6.10 of Fischer
& Steinwart (2020). We apply this result by substituting $K={K_{s}}$,
$\alpha=1$, $\beta=1$, and $\gamma=0$. Note that
$\|f\|_{{\mathcal{H}}_{K^{0}}}=\|f\|_{P_{\mathcal{X}}}$ for
$f\in{\mathcal{H}}_{K^{0}}$, and we have proved that
$\tilde{f}-f^{*}\in{{\mathcal{H}}_{{K_{s}}}}\subset{\mathcal{H}}_{K^{0}}$. For
the four conditions, we have:

  * •

Eigenvalue decay (EVD): This is assumed to be satisfied by condition.

  * •

Embedding condition (EMB) for $\alpha=1$:
$\|{{\mathcal{H}}_{{K_{s}}}}\hookrightarrow
L^{\infty}({P_{\mathcal{X}}})\|\leq c_{2}$ for some constant $c_{2}>0$. This
condition is satisfied with $c_{2}=\kappa\sqrt{M}$, as mentioned at the
beginning of this proof.

  * •

Source condition (SRC) for $\beta=1$: $\|f^{*}\|_{{\mathcal{H}}_{{K_{s}}}}\leq
c_{3}$ for some constant $c_{3}>0$. By Assumption 3, this is satisfied with
$c_{3}=\sqrt{\epsilon}B$.

  * •

Moment condition (MOM): This is assumed to be satisfied by condition.

Finally, we have ${K_{s}}(x,x)\leq M\kappa^{2}$ a.e., and
$B_{\infty}=\kappa\sqrt{M\epsilon}B$, as mentioned at the beginning of this
proof. Thus, applying this result yields the desired bound. ∎

###  B.5 Bounding the Gap Between ${\hat{K}_{s}}$ and ${K_{s}}$

######  Lemma 6.

For any $\delta>0$, the following holds with probability at least $1-\delta$
for all $p\geq 1$:

$\left|\hat{K}^{p}(x,x_{j})-K^{p}(x,x_{j})\right|\leq(p-1)\lambda_{\max}^{p-2}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}$
(12)

for all $x\in{\mathcal{X}},j\in[n+m]$, and
$\lambda_{\max}=\max{\left\\{\lambda_{1},\hat{\lambda}_{1}\right\\}}$, which
implies that

$\left|{\hat{K}_{s}}(x,x_{j})-{K_{s}}(x,x_{j})\right|\leq\left.\nabla_{\lambda}{\left(\frac{s(\lambda)}{\lambda}\right)}\right|_{\lambda=\lambda_{\max}}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}.$
(13)

###### Proof.

For any $x^{\prime}\in{\mathcal{X}}$ and any $p\geq 1$, $K^{p}(x,x^{\prime})$
as a function of $x$ satisfies

${\left\|K^{p}(x,x^{\prime})\right\|}_{{\mathcal{H}}_{K}}^{2}={\left\|\sum_{i}\lambda_{i}^{p}\psi_{i}(x)\psi_{i}(x^{\prime})\right\|}_{{\mathcal{H}}_{K}}^{2}=\sum_{i}\frac{\lambda_{i}^{2p}\psi_{i}(x^{\prime})^{2}}{\lambda_{i}}\leq\lambda_{1}^{2p-2}\kappa^{2}.$

Now, for any ${\bm{u}}\in\mathbb{R}^{n+m}$ such that $\|{\bm{u}}\|_{1}\leq 1$,
consider
$F_{p}(x)={\bm{u}}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p}{\bm{v}}_{K}(x)$.
Since ${\left\langle
K(x_{i},\cdot),K(x_{j},\cdot)\right\rangle}_{{\mathcal{H}}_{K}}=K(x_{i},x_{j})$,
we have
${\left\langle{\bm{v}}_{K},{\bm{v}}_{K}\right\rangle}_{{\mathcal{H}}_{K}}={\bm{G}}_{K}$,
which implies that

$\|F_{p}\|_{{\mathcal{H}}_{K}}^{2}={\left\langle{\bm{u}}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p}{\bm{v}}_{K},{\bm{u}}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p}{\bm{v}}_{K}\right\rangle}_{{\mathcal{H}}_{K}}={\bm{u}}^{\top}\frac{{\bm{G}}_{K}^{2p+1}}{(n+m)^{2p}}{\bm{u}}.$

We now provide a bound for $\|F_{p}\|_{{\mathcal{H}}_{K}}$, which uses the
following exercise from linear algebra:

######  Proposition 7.

For any p.s.d. matrices ${\bm{A}},{\bm{B}}\in\mathbb{R}^{d\times d}$, there is
$\operatorname{Tr}({\bm{A}}{\bm{B}})\leq\|{\bm{A}}\|_{2}\operatorname{Tr}({\bm{B}})$.***An
elementary proof can be found at
https://math.stackexchange.com/questions/2241879/reference-for-trace-norm-
inequality.

Since ${\bm{G}}_{K}$ is p.s.d., we can define ${\bm{G}}_{K}^{1/2}$. Then,
using the above exercise, we have

$\displaystyle{\bm{u}}^{\top}\frac{{\bm{G}}_{K}^{2p+1}}{(n+m)^{2p}}{\bm{u}}$
$\displaystyle=\operatorname{Tr}{\left({\bm{u}}^{\top}{\bm{G}}_{K}^{1/2}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{2p}{\bm{G}}_{K}^{1/2}{\bm{u}}\right)}$
$\displaystyle=\operatorname{Tr}{\left({\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{2p}{\bm{G}}_{K}^{1/2}{\bm{u}}{\bm{u}}^{\top}{\bm{G}}_{K}^{1/2}\right)}\leq\hat{\lambda}_{1}^{2p}\operatorname{Tr}{\left({\bm{G}}_{K}^{1/2}{\bm{u}}{\bm{u}}^{\top}{\bm{G}}_{K}^{1/2}\right)}.$

And
$\operatorname{Tr}{\left({\bm{G}}_{K}^{1/2}{\bm{u}}{\bm{u}}^{\top}{\bm{G}}_{K}^{1/2}\right)}={\bm{u}}^{\top}{\bm{G}}_{K}{\bm{u}}=\sum_{i,j=1}^{n+m}u_{i}u_{j}K(x_{i},x_{j})\leq\sum_{i,j=1}^{n+m}|u_{i}u_{j}K(x_{i},x_{j})|\leq\kappa^{2}\|{\bm{u}}\|_{1}^{2}\leq\kappa^{2}$.
Thus, we have $\|F_{p}\|_{{\mathcal{H}}_{K}}\leq\hat{\lambda}_{1}^{p}\kappa$
for all $p\geq 0$.

Define
${\mathcal{F}}:={\left\\{f=g_{1}g_{2}\;\middle|\;g_{1},g_{2}\in{{\mathcal{H}}_{K}},\|g_{1}\|_{{\mathcal{H}}_{K}},\|g_{2}\|_{{\mathcal{H}}_{K}}\leq
1\right\\}}$. Then, as we proved in the proof of Theorem 2,
$\|g_{1}\|_{\infty}\leq\kappa$ and $\|g_{2}\|_{\infty}\leq\kappa$, which means
that for all $f\in{\mathcal{F}}$, $\|f\|_{\infty}\leq\kappa^{2}$. Moreover, by
Proposition 13 of Zhai et al. (2024), we have
$\mathfrak{R}_{n}({\mathcal{F}})\leq\frac{\kappa^{2}}{\sqrt{n}}$, where
$\mathfrak{R}_{n}$ is the Rademacher complexity. Thus, by Theorem 4.10 of
Wainwright (2019), for any $\delta>0$,

$\left|\frac{1}{n+m}\sum_{i=1}^{n+m}f(x_{i})-\mathbb{E}_{X\sim{P_{\mathcal{X}}}}[f(X)]\right|\leq\frac{\kappa^{2}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}\qquad\text{for
all }f\in{\mathcal{F}}$ (14)

holds with probability at least $1-\delta$. In what follows, we suppose that
this inequality holds.

For any $p$, define ${\bm{v}}_{K^{p}}(x)\in\mathbb{R}^{n+m}$ as
${\bm{v}}_{K^{p}}(x)[i]=K^{p}(x,x_{i})$ for all $i\in[n+m]$. Then,

$\displaystyle\left|K^{p}(x,x_{j})-\hat{K}^{p}(x,x_{j})\right|$
$\displaystyle=\;$
$\displaystyle\left|K^{p}(x,x_{j})-\frac{1}{(n+m)^{p-1}}{\bm{v}}_{K}(x)^{\top}{\bm{G}}_{K}^{p-2}{\bm{v}}_{K}(x_{j})\right|$
$\displaystyle\leq\;$
$\displaystyle\left|K^{p}(x,x_{j})-\frac{1}{n+m}{\bm{v}}_{K^{p-1}}(x)^{\top}{\bm{v}}_{K}(x_{j})\right|$
$\displaystyle+\sum_{q=1}^{p-2}\frac{1}{(n+m)^{q}}\left|{\bm{v}}_{K^{p-q}}(x)^{\top}{\bm{G}}_{K}^{q-1}{\bm{v}}_{K}(x_{j})-{\bm{v}}_{K^{p-q-1}}(x)^{\top}\frac{{\bm{G}}_{K}^{q}}{n+m}{\bm{v}}_{K}(x_{j})\right|.$

Let us start with bounding the first term:

$\displaystyle\left|K^{p}(x,x_{j})-\frac{1}{n+m}{\bm{v}}_{K^{p-1}}(x)^{\top}{\bm{v}}_{K}(x_{j})\right|$
$\displaystyle=\;$
$\displaystyle\left|\int_{\mathcal{X}}K^{p-1}(x,z)K(x_{j},z)dp(z)-\frac{1}{n+m}\sum_{i=1}^{n+m}K^{p-1}(x,x_{i})K(x_{j},x_{i})\right|$
$\displaystyle\leq\;$
$\displaystyle\lambda_{1}^{p-2}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)},$

because
${\left\|K^{p-1}(x,\cdot)\right\|}_{{\mathcal{H}}_{K}}\leq\lambda_{1}^{p-2}\kappa$,
and ${\left\|K(x_{j},\cdot)\right\|}_{{\mathcal{H}}_{K}}\leq\kappa$.

For the second term, note that ${\bm{v}}_{K}(x_{j})={\bm{G}}_{K}{\bm{e}}_{j}$,
where ${\bm{e}}_{j}=[0,\cdots,0,1,0,\cdots,0]$. So we have:

$\displaystyle\frac{1}{(n+m)^{q}}\left|{\bm{v}}_{K^{p-q}}(x)^{\top}{\bm{G}}_{K}^{q-1}{\bm{v}}_{K}(x_{j})-\frac{1}{n+m}{\bm{v}}_{K^{p-q-1}}(x)^{\top}{\bm{G}}_{K}^{q}{\bm{v}}_{K}(x_{j})\right|$
$\displaystyle=\;$
$\displaystyle\left|\int_{\mathcal{X}}K^{p-q-1}(x,z){\left[{\bm{e}}_{j}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{q}{\bm{v}}_{K}(z)\right]}dp(z)-\frac{1}{n+m}\sum_{j=1}^{n+m}K^{p-q-1}(x,x_{j}){\left[{\bm{e}}_{j}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{q}{\bm{v}}_{K}(x_{j})\right]}\right|$
$\displaystyle\leq\;$
$\displaystyle\lambda_{1}^{p-q-2}\hat{\lambda}_{1}^{q}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)},$

because
${\left\|K^{p-q-1}(x,\cdot)\right\|}_{{\mathcal{H}}_{K}}\leq\lambda_{1}^{p-q-2}\kappa$,
and
${\left\|{\bm{e}}_{j}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{q}{\bm{v}}_{K}\right\|}_{{\mathcal{H}}_{K}}\leq\hat{\lambda}_{1}^{q}\kappa$
since $\|{\bm{e}}_{j}\|_{1}=1$.

Combining the above two inequalities yields Eqn. 12. Then, note that

$\nabla_{\lambda}{\left(\frac{s(\lambda)}{\lambda}\right)}=\sum_{p=1}^{\infty}\pi_{p}(p-1)\lambda^{p-2},$

which together with $\pi_{p}\geq 0$ for all $p$ yields Eqn. 13. ∎

######  Corollary 8.

If Eqn. 14 holds, then for all $i,j\in[n+m]$, and
$\lambda_{\max}=\max{\left\\{\lambda_{1},\hat{\lambda}_{1}\right\\}}$,

$\displaystyle\left|{K_{s^{2}}}(x_{i},x_{j})-\langle{\hat{K}_{s}}(x_{i},\cdot),{K_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}\right|+\left|\langle{\hat{K}_{s}}(x_{i},\cdot),{\hat{K}_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}-\langle{\hat{K}_{s}}(x_{i},\cdot),{K_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}\right|$
$\displaystyle\leq\;$ $\displaystyle
2s(\lambda_{\max})\left.\nabla_{\lambda}{\left(\frac{s(\lambda)}{\lambda}\right)}\right|_{\lambda=\lambda_{\max}}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}.$

###### Proof.

Consider
$F_{p,q}(x)={\bm{u}}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p}{\bm{v}}_{K^{q}}(x)$
for any $\|{\bm{u}}\|_{1}\leq 1$ and any $p\geq 0,q\geq 1$. If Eqn. 14 holds,
then by 7, we have

$\displaystyle\|F_{p,q}\|_{{\mathcal{H}}_{K}}^{2}$
$\displaystyle={\bm{u}}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p}{\bm{G}}_{K^{2q-1}}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p}{\bm{u}}$
$\displaystyle=\operatorname{Tr}{\left({\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p-1/2}\frac{{\bm{G}}_{K^{2q-1}}}{n+m}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p-1/2}{\bm{G}}_{K}^{1/2}{\bm{u}}{\bm{u}}^{\top}{\bm{G}}_{K}^{1/2}\right)}$
$\displaystyle\leq\hat{\lambda}_{1}^{2p-1}{\left\|\frac{{\bm{G}}_{K^{2q-1}}}{n+m}\right\|}_{2}\operatorname{Tr}{\left({\bm{G}}_{K}^{1/2}{\bm{u}}{\bm{u}}^{\top}{\bm{G}}_{K}^{1/2}\right)}$
$\displaystyle=\hat{\lambda}_{1}^{2p-1}{\left\|\frac{{\bm{G}}_{K^{2q-1}}}{n+m}\right\|}_{2}{\bm{u}}^{\top}{\bm{G}}_{K}{\bm{u}}\leq\hat{\lambda}_{1}^{2p-1}{\left\|\frac{{\bm{G}}_{K^{2q-1}}}{n+m}\right\|}_{2}\kappa^{2}.$

For any unit vector ${\bm{w}}\in\mathbb{R}^{n+m}$, we have

$\hat{\lambda}_{1}\geq{\bm{w}}^{\top}\frac{{\bm{G}}_{K}}{n+m}{\bm{w}}=\frac{1}{n+m}\sum_{i,j=1}^{n+m}w_{i}w_{j}K(x_{i},x_{j})=\frac{1}{n+m}\sum_{t}\lambda_{t}{\bm{w}}^{\top}{\bm{\Psi}}_{t}{\bm{w}},$

where ${\bm{\Psi}}_{t}\in\mathbb{R}^{(n+m)\times(n+m)}$ such that
${\bm{\Psi}}_{t}[i,j]=\psi_{t}(x_{i})\psi_{t}(x_{j})$, so ${\bm{\Psi}}_{t}$ is
p.s.d.. Thus, we have

${\bm{w}}^{\top}\frac{{\bm{G}}_{K^{2q-1}}}{n+m}{\bm{w}}=\frac{1}{n+m}\sum_{t}\lambda_{t}^{2q-1}{\bm{w}}^{\top}{\bm{\Psi}}_{t}{\bm{w}}\leq\lambda_{1}^{2q-2}\frac{1}{n+m}\sum_{t}\lambda_{t}{\bm{w}}^{\top}{\bm{\Psi}}_{t}{\bm{w}}\leq\lambda_{1}^{2q-2}\hat{\lambda}_{1},$

which implies that
${\left\|\frac{{\bm{G}}_{K^{2q-1}}}{n+m}\right\|}_{2}\leq\lambda_{1}^{2q-2}\hat{\lambda}_{1}$.
Thus,
$\|F_{p,q}\|_{{\mathcal{H}}_{K}}^{2}\leq\lambda_{1}^{2q-2}\hat{\lambda}_{1}^{2p}\kappa^{2}$.

Note that
$\langle{\bm{v}}_{K},{\bm{v}}_{K}\rangle_{P_{\mathcal{X}}}={\bm{G}}_{K^{2}}$.
So for any $p,q\geq 1$ and any $i,j\in[n+m]$, there is:

$\displaystyle\left|K^{p+q}(x_{i},x_{j})-{\left\langle\hat{K}^{p}(x_{i},\cdot),K^{q}(x_{j},\cdot)\right\rangle}_{P_{\mathcal{X}}}\right|=\left|{\bm{e}}_{i}^{\top}{\bm{G}}_{K^{p+q}}{\bm{e}}_{j}-{\bm{e}}_{i}^{\top}\frac{{\bm{G}}_{K}^{p-1}}{(n+m)^{p-1}}{\bm{G}}_{K^{q+1}}{\bm{e}}_{j}\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{t=1}^{p-1}\left|{\bm{e}}_{i}^{\top}\frac{{\bm{G}}_{K}^{p-t}}{(n+m)^{p-t}}{\bm{G}}_{K^{q+t}}{\bm{e}}_{j}-{\bm{e}}_{i}^{\top}\frac{{\bm{G}}_{K}^{p-t-1}}{(n+m)^{p-t-1}}{\bm{G}}_{K^{q+t+1}}{\bm{e}}_{j}\right|$
$\displaystyle=\;$
$\displaystyle\sum_{t=1}^{p-1}\left|\frac{1}{n+m}\sum_{l=1}^{n+m}{\left[{\bm{e}}_{i}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p-t-1}{\bm{v}}_{K}\right]}(x_{l}){\left[{\bm{e}}_{j}^{\top}{\bm{v}}_{K^{q+t}}\right]}(x_{l})-{\left\langle{\bm{e}}_{i}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p-t-1}{\bm{v}}_{K},{\bm{e}}_{j}^{\top}{\bm{v}}_{K^{q+t}}\right\rangle}_{P_{\mathcal{X}}}\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{t=1}^{p-1}\lambda_{1}^{q+t-1}\hat{\lambda}_{1}^{p-t-1}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}\leq(p-1)\lambda_{\max}^{p+q-2}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}.$

Thus, we have

$\displaystyle\left|{K_{s^{2}}}(x_{i},x_{j})-\langle{\hat{K}_{s}}(x_{i},\cdot),{K_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}\right|$
$\displaystyle=\sum_{p,q=1}^{\infty}\left|\pi_{p}\pi_{q}{\left(K^{p+q}(x_{i},x_{j})-{\left\langle\hat{K}^{p}(x_{i},\cdot),K^{q}(x_{j},\cdot)\right\rangle}_{P_{\mathcal{X}}}\right)}\right|$
$\displaystyle\leq\sum_{p,q=1}^{\infty}\pi_{p}\pi_{q}(p-1)\lambda_{\max}^{p+q-2}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}.$

Similarly, we can show that:

$\displaystyle\left|{\left\langle\hat{K}^{p}(x_{i},\cdot),\hat{K}^{q}(x_{j},\cdot)\right\rangle}_{P_{\mathcal{X}}}-{\left\langle\hat{K}^{p}(x_{i},\cdot),K^{q}(x_{j},\cdot)\right\rangle}_{P_{\mathcal{X}}}\right|$
$\displaystyle=\;$
$\displaystyle\left|{\bm{e}}_{i}^{\top}\frac{{\bm{G}}_{K}^{p-1}}{(n+m)^{p-1}}{\bm{G}}_{K^{2}}\frac{{\bm{G}}_{K}^{q-1}}{(n+m)^{q-1}}{\bm{e}}_{j}-{\bm{e}}_{i}^{\top}\frac{{\bm{G}}_{K}^{p-1}}{(n+m)^{p-1}}{\bm{G}}_{K^{q+1}}{\bm{e}}_{j}\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{t=1}^{q-1}\left|{\bm{e}}_{i}^{\top}\frac{{\bm{G}}_{K}^{p-1}}{(n+m)^{p-1}}{\bm{G}}_{K^{t+1}}\frac{{\bm{G}}_{K}^{q-t}}{(n+m)^{q-t}}{\bm{e}}_{j}-{\bm{e}}_{i}^{\top}\frac{{\bm{G}}_{K}^{p-1}}{(n+m)^{p-1}}{\bm{G}}_{K^{t+2}}\frac{{\bm{G}}_{K}^{q-t-1}}{(n+m)^{q-t-1}}{\bm{e}}_{j}\right|$
$\displaystyle=\;$
$\displaystyle\sum_{t=1}^{q-1}\left|\frac{1}{n+m}\sum_{l=1}^{n+m}{\left[{\bm{e}}_{i}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p-1}{\bm{v}}_{K^{t+1}}\right]}(x_{l}){\left[{\bm{e}}_{j}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{q-t-1}{\bm{v}}_{K}\right]}(x_{l})\right.$
$\displaystyle\left.-{\left\langle{\bm{e}}_{i}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p-1}{\bm{v}}_{K^{t+1}},{\bm{e}}_{j}^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{q-t-1}{\bm{v}}_{K}\right\rangle}_{P_{\mathcal{X}}}\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{t=1}^{q-1}\lambda_{1}^{t}\hat{\lambda}_{1}^{p+q-t-2}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}\leq(q-1)\lambda_{\max}^{p+q-2}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)},$

which implies that

$\displaystyle\left|\langle{\hat{K}_{s}}(x_{i},\cdot),{\hat{K}_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}-\langle{\hat{K}_{s}}(x_{i},\cdot),{K_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}\right|$
$\displaystyle=\;$
$\displaystyle\sum_{p,q=1}^{\infty}\left|\pi_{p}\pi_{q}{\left({\left\langle\hat{K}^{p}(x_{i},\cdot),\hat{K}^{q}(x_{j},\cdot)\right\rangle}_{P_{\mathcal{X}}}-{\left\langle\hat{K}^{p}(x_{i},\cdot),K^{q}(x_{j},\cdot)\right\rangle}_{P_{\mathcal{X}}}\right)}\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{p,q=1}^{\infty}\pi_{p}\pi_{q}(q-1)\lambda_{\max}^{p+q-2}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}.$

Combining the above inequalities, we obtain

$\displaystyle\left|{K_{s^{2}}}(x_{i},x_{j})-\langle{\hat{K}_{s}}(x_{i},\cdot),{K_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}\right|+\left|\langle{\hat{K}_{s}}(x_{i},\cdot),{\hat{K}_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}-\langle{\hat{K}_{s}}(x_{i},\cdot),{K_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{p,q=1}^{\infty}\pi_{p}\pi_{q}(p+q-2)\lambda_{\max}^{p+q-2}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}$
$\displaystyle=\;$
$\displaystyle\lambda_{\max}\left.\nabla_{\lambda}{\left(\frac{s(\lambda)^{2}}{\lambda^{2}}\right)}\right|_{\lambda=\lambda_{\max}}\frac{\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)},$

so we get the result by expanding the derivative. ∎

###  B.6 Proof of Theorem 3

Define ${\bm{v}}_{{K_{s}},n}(x)\in\mathbb{R}^{n}$ such that
${\bm{v}}_{{K_{s}},n}(x)[i]={K_{s}}(x,x_{i})$. Define
${\bm{v}}_{{\hat{K}_{s}},n}(x)$ similarly. Recall the formulas
$\tilde{f}=\tilde{{\bm{\alpha}}}^{\top}{\bm{v}}_{{K_{s}},n}$ and
$\hat{f}=\hat{{\bm{\alpha}}}^{\top}{\bm{v}}_{{\hat{K}_{s}},n}$. Define
$f^{\dagger}:=\hat{{\bm{\alpha}}}^{\top}{\bm{v}}_{{K_{s}},n}$. Since
${\bm{G}}_{{\hat{K}_{s}},n}$ is p.s.d., we can see that
$\|\hat{{\bm{\alpha}}}\|_{2}\leq\frac{\|{\bm{y}}\|_{2}}{n\beta_{n}}$, and
$\|\hat{{\bm{\alpha}}}\|_{1}\leq\sqrt{n}\|\hat{{\bm{\alpha}}}\|_{2}$. So if
Eqn. 13 in 6 holds, then by 8, we have:

$\displaystyle{\left\|\hat{f}-f^{\dagger}\right\|}_{P_{\mathcal{X}}}^{2}$
$\displaystyle=\hat{{\bm{\alpha}}}^{\top}{\left\langle{\bm{v}}_{{\hat{K}_{s}},n}-{\bm{v}}_{{K_{s}},n},{\bm{v}}_{{\hat{K}_{s}},n}-{\bm{v}}_{{K_{s}},n}\right\rangle}_{P_{\mathcal{X}}}\hat{{\bm{\alpha}}}$
$\displaystyle=\hat{{\bm{\alpha}}}^{\top}{\left(\langle{\hat{K}_{s}}(x_{i},\cdot),{\hat{K}_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}+{K_{s^{2}}}(x_{i},x_{j})-2\langle{\hat{K}_{s}}(x_{i},\cdot),{K_{s}}(x_{j},\cdot)\rangle_{P_{\mathcal{X}}}\right)}\hat{{\bm{\alpha}}}$
$\displaystyle\leq
2s(\lambda_{\max})\left.\nabla_{\lambda}{\left(\frac{s(\lambda)}{\lambda}\right)}\right|_{\lambda=\lambda_{\max}}\frac{\beta_{n}^{-2}\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}\frac{\|{\bm{y}}\|_{2}^{2}}{n}.$

By the definitions of $\tilde{{\bm{\alpha}}}$ and $\hat{{\bm{\alpha}}}$, we
can also see that:

${\left({\bm{G}}_{{K_{s}},n}+n\beta_{n}{\bm{I}}_{n}\right)}{\left(\hat{{\bm{\alpha}}}-\tilde{{\bm{\alpha}}}\right)}={\left({\bm{G}}_{{K_{s}},n}-{\bm{G}}_{{\hat{K}_{s}},n}\right)}\hat{{\bm{\alpha}}}.$
(15)

Note that
${\left\|{\bm{G}}_{{K_{s}},n}-{\bm{G}}_{{\hat{K}_{s}},n}\right\|}_{2}\leq
n{\left\|{\bm{G}}_{{K_{s}},n}-{\bm{G}}_{{\hat{K}_{s}},n}\right\|}_{\max}$.
Thus, by Eqn. 15, we have:

$\displaystyle{\left\|\tilde{f}-f^{\dagger}\right\|}_{{\mathcal{H}}_{{K_{s}}}}^{2}$
$\displaystyle={\left(\hat{{\bm{\alpha}}}-\tilde{{\bm{\alpha}}}\right)}^{\top}{\bm{G}}_{{K_{s}},n}{\left(\hat{{\bm{\alpha}}}-\tilde{{\bm{\alpha}}}\right)}$