Spectrally Transformed Kernel Regression
Authors: Runtian Zhai
Rattana Pukdee
Roger Jin
Maria Florina Balcan
Pradeep Kumar Ravikumar
Venue: ICLR 2024 spotlight (2024)
Keywords: Learning Theory
Unlabeled Data
Kernel Methods
Semi-supervised Learning
Representation Learning
Label Propagation
Primary area: learning theory
TL;DR: STKR leverages unlabeled data by mixing the information from a kernel and data distribution via diffusion. We provide new STKR estimators applicable to the inductive setting, together with statistical guarantees and complexity analysis.

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 ϵ-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.

Published as a conference paper at ICLR 2024
SPECTRALLY TRANSFORMED KERNEL REGRESSION
Runtian Zhai, Rattana Pukdee, Roger Jin, Maria-Florina Balcan, Pradeep Ravikumar Carnegie Mellon University
(rzhai, rpukdee, rrjin, ninamf, pradeeerrrrr @cs. cww. edu
ABSTRACT
Unlabeled data is a key component of modern machine learning. In general, the role of unlabeled data impose a form of smoothness, usually from the similarity information encoded in base kernel, such as the r-neighbor kernel or the adjacency matrix of graph. This work revisits the classical idea of spectrally transformed kernel regression (STKR), and provides 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 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 general transformation function, while prior work is mostly limited to the transductive setting. Third, we derive statistical guarantees for two scenarios: STKR with 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.
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 boost in computational power as well as increasing sizes of datasets. Due to their empirical successes, providing improved theoretical understanding of such representation learning methods has become an important open problem. Towards this, a big advance was made recently by HaoChen al. (2021), who showed that when using 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 other contrastive learning approaches (Johnson et al., 2023; Cabannes et al., 2023), as well as more generally to all augmentation-basse based self-super learning methods (Zhai al., 2024).
high-level summary of this recent line of work is as follows: The self-supervised learning ap- proaches implicitly specify inter-sample similarity encoded via Mercer base kernel. Suppose this kernel has the spectral decomposition K <<x,x')= = Σ Ae (x))e, (x'), where \₃ 2 X2 2 ... 2 0. The above line of work then showed that recent representation learning objectives optimal d features, which are simply the top-d cigenfunctions [v), ... vaal of this base kernel. Given these d features, "linear probe" is learned atop via regression. It can be that this proce- dure is equivalent kernel regression with the truncated kernel =a(z,z')=Ei (x (x'). More generally, one can extend this to regression with a spectrally transformed kernel (STK) K2(x,, x') Ein
learn the
where s [0, +00) - [0,+000 +20) is a general transformation function. We call this generalized method spectrally transformed kernel regression (STKR). Then, Ka amounts to an STK with the "truncation function" s(x.) = (,g(i
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 e-neighbor or the heat kernel (Belkin & Niyogi, 2003). For unlabeled data with clusters, this was the cluster kemne (Chapelle et al., 2002).

---

Published as a conference paper at ICLR 2024
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 eigenfunetions, 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 kernel machines, Bengio al. (2004) linked these approaches 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 principled and general way of using unlabeled data. Unlabeled data is useful as it provides additional information about the data distribution Px, but the kernel could be independent of Px. STKR implicitly mixes the information of Px and the kernel in the process of constructing the STK. We then prove the generality of STKR via an existence result (Theorem I): 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 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 tnite-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 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.z.. an STK K.. 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 2 norm) when s()) is known or completely unknown. By incorporating recent theoretical progress, three of our four bounds have tightness results.
In nutshell, this work conceptually establishes STKR as a general and principled way of learning with labeled and unlabeled data together with 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 X be a compact Hausdorff space, y = E be the label space, and Pxy be the underlying data distribution over X' x y, whose marginal distribution Px is Borel measure with support X'. We will use the shorthand dp(2) ()) to denote d..x(x)). Let I.2 (Px) be the Hilbert space of I functions W.E.t. Px that satisfy J fx))² ddp(x) < +00, with (2) Px = J fi f=))2(=)dp(( and
l|fllex = (f, Px f E (Px)x) also implics f E (Px),, which guarantees that Ex~ [X]] exists and is finite. Let a base kernel K(x,2') encode sample similarity information over X. We assume full access to K (i.e. we can compute K (z, x') for all x x'), and that K satisfies:
(i) K is a Mercer kernel, so it has the spectral decomposition: K(x, x') = Σ Ants where the convergence is absolute and uniform. Here Xi, 1/ are the eigenvalues and orthonormal eigenfunctions of the integral operator Tx: [2x)x) + [Px)x) defined as (f)) = 0. and (vi, v/) Px = δū, = 1(1=})
J [(x') (2,, x' )dp(s'), such that X 2 X2
(ii) K is centered: Defined Tx 1 = O, where (xx 1 and 0(x) 0. One can center any K by K (zo, vn) = K (xo. yo) f K (2,, )o)(p()))) - f K (zo. y)dp(y) + ff K(. v)dp(=)dp(v)
2

---

Published as a conference paper at ICLR 2024
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 fi and f2 equally smooth if they differ by constant a.e.. If K is not centered, then this will not be true under the RKHS norm (see Section 2. 2. 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 norm (see Györfi al. (2002) for an introduction of regression problems):
Problem. Let (xr) == f y.yddPPa (u(x (Pxxx) the targel regression function. Given n labeled samples (11,,11) .... (In, lid. Pxy, m unlabeled samples In-1;'". 3n+m Px, and access to K ((x, x²) for any x, x' E X. find a predictor E (Px()x with low prediction error: :x (f(x)
lid.
= -
where is random noise with zero mean. Let {Aa i E If be the set of non-zero eigenvalues of Tk, then define (= x') ==
One can also think of f* as the target function, and y - (x)
Eier X (z))())) for all p E R. which corresponds to an STK with s(A) X². The set {K*) delineates a diffuusion process w.E. K, because (*+ x') = f KP(x,, vo K (o)d(,))))p(()) so that K captures similarity with one additional hop to K", For continuous diffusion, p can be real-valued. Then, the reproducing kernel Hilbert space (RKHS) associated with K for any 2 1 is:
HKP =
{ Σ VEI
u.Wi
Σ <00
Σ uethe Σ Ui4
Σ
U&u
(1)
X
HxP
and || ()xK. KP is the reproducing kernel of HKP. one can verify for all f E HKr and z that (f, Kg) f(x), for KE(2) := (2(x,2), Hog is also denoted by Hx. Hgr called power spaces (Fischer & Steinwart, 2020) or interpolation Sobolev spaces (Jin et al., 2023).
Kernel ridge regression (KRR) is classical least-squares algorithm. KRR with K is given by:
( E -s) y,)² f
f E arg min JEHK
for some 3n >> O. 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 T1,-.- FT, but not In+1, , In+mm as is explicitly shown by the Representer Theorem (Schölkopf & Smola, 2002, Theorem 4.2): All minimizers of KRR admit the form
(x) = Ej Kx, æz)), where
a" E arg inf QEE"
Σ
Σ
a, ((]K();,))) Vi
+ Bn Σ a:ay K5) iJ=1
(2)
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 unla- beled nodes are useless and can be removed. Then, the graph becomes three isolated nodes, so it has zero impact the learned predictor.
222
ZG
F1
IG
I3ss
2.1 DIFFUSION INDUCED MULTISCALE SMOOTHNESS
Sample graph. Let us use this graph example to motivate STKR. Unlabeled samples are useful as they offer more information about the marginal distribution Px. The problem is that we don't know the connection between K and Px. So while KRR can leverage K, it does not necessarily exploit more information about Px 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 explicitly including another regularizer [[ that reflects the intrinsic structure of Px. For instance, | can be defined with the Belttai operator in manifold learning, or the graph Laplacian for graphs. In comparison, STKR also exploits Px, but in an implicit way-the construction of the STK mixes K with Px. To see this: In our graph example, suppose we were to use the STK K2, i.e. a two-step random walk. Then, (a) the graph would be useful again because the three labeled nodes were connected in K2, and (b) mixed K with Px since K22 is essentially
Figure 1:
3

---

Published as a conference paper at ICLR 2024
integral of K K over Px. 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 Px. 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 metric d(xr, x²) over the input space X, then one can naturally measure the smoothness of by its ((a) So it suffices to specify d(ar, x²). If 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 X' is not necessarily Euclidean in the first place.
Lipschitz constant (fp = x'
d(z,ar)
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 K2 also aligns with similarity. The kernel metric of K" is given by dxr (a, x²) == Kø 1= E, X (1) ()(x))))? which is equivalent to the diffusion distance defined in Coifman & Lafon (2006), and can be real-valued. Thus, kernel diffusion {KP} induces multiscale metric geometry over X, where a larger p induces weaker metric. Here "weaker" means dx= = (dxxc) y > One can also think of {KP) as forming a chain of smooth function classes: (Pxxx) > Hx1 3 HKa 3 ...,, and for continuous diffusion we can also have sets like HgL.. A larger p imposes stronger constraint since HKr is smaller.
Now we show: Il ll is equal to its Lipschitz constant. But this is not true for (f), which is not very tractable under the topological structure of X' Thus, we consider the space of finite signed measures over X, denoted by X. For any function ʃ on X, define its mean ʃ as a linear functional over X, such that [(n) = Jx (x)) Then, define dge u) == II KYu(a) - ʃ (Kg(()))xx ((())=[(v)l In other words, f is smooth if its mean w.r.t j does not change too much when the measure μ over X' changes by a little bit. Then, we have:
for u. E X, and Lip (f) N.PpueEX,,ttt dgr(pp)))
Proposition (Proofs in Appendix B). This LipaRo (f) satisfies: LipaR= (f) 11flllee Vf E HKr-
We define (f= = |l - Ex /fllip// LipaRr (f)² = 11f Ep [fIIBe ll and use to measure the smoothness of any I E (Px) at scale p 2 1. Here || is extended to all f E (Px): If If E HK= such that f Exx [f] Sp (Px-aee), then ||
[| gg If there is no such fp. then |l == +oo. Since K is centered, for any fi and f2 that differ by constant Px-a.e, there is (fi) = (f2)..). This would not be true without the centeredness assumption. We define Txr (f) as a ratio to make it scale-invariant, i.e. I and 2 are equally smooth, for the same purpose of decoupling smoothness and scale. And in Appendix B.2, we will discuss the connection between rx" (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 rf( := ||s - E., [f]] P Halllp//_//ipppp /Liaa, (f') for some metric de over X. Then, we assume all functions with "target smoothness" belong to Hilbert space H4. and x. x'' are similar if all functions in He give them similar predictions, i.e. de (p, v) = sup]]sll,, -1 (ff()) f(v)). We also assume that target smoothness implies hase smoothness, i.e. H. C Hx (this is relaxable).
2.2 TARGET SMOOTIINESS CAN ALWAYS BE OBTAINED FROM STK: SUFFICIENT CONDITION
Let rf) 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. (f) preserves relative smoothness: "V f2 E LPx)),, if (f) Z (f) for all p 2 1, then re(fi) 2 re(f2)", and H. C HK, then re(f) = f Ep, /ifi and H4 must be an RKHS, whose reproducing kernel is an STK that admits the following form:
K,(x,x') = -E s(x:) ()))),(x)bbll (x))b((a))
(3)
for a transformation function 8: : [0, +00) + [0, +o0) that is: (i) monotonically non-decreasing, (ii) s(X) S MD for some constant M > 0. (.i) continuous on [0, +00), and (iv) 8 (0, +00).
The proof is done by sequentially showing that (i) H4 is an RKHS; (ii) Its reproducing kernel is K2(2, z²) := E, (z) with s) 2 82 2 ... 2 0; (iii) s; = O(A); (iv) There exists such a function s()) that interpolates all s,. From now on, we will use Hx, to denote He. This theorem
4

---

Published as a conference paper at ICLR 2024
implies that s\) makes the eigenvalues decay faster than the base kernel, but it does not imply that Kg is a linear combination of {K*) p211. This result naturally leads to KRR with [| Hx. = =I
f arg min Ep IfleR,
7 E (f(x)))v)) + Bulls Ex~Px [f())]] HK,
(4)
which we term spectrally transformed kernel regression (STKR). One could also relax the assumption
Hi C HK by considering Nkr for porp2 2 Po where po < 1. Assuming that 7x is still an RKHS and H4 HKro, one can prove the same result as Theorem 1, with (ii) changed to s(A) - M
Now we develop theory for STKR, and show how exploits the unlabeled data. Here a road map: (a) We first study the easier transform-awar setting in Section 3, where a good s(A) given by an oracle. But even though (() is known, K2 is inaccessible one cannot obtain d/ with finite samples. Unlabeled data becomes useful when one constructs kernel K, to approximate Kg.
(b) In reality, such an oracle need not exist. So in Section 4, we study the harder transform cansform-agnostie setting where we have no knowledge of s()) apart from Theorem We examine two methods:
ii 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. (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 $1,-.. , in kernel PCA.
Notation: For any kernel K, we use GK E ((++m)((*+m)))))) G,,, E Raxn GK.m E IR to respectively denote its Gram matrix on all, labeled and unlabeled samples, Lee. GK[i, = (xt,,
3 TRANSFORM-AWARE STKR WITH KNOWN POLYNOMIAL TRANSFORM
Let the scale of f be measured by B. This section supposes that s(A) is known, and the following: Assumption 1. s(A) = Ep= ApP2 is a polynomial, with up 2
Assumption 2. There exists constant >> 0 such that K(x,2) x) R²² for Px-almost all x.
Assumption 3. Exx = O, and there exist constants B, >> 0 such that: || S B, f* E HK,
and || HK. S <el1st-1?> (i.e. re(s*) 2 -1). ). (cf. the isometry property in Zhai et al. (2024))
Assumption 4. Pxy satisfies the moment condition for a, > 0: Blyy flly-f't (())) S 1 2 T Tr-2 for all r 2 2 and Px-almost all x. (e.g. For y - N(0, this holds with L o.).)
2
Assumption 1 is natural condition for discrete diffusion, such as multi-step random walk graph, and starts from 1 because (0) = O. The assumption R [f*] = 0 in Assumption 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.
We implement inductive STKR by constructing a computable kernel K,(x, x²) to approx- imate the inaccessible K,. For example, if K2 x') (2, x²) = J K K(x, xo) K(x', 2o) ddp(s)). then a Monte-Carla approximation can be done by replacing the integral over To with an average over T1. -n-m. Computing this average leverages the unlabeled data. Specifically, we define:
Method:
E arg
aargmin min fEHR,
(f(x)) vi)² 1.
(5)
UK [x( G 2 uxxxx))
where K,(,,1))=- = Σ T k2 k²= --=K;
K; vo 2, (((xx
(n m)n-1
Here, (x) E Ru=+m such that Ux (x) K(x, xx). i E In + m]. One can compute (2, x') for
any x' with full access to K K(x, x'). Let y [w,,... Mn]] E RD and (x).,(r) E R" be defined
as U (x) [i] = K2( ) for i E [n]. The following closed-form solutions can be derived from the Representer Theorem. While they
not necessarily unique, will use them throughout this work:
f(x)) = UK... Tá,
ā = (G.... nn + n3, In) -1
(6)
f(x)) U URK. (z) à
â (G (R.... + 1,,
(7)
5

---

Published as a conference paper at ICLR 2024
> Results overview: Now, for all and f that satisfy the above assumptions, we bound the prediction enror |lʃ fl The bound has two parts and here is synopsis: In Part (Theorem 2), we assume access to K, 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 K2 to approximate the inaccessible Ks.
Theorem Let M be given by Theorem 1. If eigenvalues of K decay by order p for E (0, i.e. s\a) =(
( for all then under Assumptions 2 and 4, for sequence of [Bm)m21 with 3n On ) there is a constant co > 0 independent of 2 and 2 x-kk 1-''M- such that ;,,,e, x² McB²
|| | soot2 M (EB2 + o²))n ite + max {L²,
1+2p
1+P
holds for all 1 satisfying Assumption 3 and sufficiently large n with probubility at least 1 4E
Remark. The On T+क) 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 22nn 1ip ) And under Assumption
one can always choose p = 1 since i s(A,) I Σ s(2)) I M Xy = M (r(Tk) I MR2. So one statistical benefit of using an appropriate & 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 o, L (B).
}. Then, Theorem 3. Let &n be the largest eigenvalue of Gx, and denote Amax = max
21
w+m under Assumptions I and 2. for any 8 >> O, it holds with probability at least 1
ô that:
f - F S (Ss(Aaax) VA ( (s())
2x
1
|1y112
2 V 2 2
A==mmx vn + m
8
Remark. The key to prove this is to first prove uniform bound for [K xr)) K2 (1, (x,,,,) over all
r and j. With Assumptions 3 and 4, an O + o + I.²) bound for !للl can be easily obtained. If Snn = (n rウv) as in Theorem 2, then with m = w(ntiv) this bound vanishes, so more unlabeled samples than labeled ones are needed. Moreover, Xn is known to be close to λ when + is large: Lemma 2. (Shawe-Taylor et al,, 2005, Theorem 2) For any 8 0, with probability least 6,
x²2
2(n m + 1)
2 + V 19
Vn + m
5
> Implementation: STKR amounts to solving Aå = y for A = GRR... + n, In by Eqn. (7). There are two approaches: (i) Directly computing 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 Aâ = via Richardson iteration. We name it STKR-Prop Prop as it is very similar label propagation (Label-Prop) (Zhou et al., 2003). If s(A) Σimm A and q < oc, and computing K(x, x²) for any x' takes O(1) time, then Algorithm has a time complexity of O(g(n + 2 {()) log _) for achieving error less than e, where À is known upper bound of X (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 (1( time, which is as fast as Label-Prop.
k..
At inference time, one can store v computed in line 4 of Algorithm in the memory. Then for any there is fxx Σm K(2,, 2)U; + ni Σラ= K (Zzz,z)āū 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
For some other transformations, including the inverse Laplacian we are about to discuss, s is complex, but s (A) = = SpAP-r is simple. For this type of s(A), Algorithm is infeasible, but there is a viable method in Algorithm 2: It finds 0 E Rn++m such that Q0 = [áx, 0m.] T and MO G. where +n,3, Q, i, = (1
Q - S (xxx)
1, 1,0, 0) with ones and m zeros, and ÿ [y, 0m, T_ In Appendix C we will derive these formulas step by step. and prove its time complexity to be Ómmxx r (n + m And at inference time, one can
P M := (n+m)
GK
[+m
compute f(x) = (x)
Gx n+m
0 in O( + m) time for any x by storing Gxx 0 in the

---

Published as a conference paper at ICLR 2024
Algorithm 1 STKR-Prop for simple
Algorithm 2 STKR-Prop for simple s
Input: Gk. sA),, 3n. n. 1: Initialize: e 0 IR"
Input: Gk. 8 (A), Bns y. V. c
1: Initialize: 0 < 0 E R"t", ÿ t- (3. 0ml
2: while True do
2: while True do
# Compute u = (G Kmm + nn n(x
# Compute = M6
3: Ô n+m GK Ot, v 0 E IR me
3:
V < E R m
4:
for = -, 2 do v f Cx + TT
4:
for p q 1,
0 do
f-
GK
+ 02 +n,3,
5:
u G Kmn+m,n v + Ti G K n
5:
G
[1 m) 0m
(n+m))
6:
if u y 2 <|yyl 2 then return &
6:
f y. 0 t θ 7
7:
á + ā (u y)
7:
if ||a|| < e|yy 12 then return
memory, where vy is defined as in Eqn. (5). Once again, for a graph with [E] edges, STKR-Prop has a time complexity of Ó(mxx (q. r [5 [8,1), ), which is as fast as Label-Prop. Finally, here we showed the existence of good solver (Richardson), but practitioners could surely use other linear solvers.
4 TRANSFORM-AGNOSTIE INVERSE LAPLACIAN AND KERNEL PCA
We have derived learning guarantees for general inductive STKR when 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 sA)) 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
a regularizer has been widely used in various context (Zhou al., 2003; Johnson & Zhang, 2008; HaoChen et al., 2021; Zhai et al., 2024). For our problem, we want || = f K, ff to be the Laplacian, so the kernel K₂ should be the inverse Laplacian:
Example (Inverse Laplacian for the inductive setting). For nj E (0, ",), define K, such that KJ (2z, x²) K (zz,z') (x, K- and K are STKs with s()) = x and s(\) = 2º Then, S- (A) = = n for X E (0, A1] (s- is the reciprocal, not inverse), s() = Tー = Ep XP. and Il,fl = IIlflP - fll Classical Laplacian has r = and \ 1. For the connection between transductive and inductive versions of Laplacian, see Appendix B.3.
This canonical transformation empirically works well on lots of tasks, and also have this guarantee: Proposition 3. Let be the inverse Laplacian (Example 1). and 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 f given by Eqn. (6), and Theorem 2 holds by replacing e with Me.
Note that this result does not explain why inverse Laplacian is 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 is proved in Theorem must remain unchanged. So one is asked to choose d functions to represent the target function, regardless of the best choice with the lowest worst-case approximation error must be 4'1, .bg
be monotonic, the order of 1h,, 1/2, ...
Proposition 4. Let be any transformation function that satisfies Theorem 1. Let F, be the set of functions that satisfy Assumption 3 for this s. Then, the following holds for all t = [W,, dall
such that Si E (Px),,, as long as s s(x1)e > 1 and a(A1) a(A1)=
a(A211)
111)e--1]-- -]] ::
s(>441)
max min JEF, WERd
Tu +
5 Px
2 s(>1) - s(Aa+1)
(s(A1)e 11B2.
To attain equality, it is sufficient for V to span span (Vi,... , Va). and necessary if s s(aa) s()a+1).
This result motivates using representation learning with two stages: A self-supervised pretraining stage that learns a d-dimensional encoder vi = [W1, Add with the unlabeled samples, and supervised fitting stage that fits a linear probe on v with the labeled samples. The final predictor is fa(x)) = u (z), for which we do not include bias term since f is assumed to be centered.
Method:
For pretraining, the problem boils down to extracting the top-d eigenfunctions of Tw. for which 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 sulf-super pretraining (Johnson et al., 2023). Suppose that GK.m E mm the Gram matrix of K over #n+1: " mn is least rank-d. Then, kernel PCA can be formulated as:
7

---

Published as a conference paper at ICLR 2024
(x(x)) - Σ 1iLi] (In+j;
(8)
1=1
where GK.mu; -mdo; do 2 2.... da vs U. ji,j E [d] (os, vz)
mA.
For any i,j E [d]. there is (wi,, 15) = v. G GK. Uy = dag. Consider running KRR w.r.f. over all w V. For f = i L there is [lfll E (, 55) = || 112 So it amounts to minimize 1 >i (w T (zs) 3² + B,.lkul12 as in ridge regression, which is approximation of STKR with a "truncation function" sA.)) >r if S d. and 0 otherwise (not a real function
Aa = )at1). Denote (xx)), = (.1) ... (xx)) E Rdxn Then, the final predictor is given by:
fa = V i (úXX))
+ +nB.Ia)
1 (X.))y
> Results overview: We now bound the prediction error of fa for all f* satisfying Assumption with no extra knowledge about (A). The bound also has two parts. In Part I (Theorem 4), we bound the estimation error entailed by KRR over Hig given by Eqn. (9), where H.g the RKHS spanned by T = [18 .... Rall which is a subspace of Hx: In Part 2 (Theorem 5), we bound the approximation error, which is the distance from f to this subspace V Note that if v has insufficient representation capacity (e.g. d is small), then the approximation error will not vanish. Specifically, let fa be the Then, Part bounds the KRR estimation error with fa being the target function, and Part bounds Il fall""
projection of I" onto Hip i.e. Sa w V, and (Ja, I fa)
Theorem 4. Let M be given by Theorem 1. Then, under Assumptions and 4, for Eqn. (9) with sequence of B21121 with Bn = O(n T45) ) for any p E (0, 1), and any 8 O and 7 2 k- if 2 (2log3 : tthnn there is constant co >> 0 independent of n. such that:
16x 2 2
2 +
f
Fa
33
||r- Fa
+
dd
5
Px
Px
4
HK
L13g + + x² max {L2, McB2 Jn 149 + + (Ie MeB' + +k2 n
holds for all J* under Assumption 3 and sufficiently large with probability at least 1 4e 8.
Remark. This bound has two terms. The first term bounds the gap between y and new labels ÿ. where Ú: 9: - (I:) + fa(x;). 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), the eigenvalues decay the fastest with being the "truncation function".. But the side effect of this statistical benefit is the first term, as the d-dimensional & has limited capacity. The coefficient& 3 can be arbitrarily close to 1 with larger n, Co- Our astute readers might ask why V 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 V. To apply uniform deviation bounds in Theorem 4, this function class, and therefore V must not see Z1, I, during pretraining. On the contrary, the function class Theorem is HK., which independent of æ1, ... Fy, by definition.
Theorem 5. Let M be given by Theorem Let f Fa bg, where b E R, and g HK such that [gg| He 1 and (g. v.)Nxx for i [d] Then. Ilf fallix xx and
IIf" - Fallztx b² eMAi 3 B² for all f satisfying Assumption 3. (10)
A - ll9 1|x
And if Assumption holds, then for any 5 > 0, it holds with probability at least 5 that:
A441 S llall2x S dat1
x²
2 22v
3 log 6 3
Vm
Remark. When m is sufficiently large, |l can be very close to A Compared to Proposition 4,
one that the bound for I| fall? bllloli?, given by this result is near tight provided
that e(A1) a(Aa11) M: The only difference is that Equ. (10) has eM 1/ instead of eM A₃ 1.
Ay Aest
8

---

Published as a conference paper at ICLR 2024
Table 1: Experiment results. We compare Label-Prop (LP) to STKR-Prop (SP) with inverse Laplacian (Lap). with polynomial s(A) x (poly), with kernel PCA (topd), and with s(A) = À (KRR) (i.e. KRR with base kernel). (1) 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
(1)
SP-Lap
SP-poly (0)
SP-topd (1)
SP-Lap
SP-poly
SP-topd (i)
KRR (i)
Computers
77.30g.05
7.981
76.724.12
80.80a.06
77. 15.152.4
41.91
80 20.80s.28
26. 26.354.34
Cora
73.33g.00
77.04s,74
71.485.80
69.267,52
67.787.62
65. 65.199.11
63.70g.o0
28. 22.52... 56
DBLP
66.44g.78 78
65.425.02 02
64.524,20
64.86,.00 60 65.204.02
64.514.05
63.163.41
44 803,88
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) lIallix dat1 is O(vd) instead of O(d); (ii) It does not require delocalization of the top-d cigenfunctions, thereby removing the dependence on the covariance matrix; (iii) Our bound does not depend on Aa' of Ga.m takes (mm² time in general, though as of today the fastest algorithm takes ((n²)) time with < 2.38 (Demmel et al., 2007), and could be faster if the kernel is sparse.
5 EXPERIMENTS
We implement STKR- Prop (SP) with inverse Laplacian (Lap), polynomial (poly) s(A) = XP, 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()) A). Details and full results are deferred to Appendix D. and here we report a portion of the results in Table I, in which the best and second-best performances for each dataset are marked in red and blue. We make the following observations:
(a) STKR works pretty well with general polynomial (()) 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 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.
(b) STKR with sA) = X2 for > 1 is much better than KRR (i.e.
1). In fact, we observe that for STKR with sA) XP, larger p performs better (see Figure in Appendix D). This suggests one possible reason why inverse Laplacian works so well empirically: It contains KP for p = 1, so it can use multi-step similarity information up to infinitely many steps.
(c) STKR also works pretty well with kernel PCA. Specifically, 3 of the datasets we use, such as Computers, kernel PCA is better than IP and STKR with inverse Laplacian. This shows that inverse Laplacian and kernel PCA are two parallel methods neither 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.
but in some cases computing K K(x, x²) might be slow or impossible. The positive-pait kernel in contrastive learning (Johnson al., 2023) is such example, for which computing K is hard but computing I 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 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 more extensive empirical study on STKR is desired, especially within the context of manifold learning, and modern suleruuee and sumi-super learning.
Limitations and open problems. This work assumes full access to
There are three open problems from this work. (i) Improving the minimax optimal learning rate: In this work, we provided statistical bounds w.r.f. n, m. jointly, but one question we did not answer is: m is sufficiently large, can we improve the minimax optimal learning rate w.r.f. n. proved in prior work on supervised learning? (ii) Distribution shift: Diffusion induces a chain of smooth function classes L² 3 HK 3 Hx² 3 but this chain will collapse if Px changes. Can one learn predictors or encoders that are robust to the shift in ?x? (iii) Combining multiple kernels: In practice, usually the predictor is expected to satisfy multiple constraints. For example, image classifier should be invariant to small rotation, translation, perturbation, etc. When each constraint induces a kernel, how should predictor encoder be learned? We leave these problems future work.

