Small coresets via negative dependence: DPPs, linear statistics, and concentration
Authors: Rémi Bardenet
Subhroshekhar Ghosh
Hugo Simon-Onfroy
Hoang-Son Tran
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Coresets
determinantal point processes
concentration inequalities
Primary area: probabilistic_methods
TL;DR: Determinantal point processes provably yield coresets with better accuracy guarantees than independent sampling.

Abstract: Determinantal point processes (DPPs) are random configurations of points with tunable negative dependence. 
Because sampling is tractable, DPPs are natural candidates for subsampling tasks, such as minibatch selection or coreset construction. 
A \emph{coreset} is a subset of a (large) training set, such that minimizing an empirical loss averaged over the coreset is a controlled replacement for the intractable minimization of the original empirical loss.
Typically, the control takes the form of a guarantee that the average loss over the coreset approximates the total loss uniformly across the parameter space.
Recent work has provided significant empirical support in favor of using DPPs to build randomized coresets, coupled with interesting theoretical results that are suggestive but leave some key questions unanswered.
In particular, the central question of whether the cardinality of a DPP-based coreset is fundamentally smaller than one based on independent sampling remained open.
In this paper, we answer this question in the affirmative, demonstrating that \emph{DPPs can provably outperform independently drawn coresets}. 
In this vein, we contribute a conceptual understanding of coreset loss as a \emph{linear statistic} of the (random) coreset. 
We leverage this structural observation to connect the coresets problem to a more general problem of concentration phenomena for linear statistics of DPPs, wherein we obtain \emph{effective concentration inequalities that extend well-beyond the state-of-the-art}, encompassing general non-projection, even non-symmetric kernels. 
The latter have been recently shown to be of interest in machine learning beyond coresets, but come with a limited theoretical toolbox, to the extension of which our result contributes. Finally, we are also able to address the coresets problem for vector-valued objective functions, a novelty in the coresets literature.

Small coresets via negative dependence: DPPs, linear statistics, and concentration
Rémi Bardenet
Subhroshekhar Ghosh Department of Mathematics National University of Singapore
Univ. Lille, CNRS, Centrale Lille,
UMR 9189 CRISIAL. F-59000 Lille, France
10 Lower Kent Ridge Road, 119076, Singapore subhrowork@@aiil. com
remi wardeneteenrss......m.. frr
Hugo Simon-Onfroy Université Paris-Saclay, CEA, Irfu Département de Physique des Particules 191, Gif-sur- Yvette, France hugo. simon@cea.fr
Hoang Son Tran *f
Department of Mathematics National University of Singapore 10 Lower Kent Ridge Road, 119076, Singapore hoangson.. tranCu. nus edu
Abstract
Determinantal point processes (DPPs) are random configurations of points with tunable negative dependence. Because sampling is tractable, DPPs natural can- didates for subsampling tasks, such as minibatch selection or coreset construction. A coresef subset of (large) training set, such that minimizing an empirical loss averaged over the coreset is a controlled replacement for the intractable min- imization of the original empirical loss. Typically, the control takes the form of a guarantee that the average loss over the coreset approximates the total loss uni- formly across the parameter space. Recent work has provided significant empirical support in favor of using DPPs to build randomized coresets, coupled with interest- ing theoretical results that are suggestive but leave some key questions unanswered. In particular, the central question of whether the cardinality of DPP-based coreset is fundamentally smaller than one based on independent sampling remained open. In this paper, answer this question in the affirmative, demonstrating that DPPs can provably outperform independently drawn coresets. In this vein, we contribute conceptual understanding of coreset loss as linear statistic of the (random) coreset. We leverage this structural observation to connect the coresets problem to more general problem of concentration phenomena for linear statistics of DPPs, wherein we obtain effective concentration inequalities that extend well-beyond non-symmetric
the state-of-the-art, encompassing general non-projection, kernels. The latter have been recently shown to be of interest machine learning beyond coresets, but come with limited theoretical toolbox, to the extension of which our result contributes. Finally, we are also able to address the coresets problem for vector-valued objective functions, a novelty in the coresets literature.
Introduction
Let X' {x, i E [1,n]} } be set of n points in Euclidean space, called the data set. Let F be set of nonnegative functions on X' called queries. Many classical learning problems, supervised or
'The authors listed alphabetical order by their surnames Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

