Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper deals with scaling kernel ridge regression, providing a new large-scale algorithm to solve kernel ridge regression called ParK. ParK is based on combining several ideas: partitioning the training set so training can be done on smaller datasets, using a geometric approach to build the partition (i.e. space partitioning as opposed to data splitting), building the split in the feature space, forming the global estimator as a "stitch" of local ones, computing the local estimators using preconditioned CG where the preconditioner is formed using Nystrom approximation.  Theoretical analysis in a fixed design setting is provided. Basic experiments are performed.
main_review: This is a well written paper that suggests a new method (ParK) for solving large-scale KRR problems. The idea of splitting the global estimator as a stitch of local-in-feature-space estimators is interesting. This idea is complemented with an interesting theoertical analysis.

While the method has desirable computational properties, and generalizes well according to the theory (provided we have a good partition), they method and the associated theory has several shortcomings, not all of which are discussed by the authors:
1)  The estimator that is found is discontinuous since it is a stitch of several local estimators. 
2) Since the partition is geometric, there is guarantee that it will be balanced. In fact, it is possible for almost all points to belong to a single local estimator, thereby ruining any computational gain.
3) In the theory, the parameters m_q and t_q are set using quantities that are unknown (f_\star and N_\infty,q). For t_q, this is less an issue because we can simply check if the the method converged or not. However, for m_q we just need to hope the parameter is set high enough (but not too high so to waste computational resources) 
4) Generalization bounds are based on the minimal angle between the space spanned by the partition. There is a algorithm that partitions the points so to maximize this angle. However, it seems that this algorithm is heuristic, and no formal bound is given.

(all the above points should be discussed in the paper)

Novelty: of all the ideas combined to form ParK (see summary of paper), only the idea of partitioning using the feature space seems novel. All other ideas appeared elsewhere, e.g. the actual algorithm that is used to split the data seems to be from [8]? Preconditioning using Nystrom is from the FALKON paper. Much of the description in the main paper seems to be redundant and just recasting things in term of the local estimator. For example, what is essentially new in Section 3.2? Also: some of the theoertical results seems to based on adapting similar results from [24].

Experiments: somewhat basic and not really convincing. 

Minor comments: 
1) Notation is sometimes ambiguous, e.g. H_q seems to denote both space spanned by q vectors and the one spanned by partition q.
2) Might be useful to mention that N_q,infty is essentially the coherence of T (maximal leverage score). 

limitations_and_societal_impact: No societal impact. Limitations are discussed in main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a large-scale solver for kernel ridge regression. The main idea is to partition the input space using clustering in the kernel feature space and then solve local regression problems over the clusters using the FALKON method (Rudi et al., NIPS 2017). During inference, one first loads the partition to which a test point is assigned and then returns the prediction using the hypothesis learned over that partition/cluster. 

Theoretical guarantees are provided in the fixed design setting and rely on the previous analysis done by Rudi et al. (2017). The empirical results demonstrate that the approach can attain the accuracy of the FALKON method while making significant computational savings.
main_review: I find that the paper is clearly written and well-organized. It is quite easy to follow the presentation and pretty much all of the arguments (apart from lines 75-78: the reference to Lemma 4.55 in [28] is not sufficiently clear).

Partitioning data in the kernel feature space can be computationally expensive. To avoid that the authors propose an iterative procedure for the selection of centroids such that they are maps of instances from the input space. Otherwise, the pre-image of a kernel feature space centroid might not exist and would complicate the inference. The proposed iterative procedure is a greedy volume maximization approach, similar to selection of landmarks in the Nystroem method based on determinantal point processes. In each step of this iterative procedure, one needs to invert a matrix of size q (Eq. 6), where q denotes the cardinality of the current set of selected centroids. While this is an effective strategy one could ask whether an improvement might be possible using an approach with a linear complexity (e.g., kernel k-means++ sampling scheme). 

The hypothesis that is learned over a data partition uses the FALKON method and it would be good to add a discussion to the main part of the paper, clarifying in what way the proof of Theorem 1 is different from that work. In my brief pass over the appendix, I would say that there is no substantial extension of that work and that the main theoretical contributions of this paper are Propositions 2 and 3. The latter two results state that the selection of data partitions such that they are orthogonal is beneficial for the effectiveness of the local approximations. Would it be possible to link results in Propositions 2 and 3 a bit stronger to the selected data partitioning method?

Empirical study has been performed on four datasets with millions of points. The provided evidence clearly supports the argument for computational effectiveness of the approach. Now, what is lacking here is the dimensionality of the input space and how the proposed approach fares relative to that parameter. Namely, one needs to solve the partitioning problems which are affected by the dimension of the instance space and there should be a threshold where computational savings compared to the FALKON method become void or less relevant. Would it be possible to list the dimensions of these datasets and possibly add an experiment where the dimension increases ($d = 10,100,1000,10000$) -- this could be a synthetic problem purely to showcase the dependence on the input space dimension.