---

Published as a conference paper at ICLR 2024
CODE
The code of Section be found https: researcch htw.aab......a.................. www.ggooooooooocooc.oo 1m80ENF hrt.://www..aaa..aaaSSaaaeerraaa
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 grateful to anonymous ICLR reviewers, with whose help this work has been greatly improved. We acknowledge the support of NSF via IIS-190981. 16, IIS-221 1907, ONR via cooperative agreement HR001 12020003, and Bloomberg Data Science PhD fellowship.
DARPA under
REFERENCES
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6);1333-1366 2003.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, (11), 2006.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In International Conference Machine Learning, pp. 541-549. PMLR, 2018.
Yoshua Bengio, Olivier Delalleau, Nicolas Le Roux, Jean-François Paiement, Pascal Vincent, and Marie Ouimet. Learning eigenfunctions links spectral embedding and kernel pea. Neural compula- fion, 16(10):2177-2219 2004.
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-182 2013.
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.
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.rr net het.ar/wweeeeene///ommoooooo--
Gilles Blanchard, Olivier Bousquet, and Laurent Zwald. Statistical properties of Kernel Prinic- ipal Component Analysis. Machine Learning, 66(2-3):259-294 March 2007, doi: 10.1007/
510994-006-6895-9, URL htLpttp::/ httte::://haa.sciiiiii haaicceehaal0000 ha1-00377800
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. International Conference on Learning Representations, 2018.
Haim Brezis. Functional analysis, Sobolev spaces and partial differential equations. Springer, 2011.
Simon Buchholz. Kernel interpolation in sobolev spaces is not consistent in low dimensions. In Conference Learning Theory, pp. 3410-3440. PMLR, 2022.
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 Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 3252-33222222 3298. PMLR, 23-29 Jul 2023. URL https: : http///poeeenng//e/ee/ee mlr. alr.press/v/le w2lsss/2222220 wwwp/e2eeeee22222232. html.
10