unsupervised, are formulated as finding a query f in F that minimizes an additive loss function of the form
I0))= == Σ ((x)S(x),
(1)
xEX
where je: :u:- R+ is weight function. Example 1 (k-means). For X' C I& and & N, the goal of k-means clustering is to find set C* of "cluster centers" by minimizing (1) over
=-{ fc x+ min x a|ا c c R |C| = k
gEC
Here, each query f is indexed by set of ls cluster centers, and the loss (1) is the quantization enror.
Example 2 (linear regression). When X' {z; == (v:, 2i) [1, C [d+1, linear regression corresponds to minimizing (1) over
F = (v, =) + (a (aT y + b- =)² E R R]. Penalty terms can be added to each function, to cover e.g. ridge or lasso regression.
In many machine learning applications, the complexity of the corresponding optimization problem grows with the cardinality n of the dataset. When n > makes optimization intractable, one is tempted to reduce the amount of data, using only tractable number of representative samples. This the idea formalized by coresets; we refer to (Bachem, Lucic, and Krause, 2017) for a survey, and to (Huang, Li, and Wu, 2024; Cohen-Addad, Larsen, Saulpic, Schwiegelshohn, and Sheikh-Omar, 2022) for specific coreset constructions for k-means and Euclidean clustering. An E-coreset is a subset S X, possibly with corresponding weights w(x), E S, such that
Ls(f)= := (())f())
#ES
within of L(f), uniformly in f E F. If the cardinality m of significantly smaller than the intractable size of the original data set, one has reduced the complexity of the algorithm at a little cost in accuracy.
Many randomized coreset constructions, where such guarantees are shown to hold with large proba- bility, built by drawing elements independently from the data set X' (Bachem et al., 2017, Chapter 3). Because representative coreset should intuitively be made of diverse data points. negative dependence between the coreset elements has been proposed as an effective possibility improve their performance (Tremblay, Barthelmé, and Amblard, 2019). In particular, the authors advocate the use of Determinantal Point Processes (DPPs), a family of probability distributions over subsets of X kernel matrix K that enforces diversity, all of this while coming with
parametrized by an polynomial exact sampling algorithm.
Tremblay er al., 2019 give extensive theoretical and empirical justification for the use of DPPs in randomized coreset construction. In one of their key results, using concentration results in (Pemantle and Peres, 2011), Tremblay et al., 2019 bound the cardinality of a DPP-based g-coreset, and their bound is (s) However, it is known that the best e-coresets built with independent samples also of cardinality O) Thus, the crucial question of whether DPP-based coresets can provide strict improvement remained be settled; given the computational simplicity of independent schemes, this would be fundamental to justify the deployment of DPP-based methods.
In this paper, settle this question in the affirmative, demonstrating that for carefully chosen kernels, baP-based coresets provably yield significantly better accuracy guarantees than independent schemes; equivalently, achieve similar accuracy it suffices to significantly smaller coresets via DPPs. In particular, we will show that DPP-based coresets actually achieve cardinality = (==-2/(1+d) The quantity depends on the variance of the subsampled loss under the considered DPP, and some DPPs yields d > 0. A cornerstone of our approach is structural understanding of the coreset loss (2) as a so-called linear statistic of the random point set S, which enables us to go beyond earlier results that were based on concentration properties of general Lipschitz functions of DPP (Pemantle and Peres, 2011). In this endeavour, we obtain very widely-applicable concentration inequalities for linear statistics of DPPs compared to the state of the art; cf. (Breuer and Duits, 2013) that mostly focuses on scalar- valued statistics for finite rank ensembles on R. In particular, are able to address all DPPs that

---

have appeared so far in the ML literature. Specifically, our results are able to handle non non-symmetric kernels and vector-valued linear statisties.
DPPs with non-symmetric kernels have recently been shown to be of significant interest in machine learning, such recommendation systems (Gartrell, Brunel, et al., 2019; Gartrell, Han, al., 2020; Han et al., 2022), but they come with a limited theoretical toolbox, to which this paper makes a contribution. On the other hand, vector-valued statistics arise naturally in many learning problems, including coreset settings such as the gradient estimator in Stochastic Gradient Descent (Bardenet, Ghosh, al., 2021). However, the literature on coresets for vector-valued statistics is scarce, and in this paper we inaugurate their study with effective approximation guarantees via DPPs.
The rest of the paper is organized as follows. Section 2 contains background on DPPs and coresets. Section contains our contributions. Section 4 provides numerical illustrations. Section 5 contains a discussion limitations and future work.
2
Background
We introduce here the two key notions determinantal point process and coreset, and observe that a coreset guarantee is uniform control over specific linear statistics of a point process.
Determinantal point processes. A point process S Polish space X' a random locally finite subset of X. Given a reference measure on X' (e.g., the Lebesgue measure if X = IR or the counting measure if X is discrete), a point process is called DPP (w.rt. μ1) if there exists measurable function K : X x X + C such that
E Σ f f m f xx f(11...., 2k) det [et[K(ax (2;, (, my)]kx du oh (21,.... 2k),
where the sum in the LHS ranges over all pairwise distinct k-tuples of the random locally finite subset S, for all bounded measurable f: x²* + R and for all & N. Such function K is called kernel for the DPP S, and is called the background measure.
When the ground set X' is of finite cardinality an equivalent but more intuitive way to define DPPs as follows: a random subset S of X' is called DPP there exists an n x n-matrix K such that
IP C S) = det[Kr], VTC X
where Ky denotes the submatrix of K with rows and columns indexed by T.
In a similar vein to Gaussian processes, all the statistical properties of a DPP are encoded in this kernel function K and background measure A feature of DPPs with far-reaching implications for machine learning is that sampling and inference with DPPs are tractable. We refer the reader to (Hough et al., 2006; Kulesza and Taskar, 2012) for general references. Originally introduced in electronic optics (Macchi, 1975), they have been turned into generic statistical models for repulsion in spatial statistics (Lavancier et al., 2014; Biscio and Lavancier, 2017) and machine learning (Kulesza and Taskar, 2012: Belhadji et al., 2020a; Brunel, 2018; Derezinski and Mahoney, 2019; Derezinski, Liang, et al., 2020: Gartrell, Brunel, et al., 2019; Ghosh and Rigollet, 2020).
Example 3 (L-ensemble and m-DPP). Let be a finite set of cardinality n, μ be the counting n-matrix. The L-ensemble with parameter L is the
measure, and L be a positive semi-definite point process S on X' such that, for all C X, IPSS = T) x de]] where Lr is the square submatrix of L corresponding to the rows and columns indexed by the subset T. It can be shown that S a DPP on X' with kernel K := L(I + L)-!, In general, the cardinality of S is a random variable. By conditioning the event { m) obtain the so-called m- DDPS (Kulesza and Taskar, 2012).
= Rd and μ be measure on Rd having all moments finite, let (р*) the orthonormal sequence resulting from applying the As taken in the graded lexical order. The kernel k((") (ar y) := m-1 Ps (x) then defines a projection DPP on RRd called the multivariate Orthogonal Polynomial Ensemble (OPE) of rank m and reference measure J.
Example 4 (Multivariate OPE; Bardenet and Hardy, 2020). Let X=
Gram-Schmide procedure to the monomials 2 ...
Multivariate OPEs were used in (Bardenet and Hardy, 2020) nodes for numerical integration, leading to Monte Carlo estimator with mean squared error decaying in m -1-1/d faster than under
3

---

independent sampling. In (Bardenet, Ghosh, and Lin, 2021), the authors investigated the problem of DPP-based minibatch sampling for Stochastic Gradient Descent (SGD), and exploited a delicate interplay between a finite dataset and its ambient data distribution to leverage this fast decay for improved approximation guarantees. In particular, they proposed the following DPP defined on a (large) finite ground set.
Example 5 (Discretized multivariate OPE; Bardenet, Ghosh, al., 2021). Let N and X' {zi..... y C 1-1,1]4 Let g(z)dzz be a probability measure on [-1, 1j.. Let k(()) be the multivariate OPE kernel of rank m with reference measure q(x)dx, defined in Example 4. Let y: 1=1-1,1] + R+ be function, assumed to be positive on X,, and consider
q(x))
( 7(v)
K KM (z, v) =
K
(m))
(z,, v)
2,y E [-1,1]
(xx)
Consider then the n x n matrix K = K 9. xxx.. K is symmetric and positive semidefinite, and we let K be the matrix with the same eigenvectors. the m largest eigenvalues replaced by 1, and the remaining eigenvalues replaced by 0. Then K defines a DPP on X.
(m))
Coresets. Let > 0 and X' be set of cardinality n. The classical definition of a coreset is multiplicative.
Definition (multiplicatiiv coreset). A subset 8 C X is an e-multiplicative coreset if
[s(f)
YFEF L(f)
1 c,
where I. and Ls are respectively defined in (1) and (2).
An immediate and important consequence of (2) is that the ratio of the minimum value of Ls by that of L is within OE)) of (Bachem et al.. 2017, Theorem 2.1).
One way to satisfy (2) with high probability for a single f is through importance sampling, taking S to be formed of m > 0 i.i.d. samples from some instrumental density q on X, and taking w = /t/q in (2). Langberg and Schulman, 2010 showed that a suitable choice of q actually yields the uniform guarantee (2). It suffices take for instrumental pdf q(x) x u(x)s(x)), where s upper-bounds the so-called sensitivity
f(x) ΣnEX H(b)f(y)'
s(x) 2 sup JEF
Ve E x
For > 00 Sa 1og2/5 independent draws are then enough to build an e-multiplicative coreset, where 5 5 -xExxx (x))s(x);; see (Bachem al., 2017)[Section 2.3]. The tighter the bound (5), the smaller the size of the coreset. One important limitation is that finding tight bound is nontrivial.
2.2
Although not standard, natural alternative definition of coreset is that of an additive coreset. Definition 2 (additive coreset). A subset S X' is e-additive coreset if
1
Ls - L(f) V.
(6)
Note the arbitrary scaling factor 1/n in (6) compared to (2), which we adopt to simplify comparisons between the two coreset definitions. With an additive coreset, the minimal value of Ls is guaranteed to be within ins of the minimal value of L: Similarly to a multiplicative coreset, with suitably small one should be happy to train one's 's algorithm only on S.
Coreset guarantee and linear statistics. Let S be point process finite X (xI,.... ,,, For test function X' + R, we denote by A(p) Exes (xx) the so-called linear statistic of fo. In a coreset problem, for a query f E F, the estimated loss Ls(J) ) in (2) is the linear statistic A(wf). When S is DPP with kernel K on X' (w.rtt the counting measure), we will choose the weight w(x) = K(r, -1, where for I = H; E X, we define K(x,0) to be Kü. By (3), this choice makes Ls(J) an unbiased estimator for L(J). Guaranteeing a coreset guarantee such as (6) with high probability thus corresponds to a uniform-in-/ concentration inequality for the linear statistic A A(w] This motivates studying the concentration of linear statistics under DPP, which we now turn.
'Noe that we defined coreset as subset and not sub- multiset of X. thus ignoring multiplicity. This is because we allow weights in (2), that repeated items are unnecessary in coreset.

---

Theoretical results
We first give new results on the concentration of linear statistics under very general DPPs. These results are of interest in their own right, and should find applications in ML beyond coresets. Next we examine the implications of the concentration of linear statistics for coresets, showing that a suitable DPP does yield a coreset size of size o(- thus beating independent sampling.
Concentration inequalities for linear statisties of DPPs. We start with Hermitian kernlls.
Theorem 1 (Hermitian kernels), Let S be DPP Polish space X with reference measure p. and Hermitian kernel K. Then for any bounded test function X - IR, we have
P((A()) - -[A(p)] 2 2) 5 (- aar A(p)
2A Var [A(4)]
4A SO
3//4
where is a universal constant.
Our Theorem is similar in spirit to a seminal concentration inequality by Breuer and Duits, 2013. However, their result only applies to DPPs with Hermitian projection kernels of finite rank. We emphasize that our Theorem is applicable to all Hermitian kernels general Polish spaces.
In view of recent interest in machine learning on DPPs with non-symmetric kernels, we present here concentration inequality for such DPPs. We propose a novel approach to control the Laplace transform the non-symmetric case (which can also be applied to the symmetric setting). As trade-off, the range for becomes bit smaller. For simplicity. we present the result for a finite ground set, but the proof applies more generally.
Theorem 2 (Non-symmetric kernels). Let S be DPP a finite set X ( Fn) with non-symmetrie kernel K. Then for any bounded test function &p X - R, we have
Var [Ax))
P(IA()) ((A())E|A(((]] 2 e) s 2exp 4-ar
YO 5O
[A(T)
40 max(1,
K (( )
|K|]
where || llop denotes the spectral norm and || || denotes the nuclear norm of a matrix.
Remark 2.1. For simplicity, we will use the concentration inequality in Theorem 1 from now on. However, we keep in mind that we always can apply Theorem to deduce analogous results for non-symmetrie kernels.
We conclude with a concentration inequality for linear statistics of vector-valued functions.
Theorem (Vector-valued statistics). Let S be a DPP on Polish space X with reference measure I and Hermitian kernel K. Let (fI...., .p). and we denote by A()), V(Ø) the vectors (= and [A(p])))))]] 1/2 R respectively. Let ||=113 = > wi |r,|2 be a weighted norm on RP for some weights W1,... up 0. Then, for some
X Hº be a vector-valued test function,
universal constant A 0, we have
P(IA(D) - B[A( 2 2pexp (- (
for S S 2A I. Sisp
Var(A(ee] 11
DPPs for coresets. We demonstrate the effectiveness of concentration inequalities for linear statistics of DPPs in the coresets problem, achieving uniform approximation guarantees over function classes. To accommodate as many ML settings as possible, we shall consider two natural types of function classes: vector spaces of functions (A.1) and parametrized function spaces (A.2).
For vector spaces of functions, we assume that
dim spang (F) D oc for some D.
(A.I)
This assumption covers common situations like linear regression in Example 2, where we observe that each / F is quadratic function in (d + 1) variables. Thus the dimension the linear span of F is at most (d 1)2 (d 1) Another popular class of queries, originating in signal processing
5

---

problems, is the class of band-limited functions. A function f T + R (where T denotes the d-dimensional torus) said to be Land-limited there exists B E N such that its Fourier coefficients fki..... kid) whenever there is a k such that [ky] > B. It is easy to see that the space of B B-bandlimited functions satisfies dim I (2B + 1)d.
Another common scenario is when F is parametrized by a
parameter space:
F = {fo : 0 E E). where θ is a bounded subset of RR for some D,
(A.2)
llfe llx S E110 0'll for some L > O, uniformly on O.
(A.3)
Conditions (A.2) and (A.3) cover c.g. the k-means problem of Example 1, well (non-)linear regression settings. For k-means, for instance, each query is parametrized by its cluster centers C= -((4...., Ik. which can be viewed as parameter (41 (41..... 4k) E g&d
Finally, with the idea in mind to derive multiplicative coresets from additive ones, we note that since L(f) is typically of order n (for any f whose effective support covers a positive fraction of the ground set), natural to assume that
|L()2 c, for some c > O, uniformly on F.
(A.4)
Theorem 4. Let S be a DPP with Hermitian kernel K on a finite set X (x1,.... Inl and m B||ST]. Assume that for all i E {l....,m) Kü 2 p. un/nffor some p > 0 not depending on m, n. Let V 2 supser Var [n [sf)]. Under (A.1) and (A.4).
P E
[.s(I) L(f)
- -1| 2) S 2xx 6DD
16AV):
622
0 OSES 3esup ll
4ApmV
Assuming (A.2), (A.3), (A.4) and |S| S B- . m a.s. for some B > 0, we have
Ls(f)
C²E²
4ApmV
PP P(3SEF:
T(J) 26) S 2exp (CD- -logg
0385
16AV
3csupjeF |/
Here A > 0 is a universal constant and C = C(O, B,B, p, > 0 is some constant.
Remark 4.1. For a bounded query J. Var [ Ls)) = ) i..d. sampling, In compari- son, sampling with DPPs often yields smaller variance for linear statistics, in O(m for some > 0; see Section 3 for an example. Thus, the upper bound for the range of e for which we could use our concentration result is O(m -6). Plugging in ma for 5 gives the upper bounds 2 2xxp(6D - C' C'mm- m and 2 exxp CD + aD Dog m C" (66-22)) respectively (C and C' are some positive constants independent of m and ni), which both converge to O as m. - 00 as long as a < (1 + 82/2 In other words, the accuracy rate E can be chosen to be as small as m -1/2-88 /2, for any 0 < 8' < 5, which is strictly smaller than the best accuracy rate m m1/2 i...d. sampling.
Remark 4.2. For i..dd sampling S with expected size m, P( E = =)mmm/ n for all DPP S with kernel K. one has P(z; E S) 10==K, Ki.. Thus, assuming thatfor all i, K₁ 2 p. m/n-for some p > means that every point in the datasel X should have a reasonable chance to be sampled. This also guarantees that the estimated loss T.s(J) Exes (xx) (2/// x) will not blow up, where for I = 2; E X, we write K(x, for K
X. For
Remark 4.3, For the parametrized function spaces, the assumption |S| S B. a.s. is not strictly necessary, and is introduced here only for the sake of simplicity in presenting the results. version of Theorem 4 without this assumption will be discussed in Appendix A.4. In fact, we only be bounded with high probability, which follows from the condition K(x, x) 2 p. m/n and the fact that [S] is highly concentrated around its mean m.
need "ExEs K(I,x)
Remark 4.4. However, we remark that the assumption |S| < B a.s. holds for most kernels of interest; DPPs with projection kernels being rypical and significant examples. In machine learning terms. it entails that the coresets are not much bigger than their expected size m; whereas in practice, sampling schemes typically produce coresets of a fixed size (such as with projection DPPs).
Remark 4.5. It is straightfowwall to derive a version for additive coresets from Theorem 1. In fact, we will not need assumption (A.4) in the additive setting.

---

For the coresets problem for vector-valee functions, let F consist of f:f: X - R". For each f E F. we denote by (f), (f) and V(f) the vectors in Rº whose i-coordinates are Ls(f.). L(fi) and Var [n='Ls(f [f.) 1/2 respectively. Let | Di= wf |o,| be weighted norm on R".
Theorem 5. Let S be a DPP as in Theorem 4. Let V 2 supfer maxisisp w/ Var [n Ls (f().. Assuming (A.1). then
P(EfEF: -
[[(L((f) [(f]ll 22) - 2p exp (6D
C²E²
16AV
where 0 S S
4ApmV
(supres maxi=l....." llfelloo) (1f
3c
We revisit Example 5. It has been shown in (Bardenet, Ghosh, et al., 2021) that sampling with the DPP S constructed in this example yields significant variance reduction for wide class of linear statistics on X. To be more precise, in their setting, X' = [I Fn is a random data set, where 24's ' are i..d. samples from a distribution with support inside d-dimensional hypercube; measure on that hypercube. The DPP S is then defined by the kernel K in Example 5 w.r.t. the empirical measure n Erexdo 8r. We normalize the kernel by setting K == n n" so that S is DPP with kernel K w.r.t. the counting measure on X. Then, under some mild assumptions on y and ((r)dr, with high probability in the data set X. we have Var [n (fs) O(m (1+1/d)) (mm(11+/d)) for any test function f satisfying some mild regularity conditions. For more details, we refer the reader to (Bardenet, Ghosh, et al., 2021).
Application: Discretized multivariate OPE.
density estimator for 7 and q(x) is a reference
The significant reduction on the variance of linear statistics motivates us to apply Theorem 4 to this setting. We also remark that all assumptions on the kernel in Theorem 4 are satisfied for K with high probability in the data set X' (see Appendix A.6). Let F be family of test functions on X' satisfying regularity conditions as in Bardenet, Ghosh, et al., 2021. Then we can state:
Theorem 6. For Omm -1dd), w.h.p. in the data set X, we have
Ls(f) L(f)
Ps 3f E
- 2 26) 2eexp (6D- 100-Cemmm+1/p assuming (A.1),
and
L(f) Ls(f) -1| -1 S 2exp (CD-Dlog L'''Doog-C'''mmtaaii (2/)) assuming (A.2), (A.3),
Ps Bf (3f
where I's indicates the randomness only in S and C, C" > do not depend on m, n.
Remark 6.1. Theorem 6 confirms the discussion in Remark 4. for this particular example of DPP. More precisely, Theorem 6 implies that, with probability tending to 1, sampling with this DPP gives Ls((f/L(f) 1|5 m (1 2a) Wff F, where (2 + 2n) denotes any positive number strictly smaller than 28' Meanwhile, for i...d. sampling, the accuracy rate & is at best m1/2
Remark 6.2. It may be noted that, DPPs being Hilbert space-based models, they interact well with linear projection based methods. As such, our method can be applied on dinensionally reduced data, wherein the d in Remark 6.1 can be taken to be the reduced dimension, which is usually quite small. As such, the improvement in the approximation guarantees is substantial, especially for large scale problems entailing large
4 Experiments
In this section, we compare randomized coresets for the k-means problem of Example 1, on different datasets. One virtue of k-means as a benchmark is that asymptotically tight upper-bound on sensitivity (5) can easily be computed (Bachem et al., 2017, Lemma 2.2).
Competing approaches. We compare different coreset samplers." 4 Each sampler takes as input a finite dataset X, an integer m, and sampler-specific parameters. It returns a random subset S C X' of
'The link to GitHub repository is temporarily hidden for anonymity.
7

---

cardinality m. For the associated weight function w in (2), we always take the inverse of the marginal probability of inclusion, i.e. w(x) = 1/P(z S).
The first two baselines use independent sampling. The uniform method returns m samples from X' uniformly and without replacement, and runs in (m)) The second method, sensitiviss is specific to the k-means problem. It corresponds to the classical sensitivity- importance sampling coreset of Langberg and Schulman, 2010 described in Section 2. It runs in Onk + nm).
The rest of the methods use negative dependence. The third method, termed G-mDPP, uses an mnDPP sampler where the likelihood kernel is Gaussian kernel, with adjustable bandwidth denoted by h. is basically Algorithm of Tremblay et al., 2019, except we do not approximate the likelihood kernel using random features. We prefer avoiding approximations in this paper to isolatedly probe the benefit of negative dependence, but our choice comes at the cost ((2)) of performing SVD as a preprocessing, in addition to the usual O( sampling time. Similarly, we compute the marginal probabilities of inclusion of m-DPPs exactly, via Equation (205) and Algorithm 7 of Kulesza and Taskar. 2012. These costly steps will likely be approximated in real data applications; see the discussion of complexity to Section 5. The fourth method, OPE, is the discretized OPE of Example 5, We take q to be product of univariate beta pdfs, with parameters tuned to match the marginal moments of the dataset, as in (Bardenet, Ghosh, et al., 2021). We take 7 to be a kernel density estimator (KDE) built on X. using the Epanechnikov kernel, with Scott's bandwidth selection method, package (Pedregosa et al., 2011). When KDE estimation precomputed as in our experiments, the method runs in O(um²), and On + nmm² otherwise. Note that there is no cubic power of as one can perform the eigenvalue thresholding in Example 1 by reduced SVD of the m x n feature matrix (p& (x:)), The fifth method, termed Vdm-DPP, is Algorithm 2 of Tremblay et al., 2019, which runs in O O(nm²) ). It is an OPE in the sense of Example 4, but where the reference measure μ is the discrete empirical measure of the dataset. Although we have no result on how its linear statistics scale, its similarity with the discretized OPE, as well as its numerical performance in the experiments of Tremblay et al., 2019, make us expect Vdm-DPP to behave similarly to OPE. The sixth method, stratified, is stratified sampling baseline limited to the case where X' C [-1, 1] and X' is "well-spread". It partitions [-1, 1] into a grid of m bins, and then independently draws element uniformly in the intersection of X' with each bin. is special case of projection DPP, which runs in O(rm) and has obvious pitfalls, like requiring that X' has non-empty intersection with each bin, which is unlikely to be the case for non-uniformly spread datasets and high dimensions. Yet, this is a simple solution that one would likely implement to probe the benefits of negative dependence.
as implemented in the scikit-less
The performance metric. To investigate the cardinality of a coreset for a given error, we let Qs denote the quantile function of sup (fs( [(J))/T(J), the supremum over all queries of the relative error. Intuitively, Qs(0.9) = 10-2 means that 90% of the sampled coresets have a worst case relative error below 10 We shall look how an estimated Q0.9).) varies with m, especially its slope in log-log plots with respect to m. Now, the set F of all queries for k-means in combinatorially large, even for small values of k. Therefore, each time we need to evaluate the supremum of the relative error, we rather uniformly sample without replacement k elements of X, 100 times and independently, and we take the maximum value of the relative error among these 100 values. Moreover, for each method and each coreset size m, the quantile function Qs (0.9) is estimated by an empirical quantile over 100 independent coresets sampled for each value of m.
Results. We first consider a synthetic dataset of n = 1024 data points, sampled uniformly and independently in [-1, 1]4: see Figure la. We consider d = 2 for demonstration purposes, but we have observed similar results for other small dimensions. Figure 1b depicts our estimate of (0.9) as function of the coreset size m, in log-log format. The two i.i.d. baselines decrease as m as expected. The stratified baseline, intuitively well-suited to uniformly-spread datasets, outperforms all other methods with m -1 rate, consistent with its known optimal variance reduction (Novak, 1988). Finally, the m-PPP and the two DPPs also yicld a faster decay, eventually outperforming the i.i.d. baselines as grows. This is expected for the discretized OPE, as it follows from the theoretical results from Section 3; but it is interesting to see that the Gaussian m-DPP and the Vdm-DPP seem to reach a similar vn -3/4 fast rate. For the Gaussian m-DPP, however, the performance depends on the value of the bandwidth of the Gaussian kernel: in Figure Ic, we see that the rate of decay can go from i.i.d. to OPE-like as the bandwidth increases; this is expected from results like (Barthelmé et al., 2023). Note that the color code of Figure Ic differs from other figures.
8

---

975
9.0
0.25
1024
unffom ameebrtty OFE
unfbem
G-mby bias
G-nDPP b-tue
-0.30
G-nDPP: b-0.10
CanD?P
-075
strailled
GodDP
-1003
(a) Uniform dataset and sample (b) Qs vs. coreset size m
(c) (0(9. vs. coreset size m
Figure 1: Results for the uniform dataset.
In the uniform dataset of Fig. la, the sensitivity function is almost flat, which makes sensitivity behave like uniform. To give edge to sensitivity, now consider the trimodal dataset shown in Fig. 2a, with an OPE sample superimposed. The performance sensitive tivity improves; see Figure 2b, while the determinantal samplers still outperform the independent ones thanks to faster decay. For this dataset,
not easy to stratify, and we thus do not show results for stratified. We note that the size of marker placed at proportional the corresponding weight in the estimator of the average loss. Equivalently, the marker size is inversely proportional to the marginal probability of x being included in the DPP sample.
x)
Finally, we consider the classical MNIST dataset, after a PCA of dimension 4. Figure 2c shows again the faster decay of the performance metric for the two DPPs (OPE and Vdm Vdm-DPP), compared to the two independent methods. However, the advantage progressively disappears as the dimension increases be- yond 4 (unshown), expected from the gain in variance of the discretized multivariate OPE, which be- comes negligible when >> 1; see Section 5 for suggestions on how to prove dimension- caapssiioon-ndeeddeenn decay. The source code used in this work is available gi github. cwm/hs cow/hssmonffeee immonforr/ooo /DPP coresets, where DPP samplers are built upon the Python package DPPy (Gautier et al., 2019).
1.034
data 2325
mnfen
milen
Vila DPP GomDiP h.01
0100ppartha weddddeogg om rel eene
0.00
-005
-3.30
16
111
11
100
107
-05
sxmple dize
sample site
(a) Trimodal dataset and OPE sample
(b) Q0(9. vs. coreset size m
(c) Qs((..) coreset size
Figure 2: Results on other datasets.
5 Discussion
Limitations. Our paper is theoretical contribution, and our approach has several limitations before it can be practical addition to the coreset toolbox. The improvement over independent sampling relies on a variance scaling for linear statistics of a particular DPP, which itself relies on
both 1) an Ansatz that the dataset was generated i.i.d. from some pdf - with a large support, and 2) the availability of good approximation to 7; see Section and (Bardenet, Ghosh, al., 2021). While Item 1) is usually deemed to be reasonable in wide range of situations, solve Item 2) by

---

relying on kernel density estimator, which is costly to manipulate. Another limitation is that the improvement over independent sampling in 1/d and thus progressively vanishes as the dimension increases. Finally, classical caveat is that although tractable, sampling DPP still costs (nmm²), provided the kernel is available in diagonalized form.
Future work. The limitations above set up research program. In particular, an intriguing observa- tion our empirical studies is the comparative performance various DPP-based coreset samplers; several of them exhibit effective performance. While we have sharp theoretical guarantees for the discretized OPE-based scheme, obtaining similar guarantees and parameter-tuning protocols for other samplers, like m- m-DPPs, will be of great practical interest they would bypass the need, e.g. for an approximation to the data-genera mechanism 7. The DPP called Vdm-DPP in Section 4, which is itself an OPE for discrete measure, might be bridge between OPEs and m-DPPs, Vdm- can be seen as a limit of Gaussian m-DPPs (Barthelmé et al., 2023). On a more general note, improving the computational complexity of sampling DPPs remains an active topic, and we should examine which techniques, e.g. by leveraging low-rank structures, preserve the small coreset property. Any breakthrough in the complexity of DPP sampling would also have salutary consequences for the broader program of negative dependence as toolbox for machine learning. On the dependence of the rate the dimension, rate: in numerical integration with mixtures of DPPs, smoothness does bring dimension-inndeeedenn rates (Belhadji al., 2020b). Finally, in a more theoretical direction, extending concentration inequalities for linear statistics beyond the restricted range of E appearing e.g. in Theorem 1 is mathematically challenging problem, with potential learning-theoree consequences.
propose investigate the impact of smoothness of the test functions on the
Acknowledgments and Disclosure of Funding
RB and HSO acknowledge support from ERC grant Blackjack (ERC-2019-STG--63) and ANR AI chair Baccarat (ANR-20-CHIA-0000) SG was supported in part by the MOE grants R- R-146-000- 250-133, R-146-000-312-1144 A- A-8002014-00-00 and MOE-T2EP20122-00113 HST was supported by the NUS Research Scholarship.
References
[1] Olivier Bachem, Mario Lucic, and Andreas Krause. "Practical Coreset Constructions for Machine Learning". In: arXiv: Machine Learning (2017). URL: https : / api
semanticscholas org/CorpusllI 88511375.
[2] Rémi Bardenet, Subhroshekhar Ghosh, and Mcixia Lin. "Determinantal point processes based orthogonal polynomials for sampling minibatches in SGD". In: Advances in Neural Information Processing Systems 34 (2021), pp. 16226-16237.
[3] Rémi Bardenet and Adrien Hardy. "Monte Carlo with Determinantal Point Processes". In: Annals of Applied Probability (2020). URL: https: h archives-ouverteee fr/hal- 11311263.
[4] Simon Barthelmé, Nicolas Tremblay, Konstantin Usevich, and Pierre-Olivier Amblard. "Deter- minantal point processes in the flat limit". In: Bernoulli 29.2 (2023), pp. 957-983.
[5] Ayoub Belhadji, Rémi Bardenet, and Pierre Chainais. "A determinantal point process for column subset selection". In: Journal of machine learning research 29. (2020), pp. 1-62.
[6] Ayoub Belhadji, Rémi Bardenet, and Pierre Chainais. "Kernel interpolation with continuous volume sampling". : In: International Conference on Machine Learning. PMLR. 2020, pp. 725- 735.
[7] Christophe Ange Napoléon Biscio and Frédéric Lavancier. "Contrast estimation for parametric stationary determinantal point processes". In: Scandinavian Journal of Statistics 44.1 (2017), pp. 204-229.
[8] Jonathan Breuer and Maurice Duits. "The Nevai condition and a local law of large numbers for orthogonal polynomial ensembles". In: Advances Mathematics 265 (2013), pp. 441 484- URL: https::/ts// //api. httaapp.semaaaa semanti cscholar.
wrg/CorpuuIDD :DDD::19995 119731958.
[9] Victor- Emmmauel Brunel. "Learning signed determinantal point processes through the principal minor assignment problem". "" In: Advances in Neural Information Processing Systems 31 (2018).
10

---

[10] Vincent Adden-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh- Omar. "Improved Coresets for Euclidean k-Means", English. In: Advances in Neural Information Processing Systems 35 36th Conference on Neural Information Processing Systems, NeurlPS 2022. Ed. by S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh. Advances in Neural Information Processing Systems. Publisher Copyright: O 2022 Neural information processing systems foundation, All rights reserved.; 36th Conference on Neural Information Processing Systems, NeurIPS 2022: Conference date: 28- 1-2022 Through 09-12-2022. Neural Information Processing Systems Foundation, 2022.
[11] Michal Derezinski, Feynman Liang, and Michael Mahoney. "Bayesian experimental design using regularized determinantal point processes". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2020, pp. 1197-3207.
[12] Michal Derezinski and Michael Mahoney. "Distributed estimation of the inverse Hessian by determinantal averaging". In: Advances Neurul Information Processing Systems 32. Ed. by H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett. Curran Associates, Inc., 2019, pp- 11401-11411.
[13] Mike Gartrell,
Brunel, Elvis Dohmatob, and Syrine Krichene. "Learning nonsymmetric determinantal point processes". In: Advances in Neural Information Processing Systems 32 (2019).
[14] Mike Gartrell, Insu Han, Elvis Dohmatob, Jennifer Gillenwater, and
Brunel. "Scalable learning and MAP inference for nonsymmetric determinantal point processes". In:
arXiv preprint arXiv:2006. 09862 (2020).
[15] Guillaume Gautier, Guillermo Polito, Rémi Bardenet, and Michal Valko. "DPPy: DPP Sam- pling with Python". In: Journal of Machine Learning Research 20.180 (2019), pp. 1-7. URL: org/ pwppps/pppsse/eee stweers////111 101//191199 .tmml.
[16] Subhroshekhar Ghosh and Philippe Rigollet. "Gaussian determinantal processes: A new model for directionality in data". In: Proceedings of the National Academy of Sciences 117.24 (2020), pp. 13207-13213.
[17] Insu Han, Mike Gartrell, Elvis Dohmatob, and Amin Karbasi. "Scalable MCMC sampling for nonsymmetric determinantal point processes". In: International Conference on Machine Learning. PMLR. 2022, pp. 8213-8229.
[18] J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág. "Determinantal Processes and Independence". In: Probability Surveys 3 (2006). URL: https: //ttps://oo... org/10..//.. 1214% 2F BF154957806000000077
[19] Lingxiao Huang, Jian Li, and Xuan Wu. "On Optimal Coreset Construction for Euclidean (k,z)- Clustering" In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC 2024. Vancouver, BC, Canada: Association for Computing Machinery, 2024, pp. 1594- 1604. ISBN: 9798400703836,.
DOI: 10. 1141/1111111 www.66611.....22 3649707. URL:: https::/ddo.o org/
10. 11451 /2145/3618200 /w11166..66416677....
[20] Kurt Johansson and Gaultier Lambert. "Gaussian and non Gaussaan fluctuations for meso- scopic linear statistics in determinantal processes". In: The Annals of Probability 46.3 (2018), pp. 1201-1278. DOI: 10. / AOP1178. URL: https: / /oi. org/ 10. 1 17- AOP1178.
[21] Alex Kulesza and Ben Taskar. "Determinantal Point Processes for Machine Learning". In: Foundations and Trends@ in Machine Learning 5.2-3 (2012), pp. 123-286. ISSN: 1935-8237. URL: http: //tt:://xxx doi. org/ hrgg/00. 10. 1 [22] Michael Langberg and Leonard J. Schulman. "Universal epsilon-approoximato for integrals". In: Proceedings of the 2010 Annual ACM- Symposium on Discrete Algorithmss (SODA). 2010, pp. 598 607. DOI:
DOI: 10. /
50. eprint: https: //tppbepp..////////// siam. org/doi h//doi//pft pdf 10. 1137/1 /tt.////111911119999997 77811199777771.... 50. URL: atttps://epubae .albbbssiiiae siam. org/doi/ abs/10. 1t5/100.11//119811111177777
[23] Frédéric Lavancier, Jesper Møller, and Ege Rubak. "Determinantal Point Process Models and Statistical Inference". In: Journal of the Royal Statistical Society Series B: Statistical Methodology 77.4 (Dec. 2014), pp. 853-877. ISSN: 1467-9868. DOI: 10. www.l/11issbb... 12096.
URL: attp://dxx doi. org/10. /0/ 111.../................. 12096.
[24] Odile Macchi. "Processus ponctuels et coincidences. Contributions à l'étude théorique des processus ponctuels, avec applications à l'optique statistique et aux communications optiques". PhD thesis. Université Paris-Sud 1972.

---

[25] Odile Macchi. "The Coincidence Approach to Stochastic Point Processes", In: Advances in Applied Probability 7.1 (1975), pp. 83-122. ISSN: 00018678. URL: http: /www jstor
org/stables 1425555 (visited on 05/22/2024).
[26] Erich Novak. Deterministic and Stochastic Error Bounds in Numerical Analysis. Vol. 1349. Lecture Notes in Mathematics. Berlin, Heidelberg: Springer, 1988. ISBN: 978-3-540-50368.
URL: http:/ /tte//11 /tink.ink.... http://nnnn..iiiiiii.ee swr.iggrrnn www.coomooooomm 10mm//0.... 1007 10w.:0000/BBBB BBD007979. [27] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion,
DOL: 1 wtw.1007/BBb00790
Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. "Scikit-learn: Machine Learning in Python". In: Journal of Machine Learning Research 12 (2011) I), pp. 1825-2833
[28] Robin Pemantle and Yuval Peres. "Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Mcasures". In: Combinatorics Probability and Computing 23 (Aug. 2011). DOI: 10. 2...1117/S0066. 00177/009633883300033333
[29] A. Soshnikov. "Determinantal random point fields". In: Russian Mathematical Surveys 55 (2000), pp. 923-975.
[30] Nicolas Tremblay. Simon Barthelmé, and Pierre-Olivier Amblard. "Determinantal point pro-
cesses for coresets", In: Journal of Machine Learning Research 20.168 (2019), pp. 1-70.
12

---

A Appendix supplemental material
A.1 Proof of Theorem
We present here the proof for the general setting, i... when X' is a Polish space and S is DPP with a Hermitian kernel K w.r.t background measure J.. By abuse of notation, will also denote by K the integral operator
[(a) / ((c,9)S())d(())
K (2, (1)
We denote by Cx 2 the cumulants of A(p), i..
C2(yp)
log [E(e ((P))
Σ
th,
for t near 0.
k!
A21
Note that (1p) B[A(F)], C2(p) Var [A())]. In general, we have the formula (see Johansson and Lambert, 2018)
(-1)ott
k!
Ck((p)
Σ
Trip K. &
9
ki!
kigl
where $ pt) - (2, (b) the operator f(x) + ((x)
By the Macchi-Soshnikov theorem (Macchi, 1972; Soshnikov, 2000), 0 3 K 3 I, and we can write
C2((p) Tr KYłK] Tr K)ыvK]= ||v K K HS*
where || || denotes the Hilbert-Schmidt norm of an operator.
Lemma 1. For k 2 we have
lIvT - KΦ K S k|ls/| KOv K|Iss,
where |1 == sup (f(z)).
Proof. One has
IIVI K V
(I K)T V
Tr/O0(I - -K) K]
Tr/O2K/]] Tr| KTt
/ ((t))*((zzz)ddlll
/ʃ ((o)* ((ux)))))d
/ (())22 (K(x,)) (K(x)))))) - /
- K (x,,)) x) du(x)
2 ///(vo/ (p(a)*
1 - ((u)
Since 0 = K - I, we have
12 = K, which implies K(x,1) 2 K(x, v) KW =)du(y) for p-a.e.
r. Thus,
/ p(x)22 K ((x,2) - K K( du(())
11 / p(x)2 (()))(((())) ((( K(.
( vdd(l) du(x).
On the other hand, by the symmetry of K, we have x, E X. Note that
[K(z 0 for all
k-1
1p(x)* ((t))1=1((())) ((v)
Σ
((())(()))-11)
1 (p()) ((v))-
1=0
Combining all ingredients, we deduce that |IVT K as desired.
/
<11111120 VT K j
13

---

Lemma 2. For k 2 3, we have
Cx((p)
1
**
3//2
(pll0)(((())
V2T
Proof. We recall the formula (7), observe that
1))
Σ
k1!. hgg 0.
Then one can write
1)9-1
k!
C2((p)
Triaph KooiiK... K... ".. -Tr(0*
ky!... lig!
(-1)9-1
k!
(Tr(phiK K. K... K] Tr((*(])
ky!... Rig!
=
For any k1, .i....,
.......kg kig such that 1 +... + k ki we observe that
(T( ki K xh " -- t
K| Tr(
a K K]]
Tr(ph/ K... K
K k) K]]
Tr(VK K. k V K K kg VI - K KVI K K
II K 4 K K K
v I1 VI K K K HS
IVK K 4² h K op
K HSS || K + %
|HS
1 W &K K... t 2 K
llop
k 2 K its
here we used Lemma the fact that 3 K 1 I llll l| and the || llop norm is submultipliaatiee Since kj & k for all 1 و 9. using telescoping argument gives
|Tr K
thx [K Tr(** K]1 s y 2
Hence
[Cx(p)) < Σ
k2 11 CZ(p)) kyg
k1
A Ap 21
th,
=k
Now observe that for 2 3
c v k
Σ
Σ
hng
Thus,
[x((p)]
1
v 2
Combining all ingredients above, one can show that.
Lemma 3. For [t] < 1/(3||pll)o)) we have
log Ele)) -I[AA()) < A Var [A(p)),
where A 0 is universal constant.
14

---

Proof. For [t] -
1
we have
CR((p)
log
[[c(A(())
th
k!
12
Ca((p)
|t/
k!
2
I C2(p))
(
+
Σ
1
e"
3/2 (1|1
2
V2
k23
s (1(C2(()
3/2 (e/3)
2
k23
A1² Var [A(+)),
where A > 0 is some universal constant.
We can finish the proof of Theorem as follows.
Proof of Theorem 1. Let 0. We have
log P(A(p) E[A(p)] 2)
s inf log E(c(ko] -EE[A())] - te)
$ inf 8
- te + 12 Aar (A(1))
where the infimum taken on (0, (3,1/(3||)ll=)))
24 Var[A(e] choosing
For Se S
to 2A Var [A(t)]
3/
gives
log P(A(p)) E[A(p)] 28) 4A Var A())
as desired.
A.2
Proof of Theorem 2
Denote by the diagonal matrix Diag(p) E Raxx, For each & E R, we define
tk
G = I exp(t() = I-epp(t)
k!
Am
By the Campbell formula, we have E[c))())] del[I enough such that ||G,Kloop < 1, one can expand
G,K), E R. By choosing / 2 0 small
log det/tI - G.K] =
Observe that || |G < cl - 15 2/t|||y||bo for all |t| < 1l33)))) From now on, we will consider 2 such that
0 +|lppl < 3'
where M : max( K| Kllop. 1). This choice for t will particularly imply that ||,,K|lop S 2/3.
15

---

For h = 1, we have
80 1 Σ
Tr TK
p!
I (E)(()]] + 82
Σ t
Tr|p²K] +
|r
K
2
p!
P23
8 Tr|02<] Σ
8
s [B[A(T]]+ +
44
11
K|
2
p!
p23
1 Tr|
s [B[A(})]
1111
K|
2
For k = 2, we have
t
Σ
Tr TTOK"K"K
2
=
2
plg!
p.
t²
Tr[oK*k]
1
Σ
T+
2
plg!
p4923
8
TrooKpk]
+
1
Σ
t
2
||
K op
K
2
8 Tr + + 1
K K
Klopp.
2
For 2 3, we observe that
(
k-3
K |
K|| <
(211lppl>x)
111 |K]..
3
Thus
14
K
K
Combining all ingredients, we deduce that
12
log M[]) < [E[A(p)] + Var [A(p)] + 1111 |K||| (1 + ||||| + 88/KK
2
12
[B({())] + Var [A(p)] + 10 2
2
Let > We have
log - E(A())) 26) I inf (lo E(c [E[A((p) -(E(A)))) - tt)
!
t²
inf
te + 2
Var [A(p)] +t + 1011p111 [KI.M²
where the infimum taken on E (0, (3
Var[A[p]]]
For 0 < S
|| Mr, we choose
40]|yp
Var [A(p)]
2M
K
1
to Var [A(p)]
20
40 1 K
M
40
|
K
M
3 3llspllooM M
This choice yields
log(P(A(pp) - [[A())]2=)
+ S
18 ||
2 2ar [A(p)]
16

---

Note that
c²
10 |KI1. 1
10 | || 1 v
Var [A())]
Var [A())]
This implies
E²
log [
26)
4 4ar [A(
as desired.
A.3
Proof of Theorem 3
Proof of Theorem 3. By a scaling argument, it suffices to prove for the case wi =... up = 1. We
have
(() []](+)]|l 26) = I A(p:)) - B[A(P:]] 2²²)
Var [A(p.)]
(A(p)) - E[A(PN]] 2 2
=
1=1
Var [A(ri)]
P ((A(P)) E[A(A)] 2
|V(()]1
each < i S p. applying Theorem gives
((AA(p))-[[((.))) /Var [A(p:)]
E² <<A[V[()
50 2A 2A
Var [A(12).
2exp
[V(+)]12
3/ 10
The theorem follows.
A.4 Proof of Theorem 4
Using (A.4), we deduce that Ls()) L(f)
-1 [s(s) - I(OI. VSEF.
This implies
P
Ls(S)
22 20) SP <P(3S EF: (1,s(0) - T(f)I 2 cz). L(f) - 1
Thus, it suffices to bound the RHS. For each / E F, let V > Var - [.s( we apply Theorem for the linear statistic Ls()) = A(f/K) to obtain
TP ( Ls() - TLSI 2 ce) S 2exp (
G282
2AnV
5
4AV
3ell [||]
Using K(x,x) 2 pm//n, we deduce that the above inequality holds for any 0 S S
2ApmV 3e
Proof of Theorem 4: Assuming (A.1). We let Faym == (Af : | S 1 E F), and let B be the convex hull of Fsym- Since B is symmetric convex body in F. there exists norm ||>= in F such that is the unit ball (F, ||=))
Define
C()) == n
I EF
then it is clear that L(f) is linear in f. Moreover, for any f.g E F, one has
[C() C(g) |C( g)l = II allt < || { g|lx )
1-9 9
$ ||f
glls sup [(h)]- heB
17

---

For each o > 0, let B3 be a ô-net for (B, || ||=). By definition of a ô-net, for any f E B, there exists an fo B3 such that If foll= v 6. Thus, for every f B
[C()) & (c())) + [C()) - [(fo)] - [((6) + à sup |c(h)] - sup + å sup [ch)).
[((g]]
hEB
gEB;
hEB
This implies yu |c(f) - 1 sup sep, SEB, [(f],, v0 < 8 < 1. In particular, choosing å 1/2 gives
sup fEB
[()) S 2 sup
((())
/2B
Therefore
P( sup [c()) 2 <z) <P(2 fEB
1 L(f)) cf/2) |c()) 2 = P(3f B1/2: n
sup
feB1/2
Let (B, || 1/2) be the 1/2-covering number of B, then
(P(2f E B - [s(f) L(f) cz) s SN |l ||x, 1/2) 22 26181
for any
1 L
4ApmV V
sup Var fEB
0SE5
n
3esup JEB loc.
Note that for finite dimensional normed vector space, for one has
3
dim
N(B, 11r, -
8
This implies
P(3f E B: 1
- - Ls(f- 2 ez)
E²E²
S 2exp
6D
(8)
16AV
Since J C B, is clear that
P(3SEF: (Ts(s) -(f] 2 nes) S (P E (::( I(f) 2 moe).
On the other hand, for each f E B, there exist 0 S t < 1, s 1, E F,i = 1,2 such that fiif + (1 2222f2. Therefore
Var [Ls(f)]
Var + t)
Var (Ls(
+ Ls(
t)d2f2))
War ILs ( () (Ls(f2))
Var [L
sup
gEF
Moreover,
|f sup f(x)) < t sup [x(( + (1 - t) sup ZE
[f((z) N sup |lg|l
xEX
z
gef
Thus,
sup Var [Ts(())] sup Var [Ts(S)] JEB
sup feB
sup f FEF
(10)
feF
From (8), (9), (10), the theorem follows.
Proof of Theorem 4: Assuming (A.2), (A.3). We define [()) = ( - T(JO)),, 0 E e.. Then
P(aEEF: 1 n Ls(s) L(f) 2 cs) P(30E [C()] 2 cs) PPssup [C(0) 2 cE).
ace
Using (A.3), we have (Lfo) L(fer) S nel 0'll and
[Ls(f)) Ls(ser) s 810 0'1l Σ
< 8110 0' 'm -((). (11)
K K(x,
18

---

This implies [()) - [()) - 0|0 - 6 a.s., for some constant C' depending on B, l. Let I' be -net for then
sup
sup d'el
|C((0)
Thus
P(sup [2()] 2 cε) - (sup [((0)] 2 cE/2)
og
note that O(= This completes proof.
Remark 6.3. Without the assumption [S] S B m. a.s.,
continue from (11) as follows. the eigenvalues of K, is known that [S] =a X1 + Xas where
Denote by X1 .... X; ~ (er(A;) are independent. Let B > O, then using a multiplicative Chernoff bound for the sum of independent Bernoulli variables gives
PP(() > (B 1)m) = x, (B+ S exp (-
B
B m
By choosing B large, this event will have small probability. Meanwhile, on the event {|S] s (B + 1)m3, we can use exactly the same argument as in the proof above.
A.5 Proof of Theorem
Proof of Theorem 5. It suffices to show for the case wh applying Theorem and union bound argument, have
wp 1. For each f E F, by
P C (s(() l(F)l 2 2) 2pexp
c²eZ
2ApmV
4AV
3e max; 1
Using the same argument as in the proof of Theorem 4 under assumption (A.I) gives the result.
A.6 Proof of Theorem
Proof of Theorem 6. We remark that Var [n-1 O( (1+1/dd) uniformly for f E F, w.h.p. in the data set X. Hence, Theorem 6 is a direct application of Theorem 4 with V Cm (141/d) for some constant > 0. As we discussed in the Remark 4.1, the range for s is O(m 1/d). Thus, it suffices to check the conditions on K. Since K is projection of rank m, Moreover, we have nk(r, x)) = K(r,v), which is typically of order m. where we used an uniform CLT result and an asymptotic for multivariate OPE kernels (see Bardenet, Ghosh, et al., 2021 for more details).
|S|
19

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We claim theoretical results, which are established as theorems in the main
text.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations in Section 5.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We give our assumptions and results in Section 3.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We give experimental details in Section 4.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will release code to reproduce the experimental section in public GitHub repository upon acceptance. We stress our contributions are the theoretical results the main paper; the code is there only to support our theoretical claims.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We give details in Section 4.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Our metric a quantile of worst-case error; there is no standard error bar.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Our experiments are small-scale and were performed on personal computer; mention this in Section 4.
20

---

9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics pentpa://neuriie http::pp....ppppipi/hccccccccced
Answer: [Yes]
Justification: It is theoretical paper, and we cannot see any potential harmful consequence.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: It a theoretical paper, so socictal impact is a long way downstream, A positive impact
see in the study of coresets is the possibility of saving energy when training large models.
Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risk.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: properly cite the Python libraries use.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
21


Reviews:
[{"review_id": "OXKVLEuF7x", "reviewer": "Reviewer_329X", "summary": "This work improves on the concentration bounds on DPP for coresets by explicitly relying on the fact that loss based coresets are linear functionals. To this end, this paper also add the coreset results for Non-symmetric kernels, (including additive coresets) expanding on the previous results on DPP Coresets (which were solely in the hermitian regime). Paper compares against other sampling based theoretical coresets (including DPPs) for approximation errors.", "questions": "Refer to the weakness.", "limitations": "Refer to the weakness.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like the fact that this paper extended the DPP bounds to Non-symmetric kernels. Overall the paper is not difficult to parse through, despite many theoretical statements.", "weaknesses": "I cannot exactly pin down the weakness in this work since I'm not expert in this area, however, I'd like to point out a few things that can help to understand this work better. \n\n- When going from lipschitz (Peres and Pemantle) to linear functional concentration, what exactly changes which leads to the better bounds? \n\n- Can the authors have a side by side comparision of the sample complexity for the previous existing works (DPP for coresets paper), in a tablular form to understand the contributions of this work better?\n\n- What is an intuitive explanation of the fact that the range of $\\epsilon$ got tighter in non-symmetric case? \n\n- Can there be chaining related improvements to further improve the provided bounds, as done in Bhatt and Bilmes 2021? \n\n- Is it possible to provide some experimental results with different choice of kernels including non-symmetric? \n\n- Writing Suggestion: It might improve readability of $\\|\\varphi\\|_{\\infty}$ is replaced by some constant bounding the loss function. \n\nReferences:\n- Tighter m-DPP Coreset Sample Complexity Bounds, Bhatt and Bilmes 2021. Subset ML at ICML'21", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive review! Here are answers to your comments.\n\n> When going from Lipschitz (Peres and Pemantle) to linear functional concentration, what exactly changes which leads to the better bounds?\n\nThe Pemantle-Peres results aim to address general Lipschitz functions in several variables. Roughly speaking, one has to pay for the generality by having a much cruder result. A key point we make is that, in many practical situations, functionals of DPPs that are of interest have a linear structure. Therefore it is natural to develop a theory of concentration of linear functionals of a DPP, as we do in this paper. Unlike the general Lipschitz case, the Laplace transform of linear statistics of DPPs is explicitly given by a Fredholm determinant. This is the starting point of the derivation of a tighter concentration result. Another advantage is that careful work around this Fredholm determinant allows keeping in the bound the variance of the linear statistic under scrutiny, like in the classical Bernstein inequality. In that view, the result of Pemantle and Peres is more similar to the Hoeffding inequality. \n\n> Can the authors have a side by side comparison of the sample complexity for the previous existing works (DPP for coresets paper), in a tabular form to understand the contributions of this work better?\n\nWe will mention this early on in the introduction when we list our contributions. Right now, the sample complexity is indeed a bit hidden in our Remark 4.1. Essentially, the best (multiplicative) $\\epsilon$-coresets built with independent samples are of size $m=\\mathcal{O}(\\epsilon^{-2})$. Using the general result of Pemantle and Peres, Tremblay et al. (the “DPPs for coresets” paper) provided a bound with the same dependence in $\\epsilon$ for DPPs. On our side, we show that we can actually take $m=\\mathcal{O}(\\epsilon^{-2/(1+\\delta)})$, where $\\delta$ depends on the variance of the subsampled loss under the considered DPP. In particular, for the discretized multivariate OPE introduced in Example 5, any $\\delta \\in(0,1/d)$ works, where data are assumed to live in $\\mathbb{R}^d$ (in fact, in practical terms we recommend applying the algorithm there on dimensionally reduced data, and the $d$ here can be taken to be this reduced dimension).  This shows that if the DPP is suitably chosen, the dependence of the coreset size in $\\epsilon$ is provably better than for independent coresets.\n\nA table summarizing our sample complexity could look like this.\n\n| Independent sampling | Generic DPPs | Discretized multivariate OPE |\n|---|---|---|\n| $\\mathcal{O}(\\epsilon^{-2})$ | $\\mathcal{O}(\\epsilon^{-2/(1+\\delta)})$ for $\\delta \\geq 0$ based on the DPP | $\\mathcal{O}(\\epsilon^{-2/(1+1/d-\\eta)})$ for any $\\eta>0$. |\n\n\n> What is an intuitive explanation of the fact that the range of $\\epsilon$ got tighter in the non-symmetric case?\n\nIt is not so clear to us that the range gets tighter. The nuclear norm of the kernel is roughly $m$, so that everything depends again on the variance of the linear statistic. Much less is known on the latter for non-symmetric kernels. \n\nIn fact, although the bounds look similar in the symmetric and non-symmetric cases, the non-symmetric case forced us to change our proof technique, leading to a different range for $\\epsilon$. In general, for symmetric kernels, an elaborate spectral theory is available and generally finer analysis (e.g., involving algebraic cancellations) is possible. A case in point would be the Christoffel-Darboux theory that allows for the improved bounds in Example 5. \n\n> Can there be chaining related improvements to further improve the provided bounds, as done in Bhatt and Bilmes 2021? \n\nThanks for bringing this interesting paper to our attention. There could be a small improvement in a smart chaining argument, but it is very unlikely that we can substantially improve the rate in the dependence of $m$ in $\\epsilon$. In [Bhatt and Bilmes 2021], they indeed gain a log term that was implicitly there in [Tremblay et al. 2019]; this definitely makes for a cleaner result, but does not substantially change the rate.\n\n> Is it possible to provide some experimental results with different choice of kernels including non-symmetric?\n\nIn our experiments, we do explore several choices of kernels. These kernels are all symmetric in nature. While our concentration results are generally applicable, our experimental investigations in the paper focus on the problem of coreset construction. The setting of non-symmetric kernels is not very natural to the problem of sampling coresets. Generally speaking, non-symmetric kernels are much less tractable, analytically and algorithmically. Therefore, in the problem of DPP-based coreset construction, where the kernel is our choice, one nearly always goes for a symmetric kernel to produce the desired repulsive effects among sample points and the attendant variance reduction. In particular, the fast decay of the variance of linear statistics is key in deriving *small* coresets from our concentration inequality. To our knowledge, there is no known non-symmetric DPP with a fast-decaying variance of linear statistics, and we thus do not have a clear non-symmetric candidate DPP for comparing coresets. \n\nA key application of non-symmetric kernels is in situations where it is desirable that the mutual repulsion between points is violated at certain locations; cf [Gartrell et al. 2019](https://arxiv.org/abs/1905.12962), or  [Poulson 2019](https://arxiv.org/abs/1905.00165) and references therein. In such problems, it is of natural interest to obtain confidence bands for the outputs of the non-symmetric DPP based methods, and our concentration results for non-symmetric DPPs are the first ones to provide such guarantees. The experimental analysis related to our concentration results for the non-symmetric case are thus better suited to a different work which focuses on such relevant applications of non-symmetric kernels.", "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": "", "extra_scores": {}}, {"review_id": "G35GylZQXB", "reviewer": "Reviewer_koaH", "summary": "This paper presents a study on the use of Determinantal Point Processes (DPPs) for constructing coresets in machine learning tasks. DPPs are random configurations of points with negative dependence, making them suitable for subsampling tasks like minibatch selection or coreset construction. Therefore, it is natural to ask can DPP-based coresets have smaller size than the independent-sampling-based coresets. The paper answers the question, demonstrating that DPP-based method outperforms.\n\nTo achieve this, the author provide a new understanding of coreset loss as a linear statistic of the random point set. Then they connect the coreset construction to the concentration inequalities of the linear statistic and show that a suitable DPP yields a coreset of size $o(\\varepsilon^{-2})$.", "questions": "- What is the time complexity of DPP-based coreset construction?\n- The paper proposes some assumptions on the DPPs. Are these assumptions fair compared to previous methods?", "limitations": "none", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- New concentration inequalities for linear statistics of DPPs are presented, which are applicable to general non-projection and non-symmetric kernels.\n- The DPPs-based coresets have a smaller theoretical size than the independent-sampling-based coresets.\n- The paper introduces the study of coresets for vector-valued objective functions, a topic that holds independent interest.", "weaknesses": "see the questions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive review. Here are answers to your questions.\n\n> What is the time complexity of DPP-based coreset construction?\n\nIn general, sampling a DPP of cardinality $m$ among a ground set of size $n$ is $O(nm^2)$ provided the kernel matrix has been diagonalized beforehand. Depending on how the kernel is specified, the diagonalization preprocessing can add up to $O(n^3)$ operations. In practice, randomization and low-rank approximation techniques can be used to take down these costs for large-scale applications; see e.g. [Kulesza and Taskar, FTML 2012](https://www.nowpublishers.com/article/Details/MAL-044). \n\nGiven that coreset guarantees are uniform bounds for entire function classes, the same coreset once sampled can give accurate approximation for a range of functions of interest for a particular application, and thus DPP sampling is essentially a one-time preprocessing overhead.\n\nOn a related note, leveraging the fact that the coreset-based approximant is a linear statistic, the sampling problem may be reduced to that of sampling a real-valued random variable via its Laplace transform, cf. [Bardenet et al., Arxiv](https://arxiv.org/abs/2007.04287). \n\nIt may be noted that in many modern coreset applications, the functional evaluation is often computationally very expensive, and the cost of coreset sampling can be secondary to that. A typical example would be the computation of the output of a large-scale neural network, or its training dynamics where the gradient is computed via a backpropagation through the network. Another instance is that of large-scale conditional random field models. In such situations, it is imperative to reduce the number of function evaluations, and smaller coresets are very helpful in achieving that objective.\n\n> The paper proposes some assumptions on the DPPs. Are these assumptions fair compared to previous methods?\n\nOur concentration results are very generic, and we even consider DPPs with non-symmetric kernels. In the application to coreset construction, we make very minimal assumptions on the DPP that is used. In fact, we only bound from below the marginal probability of seeing any item of the ground set in the coreset; see Remark 4.2. This seems reasonable to us: since our goal is to estimate a mean over the $n$ data points, there should be a chance, even minute, of sampling each data point. \n\nMost of our assumptions are on the complexity of the space of queries $\\mathcal F$. However, as demonstrated in our paper, these assumptions cover most of the learning tasks for which coresets have been studied: $k$-means, linear regression, etc, and also some important spaces of test functions of other fields (e.g. band-limited functions in signal processing).", "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": "", "extra_scores": {}}, {"review_id": "SyGOleoAH6", "reviewer": "Reviewer_5TaP", "summary": "The paper proves concentration inequalities for linear statistics of samples form a DPP. In particular, a guarantee for the coreset sampling problem is shown: If the coreset is sampled from a DPP then the loss over the coreset approaches the loss over the full dataset faster then when the coreset is sampled uniformly. \nThe superiority of DPP samples over uniform samples is demonstrated in a k-means application on toy data and MNIST data.", "questions": "Remark 3.3 mentioned that the assumption on a set's cardinality holds for most kernels of interest. Are there more examples other than the projection kernels? I assume it holds for the Gaussian kernel as it is used in the experiments? Are there examples of common kernels where the assumption does not hold?", "limitations": "yes, there is a dedicated limitations sections that I perceive as accurate", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* proper theoretical justification of results that have been empirically observed in previous work \n* The paper is well written, e.g., it contains a compact introduction to coresets that one can easily follow even if unfamiliar with coresets.\n* The assumptions of the theoretical results are stated clearly and are discussed.\n* informative and honest discussion section about limitations and interesting future work directions\n* The results generalize beyond the coreset problem and could potentially be interesting for other DPP application areas, too.\n* The results also apply to non-symmetric kernels.", "weaknesses": "* The markers in Figure 1 (a) and 2 (a) are different sizes, but I can't find information on what a marker's size encodes. I would appreciate a clarification. \n* The comparison to the related work \"Tremblay et al 2019\" (see line 52-55) could be a little bit more detailed. It's just mentioned that this other paper also contains theoretical results for the same/ a similar setting, but not what their nature is and how they differ from the results in the present paper (I don't doubt they do, but I think 1-2 sentences more on this would be useful).  \n* The \"stratified\" baseline seems much stronger than the uniform baseline and the DPP sampler—at least, where it is straightforward to apply. Other heuristical sampling methods that encode repulsiveness between data items without being DPPs might also be preferable in large-scale machine learning applications, including coreset problems. The practical relevance might be limited, but I don't consider this a major issue as the paper is of a theoretical nature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive review. Here are answers to some of your comments/questions.\n\n> The markers in Figure 1 (a) and 2 (a) are different sizes, but I can't find information on what a marker's size encodes. I would appreciate a clarification.\n\nThe size of a marker placed at $x$ is proportional to the corresponding weight $1/K(x,x)$ in the estimator of the average loss. Equivalently, the marker size is inversely proportional to the marginal probability of $x$ being included in the DPP sample. We will clarify this in the final version of the paper.\n\n> The comparison to the related work \"Tremblay et al 2019\" (see line 52-55) could be a little bit more detailed. [...] I think 1-2 sentences more on this would be useful).\n\nWe will add a brief discussion to clarify the differences. The most important thing for our paper is that Tremblay et al 2019 only prove that DPP-based coresets of accuracy $\\epsilon$ should have cardinality $\\mathcal{O}(\\epsilon^{-2})$, which is the same rate as independent samples. This falls short of demonstrating that repulsiveness of DPPs leads to an improvement in the rate of convergence in sampling tasks, as believed from physical heuristics. This provides a natural   Besides our generic concentration inequalities, our key contribution is that we show that appropriately chosen DPPs can lead to significantly smaller coresets, i.e. of cardinality $\\mathcal{O}(\\epsilon^{-\\gamma})$ with $\\gamma > 2$ as $\\epsilon$ goes to zero.\nTremblay et al. (2019) have a number of other interesting results in their paper, for instance that for any DPP with an Hermitian kernel that has for diagonal the sensitivity, the cardinality of the DPP coreset is smaller than i.i.d. sampling proportionally to the sensitivity. This is another hint that repulsiveness helps, but it is not a direct proof of the heuristic that smaller DPP coresets work. A key contribution of ours is that we quantify how small DPP coresets can be, and we show that they can break the $\\mathcal{O}(\\epsilon^{-2})$ barrier of independent samples.\n\n> The \"stratified\" baseline seems much stronger than the uniform baseline and the DPP sampler—at least, where it is straightforward to apply. Other heuristical sampling methods that encode repulsiveness between data items without being DPPs might also be preferable in large-scale machine learning applications, including coreset problems. The practical relevance might be limited, but I don't consider this a major issue as the paper is of a theoretical nature.\n\nActually, it is not hard to show that stratified sampling as we implement is a DPP, although it is rarely introduced that way. But we agree that there are plenty of useful repulsive methods and heuristics that are not DPPs. However, the stochastic dependencies in other repulsive or negatively dependent heuristics are often too complicated to understand from a theoretical point of view. As such, they come with very little mathematical guarantees. We see DPPs as a tractable tool to mathematically quantify the power of negative dependence in sampling applications. \n\n> Remark 3.3 mentioned that the assumption on a set's cardinality holds for most kernels of interest. Are there more examples other than the projection kernels? I assume it holds for the Gaussian kernel as it is used in the experiments? Are there examples of common kernels where the assumption does not hold?\n\nThere is no Remark 3.3, but you likely mean Remark 4.3 or 6.3, which both discuss cardinality. The assumption $\\vert\\mathcal{S}\\vert \\leq Bm$ a.s. is equivalent to the kernel having at most $Bm$ nonzero eigenvalues; this includes DPPs with projection as well as many non-projection kernels. Note that the assumption is here to simplify the proof for the reader who focuses on projection kernels, but the assumption is easy to avoid for a generic Hermitian kernel, thanks to a control on the tail $\\mathbb{P}(\\vert \\mathcal{S}\\vert\\geq (B+1)m)$ and our assumption that the marginal probability of seeing any item is lower bounded, as mentioned in Remarks 4.3 and 6.3. The case of a DPP with Gaussian kernel and Gaussian reference measure, where the number of nonzero eigenvalues is infinite, is covered by that extension.\n\nFor the Gaussian kernel in the experiments, the situation is slightly different. We indeed include $m$-DPPs with Gaussian kernels in our experiments, but an $m$-DPP is not a DPP. Strictly speaking, our proof thus does not cover $m$-DPPs, and we rather include $m$-DPPs in our experiments for comparison to previous work. Note however that $m$-DPPs are conditional DPPs (conditioned on the number of points), and we could easily extend the proof of our concentration inequalities by a simple conditioning argument, if needed for the sake of exhaustiveness.", "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": "", "extra_scores": {}}, {"review_id": "EOLG3AVL2E", "reviewer": "Reviewer_818N", "summary": "This paper studies corsets and aims to construct them using determinantal point processes (DPPs). The authors show that DPPs can provably outperform independently drawn corsets due to linear statistics and better concentration of DPPs.", "questions": "By reading the paper, I am still confused about when DPPs outperform importance sampling. Could you give some concrete examples, e.g., under what optimization problem and what dataset, what is the coreset size by DPP v.s. by importance sampling?\n\n--\nThanks for the response. I increase my score to 5.", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The topic of coreset problems is essential in machine learning.\n- The paper is technically solid, providing interesting theoretical results.\n- Empirical results confirm the power of DPPs in independent data.", "weaknesses": "- The writing can be improved. There are many theorems and remarks in the paper, which makes it confused about the main contribution. The theorems are technical but without explanations. What are the conclusions and applications of these theorems?\n\n- Lack of coreset literature. For instance, Cohen-Addad, V., Larsen, K.G., Saulpic, D., Schwiegelshohn, C., & Sheikh-Omar, O.A. (2022). Improved Coresets for Euclidean $k$-Means; 2) Huang, Lingxiao, Jian Li and Xuan Wu. “On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review. Here are answers to your comments/questions that we hope will clarify things.\n\n> The writing can be improved. There are many theorems and remarks in the paper, which makes it confused about the main contribution. The theorems are technical but without explanations. What are the conclusions and applications of these theorems?\n\nWe are sorry about the confusion. Since we otherwise got good marks for presentation, we are confident that we can make some limited adjustments to further clarify the role of each theorem and remark. In particular, following a suggestion of Reviewer 329X, we will explicitly include in the introduction our claim on the sample complexity of coresets with DPPs.\n\nIn a nutshell, coresets built using independent samples require a cardinality in $\\mathcal{O}(\\epsilon^{-2})$ for a uniform multiplicative error of $\\epsilon$. DPPs always come with at worst the same dependence, while *specific* DPPs come with a strictly better dependence of the cardinality to $\\epsilon$. The meaning of *specific* is that the chosen DPP should come with a fast-decaying variance of linear statistics, as is the case for the DPP we introduce in Example 5. See our Remarks 4.1 and 6.1, and our answer to Reviewer 329X for more details on the impact of variance reduction on the size of the coreset.\n\n> Lack of coreset literature. For instance, Cohen-Addad, V., Larsen, K.G., Saulpic, D., Schwiegelshohn, C., & Sheikh-Omar, O.A. (2022). Improved Coresets for Euclidean-Means; 2) Huang, Lingxiao, Jian Li and Xuan Wu. “On Optimal Coreset Construction for Euclidean-Clustering.\n\nWe thank the reviewer for drawing our attention to these interesting references; we will add them to our paper. We note that we see the paper as a DPP paper with a view to the coresets problem, so  this submission is a way for us to connect with the coresets-for-ML community and raise awareness on the potential of DPPs and negative dependence in that context. This explains why we limited ourselves to general references on coresets, and largely refrained from delving into the rich literature on coresets that address specific problems, such as Euclidean clustering. Our point is that a very generic DPP-based coreset construction can improve on the dependence of $m$ in $\\epsilon^{-2}$ in a precise sense. We would be happy if the paper generated discussions on particular coreset settings like $k$-means clustering, for which much theoretical work is available. Comparison to dedicated literature for such applications are a natural direction for follow-up research.\n\n> By reading the paper, I am still confused about when DPPs outperform importance sampling. Could you give some concrete examples, e.g., under what optimization problem and what dataset, what is the coreset size by DPP v.s. by importance sampling?\n\nDPPs outperform importance sampling in the sense that some DPPs, like the discretized multivariate OPE of Example 5, provide randomized $\\epsilon$-coresets with a cardinality $m$ that grows strictly slower as $\\epsilon$ decreases; see Theorems 4 and 6, and in particular Remarks 4.1 and 6.1. Another way to say the same thing is that, under some DPPs, *the approximation error* $\\epsilon$ decreases faster with $m$ than the importance sampling rate $m^{-1/2}$. This is confirmed by our experiments. \n\nThe meaning of *some DPPs* above is that we need DPPs that come with a fast-decaying variance of linear statistics. This has been proved for certain DPPs, such as the discretized multivariate OPE introduced in Example 5. Note that the latter DPP does not use any information on the loss function nor the optimization algorithm used, so that our guarantee is fairly general, at the risk of the constants not being tight. The loss function only enters our guarantees through assumptions (A.1) to (A.4). \n\nConceptually, the reason for better performance of DPPs is that the repulsion between sample points baked into the framework discourages the selection of multiple points with similar properties in the sample. DPP-based diverse samples thus cover more ground in a single sample, and can be shown to be more stable statistically. On the other hand, in importance sampling, two sample points do not “see” each other, and this can lead to oversampling in regions with higher importance scores. In the setting of Example 5, it can be shown that the variance reduction accorded by moving from uniform random sampling to importance sampling can lead to an improvement in the leading constant, whereas using an appropriate DPP can lead to an improvement in the exponent.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their careful reading of the paper, and their detailed comments, to which we have responded point by point below. We would like to take this opportunity to elaborate on the fact that our submission is appropriately viewed in the context of a wider programme of leveraging negative dependence as a toolbox for machine learning. In particular, this enables us to exploit the diversity of samples generated using a DPP to provide more representative and more parsimonious summaries of datasets (or approximations to functions of datasets). While this is motivated by physical heuristics coming from quantum and statistical mechanics, establishing this as a principled learning paradigm with robust and rigorous guarantees has proven to be a much more difficult task, with only a limited number of use-cases to support more extensive experimental evidence. Our work contributes to this overall programme by addressing the problem of sampling coresets.

From this perspective, for our paper, the coresets problem is an important application domain wherein we establish the effectiveness of negative association-based methods (in contrast with, e.g., a paper that is situated deep within the coresets literature). As such, our evaluations and comparison benchmarks are also principally based on literature that has attempted to accomplish this goal (e.g., Tremblay et al. 2019). On a related note, discussion of the nuances of the coresets literature in specific settings (such as clustering or regression) in our paper are somewhat muted, especially in view of the limited space available in a NeurIPS submission. Having established foundational guarantees for DPPs as a coresets generating mechanism in this paper, it would be natural to explore in future works the performance of DPP-based coresets in such specific applications. Such future works would be natural venues where detailed comparisons to established benchmarks in those particular settings can be undertaken. In contrast, the present work focuses on very general, foundational guarantees for an approach based on negative association, and is ideally perceived and evaluated in that framework.

Meta-review: This paper introduces significant new theoretical results showing that coresets sampled using DPPs can asymptotically outperform those sampled independently, and demonstrates the effect in simple empirical settings. The results are based on novel concentration inequalities for linear statistics of DPPs, which could also be of independent interest.

Following the author rebuttal, all reviewers felt that the paper deserves acceptance. The writing is clear (particularly given its technical density), the problem is important, and the results themselves are clean and general (including DPPs with non-symmetric kernels). Please consider the suggestions made by reviewers when preparing the final version of the paper.
Decision: Accept (spotlight)