limitations_and_societal_impact: This has been adequately addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of kernel ridge regression. They propose a large-scale solver named ParK, which combines multiple techniques from the literature, including sketching and preconditioning. Their main conceptual contribution is to use a divide-and-conquer approach that partitions the feature space rather than the input space. The authors show that this makes the algorithm faster without affecting its statistical performance.
main_review: The paper provides a solid contribution by pushing the computational limits of kernel ridge regression solvers. Moreover, I believe the ideas in this paper could help improve the state-of-the-art software. Nonetheless, the proposed method is not particularly original as it primarily combines ideas from [8] and [19].

To the best of my knowledge, the technical contributions are simple and mathematically sound. The authors present a fair amount of theoretical and practical evidence to support their claims. In particular, they prove nontrivial error bounds, that are minimax optimal for some settings, and show numerically that their implementation is a constant times faster than FALKON [19] (a state-of-the-art solver). Broadly speaking, the paper is well-written and easy to read. However, there are some points I'd like the authors to address to improve this manuscript; see below.

# Comments
- I'd like to see a better comparison with existing methods. For example, I'd like to know how ParK compares in terms of sample complexity, risk bounds, and computational complexity. Maybe a table?
- On a related note, the guarantees prove in this work are for a fixed design (i.e., fixed features x_i). However, most of the literature concerning partitions has guarantees assuming a random design. Therefore, it would be interesting to extend the analysis to random settings and see how they compare.
- I would suggest the authors work a bit on the introduction. I felt the second paragraph is broad and hard to follow without more context. It will be better to start with the contributions of the paper rather than related work
- The authors should specify the RAM of the machine used to run the experiments.
- For me is a little bit of an overstatement to say that Corollary 4 shows a  statistical-computational tradeoff. This result proves an upper bound for one method. It doesn't give a lower bound for a meaningful class of polynomial-time methods.

# Questions
- The authors claim that using partitions in the feature space allows them to promote orthogonality among the estimators. This is intuitively true, but is there a way to formalize it and compare it with other approaches? Why isn't it possible to do something similar with previous estimators?
- The following comment might be a result of using different machines, but I found it interesting and wondered if the authors have an explanation for it. The experiments used the same datasets as the ones used by FALKON [19]. Yet, the running times are not consistent with the ones obtained in [19]. For example for TAXI, [19] got a run time of 3628 sec (as opposed to 120 sec in the present manuscript), while for AIRLINE-CLS, the time reported by [19] was 186 sec (in comparison, the experiment in this paper gave 391 sec).

limitations_and_societal_impact: Yes, they did address these issues. This work doesn't have a significant societal impact as it deals with a theoretical question.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a computationally efficient algorithm for KRR, called "ParK". ParK combines three ideas in the literature: partitioning input samples, the FALKON solver for KRR, and Nystrom subsampling. After partitioning, FALKON and Nystrom are applied black-box based on the prior literature, while the partitioning is claimed to be new (I am not an expert on partitioning techniques). The partitioning is a Voronoi Diagram in the feature space whose centers are heuristically chosen to promote orthogonality between local estimators.

A few experiments are run, with emphasis on improved runtime. Statistical guarantees are in the fixed design setting, and most of the theoretical effort is spent showing that if the partitions are nearly orthogonal in the feature space, then ParK has near-optimal statistical complexity.
main_review: Overall, the paper is both nice and approachable. I recommend it for publication.

It would benefit from minor revisions throughout, but those are just simple fixes for the sake of clarity.

My background is largely theoretical in KRR, so I will mostly discuss that aspect, and not focus on the experimental side so much. To me, the experiments seem reasonable and promising.

The ParK method is a combination of largely existing ideas. Nystrom and FALKON are both pre-existing, but the feature-space partitioning appears to be novel (I am not an expert on partitioning techniques). Since the feature space partitioning is the focus of the paper, the paper seems original enough and distinct from prior works. I feel the idea is significant enough to merit publication.

Related works are well cited throughout the paper.

The paper seems to be technically sound, and I tried to review all the proofs in it, but the mathematical notation can be frustrating at times. Further, the proofs lack clarity in several nontrivial steps. There are several reasonable-looking mathematical statements that I did not verify. I list concrete examples at the end of this text, and would strongly recommend clarifying much of this.

Aside from these mathematical frustrations, the paper is clear and interesting.

The theoretical results are sufficient, but not particularly exciting. The fixed design setting is okay, but I am admittedly a little concerned about how well the voronoi diagram will generalize near the edges of the diagram (i.e. on the edges of the partition).

The main stated limitation of not guaranteeing highly orthogonal subspaces is earnest and interesting. I am curious to see if future works can provably increase the angle between subspaces / decrease the incoherence of each partition's kernel. (see below for more on incoherence)

