Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning
Authors: Vivien Cabannes
Loucas Pillaud-Vivien
Francis Bach
Alessandro Rudi
Venue: NeurIPS 2021 Poster (2021)
Keywords: semi-supervised learning
Laplacian
Laplacian regularization
weakly supervised learning
kernel methods
spectral filtering
partial labelling
diffusion
functional analysis
statistical learning
generalization bounds

Abstract: As annotations of data can be scarce in large-scale practical problems, leveraging unlabelled examples is one of the most important aspects of machine learning. This is the aim of semi-supervised learning. To benefit from the access to unlabelled data, it is natural to diffuse smoothly knowledge of labelled data to unlabelled one. This induces to the use of Laplacian regularization. Yet, current implementations of Laplacian regularization suffer from several drawbacks, notably the well-known curse of dimensionality. In this paper, we design a new class of algorithms overcoming this issue, unveiling a large body of spectral filtering methods. Additionally, we provide a statistical analysis showing that our estimators exhibit desirable behaviors. They are implemented through (reproducing) kernel methods, for which we provide realistic computational guidelines in order to make our method usable with large amounts of data.  


Overcoming the curse of dimensionality with
Laplacian regularization in semi-supervised learning
Vivien Cabannes
Loucas Pillaud-Vivien
Francis Bach ENS - INRIA PPLL
ENS- INRIA PSL
EPFL Lausanne, Switzerland
Paris, France
Paris, France
vivien. wawannesggmail.lccmmmm com
Alessandro Rudi ENS INRIA - PSLL
Paris, France
Abstract
As annotations of data can be scarce in large-scale practical problems, leveraging unlabelled examples one of the most important aspects of machine learning. This is the aim of semi-supervised learning. To benefit from the access to unlabelled data, it is natural to diffuse smoothly knowledge labelled data to unlabelled one. This induces to the use of Laplacian regularization. Yet, current implementations of Laplacian regularization suffer from several drawbacks, notably the well-known curse of dimensionality. In this paper, provide statistical analysis overcome those issues, and unveil a large body of spectral filtering methods that exhibit desirable behaviors. They implemented through (reproducing) kernel methods, for which we provide realistic computational guidelines in order to make our method usable with large amounts of data.
In the last decade, machine learning has been able to tackle amazingly complex tasks, which was mainly allowed by computational power to train large learning models large annotated datasets. For instance, ImageNet made of tens of millions of images, which have all been manually annotated by humans [6]. The greediness in data annotation of such a current learning paradigm is major limitation. In particular, when annotation of data demands in-depth expertise, relying on techniques that require zillions of labelled data is not viable. This motivates several research streams to overcome the need for annotations, such as self-supervised learning for images or natural language processing [17] Aiming for generality, semi-supervised learning is the most classical one, assuming access to a vast amount of input data, but among which only a scarce percentage is labelled. To leverage the presence of unlabelled data, most semi-supervised techniques assume form of low-density separation hypothesis, as detailed in the recent review of van Engelen and Hoos (52), and illustrated by state-of the-art models 6 [5].. This hypothesis assumes that the function learn from the data varies smoothly in highly populated regions of the input space, but might vary more strongly in scarcely populated areas, or that the decision frontiers between classes lie in regions with low-density, In such setting, it is natural to enforce constraints on the variations of the function to learn. While semi-superviee supervised learning is an important learning framework, has not provided as much exciting realizations as one could have expected. This might be related to the fact that it is classically approached through graph-based Laplacian, technique that does not scale well with the dimension of the input space 5
Paper organization. In Section we motivate Laplacian regularization, and recall drawbacks of naive implementations. These limitations are overcome in Section 2 where we expose a theoretically principled path derive well-behaver algorithms. More precisely, we unveil a vast class of estimates
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

