An analysis of Ermakov-Zolotukhin quadrature using kernels
Authors: Ayoub Belhadji
Venue: NeurIPS 2021 Poster (2021)
Keywords: Determinantal point processes
quadrature
kernel
monte carlo
numerical integration

Abstract: We study a quadrature, proposed by Ermakov and Zolotukhin in the sixties, through the lens of kernel methods. The nodes of this quadrature rule follow the distribution of a determinantal point process, while the weights are defined through a linear system, similarly to the optimal kernel quadrature. In this work, we show how these two classes of quadrature are related, and we prove a tractable formula of the expected value of the squared worst-case integration error on the unit ball of an RKHS of the former quadrature. In particular, this formula involves the eigenvalues of the corresponding kernel and leads to improving on the existing theoretical guarantees of the optimal kernel quadrature with determinantal point processes. 


An analysis of Ermakov-Zolotukhin quadrature using kernels
Ayoub Belhadji Univ Lyon, ENS de Lyon Inria, CNRS, UCBL LIP UMR 5668, Lyon, France ayoub. belbadb @end-jyoenooooo fr
Abstract
We study quadrature, proposed by Ermakov and Zolotukhin in the sixties, through the lens of kernel methods. The nodes of this quadrature rule follow the distribution of determinantal point process, while the weights defined through linear system, similarly to the optimal kernel quadrature. In this work, we show how these two classes of quadrature are related, and we prove tractable formula of the expected value of the squared worst-case integration error on the unit ball of an RKHS of the former quadrature. In particular, this formula involves the eigenvalues of the corresponding kernel and leads to improving on the existing theoretical guarantees of the optimal kernel quadrature with determinantal point processes.
Introduction
Integrals appear in many scientific fields as quantities of interest per For example, in statistics, they represent expectations (27), while in mathematical finance, they represent the prices of financial products [17]. Unfortunately, integrals that can be written in closed form are exceptional. In general, their values are only known through approximations. For this reason, numerical integration is at the heart of many tasks in applied mathematics and statisties. Among all the possible approximation schemes, quadratures are the most practical since they approximate the integral of function by finite mixture of its evaluations. In this work, focus quadrature rules that take the form
J (()))())dw()))
Σ SE[N]
wi (xx(,,)
where the nodes x; are independent of f and g. while the weights w; depend only on g. The nodes and the weights of a quadrature may be seen as degrees of freedom that the practitioner may tune in order achieve given level of approximation error. The design of quadratures gave birth a rich literature from Gaussian quadrature [15] to Monte Carlo methods (25 to quadratures based on determinantal point processes (DPPs) [.. These latter form large class of probabilistic models of repulsive random subsets that make numerical integration possible in variety of domains with strong theoretical guarantees. particular, central limit theorems with asymptotic convergence rates that scale better than the typical Monte Carlo rate O(N 11/)) were proven for several DPP based quadratures: when the integrand is a C² function [ or even when the integrand is non-differentiable [IO]. Moreover, is possible to design quadrature rules based on DPPs with non-asymptotic guarantees and with rates of convergence that adapt to the smoothness of the integrand. This is the case of the quadrature proposed by Ermakov and Zolotukhin in [4 and recently revisited in [16), and the optimal kernel quadrature (3]
In this work, study the quadrature rule proposed by Ermakov and Zolotukhin (EZQ) through the lens of kernel methods. We start by comparing the weights of EZQ to the weights of the optimal
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

kernel quadrature (OKQ), and we prove that they both belong to a broader class of quadrature rules that we call kernel based interpolation quadrature, Then, we study the approximation quality of EZQ in reproducing kernel Hilbert spaces (RKHSs). This is done by proving a general tractable formula of the expected value of the squared worst-case integration error for functions that belong to the unit ball of an RKHS when the nodes follow the distribution of a determinantal point process. This formula involves principally the cigenvalues of the integral operator, and converges to at a slightly slower rate than the optimal rate. Interestingly, this analysis yields a better upper bound for the optimal kernel quadrature with DPPs proposed initially in [3] Comparably to the theoretical guarantees given in 14 [16], theoretical guarantees independent of the choice of the test function. This facilitates the comparison of EZQ with other quadratures such as OKQ.
The rest of the article is organized as follows. Section 2 reviews the work of 14 and recall key
concepts on kernel based quadrature. In Section 3 we present the main results this work and their consequences. A sketch of the proof of the main theorem is given in Section 4 We illustrate the theoretical results by numerical experiments in Section [
Finally, we give a conclusion in Section 6
Notation and assumptions. We use the notation N = - {0}. We denote by w Borel measure supported on X, and we denote by C2(w) the Hilbert space of square integrable real-valued functions on X' with respect to equipped with the inner product (-. 1)w, and the associated norm Il-llw. For N N we denote by w@N the tensor product of w defined on X Moreover, we denote by the RKHS associated to the kernel k: : X x X' -> IR that we assume to be continuous and satisfying the condition fx (xx x (x) < +00. particular, we assume the Mercer decomposition
k(x,y)=
Σ omdm (2)@m (y), mEN
to hold, where the convergence is pointwise, and o. and Φm are the corresponding eigenvalues and eigenfunctions of the integral operator Σ defined for f [2(w) by
ΣS(- ((.2))(()dw()))
We assume that the sequence o = (om)mEN is non-inereassig and its elements are non-vanishing, and we assume that the corresponding cigenfunctions om are continuous. Note that the om are normalized: |l = for m N*. In particular, (om)mEN is an o.n.b. of Le(w), and every element f satisfies
(ʃ. Ummm < t00.
Σ meR-
(4)
Tm
Moreover, for every N E N we denote by Ex the eigen-subspace of L2(w) spanned by Φ1, $1....,, 2N. For any kernel k X x X + R, and for E X we define the kernel matrix <(x) == 2)),,En E NNN Finally, we denote in bold fonts the corresponding kernel matrices: K (æ) for the kernel k, (xx for the kernel ky. K (a)) for the kernel k k(x) for the kernel k... Similarly, for any function X' R and for x N we define the vector of evaluations μxx) = (u(Z;)))E[M) E R.N.
2 Related work
In the section, we review some results that are relevant to the contribution.
2.1
Ermakov-Zolotukhhin quadrature
The quadrature rule proposed by Ermakov and Zolotukhin in 14 deals with integrals that write
J (())mm())duu()
(5)
where f E L2(w), and (dm)mERS is an orthonormal family with respect to the measure w. Its construction goes as follows. Let N E No and let x E x such that the matrix
+ ny (z) = (Øn

---

is non-singular. For n E [M], define
1 (f)
Σ dE[M]
Wi
EZ..
f(re),
where w EZ.n = (10.z2.)) MEIN E R is given by R @ (2)) en. with en is the vector of
RN with the n-th coordinate is 1 and the rest are 0 We can prove easily that this quadrature is exact
vf E Span(on)nett
Σ
wi FZ." f(zi)
f(=))) f(x)0n()) dw(x).
EEIM
quadrature rule that satisfies is typically called an interpolatory quadrature rule.
Now, if f & Span (eau(ón)men (e)) the authors studied the expected value and the variance of 1BZ.n (f) when æ = (.i...., IN) is taken to be random variable in X that follows the distribution of density
1 Det x (ar), N!
PDPp(41......
with respect to the product measure &N defined on X it was observed in [6] the nodes of the quadrature follow the distribution of the determinantal point process of reference measure w and marginal kernel KN defined by KN (z, y) EnEINi @n (z) (y). We refer to (20) for further details
on determinantal point processes. Now, we recall the main result of [14]
Theorem 1. Let x be a random subset of X that follows the distribution of DPP of kernel KN and reference measure w. Let C2(w), and n E [N]. Then
Enppl EZ, (2) 1
/ f(z))n
(9)
and
Dpp! (A,p/EZ,n1() (J)
Σ m2N+1
(10)
Theorem shows that the F (f) is an unbiased estimator of fx f())) (x), and its variance depends on the coefficients (f, @miw for m 2 N 1. Consequently, the expected squared error of the quadrature is equal to the variance of JEZ. (f) and given by
Eppp / f(x)) ((x))x())))((()
Σ KE[N]
EZ,a W
f(x;))
Σ m2N+1
(f,
(11)
The identity (11) gives theoretical guarantee for interpolatory quadrature rule when the nodes follow the distribution of the DPP defined by (8). Compared to existing work on the literature
22 23 24
is generic and applies to any orthonormal family.
Now, we may observe that the expected squared error in (T]) depends strongly on the function f. This makes the comparison between EZQ and other quadratures, based on some test function f. tricky: the choice of if may favor (or disfavor) EZQ. In order to circumvent this difficulty, we suggest to study figure of merit that is independent of the choice of the function This is possible using kernels through the study of the worst-case integration error on the unit ball of an RKHS. The definition of this quantity will be recalled in the following section.
2.2
The worst integration error in kernel quadrature
The use of the kernel framework in the context of numerical integration can be tracked back the work of Hickernell [8 19), who introduced the use of kernels to the quasi Monte Carlo community. Their use was popularized in the machine learning community by 22 D. In this framework, the quality of a quadrature is assessed by the worst-case integration error on the unit ball of an RKHS F associated some kernel k X X + R.. This quantity is defined as follows
sup / feF f(x)g())dd((z)) I X
Σ wxf(x;)
(12)
(E[N]
'The dependency of the vector EZ.n on was dropped for simplicity.
3

---

This quantity reflects how good is the quadrature uniformly on the unit ball of F. Interestingly, this quantity has closed formula
M'
Σ SE[N]
wak(s;
(13)
where My = Eg is the so-called embedding of g in the RKHS F. We shall use Scction 3.2 the equivalent expression (13) of the worst-case integration error, to derive closed formula of
If f(x)g())d((()) 1
2
EDPP sup FEF,
Σ EEIM
u EZ,n f(xi)
(14)
F2,. of EZQ non-optimal in the sense that they do By now, observe that the weights w; ui minimize (13). By definition, the optimal kernel quadrature for a given configuration æ, such that the kernel matrix K (x) is non-singular, is the quadrature with nodes the æ; and weights the úū; that minimize (13). We specify in Section 3.e subtle difference between the quadrature of Ermakov and Zolotukhin and the optimal kernel quadrature. Before that, we review the existing constructions of the optimal kernel quadrature in the following section.
2.3 The design of the optimal kernel quadrature
The optimal kernel quadrature may be calculated numerically under the assumption that the matrix K (x) non-singular. Indeed, for given configuration of nodes æ X the square of (13) is quadratic and have unique solution given by u oKQ. K ((x))~"u (1) In particular, the optimal mixture Eie[N] úi; (
takes the same values as bg on the nodes æy; the optimal mixture interpolates the function (4g on the configuration nodes æ. At this level, æ still degree of freedom and need to be designed. This task was tackled by different approaches. One approach consists on using adhoc designs for which a theoretical analysis of the convergence rate is possible. This is the case of, inter alia, the uniform grid in the periodic Sobolev space [6 26). higher-order digital nets sequences in tensor products of Sobolev spaces [8), or tensor product of scaled Hermite roots in the RKHS defined by the Gaussian kernel [22] Another approach consists
using a sequential algorithm to build up the configuration æ 12 these greedy algorithms requires solve non-convex problem and costly approximations must be employed. Alternatively, random designs, based on determinantal point processes and their mixtures were shown to have strong theoretical guarantees and competitive empirical performances. More precisely, was shown that if æ follows the distribution of DPP of reference measure w and marginal kernel KN, and if g (2(w) such that ||/|| 1, then
13 21 71. In general, each step of
3 4
EpPP Mg
Σ SEIN]
OKQ OKQ.91(Z, M(T..))
20N+1 2
Σ Kg on)ual) NrN. nE[N]
(15)
where NN = -m om 2 (Theorem 4.8). However, numerical simulations suggest that the l...s of 115) converges to 0 at the faster rate N(NN+1). which corresponds to the best achievable rate
according 44. This optimal rate was proved be achieved, under some mild conditions on the cigenvalues on, using the distribution of continuous volume sampling (CVS) 4 This distribution is mixture of determinantal point processes and is closely tied the projection DPP used in [3] and comes with the following guarantee
Vg L2(w), Eevs Mg
Σ RE[N]
ii
OKQ.S
Σ meN-
(16)
where 6m (N) = ((aN+1) for every m E No, so that the expected squared worst-integration error of OKQ under the continuous volume sampling distribution scales O(aN+1) for every E L2(w).
The dependency of the vector u OKQ.9 on dropped for simplicity.

---

3
Main results
This section gathers the main contributions of this article. In Section 3.1 we prove that both EZQ and OKQ belong to larger class of quadrature rules called kernel- based interpolation quadrature (KBIQ). In Section 3.2 we prove a close formula the expected squared worst-case integration error of EZQ. In Section
3.3 we Theorem improve the existing theoretical guarantees of OKQ
with DPPs.
3.1 Kernel-based interpolation quadrature
In this section, we define a new class of quadrature rules that extends both Ermakov-Zolotukhin quadrature and the optimal kernel quadrature. We start by the following observation: the weights w EZ,n (x) EZQ, defined in (6). writes
w EZ. (z) (x)x)
(17)
By observing that (x) 4 (N(()) en and (N) andx
=+ (2((x))TN((( we prove that
w EZ Ez) (x) = (N(x)) on (x))
(18)
Equivalently, we have 6n (x) K.N (x) ) EZ. (x:). In other words, EXENN Wi (1:"""(()))))) (x),.) takes the same values as d,, on the nodes zy. in EZ," (xx is the vector resulting of the interpolation of Φn by the kernel KN. From this observation, extension of EZQ as follows: let y == (Ti mmm) be a sequence of positive real numbers, and let M E NO U {+oo]. Define the kernel 7 X' x by
EZ."
define kernel-based interpolation quadrature as
M Σ m=1
Ve,YEE W7.M (I.
Im (2))mm (y)-
(19)
Now, starting from a configuration æ E X such that Det NE (ar) > 0, we have Det N. (x) > and for given E L2(w), we define the vector of weights ub T.M (x)) E R.N by
n. (x) = 1 > (x) + M.M (x))
(20)
where
M Σ m=1
1 (x)
7m (g, @m)
(21)
M. x M. (xi..) takes the same values as 1...M on the nodes æ; the We check again that EiE[N] vē?7
mixture interpolates 1zz on the nodes z4. Now, for given g C2(w), the vector of weights w.. (x) have two degrees of freedom: the sequence 7 and the rank of the kernel M. These degrees of freedom may be mixed in variety of ways to cover large class of quadrature rules. In particular, we show Section I.I.Ithat. for any sequence 7, KBIQ is equivalent to EZQ when M = N, and we show in Section 3.1.2 that KBIQ is equivalent to OKQ when M +oo and y o; as summarized in Table We may also consider M to be finite but strictly larger than N. Yet, the theoretical analysis of these intermediate quadrature rules is beyond the scope of this work.
Quadrature
M
K 7.
EZQ
N
Any
Eme(N) I'n (g, In)won
K7.N
EZQ
N
7m
9N
2nEIN (0, Pn
KN
Pg Table 1: An overview of some examples of KBIQ with the corresponding couples (x $17. H...M
OKQ
+00
See Appendix D.I. in 3 for proof.
5

---

3.1.1 EZQ is special case of KBIQ
We recover EZQ. defined in [14] 16].1611111. by taking M = N, and y is defined by 7/ = 1 for every
m E N", and g = on for some [N]. The equivalent definition 20 extends EZQ the situation
when g Ev. Even better, we show in the following that w (x) is independent of when
M = N. In particular, for any sequence of positive numbers 7 we have
Vn E [N], w T..NN." - =Zz,
(22)
Proposition 2.
Let g E EN. and let a XN such that Det (N(x)) > 0. Let 7 = (Mm)mNN- and (mm)mNN- be two sequences of positive mumbers. We have
i 7.N = (x)..
(23)
Thanks the invariance of 7.NNg with respect to Y, we simplify the notation and write w 92. instead Moreover, using this invariance, EZQ may be seen as an approximation of OKQ when 9 Ex. Indeed, by approximating the kernel matrix ((x) Kx(x) where kx (r. y) ΣnE(N) Tn (z))())) we have
K (z) - Mg (x) R ih E2.9
(24)
since K (x(x)_pppp (x) i F7.9 by Proposition 2 Interestingly, this approximation is reminiscent to one used 23 in the case of the Gaussian kernel.
3.1.2 OKQ is special case of KBIQ
The optimal kernel quadrature is special case of KBIQ when M to0 and y Indeed, in this case, we have w7.M k. and pg.at = Mgg so that
E M.9 (x)
K
x
pg (g(x))
w OKQ.9
(25)
In other words, instances of interpolation based kernel quadrature that correspond to the regimes = N and M = +00 As it was shown in Proposition 2 the weights of EZQ depend only on the eigenfunctions on and do not depend on the eigenvalues om- This to compared to the weights of OKQ that depend simultancously the eigenvalues and the eigenfunctions.
quadrature and the optimal kernel quadrature are extreme
3.2 Main theorem
We give in this section the theoretical analysis the worst case integration error of EZQ under distribution of the projection DPP.
Theorem 3. Let N N We have
Vgg E En, Eprrllig
Σ RE[N]
W
EZ.9
-113==
Σ
(g. LnnaNn
(26)
nE(N]
where NN = =m On- Moreover,
Vg [2(W), EDPPlIM
Σ
W
EZ. k k(zi, (x.1 - <4119/B....
(27)
1E[N]
As an immediate consequence Theorem
we have
/ f(z)g(2)dv(()) -
Ag L2(w), EDPP sup feF. =
Σ SE[N]
w f(z:)f(zz)) O(rw). (28)
In other words, the squared worst-case integration emrrr of mimaakov-Zoouukhin quadrature with DPP nodes converges to 0 at the rate (( This rate slower than the rate of convergence of
In the on for some E [NV] úo oZ i EZ.n alternatieel..

---

EDPp/ 1 (f)² given by Theorem ! Indeed, if f E F then |1 EmEN- (f, (f.0m///mm < too,
and Theorem Toreemmyyiilll yields
Wppp EZ,
1 (f)2 S oN++llf113.
(29)
so that
Eppp / (()
- Σ
1 E f(z;) = -Drp
(30)
N
for some 8 > 1/2, then FN+1 ( We conclude that the convergence of EZQ under DPP is slower than the optimal rate N+1 that observed empirically for OKQ under DPP in [3] and proved theoretically for OKQ under CVS in [4] if we consider the worst-case integration error as a figure of merit. This is be compared with the theoretical result of [14] that can predict the
Now, observe that for some sequences we have xN+1 =(rN+1). For instance, if 0m
difference in the rate of convergence between EZQ and OKQ: our analysis highlights the interest of using kernels when comparing quadratures.
3.3 Improved theoretical guarantees for the optimal kernel quadrature with DPPs
Theorem improves on the existing theoretical guarantees of the optimal kernel quadrature with determinantal point processes initially proposed in [3. This is the purpose of the following result.
Theorem 4. Ler N E N We have
Vg E C2(w), Epppllug
Σ KE[N]
w okQ ((,,, 411g1ir
(31)
Compared to the analysis conducted in [3] Theorem offers sharper upper bound of
Epppllug
w;
OKQ .I..
(32)
KE[N]
Indeed, the upper bound 31
is dominated by E (g. 2 comparably the upper bound (5
proved in (3), dominated by (E Kg 1) Nr:: our bound improves upon (T5) by a factor of N2, since
Kg. 2)) N
Σ (g. 2n s NllllE.
(33)
Theorem follows immediately from Theorem 3 by observing that
||
Σ
OKQ .)3 S 1| Wi
Σ
W
EZ.g
((z. .)I..
(34)
XE[M]
EE[N]
Table summarizes the theoretical contributions of this work compared to the existing literature.
Quadrature
Distribution
Theoretical rate
Empirical rate
Reference
EZQ
DPP
O(rN+1)
((r++1)
Theorem
OKQ
DPP
N²O(rN41)
O(aN+1)
(
O(aN+1)
Theorem
OKQ
CVS
((oN+1)
(
Table 2: comparison of the rates given by Theorem
3 and Theorem
compared to the existing
guarantees in the literature.
We give in the following section, a sketch of the main ideas behind the proof of Theorem 3
Sketch of the proof
The proof of Theorem 3 decomposes into two steps. First, in Section 4.1 we give decomposition of this decomposition to prove closed formula of EDPPllI, - EiE[N] w. (177,)()..)))1)
the squared approximation error [|, EiE[N] wi (.2Z.k(I,,))) .l13. then, in Section 4.2 F7.g

---

4.1 A decomposition of the approximation error
Let g E EN and let a E X such that Det ( > O, we have
Σ RE(N]
10.22 k( -133 I| |1 2pg (a)) T b2. + in E2," K (ar))o
(35)
The last two terms of the r.h.s of 355 decompose follows. Proposition 5. Let g EN and let X such that Det (2) > O. We have
Mg (n E2,9 ||
(36)
and
EZ.9 K ((w)(iB22 = 11 + TT xxx)
-17 K (xx)
(37)
where E EnE(Ny (9 en. and kit the kernel defined by
(x,
Σ
(m0m(I))m
(38)
m2N+1
The proof of Proposition 5ss detailed in Appendix A.3 Now, by combining (35). (36) and 37
get
l14
Σ g
W;
k( Luott - 2110 + | + t (x)(2=)) (x) le. )|
*E[M]
This proves the following result.
Theorem 6. Let g E En and let x E X such that Det N. NN > We have
l1
w E7. -11 (x) (x)) e,
(39)
i
where c -EEENN (g. Oniwen
4.2 A tractable formula of the expected approximation error
In the following, we prove a closed formula for EEPpllls EiEIN w EZ. 1 k(,, )1 By Theorem 6 is enough calculate
EDPpE t (xx) K (x) N (x)
(40)
for e e N For this purpose, observe that K & (x)
Em ( (x) so that
(Z) K (=)
Σ
om e o x
2m
c. (41)
m2N+1
Therefore, the calculation 40 boils down to the calculation of
EDrrE 4 (xx) @m (2)) (x:) (x) -1,,
(42)
for m 2 N + 1. This is the purpose of the following result.
Theorem 7. Let EnE(Ny 6n ΣnEIN) En E R and 2 N + 1. Then
xx(() 11 (xx "e
Σ EnE.. nE[N]
(43)
In particular,
( -1 K ( Σ Om Σ En
(44)
m NEIN

---

SnuurSeurree aroun
Koque Equaroo areon)
logus ESquaa
kogalNi
legalNi
IngaaNi
EZQ (s
(b) KBIQ 2)
(c) OKQ 2)
6"A
67%
tog Souu/Soaann aroo
Logu Se///Suuaaaa crod
-10
-10
20 Igba/N1
20
30
50
100
20
Ingaahi
kiba/N1
(d) EZQ (8 3)
(c) KBIQ (8= 3)
(f) OKQ (s 3)
Figure 1: Squared worst-case integration error vs. number nodes
EZQ, KBIQ and OKQ in
the Sobolev space of periodic functions of order {2,3].
We give the proof of Theorem in Appendix A.4 Theorem 7
By taking e = = EnE(N (0, onlwen in As for 27). it is suffcient to observe that
we obtain 26
1| Σ
EZ.8 W
k(I,,
13 2 (111g Max 113 + l|
Σ
w EZ. k(xx,.))33)
(45)
KE[M
+E[N]
where ON = EnE(N] (g, wn E EN so that we can apply 266
to IN and we obtain
EpPp
Σ iE[N]
EZ. wi
Σ on)
Σ
om S
11
Σ
(46)
NEIN]
M2
m2
The term ||wg - May |1ž is upper bounded by 11 We give the details in Appendix This concludes the proof of Theorem 3 In the following section, we give numerical experiments illustrating this result.
A
Numerical experiments
In this section, illustrate the theoretical results presented in Section in the case of the RKHS associated to the kernel
(z 1
Σ mEN-
1 cos(2mmm( -y),,
(47)
that corresponds to the periodic Sobolev space of order [0, 1] [ and take w to be the uniform
measure on X' = [0, 1). We compare the squared worst-case integration error of EZQ and OKQ and KBIQ, with M 2.V and 7 a, for æ that follows the distribution of the projection DPP and for e10, e20 J. We take N E [5, 100]. Figure I shows log-log plots of the squared error w.r.t. E e11
N, averaged over 1000 samples for each point, for E (2,3). We observe that the squared error of EZQ converges to at the exact rate (rN++1) predicted by Theorem 3 while the squared error of OKQ converges to 0 the rate ( ) as was already observed in 3. which is still better than the rate Orr441) proved in Theorem 4 Finally, KBIQ (M 2N and
ot) converges to 0 at the rate ( We conclude that, by taking M = aN with a > 1, KBIQ have practically the same averaged error as OKQ (M +oo). As we have mentioned before, the theoretical analysis of KBIQ in the regime when M is finite and strictly larger than N beyond the scope of this work, and we defer it for future work.

---

Conclusion
We studied the quadrature rule proposed by Ermakov and Zolotukhin through the lens of kernel methods. We proved that EZQ and OKQ belong to a larger class of quadrature rules that may be defined through kernel based interpolation. From this new perspective, EZQ may be seen as an approximation of OKQ. Moreover, we studied the expected value of the squared worst-case integration error of EZQ when the nodes follow the distribution of DPP. In particular, we proved that EZQ converges to 0 at the rate O(rN+1) which is slower than the optimal rate O 1) typically observed for OKQ with DPPs. This work shows the importance of the worst-case integration error figure of merit when comparing quadrature rules. Interestingly. we our analysis of EZQ to improve upon the existing theoretical guarantees of OKQ under DPPs. Finally, we illustrated the theoretical results by some numerical experiments that hint that KBIQ in the regime M > N may have similar performances as OKQ. It would be interesting to study this broader class quadratures in the future.
Broader impact
This article makes contributions to the fundamentals of numerical integration, and due to its theoretical nature, the author sees ethical or immediate societal consequence of this work.
Acknowledgments and Disclosure of Funding
This project was supported by the AllegroAssai ANR project would like thank the reviewers for their thorough and constructive reviews and would like thank Pierre Chainais and Rémi Bardenet for their constructive feedback on early version of this work.
The author
10

---

References
[1] R. Bardenet and A. Hardy. Monte Carlo with determinantal point processes. The Annals of Applied Probability, 30(1):368-411 -17, 2020.
[2] A. Belhadji. Subspace sampling using determinantal point processes. PhD thesis, Ecole Centrale de Lille, 2020.
[3] A. Belhadji. R. Bardenet, and P. Chainais. Kemel quadrature with DPPs. In Advances in Neural Information Processing Systems 32, pages 12907-12917. 2019.
[4] A. Belhadji, R. Bardenet, and P. Chainais. Kernel interpolation with continuous volume sampling. Proceedings of the 37th International Coference on International Conference on Machine Learning, 2020.
[5] A. Berlinet and C. Thomas-Agnan. Reproducing kernel Hilbert spaces in probability and statistics. Springer Science & Business Media, 2011.
[6] B. Bojanov. Uniqueness of the optimal nodes of quadrature formulae. Mathematics of compula- tion, 36(154):525-546, 1981.
[7] X. Briol, C. Oates, M. Girolami, and M. Osborne. Trank-Wolfs Bayesian quadrature: Probabilistic integration with theoretical guarantees. In Advances in Neural Information Processing Systems, pages 1162-1170, 2015.
[8] F. X. Briol, C. J. Oates, M. Girolami, M. A. Osbore,, D. Sejdinovic, et al. Probabilistic integration: role statistical computation? Statistical Science, 34(1):1-22, 2019.
[9] Y. Chen, M. Welling, and A. Smola. Super-samples from kernel herding. In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, UAT' 10. pages 109-116, Arlington, Virginia, United States, 2010. AUAI Press.
[10] J. F. Cocurjolly, A. Mazoyer, and P. O. Amblard. Monte carlo integration of non-differemtiable functions on [0, 1]". = 1...., d, using a single determinantal point pattern defined on [0, 1|d. arXiv preprint 20X1v:2003.10323, 2020.
[11] Davis and P. Rabinowitz. Methods of numerical integration. 1984. Comput. Sci. Appl. Math, 1984.
[12] S. De Marchi. On optimal center locations for radial basis function interpolation: computational aspects. Rend. Splines Radial Basis Functions and Applications, 61(3):343-355 2003.
[13] S. De Marchi, R. Schaback, and H. Wendland. Near-optimal data- independent point locations for radial basis function interpolation. Advances in Computational Mathematics, 23(3):317-330 2005.
[14] S. M. Ermakov and V. Zolotukhin. Polynomial approximations and the monte-carlo method. Theory of Probability & Its Applications, 5(4):428 1960.
[15] C. F. Gauss. Methodus nova integralium valores per approximationem inveniendi. apvd Henrievm Dieterich, 1815.
[16] G. Gautier, R. Bardenet, and M. Valko. On two ways to use determinantal point processes for monte carlo integration. In Advances in Neural Information Processing Systems, volume 32, 2019.
[17] P. Glasserman. Monte Carlo methods in financial engineering, volume 53. Springer Science & Business Media, 2013.
[18) J. Hickernell. Quadrature error bounds with applications to lattice rules. SIAM Journal on Numerical Analysis, 1995:1999- 1996.
[19] J. Hickernell. generalized discrepancy and quadrature error bound. Mathematcss of computation, 67(22)):299-33) 1998.

---

[20] J. B. Hough, M. Krishnapur, Y. Peres, and B. Virág. Determinantal processes and independence. Probability surveys, 3:206-229, 2006.
[21] Huszár and D. Duvenaud. Optimally-weighted herding Bayesian quadrature. In Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, UAI'12, 12, pages 377- 386. AUAI Press, 2012.
[22] T. Karvonen, C. Oates, and M. Girolami, Integration in reproducing kernel Hilbert spaces of gaussian kernels. arXiv preprint arXiv:2004. /2654, 2020.
[23] Karvonen and S. Särkkä. Gaussian kernel quadrature at scaled Numerical Mathematics, pages 1-26, 2019.
nodes. BIT
[24] J. Ma, V. Rokhlin, and S. Wandzura. Generalized gaussian quadrature rules for systems of arbitrary functions. SIAM Journal on Numerical Analysis, 23(3):97-9996 1996.
[25] N. Metropolis and S. Ulam. The Monte Carlo method. Journal of the American statistical association, 44(24))333-23 33,1331,,1133-- 1949.
[26] E. Novak, M. Ullrich, and H. Wožniakowski. Complexity of oscillatory integration for univariate sobolev spaces. Journal of Complexiry, 31(1):15 41, 2015.
[27] C. P. Robert and G. Casella. Monte Carlo statistical methods. Springer, 2004.
[28] A. Smola, A. Gretton, L. Song, and B. Schölkopf. A Hilbert space embedding for distributions.
In International Conference on Algorithmic Learning Theory, pages 13-31. Springer, 2007.
12


Reviews:
[{"review_id": "flc262wT33C", "reviewer": "Reviewer_yKqn", "summary": "The authors demonstrate how two kinds of kernel quadrature are related (Ermakov-Zolotukhin quadrature and optimal kernel quadrature) by defining a generalisation that encapsulates both. They then give worst case bounds for Ermakov-Zolotukhin quadrature, which are worse than for the optimal one. However, they then build on this result to tighten the known bounds of optimal kernel quadrature when using a determimental point process to distribute the nodes.\n\nResult is certainly relevant and valuable, though of very niche interest. Still a lot more interesting than most \"0.1% better\" NN papers though! Paper itself is as clear as a wall of maths can be (and has a good intro), but while the precision is critical I will always object to this mode of presentation: maths written without intuition or examples works only for those who already understand the solution. For everyone else it creates an unnecessary challenge to understanding. But maybe this doesn't matter given the niche nature of the result.\n\nTo allow a reader to apply an appropriate weight to this review, it should be known that I have not understood this paper to the standard I would usually obtain. There is too much, I haven't had the time and I remain extremely burned out (or whatever this is; \"brain replaced with tired cloud\" fits just as well) from the extreme workload of the last year. Saying that, given the shear mathematical denseness within this paper I'm not convinced giving it a proper review in the tight time frame of a conference review is actually a realistic prospect.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "Maths looks correct, and no errors have jumped out, but I have not checked it to any real depth, so can't be sure. Notation is very verbose at points, even with the occasional simplification - the visual complexity creates an additional barrier to the reader.\n\nConclusion: \"This work shows the importance of the worst-case integration error as a figure of merit when comparing quadrature rules.\": Does it? It shows that results can be derived and match experimental results, so I would agree with \"useful\". But I see no reason why you could conclude, based on the evidence within, that it's anything more than one of many equally valid bounds, none more important than the next.\n\n\nGrammer etc. issues (all minor):\n\nL11: \"interest interesting\"\nL24: CLTs used without prior definition\nL36: RKHS used without prior definition (though words given two lines above).\nL55: \"We precise\"\nL67: \"integrals that write as\"\nL99: \"this quantity have\"\nL106: \"We precise in\"\nFigure 1: A separate key, shared by all graphs, could probably be made large enough to be readable. In a paper swarming with equations it seems weird to type \"squared error\" for the y-axis!\nNot sure of the wisdom of having appendix A link to \"supplementary.pdf\" - I renamed that file to have the name of the paper in (same directory as other reviews) so link was broken.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "14"}, "extra_text": {}}, {"review_id": "a8ZbmPmGMx", "reviewer": "Reviewer_74Tt", "summary": "The paper gives a kernel quadrature interpretation for certain interpolatory quadrature rules specified by the property that they integrate exactly all functions in certain finite-dimensional spaces spanned by $L^2$-orthonormal functions. Error estimates in expectation are proved when the integration nodes are sampled from a DPP. The authors call these quadratures Ermakov-Zolotukhin quadratures (EZQ).", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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 am very glad to see that the authors are interested in these topics. Unfortunately, I have to recommend that the paper be rejected. The paper contains two contributions: (1) the kernel quadrature interpretation of what the authors call Ermakov-Zolotukhin quadrature (EZQ) and (2) worst-case error estimates for EZQ (when DPP points are used) in RKHSs. As I will detail below, the first contribution is at most of marginal novelty and demonstrates a marked lack of familiarity with literature on interpolatory quadrature. As to the second contribution, I do not know how interesting someone working with DPPs would find the error estimates. In any case, this contribution is very incremental and the proofs are very straightforward applications of an uncorrelatedness result from [15] (and, if written in a more economically, would probably not require a supplement). I also believe that there is a serious error in the proof of one of the main results. Furthermore, the error estimates are quite generic and difficult to use in most cases if one insists on starting from a given kernel because Mercer decompositions are usually unavailable.\n\nThe paper is very well written and, except perhaps for the supplement, a pleasure to read, and would in my opinion suit well for a less prominent venue after some revisions.\n\nON NOVELTY. The central idea of the paper is that quadrature rules defined by the property that they integrate certain $N$ functions exactly can be interpreted as kernel quadratures for a kernel whose RKHS is $N$-dimensional has appeared many times before, even in machine learning community. As the authors mention, this is done in refs. [21] and [22], but to this list I can add and Fasshauer & McCourt 2012 and Karvonen & Särkkä 2017 (both contain some material on the intermediate case $M > N$) as well as the use of kernels in classical quadrature theory, for which I refer to the review in Section 7.2 in Cools 1997. The extension from polynomials (or related functions) used in these works to orthonormal basis functions used in this paper is rather trivial. The authors may also find material on generalised Gaussian quadratures quite familiar (e.g., Ma et al. 1996).\n\n\nON PROOFS AND MATH.\n- Equation (63) in the supplement is not true for general $g \\\\in \\\\mathcal{L}_2(\\\\omega)$. \n\nThis equation would hold only if we had $\\\\mu_g(x_i) = \\\\mu_{g_N}(x_i)$ for every $i \\\\in [N]$, but this obviously is not the case since the l.h.s is\n$$\n\\\\sum_{m > 0} \\\\sigma_m \\\\phi_m(x_i) \\\\langle g, \\\\phi_m \\\\rangle_\\\\omega\n$$\nwhile the r.h.s. is\n$$\n\\\\sum_{m \\\\in [N]} \\\\sigma_m \\\\phi_m(x_i) \\\\langle g, \\\\phi_m \\\\rangle_\\\\omega.\n$$\nThis probably complicates or invalidates the proof Equation (27), which is the main result of the paper.\n- Lemma 1 in the supplement is unnecessary.\n\nEquation (36) in Proposition 5 can be proved by observing that for $g \\\\in \\\\mathcal{E}_N$ the embedding $\\\\mu_g$ is an element of $\\\\mathcal{E}_N$. Since the l.h.s. of (36) is the EZQ estimate of the integral of $\\\\mu_g$ and, by the reproducing property, the r.h.s. equals the integral of $\\\\mu_g$, it follows from the fact that the EZQ integrates all functions in $\\\\mathcal{E}_N$ exactly that (36) is true.\n\n- I see little reason to work with $\\\\epsilon$, $\\\\epsilon'$, the kernel $k^\\\\bot$ and bunch of linear algebra as Equation (26) can be proved in a more transparent way as follows:\n\n\\\\begin{align*}\n\n\\\\bigg\\\\lVert \\\\mu_g - \\\\sum_{i \\\\in [N]} \\\\hat{w}_i^{\\\\text{EZ},g} k(x_i, \\\\cdot) \\\\bigg\\\\rVert_\\\\mathcal{F}^2 &= \\\\bigg\\\\lVert \\\\sum_{m > 0} \\\\sigma_m \\\\phi_m \\\\bigg( \\\\int_\\\\mathcal{X} \\\\phi_m(x) g(x) d \\\\omega(x) - I^{\\\\text{EZ},g}( \\\\phi_m ) \\\\bigg) \\\\bigg\\\\rVert_\\\\mathcal{F}^2 \\\\\\\\\n\n&= \\\\bigg\\\\lVert \\\\sum_{m > N} \\\\sigma_m \\\\phi_m \\\\bigg( \\\\int_\\\\mathcal{X} \\\\phi_m(x) g(x) d \\\\omega(x) - I^{\\\\text{EZ},g}( \\\\phi_m ) \\\\bigg) \\\\bigg\\\\rVert_\\\\mathcal{F}^2 \\\\\\\\\n\n&= \\\\sum_{m,n >N} \\\\sigma_m \\\\sigma_n \\\\langle \\\\phi_m, \\\\phi_m \\\\rangle_\\\\mathcal{F} \\\\bigg( \\\\int_\\\\mathcal{X} \\\\phi_m(x) g(x) d \\\\omega(x) - I^{\\\\text{EZ},g}( \\\\phi_m ) \\\\bigg) \\\\bigg( \\\\int_\\\\mathcal{X} \\\\phi_n(x) g(x) d \\\\omega(x) - I^{\\\\text{EZ},g}( \\\\phi_n ) \\\\bigg) \\\\\\\\\n\n&= \\\\sum_{m > N} \\\\sigma_m I^{\\\\text{EZ},g}( \\\\phi_m )^2 .\n\n\\\\end{align*}\n\nTaking the DPP expectation and, writing $I^{\\\\text{EZ},g}( \\\\phi_m ) = \\\\sum_{n \\\\in [N]} \\\\langle g, \\\\phi_n \\\\rangle_\\\\omega I^{\\\\text{EZ},n}( \\\\phi_m )$ and using the sum of variance formula and Proposition 1 in the supplement yields Equation (26).\n\n\nON THE ROLE OF KERNELS. One of the main points of this paper is that kernel methods help in understanding the Ermakov-Zolotukhin quadrature. I do not completely agree with this and would argue that kernels play merely an incidental role here. The authors take what I would call a kernel-centric approach, selecting a kernel and its Mercer decomposition and constructing the EZQ using the Mercer basis functions. However, one could as well select first an orthonormal basis $(\\\\phi_m)$ of $\\\\mathcal{L}_2(\\\\omega)$ and some non-increasing positive constants $\\\\sigma_m$. Then the results of the paper could be modified to state that the rate of decay of $\\\\sigma_m$ controls the rate of convergence the EZQ in the space of functions whose $\\\\mathcal{L}_2(\\\\omega)$-coefficients decay sufficiently fast to guarantee that Equation (4) holds. That this space happens to be an RKHS under a summability condition on $\\\\sigma_m$ can be considered somewhat coincidental. For example, papers by Irrgeher & Leobacher 2015 and Irrgeher et al. 2015 consider different function spaces that arise when the basis functions are Hermite polynomials and $\\\\sigma_m$ decay with different rates. There is a similar flavour in Zwicknagl & Schaback 2013. Indeed, it is not difficult to derive Equation (26) directly from\n\n$$\n\\\\sup_{ \\\\lVert f \\\\rVert_\\\\mathcal{F} \\\\leq 1} \\bigg \\lvert \\int f(x) g(x) d \\omega(x) - I^{\\text{EZ},g}(f) \\bigg\\rvert^2 = \\\\sup_{ \\\\lVert f \\\\rVert_\\\\mathcal{F} \\\\leq 1} \\bigg \\lvert \\sum_{m > N} \\langle f, \\phi_m \\rangle_\\omega \\bigg( \\int \\phi_m(x) g(x) d \\omega(x) - I^{\\text{EZ},g}(\\phi_m) \\bigg) \\bigg\\rvert^2,\n$$\nthe fact that $\\sqrt{\\text{Eq. (4)}} = \\\\lVert f \\\\rVert_\\\\mathcal{F} \\\\leq 1$ implies that $-\\\\sqrt{\\\\sigma_m} \\leq \\langle f, \\phi_m \\rangle_\\omega \\leq \\\\sqrt{\\\\sigma_m}$, and Proposition 1 in the supplement.\n\nNow, the kernel-centric approach of the authors is of course useful if one is specifically interested in using a certain kernel and understanding how fast certain quadrature rules converge in its RKHS (e.g., ref [21], Kuo & Wozniakowski 2012 or Kuo et al. 2017; some results of this type are also collected in Chapter 6 of Oettershagen 2017) or in approximating the optimal kernel quadrature weights for computational purposes (e.g., ref [22] or Fasshauer & McCourt 2012). But in general this is complicated by the fact that Mercer expansions (or any RKHS-orthonormal bases) are available only for few kernels. The jump from generic analysis in this paper to something that might be useful in practice tends to be substantial. \n\nON TERMINOLOGY. The Ermakov-Zolotukhin quadrature is a rather obscure quadrature method whose distinguishing, as I understand it, feature is the use of nodes drawn from a DPP. However, this article (in particular Section 3) effectively renames all quadrature rules whose weights are solved from Equation (17) as EZQs. This terminology is quite non-standard. For example, all Gaussian quadratures would be special cases of the EZQ (select $\\\\phi_i$ as the orthonormal polynomials for the measure $\\\\omega$). Quadratures whose weights are defined using an equation like (17), which guarantees that they are exact for functions in an N-dimensional function space, are typically called interpolatory quadrature rules (e.g., Section 6.1 in Cools 1997). Furthermore, I don't quite understand the term \"kernel-based interpolation quadrature\" introduced in Section 3.1 as each of these quadratures in Equation (20) is simply an optimal kernel quadrature for a kernel whose RKHS is M-dimensional.\n\nSPECIFIC COMMENTS:\n- Abstract: \"while the weights are defined through a linear system, similarly to the optimal kernel quadrature\". This sentence makes it sound like the quadrature weights being defined as the solution of a linear system is a special property of kernel quadrature. However, this is how the weights of any interpolatory quadrature rule (i.e., a quadrature rule which has N points and which is exact for all elements of some N-dimensional function space) can be computed, including Gaussian, Newton-Cotes and Clenshaw-Curtis quadratures. It is just that this linear-algebraic construction is not computationally efficient or stable for classical quadratures and hence rarely used.\n- Lines 87-92 & 262-3: These give the impression that using the worst-case error in a function space to assess and compare the accuracy of different quadrature rules is a new or recent innovation.\n- Lines 94-95: It may be that Fred Hickernell popularised the use of kernel methods in the QMC community, but the relationship between kernels and numerical integration is much older. Larkin 1970 is the oldest paper that I know of where optimal kernel quadrature appears explicitly.\n- The definition of \"optimal kernel quadrature\" on lines 104-6 is confused: It is first implied that the nodes are fixed (\"for a given configuration\") but later these appear to be free parameters (\"with the nodes and weights that minimize (13)\"). The first interpretation seems to be the one that is used in the paper.\n- Line 120: While perfectly suitable for numerical integration, the so called $P$-greedy points in [11] and [12] do not encode any knowledge about the integration measure $\\\\omega$. This may be worth pointing out.\n- Lines 169-170: I do not see any reason why this approximation would not be valid also for $g \\\\notin \\\\mathcal{E}_N$. In that case the mean embedding vectors defining the EZQ and OKQ weights will of course be different, but for large $N$ the difference will be negligible.\n- It would be helpful to provide the closed-form expression that I believe the kernel in Equation (47) has in terms of a Bernoulli polynomial.\n- The proof of Theorem 3 is confusingly given partially in the main text and partially in the supplement. For example, currently Equation (60) serves no purpose in the supplement.\n\nMISCELLANEOUS THOUGHTS:\n- Taking $\\\\omega$ as the Gaussian measure and the orthornormal basis functions as Hermite polynomials one can obtain the Mehler kernel. See Irrgeher & Leobacher 2015 and Irrgeher et al. 2015 for related error analysis.\n- No $\\\\mathcal{L}_2(\\\\omega)$-orthogonality is necessary to construct a quadrature rule with weights like (17) as in general the vector $e_n$ on the r.h.s. consists of integrals of the basis functions. How necessary is orthogonality really? Is it required in DPP-related results?\n- One way to derive a worst-case result would be to take supremum in Equation (10). This is of course differs from what the authors do in that DPP-expectation and supremum are taken in different order.\n\nMINOR COMMENTS:\n- Lines 54-55: This makes it sound like the eigenfunctions can be taken to be continuous because the eigenvalues are positive and non-increasing, while in reality this follows from the kernel (and hence its RKHS) being continuous.\n- Line 58: $\\\\mathcal{L}(\\\\omega)$ is missing a subscript.\n- Line 125: $\\\\mathcal{L}(\\\\omega)$ is missing a subscript.\n- Line 133: $\\\\mathcal{L}(\\\\omega)$ is missing a subscript.\n- Line 186: \"In particular\" should probably be replaced with \"Furthermore\" or something similar.\n- Subscripts in suprema of Equations (12) and (28) are written differently.\n- Line 243: Reference to [5] could be more specific.\n- Ref [1]: \"Monte carlo\"\n- Ref [7]: \"F. Briol\"\n- Ref [21]: \"hilbert\"\n- $n'$ is somehow messed up in the supplement.\n\nREFERENCES (note that many of these are only tangentially related to the paper)\n\n- Larkin 1970. Optimal approximation in Hilbert spaces with reproducing kernel functions. Mathematics of Computation.\n- Ma, Rokhlin & Wandzura 1996. Generalized Gaussian quadrature rules for systems of arbitrary functions. SIAM Journal on Numerical Analysis.\n- Cools 1997. Constructing cubature formulae: the science behind the art. Acta Numerica.\n- Fasshauer & McCourt 2012. Stable evaluation of Gaussian radial basisfunction interpolants. SIAM Journal on Scientific Computing.\n- Kuo & Wozniakowski 2012. Gauss-Hermite quadratures for functions from Hilbert spaces with Gaussian reproducing kernels. BIT Numerical Mathematics.\n- Zwicknagl & Schaback 2013. Interpolation and approximation in Taylor spaces. Journal of Approximation Theory.\n- Irrgeher & Leobacher 2015. High-dimensional integration on $\\\\mathbb{R}^d$, weighted Hermite spaces, and orthogonal transforms. Journal of Complexity. \n- Irrgeher, Kritzer, Leobacher & Pillichshammer 2015. Integration in Hermite spaces of analytic functions. Journal of Complexity.\n- Karvonen & Särkkä 2017. Classical quadrature rules via Gaussian processes. In 27th IEEE International Workshop on Machine Learning for Signal Processing.\n- Kuo, Sloan & Wozniakowski 2017. Multivariate integration for analytic functions with Gaussian kernels. Mathematics of Computation.\n- Oettershagen 2017. Construction of Optimal Cubature Algorithms with Applications to Econometrics and Uncertainty Quantification. PhD dissertation.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is little discussion on limitations of the theoretical results. As I mentioned in the main review, my opinion is that generic results like these tend to be quite difficult to apply to concrete numerical integration problems.\n\nFurthermore, throughout the paper it is assumed that the truncated kernel matrix $\\\\kappa_N(x)$ is non-singular. While DPP sampling should ensure this, it is not difficult to come up with reasonable nodes for which the matrix is singular. This topic is known as unisolvency in the literature.", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "TD27rOYcI-J", "reviewer": "Reviewer_LzsW", "summary": "The authors improve integration error bounds of Ermakov and Zolotukhin quadrature, and optimal quadrature with DPP sampled nodes for functions from the associated RKHS. ", "questions": "", "limitations": "", "rating": 6, "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": "Clarity\n------------\nThe paper is written very clearly and I was able to follow it easily.\n\nNovelty\n-----------\nI am not very familiar with the related works, hence I am not sure if the list of related works is exhaustive that authors provide, but their presentation seems genuine. \n\nContributions\n-----------------\nThis paper has an easy and quick result improving a bound for optimal quadrature by a factor of N^2 and EZ from a sum of tail of eigenvalues to the largest eigenvalue not in the approximated operator. I was not aware of this being an important open problem since EZ or general DPP sampled nodes is not something I tended to use in practice. \n\nThe paper discusses general classes of quadratures where both instances fall, but I do not think this is particularly englighting, and in the context of quadratures one can compartmentalize the rules in many different ways.\n\nWhile this paper certainly brings contributions in it, it left me with the feeling that the contributions are small, especially in the context that I do not find these EZ or DPP based quadratures very practical. While it is true that finding optimal nodes is indeed NP hard, often this is solved in a greedy way. But this opinion of mine does not diminish the contribution this paper carries with itself. In my opinion it just limits the target audience. \n\nVerdict\n--------------\nI see no problem in accepting this paper but papers with more practical relevance should be given priority appearing at NeurIPS in opinion, since this paper has, in my opinion, a limited audience. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work.", "review_text": "", "extra_scores": {"ethical_concerns": "None identified.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "QUq1UwhK94", "reviewer": "Reviewer_sHED", "summary": "This paper studies a classic quadrature rule by Ermakov and Zolotukhin and its connections to kernel quadrature rules with DPPs. The authors show that these quadrature rules can be interpreted as special cases of kernel-based interpolation quadrature rules formulated in the paper. By analyzing the worst-case error in an RKHS for the Ermakov-Zolotukhin quadrature, they provide an upper bound on the worst-case error of kernel quadrature with DPPs that improves upon the upper bound in previous work. Synthetic experiments are provided for validating the obtained theoretical results.", "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": "[Originality]\nTo my knowledge, the obtained results are novel and original. This paper makes a nice contribution to the literature on kernel quadrature rules by establishing a connection to an old work by Ermakov and Zolotukhin, which has not been well known in the community.  \n\n[Quality]\nThe paper's quality is high. While I have not checked the proofs in the supplementary materials, the proof sketches in the main body are convincing. The literature review is done adequately.  Experiments are well designed. \n\n[Clarity]\nThe paper is basically clearly written. While the presentation is adequate for experts, it may be a bit hard to follow for non-experts. A few suggestions:\n\n- The title should be more appealing to a wider audience. For instance, you could include ``DPPs'' in the title. \n\n- You should explain what $g$ and $\\omega$ are in a usual setting. I suppose $\\omega$ is a probability measure of interest, and usually we set $g(x) = 1$ as a constant function.\n\n- Lines 71-72: ``$e_n$ is the $n$-th element of the canonical basis of $\\mathbb{R}^N$'' Can you simply say that this is a $N$-vector with the $n$-th coordinate is $1$ and the rest are $0$?\n\n- Theorem 3.  I think ``In particular\" just before Eq. (27) is misleading, because  (27) is not a special case of (26) but needs to proved using (26). Maybe ``moreover'' is appropriate. \n\n- Experiments: Can you explain why the different choices of $g$ lead to different convergence behaviors? These $g$ are all canonical, and I don't know why they result in different behaviors.\n\n- It would be nice if you explain whether it's easy to generate sample points from the DPP with the truncated kernel. \n\n[Significance] \n- Theorem 4, which is a direct corollary of Theorem 3, is really nice, in that it provides a sharper error bound for kernel quadrature with DPPs than the previous work by [3]. This previous work's convergence bound is not very tight and does not capture the real empirical performance of kernel quadrature with DPPs. Theorem 4 in the current paper solves this problem, and this is a nice contribution to the literature. Conceptually, this paper's contribution provides theoretical support for the use of DPPs in the construction of nodes for kernel quadrature. \n", "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": "16 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper identifies connections between the literatures on kernel quadrature and determinantal point processes and uses these connections to perform theoretical analysis for a quadrature method due to Ermakov and Zolotukhin.  The reviewers agreed on the correctness and the extent of the novelty of the paper (somewhat incremental), but strongly disagreed about its significance, with one reviewer arguing that the Ermakov-Zolotukhin method is not widely used and thus unimportant, and one reviewer championing the paper as being of theoretical interest.  I believe the balance is somewhere in between these extremes - this paper makes a small theoretical contribution, but it is nevertheless one that will interest a subset of the participants at NeurIPS.
Decision: Accept (Poster)