Some smaller questions:
- [Line 52] Is there any reason why the input values $x_1,...,x_n$ need to be real-valued? This seems like a strong constraint which is rarely needed in kernel problems.
- [Line 178] Since ParK is not an average of local estimators, does it have discontinuities at the boundaries of the partitions? Will this hurt the out-of-sample performance of ParK, or limit it's statistical guarantees for $x\\notin\\{x_1,...,x_n\\}$?
- [Lines 207, 230] The term $N_\{q,\infty\}$ seems to be an incoherence parameter (specifically, it is the largest ridge leverage score). This means that Theorem 1 and Corollary 4 both have the number of samples in a partition depend on the incoherence of the kernel matrix of that partition.
    - Is this circular dependence inevitable?
    - This interpretation seems interesting enough of a context to be worth mentioning?


Unclear points:
- $\\|\cdot\\|$ is never defined without subscript, for neither vectors nor matrices, despite the fact that both appear in the appendix. I understood these to be the L2 norm for vectors, and the spectral norm for matrices.
- In Algorithms 1 and 2, the process of finding the corresponding centroid should be written in terms of the kernel function, since we generally don't expect algorithms to explicitly build vectors in the feature space.
- [Line 98] Does finding a centroid not take $O(Q)$ time, not $O(1)$. $Q$ is assumed non-constant in other big-O notations later on.
- [Line 191] The overall notation of $L^2 = L^2(\\rho)$ often confuses me. The inner product $\\langle u,w \\rangle_{L^2} = \\frac1n u^\\intercal w$ suggests that $u\\in L^2$ is a real vector, presumably with $n$ components. The following $\\|\hat f - f_*\\|_{L^2}$ suggests that real-valued functions of real-inputs lie in $L^2$.
    - The confusion propagates to the Appendix A.1, where the distinction between functions and vectors gets much more confusing. Does $Sf(x)$ denotes $\[Sf\](x)$ or $S\[f(x)\]$? If $Sf(x)=\\langle f, \phi(x) \\rangle_{H}$, this seems to be a real number so how can it lie in $L^2$?
- [Line 519] The W matrix should have different subscripts in the bottom left and top right corners, in both block matrices.
- [Line 522] Specify $\beta_q \geq 0$, which is used a few lines lower.
- [Line 525] In the last line of math, what inequality is used to pull this spectral norm of $M_q$ out?
- [Line 526] The 5th line, I think, uses an adapted version of the Push-Through identity (specialized to use a scaled identity matrix)? I would clarify this.
- [Line 527] Again, I think an adapted push-through identity was used? Clarify this.
- [Line 528] What inequality is used in the final line? I get the triangle inequality to separate the $+1$ term, but how did $\\lambda_q$ get outside the norm?
- [Line 528] How does $\\frac1n \\sum_\{\\phi(x_i)\\notin V_q\} \\|P_q\phi(x_i)\\|$ relate to the right hand side? Was this bounded anywhere else in the paper?


Recommended edits:
- State somewhere early on that you take $Q=O(1)$ empirically, around 32, to help the audience understand the scale of the partitioning scheme.
- [Line 74] The sentence "Unlike classical ..." is awkwardly phrased
- [Line 117] This Schur complement also arises as the variance of a Gaussian Process at $c$ given $c_1,\\ldots,c_q$. Seems like another interesting interpretation for the heuristic, in case you want to mention that.
- [Line 198] The $\\otimes$ notation is only used in some KRR communities. I recommend defining it in section 2.
- [Line 230] It seems odd to describe Theorem 1 as a new theorem. The proof of it just plugs together theorems of prior works, and spends most of its time working with notation. I would at least elevate Corollary 4 to be a theorem, and considering demoting this to be a corrolary.
- [Line 454] It may be unwise to define both the symbols $L$ and $L^2$, where one is an operator and the other is a space. I'd recommend using different symbols.
- [Line 527] The inline equation's first step was unclear to me for a while. Simply adding "Taking this inequality and setting..." to the start of the sentence would be nice.
limitations_and_societal_impact: The authors are candid and clear with the limitations of the work. Most centrally, there lacks a guarantee connecting the partitioning algorithm to the orthogonality of the resulting partitions.

While it would, of course, be better to have seen such a result in this paper, the empirical evidence for the algorithm is convincing enough. Further, provably promoting such orthogonality is a problem of large enough scope to merit a completely separate publication.


Societal Impact: No concerns; not relevant.
review_title: null

Meta-review: The focus of the submission is the solution of kernel ridge regression (KRR) in the large-scale setting. Particularly, the authors propose to use a combination of partitioning (a Voronoi one in the feature space), preconditioned iterative optimization and sketching. The resulting KRR solver is shown to be able to achieve the minimax optimal global KRR rate in the fixed design setting in terms of the excess risk (14), while significantly reducing the computational load. The efficiency of the approach is demonstrated on 4 large-scale benchmarks.

Kernel methods are among the most successful machine learning tools of our times. By the construction of a novel KRR solver with optimal statistical performance and reduced computational complexity, the authors provide a valuable contribution to the field which is of both theoretical and practical interest.
Decision: Accept (Poster)