---

Published as a conference paper at ICLR 2024
Olivier Chapelle, Jason Weston, and Bernhard Schölkopf. Cluster kernels for semi-supervised learning. Advances in neural information processing systems, 15, 2002.
Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien. Semi-supervised learning. MIT Press, 2, 2006.
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.
Fan RK Chung. Spectral graph theory, volume 92, American Mathematical Soc., 1997.
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
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 pallern recognition, pp. 113-123, 2019.
Ekin Cubuk, Barret Zoph, Jonathon Shlens, and Quoe Le. Randaugment: Practical automated data augmentation with reduced search space. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pp. 702-703, 2020.
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, 1411111111143 2021.
Maarten de Hoop, Nikola B Kovachki, Nicholas H Nelsen, and Andrew M Staart. Convergence rates for learning linear operators from noisy data. SIAM/ASA Journal Uncertainty Quantification 11(2):480-513, 2023.
James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik, 108(1):59 91, 2007.
Jacob Devlin, Ming-Was 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 I (Long and Short Papers), pp. 4171-4186, Minncapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10.18655/11/1119144477 URL https: //acla //aclanthh ho Logy- org/ N19 9- 1423.
Terrance DrVsies and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv:1708.0455: 2017.
David Elworthy. Does baum welch re-estimation help taggers? CoRR, abs/empp-g/9411001,, 1994. URL pest:://arxe org/ abs/ abs/aabs//a//a /tlg//4100 9410012.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. The Journal of Machine Learning Research, 21(1):8464-855 8501, 2020.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning, Advances neural information processing systems, 32, 2019.
Ian Goodfellow, Mehdi Mirza, Aaron Courville, and Yoshua Bengio. Aulti-prediction deep boltz- mann machines. In C.J. Burges, I. Bottou, M. Welling, Z. Ghahramani, and K.Q. Wein- berger (eds.), Advances Neural Information Processing Systems, volume 26. Curran Asso- ciates, Inc., 2013. URL https: httpp//:////pp.pep/./s/...////ss www.:gsssseuuiiie wwwripsuu....e wctppper__aaieeeeeeee files/ files//aper////// paper/ http://bbbeeeeeeeee htt3://iie/bbbeeee112222222e22e2
László Györfi. Michael Kohler, Adan Krzyzak, and Harro Walk. distribution-fre theory of nonparametric regression, volume 1. Springer, 2002.
11

---

Published as a conference paper at ICLR 2024
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
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.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning graphs. In International conference on machine learning, pp. 4116-4126. PMLR, 2020.
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.
Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. International Conference on Learning Representations, 2019. URL https: /oopenreview.r. www.aaaiieee.nettooome....ee... forummiddBBi133 30CcKX.
Devon Hjelm, Alex Fedorov, Samuel
Carl Huberty and Stephen Olejnik. Applied MANOVA and discriminant analysis. John Wiley & Sons, 2006.
Jikai Jin, Yiping Lu, Jose Blanchet, and Lexing Ying. Minimax optimal kemnel operator learning via multilevel training. The Eleventh International Conference on Learning Representations, 2023. URL httpt::t///// /ttps/////ppeeeeeeeeeeem
net. forum? iidiiddlliiiii Eha-nEEIBBB.a....
Daniel D. Johnson, Ayoub Hanchi, and Chris Maddison. Contrastive learning can find an optimal basis for approximately view-invariant functions. In The Eleventh International Confer- ence on Learning Representations, 2023. URL https:ttp//cccc.tt.. https///ppeeeeieeeeeeeee / net forum? iid=
AjCOKB iMMu.
Rie Johnson and Tong Zhang. Graph-based semi-supervised learning and spectral kernel design. IEEE Transactions on Information Theory, 54(1):275-288 2008
Kwang-Sung Jun, Ashok Cutkosky, and Francesco Orabona. Kernel truncated randomized ridge regression: Optimal rates and low noise acceleration. Advances neural information processing systems, 32, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2016.
Risi Imre Kondor and John Lafferty. Diffussonn kernels graphs and other discrete structures. In Proceedings of the 19th international conference on machine learning, volume 2002, pp. 315-322, 2002.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning, In International Conference Learning Representations, 2017. URL http:httss//peeeeeeeee http:////pee/evveeeeeee ww..eeeeewwee................... net/ /o//m/rrmmm 1d=BJ6o0fqge.
Dong-Hyun Lee. Pseudo-label: : The simple and efficient semi-supervised learning method for deep neural networks. In ICMI. 2013 Workshop Challenges in Representation Learning, 2013.
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 1443-44452200 2022.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "Ridgeless" regression can gen- eralize. The Annals of Statistics, 48(3):1329 1347, 2020. doi: 10.1214/19-A0S1844) URL https:/ htt.:///oooooo.////////o//////// 12111111// 4/14 4 AOS1849.
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-88) 890, 2020.
12

---

Published as a conference paper at ICLR 2024
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-7145 2021.
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.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: regularization method for supervised and semi-supervised learning. IEEE transactions on pattern analysis and machine intelligence, 197991997, 2018.
Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Dietterich, S. Becker, and Z. Ghahramani (evvancee in Neural Information Processing Sys- tems, volume 14. MIT Press, 2001. URL httpps::/ppccceednngg
nwwrips. wttpppss.ccppaaaeeee ccpppper__.........pppppppe..... wwwee////ee/////////////eeeeeeee http://220.2.oooo//////eeeeeeee1 Papeeeeeeeeepeppppppee.eee--eeee .df.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprinl
2018.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking Bringing order the web. In The Web Conference, 1999. URL https://api.
semanti iestanttischolatt org/
Saag//oorpie CCrpporrrpp : 1508503.
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-24666 2020.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Alexander Rakhlin and Xiyu Zhai. Consistency of interpolation with laplace kernels is high- dimensional phenomenon. In Conference on Learning Theory, pp. 2595-2623. PMLR, 2019.
Marc' Aurelio Ranzato and Martin Szummer. Semi-supervised learning compact document representations with deep networks. In Proceedings of the 25th international conference
Machine learning, pp. 792-799, 2008.
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.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 29005500)):23332232,, 2000.
Bernhard Schölkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
John Shawe- Shawe-Taylor, Christopher KI Williams, Nello Cristianini, and Jaz Kandola. On the eigen- spectrum of the gram matrix and the generalization error of kernel-pea. IEEE Transactions on Information Theory, 51(7):2510-252 2005.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop NeurIPS. 2018.
Mingguang Shi and Bing Zhang. Semi-supervised learning improves gene expression-based predic- tion of cancer recurrence. Bioinformatics, 27(21):001733223, 2011.
Aman Sinha and John C Duchi. Learning kernels with random features. Advances in neural information processing systems, 29, 2016.
Alexander 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.
13

---

Published as a conference paper at ICLR 2024
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Do- gus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi sumi-supe learning with consistency and confidence. Advances in neural information processing systems, 33:596-608, 2020.
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science Business Media, 2008.
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.
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.
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.
Joshua B Tenenbaum, Vin de Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500) 2323, 2000.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge university press, 2019.
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.
Qizhe Xie. Minh- Thang Luong, Eduard Hovy, and Quoe 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.
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.
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: http///ppeeeeeeeeeeeeeeeeeeeeeee ew.
net/ / forum? i idd Ax2yyhCCrr..
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017. URL https: http///pppeee.e.eeee//e/ee nww.eeiwwwweeeeeeeeeeeeeeeeeeeee
Fid= 8gdx9xx.
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:
// ///p//neevii..neeeeeeee net forum?id-r1Dee
Rb.
Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances neural information processing systems, 16, 2003.
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propaga- tion. In CMU CALD tech report CMU-CALD-02-100; 2002.
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.
14

---