based on spectral filterin. We turn to implementation in Section 3 where we provide realistic guidelines ensure scalability of the proposed algorithms. Statistical properties of our estimators are stated in Section 4
Contributions. They are two folds. (i) Statistically, we explain that Laplacian regularization can be properly leveraged based on functional space considerations, and that those considerations can be turned into concrete implementations thanks to kernel methods. As result, we provide consistent estimators that exhibit fast convergence rates under low density separation hypothesis, and that, in particular, do not suffer from the curse of dimensionality. (ii) Computationally. we avoid dealing with large matrices of derivatives by providing low-rank approximation that allows to deal with n" log(n) x n² log(n) matrices, with a parameter y E (0, 1] depending on the regularity of the problem, instead of n(d + 1) x nid + 1) matrices, thus cutting down to (logg() (n)oggn)"" potential (n dd) training cost.
1 (22d) the
Related work. Interplays between graph theory and machine learning were proven successful in the 2000s [47). The seminal paper of Zhu et al. [62] introduced graph-Laplacian as a transductive method in the context of semi-supervised learning. A smoothing variant was proposed by [60], which coherent with the fact that enforcing constraints on labelled points leads to spikes M.. Interestingly, graph Laplacians do converge to diffusion operators linked with the weighted Laplace Beltrami operator [24 2T. However, these local diffusion methods are known suffer from the curse of
dimensionality 5 That is, local averaging methods are intuitive learning methods that have been used for more than half century (20]. Yet, those methods do not scale well with the dimension of the input space [56]. This is related with the fact that to cover [0, 1] we need e- balls of radius e. Interestingly, if the function to learn m times differentiable with smooth partial derivatives. it is possible to leverage more information from function evaluations and overcome the curse of dimensionality when m Z This property is related to covering numbers (a.k.a. capacity) of Sobolev spaces (28) and is leveraged by (reproducing) kernel methods 449 TO]. The crux of this paper is apply this fact to Laplacian regularization techniques. Note that derivative with reproducing kernel methods in machine learning have already been considered in different settings by [6] 19]
Laplacian regularization
In this section, we introduce the notations and concepts related to the semi-supervised learning regression problem, noting that most of our results extend to any convex loss beyond least-squares. We motivate and describe Laplacian regularization that will allow us to leverage the low-density separation hypothesis. We explain statistical drawbacks usually linked with Laplacian regularization, and discuss on how to circumvent them.
In the following, we denote by X = Rd the input space, y = R the output space, and by p Axxx the joint distribution on X' x y. For simplicity. we assume that has compact support. In the following, we denote by px the marginal of p over X. and by pla the conditional distribution of Y given X x. As usual, for p E No, T. (RR) is the space of functions such that f" is integrable. Moreover, we define usual Sobolev spaces: for E N. (=P(R)) stands for the space of functions whose weak derivatives of order s-th are in (Rd).. When p = 2, they have Hilbertian structure and we denote, H (RRd) (IR)( these Hilbertian spaces. Ideally, we would like to retrieve the mapping g": : X + y defined as
g* arg min ExxYrw [1x(x) - -1[]] = arg min I|g golliA((x) = 9p- gELA(px)
geL)(ex)
where 9p : X'' - + is defined as (r(x) E = In semi-supervised learning, we assume that we do not have access to p but we have access to n independent samples (Xi)sgn Px among which we have ny labels Y, ~ plx, for i < ng, with potentially much smaller than n. In other terms, we have nig supervised pairs (X,, Y.)igne and n n, unsupervised samples (Xi)nesisn While we restrict ourselves to real-valued regression for simplicity, our exposition indeed applies generically to partially supervised learning. particular, it can be used off off-lle-shelve to complement the approaches of [ g as we detailed in Appendix

---

Semi-supervision setting
Baseline: 1 ş =
Result: 1= μ 1/n
Figure I: Motivating example. (Left) We suppose given 7 = 2000 points in N' = R², represented as labelled points, with labels
black dots, spanning 4 concentric circles. Among those points are being either represented in red, and represented in blue. In this setting, is natural assume that should be constant on each circles, which ridge regression estimate based on the labelled points with Gaussian kernel of bandwidth a = .2r, r being the radius of the innermost circle. (Right) Laplacian regularization reconstruction. The reconstruction is based on approximate empirical risk minimization with which ensures a computational complexity the exact empirical risk minimizer
encoded VVVg"
on supp px: (Middle) Kernel
of Opp (d), instead of O( d²)) needed
1.1 Diffusion operator L
In order to leverage unlabelled data, we will assume that g" varies smoothly on highly populated regions of X, and might vary highly on low density regions. For example, this is the case when data clustered in well separated regions of space, and labels are constant on clusters. This captured by the fact that the Dirichlet energy
fe (Vo" px(dr)= Ex [XVX* =: - [2(xx))
is assumed to be small. Because the quadratic functional (2) will play a crucial role in our exposition, we define L as the self-adjoint operator (px extending the operator (xxxx) representing this functional. Under mild assumptions on p.x. L-1 can be shown to be a compact operator, which we will assume in the following. essence, we will assume that if have lot of unlabelled data and || can be well approximated for any function 9, then we do not need lot of labelled data to estimate correctly g" To illustrate this, at one extreme, we know that || = O, then g" known to be constant each connected component of px that, along with the knowledge of px, only few labelled points would be sufficient to recover perfectly g". We illustrate those considerations Figure]
1.2 Drawbacks of naive Laplacian regularization
Following the motivations presented precedently, is natural consider the regularized objective and solution defined, for À > 0, as
arg min E(x,r)~ [11((X) x11] +XExppx [IVg(() (xX)(xx)
9A
(3)
arg min llg - 90ll 901l2 + + 22 (x(px) = (1 XC) 90-
(EX)
This regularization has nice properties. In particular, for small X, it can be seen first order approximation of the heat equation solution -x- which represents the temperature profile at time t = X, instantiated with the initial profile 9,. and with Px modelling the thermal conductivity. It also has interpretations in term of random walk and Langevin diffusion [40] 48). In a word, 9x the diffusion of 9, with respect to the density Px, which relates to the idea of diffusing labelled data with respect to the intrinsic geometry of the data, which is the idea captured by [62].
However, from learning perspective, Eq. (3) is linked with the prior that g" belongs to H (px), prior that is not strong enough to overcome the curse dimensionality as we saw in the related work section. Moreover, assuming we have enough unsupervised data to suppose known px, and therefore
C. Eq. (3) leads to the naive empirical estimate Itnaive) arg ming.x-- Ens llg(X,) Y
ned /3]]² While the definition of Itaaive) could seem like great idea, in fact, such estimate Koaive) is known to be mostly constant and spiking interpolate the data (X,, Y2) soon d 2

---

37 This is to be related with the capacity of the space associated with the pseudo-norm || in I.2. This capacity, related to H" is too large for the Laplacian regularization term to constraint Roaive) meaningful way. other terms, we need regularize with stronger penalties.
1.3 Stronger regularization
In this subsection, we discuss techniques to overcome the issues encountered with G(nnive). Those techniques are based on functional space constraints or on spectral filtering techniques.
Functional spaces. A solution overcome the capacity issue of H² in L is to constrain the estimate of g" to belong to a smaller functional space. In the realm of graph Laplacian, [ proposed to solve this problem by considering the r-Laplacian regularization reading 22, fx (V )ll p(dz), with r > In essence, this restricts g to live in (xx')(x) for > d, and allows to avoid spikes associated with Mauiive)- However considering high power of the gradient is likely to introduce instability (think that is the potentially really big dimension of the input space), and from learning perspective, the capacity of WL,., which compares to the one of H2, is still too big.
In this paper, will rather keep the diffusion operator L. and add second penalty reduce the space in which we look for the solution. With G an Hilbert space of functions, we could look for, with μ >> 0 second regularization parameter
IA. arg min 11g 3pll22(xx) 2 1// [P(xx) + +1p119113. 9.GnH+((x)
(4)
This formulation restricts 2A to belong both H H (px) (thanks the term in X) and & (thanks to the term in p)). In particular the resulting space (px) ng to which IN belongs, has smaller capacity in 2 than the one of G in L.2. In practice, we do not have access to / and px but to (X,, Yi)es, and (X,)ssn, and we might consider the empirical estimator defined through empirical risk minimization
ne Σ llo(..) Y2ll + An An- Vo((X)) +xp legl.
I arg min n SEg
(5)
For example, we could consider G to be the Sobolev space HTT (dx). Note the difference between g linked with dz, the Lebesgue measure, that is known, and L linked with px, the marginal of over X, that is not known. In this setting, the regularization /| g|| /llle11 reads fx [Dg(z)]l (x(d))= +
u fx Ex || DD)g(a)] da. Because of the size of TT in L2, this allows for efficient approximation of 9x.x based empirical risk minimization. In particular, if n +o0, we expect the minimizer
(5) to converge toward Ix2, at rates in L scaling similarly to n2 mm/d mmm//d in ng. To complete the picture, depending on a prior on Sp- Jx might exhibit good convergence properties towards Op as and μ go to zero. This contrasts with the problem encountered with (inaiv))- Those considerations are exactly what reproducing kernel Hilbert space will provide, additionally with computationally friendly framework to perform the estimation. Note that quantity similar to 9A,z were considered in 61
Spectral filtering. Without looking for higher power-norm, 33 proposed overcome the capacity issue by considering approximation of the operator L based on the graph-based technique provided by 4 and to reduce the search of gn, on the space spanned by the first few eigenvectors of the Laplacian. In particular, on Figure [ g" could be searched in the null space of L. that is, among functions that are constant on each connected component of supp px. This technique exhibits two parts, the "unsupervised" estimation of L that will depend on the total number of data and the "supervised" search for 9p on the first few eigenvectors of L that will depend on the number of labels nig While, at first sight, this technique seems to be completely different than Tikhonov regularization ( it can be cast, along with gradient descent, into the same spectral filtering framework [30]. This point of view enables the use of wide range of techniques offered by spectral manipulations on the diffusion operator L.
This paper is motivated by the fact that current well-grounded semi-supervised learning techniques are implemented based on graph-based Laplacian, which a local averaging method that does not leverage smartly functional capacity. In particular, recalled earlier, graph- based Laplacian is known

---

to suffer from the curse of dimensionality, in the sense that the convergence of the empirical estimator È towards the L exhibits rate of convergence of order 11dd with d the dimension of the input space X [24]. In this work, we will bypass this curse of dimensionality by looking for g in smooth universal reproducing kemel Hilbert space, which will lead to efficient empirical estimates.
Spectral Filtering with Kernel Laplacian
In this section, approach Laplacian regularization from functional analysis perspective. We first introduce kernel methods and derivatives in reproducing kernel Hilbert space (RKHS). We then translate the considerations provided in Section 1.3 in the realm of kernel methods.
2.1 Kernel methods and derivatives evaluation maps
In this subsection, we introduce kernel methods (see 46 49] for more details Consider (H, (ts H
reproducting kemnel Hilbert space, that is Hilbert space of functions from X' to R such that
the evaluation functionals Lg + R; g - g(z) are continuous linear forms for any æ E X. Such forms can be represented by ha E H such that, for any g H. Lo(g) (kg, 9. A reproducing kernel Hilbert space can alternatively be defined from a symmetric positive semi- N and (æi)ign X the matrix (k(x,, (,),,, is symmetric positive semi-definite, by building (Kz)ze such that x(x,x')= = (kz, ) From a learning perspective, it is useful to use the evaluation maps rewrite H= (g0: :00:20 x + (kiz 0) 0 E H}. As such, kernel methods can be seen as "linear models" with features kn, allowing to parameterize large spaces of functions (34). In the following, differentiate seen as an element of H and go seen as its embedding in L.2_ To make this distinction formal, we define the embedding S (H, (+. 1Hx) + (L2 (2)) : > ge. as well as its adjoint S* (px) H.
definite kernel ks X + X IR, that is function such that for any
will
Given linear parametric model of functions go gx(x) = (0, 2 it possible to compute derivatives of go based on derivatives of the feature vector - think of H R2 and of kg = p(xx) as feature vector with : Rd + R². For E N with |a| = Eisa a% we have the following equality of partial derivatives, when k is 2 |a| times differentiable.
jlal
Dd go(x) = (0, D Dake),
where
D
(0zz) na (0zz) ... (ax.)os
Here and Dd has to be understood as the partial derivative of the mapping of x E X' to kig E H. which can be shown belong H. [6I]. In the following, we assume that is twice differentiable with continuous derivatives, and will make an extensive use of derivatives of the form 0,kg = Ōk./ /dx; for i S d and x E X. Note that, as well we can describe completely the Hilbertian geometry the space Span (liz x X) through k(x,," (kiz, Kg). for Jr x'' X' we can describe the Hilbertian geometry of Span {kz x E X3 + Span (a,ka X), through
0, 01,k((r, x') =
-0 (8,kiz, kr) and
01.02,,k = (0,kiz, k
where 01,; denotes the partial derivative with respect to the i-th coordinates of the first variable. This echoes to so-called "representer theorems".
Example 1 (Gaussian kernel). A classical kernel is the Gaussian kernel, also known as radial basis function, defined for 0 as the following k, and satisfying, for $ j. the following equalities.
|| ||--x'11 x'1 (_1x-=²1
(x, u)(2,, 4/) k(x,)),
(x,x') = exp
01,02,,(z,u))
20
(xi Vi) k(k,
(x: y1) 0²
01,
0r,02,,(I,H)
((Zz,))
0²
where I; designs the i-th coordinates of the vector a E X Rdd
5

---

Eigen vector #1 (e1)
Eigen vector #4 (e4)
Eigen vector #8 (es)
Figure 2: Few of the first generalized eigenvectors of (É; L + pf) (with 1/n). The first four eigenvectors correspond constant functions each circle, shown with en and The few eigenvectors after correspond second harmonics localized on single circle shown with es.
2.2 Tikhonov, spectral filtering and dimensionality reduction
Given the kemnel k; its associated RKHS H and S the embedding of H in I22, rewrite Eq. under its "parameterized" version
||50 9pll12((x) + > + Ss
Ap 1101
9A.. S arg min
[e(px)
not hesitate to refer to Table T to keep track of notations. In the following, we will use that ||/// [P(ex))
|0 (SS CS //)=/2011 This equality explains why we consider μd instead of y in the last term. In the RKHS setting, the study of Eq. (4) unveils the three operators E, L. and on H. (indeed IA,, S arg mingen {6" (B-(E= XL Aua 20 S* 9' where / is the identity, and, as we detail in Appendix
= = Ex<px [ex & kx],
and
L L= CS = Ex~ex
Σ 0,kx 8 00
(6)
Regularization and spectral filtering have been well-studied in the inverse-probles literature. In particular, the regularization Eq. (4) is known to be linked with the generalized singular value decom- position of [E; L μu] (see, e.g.. (18), which linked the generalized eigenvalue decomposition of (E, L + uI) (22]. We derive the following characterization of Eq. (4), whose proof is reported in Appendix D
Proposition 1. Let (Aig)ieN E IR, (Oi,,)iEns E H be the generalized eigenvalue decomposition of the puir (E, + pl), that is (0i,) generating H and such that for any i, E N, Σ0,,a (L
limj. (L + pl 0i. and (Oi,gs e (L + pl Oznr) =limj. Eq. (4) can be rewrillen
Σ
(Sr,)) 8 S0 90
T ((un)) (S* 9p. 0x,) S0
(7)
iEN
with v) RR, R: based filter function
2) Eq. IR+ R.
should be seen as a specific instance of spectral filtering
Interestingly, the generalized eigenvalue decomposition of the pair (E, L++u)) was already considered by Hillaud-Vivies [40] to estimate the first eigenvalue of the Laplacian. Moreover, Pillaud- Vivien [4] suggests leverage this decomposition for dimensionality reduction based on the first eigenvectors of the Laplacian. As well as Eq. (4) contrasts with graph-based sumi-superviied learning techniques, this dimensionality reduction technique contrasts with methods based on graph Laplacian provided by 1[4. Remarkably, the semi-supervised learning algorithm that consists in using the unsupervised data to perform dimensionality reduction based on Laplacian eigenvalue decomposition, before solving a small linear regression problem on the small resulting space, can be seen specific eigenvalue, which
instance of spectral filtering, based on regularization by thresholding/cutingg corresponds to & x 1,sa for given threshold À 0 in Eq. (
3 Implementation
In this section, we discuss on how to practically implement estimates for Eq. 7 based on empirical data (X,, Y))isn and (Xi)nysisn We first review how we approximate the integral operators of

---

Eq. (6) based on data. We then discuss on how to implement our methods practically on computer. We end this section by considering approximations that allow cut down high computational costs associated with kernel methods involving derivatives.
Algorithm 1: Empirical estimates based on spectral filtering.
Data: (X,, Yi)igne (Xi),, <iss, a kernel k. filter vi regularizer μ
Result: Or through E IRP defining (p(x) = Ei= Cak(2r, X₂) = Taa
Compute S, To = (k(X,, X,) kensssss E g=xP in (pm)
Compute Z Ta
(X,, X, (s))ssdds E IRd in (pmd)
Build 2 ETa =n (S, ( in O(p2n)
Build T LTT = (Z, (Zn Tn Ta) Opp2nd
Build T.
Ky))sspp E RPxP in (()) partial copy of S,
Get (Ni, Ui,y)sgn the generalized eigenelements of (T) (TrÉTa, Ta (L pl)Ta) in O(p))
Get = TgO = (nr EE Y, xyp E TR in Opme)
Return c = ΣT= (Ajju, E R in Opp')
"Building this matrix can be avoided by using the generalized singular value decomposition rather than the generalized eigenvector decomposition. Implemented with Lapack, such a procedure will also requires O(p2rad) floating point operations, but with a smaller constant in the big O 22
3.1 Integral operators approximation
The classical empirical risk minimization in Eq. (5) can be understood the plugging of the approximate distributions أ = n Σi= ōx, @ ōy; and Px "'= óx, instead of p and px in Eq. 4 It can also be understood as the same replacement when dealing with integral operators, leading to the three following important quantities to rewrite Eq. 7
Σ:=
Σ Ex, kx., = n
0,kx. & 0fkx. == nz
Yix, (8)
It should be noted that while considering n in the definition of E is natural from the spectral filtering perspective, to make formally equivalent with the empirical risk minimization (5). it should be
replaced by ny. Eq. (8) allows to rewrite Eq. (7) without relying on the knowledge of p. by considering (Ai,p pt) the generalized eigenvalue decomposition of (2, L) and considering
Σ (hina)) ( (Stgpr 0.m)) S0..r IEN
We present the first cigenvectors (after plunging them in L through S) of the generalized eigenvalue decomposition of (É, f. + μT) on Figure 2 The first eigenvectors allow to recover the null space of L. This explains clearly the behavior on the right of Figure
3.2 Matrix representation and approximation of operators
Currently, we dealing with operators (É, L) and vectors (e.g., 0) in the Hilbert space H. It is natural to wonder on how to represent this on a computer. The answer is the object of representer theorems (see Theorem 1 of [61],, and consists in noticing that all the objects introduced are actually defined in, or operate on, H. + Hn,a C H. with Hn = Span (kx, i I n} and Hn = Span (0,kx, i & n.j S d). This subspace of H is of dimension at most nidd + 1) and if T: Rp H.. + Hn.a (with p S n(d + 1)) parameterizes Hi + Ho.a. our problem can be cast in IR by considering the p matrices TT and (ī + uI)T instead of the operators E and L + ul. The canonical representation consists in taking p = 12(d + 1) and considering for E IR=(d+1), the
nd mapping T.c- ΣT. cookx E k,j,,kx 61 44
This exact implementation implies dealing and finding the generalized eigen value decomposition of p x p matrices with p = nid + 1), which leads to computational costs On3d))) which can be prohibitive. Two solutions are known to cut down prohibitive computational costs of kernel methods.
7

---

Both methods consist in looking for space that can be parameterized by I" for a small and that approximates well the space Hn, + Hn.a C H. The first solution is provided by random features [42] It consists in approximating H with a space of small dimension p E N, linked with an explicit
representation y X -> TRe that approximate k(x, x') = (x, x²) (f( spxx)))))))))))))) (z))) In theory, substitutes the kernel k by kgg. In practice, all computations can be done with the explicit feature yp.
Approximate solution. The second solution, which we are going to use in this work, consists in approximating Hn. + Hn,o by Hp Span (ep for p S n. This method echoes the celebrated Nyström method [55], as well as the Rayleigh-Rizz method for -iovvlLio problems. In essence, 45 shows that, when considering subsampling based on leverage score, p = n² log(n). with 7 E (0, 1] linked to the "size" of the RKHS and the regularity of the solution, is a good enough approximation, in the sense that it only downgrades the sample complexity by a constant factor. In theory, we know that the space Hpp will converge to H Closure Span {ka] resuppp ex p goes to infinity. In practice, it means considering the approximation mapping Ta TRP - Hic Ei Gaxx,, and dealing with the p X p matrices ETT,, and T: L.T.- It should be noted that the computation of T LTa requires to multiply p nd matrix by its transpose. Overall, training this method can be done with (pd"nd) basic operations, and inference with this method can be done in Opp). The saving cost of this approximate method is huge: without compromising the precision of our estimator, we went from (nndd*) run time complexities to ([log()) 1 computations. with y possibly very small. Similarly, the memory cost went from O(n dd) down to O(nd + n
4 Statistical analysis
In this section, we are interested in quantifying the risk of the learnt mapping 9. We study it through the generalization bound, which consists in obtaining a bound on the averaged excess risk Edata وا - gpll In particular, we want to answer the following points.
1. How, and under which assumptions, Laplacian regularization boost learning? 2. How the excess of risk relates to the number of labelled and unlahelled data?
In terms of priors, we want to leverage a low-density separation hypothesis. In particular, we can suppose that when diffusing 9, with e -tc we stay close to 9p, or that 9p is supported on a finite dimensional space of functions on which || || /|] (which measures the variation of g) is small. Both those assumptions can be made formal by assuming the 9p is supported by the first eigenvectors of the diffusion operator L.
Assumption (Source condition). 9p is supported on a finite dimensional space that left stable by the diffusion operator L. In other terms, if (es) E (I.2)% are the eigenvectors of L, there exists r E N. such that 9p E Span {elherr
We will also assume that the diffusion operator L can be well approximated by the RKHS associated with k. In practice, under mild assumptions, c.f. Appendix C the eigenvectors of the Laplacian are known to be regular, in particular to belong to Hm for m E N bigger than d. As such, many classical kernels would allow to verify the following assumption.
Assumption (Approximation condition). The eigenvectors (et) of L belongs to the RKHS H.
We add one technical assumptions regarding the eigenvalue decay of the operator Σ compared to the A is
operator L, with < denoting the Löwner order (i.e., for and B symmetric, A < B if
positive semi-definite.
Assumption 3 (Eigenvalue decay). There exists a E [0, 1] and > 0 such that L - c.n
Note that, in our setting. L is compact and bounded and Assumption is always satisfied with For translation-invariant kernel, such as Gaussian or Laplace kernels, based on considerations linking eigenvalue decay of operators with functional space capacities [49), under mild assumptions, we can take - 2/d. We discuss all assumptions in more details in Appendix C
To study the consistency of our algorithms, we can reuse the extensive literature on kernel ridge regression [10 30 This literature body provides an extensive picture on convergence rates relying
'Our code is available online at httts:///tthhoooo//////eaaaa/aaa

---

Classification error
Computational complexity
0.4
kemelized graph-bused
Training time (8)
10
small kemel
Loss (0-1)
graph-hased
10"
0.2
10-3
10c
10
10
10a
10a
Number of samples
Number of samples
Figure 3: (Left) Comparison between our kemeliied Laplacian method (Tikhonov regularization version with À = 1, Mm, = n -1 p 50) and graph-based Laplacian based on the same Gaussian kernel with handwidth dn n - उ log(n) suggested by graph-based theoretical results 24 We report classification emrrr functiin of the number of samples The error is averaged over 50 trials, with errorbars representing standard deviations. We fixed the ratio Tu n to one tenth, and generated the data according to two Gaussians in dimension d = 10 with unit variance and whose centers are at distance 5 = 3 of cach other (similar to the setting of [1 29)). Our method discovers the structure of the data much faster than graph-bascl Laplacian (to get 20% error need 40 points, while graph-baser based need 700). (Right) Time to perform training with graph-basee Laplacian orange, with Algorithm I blue (with the specification of the left figure), and with the naive representation in R R=((+1)) of the empirical minimizer Eq. (5) in green. When dealing with 1000 points, algorithm, as well graph-based Laplacian, can be computed in about one tenth of second on a GHz processor, while the naive kernel implementation requires 10 seconds. We show in Appendix that this cut costs is not associated with loss in performance.
on various filters and assumptions of capacity, a.k.a effective dimension, and source conditions. Our setting is slightly different and showcases two specificities: (i) the eigenelements (Ar, Pi,,.) are dependent of μæ (ii) the low-rank approximation in Algorithm I specific to settings with derivatives. We end our exposition with the following convergence result, proven in Appendix [ Note that the dependency of in n can be improved based on subsampling techniques that leverage expressiveness of the different (kx,)) 45 Moreover, universal consistency results could also be provided when the RKHS is dense in H as well as convergence rates for other filters and laxer assumptions which we discuss in Appendix E (in particular, the source condition can be relaxed by considering the biggest
2 E (0, 1] such that y im L9).
nor n E N, when considering Theorem (Convergence rates), Under Assumptions 7 and for ne, the spectral filterigg Algorithm with thx : x - (x + X) there exists a constant C independent of n, ng X y and p such that the estimate Op defined in Algorithm 7 Verifies
ED, [10p - 90 90l s cx Ap
on
nnn" + n
log(p) 1o8(1))) pa
(10)
Ap
with of is a variance parameter that relates to the variance of the variable Y + -6x. inheriting its randomness from (X,Y) p. In particular, when the ratio = ne/n is fixed, with the regularization scheme An = Aan 11/, pnn pon 1/4, for any No > 0 and pa > O, and the subsampling scheme pn. = Pyn" (n) for any po > 0 and with s = max(1/2, 1/2a), there exists a constant C' independent of n and n4 such that the excess of risk verifies
ED. [100 - g0llia]] s 12
(11)
Theorem I answers the two questions asked at the beginning of this section. In particular, characterizes the dependency of the need for labelled data to variance parameter linked with the diffusion of observations (X,, Y,) based on the density Px through the operator C. Finally, Theorem I is remarkable in that it exhibits no dependency to the dimension of X' in the power of n and ng- This contrasts with graph-based Laplacian methods that do not scale well with the input space dimensionality 5 24 Indeed, Figure 3 shows the superiority of our method over graph-based
Laplacian in dimension 10, with mixture of Gaussians. We provide details as well as additional experiments in Appendix
B

---

Conclusion
Diffusing information or enforcing regularity through penalties on derivatives are natural ideas to tackle many machine learning problems. Those ideas can be captured informally with graph-base base techniques and finite element differences, or captured more formally with the diffusion operator we introduced in this work. This formalization allowed us to shed lights on Laplacian regularization techniques based on statistical learning considerations. In order to make our method usable in practice, we provided strong computational guidelines to cut down prohibitive cost associated with a naive implementation our methods. In particular, we were able to develop computationally efficient semi-supervised techniques that do not suffer from the curse of dimensionality.
This work paves the way to many extensions beyond semi-supervised learning. For example. in Appendix A we describe its usefulness to the partial supervised learning problem, where minimizing the Dirichlet energy provide a learning principle, in order to bypass the restrictive con-ambiguity assumption usually made in this setup [5] 31 7 8 Moreover, in the context of active learning, retaking the strategy of Karzand and Nowak [27], this energy provides a computationally--ffee theoretically--roune
data-dependent score to select the next point to query. As such, follow-ups would be of interest see how this introductory theoretical paper makes its way into the world of concrete applications.
Acknowledgments and Disclosure of Funding
This work was funded in part by the French government under management of Agence Nationale de Recherche part of the "Investissements d' d'avenir" program, reference ANR-19-P3IA-000) (PRAIRIE 31A Institute). We also acknowledge support of the European Research Council (grants SEQUOIA 724063 and REAL 94790).
References
[1] Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin Wainwright, and Michael Jordan. Asymptotic behavior of by-based Laplacian regularization in semi-supervised learning. In Conference on Learning Theory, 2016.
[2] lean-Baptiste Alayrac, Piotr Bojanowski, Nishant Agrawal, Josef Sivic, Ivan Laptev, and Simon Lacoste-Julien. Unsupervised learning from narrated instruction videos. In Conference Computer Vision and Pattern Recognition, 2016.
[3] Nachman Aronszajn. Theory of reproducing kemels. Transactions of the American Mathemati- cal Society, 1950.
[4] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 2003.
[5] Yoshua Bengio, Olivier Delalleau, and Nicolas Le Roux. Label propagation and quadratic criterion. In Semi-Supervised Learning. MIT Press, 2006.
[6] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin Raffel. Mixmatch: holistic approach to semi-supervised learning. Neural Information Processing Systems, 2019.
[7] Vivien Cabannes, Alessandro Rudi, and Francis Bach. Structured prediction with partial labelling through the infimum loss. In International Conference on Machine Learning, 2020.
[8] Vivien Cabannes, Alessandro Rudi, and Francis Bach. Disambiguation of weak supervision with exponential convergence rates. In International Conference on Machine Learning, 2021.
[9] Vivien Cabannes, Alessandro Rudi, and Francis Bach. Fast rates in structured prediction. In Conference on Learning Theory, 2021.
[10] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 2006.
10

---

[11] Vittorio Castelli and Thomas Cover. On the exponential value of labeled samples. Pattern Recognition Letters, 1995.
[12] Lin Chen and Sheng Xu. Deep neural tangent kemel and Laplace kernel have the same RKHS. In International Conference on Learning Representations, 2021.
[13] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A general framework for consistent structured prediction with implicit loss embeddings. Journal of Machine Learning Research, 2020.
[14] Ronald Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 2006.
[15] Timothée Cour, Benjamin Sapp, and Ben Taskar. Learning from partial labels. Journal of Machine Learning Research, 2011.
[16] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. Imagenet: A large-scale hierarchical image database. Computer Vision and Pattern Recognition, 2009.
[17] Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In North American Chapter the Association,fe for Computational Linguistics: Human Language Techmologies, 2019.
[18] Alan Edelman and Yuyang Wang. The GSVD: where are the ellipses?, matrix trigonometry. and more. Journal on Matrix Analysis and Applications, 2020.
[19] David Eriksson, Kun Dong, Eric Hans Lee, David Bindel, and Andrew Gordon Wilson. Scaling Gaussian process regression with derivatives. In Neural Information Processing Systems, 2018.
[20] Evelyn Fix and Joseph Hodges. Discriminatory analysis. nonparametric discrimination: Consis- tency properties. Technical report, SAF School of Aviation Medicine, Randolph Field, Texas, 1951.
[21] Nicolás Gareía Trillos, Moritz Gerlach, Matthias Hein, and Dejan Slepčev. Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator. Foundations of Computational Mathematics, 2019.
[22] Gene Golub and Charles Van Loan. Matrix computations (4th editions). Johns Hopkins University Press, 2013.
[23] Yves Grandvalet. Logistic regression for partial labels. In 9th Information Processing and Management of Uncertainty, 2002.
[24] Matthias Hein, Jean-Yve Audibert, and Ulrike Luxburg. Graph Laplacians and their convergence on random neighborhood graphs. Journal of Machine Learning Research, 2007.
[25) Eyke Hüllermeier, Johannes Fürnkranz, Weiwei Cheng, and Klaus Brinker. Label ranking by learning pairwise preferences. Artificial Intelligence, 2008
(26] Rong Jin and Zoubin Ghahramani. Learning with multiple labels. In Neural Information Processing Systems, 2002.
[27] Mina Karzand and Robert Nowak. Maximin active learning in overparameterized model classes. IEEE Journal on Selected Areas in Information Theory, 2020.
[28] Andrey Kolmogorov and Vladimir Tikhomirov. s-entropy and e-capacity of sets in functional spaces. Uspekhi Matematicheskikh Nauk, 1959.
[29] Mare Lelarge and Léo Miolane. Asymptotic Bayes risk for Gaussian mixture in semi- supervised setting. In International Workshop on Computational Advances in Multi-Senson Adaptive Processing, 2019.
[30] 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, 2020.

---

[31] Li-Ping Liu and Thomas Dietterich. Learnability of the superset label learning problem. In International Conference on Machine Learning. 2014.
[32] Xinghua Lou and Fred Hamprecht. Structured learning from partial annotations. International Conference Machine Learning. 2012.
[33] Jie Luo and Francesco Orabona. Learning from candidate labeling sets. In Neural Information Processing Systems, 2010.
[34] Charles Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine Learning Research, 2006.
[35] Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivic. Howtol 00m: Learning text-video embedding by watching hundred million narrated video clips. In International Conference on Computer Vision, 2019.
[36] Stanislav Minsker. On some extensions of Bernstein's inequality for self-adjoint operators. Statistics & Probubility Letters, 2017.
[37] Boaz Nadler, Nathan Srebro, and Xueyuan Zhou. Statistical analysis of semi-supervised learning: The limit of infinite unlabelled data. In Neural Information Processing Systems, 2009.
[38] Nam Nguyen and Rich Caruana. Classification with partial labels. In 14th International Conference on Knowledge Discovery and Data Mining, 2008
[39] George Papandreou, Liang-Chie Chich Chen, Kevin Murphy, and Alan Yuille. Weakly-and semi- supervised learning of a deep convolutional network for semantic image segmentation. In International Conference on Computer Vision, 2015.
[40] Loucas Pillaud-Vivisn Statistical estimation of the poincaré constant and application to sampling multimodal distributions. In International Conference on Artificial Intelligence and Statistics, 2020.
[41] Loucas Fillau-Viviess Learning with Reproducing Kernel Hilbert Spaces: Stochastic Gradient Descent and Laplacian Estimation. Phd thesis, Ecole normale supérieure, 2020.
[42] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Neural Information Processing Systems, 2007.
[43] Philippe Rigollet. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 2007.
[44] Lorenzo Rosasco, Silvia Villa, Sofia Mosci, Mattco Santoro, and Alessandro verri. Nonpara- metric sparsity and regularization. Journal of Machine Learning Research, 2013.
[45] Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco. Less is more: Nyström computa- tional regularization. In Neural Information Processing Systems, 2015.
[46] Berhhard Scholkopf and Alex Smola. Learning with kernels: support vector machines, regular- izution, optimization, and beyond. MIT press, 2001.
[47] Alexander Smola and Risi Kondor, Kernels and regularization on graphs. In Conference on Computational Learning Theory, 2003.
[48] Boumediene Hamzi Stefan Klus, Feliks Nüske. Kernel-based approximation of the koopman generator and schrödinger operator. Entropy, 2020.
[49] Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer, 2008
[50] James Tobin. Estimation of relationships for limited dependent variables. Econometrica, 1958.
[51] Alan Turing. Computing machinery and intelligence. Mind, 1950.
[52] Jesper van Engelen and Holger Hoos. A survey on semi-supervised learning. Machine Learning Journal, 2020.
12

---

[53] Jakob Verbeek and William Triggs. Scene Segmentation with CRFs Learned from Partially Labeled Images. In Neural Information Processing Systems, 2008.
[54] Vikas Verma, Alex Lamb, Juho Kannala, Yoshua Bengio, and David Lopez-Paz. Interpolation consistency training for semi-supervised learning. In International Joint Conference on Artificial Intelligence, 2019.
[55] Christopher Williams and Matthias Seeger. Using the Nyström method to speed up kernel machines. In Neural Information Processing Systems, 2000.
[56] Yuhong Yang. Minimax nonparametric classification. Rates of convergence, IEEE Transac- tions on Information Theory, 1999.
[57] Hsiang-Fu Yu, Prateek Jain, Purushottam Kar, and Inderjit Dhillon. Large-scale multi-label learning with missing labels. In International Conference on Machine Learning, 2014.
[58] Vadim Vladimirovich Yurinskii. On an infinite-dimennioonll version of N. Bernstein's inequalities. Theory of Probability and Its Applications, 1970.
[59] Mingyuan Zhang and Shivani Agarwal. Bayes consistency H-consistency: The interplay be- tween surrogate loss functions and the scoring function class. In Neural Information Processing Systems, 2020.
[60] Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Neural Information Processing Systems, 2003.
[61] Ding-Xuan Zhou. Derivative reproducing properties for kernel methods in learning theory. Journal of Computational and Applied Mathematics, 2008
[62] Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In International Conference of Machine Learning. 2003.
13


Reviews:
[{"review_id": "XMqZVSeSX-P", "reviewer": "Reviewer_UNaU", "summary": "This paper considers the problem of semi-supervised learning using Laplacian regularization. The authors use principles and methods from RKHS to mitigate issues with the curse of dimensionality. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper appears to be original and is tackling an important problem. The experiments seem correct and support the authors' claim.\n\nMy main complaint is that the paper is highly technical. While technical papers are welcomed at NeurIPS, I think it could be made a bit more accessible to the general NeurIPS community. As it stands, it seems the paper will be mostly of interest to those who are deeply in this field. Perhaps some of the technical results could be summarized better with details left for the supplementary material and more experiments moved to the main paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "8oMjavaNp2K", "reviewer": "Reviewer_YQhQ", "summary": "The paper proposes a novel Laplacian regularization method for semi-supervised learning that incorporates an additional penalty term that constraints the learned function to be in a smaller, smoother, RKHS. They characterize their approach via a spectral filtering perspective, provided an approximation that improves the computational complexity in the generalized eigendecomposition, and provided a convergence rate bound under several assumptions that they clearly identified. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "I believe that semi-supervised learning and Laplacian regularization are significant problems of broad interest. \n\nThe exposition is clear, and the paper is well organized and well motivated. The technical/mathematical parts of the paper are well written and a pleasure to read. \n\nThe authors provided ample background information and motivated their problem clearly, proposed their regularization method, provided different characterizations of their method, and provided a computational approximation that offers a big speedup in computing the eigendecomposition. They outlined their assumptions clearly and provided statistical guarantees. \n\nThis is a good quality theory/methods paper. \n\nSeveral comments: \n1. In figure 3b (the subfigure on the right), the computational complexity of small kernel and graph based Laplacian appear to be similar (with the graph-based laplacian appear to be slightly faster than the small kernel)....perhaps in that figure the dimension is not high enough? I would expect that the proposed method with the approximation proposed should scale better computationally than naive Laplacian regularization as dimension scales higher. If so perhaps this can be illustrated with a plot of computational complexity comparison of said methods as you try different dimensions along the x axis? \n\n2. Optimality of bounds: I understand that lower bounds are difficult to show (I certainly don't expect a lower bound to be included in the revision of this paper), but I wonder whether the authors have anything to say about the optimality of their statistical guarantees. Perhaps an easier way to give evidence of how tight their upper bound is is to do some simple simulations under very ideal settings and plot the empirical results along with your bound to show that your bounds are perhaps not (too) loose. \n\n3. Simulations: I understand that this is largely a theory/methods paper, but I do think more simulations/experiments could help make the case more compelling. For one, you mentioned the limitation of the work of El Alaoui et al in part of your motivation but did not provide comparisons against their methods in simulations/experiments. \n\n* A side note is that there is a typo in your reference : Your reference [1] contains only El Alaoui, but the actual paper has many more authors. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Since this is mainly a math/theoretical paper, I don't believe any potential negative societal impact is applicable here. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "0hq6gysKoAx", "reviewer": "Reviewer_Cz7V", "summary": "This paper addresses the settings of self-supervised learning, providing a new perspective on Laplacian regularization by restricting the solution to a reproducing kernel Hilbert space. They show this formulation leads to new efficient empirical estimates, and demonstrate their approach out-performs the classical graph Laplacian regularization, both in terms of accuracy and computational complexity.     \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The authors provide an interesting new solution to semi-supervised learning, by casting the classical Laplacian regularization typically used into an RKHS perspective. They provide both convergence rates as well as a practical algorithm for their new approach.  \nMy main concern with this paper is that it is ~40 page journal paper trying to squeeze into a dense 9 page conference paper + appendix. As such, the flow of the paper is hard to follow and useful insights and mathematical background that would be of use to the general reader are buried in the appendix, as are experimental results that are more interesting than those presented in the main text. For example, given the limited page length, is Figure 2 essential to the main text? Figures 4 and 5 in the appendix would be more important to demonstrate the performance of the approach.   \n\nMy second concern is the motivation. The authors claim the graph-based Laplacian is a technique that does not scale well with the dimension. In the text they clarify this statement in 2 places, once in lines 156-157 regarding the scaling of the convergence of the estimator of the graph Laplcian and once in the experimental results in setting the bandwidth of the Gaussian kernel. In practice, regularization with the graph Laplacian has been demonstrated successfully in a broad range of applications with high dimensional data: matrix factorization, convex clustering, dictionary learning, recommender system, data imputation, dimensionality reduction, etc., such that this theoretical concern seems of limited practical implications.  \n\nIn this context, how dependent are the experimental results on the kernel bandwidth used for the graph Laplacian? In practice, the bandwidth of the Gaussian kernel is typically set in a data-driven manner, such as the median distance of k-nearest neighbors of all points, or using an adaptive bandwidth such as self-tuning bandwidth (Zelnik-Manor and Perona), or multiple other possibilities. The bandwidth used by the author does not seem to depend in any way on the scale of the data itself. \n\nThe experiments themselves are synthetic and limited, mostly proof of concept, and more extensive experiments would be required to adopt the author’s approach which the authors state is their goal (I understand this is beyond the scope of the paper).\n\nThe paper doesn’t mention recent literature on RKHS in the graph signal processing field for data reconstruction, LMS solutions and spectral filtering:  \n* SEMI-PARAMETRIC GRAPH KERNEL-BASED RECONSTRUCTION† Vassilis N. Ioannidis, Athanasios N. Nikolakopoulos, and Georgios B. Giannakis\n* Kernel-based Reconstruction of Graph Signals Daniel Romero, Meng Ma, Georgios B. Giannakis\n* Adaptive Graph Filters in Reproducing Kernel Hilbert Spaces: Design and Performance Analysis, V. R. M. Elias, V. C. Gogineni, W. A. Martins and S. Werner\nAdditional missing references:\n* Semi-supervised learning on Riemannian manifolds, M Belkin, P Niyogi -\n* Regularization and semi-supervised learning on large graphs, M Belkin, I Matveeva, P Niyogi \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "These were addressed in the appendix and not in the main text.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper received positive reviews. However, only 3 out of 4 reviewers submitted a review, and therefore the AC very carefully read the paper on their own. They do share the positive impressions of the reviewers regarding novelty and they also think that for somebody familiar with the topic this paper is very accessible, while for others it is certainly a hard read. Their major concern regarding the paper is Assumption 1, which unfortunately has not been seen as an issue during the review/rebuttal phase. The main problem they see with Assumption 1 is that it is very restrictive, in fact much more restrictive than a usual source condition, as it explicitly assumes that the target function can be expressed by a finite number of eigenfunctions of the Laplacian, whereas "normal" source conditions are usually phrased in terms of an essentially polynomial decay of the Fourier coefficients. Even worse, the main result, Theorem 1, does not specify the dependence on the number of required eigenfunctions, and a quick look at the appendix did not resolve this issue. As a consequence, the AC views the main result, Theorem 1, as rather premature.

These concerns were discussed with the reviewers and SAC, and it was concluded that this paper should nonetheless be accepted. 1) the authors are attacking a problem of interest to the community; 2) they have some new non-trivial results; 3) the writing is good. The only concern is that the assumption made is not as nice as one might like. 
Decision: Accept (Poster)