Summary
This article studies a family of quadrature rules suited for functions that belongs to an RKHS. The proposed construction is based on an algorithm called randomly pivoted Cholesky (RPCholesky). The latter was studied for the task of approximating positive-semidefinite matrices. In particular, the authors extended RPC to continuous domain, and investigated its effectiveness for kernel quadrature. More specifically, the authors studied the quadrature rule obtained by taking the nodes to be the configuration of points that RPCholesky and by taking the weights that minimises the worst-case integration error on the unit ball of the RKHS (WCE). In particular, they proved that the expected value of the squared WCE of this quadrature rule converges to 0, with a rate of convergence that depends on the eigenvalues of the integration operator. Moreover, they studied the expected runtime of the proposed algorithmes.
The contributions of the article may be summarised as follows:
* An extension of the RPCholesky algorithm to a continuous domain (Algorithm 1) along with a detailed implementation of it using rejection sampling (Algorithm 2).
* An implementation of RPCholesky with optimized rejection sampling (Algorithm 4).
* A generic result (Theorem 1) gives the upper bound of the expected squared WCE for the proposed quadrature rule.
* The study of the expected runtime of Algorithm 2 (Theorem 4).
Strengths
- The article is very well written.
- The article expands the application of the randomly pivoted Cholesky algorithm into the continuous domain, establishing another bridge between the numerical linear algebra community and the kernel quadrature community.
- The proof of the main result (Theorem 1) is original and may be beneficial for the community of kernel quadrature in the future.
Weaknesses
At first sight, the proposed algorithm seems to bring a significant algorithmic improvement upon continuous volume sampling. This is at least what we may understand reading the comments of Figure 2 (line 235-line 238). While, the relative improvement is undeniable, RPCholesky suffers from the same limitation of continuous volume sampling that is poor scalability for large values of $N$, especially for smooth kernels. Figure 2 of the article is corroborating this claim: the dependence of the empirical expected time as a function of $N$ seems to be polynomial. This is particularly the case in dimension 1, where we have $\lambda_m = \mathcal{O}(m^{-2s})$ so that $1/\sum_{m=N+1}^{+\infty}\lambda_{m} = \mathcal{O}(N^{2s+1})$. In other words, the smoother is the kernel the longer it will takes to sample from the RPCholesky, which is exactly the same problem with Gibbs sampling proposed in [1], which provably approximate continuous volume sampling. It turns out that Algorithm 1 is nothing but the algorithm proposed in [1] to initialise an MCMC algorithm that approximate continuous volume sampling; see Algorithm 1 in [1]. The difference between the two works is in the subroutine that consist in sampling from the probability measure $x \mapsto k(x,x) \mathrm{d}\mu(x)/\int_{\mathcal{X}}k(u,u)\mathrm{d}\mu(u)$: [1] proposed to use a ‘stochastic greedy’ algorithm using rejection sampling, while this article proposed to use RPCholesky with rejection sampling. Interestingly, the two algorithms have an expected time that depends on $1/\sum_{m=N+1}^{+\infty}\lambda_{m}$, where is the number of nodes in the quadrature rule, see Lemma 5.1 in [1]. In other words, this work does not break the ‘curse of smoothness’ that hinders the scalability of continuous volume sampling.
[1] Rezaei, A., & Gharan, S. O. (2019, May). A polynomial time MCMC method for sampling from continuous determinantal point processes. In International Conference on Machine Learning (pp. 5438-5447). PMLR.
[2] Anari, N., Gharan, S. O., & Rezaei, A. (2016, June). Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes. In Conference on Learning Theory (pp. 103-115). PMLR.
Questions
- The empirical comparison in section 5 was limited to Sobolev spaces of order s=3. It may be interesting to compare RPCholesky to other algorithms on other RKHSs.
- The empirical experiments make use of a continuous analog of a ’basis-exchange’ MCMC algorithm proposed in [2] instead of the MCMC algorithm based on Gibbs sampling proposed in [1]. Up to my knowledge, only the latter was studied theoretically, and it is possible that the convergence of ’basis-exchange’ MCMC algorithm is slower than the Gibbs sampling.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.