Published as a conference paper at ICLR 2024
APPENDIX
Table 2: Table of notations.
Notation
Description
Kronecker delta. Equal to I if j, and 0 otherwise Input space, assumed to be compact Hausdorff space Label space, assumed to be IR
X'
Y
Pxy
Underlying data distribution over X' }
Px, Py
Marginal distributions of Pxy
dp(x)
A shorthand of (1)
n,
Numbers of labeled and unlabeled i..d. samples from Pxy and Px, respectively
$1.-.
mm+m
21, .... In are the labeled samples, and Tn+1,' Inn+m are unlabeled
The observed labels. Also define y = [M,,-.. Nyx] E 12
LP(xx)
2 function space w.r.f. Px, with inner product (-, P) and norm || Ipx
K(t,x')
A Mercer base kernel that encodes inter-sample similarity information
GK
(n + m) x (n + m) Gram matrix over all samples. Gx(i,j] K K(x,, zy)
GK
n X Gram matrix over the n labeled samples
Gkm
m. X m Gram matrix over the m unlabeled samples
Tk
An integral operator w.E.. K. (Tk (z) = J f(z') x' dp((z)
(As, W/s
Eigenvalue and eigenfunction of Tx such that Tx = Xath. X1 A2 ...
The set fi E N: X; > 0}
K,(xxx)
A spectrally transformed kernel of K, whose formula is given by Eqn. (3)
s(A)
The transformation function K2 (x x²)
M.
s() < .M À as proved in Theorem 1. Frequently used in other theorems
K²(Z,²))
Equivalent to (2, æ²) with s(A = XP, for all E R
HK
The RKHS associated with (2(x,, x²) when p 2 1. Hg is also denoted by Hx
HK,
The RKHS associated with K K, that encodes target smoothness
dge
The kernel metric of K", defined as dgr(x,x')
E; (xbx((ar) vhy (xx))
Lipaga (f)
The Lipschitz constant of w.E.. metric dır over X defined in Section 2.1
TR*())
Defined || F [/ Lipdge (f)2, similar the discriminant function
re()
Defined | Px [fllfyy /iip,, (f) de is defined in Section 2.1
f
Regression function defined as f(( := f'y dPxy L (Pxx
f
A predictor that approximates ft. For STKR, its formula given by Eqn. (4)
B
The scale of f*, defined as || - B
The coefficient of K2 when is assumed to be polynomial in Assumption
The upper bound of K K(x,, x) for Px-a.e. E X. See Assumption 2
I' is assumed to satisfy ra (f*) -1 in Assumption
L
Used in the moment condition in Assumption 4
Bn
The regularization coefficient in KRR and STKR. Can change with n
R,
A computable kernel used to approximate K,, defined in Eqn. (5)
(k(z)
An "=++ vector. An important component of K2 defined after Eqn. (5)
A predictor defined in Eqn. (6) that is inaccessible, but important in our analysis
ā,
Defined in Eqns. (6) and (7)
The largest eigenvalue of GK
7
The "step size" in STKR-Prop implemented with Richardson iteration
A hyperparameter of inverse Laplacian, which defined with s -A) -
A pretrained d-dimennional representation [,,,... vd) in representation learning
A linear probe on top of & trained during downstream, and fa(x) = u Tx()
Hig
A d-dimensional RKHS spanned by V, and it a subspace of 7 HK
fa
Projection of f onto H.g
15

---

Published as a conference paper at ICLR 2024
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: mnelidean-based consistency, prediction-base consistency and similarity- amileaity-bbseed consistency.
Euclidean consistency supposes X' to be an Euclidean space, and relies on the assumption that x, have the same label with high probability if they are close the Euclidean distance, which is the foundation of many classical methods including nearest neighbor, clustering and RBF kernels. In the context of semi- ceni-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 basded consistency, which assumes that for two samples (211, y1) and (I22, 12) and any O (0, 1), the label of Ozr, + (1 0)æ² should be close to fy: + (1 0)y2. 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 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 model only on the labeled samples, then uses label the unlabeled samples, and finally trains a second label on all samples. There are a large number of variants of pseudo laheling, 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% 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), MeMc (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 (De & 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 leam 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 consistency be roughly classified into Fuclidean-
16

---

Published as a conference paper at ICLR 2024
based 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 eigemmaps (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-basser consistency is the basis of most deep representation learning algorithms. In fact, Euclidean-basse baaed consistency can be viewed as special case of similarity- consistency, which assumes near samples under the Euclidean distance to be similar. The most obvious similarity-be method is contrastive learning (Oord et al., 2018; Hjelm et al., 2019; Chen et al., 2020), which requires the model to assign similar representations 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-baxee
limeniiaianii target function g(x), then by defining kernel Kg K2,2, x²) == (0(x), (xx)), the task can also be seen as approximating Kg. and Kg encodes some kind of inter-sample similarity. For example, even supervised pretraining such as ImageNet pretraining, can be viewed as enforcing similarity-base 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 natural consequence of enforcing class- bassd 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.
consistency. If the auxiliary task is to learn a certain
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) 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-basee methods.
A.2 STATISTICAL LEARNING THEORY ON KERNEL METHODS
Kernel methods have very long history and there is 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 lot in this work: Schölkopf & Smola (2002); Steinwart & Christmann (2008). Also, Chapters 12- 12-14 of Wainwright (2019) can be more helpful and easier 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 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 solved problem. As Jun 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-non 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 survey random features. The high-level idea of random features is the following: One first constructs a class of features (1((x, } parameterized by 0, e.g. Fourier features. Then, randomly sample D features from
17

---

Published as a conference paper at ICLR 2024
this class, and perform KRR 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 (overparameterizeed regime), then the approximation error is small since f* should be well represented by the D features, but the estimattio error is large because more features means more complexity; If D is very small (underparameterizzed 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 {10(z, 0) 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 pre-defined class of random features such that the resulting kernel aligns with the labels.
B PROOFS
B.1 PROOF OF PROPOSITION 1
Proof. First, for all f E HKe, and na, u E & we have
[f()- [-()( = 1/x M(x)du(x) - 1x ((a)duucs)= - =
1 Kzdu(a))
Kīdu(a)
Hxp
S &11f1lH 1/2 Kīdu(x) Kīdu(v)
=11
HKP
which means that Lipáxy (f) S ||f||
Second, {Kg- - KP x' Je,''ex span the entire Hy. because f E Hgr satisfies (S. Kg 1r7-K3 K2, Hgr O for all xx then f = for some c, which means that f = 0 since 0 is the only constant function in Hgr (because K is centered). Thus, any f HKP can be written as == [f (Kg K2 dd x') for some finite signed measure & over X x X, and thus f = Kgdu(x)) Sx Kgdv(x), where y. v are the marginal measures of Ş. By using such defined [4, v in the above formula, we can see that Lipage (f) I
B.2 PROOF OF THEOREM 1
First, we show that H4 must be an RKHS. Since the is the top-1 eigenfunction of KP for all p 2 1, we
have TKe (1/1) 2 TK*(f) (f) for all f E Hk, which implies that re(1)) 2 rt(f) for all f E He C Hk.
Let Co : 1e(1)). Then, for all f E H4, since must be centered, we have || lifl Co Lip (f)
Let f = f/ ll, then:
inf 1f(x) f(x')
1| S V
sup xx aattaa
I1 [f((x) - fi(x')
[f()) - f(x') x ff(x) - f(x')
S V sup
= Voll//l
This implies that 11, is stronger than ||. 1|px- Thus, if there is sequence of points (x;) such that I; + w.E.. || I.. then (a) x E Hi because H4 is a Hilbert space, and (b) 2; - 2 w.r.f. || Ilp.- Meanwhile, we know that || is stronger than || |pxx 80 I; + I w.F.t.
|| also implies
It; + w.rkt || ||xx:
Now, consider the inclusion map T: 74 -> HK, such that Ta = x. For any sequence {ar}} C He such that x; + w.t. ||- |I, and Iz; y w.r.t ||- -l have 2; - w.r.t. 11 and x; + w.t. || | Thus, we must have y = x = 1x, meaning that the graph of is closed. So the closed graph theorem says that I must be bounded operator, meaning that there exists constant C 0 such that || I ClIfflx for all f E 74. (For an introduction the closed graph theorem, see Chapter 2 of Brezis (2011).)
For all f E HK. let 6n + f(x) be the evaluation functional at point x. Since Hx is an RKHS, for any X, oz is bounded functional on H K, which means that there exists constant
18

---

Published as a conference paper at ICLR 2024
Mr > 0 such that [f(x) < Mellflbue for all f E Hg. So for any f Hi Hx, there is [f(x)) & Mfllfllng
ff which means that 6₂ is also a bounded functional on H4. Thus, H4 must be an RKHS. Let K₂ be the reproducing kernel of H4. From now on, we will use Hk, to denote Hy- Now that Hx, is an RKHS, we can use the proof of Proposition I to show that Lipa, = ll, which implies that rf( = flf - Ep, /11ff
Second, we prove by induction that 1/1- ... , Ma are the top-d eigenfunctions of Ks, and they are pairwise orthogonal w.E.t. HK. When d = 1, 1/1 is the top-1 eigenfunction of KP for all p 2 so 4/1 E arg max (ErP((() TKp (f). By the relative smoothness preserving assumption, this implies that 2/1 E arg max (EL(((() (f)).. Therefore, 2/1 must be the top- eigenfunction of Kg. Now for d 2 2, suppose $1.... tha-1 are the top-(d - 1) eigenfunctions of K, with eigenvalues $1,".. .8-11 and they are pairwise orthogonal w.r.t. Hk. Let Ho = {f : (f, 1s) (s) Px = O. Vi E [d- 1]]- Obviously, Ho n Hgr is closed subspace of Hgr for all 2 1. And for any f E Ho n HK, and any i E [d 11, we have (S, th. S [K, 1/s) closed subspace of Hx,- Applying the assumption with this Ho. we can see that vha is the top- d cigenfinnctio of Kg, and is orthogonal to $1.-.. .0-1 w.r.f both Hk, Thus, our proof by induction. And if da = Adt1, then we can show that both 1n . tha and 1/,.... , Vdd-1, P4+1 are the top-d cigenfunctions of K,, meaning that Sa s4+1. Thus, K2 can be written as (2, x') = E; (:tha()))) where 81 2 82 2 ... 2 0, and 8; = 8;+1 if X = A141- Moreover, by Hk, C Hx, it is obviously true that X;
ʃ [' v/: = O. so Hx, n H is
Pd-1
complete
implies s; = 0.
Third, we prove by contradiction that s; S MA; for all i. this statement is false, then obviously
one can find l < 1/2 < ... such that St, 2 i Xe, for all i. Consider f = Σ. 11, for which ||51 = Σ, i = +00. Since Hk. C Mxx this implies that I = +00, so we have de
+00 = -E Aeg E-9.
I E. PA1, = E. < +00, which gives a contradiction and proves the claim.
Fourth, we find function sA) that satisfies the conditions in the theorem to interpolate those points. Before interpolation, we first point out that we can WLOG assume that X; < 22 for all i: If there is an i that does not satisfy this condition, we simply insert some new X's between A; and A4+1, whose corresponding s's are the linear interpolations between 8; and 81+1, so that 8; S MA, still holds. With this assumption, it suffices to construct a series of bump functions [fi] where fi if X; A;-1; otherwise, (A) 8; 8i+1 for À 2 X; and f((A) = 0 for X E A1t1- Such bump functions are C and monotonically non-decreasing. Then, define s(A) = f(A) for O. and s() O. This sum of bump functions converges every on (0, +00), since it is finite sum locally everywhere. Clearly this is monotonic, interpolates all the points, continuous on [0, +00) and C on (00). And for all that is not A; for instance À E (A++1, there is s(A) S s(x)) S MA S 2M S 2M Thus, s()) = O()) for A E t00).
Remark. In general, we cannot guarantee that s(A) is differentiable at À = 0. Here is counterex- ample: A = 3- and 5; = 3- if i is odd and 2- 3- if is even. Were s(A) to be differentiable at X = 0, its derivative would be 1 and also would be 2, which leads to contradiction. Nevertheless, if the target smoothness is strictly stronger than base smoothness, i.e. Lipay (f) = oLipa, (f)), then s can be differentiable at x 0 but still not C
Link with discriminant analysis and the Poincaré constant. First, we point out the connection between T (f=(f) and the discriminant function in discriminant analysis (see Chapters 3-4 of Huberty & Olejnik (2006)). We can see that Tk=(f is defined as the proportion of variance of f w.r.t. (2x))) and w.r.t. Hg, essentially Tx* (f) measures how much variance of f is kept by the inclusion map MxT + (Pxx) 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 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 TKe (f) is equivalent to the discriminant function (i.e. the r7² defined in Section 4.2.1 of Huberty & Olejnik (2006)).
Moreover, Txp (f) defined for the interpolation Sobolev space HKr is analogous to the Poincaré constant for the Sobolev space. Specifically, the Poincaré- Poincaré-Wirtinger inequality states that for any
19

---

Published as a conference paper at ICLR 2024
1 p oo and any bounded connected open set of C' functions Q there exists a constant C depending on p and such that for all u in the Sobolev space Wl))( there is ||u - ü| (.(()) S
C'IVull where ū = [o] Sor u is the mean, and the smallest value of such C' is called the Poincaré
I
constant (see Chapter 9.4, Brezis (2011)). Consider the special case p = 2. and replace (22 with (u) for probability measure du such that du(x))
where V is called the potential function. Then, with proper boundary conditions, we can show with integration by parts that [V = (u, L(()), where C is the diffusion operator defined as Lf = - + VV Vf
for all f. Here, A Ei 82 is the Saplace-Beltrami operator. Now, by replacing L with the integral Buy
operator TKp, we can see that C2 is equivalent to sup, Tx= (f) for the interpolation Sobolev space HKP, which is known to be TKp (1/1 = A if f E (Pxx). and TkP = ' if f is orthogonal to "', 11y-1 (Lee Ho defined in the proof above).
B.3 CONNECTION BETWEEN TRANSDUCTIVE AND INDUCTIVE FOR INVERSE LAPLACIAN
Proposition 5. Let == (I1,-.. In+m J. and G be graph with node set X and edge weights Wsj- [[i Waj. and D be a diagonal matrix such that D [i,
Define W, W,D D E [R(++m)x(++m)) E, Wig. Suppose W is p.s.d. and Diū, 0 for all i. Let L := Ia+m 1/D-1/2 D 11/2 for
Dia. constant n, Let Px be a distribution over X such that p(a;)) "T(D)' Define kernel K X X
(D WD $ }
R as (,), = Tr(D)(D WD [..g). For any B and ÿ
-eaail/VTrrrrrr (T(D)D 1 D WWD 1) ÿ. Then, we have
define f x + as: [f(1), ... f((n+m)] =
ÿ Lý |1fl mllA11px
n Σ (xx))p((....
Proof. Denote f= [fx)), ... . ( ). Let Gx- = K (x,, Le. Gk- is the Gram matrix of K-1, Let P D/ Tr(D) (pag()())); ... [[(n+t))]. Then, we have
1l - nl1.11ip. f PG nf Pf.
Let us first characterize GK- 1. For any f E Hk, there is
P is
I(t (11, = f(x)),
meaning that PGxx = f. Moreover, let w D then f -T-DD
Tr(D) W. so we have
s PGK- = Gr.
uu ( WD 1
))
Besides, pf
WWD So |1 - - Lý.
Remark. The definition of K, i.e. GK = T WWD1, 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 D WDD- is that it has D-1 instead of D 4. However, the above result says that using a kernel with Gram matrix D-IDD- in the inductive setting is equivalent to using the matrix à WDD D- 3 in the transductive setting. Moreover, this result assumes that ý belongs to the column space of D W (which what u is used for). This is necessary for ÿ to be representable by an f E Hx: otherwise, ÿ cannot be expressed by any f E Hk.
20

---

Published as a conference paper at ICLR 2024
B.4 PROOF OF THEOREM 2
First of all, note that for any f E,uri uabr E Hx such that || 3 T, there is f(x)² C Cc)x < (2x Axss (1)) < T i.e. [f(x)) S KT for Px-almost all x. And for any f HK. such that lll I T, by Theorem 1 we have || I VMT, so there is [f(z)) & RVMT for Px-almost all æ.
The main tool prove this result is Theorem 3.1 in Fischer & Steinwart (2020), stated below:
Theorem 6 (Theorem 3.1, Fischer & Steinwart (2020)), Let Pxy, Px and the regression function
I be defined as Section Let HK be a sepurable RKHS on X with respect to a measurable and bounded kernel K, and K (x,x) S x² for Px-almost all x. Define the integral operator x' dd'pp") Let the eigenvaluesfinnctonss Let HKr be defined as Eqn. (1). Assume that there exists
Tk: (L((x) + (Px)x) as (x)) = f(') of be Xi, ths with X1 X2 constant B > such that IIf ([==)) S Bso, and the following four conditions holds:
Eigenvalue decay (EVD): X S ciiii for some constant > 0 and E (0,
Embedding condition (EMB) for E (0, 1]: The inclusion map HKa + [xx( is bounded, with [|Hg + 1 (x)]l 02 for some constant 02 > 0.
Source condition (SRC) for 3 E (0, 2]: l Sca for some constant > O.
Moment condition (MOM): There exist constants a, I. O such that for Px-almost all I E X and all 2 2, fly (=))')" p(dy)))(dd))a) S L
Let f be the KRR predictor with 3n O. Let be any constant such that y E [0, 1] and y 3. If 3 + p > a, and Bn = O(n σtr), ), then there a constant A independent of n 2 and > such that:
(02n2+ e3ch))
ci max (1, (Bx + 020g))
|5- MKY
< 20239 + A+
(11)
n,37
n² a
holds for sufficiently large n with Px" "xr-obbbbillity least -e
This exact bound can be derived from the proof in Sections 1--.100 of Fischer & Steinwart (2020). We apply this result by substituting K K a = 11, B 1, and 7 O. Note that || = ||
for f E ko, and have proved that f f Hk, H go. For the four conditions, have:
Eigenvalue decay (EVD): This is assumed to be satisfied by condition.
Embedding condition (EMB) for = 1: |1H,, - x (Px)ll S 02 for some constant 02 > 0. This condition satisfied with 62 = Nv M, as mentioned the beginning this proof.
Source condition (SRC) for 3 = 1: || < for some constant 03 > 0. By
Hx, Assumption 3, this is satisfied with c3 VEB.
Moment condition (MOM): This is assumed to be satisfied by condition.
Finally, we have K.(x, .) < 2 a.e. and Bx: = xV MeB, as mentioned at the beginning of this proof. Thus, applying this result yields the desired bound.
B.5 BOUNDING THE GAP BETWEEN K, AND K.
Lemma 6. For any > O, the following holds with probability at least - 8 for all p 2 1:
4 In m
(T(,, (P(x,2;) < (p-1 1)2p-2
2+ V
2 220g
(12)
21

---

Published as a conference paper at ICLR 2024
for all x E N.j E In + ml. and Amax = max { (21:21) 213. which implies that
Rg(x, ko(o,zz) S Vx (2((0) (((A)) (x()(N)
2 v 22 1
(13)
vn +
8)
A=Ama
Proof. For any x' X and any p 2 1, KP (z, x') as a function of satisfies
2 (h(a'())
Σ (e((())
262
HK
Now, for any u Ru+m such that |/ulli S consider F2(x)
u
(x(x). Since
m+m
(K(,),) )) K( 1) KKir; have (UK, UKtNE = =GK, which implies that
|| = (u [TT
GK ) ok, UT
GK + m
2p+1 (n + m) u.
OK
u
n n m++m)
Hx
We now provide bound for |F which uses the following exercise from linear algebra:
Proposition 7. For any p.s.d. matrices A,B E Idddd there is Tr(AB) S || Tr(B)."
Since GK is p.s.d., we can define Gk2² 1//2 Then, using the above exercise, have
u
2p+1 u Tr u
G
Gk
2p
Gk u
(n + m)
n n m
GK
2p
=Ir
Gk2² wuuuu Gkk?
< 2PP Tr @ uu Gak?
n1 +
And Tr (G uu G./22) T = Gruu = Lig=1 u.ujK(Ii, S
Satm Zij=1 (X;, S
x² =2][u|l] < x². Thus, we have [| S S5 for all 2
Define F = { = 9192 91.92 E HK: Il xx 11 I 1). Then, as we proved in the proof of Theorem 2, || x0
and l|gallo I K, which means that for all f F. II x². Moreover, by Proposition 13 of Zhai et al. (2024), we have (F) I x² where R. is the Rademacher complexity. Thus, by Theorem 4.10 of Wainwright (2019), for any > 0.
R²
1 x for all f e F (14)
f(z.) Ex-Px [f(])
<
2
2 log
n2 +
V
n
holds with probability at least - 8. In what follows, we suppose that this inequality holds. For any p. define Uxz (z) E Rm+m as (x)(1) = K2(x, ..) for all i E [n + m]. Then,
KP (²( - (x)
1
(n + m)p-1 UK (z) (x(x)
(²(
n + Uka 1 (z) T (zz)
p-2
(k (x) T Gk un (22)) (x)-)-1(x) Gk n m
ug (x())))
m)7
"An elementary proof can be found at https: / //tp///ath..// htt////ttttttaeeeatee sttackexchange.com/cuuuu 2241879/referenee for-trace--orm--- now.aneennn-n-nnnnnaaaaaa mequulllty
22

---

Published as a conference paper at ICLR 2024
Let us start with bounding the first term:
1
K (x n+ m UK* [x)
uk vx()))
1/ KP (x- (23, =dd)))
KP 1 (
n
S 11 2P-2 xx
2 v 2 log 5)
Vn
because | (I,, )1 Hx - xpp-2n K. and |K(2, )) Hx S ks.
For the second term, note that uK (1rz) Gkej, where Bj = 10,... 1,,10.,..,,0 So we have:
1
UKz-a (x)
(x((x)) (Iz) (
n m (KO-o- (x) T G uk (2n)
GkuuK
nn + m)
J/8 KP (P-0-1 (x,
" Gk
(x(3))p(2)) dp(z)= 1 n+m
" Gx n2 + m
e n m
Km- (1,-)-((1
m j=1
A²
< A9 9
8 279
2 V 2 log σ
vn +
because || (I,
I11xx
S Ap- ki and [e]
GK ++m
S A9n since ||ey||1 = 1.
OK
Hx
Combining the above two inequalities yields Eqn. (12). Then, note that
s(1)
V
Tp - 1)282
which together with Tp 2 O for all yields Eqn. (13).
Corollary 8. Eqn. (14) holds, then for all j,j E [m + ml, and Amax = max { 21, }1),.
(Ki, - (Ka(at))) ), K.(zg, 1) Px
(K. -), Ko( Mx (Ka((1)) )) Ks Ko(Uj, +)) Px
(A)) X
xa
S 2m(x)) VA
2 +
2
A=mmax Vn + m
Proof. Consider (x)
un
GK m+m
P Uxo(x) (x) for any ||ul/a S 1 and any p 2 0,4 2 1. If
Eqn. (14) holds, then by Proposition 7, we have
GK
GK
|P = TT
Gkar
u
n + m
n m
Gk
p-1/2
Gk2--1
Gk
p-1/2
G1/22 uu G2/2
TTr
n + m
n + m
n m
< 1 33p-1
K2
Tr [G 1/2 K uu T Gx
n + m
1
11
G G
u G < 82p-1
Gk n m 2
2
n + m
1
For any unit vector w E pn+mm we have
Å w
GK w-
m
waw ((,,
Σ mow L,W.
n + m
n + m
n + m
1=
23

---

Published as a conference paper at ICLR 2024
where v E R (((+tm)((=+)) such that [[( (x(()) (22), so v is p.s.d. Thus, we have
w T G
1
2q
Ap 2 w
n m _x Drw A w Ap 20-22 2
1
m
n2
m
which implies that
Gkay-1 n+m
S \
20-2 Ån. Thus, |1 IFx S X1 2 X22
Note that (UK. UK) = Gk.. So for any p. 9 2 1 and any i.j [n + ml. there is:
G
K (21, x3) -
(z
e, G - (n+ + m)p-1 G GRvnee
=
Px
G
GK Gh-t-1
e,
(n m GRvlle - (n m))---i Gx
u+m
GK
8-2-1
Gk
p-1-1
e
T
UK
(zi) uk (2))
e
Uk Ugote
n
n2 + m
11 +
Px
n²
1
x² vn m
(2
1
2 /
2 log
$ (p - 1)
2
22log x
vn m
x
Thus, we have
(,( - (Ko(xx)) Ka(rs P)
Σ
Ta KKtt (zi, (xi))
(R +), K ( :))
Px
p.9=1
x²
Tp 1)
vn + 2 v /210g 8
P.g
Similarly, we can show that:
Rd (Z( (, (zzz (1)))))
- (,, )z Px
Px
Gk1
G9-1
GP-1 K
T
Gk²
(n + mmmmmm--eee Bj
ei (n m)p-I Gkvtie
G
Gk
Gk-1-1
K
GR
Ej e
(n m))-1 GRI12
ej
(n + (m) m)p-1
(n m) g-
(n + m---1-1
n+m
GK
p-1
Gk
9-r-1
e
UKill
(xi)
Gj
OK
(x1)
n m
n + m
n + m
1=1
Gx
p-1
GK
9-t-1
ex+t1ee
OK
n + m
n m
Px
2 12
2 log [
1
S 5(9 - 1)
2 v22
log 3
1
Vn+m m
Vn + m
which implies that
(1, -), (o(aas - (R, )), KK(z):)))P
Σ
To ((P (, R9())))
(K K3 (ET))))) Px
Px
22og 1 8
<
Tp - 1)2pta
2 V
vn m
1
24

---

Published as a conference paper at ICLR 2024
Combining the above inequalities, we obtain
K2 (Zi, mz) (Ka +), (2( Px
(Tx. -) R, Ro Mrx (K, ) Ks (o 1x
x²
Tp (p + 2)
2 V /2log 8
vn + m
P:g=1
{{))2
Amax
V
2 +
2og 5
2
A
Vn + m
A=xmax
so we get the result by expanding the derivative.
B.6 PROOF OF THEOREMS 3
Define UK, (z) I" such that Vk, " (x) (,),, Define &R (x) similarly. Recall the formulas f = à uK and f f= à. Rn.."' Define ft := â UK,.. Since G Rn,n is p.s.d., we can see that ||á||2 S l and ||ál|1 / So if Eqn. (13) in Lemma 6 holds, then by Corollary 8,
nBn
we have:
|
f
â (UR.. vK.m Vk,, vK..n á Px
Px
= a
( (Rasoss) ), R, (o,,, Mex + (xa(Fs. - ((R Ka(1,, Px )
VA s(A)
3-2xx n²
- 2mmxA))
2 V 2 22 x
Vn +
A==maxx
By the definitions of à and &, we can also see that:
(G.., + nB n (á - -a) = (GK.. G Gk,,n) a.
(15)
Note that GK,, G GR.m || sn Gk Sn|Gk,
Gkammlnn Thus, by Eqn. (15), have:
|| - st|
= (Ōx - "]]GK,,n Gk -á)
HK.
(a -à) "GKKn.m GK n3n - aā a)
< ||áll2|| Gk,, - GR.. ||o0/12 + +|10|12 Gk.,n G Gkom!
||
(0(2))
Br2n²
1 |//11
V
X d=xaux Vn + m
2 V 2 22og
8)
And note that we have
|.5 f Px
S s(Aii) 1 ft
S ((Amaxx)
5--1( f Mx.
Thus,
NK.
| Px
52 <2(1 111?
+ +1|5 - 1/112-
< 8s(Amax) VA ((2))
3, 3,22% x /n
1 8
|
2 V 2lo
A=Amac
as desired.
B.7 PROOF OF PROPOSITION
By Assumption there is 1
<e|1f"11>>> Let 8 =
Es u.tr. then this equivalent
uf
Σ s*(s))
<c Σ ut
25

---

Published as a conference paper at ICLR 2024
Let s(A) I- be the inverse Laplacian, then we have
of
S Me Σ u
(A.)
X
('A)
which means that f also satisfies Assumption 3 w.r.t s by replacing e with Mc. All other conditions are the same, so we can continue to apply Theorems 2 and 3.
B.8 PROOF OF PROPOSITION 4
This proof is similar to the proof of Proposition 4 in Zhai et al. (2024).
Since & is at most rank-d, there must be function in span (ya, (1),,-., (e411 that is orthogonal to t.
Thus, we can find two functions f1, f2 E span(V1," "1, vd+11 such that: ll M/ |1 Px 1, fi is orthogonal to L. f2 = u (which means that fi 1 f2), and th E span f2]. Let 1/1 = on fi + 02 and without loss of generality suppose that on1 02 [0, 1). Then, of + o3 1. Let
fo = 02/11 - on f2, then f| = and (Jo; 111 Px = 0. This also implies that (fo, th V1/HK, = 0.
Let , [0, 1] be any value such that 88 + 33 1. Let f B(8 + (2.0)), then [| B. B
And we have || B²
131(1.1111 (1.31/1 1ex + 1132Jo pixx S B²
85
S BB2 as long
((A))
*(Ae41)
as 3 S
a(Ar+)) (( (s(A)) 1]. This means that f E F..
Let F(a1) == 31 +02 = 31 1 + a for E [0,1] 1]. It easy to show that F(ar) ) first increases and then decreases on [0, 1]. so F(an)² 2 min (
min {8P. (2). which
=(he=1) can be s(A.)- (s(Ai)e - 1] given that is at most 1.2 Thus, for this S. we have
w Tú - -1|2 Px = +
s(a+1))
min wERd
B2F(a1) 2 s(\1) - s(Aa+1) [s(Ai]e - 1JB2. + a23iiiillex
if If the equality is attained, then we must have [l = s(A441) -.o s(Aa) > s(Xo+1), then i must span the linear span of -1,-.. .4d.
Finally, prove that fE,, win 120 1 - 11 P2 s(A1)-s(>a--)) [s(X1]e - 1]B² if $
((hay1)
I
spans span (.,,..,, ...
, val. For any f = E, 4:1// E Fs, we have E. uf S Bd, and E;
u²
a(A.)
Σ, u. Let = Ei2041 uf, and b = Σi= u. Then, b B². So we have
u? - Σ uf 2
1
1 1
0 >
s(x))
(A1))
-
E b+
(s(++1) -Epa
(since s is monotonic)
i
s(1)) / (B2
1
a)+ aB)
s(Na-1)
6 =1j
=
s(>1)
B²
66 B2 + ((Na+1)
s(A1)
which implies that min
1 T - $1|
S
s(ha
[s()1)e 11B2.
s(Ai)-s(Dd11))
Px
B.9 PROOF OF THEOREM 4
For any f= u.t// Hk, satisfying Assumption 3, 11 = =E, u²
S E.
s(Mi)/M S cMB²
u²
Define fa as the projection of f onto v w.t.. Hg. Define RKHS H.g := span Sن ... ; 33) as subspace of Hk. then fa E Hgg Let K2 be the reproducing kernel of Hgg Let ÿ (0r, ... -n). where ÿ = fa(xz) + ys - (x,). Then, the KRR of fa with K is given by
fl = T V 10 = (x,,),)( + +nBrIa) - "((X))).
26

---

Published as a conference paper at ICLR 2024
First, we show a lower bound for the eigenvalues of 1/ (Xx,) Similar to Eqn. (14), define F := {f = 9192 91.92 E Hx, 11 Hix.
l1 ll Mxx $ 11. then we have:
x²2
2
f(a:) -xx)) ExxxxI((X)) =
2 +
2 2
for all fEF;
(16)
vni
- Σ -xxxxxx-)((())
R+
2 + V 2 log 2 R²
for all fe F
(17)
vm
8
hold simultaneously with probability at least 1 for any 5 > O. In what follows, we assume them
to hold. Then for all f E F, we have 1/2 Ei= f(z))
1 Li=nti f(xi) S / 4 (A+ 2 log }
For any unit vector E RRd let f ru V. Then, || E 1, f E F. And we have
n+m
Σ = -
|| ... mmdaaju " Σ mdju3 2 mds:
i=n+1
which implies that
n22 (
2 4 2 2 log x
n f(,))²
2 Ao
for all f = u T where R is unit vector.
Vn
Thus, for any unit vector u E Rd, u E xx) 2 ndd - n² v (4+ 2 2
Second, we bound Ilfa- - fill Denote Ay = (f1 - Fa(x))) ... (x - Fa(an)) R".
Note that (1) }HH = La. so we have
[ ( ((x)) + +n (((x)(( - 5)) v
f 12 Hx
Hx
(x,xx,x(X ((x).))( + tn Ld (0x(,,
(X,n)
So it suffices to bound o 1 (X, ||² where Q- = (Xx))
n,3,, La which is equal to
the largest eigenvalue of 1/ (X,)) ) Q (X,), which is further equal to the largest eigenvalue of Q - (Xx) (X,)) by Sylvester's theorem. Let the eigenvalues of V (X,,)((XX (X,,) be μn > 2 Ha 2 O, with corresponding eigenvectors a1 ... ag that form an orthonormal basis of IR For all E [d], if μr = 0, then Q 2 ((x,) T a = 0. meaning that as is also an eigenvector of Q 2 2 J (X,)) T with eigenvalue 0. And if μ4 > 0, then we have
Qa V(X,,,, V (x,) a: + n = (Mt + +BB))a
which implies that Qa = Q(u + nBn) )a; = (m4 + nn = (mrtag,)) (X
X,,, ( a.
n: Hi
Thus, a; an eigenvector of Q 26 X,, (x)) (Xx)) T with eigenvalue (ustmB.)2- This means that 0i an are all eigenvectors of Q V (X,,) (X,)) On the other hand, we have us 2 nds - x2 v 4 + / 2ogg3). and suppose that n is large enough so that pa 2 ndg
2 i.e.
n 2 1 (4 + / 2 log / Then, we have
X3
|
v (X,)
|
max rE[d]
P1 (M:: nB,))²
< max Eld
1
<
2
ndd
Thus,
fa f/
|ل : n
Mx
Au
27

---

Published as a conference paper at ICLR 2024
Third, we bound Il falliyy. Denote Af = [f((11) (m1). fa(en) (=,)) ER. Then, we have
A (x,), T (wi -00 ú (x,)) T (((X + +n (x
Similarly, can show that the cigenvalues of (X,)) T V (X, (Xn)) + +n3rJa)
(Xx) are which are no larger than 1. Thus, | - L And by Equ. (16), we have
|| A
2 n²² ( 2 22log
fallex +I falliex vn S 11f
n
So by Equ. (16), we have
|
R=2
2 8
Ilfa - -ddlle I
+ I1fa- - fall
2ix Vn
2+
2 log
n
2x²
1 1
2 + 12 log
T2.
Xavn n
R²
2
2x²
2 z
<
|11 Fallex + 115- - Sall HK Vn
2 +
V
2 log
+
2 -
2 log
\dv
3
da
2411 115 111"
|1 - Fallex +
fallzek
2
4
4x (4 + 2/ log z xx
where the final step uses
2
Finally, we bound f - Fel using Theorem 6 with K = Kig a = B = 1, and y = 0. Recall the four conditions:
(EVD) satisfied for any p (0, since K has at most d non-zero eigenvalues.
(EMB) is satisfied with e2 since [[ |If lxx for all E H.g.
(SRC) is satisfied with eg = VeMB B since [| < || S VeMB.
(MOM) is satisfied by condition.
And we have Bxc = KVEMB. B. Thus, when -1 holds with probability at least 4T
that
[ fa
142n 0o 72 [ne + + + + n² max {T?,, MMBBB S
T+p
Px
2
Combining the two inequalities with (a + b)2 < 2(a² + b²) yields the result.
B.10 PROOF OF THEOREM 5
We start with the following lemma:
Lemma 9, For any E HK such that ll = 1 and (g, di) for all i E [d], there is
11 112x + +... 11balleex + Ilalle I An + +... ddt1-
(18)
Proof. Let [ū..... Ha o) QD where DA diag(A \ι, )2,-..) and v 12,02,.-0
Is+1, and Then, QQT (1ih: ... Br. g) [ur,... (. Hx
11 +... Ik - 11111i1 = Tr (QD.QT).
So obtain the result by applying Lemma 9 in Zhai al. (2024).
28

---

Published as a conference paper at ICLR 2024
Define Fa Fa:= f Ei= o. 91 E Hk. (gt. (5 = =. We now bound its Rademacher com-
plexity. For any x, denote v(x) - 21/221 1/ (2) (2)) For any { Im denote V ((xx) for [m]. Let gx(x) u (x)), and denote U (u..... ua]. Then, U la-
Let a = -1,, mm be Rademacher variates. Thus, the empirical Rademacher complexity satisfies:
Ng (J))
sup U1.""
Mx VA ui
sup
Tr
U
ON
L V
U
U.U U=
m
sup U:UTU=I:
Tr
1
on
UU
m
Let #1 22 ... be the singular values of E V For any U, the singular values of UUT are d ones and then zeros. So by von Neumann's 's trace inequality, we have:
VR UUT)
S t Vd
sup U=Ia
Tr
Σ
A=1
where the last step is Cauchy- Secchy---chwrzzz incquality applied to the diagonalized matrix. So we have:
Vd E
N² vd
Rs(Fa) <
Σ
almost surely,
Vm
where the last step proved in Proposition 13 of Zhai et al. (2024). Thus, for the Rademacher complexity we have Rm (Fa) = Es(Dis(Fa)
va Moreover, for Px-almost x, we have: vm
d
Σ i = UU (xx S | 12 = (c))l
where the last step is because V (x)))((()) of Wainwright (2019), we have:
E, (x) S R2 for all Hence, by Theorem 4.10
n²2
Σ f(z.) - Ex~ [f(X]] 1n+11
S
2vd / 2
for all f Fa
(19)
mm
holds with probability at least - 8
2. Let F(x) = -i=1 (x)² Then, F E F.. And for all i [d],
Σd
there is [u=((n+1),... -... Pi (xn+m) )1 Gb.m U; = m) so (x((n+1)2 + ... + (xn+m))
m2 X3 1 = md; Thus, 1 Eatt F(x;)) = λι + +... Ad. So Eqn. (19) holds, then
R²
2vd v 2 2oo 2 8
1 + + 11 2 t d
Vm
Since *..... de are the eigenvalues of Gk. by Theorem 3.2 of Blanchard et al. (2007), we have:
x²
Å da A1 Aa
log
5
holds with probability at least
& By union bound, it holds with probability at least ô that
x²
1 + I1aal 2 A1 As
2vd + 3010
vm
Let f fa bg. where b E R. and g E Hk satisfies Ilgll and (g. din = for [d].
Then, by Lemma 9, we have
x²
llll S Ada1 +
2/d 2vd+3/ + 3/ 1ox
Vm
29

---

Published as a conference paper at ICLR 2024
Let Ifall Then, 11 a² + b². Since 11flBi I <MM =M Ilix we have:
a² + b²
+ = 11 - ( bllollex)
)² s 22(a²>1 + (191))))xx)
cM
which implies that
(A1 - 11a1l )b² 1 (21 2cM (a² bo)+ (NCM (MIcM-11 1
2 7
which completes the proof.
C DETAILS OF NUMERICAL IMPLEMENTATIONS
Algorithm 3 Directly solving STKR
Input: (xx,x'), s(A) Eq= Tpd Bus y # mKn.mmn is the left n columns of Gk
1: Initialize: M s- GK,n+m,n R(n+m)xx
2: A n.,, In + +TIKK, E nR
3: for p 2, ,9 do
4: A - A + Tp
G KKntmmn M
5: M n+m
GRM
6: Solve Aá y
STKR amounts to solving Aá = y for A G GR.n nBB First, consider s(A) - AP with q < cc. Provided that computing K(x, x') for any x, x, takes O(1) time, directly computing A and then solving Aâ y described above has a time complexity of (())+)))n)) it performs (g)) matrix multiplications, and a space complexity of O((n + m)n). Calculating directly could be expensive since it may require many matrix matrix multiplications.
Alternativlyy we can use iterative methods, such as Richardson iteration that solves Aå = y with 44+1 &; - r(A, y) for some y > 0, described in Algorithm in the main text. This faster than the direct method since replaces matrix-matrix multiplication with matrix-vector multiplication.
is well-known that with a proper y, it takes (nx(A) log 1) Richardson iterations to ensure ||áq
á. <||6>=122 where &, is the real solution, and s²( (A) is the condition number of A. Let be known upper bound of X (e.g. for augmentation
pretraining, À (Zhai et al., 2024)). With sufficiently large n, we have x(A) = -(3 almost surely, Richardson iteration has total time complexity of O((n + m)² 9, ((Aq log }) and a space complexity of O(n + m). The method can be much faster if K is sparse. For instance, if K is the adjacency matrix of a graph with [E] edges, then each iteration only takes Olg (El) time instead of O(g(n + m)²).
Next, we consider the case where could be complex, but 5 -A) =0 ES Sp SpXP-T as the inverse Laplacian (Example 1). In this case we cannot compute G k,,. but if we define
is simple, such
Q : D Ep h+m " then there is G k. Q = (n +m+m
With this observation, we use an n+m
GK
indirect approach to find à, which to find a E mR=++m such that QO = (áx, 0m)) [T Note that by the
definition of &, the first n elements of (GR, + n1, In [á, _m] = (GR, + n.3,Intm Q0
(nn + m) Gx )" + n,B,, Q 0 is y, which provides linear equations. The last m elements of Qe n+mm are zeros, which gives m linear equations. Combining these two gives an (n + m)ddimnsiional linear system, which we simplify
GK ) + n.B.. and و = [y, 0ml n + m
M0 = ÿ, where M = (n + m)
(20)
Here, i, == diag(1, (1.......... ....... iteration, described in Algorithm 2, with On + m) space complexity. Let uk be defined in
0, ..... 00. with n ones and m zeros. Again, we can find by Richardson
30

---

Published as a conference paper at ICLR 2024
r-1
Eqn. (5). Then, at inference time, one can compute f(x) (x)
Gx n+m
0 in O + m) time
by storing
GK
O in the memory.
n+
We now discuss the time complexity of Algorithm 2. We cannot use the previous argument because X
now M is not symmetrical. Let p(>) = =(A] = Σø=o Sp, where p(0) = So > 0. Then, p(A) is
continuous on [0, +oo). Denote its maximum and minimum on [0, A] by Pmax and Pmin. where again is a known upper bound of A Then, we have the following:
X'mmoalle llvlla Proposition 10. With 7 (nx*)=1, Algorithm 2 takes O N log mmxx (c' " Ja. Bu.Piin iterations that à - elláx112 almost surely for sufficiently large n, where de, is the ground truth solution and Y is the oulput of the algorithm. Each iteration takes ((max (q, (n my time.
1)
Thus, the totll time complexity is O (n m)3 --1 max {g.r)x log (max 1. N Pmee 119/2
3-=
m.3 la.
Proof. Let d1 ... ...22...1 2m+m be the eigenvalues of GK. It is easy to show that Q has the same n+m eigenvectors as Gx with eigenvalues g(Az).- 9(22). By Lemma and Borel-Cantelli lemma, as n + oc, Å₁ 4s, \1. For simplicity, let us assume that À is slightly larger than Y₁ so almost surely there is a S A. Then, all eigenvalues of Q are in ipmin pmax].
The first part of this proof is to bound ||uell2- where u. == (n + (m++)ii, the & at iteration and 0, be the solution to Eqn. (20). Since 8, 0, we have
Gk
(0, -,). Let O, be
ntm
GK
0. - 02
I Intm - (n m)
mi)
+ + Q
0. + 77
n2 + m
[( [Iutm - (n mm),
GK
r
+ + 2)
)0000000 0c-1 + 75
n1 + m Gk
(21)
Ln+m -7 7 (n + m)
+ n3 Q
) )(00 -.-1)
n + m
Gk
+ +n3 ) '
)o. O..
(n + m) Intm -7
n m
Note that
GK r/2
Intm - (n
GK )
+ +n3n 2
+ m
n m
GK
r/2
Gk
1/2
Gx
r/2
In-m -
(n m)
In
+ +n8,1)
+ m
n +
n2
r/2
Thus, by propagating
Gx m+m
from left right, we get
GK
r/2
r/2 GK
(0, 0,) = (Iatm - -RR)
0.,
+
n m
r/2
1/2
where R = (n + m)
Gk n+m
In
Gx n+m
+ nn3 Q is p.s.d. matrix. Denote the smallest and
largest eigenvalues of R by Xmin and 7max- Then, Amin 2 nn8.Ptiinn In terms of Ămaxo we have
GK
r/2
GK
r/2
( GK (GK]
(
GK
(n + m)
i
n +
n +
mm+m)
n 1 m
By Sylvester's theorem, all non-zero eigenvalues of G G are the eigenvalues of G,, ie. the non-zero eigenvalues of G.,n- By Lemma 2, 1 Then, Ámax "dA" + n.3
G |
ar, do so suppose || 1l2 S nd.
31

---

Published as a conference paper at ICLR 2024
1/2
f/2 we have R
1/2
r/2
Since MO. y, and
GK
M R
Gk
0,
Gx
y.
n+m
n+
a+
Note that R - -R)
(In+m - -7R) R. Thus, have
GK
r/2
Gk
1/2
(0. - 01) = (Intm -R))
O.
T +
+
GK
r/2
R 'In+m - -2R) + m
0,
GK
r/2
RR -R - -yR)²
y.
n1 + m
Now we bound |u.|12. First, note that for any matrices A, B Rdxd where B is p.s.d., there
is u T A "BAu I BB2 Aull < || 2 for any E R. so || T BA 1 S
| 12 ||A Alla. Second, note that the last m elements of ÿ are zeros, which means that ý I,
Thus, we have
GK
-001
U
l2
n + m In
(0,
n
G
r/2
Gk
1/2
n + m In
R "I -yR)
ÿ
+
n n m
(n + m)
Gk
r/2
14-m-77P 12 R " -²R)
Gx
r/2
+
m
Gk
(In+m 7R)
R- R- -In+t-
(n (n+ m)
In 2
|
12 + m
1nttm
Amin
Gx p+m where the last step is because we have already proved (mn + m)in
[n
S nd..
Now, for y ndrs when is sufficiently large it less than Xmmax Aamin because Bn = o(1). Thus,
Intm
-R I
Aman Wx
Paann Thus, we have
(1- (1- PmPmin
A
Iu 1|2
||
dr
AmPaii
The second part of this proof is to bound ||Q(0, 02) Let return to Eqn. (21), which says that
(Q, 0(+1)ll2 [I(Iatm - ,n,,, Q)Q(O. 0.) -7Quell2
8xPmin x
||Q(0, 0,)
Pmax
nd uu 1|2.
Here again, we assume that n is large enough so that X > 8mPwin. This implics that
QQ( 0st1)lla -0(1- BuPmin
x= ) "Pmax |1
12,3aain
BnPmin
1Q(0, - 0.)ll2 - -t (t-1) 11(1 AmPriin x-
r-1
Pmax y 11
xr
n2,30,
(1
BuPrnin) x²
){(1
BuPanin
Pmaxx 1/ lzll
S
IQ0.112 +
x,
n13,amii
Thus, there is ||Q(0_ -Q0l-0))ll3 - =<(1-
(1-
Bm
) '11Q0,11e + +t(1 x=
Bapmin 2-1
Peanx llvlla Using niai,
x S5 we have
(-
[_SnPuint Ar
x" BaPmiaatt -1)
Pmax 11
1Q(0, 0,)112 S exxp
|1Q0,112 + teexp
n2, Pmii
32

---

Published as a conference paper at ICLR 2024
When t = to
4A"
log
22" Pmax 11y
by log(2r) for > O, we have
Puii
nD P Q0.
PaPmin t
2X Pmax y 2
4X" Pmax 11/12 log
2X Pmax |1112
exp
2
n min Q0 12
m min 100112
n min min QQ0, 1l.
Let F(I) = exp
Buneein 2A*
Pmaxx 11y
Then we have F(lo) 2 0. And it is easy show
PDnnimin Q8. la
that for all 2 2. there is (t) 2 This means that when 2 to. there F(t) 2 O, so we have
(- AnPmint x²
I1Q0.1l2 + exp (- BmPriin
(2 2
(2-1) |100.122
1Q - 0,)1l2 S exp
x
Hence, when 2 max
22
log 2 + 2, to ). we have I|Q(0, 0,) S <e|000112, which implies
Prit
that the relative estimation error of  is less than 6.
D EXPERIMENTS
The purpose of our experiments is threcfold:
Verify that STKR- -erKR-Proppa (Algorithms and 2) works with general polynomial (A) including inverse Laplacian under transductive and inductive settings on real datasets, and compare them to label propagation (for the transductive setting).
(ii) Explore possible reasons why canonical Laplacian works so well empirically, by examining the effect of p on the performance when using STKR with s(A) = X².
(iii)
Verify that STKR-Prop works with kernel PCA on real datasets, and compare it other methods.
D.1 SETUP
Datasets. We focus on graph node classification tasks, and work with the publicly available datasets in the PyTorch Geometric library (Fey & Lenssen, 2019), among which Cora, CiteScer and PubMed are based on Yang et al. (2016); Computers, Photos, CS and Physics are based on Shchur et al. (2018); DBLP and CoraFull are based on Bojchevski & Günnemann (2018). See Table for summary of the dataset statistics.
Train//al/test/other splits. We split dataset into four sets: train, validation (val), test and other. Among them, train and val contain labeled samples, while test and other contain unlabeled samples. The test performance which we will report later is only evaluated on the test set. The val set is used to select the best model, so it is used in a similar way as the test set as explained below:
In the transductive setting, the learner can see all four sets at train time. The learner manually hides the labels of the samples in the val set (so that the val performance approximates the test performance). Thus, the size of the train set, while is the size of the other three combined.
In the inductive setting, the learner can see train, val and other, but not test. Neither can it see any edges connected to test nodes. Then, the learner manually hides the entire val set (nodes, outcoming edges and labels), so that the val performance approximates the test performance. Thus, n is the size of the train set, while m is the size of the other set.
In all our experiments, these four sets are randomly split. This means that with the same random seed, the four splits are exactly the same; With different random seed, the four splits are different, but their sizes are kept the same for the same dataset.
Sizes of the splits. First, we specify hyperparameter Piest, and then Piesa of all the samples will be in the test set. For Cora, CiteSeer and PubMed, we use the default train/validation/esst split size, and from the test set we take out P #(al samples) of the samples to be the real test set, and the rest of the samples go to the other set. For the other six datasets, we set the train and validation set size to be 20x number of classes. For example, the Physics dataset has 5 classes, so we randomly sample 100 samples to be train data, and another 100 samples to be validation data. We also do an ablation study for Preat in our experiments, where Prest could range from 1 % to 50%.
33

---

Published as a conference paper at ICLR 2024
Table 3: Number of classes, nodes, edges, fractions (%) train validation sets.
Classes
Nodes
Edges
Train
Validation
Cora
7
2,708
10,556
5.17
18.46
CiteSeer
6
3,327
9,104
3.61
15.03
PubMed
3
19,717
88,648
0.3
2.54
Amazon Computers
10
13,752
491,722
1.45
1.45
Amazon Photos
8
7,650
238,162
2.09
2.09
Coauthor CS
15
18,333
163,788
1.64
1.64
Coauthor Physics
34,493
495,924
0.29
0.29
DBLP
4
17,716
105,734
0.45
0.45
CoraFull
70
19,793
126,842
7.07
7.07
Implementations. For label propagation, we use the version in Zhou et al. (2003), which solves:
(Iu+m T) y, where ÿ = (g/ 0mm]
(22)
Here is the predicted labels for all + samples under the transductive setting, and S is defined as S = D WDD+ where W is the adjacency matrix such that W [i,j] 1 if x; is connected to Ty and otherwise, and D is diagonal matrix defined D(i, For STKR, define the base kernel K as:
Σ ン W[i,j] for i [n m].
x(x,x') ((x))
K(x, x²) = (n +))
(23)
where Wx);; = W[, and for the transductive setting there is D(z;) = DÍi, t]. so that S Gk. For the inductive setting, D(x,) Σ jéues modes Iz),,,) for all i E [n m], i.e. the n+="" sum only taken over the visible nodes at train time.
Hyperparameters. Below are the hyperparameters we use in the experiments. Best hyperparame- ters are selected with the validation split detailed above.
Label Propagation
Number of iteration T E [1, 4, 8, 16
E [0.7, 0.8, 0.9, 0.99, 0.999, 0.9999, 0.99999, 0.999999]
STKR transductive
Number of iteration 7 E [1, 4, 16
Laplacian -- = --1-
0.87, 0.9, 0.99, 0.999, 0.9999, 0.99999, 0.999999)
Polynomial s(A) = A: e [1,2,,,,66
33 E [10*, 10", 10", , 110-1,102,,10 10
10
10
10
10
STKR inductive
LLallccian -1 ((A) 1-
-----= . 0077 0.7,0.8,0.9. 0.9, 0.9.,..99.9999.. 0.999, 0.9999, 0.99999, 0.999999]
Polynomial = 2.
- -B E (
100100-11000 10- 3000, 10-5, 10 9,10-11110 100 10-8
Kernel PCA
Number of representation dimension E [3, 128, 226, 512]
256
[10 102 10a 10", 10-1, 10
-00 3, 10- 10 10 10-7,10
D.2 RESULTS
We report the test accuracy of STKR-Prop with different transformations and the Label-Prop algorithm in Table 4. To make a fair comparison between the transductive and inductive setting, we report the test accuracy the same Pres = 0.01 fraction of the data (for the same random seed). This is part of the unlabeled data the transductive setting, but is completely hidden from the learner in the inductive setting train time.
First, our results show that STKR-Prop can work pretty well with general s(A) under the inductive setting. The drops in the accuracy of the inductive STKR-Prop compared transductive small. In
34

---

Published as a conference paper at ICLR 2024
Table 4: The test acouracy (%) of Label-Prop (LP), PTRR-Prop (SP) with inverse Laplacian (Lap), with polynomial s(A) = X (poly), with kernel PCA (topd), and with s() À (KRR). (1) and (i) indicate the transductive and inductive settings. We report the test accuracy when Prst 0.01, i.e. test samples account for 1% of all samples. Standard deviations are given across ten random sceds. The best and second-best results for each datasct are marked in red and blue, respectively.
CS
CiteSeer
Computers
Cora
CoraFull
DBLP
Photo
Physies
PubMed
LP
79,07 19
52.737.12
77. 77.30g.0s
73.336.00 00
54.47
66,44s.78
83.95s.78
84.33, 86
72.28s.0
SP-Lap (t)
78.962.58
77.81 62.12
77.04s.74
63.812.34
65.42s.02
84.088.52
84.22 ss
71.93,
SP-poly (t)
79. 29
48.79 79s.s1
70.72s.12
71.48s.00
53. 25..5.
64.52 z0
84.451 79.21
72.184
SP-topd (1)
78.803.22
46.061.0s
80.80g.06
69.267,82
50.362as
64.86 60
84.61g.00
83.202
65.38s.6r 86
SP.Lap (i)
78.422.81
46.06a.97
77.152.64
67.787.62
53.30a.24
65.204.92
84.87s.c
83.115.09
70.364.90
SP-puly
79.022.42
44.550.16
71.974.18
65.199.11
51.98a.s8
64.524.00
78.427.50
84.684.ss
20.764.2
SP-topd (i)
79.138.35
41.526.11
80 80
63.70s.0
47. 47.413.39
63.166..1
85, 85.533.68
82.44
64.314.95
KRR (i)
13
13.6-15.3
20.35
28.52s.50 56
19. 19.802.22
44.80s
33.95
19.741.44
20.762.00
Table 5: Test accuracy (%) of STKR-Prop (SP) with inverse Laplacian (Lap), with polynomial s(A) = x
(poly) and with kernel PCA (topd) for inductive setting with different value of Piex E (0.01, 0.05, 0.2, 0.33. Standard deviations are given across ten random seeds.
Methods
Pisi
CS
CiteSeer
Computers
Cora
CoraFull
DBLP
Photo
Physics
PubMed
0.01
78.422.a1 81
46.06
77.15266
G7. 67.787.82
53.30
65.20,,92
84.875.00
83.11
70.36
0.05
77.93
11.75
77.122.05
62.377.e4
51.636.90
65.572.2
81.902.00
67.814.58 82.72..2
SP-Lap
0.1
76.451.17
39.9972.a
77.401as
69.74g.37
50.222.75
65.342.09
84.10
66. 66.433.c2 82.02..11
0.2
75.06 01
35.50 .4
77.18200
55. 102 92
47 47.846.79
63.24
83.811.m
81 31.333.5 59
63.77a.36
0.3
72.89p.9s
30.92,.14
76.59,.71
50.22 87
44.966.77
00.44..6
63.28,.11
80.275.15
60.252.75
0.01
14.55g.15 79.13
71.974.15
65, 19..9
51, 51.98a.s
641.24..0
78.427.80
70.76 84.68
0.05
78.74 48.744142
40.36p.61
73 78.004..0
61.854.15
50.21 L.c
64.642..0
79.084..1
84.05
67.6% 67.682.91
SP-poly
0.1
77.51 ma
38.58 so
73. 101 .s
58.56y.to .e
49.06..5
64.211.0s
78.59
83. 133..
06.08 96
0.2
33.651.78 75.741.02
72. 701.1
53.112.39
46. 16.53o.79
61.892.05
78.82s.05
82.36g.27
62.97s.10
0.3
73.35n.70
28.981.21
72.351.00
47.99)2.a
43 43.422.77
59.562.02
78.202.7a
81. $1.088..5
59.322.67
0.01
41.526.71 79.18
80.803
63. 13.700.co
47.413.39
63.166..4
85.588..0
82, 82.44
64.314.90
0.05
78.371 a8
40.00b.14
80.17
G1. 70..00.5
47.171.53
62.79s.36
85.472.07
82.26 as
02.799..
SP-topd
0.1
77.171.02
38.67
79.352.87
58.81a.26
45.226.s0
61.512.00
84.851.70
80.59
61.76g.3
0,2
75.Gln.e4
35. 10,660..4
79.000 79.002.02
55.514.21
42.31o.91
60.302.60
84.631.44
80.151.sd
59, 6.2.0
0.3
72.50a.70
32.921.92
78.091.7
51.714.30
38.622.79
59.182.20
83.911.00
79.072.33
57. 57.50p.50
Table 5, we further provide ablation the test accuracy as we increase Pust- As Pust is larger, the performance of inductive STKR decreases across the board. Nevertheless, there are many datasets such as Photo, Physics, Computer where the performance drop is fairly small at around 2 3 percent even when Prest = 0.3. Our ablation study shows that inductive STKR is quite robust to the number of available unlabeled data the training time. Our experiment clearly demonstrates that one can implement STKR with a general transformation such as s()) = A efficiently. The running time of STKR-Prop is similar to that of Label-Prop with the same number of iterations.
Second, we explore the impact of the "number of hop" p on the performance of STKR with s(A) - AP (Figure 2). We consider p E {1. 2, 4, 6, 8). and note that for p performing a KRR with the base kernel. As we have already seen in Table 4, the performance of such KRR is extremely poor compared to the other methods. This is consistent with our analysis in Section 2 that KRR with the base kernel is not sufficient. We find that by increasing which in turns increase the additional smoothness requirement, the performance of STKR increases by a large margin for all datasets. This clearly illustrates the benefits of the transitivity of similarity, and offers possible explanation why the inverse Laplacian transformation performs so well in practice: It uses multi-hop similarity information up to infinitely many hops.
this STKR is equivalent to
Third, the results show that STKR also works pretty well with kernel PCA. Comparing between kernel PCA and LP (or STKR with inverse Laplacian), on 3 of the 9 datasets we use, the former is better. Thus, this experiment clearly demonstrates the parallel nature of these two methodologies STKR with inverse Laplacian, and kernel PCA.
Finally, we provide an ablation study about the effect of v in inverse Laplacian on the performance of SP-Lap. Recall that for inverse Laplacian we have s --( = X 17. Our observation is that when 1) is very close to 0, the performance is low; once it is bounded away from 0, the performance is fairly consistent, and gets slightly better with a larger 17. Only on dataset CS do we observe a significant performance boost as 17 increases.
35

---

Published as a conference paper at ICLR 2024
CS
CiteSeer
Computers
Cora
CoraFull
DBLP
Text accuracy
Photo
Physics
PubMed
2
6
s(A) ())
Lnv
Figure 2: Test accuracy (%) of STKR-Prop (SP) with polynomial with s(A) X for E (1, 8}. The test accuracy increases significantly as p is larger than illustrating the benefits of the transitivity of similarity.
0.8
0.7
0.6
Accuracy
Data
0.3
CS
DBLP
CiteSeer
Photo
Computers
Physics
0.2
Cora
PubMed
CoraFull
0.1
0,0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
STKR inv Lap --1=-~1-1-----
Figure 3: Test accuracy of SP-Lap with different values of The test accuracy is fairly consistent as long as 1) is not too close to and gets slightly better with larger 17. All reported performances are averaged across ten random seeds.
36


Reviews:
[{"review_id": "wiRsqxWMWl", "reviewer": "Reviewer_nUyP", "summary": "The paper focuses on utilising unlabelled data within the framework of Spectrally Transformed Kernel Regression (STKR). The rough idea is that unlabelled data can be used to infer the smoothness of the kernel. This is achieved by considering spectrally transformed (Mercer) kernels:\n$$ K_s(x,y) = \\sum_{i=1}^\\infty s(\\lambda_i) \\psi_i(x)\\psi_i(y). $$\nThe form of the transformation $s(\\lambda)$ influences the smoothness of the kernel and this is what is learned from the unlabelled data. The paper investigates this theoretically by assuming the target function $f^*$ has a target smoothness constraint $f^* \\in \\mathcal{H}_t$ and assumes the target smoothness is at least as smooth as the base kernel $\\mathcal{H}_t \\subset \\mathcal{H}_K$. \n\nTheorem 1 states that under certain conditions, $\\mathcal{H}_t$ is the RKHS of a spectrally transformed kernel. This can be viewed as an existence result of a suitable $s$ and so motivates the rest of the paper.\n\nNext, the authors consider the theoretical implications of this and construct algorithms of STKR in two different settings: (1) $s$ is known and (2) $s$ is unknown. Setting (2) is the real-world situation and so is of more practical benefit. \n\nSetting (1):\n\nThe problem here is that $K_s$ may not be computable. Therefore, the authors utilise the unlabelled data to estimate $K_s$ by a Monte-Carlo approximation of the kernels $K^p$, which is $K_s$ with $s(\\lambda) = \\lambda^p$ (it is assumed that the true $s$ is expressible as a power series). Under this scenario, it is shown that KRR is minimax optimal under exact evaluation of $K_s$ (Theorem 2). The approximation error of using $\\hat{K}_s$ over $K_s$ is also shown to be bounded (Theorem 3).\n\nSetting (2):\n\nFirstly, the authors consider $s$ as the inverse regularised Laplacian. This is motivated by the fact that this $s$ has been shown to work well empirically in prior work and can be analysed theoretically.\n\nNext, the authors consider a kernel where the first $d$ eigenfunctions are learned through kernel PCA on the unlabelled data. This is equivalent to STKR with $s$ as a truncation function, all eigenvalues smaller than $\\lambda_d$ are eliminated. The authors provide theoretical guarantees that lower bound and upper bound the worst and best case errors respectively.\n\nMain Contributions:\n- Establishing STKR as a principled way to utilise unlabelled data, showing that under certain smoothness conditions, a target function must be smooth with respect to a certain Spectrally Transformed Kernel (STK).\n- Implementing practicable STKR algorithm in an inductive setting with general transformations, which is more practical than previous transductive approaches. This implementation is scalable, has closed-form formulas for the predictor, and comes with statistical guarantees.\n- Developing rigorous theoretical bounds for this general inductive STKR, proving estimation and approximation error bounds, some of which are tight or near-tight.", "questions": "Can you discuss when the conditions of theorem 1 are satisfied? The conditions being that 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)$. Could there be situations where this condition is violated and so the resulting theory doesn't hold? Does this have any practical consequences?\n\nCould proposition 3 be generalised for other transformations $s(\\lambda)$? With $s(\\lambda) \\geq \\lambda$?\n\nDo you have any intuition as to why STKR performance degrades as $p_{test}$ increases? Does this imply scalability issues?\n\nWill the code used in the experiments be provided for reproducibility?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "Overall, I find the paper very good. The authors provide a theoretical framework that unifies previous works of incorporating unlabelled data into learning algorithms. The author's approach, to my knowledge, has not been considered before.\n\nThe theoretical results are very interesting. The methodology developed is motivated and justified from the author's theoretical work. The authors developed a rigorous theoretical underpinning for inductive STKR and provide tight statistical learning bounds for prediction errors. This addresses the issue of generalisability in STKR, by offering strong statistical guarantees. Not only this, the methodology is practicable and this is evidenced from the experimental results and computational complexity calculations. \n\nThe paper is very well written and easy to understand. A lot of background material is presented, which contextualises the work. The appendices are also well written and include extensive discussions on related works.", "weaknesses": "The main weakness, in my view, is the lack of a comprehensive empirical investigation. \n\nWhile the paper does explore the effect of different transformations $s(\\lambda)$ and provides a comparison to other methods such as label propagation and kernel PCA, it does not delve deeply into the conditions or characteristics of datasets that would lead to STKR's superior performance. It is probably very difficult to do this theoretically, but a more comprehensive empirical investigation could lead to insights. This could be seen as a limitation in fully understanding the potential and limitations of STKR.\n\nAlso, although the experiments cover several datasets, they are all within the realm of graph node classification. Expanding to other types of data could demonstrate the generality of the approach.\n\nWhile the paper mentions the efficiency of the STKR-Prop, a detailed computational complexity analysis, especially in comparison with other methods, could add more depth to the evaluation of the methodology. \n\nFinally, I don't see where the regularisation term $\\eta$ in SP-Lap is specified within the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g6z3ZmgjVw", "reviewer": "Reviewer_SncV", "summary": "This paper considers spectrally transformed kernel regression, a way of performing unsupervised or semi-supervised learning with kernels. Unlabeled data can be leveraged to obtain better estimates of a spectral transformation of the kernel, which can then be used for kernel regression. The paper proposes scalable algorithms to implement STKR for two different types of spectral transformations in the inductive setting, which is more practical than the transductive setting that is often used. Moreover, it provides a characterization of target smoothness of functions and provides theoretical guarantees on how fast such smooth functions can be learned using STKR.", "questions": "**Questions**:\nIn Example 1, is $K^0(x, x')$ just $\\mathrm{tr}(K)$?\n\nIs there a setting in which a provable benefit of semi-supervised learning over supervised learning can be proven?\n\nCould label propagation be made inductive by using it to label the unlabeled \"other\" set transductively, and then using these pseudo-labels to fit a supervised kernel regression method (\"distillation\")? How would you expect this to compare to STKR in terms of runtime and accuracy?\n\nIn the proposed algorithms, could it be beneficial to use more advanced linear system solvers like the CG method instead of Richardson iteration?\n\n\n**Major comments**:\nParagraph before Proposition 1: The definition of $\\overline{\\mathcal{X}}$ is very imprecise. It looks like you are summing inside of $\\mathcal{X}$, even though $\\mathcal{X}$ might not be a vector space. It is also not clear whether the sums are allowed to be infinite. On the one hand, I would assume them to be finite because you didn't impose any assumptions on the $a_i$. On the other hand, you say later that $\\overline{\\mathcal{X}}$ is a Banach space, but it wouldn't be complete if you only allowed finite sums. I assume that you would want $\\overline{\\mathcal{X}}$ to be the space of finite signed measures on $\\mathcal{X}$, then the norm / distance could be defined through kernel mean embeddings, and $f(\\mu) = \\mu_f$ would be the pushforward measure.\n\nProposition 1 seems to be mathematically elegant, at least when reformulating it with measures as discussed in the previous comment. However, the notion of this \"alternative\" Lipschitz constant seems rather unintuitive to me, and I am not sure what benefit it brings compared to just using the RKHS norm.\n\nThe centeredness assumption on the base kernel is worrying me, as I do not fully understand its practical and theoretical implications. Where is this assumption necessary? I understand that it is necessary for Proposition 1. Is the purpose to make the smoothness notion shift invariant and not having to worry about the constant part of the target function that is not covered by the smoothness $r_t(f)$?\n\nIn Theorem 1, it was not fully clear to me whether the assumptions above Section 2.2 are also assumed in the theorem; for example, the assumption $\\mathcal{H}_t \\subset \\mathcal{H}_K$ is repeated in the theorem.\n\n**Minor comments**:\n- Section 2, page 2: You write $dp(x)$ in the integral multiple times, but you did not define $p$. You could just write $dP_{\\mathcal{X}}(x)$.\n- Footnote on page 2: Since $L^1(P_{\\mathcal{X}}) \\subseteq L^2(P_{\\mathcal{X}})$, it is not necessary to assume boundedness for the existence of the expectation. Is boundedness also required for other things?\n\"$\\mathcal{H}_{K_p}$ are also known as interpolation Sobolev spaces\": I think from the definition these are known as power spaces, see e.g. [1], although they are often (?) identical to interpolation spaces. In the case where the RKHS of $K$ is a Sobolev space, these are usually also Sobolev spaces, but you did not assume this.\n- Small typesetting observation: In Proposition 1, $\\overline{\\mathrm{Lip}}$ is italic while it is not italic above. Maybe you used \\text{Lip} instead of other commands such as \\DeclareMathOperator or \\operatorname or \\mathrm?\n- Before Section 2.2, you use the absolute value on $\\overline{\\mathcal{X}}$, is this supposed to be the total variation norm?\n- In Section 3 (page 6), you should explain that $s^{-1}(\\lambda) = 1/s(\\lambda)$ (if I understand correctly), or perhaps directly write $s(\\lambda)^{-1}$. I thought that $s^{-1}$ was the inverse of $s$ until I noticed that it didn't fit with the implementation.\n\n[1] https://link.springer.com/article/10.1007/s00365-012-9153-3\n\n**Summary of discussion:**\nWhile the authors did not extend their experiments much, the theoretical analysis is interesting in its own right and the authors fixed some technical issues and improved some explanations, so I raised my score from 6 to 8.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality: While STKR itself is apparently well-known, the authors advance the understanding of this method both in algorithmical and theoretical aspects.\nQuality: While I have not verified the proofs in the appendix except for Proposition 1, the quality of the results seems to be good.\nClarity: The paper is well-written, in particular it provides many useful comments on the motivation and interpretation of the theoretical results.\nSignificance: I am not familiar with previous literature on semi-supervised learning with kernels, but judging from the description in the paper, the existence of theoretical guarantees seems to be an advantage compared to previous work, and the introduction of practical algorithms for the inductive setting also appears to be relevant. I am not sure about the practical relevance due to limited experimental results.", "weaknesses": "The experiments are rather limited. First, they are limited to node classification in graphs, which is certainly an interesting class of problems, but it leaves me wondering whether the proposed method, despite its generality, is useful on other types of problems. Moreover, the results are only compared to one competitor method, label propagation. It would be interesting to see\n- how the proposed method compares to label propagation in terms of (training and) inference time,\n- if there is another known feasible inductive method, how this method compares to STKR,\n- how the proposed method compares to other (non-kernel) methods, surely there have to be some deep learning methods for these problems?\nOf course, the proposed method is already relevant through its theoretical analysis, but a better experimental evaluation would help to better understand the practical relevance.\n\nThe assumptions used in the theoretical analysis appear to be relatively strong compared to what I know from the supervised learning literature, at least when thinking about continuous input spaces rather than graphs. For example, if the base kernel was a Sobolev kernel, the associated RKHS would have to have a smoothness $s > d/2$, which might be unrealistic in high dimensions. In this case, many theoretical results such as the ones in Fischer & Steinwart (2020) allow the target function to lie in an interpolation space that is larger than the RKHS. In the case of this paper, I am wondering whether such an assumption could be sensible, as having higher smoothness than the base kernel appears to be crucial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kuJoNQ8Hiq", "reviewer": "Reviewer_bYf4", "summary": "This paper studies regression problems in indusctive and transductive settings. The authors establish that if the target function space satisfies a multiscale smoothness assumption, then its reproducing kernel can be represented using a spectral transformed kernel (STK) of on the original space.  Under inductive settings when the spectral transformation function is known, they arrive at convergence guarantees of the learnt model to that of the true one, and the approximation guarantees for using an estimated kernel. Algorithm(s) SKTR-prop estimate the parameters \\alpha when s(\\lambda) or s^{-1}(\\lambda) is analytical, which are in turn used for the prediction. They also show convergence and approximation bounds when s(\\lambda) is not known, while constraining the space using regularized inverse laplacian kernel or top-d components from kernel PCA. They illustrate on node classification tasks comparing well against label prop and kernel ridge regression.", "questions": "- The laplacian kernel and kernel PCA are known in the literature. In terms of final application, how exactly this work exactly differs in applying them for the problems? Are there other recommendations for choosing the transformation functions for practical use cases ?\n\n- Notation: p is an integer in eqn 7, while a real number in eqn 10. Are they consistent ?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- As the authors mentioned, though STK, STKR are known before, the theoretical results seem original (to the understanding of the reviewer). \n\n- The regularized laplacian and kernel pca strategies makes good illustration for the applicability of the results, along with the experimental results.", "weaknesses": "- Though the flow of the paper is neat, the presentation may be improved which may help with reading such dense set of results. For instance, the definitions of the (target)-smoothness may be done clearer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "04SelU77KH", "reviewer": "Reviewer_j9KG", "summary": "The paper presents a universality type result in the context of Spectrally Transformed Kernel Regression (STKR): They show that any target smoothness that preserves multiscale smoothness can be encoded by a spectrally transformed kernel (theorem1).\n\nThe goal of the work is use unlabelled data in encoding the target smoothness and then perform (ridge) regression over labelled data. Accordingly, in the case the spectral transform is known, they propose to perform a montecarlo estimation of the STK using labelled as well as unlabelled examples and perform STKR using labelled samples. For this methodology both estimation and approximation errors are bounded (theorem2,3). Implementation details are also discussed.\n\nFor the case the transform is not known, they propose following a commonly used two stage process: self-supervised learning using unlabelled samples to learn a d-dim representation. Then, perform ridge regression using the labelled examples under the learnt representation. Again, theorem4,5 provide the estimation and approximation errors. Interestingly, the approximation is shown to be tight (theorem 5& prop5), proving that this methodoloy is no worse than the original proposal of STKR.\n\nSimulations results on few benchmarks are provided.", "questions": "1. Proposition 1 assumes functions extended to \\bar{X}. But what if X itself is a vector space? then this extension basically means we are considering only linear functions over X. So proposition 1 would be restricted to linear functions over X. Am I missing something? Since prop1 is used in theorem 1, perhaps this is an issue?\n\nMinor comments:\n1. pg3 \"p\" is used as exponent as well as likelihood.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I think theorem 1 is insightful and provides perhaps a first universality kind of result connecting smoothness and RKHS.\n\n2. Theorem 5 is also interesting and seems to improve over current bounds i.e., Zhai et.al. 2023.", "weaknesses": "questions section", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EqV3741CY6", "reviewer": "Reviewer_aR59", "summary": "This work stands at the crossroads of kernel learning and regression, in close connection with manifold learning. The contribution is presented as a novel theory to incorporate both unlabeled and labeled data into the resolution of the regression task (see our comments).  The authors propose to address an inductive regression estimation problem with the additional assumption that the target function satisfies a smoothness constraint defined with respect to a given Mercer kernel-induced metric. A key result of the paper is that the target is proved to be attainable within a RKHS based on a spectrally transformed kernel (say $H_{K_s}$).\nEmpirically this problem can be handled with the choice of a single regularization term that writes as a variance term in the RKHS H_{K_s}.\nThe authors then propose two novel (closed-form) estimators that rely on both kernel and representation coefficients learning. In the first setting, the user is supposed to know exactly the spectral transformation of the eigenvalues at work in the spectrally transformed kernel built from the eigenvalues of the original base kernel. A computable kernel $\\hat{K}_s$ is recursively built and a closed-form solution is provided for the empirical ridge regression problem in the RKHS associated with the approximate kernel. This novel estimator comes with an minimax optimal excess risk bound. In the second setting, a (two-step) transform-agnostic estimator is proposed with $K_s$ defined as the inverse Laplacian and a finite feature map representation based on kernel PCA applied on unlabeled data. The novel estimator is also studied at the lens of an excess risk bound. Numerical experiments complete the picture with a comparison of  the STKR different variants to Label-Propagation.", "questions": "* There is no discussion about the base kernel K upon which the spectrally-transformed kernel is built. How to choose it ?\n* finally to improve the clarity of the paper: \n- please clearly state when you introduce the intuition and then formally state the theoretical results, there is a mix of evreything all along the paper which makes the paper sometimes difficult to read?\n- express more clearly Theorem 1: how is defined r_t prior to the conclusion: only a function from $L^2(P_X)$ to $\\mathbb{R}$ ?\n- explain the importance of centering the functions or alternatively using a \"variance term\" as a penalty.\n- give the analytic complexity in time of the algorithms\n- in the experiments provide the behaviour of Mainfold learning (Belkin et al. 2006), especially the closed-form with ridge and laplacian regularisation.\n\nI have read the author's rebuttal and am satisfied the answers. I increase my score from 7 to 8.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "*Overall, the paper proposes a rich framework that tackles both representation learning and regression estimation within RKHSs. It follows a long line of research linked to manifold learning in a transductive or inductive way and a spectral approach to kernel learning. The works presented here are substantial with a solid theoretical back up and extensive discussions. I appreciate the elegance of the approach that inherently incorporates into the joint choice of the regularization term  (variance) and the kernel choice the smoothness contraints without leveraging the two regularization terms usually at work in manifold learning. It is a pleasant paper to read, even if it is dense.\n\n*The proposed framework can be naturally applied to transductive or inductive setting, the latter being the most interesting.\nOverall the work shed slight on how kernel learning can be considered in a systematic and powerful way for a general regression problem leveraging unlabeled and labeled data.\n* The work appears as original and rather well written even if the writing can still be improved.", "weaknesses": "* Please note that my score is currently 7\n* Claims: it is stated in the abstract and in the paper many times, that this contribution provides a unifyied theory for learning with unlabeled data and a base kernel. I think this message does not hold and is misleading for the reader. I consider that the paper provides a novel class of regression estimators able to exploit labeled and unlabeled data by considering that the right space to work in is the RKHS associated to a Spectrally transformed kernel or its approximation.\n*I am surprised that the discussion in page 3 takes classic kernel ridge regression as a reference method while manifold learning with Laplacian regularization (in addition to $\\ell_2$ norm ) would be more interesting to discuss here : see Belkin et al. 2006 JMLR to be cited (other papers of Belkin are cited, though)\nBelkin, M., Niyogi, P., & Sindhwani, V. (2006). Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of machine learning research, 7(11).\nIn particular, the example discussed in figure 1 could have been solved with manifold learning. \nat this stage of the paper, I see the advantage of defining the right regularization term with the right kernel to empower the RKHS with the good smoothness properties. However I am a bit confused then by example 1 given in page 7.\n* In Example 1 page 7 (Inverse laplacian), I am interested in a discussion about the pros and cons of the proposed method where $K_s$ is defined as a combination of two kernels with a hyperamater eta that seems to play a similar  role that the weight controlling the importance of $\\ell_2$ norm and the Laplacian smoothness penalty. Here, I don't see how one can take into account the dependency of the excess risk on this \"hidden\" parameter.\n* originality: the paper resembles a bit to the recent work of Zhai et al. (2023) and it should be interested to highlight the differences; I will advise the authors not to go to far in the direction of data augmentation to strengthen the differences.\n* the paper is very dense and clarity can be improved. Some suggestions:\nPlease provide a table (can be in the first page of the supplements) with a reminder of all the notations for the various kernels, $K_s$, $K^p$, \\tilde{f}, \\hat{f}, ..\n* clearly state when you introduce the intuition and then formally state the theoretical results, there is a mix of evreything all along the paper which makes the paper sometimes difficult to read\n* in experimental results (last page): complete the legend so that the reader can see what is the used criterion here (accuracy with a post-processing of the regression estimation outputs).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)