ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions
Authors: Luigi Carratino
Stefano Vigogna
Daniele Calandriello
Lorenzo Rosasco
Venue: NeurIPS 2021 Poster (2021)
Keywords: Large-scale kernel methods
kernel ridge regression
random projections
partitions

Abstract: We introduce ParK, a new large-scale solver for kernel ridge regression. Our approach combines partitioning with random projections and iterative optimization to reduce space and time complexity while provably maintaining the same statistical accuracy. In particular, constructing suitable partitions directly in the feature space rather than in the input space, we promote orthogonality between the local estimators, thus ensuring that key quantities such as local effective dimension and bias remain under control. We characterize the statistical-computational tradeoff of our model, and demonstrate the effectiveness of our method by numerical experiments on large-scale datasets.

ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions
Luigi Carratino" MaLGa DIBRIS, University of Genova carraaiirrati unige. bagee.1 it
Stefano Vigogna"
MaLGa DIBRIS, University of Genova
vigognaédibris. unige.it
Daniele Calandriello
Lorenzo Rosasco
DeepMind Paris
MaLGa DIBRIS, University of Genova IIT. CBMM MIT
deallandrielll@googlee. com
1rosascodmit.edu
Abstract
We introduce ParK, new large-scale solver for kernel ridge regression. Our approach combines partitioning with random projections and iterative optimization to reduce space and time complexity while provably maintaining the same statistical accuracy. In particular, constructing suitable partitions directly in the feature space rather than in the input space, promote orthogonality between the local estimators, thus ensuring that key quantities such as local effective dimension and bias remain under control. We characterize the statistical statisticalccomputationaaa tradeoff of our model, and demonstrate the effectiveness of our method by numerical experiments on large-scale datasets.
1 Introduction
The development of provably accurate and efficient algorithms for learning is key to tackle modern large-scale applications. Kernel methods [31, 32] provide natural ground to develop this research direction. On the one hand they have sound statistical guarantees [7, 32, 33]. but on the other hand their basic implementations
limited to sample size of only few tens of thousands of points [32, Chapter 11]. Recent years have witnessed a growing literature introducing algorithmic solutions to improve efficiency, but also theoretical guarantees that quantify how accuracy is affected.
We next recall few lines of work relevant to our study. first line of work is based on exploiting ideas from optimization and numerical analysis. This includes for example gradient methods [37], as well as their accelerated [3], stochastic [10]. preconditioned [13] and distributed [27] variants. second line of work is based on using randomized approaches to reduce the size of the problem to be solved. This includes Nyström approximations [36], random features [25] and more generally sketching methods [1]. The theoretical properties of these methods have been recently characterized in terms sharp statistical bounds [28, 30]. Finally, a third line of work considers different partitioning strategies to divide the estimation step in smaller subproblems. This approach is based splitting the input space in regions where local estimators are defined [23, 35, 34, 11, 24, 5]. In this context, allowing the estimation of larger classes of functions. Another form of
the emphasis is typically partitioning, called divide-and-con -ovide-and-conquer, is instead based on randomly splitting the training data to then obtain global estimator by averaging [38, 20, 14]. In this approach, the focus is primarily computational saving. Notably, a number of works have considered combinations of these ideas, see for example [6, 29, 8, 24, 19].
equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this paper we propose and study a local kernel algorithm, called ParK, combining partitioning with iterative optimization and sketching. Our goal is to provide an efficient and accurate approximation to a global kernel ridge regression estimator. The main novelty in ParK is in the form of the considered partition, that we define in the feature space, rather than in the input space as in traditional partitioning methods. This allows to promote orthogonality between the local estimators, and thus to control the local effective dimension and the local bias. Given a partition, local kernel ridge estimators are computed using sketching and preconditioned conjugate gradient iterations [29]. From theoretical point of view, our main contribution characterizing the statistical properties of ParK, terms of conditions the partition and the choice of the ayper-parametert Borrowing ideas from subspace clustering [12]. we show that the minimal angle between suitable subspaces induced by the partition plays crucial role. Indeed, our analysis shows that, if such an angle is sufficiently large, ParK can achieve the same accuracy as global kernel ridge regression estimators, with only a fraction of computations, Our theoretical results complemented with numerical experiments very large datasets, which show that ParK can indeed provide excellent performances, on par and often better than the best available large-scale kernel methods.
The rest of the paper is organized as follows. In Section we state the problem and recall the basics of kernel ridge regression. In Section 3 we illustrate our algorithm. In Section 4 we analyze the prediction eπror of our method. In Section 5 we present the results of our numerical experiments. In Section 6 we draw some conclusions and report the main limitations of our work. Additional proofs and details are collected in Appendix A.
Background
Let (Iz, Us) with i E [n] = (1,...,,7 n be pairs of points in X' x V where X' C Rd with d E N and V S R. We assume the relation between input points 2; and output points ys to be determined by the noisy evaluations of an unknown function S. X + y as
y = f. (zx) + E i [n].
(1)
Based on the samples (t), we want estimate the function f., searching for solutions in suitable hypothesis space H as detailed below.
Let H. be reproducing kernel Hilbert space (RKHS), that is, a Hilbert space of functions with inner
product 2y and symmetric positive definite kernel K : X' x X + IR such that K2 = K K(x,-) E H and ((x (J, Ka)y for all ʃ E H. E X. We recall that, for every RKHS H. there exist Hilbert feature space ff and a feature map Φ X + F such that K(x,x') = (o(x), (((x))> for all X. The feature map not unique; in particular, one may take, as we do in all that follows, I, F= H and 6(x)= Kg. in which case H. span o(X'), where ((X) = (ő(x) x E X}.
Kernel ridge regression (KRR) corresponds minimizing
Σ (f(x.) vil + 11
min JEH
where À 0 and |l (f. fyM. By the representer theorem [31], the (unique) solution to problem (2) can be written as
Aa(x) Σ o ((;,a))) a a= (Kn Ann)
where a = (a......................... anl Y [y......, yn JT R", and K,, E Raxx is the kernel matrix defined by (Kn),, ((x,, .,) for i, E [n]. As consequence, the estimator (3) can be derived restricting the minimization problem (2) to the finite-dimensional subspace H. = span(á(1s)
i E [n]]- Computing (3) for large is prohibitively expensive, space and time complexities are, respectively, Onn²) and O(n²). The goal of this paper is to provide an algorithm to compute an efficient approximation to (3).
3 Algorithm
Our method combines diverse techniques, including partitioning, sketching and preconditioned iterative optimization. We begin focusing on partitioning. While classical partitioning methods

---

construct partitions in the input space, the main novelty of our approach is that we construct partitions the feature space. Note that, the case universal kernel on compact imput space, every feature map is injective [32, Lemma 4.53], hence every partition of the input space defines corresponding partition of the feature space. Thus, we may see our approach as generalization of classical input space partitioning approaches. As will become apparent from our analysis, the performance of partitioned kernel estimator depends crucially on two main quantities: the local biases and the local effective dimensions. Since both quantities are strictly related to the RKHS of choice, constructing partitions feature space allows for more direct control. In particular, promoting orthogonality in the RKHS metric will generate feature space partitions which tend minimize both the local biases and the local effective dimensions, In the next section we start discussing how such partitions can be defined.
3.1 Learning feature space partitions
For Q E N, we define a partition of d(2) as a family (Volee of subsets Vg S o(1) such that
(xx) = U Va
Vonv = a k.
(4)
q=1
The partition (4) induces a local subsampling of the training set and a local hypothesis space. Namely, define
[mlg {i E [m] d(x,) E VgJ. Hy span VoJ.
Also, we denote by mg # [m]] the local subsampling rate.
Voronoi partitions. Notice that far V, is an arbitrary subset of H. and therefore computing the set [r], can be arbitrarily difficult (e.g., V,, could be defined using an infinite number of constraints and be non-computablle. For this reason, although our theoretical analysis holds for any partition defined as in (4), we focus on the special case of Voronoi partitions, where the subsets (also called cells) are induced by set of Q centroids {Ø(cg)) with Cg X points in the input space. Then, each cell Vg uniquely defined as
Vq {Ø(z) arg min |lő(x) ((e))
ke(q)
with ties broken arbitrarily (c.g.. by assigning the point to the cell with the smaller q). It is now possible to identify the set indices [ni], using the RKHS distance
[|<(()) <(x')l)² K(x, 2) + (('','') 2K(x,
(5)
computing the distance each centroid and taking the minimum.
We remark that our approach based on directly partitioning the feature space has quite different implications compared previous approaches that partition the input space. For example, Voronoi partition of the feature space is very different from a Voronoi partition of the imput space, since the pre-image (x: X' Φ(x) Vg) does not need to follow any Voronoi shape. Moving from input to feature space partitions also opens new computational challenges. For example, we choose to explicitly represent the cell centroid d(c,) so that computing the distance and the assignment of each point to a centroid is a (11) operation. If instead we chose a more complex centroid, such as a cluster barycenter generated by kernel k-means, or an eigenvector computed by kernel PCA, this complexity might be much larger. As an example, the barycenter of a cluster of m points in H. might not correspond any single point in X, and therefore cannot be explicitely represented, but only implicitly as an average of m points in H. Therefore, computing distance to such a centroid O(1). These and more subtle pitfalls appear only when we
would be an O(m) operation rather than a consider the more flexible framework of feature space partitions.
Minimal principal angle. Focusing on partitions of Voronoi type, constructing a good partition is equivalent to choosing set of centroids that preserve the learning accuracy as much as possible. As we rigorously show in Section 4, this can be guaranteed by choosing centroids that maximize the minimal principal angle between subspaces. This quantity frequently appears in the analysis of
3

---

subspace clustering [12], and will be important for us to control both the bias and the variance of our estimator. The first principal angle between two linear subspaces and W of Hilbert space of inner product ( and norm is defined as
LU, W) min minnarccos(( (u, w)) u U, w W, ||||| = || = 13.
We call the minimal first principal angle between the subspaces Hg. that is,
min (Hzg H.x) qzt
(6)
Once again, for computational reasons cannot use direct optimization of this quantity in H as objective, since the optimal centroid placement might be impossible to express using points from X. Instead, to promote large principal angles and obtain centroids that computationally easy to handle, we consider the following greedy iterative procedure. Let X = {2s á E [m]]. Then (c),
C1 arg max K ((c, c),
Cq+1 arg
max CEX CEX (C
eEX
where
=
K(c,
is the Schur complement of candidate centroid with respect to the already selected centroids {cI,..., C. and K, E R2x4 is defined by (K,),, be efficiently computed using rank-1 updates. This strategy has been originally proposed by [9] with the goal of maximizing the volume spanned by the points in the feature space, which is achieved when the angle between all points selected large as required by our condition. Crucially, it is also easy to apply to RKHS's, since computing Schur complements involves only inner products. Beyond promoting large volume and orthogonality, the Schur complement also has important links with uncertainty estimation and spectral approximation. In particular, SCy (c) is also equivalent to the posterior variance of in a Gaussian process [26], and to the leverage score of e w.r.t. the already selected point in the context of randomized linear algebra [21].
Note that the inversion of K2 can
3.2 Learning local KRR estimators by sketched preconditioned conjugate gradient
For each cell of partition, local estimator Fg can be defined as the solution to the local KRR problem
min FEH, Thy kE(rig
Σ 1f(x;) - val + Ag 11fl
(8)
with A Given the local estimators Fap we then define a global estimator f by
= fy if ((x) E Vq-
(9)
Note that the evaluation of the global estimator at point needs only one local estimator.
Guidance on how to pick the values Ag in (8) will follow from our theoretical analysis. Meanwhile, focus on how to efficiently solve the minimization problems (8). Let X, {x, E X : [mly] Ro,xd and Y, {yr Y : (mlg) E R be the local subsets of input/output points, and let Kn, E Xn, be the local kernel matrix with entries (Kn,)i. = K(x;, for i, E [m]y-
Following the same ideas to derive (3), one could compute fy by
[x(x)=
Σ (ag), VEimly
(4qq (Kn, + T) "
(10)
This would already result in a smaller computational burden compared to the vanilla KRR estimator (3): the space and time complexities are now ((maxye(Q) n,,2) and O(EnE(a) 3) potentially with
My R. Moreover, additional saving in time can be obtained by distributing each task (10) over Q different machines, leading to (max, (Q) n2y time complexity. However, the scaling in n, is still quadratic and cubical. To improve these dependencies, we solve (10) only approximately, using the
FALKON algorithm proposed in [29]. To this end, we first need to introduce several key ingredients. While the following constructions hold in general for any set of points, here we adapt them to the partition setting outlined in the previous section.

---

Local Nyström subsampling, For each [Q], we consider a subset of my S ny points
X, fTg.1.... Tgmm, Xg sampled uniformly random from Xg- We then define Km, Rm by (Km,)i kis K (Tgg, (9g) for i, E [mg]] and Kn,m, E 1R Xma by (Kn,m,)is = K (Zi, for [m]g:]] [mg]]
(11)
Local Preconditioner. For each g E [Q]. we define the local (sketched) preconditioner Bg E Rmyxma as
Bg =
Bg Kmm + Xmn
mg
Conjugate gradient descent. We let Bg E Rm be the t-th iteration of conjugate gradient minimiz- ing
1
(3) = - -I ( B X33 (B, Km, Bg)
rgll2 -
(12)
T4
Finally, we define the local FALKON estimator
(z) = > By (
q [Q].
(13)
3.3 ParK
We are now ready to present ParK. Let (p(c)))g=1 with e2 X be the centroids of the cells (V₂) selected greedily according to (7), We define the ParK estimator as
=x) = Fz) if of)()) Vgg
(14)
The algorithm to train the above estimator (see Algorithm 1) consists of three main parts. The first such such that (o(c))) are the centroids of the cells; the second one identifies the subsets of points Xy. associated to each cell: the third one uses the FALKON algorithm to solve the local minimization problem (12) for each X,, Y, with g E [Q]. thus deriving the Q local estimators (13). prediction time, the algorithm first identifies which cell the test point belongs, and then proceeds using the local estimator of the selected cell to predict output (see Algorithm 2). Note that the RKHS distances in llne of Algorithm and line I of Algorithm 2) are computed using the polarization identity (5).
one greedily identifies the representative points (cy)
Algorithm ParK: Train
Require: Training set = (a:) E Raxd y (yi) E IR" numbers of local Nyström centers {mg]g=1 E Nº, local regularization parameters ( E R_, number of local iterations (ta)==1 (t ENQ
1
1: Initialize [n], = 0 for all q
[Q]
2: Greedily select (o(c,)) according to (7)
3: for f 1,
do
4: Compute ar argmin Φ [(((z,) o(c,)11
5: Update [n], [n], u (i)
6: end for
7: for 1,..., do
8: Select X, = (z, X ( and Y, {v E Y i [m]p]
9: Compute Fq.,, as in eq. (13) using X,, Y,
end for
11: Collect the local estimators Jan, and return the ParK estimator 7, as in eq. (14)
5

---

Algorithm 2 ParK: Predict
Require: Test point RR, local estimators ( " representatives of partition C' = (cg)g=1 [l((x) [l((x)
1: Select 7 argminge(q)
((c,)ll
2:
Evaluate (z,)(x)
The time complexity of training Park is log"n) to compute the centroids, ((Qn) to com- pute the indices [n]]g. and (gg) to compute each local estimator. Putting these quantities together we get OQQ²n n log(n) + Enero fg))))g)) in time, and (mmax m2²) in space. If we parallelize the training of the local estimators over Q machines, the time complexity further reduces to ( log(n) m QQ] ng)) In many practical scenarios, we can think Q as (11) For example, in all our experiments we take Q 32 (see Section 5). We compare the complexity of several KRR solver Table 1.
Table I: Computational complexity of some KRR solvers (up constants). For D&C and ParK, report the time complexity on Q parallel machines and the space requirement for each machine.
naive
iterative [37]
Nyström/RI [36, 25] FALKON [29]
D&C [38]
Park
space
n²
n²
m²
m²
(n/()²
max, my 2
time n
fn
m2n
tmn
(n/Q)$
Qonlog(n) + max, fy m, + max, my
test
Space partitioning vs data splitting
We conclude this section commenting on a different yet related distributed approach. As briefly recalled in the introduction, straightforward way to decompose the KRR problem is by simple split of the training data. For example, one can divide the samples uniformly at random into Q disjoint subsets of cardinality n, n/Q. Methods performing such step are known divide-and-conquer [38, 20, 14J. Consisting essentially in a block diagonal approximation of the kernel matrix, the resulting final estimator is an average of globally subsampled models. Divide-and-conquer methods are appealing due to the extreme simplicity the splitting procedure and the direct control of the subsampling rates ng. However, they suffer from worse approximation error (see discussion in [34]), and be expensive at test and evaluation time. On the other hand, partitions present several potential benefits. First, data splitting is byproduct of a geometric partition. This opens to the opportunity of exploiting the structure of the space, for instance enforcing notions of locality or orthogonality. Consistently, the final estimator is union of local estimators, opposed to average of global ones. Hence, partitioning may enhance the approximation power of the model, capturing relevant local correlations [23]. As another consequence, at evaluation time only one local estimator, instead of the average of all estimators, needs to be called, yielding further computational saving. These nice properties have motivated fruitful line of research, notably [23, 34, 24], where the advantage in the partitioning approach has been studied both in statistical and in computational terms. In this paper we concentrate on the computational aspects, expanding on theoretical tradeoffs outlined in [34, 24] and developing [24] with new algorithmic ideas.
4 Theory
To simplify the analysis and better highlight the new ideas in play, we consider the problem (1) in fixed design setting [2, 15], where the 24 are deterministic and the E; are independent and identically distributed random variables.
Let 1.2 Tp)(p) with p Em &..-- We may identify 1,2 with RD endowed with the inner product
(u, w) Lي = fu T w. We define the excess risk of an estimate π of f. in problem (1) as
1 Σ [xx - (x T
R() = 115 -.
(15)

---

We are interested in studying the performance of the estimator J, defined in (14) given partition (4), as measured by the excess risk (15). Our theory will suggest how to construct the partition and tune the regularization in order to get the best learning rate.
4.1 Definitions and assumptions
We start by defining some relevant operators global and local variants. view of (3) (and the fixed design setting), we assume without loss of generality that H = Hn. We define the covariance operator T H - as 1/ Eie(m) d(x,) & ((x)), where, for e, w E H, v @ w denotes the operator u E H + (u, H) E H. The operator T is standard in the analysis of kernel methods [7]. We now define the local version of the covariance operator conditioned on the partitioning (4). Thanks to (10) (and the fixed design setting), we can assume without loss of [mlg]- The local covariance operator Tç H. + H. is defined as T. 1 LieM., ((x;)) @ ((x)). We denote with P. H. + H. the orthogonal projection onto the Ri subspace H.g For all E [Q]. we let P. = nn/n. Recall that we denote by the minimal principal angle between the subspaces Hg. as defined in (6).
generality that Hg = (244)
To mcasure the capacity of the hypothesis spaces, we will use the standard notion of effective dimension [7].
Effective dimension. The (global) effective dimension of the space H is given by ((A Tr((T + IT)
A 0.
Consistently, we define the local effective dimension of each space Hg
N₂,(,,) = (T((T, + A,,) >,,) -T,)
Ag > 0.
We also define the local maximal degrees of freedom [2] as
o sup (ó(x), (T, + (x=)) =
Ag ~000
which gives the bound (An) S Noc.a (2e)) S sup, K xx), The effective dimension is related to the spectrum decay of the covariance operator, and thus it provides a way to quantify how many important eigenfunctions the RKHS contains. In this sense, serves as an implicit number of parameters for the nonparametric model represented by the RKHS. The interplay between global and local effective dimensions, hence between global and local model complexity, will play major role in our analysis. Similarly, there exist an interplay between local and a global version of the maximal degrees of freedom (A), which also connected to the coherence of the T operator, and to the concept of maximal leverage score [2].
We will need few basic assumptions.
Assumption 1. f. E H.
Assumption 2. x² = supzex K(x, x) < co.
Assumption 3. The noise variables E; are i.i.d. sub- nub-Gaussian of variance proxy 0² 00, i [m].
Assumption 3 is standard in the analysis of any regression model. In particular, uub-Gaussianity allows control the tails of the noise, and therefore to establish bounds in high probability. Bounded and Gaussian noise are examples, but any variable with sub- Sab-Gassiin tail is covered. Assumptions 1 and 2 are instead typical of kernel methods. With Assumption 1, we suppose that the RKHS is a well specified model. We stick to Assumption 1 for simplicity, but we could easily relax it assuming the existence of function in the RKHS with same excess risk as fa, or considering the excess risk with respect to the best in class. Assumption 2 allows to provide explicit bound for kernel related quantities, and ensures in particular that functions the RKHS are bounded.
4.2
Main results
Our first proposition generalizes the classical bias-variance tradeoff of KRR estimators incorporating iterative optimization, random projections and feature partitioning. The result a high probability bound for the excess risk of our ParK estimator.
7

---

Proposition 1. Let 8 E (0,1). Under the regression model (1) and the assumptions of Section 4.1,
let Jt, be the Park estimator as defined in (14). If for each q E [Q), 0 < Ag S kn?
SN²
40 (1
my 2 5[1 + 14N (Aa)) log(
2,
b 2 2log
then, with probability at least 1 46,
Q Ng + vNg(A,) log( 1/8) 1ogg(1/))
R(T,)) S 16
Σ q=1
PPaJalla Ap4 + 0²
The proof of Proposition is given in Appendix A.2. The bound consists of bias and variance term. The bias term is an average of local biases, measured by the projection the target function onto the local hypothesis spaces, regularized by local penalization. The variance term is essentially the ratio between the sum of local effective dimensions and the global sample size. We are going to control bias and variance in the next two propositions, whose proof is postponed Appendix A.3. For the bias, we prove the following generalized Bessel inequality. Proposition 2. With the definitions of Section 4.1, we have
Pat. $ Q2 cos co)(l)
Proposition bounds the possible redundancy of the local projections by the minimal principal angle between the local subspaces. In particular, if the local subspaces are an orthogonal decomposition of the global space, the partitioned estimator has no additional local bias. On the other hand, lack of orthogonality results in a larger bias. Turning to the variance, we obtain the following bound on the local effective dimensions.
Proposition 3. With the definitions of Section 4.1. 2g = =Ap= we have
Σ NG(W (1+ n2 9-1
A (0) N(A).
Once again, the minimal principal angle controls the ratio between local and global quantities. Where there perfect orthogonality, splitting the hypothesis space does not increase the effective dimension; otherwise, a price proportional to the minimal principal angle is paid. With the above results in hand, we can now control the excess risk the ParK estimator in terms of the global norm of the target function and the global effective dimension. This allows to compare the performance of our partitioned method to that of a typical global method.
Theorem 4. Let E (0, 1). Under the same assumptions of Proposition I, let q = argmin |E|Q] Pq. for 0 < X S paR2 when Xq Xp= for each E [Q], with probability at least - 46,
402
(1+12000=(0)
R(F.) & 16(1 + Q² cos cos( 1
((A)
If we consider a model where H. is the orthogonal sum of the subspaces Hep as [24], then (os = O, and the bound of Theorem 4 simplifies to R(T.) = OAI]s,111 (1))m-1) In particular, setting À ((1/v1)) optimal rate, in the minimax sense, for global KRR models [7]. Note that, in the orthogonal case, the constraint S Py translates to the minimal local point requirement n, Z vn for all g, and hence to bound on the partition size, namely Q S Vn. On the other hand, when the subspaces H. are perfectly orthogonal, our bound manifests Maaiisical-computationn tradeoff, which is however quantified by the minimal principal angle. Further, the constraints on the local number of Nyström centers my. iterations tg of Proposition 1, and the choice Xg = Ap with À = 1/vn to achieve the minimax rate, allows recover time complexity of O (Qen log(n) + Eve(Q) may vn
obtain the learning rate ((1//n) This is known to be the
log(
nl vn

---

Analyses of (input space) partitioned kernel estimators have been conducted within different models, such as Gaussian SVM's on Voronoi partitions [23]. general kernels on clusters [34], and block- diagonal kernels on arbitrary partitions [24]. In these works, the bounds are established in random design, for plain [23, 34] or Nyström [24] local KRR estimators. Our result in fixed design, but compared to [24] incorporates the additional algorithmic ingredient of iterative optimization. For perfectly orthogonal model (cos = 0), we recover the result in [24] as a special case (although in fixed design). In [34], the bias is controlled choosing same X, for all g. while the crucial bound of Proposition 3 is made as an assumption. Note however that, at least in our proof of Proposition 3, is important to choose differently scaled X for each cell. Furthermore, our analysis and numerical tests motivate that partitioning the feature space is key to control both local bias and local effective dimension. Rather than computational aspects, [23] focuses extending statistical optimality for functions of local smoothness. This theme is also explored in [34, 24]. However, since the proposed partitioning step is either unsupervised [23, 34] unspecified [24], improved rates be obtained only under oracle assumptions, that is, assuming that the smoothness of the target function is localized right on the cells of the chosen partition. Partitions adapting to the unknown local smoothness of the target function can arguably be learned only in a supervised manner. This has been done for piecewise polynomial regression drawing ideas from multi-resolution analysis [4, 18]. An application of these ideas for kernel methods is not straightforward due to the usual computational constraints, but could be subject of future work.
Experiments
In this section we study the performance of ParK on some large-scale datasets (n z 10 107, 10%). In particular we consider dataset where at the moment, because of their cardinality, only a few solvers can efficiently learn from. For this reason we compare to the global large-scale kernel method FALKON which has so far being the method that performs the best in terms of time and accuracy on these datasets [22]. A standard divide-and aeeee-nnd-couuee method can not run on these datasets (for the high space complexity), for this reason we compare with a version where each local estimator is sketched KRR estimator computed with FALKON. We run two different versions of this algorithm, D&C-FALK(vI) and D&C-FALK(v2), that differ only in their hyper-parameters choices as specified later in this section. We also consider a second version of ParK where the centroids of the partition's 's cells are chosen as {o(c,)] with Cg selected uniformly at randomly from the training data X (referred to ParK-Uni). For each experiment we report mean and standard deviation on 10 trials. The experiments are implemented in python using pytorch and the FALKON library [22]. The experiments run on machine with 2 Intel Xeon Silver 41 16 CPUs and 1 GPU NVIDIA Titan Xp. The ram of the machine is 256 GB. We perform experiments on the four large-scale datasets TAXI (n 10", d = 9, regression), HIGGS (n 10 d = 28, classification), AIRLINE (n 2 10 d = 8, regression), AIRLINE-CLS (n RV 105, d = 8, classification) with the same pre-processing and same random train/test split used in [22]. We do not cross validate hyper- prper-paraeeters of the local estimators of ParK. Instead we use the same used by FALKON in the paper [22] with the following exeptions: let be the global regularization parameters of FALKON and m the number of the Nyström points, the local estimators of ParK use regularization Ag Ap and my = mp, as suggested by the theory. D&C-FALK(v1) also follows the same rule for setting the hyper-parameters of its local estimators, while D&C-FALK centers which are 3m, in AIRLINE and AIRLINE-CLS, 5mg in HIGGS, and 6m in TAXI. The number of centroids used by ParK and D&C-FALK is Q 32 for all experiments. Performance for different Q values remains almost identical but worsen in time for higher values. Further, note that the local estimators of ParK and D&C-FALK are learned sequentially. We report in Table 2 the errors and times. In particular, for ParK(-Umi we report the initialization time that include the greedy algorithm to select the centroids (not for ParK- Uni) and the assignment of the training points to the corresponding cell, the sequential training times of the local estimators, and the total time of this pipeline.
uses the same of the (v1) version except the number of Nyström
We can see that ParK can match the accuracy of the global FALKON estimator with a smaller computational cost. ParK-Uni requires further less time, at the expense of some loss in accuracy, confirming that a worse partition can affect generalization, as suggested by our theory. The reason of the ParK-Uni speedup is twofold. First, the initialization step requires only to assign points to set of randomly selected centroids, and second, the local subsets of points have uniform cardinality (which is usually not the case for normal ParK). D&C-FALK(vI) is the algorithm with with smallest

---

Table 2: Accuracy and running time comparison on large-scale datasets.
TAXI
10"
HIGGS 10"
(MIN.)
ERROR (1-AUC)
(SEC.)
(RMSE)
INIT
TRAIN
TOTAL
INIT
TRAIN
TOTAL
PARK
312.0++0.2
25:11
39=13
64+13
0.182++0.001
30+2
474+172
504+172
PARK-UNI
315.7=00.6
5#1
13=1
18:1
0.192=00.000
3+1
67#7
70+7
FALKON
311.710.1
120.11
0.180.10.001
7151:
D&C-FALK(VI)
356.2100.
1411
0.21211.000
50:11
D&C-FALK(V2)
327.4+0.1
29:11
0.195=10.000
288+2
AIRLINE n 10
AIRLINE-CLS n 10
ERROR (MSE)
TIME (SEC.)
ERROR (C-BRR)
TIME (SBC.)
INIT
TRAIN
TOTAL
INIT
TRAIN
TOTAL
PARK
0.760:10.005
6111
71-99
77::10
31.5+0.2%
9+1
5516
6416
PARK-UNI
0.766=00.06
1+1
32=3
3343
31.6+022%
2+1
22422
24:2
FALKON
0.758++0.005
334+-2
31.5+002%%
391+5
D&C-FALK(Y 0.804
27+1
33.2+ %
20+1
D&C-FALK(V2)
0.799110.05
96111
32.210.1
7311
training time but achieve significantly worse performance using the same rule to choose the number of Nyström points of ParK. For this reason, in D&C-FALK(v2) we increase the number of centroid improve the performance, but the error of the method still results higher than the others with training time now higher than ParK.
6 Conclusions and limitations.
In this paper we have proposed a new algorithm for large scale kernel ridge regression. Our method integrates and jointly exploits three previously uncombined algorithmic strategies, namely partitions, sketching and (preconditioned) iterative optimization. Distinctively from traditional partitioned methods, have introduced the idea of partitioning the feature space, which allows to directly control and resolve the localization of the kernel model. We have presented a simple analysis that characterizes the statistical-comme conppuatccomtttinnnall trade-off of partitioned kernel estimator by the interplay of intuitive quantities. Moreover, we have demonstrated that our algorithm performs favourably against a sfate-ofthhee large scale global method.
The main theoretical limitation our work the lack of a result connecting the proposed partitioning algorithm the properties of the resulting partition. This seems to be a common gap the literature of partitioned kernel methods, where partitions are often assumed to be given or, if explicitly constructed, statistically characterized. While construction theoretically motivated by the analysis and practically validated by the experiments, an actual guarantee is missing. In particular, one could try to prove that the proposed greedy procedure would actually find a maximally orthogonal decomposition of the hypothesis space, under suitable assumptions. From an algorithmic point of view, we point out that the computational cost of the greedy algorithm limits the choice of the partition size. Indeed, large partitions accelerate the training step, but increase the initialization time. We remark, however, that our model is flexible enough include cheaper partitioning options. For example, our experiments show that uniformly chosen partitions can still produce good results.
A Acknowledgments and Disclosure of Funding
The authors thank Nicole Mücke for her useful feedback. This material is based upon work supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF- ICF-1231216 and the Italian Institute of Technology. We gratefully acknowledge the support of NVIDIA Cor- poration for the donation of the Titan Xp GPUs and the Tesla k40 GPU used for this research. L. R. acknowledges the financial support of the European Research Council (grant SLING 819789), and AAA-ARL---OOOR-200
the AFOSR projects FA9550-18-15 18-1-7009, (Furopean Office of Aerospace Research and Development), and the EU H2020-MSCA-RISS project NoMADS DLV-777826.
10

---

References
and [1] H. Avron, V. Sindhwani, and D. Woodruff. "Sketching structured matrices for faster nonlinear
regression". In: Advances in neural information processing systems. 2013, pp. 2994-3002.
[2] F. Bach. "Sharp analysis of low-rank kernel matrix approximations". In: Proceedings of the 26th Conference on Learning Theory (COLT) PMLR 30 (2013), pp. 185-209.
[3] F. Bauer, S. Pereverzev, and L. Rosasco. "On regularization algorithms in learning theory". In:
Journal of Complexity 23.1 (2007), pp. 52-72.
[4] P. Binev, A. Cohen, W. Dahmen, and R. A. DeVore. "Universal Algorithms for Learning Theory Part II: Piecewise Polynomial Functions". In: Constructive Approximation 26.2 (2007),
pp. 127-152.
[5] I. Blaschzyk and I. Steinwart. Improved Classification Rates for Localized SVMs. arXiv:1905.01555 2019.
[6] R. Camoriano, T. Angles, A. Rudi, and L. Rosasco. "Nytro: When subsampling meets early stopping".. In: Artificial Intelligence and Statistics. 2016, pp. 1403-1411.
[7] A. Caponnetto and E. De Vito. "Optimal rates for the regularized least-squares algorithm". In: Foundations of Computational Mathematics 7.3 (2007), pp. 331-368.
[8] L. Carratino, A. Rudi, and L. Rosasco. "Learning with SGD and Random Features". In: Ad- vances Neural Information Processing Systems. Ed. by S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett. Vol. 31. Curran Associates, Inc., 2018.
[9] L. Chen, G. Zhang, and E. Zhou. "Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity". In: Advances in Neural Information Processing Systems. Ed. by S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. R. Garnett. Vol. 31. Curran Associates, Inc., 2018.
[10] A. Dieuleveut and F. Bach. "Nonparametric stochastic approximation with large step-sizes".
In: The Annals of Statistics 44.4 (2016), pp. 1363-1399.
[11] F. Dumpert and A. Christmann. "Universal consistency and robustness of localized support vector machines" In: Neurocomputing 315 (2018), pp. 96-106.
[12] E. Elhamifar and R. Vidal. "Sparse Subspace Clustering: Algorithm, Theory, and Applications".
In: IEEE Transactions on Pattern Analysis and Machine Intelligence 35.11 (2013), pp. 2765- 2781.
[13] Gonen, Orabona, and S. Shalev-Shwartz. "Solving ridge regression using sketched preconditioned svrg". In: International Conference on Machine Learning. 2016. pp. 1397- 1405.
[14] Z.-. Guo, S.-B. Lin, and D.-X. Zhou. "Learning theory of distributed spectral algorithms", In: Inverse Problems 33.7 (2017), p. 074009.
[15] Hsu, M. Kakade, and T. Zhang. "Random Design Analysis of Ridge Regression", In: Proceedings of the 25th Annual Conference on Learning Theory (COLT) PMLR 23 (2012),
pp. 9.1.4.24
[16] D. Hsu, S. Kakade, T. Zhang, et al. "A tail inequality for quadratic forms of subgaussian random vectors". In: Electronic Communications in Probability 17 (2012).
[17] T. Klock, A. Lanteri, and Vigogna. "Estimating multi-index models with response- conditional least squares". In: Electronic Journal of Statistics 15.1 (2021), pp. 589-629,
[18] W. Liao, M. Maggioni, and S. Vigogna. "Multiscale regression unknown manifolds". In: Mathematics Engineering 4.4 (2022), pp. 1-25.
[19] J. Lin and V. Cevher. "Kernel Conjugate Gradient Methods with Random Projections". In: Applied and Computational Harmonic Analysis (2021).
[20] S.BB. Lin, X. Guo, and D.-X. Zhou. "Distributed Learning with Regularized Least Squares".
In: Journal of Machine Learning Research 18.92 (2017), pp. 1-31.
[21] M. W. Mahoney and P. Drineas. "CUR matrix decompositions for improved data analysis". In:
vol. 106. 3. 2009, pp. 697-702.
[22] G. Meanti, L. Carratino, L. Rosasco, and A. Rudi. "Kernel Methods Through the Roof: Handling Billions of Points Efficiently". In: Advances Neural Information Processing Systems. Ed. by H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin. Vol. 33. Curran Associates, Inc., 2020, pp. 14422-14422.

---

[23] M. Meister and I. Steinwart. "Optimal Learning Rates for Localized SVMs". In: Journal of Machine Learning Research 17.194 (2016), pp. 1-44.
[24] Mücke. "Reducing training time by efficient localized kernel regression". In: Proceedings
of the Twenty-Second International Conference Artificial Intelligence and Statisties. Vol. 89.
2019, pp. 2603-2610.
[25] A. Rahimi and B. Recht. "Random features for large-scale kernel machines". In: Advances in neural information processing systems. 2008, pp. 1177-1184.
[26] C. E. Rasmussen and C. K. I. Williams. Gaussian processes for muchine learning. Adaptive computation and machine learning. MIT Press, 2006. ISBN: 026218253X.
[27] D. Richards and P. Rebeschini. "Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up". In: Advances in Neural Information Processing Systems.
Vol. 32. 2019.
[28] A. Rudi, R. Camoriano, and L. Rosasco. "Less is more: Nyström computational regularization".
In: Advances in Neural Information Processing Systems. 2015, pp. 1657-1665
[29] A. Rudi, L. Carratino, and L. Rosasco. "FALKON: An optimal large scale kernel method". In: Advances in Neural Information Processing Systems. 2017, pp. 3891-3901.
[30] A. Rudi and L. Rosasco. "Generalization Properties of Learning with Random Features". In: Advances in Neural Information Processing Systems 30. 2017, pp. 3215-3225.
[31] Schölkopf and A. Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT Press, 2002.
[32] I. Steinwart and A. Christmann. Support vector machines. Springer-Vertee New York, 2008.
[33] I. Steinwart, D. R. Hush, C. Scovel, et al. "Optimal Rates for Regularized Least Squares Regression." " In: COLT, 2009,
[34] R. Tandon, S. Si, P. Ravikumar, and I. Dhillon. Kernel Ridge Regression via Partitioning. arXiv: DeXiv:1608.000 160..01976. 2016.
[35] P. Thomann, I. Blaschzyk, M. Meister, and I. Steinwart. "Spatial Decompositions for Large Scale SVMs". In: Proceedings of the 20th International Conference Artificial Intelligence and Statistics. Vol. 54. Proceedings of Machine Learning Research. PMLR, 2017, pp. 1329- 1337.
[36] C. K. Williams and M. Seeger. "Using the Nyström method to speed up kernel machines". In: Advances in neural information processing systems. 2001, pp. 682-688.
[37] Y. Yao, L. Rosasco, and A. Caponnetto. "On Early Stopping in Gradient Descent Learning". In: Constructive Approximation 26.2 (2007), pp. 289-315.
[38] Y. Zhang, J. Duchi, and M. Wainwright. "Divide and Conquer Kernel Ridge Regression:
A Distributed Algorithm with Minimax Optimal Rates". In: Journal of Machine Learning Research 16.10 6.1002 (2015), pp. 2390-
12


Reviews:
[{"review_id": "m-S-UTqlR8L", "reviewer": "Reviewer_gQRE", "summary": "\nThis work introduces a new approach to large scale KRR, ParK.\nThis approach relies on the combination of two main elements : \na Voronoi partition of the feature space that aims at maximizing the first principal angle  of the partition,\nand a careful use of the FALKON estimator.\nThe authors provide a theoretical upper bound of the risk of ParK, and compare the performance of ParK to FALKON on different experiments.\n ", "questions": "", "limitations": "", "rating": 5, "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": "While the use of the FALKON estimator is not new, the idea of splitting the feature space using a Voronoi partition is original (to the best of my knowledge), appears natural and yields interesting results.\nOn the one hand, I found the link between the first principal angle of the partition and the risk of the ParK estimator to be particularly insightful (Theorem 1, Prop 2 & 3). \nOn the other hand, the experimental evaluation seems a bit insufficient, and some statement could benefit from being clarified. These points are developed below. \nIf the authors can address these questions, I am willing to increase my  rating.\n\n## Questions :\n\n\n### Q1\nThe authors claim (line 161) that the complexity of finding the centroid is $O(Q^2n \\log n)$.\nHowever, given equation (6), shouldn't the complexity be $\\sum_q O (n q^3) \\approx O(nQ^4) $?\nindeed, each centroid requires the inversion of $K_q$, a matrix of size $q \\times q$.\nThis is particularly important in the case where $Q$ is comparable to $\\sqrt{n}$, discussed by the authors line 252-260, as it drastically changes the complexity of ParK.\n\n\n###  Q2\n I do not understand the inequality  line 208\n$$  \\mathcal{N}_{\\infty,q} \\le \\lambda_q^{-1} \\lambda_\\max{}(T_q)  $$\nShouldn't  $\\lambda_\\min{}(T_q)$ appear instead ? Can the authors elaborate on the proof of this inequality ?\n\n### Q3 \n\nWhile Assumption 1 is not unheard of in kernel theory, in this paper the authors also make the hypothesis \n$H=H_n$ . Hence, in the paper, the resulting assumption is $f_* \\in H_n,$  i.e. $ f_*$ can be perfectly estimated given the observations. This assumption seems too strong for me, can the authors discuss this question ? \n\n\n### Q4. About experiments\n\nWhile the results of the experimental evaluation look promising, the following elements appear to be missing.\n\n1.Which kernel  did the authors chose? This is particularly key for ParK, as the kernel also influences the partition. Also, it would be interesting to study the influence of the choice of the kernel, e.g. by trying multiple kernel on each datasets. \n\n2.In the experiments the authors limit themselves to $Q=32$.  As a consequence, $n_q$ is close to $n$, and the benefit of ParK on time complexity are more limited.  Can the authors elaborate on the consequences of $Q >> 1$ in practice ? \n\n3.Surprisingly, the loss of performance resulting from using random partitioning (Uni-Park) instead of Voronoi partitioning (Park) is small. Can the authors elaborate on the apparent  small benefits produced by their partitioning  method ?\n\n4.Finally, I think it would be particularly interesting to report the first principle angle of the partition in each dataset, and compare it to the results of ParK.\n\n=========================================\nUpdate after rebuttal.\n\nThank you for answering the questions, in particular for clarifying Q2. However, after carefully considering the authors' response, I still consider that the experimental evaluation of the method is lacking in its current form. Therefore I only change my evaluation from 4 to 5.  I suggest that the authors add all the new results they mentioned in their rebuttal to the paper for future submissions. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See questions above. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Z-2gK7o1bh6", "reviewer": "Reviewer_QUZt", "summary": "In nonparametric methods such as kernel ridge regression, the number of data is a bottleneck for calculation while large number is needed for the performance. The paper considers the partition of space to reduce the computation time by using the subset of data in each partition that the testing datum belongs to. The authors use the partitioning in the feature space by maximizing the minimal principal angle between partitions, and Determinantal Point Process (DPP) equation is used ensuring the diversity of subspaces.", "questions": "", "limitations": "", "rating": 7, "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": "The paper is clearly written and coherent with its objective from the motivations to the experiments. The objective is to reduce the computation complexity while preserving the accuracy with many data. In the experiment, the authors showed the result with up to 10^9 number of data, reducing the calculation time significantly while preserving the prediction performance.\n\nThe algorithms are reasonable including the choice of DPP equation for selecting centroids.\n\nFor minor comments, the authors need more explanations about their experiments to ensure the reproducibility. For example, authors did not provide the source of datasets including the TAXI having 10^9 number of data. \n\nThe authors commented that they used GPUs. Explanations have to be provided which part of the algorithm is implemented by GPUs. That is an important explanation because calculation time is an important metric in this work.\n\nThe reduction of calculation time varies for different datasets. For TAXI, the reduction is half while it is 1/5 for AIRLINE-CLS. If the authors used commonly the 32 partitions for all datasets, why the time reductions are different? And why the reduction is not 1/32?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. Experiments need more explanation for reproduction.\n\n2. Lack of comparison with other partitioning algorithms\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "GK1gMWIkqh5", "reviewer": "Reviewer_J1kM", "summary": "The paper proposes a new large-scale solver for kernel ridge regression (KRR). To be specific, the paper first makes a partition on feature space, and in each local space, a KRR estimator with Nystrom subsampling and preconditioner are trained. The paper also presents the theoretical analysis and numerical experiments.", "questions": "", "limitations": "", "rating": 5, "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 appreciate the solid theoretical proofs, but the proposed method seems just a wrapper of some existing techniques and lacks novelty. Large-scale KRR is also few applied in practice at present.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The studied problem and proposed method are not very interesting.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "ArJOg8qAlxV", "reviewer": "Reviewer_STtd", "summary": "The author introduces a partitioning method for solving large-scale kernel ridge regression. Instead of working on the input space, the author proposes constructing partitions directly in the feature space. The effectiveness of the method is demonstrated through numerical experiments. The main limitations are also discussed.", "questions": "", "limitations": "", "rating": 5, "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": "It is an interesting idea considering partition directly in the feature space rather than the input space. However, the advantages are not clearly shown in the work. \nThe choices of centroids and hyper-parameters are carefully discussed. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. The author claims that considering partition in the feature space rather than in the input space allows promoting orthogonality between the local estimators, and can control the local effective dimension and the local bias. However, such a claim is not clearly explained in the rest of the paper. It remains unclear why the space partition can promote orthogonality, and how. In addition, the comparison between space partition and data splitting is lacking, it is better to add the results of the data splitting method in the numerical experiments.\n\n2. In algorithm 1, there are steps on calculating the set $[n]_{\\bar q}$. What is the set used for?\n\n3. The proposed method results in a union of local estimators, when predicting, the data needs to be located first based on the partition. Is the final result sensitive to the way of partition? How to deal with the estimation on the boundaries of the partitions?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an algorithm make the learning of a kernel-based  in the large scale scenario using, as its core, a partition computed in the kernel feature space. If the paper goes beyond a pipeline of existing methods, the paper would gain a lot of strength if:
-  beyond the combination of existing methods, the amount of novelty of each part of this combination was discussed: how new is the feature space partitioning? How would it differ from a simple Kernelized partitioning methods with a clever (greedy) initialization?
- what is the credit assignment in place regarding the proposed pipeline: what makes the method work? The partitioning, the Nystrom approximation? The optimisation procedure? This should be clarified. 
- Would other acceleration methods dedicated to kernels such as random features (Rahimi and Recht) would fit into the pipeline? If no, why?

If the technical parts are okay, there is a lack of perspective on the work, preventing the reader to know what are the key parts that make the proposed method effective.
Decision: Accept (Poster)