Small coresets via negative dependence: DPPs, linear statistics, and concentration

Authors: rémi  bardenet
subhroshekhar  ghosh
hugo  simon-onfroy
son  hoang
  tran
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 09:33:40

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.

Main paper: 
 introduction: 
 Let X = {x i | i ∈ 1, n } be a set of n points in a Euclidean space, called the data set. Let F be a set of nonnegative functions on X , called queries. Many classical learning problems, supervised or unsupervised, are formulated as finding a query f * in F that minimizes an additive loss function of the form L(fEQUATIONwhere µ : X → R + is a weight function.Example 1 (k-means). For X ⊂ R d and k ∈ N, the goal of k-means clustering is to find a set C * of k "cluster centers" by minimizing (1) overF = f C : x → min q∈C ∥x -q∥ 2 2 | C ⊂ R d , |C| = k .Here, each query f is indexed by a set of k cluster centers, and the loss (1) is the quantization error.Example 2 (linear regression). When X = {x i := (y i , z i ) | i ∈ 1, n } ⊂ R d+1 , linear regression corresponds to minimizing (1) overF = (y, z) → (a ⊤ y + b -z) 2 | a ∈ R d , b ∈ 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 ≫ 1 makes optimization intractable, one is tempted to reduce the amount of data, using only a tractable number of representative samples. This is 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 ε-coreset is a subset S ⊂ X , possibly with corresponding weights ω(x), x ∈ S, such thatEQUATIONis within ε of L(f ), uniformly in f ∈ F. If the cardinality m of S is significantly smaller than the intractable size n 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 probability, are built by drawing elements independently from the data set X (Bachem et al., 2017, Chapter 3). Because a representative coreset should intuitively be made of diverse data points, negative dependence between the coreset elements has been proposed as an effective possibility to 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 parametrized by an n × n kernel matrix K that enforces diversity, all of this while coming with a polynomial-time exact sampling algorithm. Tremblay et 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 ε-coreset, and their bound is O(ε -2 ). However, it is known that the best ε-coresets built with independent samples are also of cardinality O(ε -2 ). Thus, the crucial question of whether DPP-based coresets can provide a strict improvement remained to be settled; given the computational simplicity of independent schemes, this would be fundamental to justify the deployment of DPP-based methods.In this paper, we settle this question in the affirmative, demonstrating that for carefully chosen kernels, DPP-based coresets provably yield significantly better accuracy guarantees than independent schemes; equivalently, to achieve similar accuracy it suffices to use significantly smaller coresets via DPPs. In particular, we will show that DPP-based coresets actually can achieve cardinality m = O(ε -2/(1+δ) ).The quantity δ depends on the variance of the subsampled loss under the considered DPP, and some DPPs yields δ > 0. A cornerstone of our approach is a 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 a 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 scalarvalued statistics for finite rank ensembles on R. In particular, we are able to address all DPPs that have appeared so far in the ML literature. Specifically, our results are able to handle non-symmetric kernels and vector-valued linear statistics.DPPs with non-symmetric kernels have recently been shown to be of significant interest in machine learning, such as recommendation systems (Gartrell, Brunel, et al., 2019; Gartrell, Han, et 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, et 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 3 contains our contributions. Section 4 provides numerical illustrations. Section 5 contains a discussion on limitations and future work. 
background: 
 We introduce here the two key notions of determinantal point process and coreset, and observe that a coreset guarantee is a uniform control over specific linear statistics of a point process.A point process S on a Polish space X is a random locally finite subset of X . Given a reference measure µ on X (e.g., the Lebesgue measure ifEQUATIONwhere 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 k → R and for all k ∈ N. Such a function K is called a kernel for the DPP S, and µ is called the background measure.When the ground set X is of finite cardinality n, an equivalent but more intuitive way to define DPPs is as follows: a random subset S of X is called a DPP if there exists an n × n-matrix K such thatP(T ⊂ S) = det[K T ], ∀ T ⊂ X, where K T 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) Example 3 (L-ensemble and m-DPP). Let X be a finite set of cardinality n, µ be the counting measure, and L be a positive semi-definite n × n-matrix. The L-ensemble with parameter L is the point process S on X such that, for all T ⊂ X , P(S = T ) ∝ det[L T ], where L T is the square submatrix of L corresponding to the rows and columns indexed by the subset T . It can be shown that S is a DPP on X with kernel K := L(I + L) -1 . In general, the cardinality of S is a random variable. By conditioning on the event {|S| = m}, we obtain the so-called m-DPPs (Kulesza and Taskar, 2012) . Example 4 (Multivariate OPE; Bardenet and Hardy, 2020) . Let X = R d and µ be a measure on R d having all moments finite, let (p k ) k∈N d be the orthonormal sequence resulting from applying the Gram-Schmidt procedure to the monomials x k1 1 . . . x k d d , taken in the graded lexical order. The kernel K Multivariate OPEs were used in (Bardenet and Hardy, 2020) as nodes for numerical integration, leading to a Monte Carlo estimator with mean squared error decaying in m -1-1/d , faster than under 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, et al., 2021) . Let n ∈ N and X = {x 1 , . . . , x n } ⊂ [-1, 1] d . Let q(x)dx be a probability measure on [-1, 1] d . Let K (m) q be the multivariate OPE kernel of rank m with reference measure q(x)dx, as defined in Example 4. Let γ : [-1, 1] d → R + be a function, assumed to be positive on X , and considerK (m) q,γ (x, y) := q(x) γ(x) K (m) q (x, y) q(y) γ(y) , x, y ∈ [-1, 1] d .Consider then the n× n matrix K = K (m)q,γ | X ×X . 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 .Coresets. Let ε > 0 and X be a set of cardinality n. The classical definition of a coreset is multiplicative.EQUATIONwhere L and L S are respectively defined in (1) and ( 2).An immediate and important consequence of ( 2) is that the ratio of the minimum value of L S by that of L is within O(ε) of 1 (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 ω = µ/q in (2). Langberg and Schulman, 2010 showed that a suitable choice of q actually yields the uniform guarantee (2) . It suffices to take for instrumental pdf q(x) ∝ µ(x)s(x), where s upper-bounds the so-called sensitivityEQUATIONFor δ > 0, k ≥ S 2 2ε 2 log 2/δ independent draws are then enough to build an ε-multiplicative coreset, where S = x∈X µ(x)s(x); see (Bachem et al., 2017) [Section 2.3]. The tighter the bound (5), the smaller the size of the coreset. One important limitation is that finding a tight bound is nontrivial.Although not standard, a natural alternative definition of a coreset is that of an additive coreset. Definition 2 (additive coreset). A subset S ⊂ X is an ε-additive coreset ifEQUATIONNote 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 L S is guaranteed to be within ±nε of the minimal value of L: Similarly to a multiplicative coreset, with ε suitably small one should be happy to train one's algorithm only on S.Coreset guarantee and linear statistics. Let S be a point process on a finite X = {x 1 , . . . , x n }.For a test function φ : X → R, we denote by Λ(φ) := x∈S φ(x) the so-called linear statistic of φ. In a coreset problem, for a query f ∈ F, the estimated loss L S (f ) in ( 2) is the linear statistic Λ(ωf ). When S is a DPP with a kernel K on X (w.r.t. the counting measure), we will choose the weight ω(x) = K(x, x) -1 , where for x = x i ∈ X , we define K(x, x) to be K ii . By (3), this choice makes L S (f ) an unbiased estimator for L(f ). Guaranteeing a coreset guarantee such as (6) with high probability thus corresponds to a uniform-in-f concentration inequality for the linear statistic Λ(ωf ). This motivates studying the concentration of linear statistics under a DPP, to which we now turn. 
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(ε -2 ), thus beating independent sampling.Concentration inequalities for linear statistics of DPPs. We start with Hermitian kernels. Theorem 1 (Hermitian kernels). Let S be a DPP on a Polish space X with reference measure µ and Hermitian kernel K. Then for any bounded test function φ : X → R, we haveP(|Λ(φ) -E[Λ(φ)]| ≥ ε) ≤ 2 exp - ε 2 4A Var [Λ(φ)] , ∀0 ≤ ε ≤ 2A Var [Λ(φ)] 3∥φ∥ ∞ ,where A > 0 is a universal constant.Our Theorem 1 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 1 is applicable to all Hermitian kernels on general Polish spaces.In view of recent interest in machine learning on DPPs with non-symmetric kernels, we present here a concentration inequality for such DPPs. We propose a novel approach to control the Laplace transform in the non-symmetric case (which can also be applied to the symmetric setting). As a trade-off, the range for ε becomes a 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 a DPP on a finite set X = {x 1 , . . . , x n } with a non-symmetric kernel K. Then for any bounded test function φ : X → R, we haveP(|Λ(φ)-E[Λ(φ)]| ≥ ε) ≤ 2 exp - ε 2 4 Var [Λ(φ)] , ∀0 ≤ ε ≤ Var [Λ(φ)] 2 40∥φ∥ 3 ∞ • max(1, ∥K∥ 2 op ) • ∥K∥ * ,where ∥ • ∥ op 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 2 to deduce analogous results for non-symmetric kernels.We conclude with a concentration inequality for linear statistics of vector-valued functions. Theorem 3 (Vector-valued statistics). Let S be a DPP on a Polish space X with reference measure µ and Hermitian kernel K. Let Φ = (φ 1 , . . . , φ p ) ⊤ : X → R p be a vector-valued test function, and we denote byΛ(Φ), V(Φ) the vectors (Λ(φ i )) p i=1 and (Var [Λ(φ i )] 1/2 ) p i=1 , respectively. Let ∥x∥ 2 ω := p i=1 ω 2 i |x i | 2be a weighted norm on R p for some weights ω 1 , . . . ω p ≥ 0. Then, for some universal constant A > 0, we haveP(∥Λ(Φ) -E[Λ(Φ)]∥ ω ≥ ε) ≤ 2p exp - ε 2 4A∥V(Φ)∥ 2 ω , for 0 ≤ ε ≤ 2A∥V(Φ)∥ω 3 min 1≤i≤p √ Var[Λ(φi)] ∥φi∥∞• 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 Another common scenario is when F is parametrized by a finite-dimensional parameter space:dim span R (F) = D < ∞ for some D. (A.F = {f θ : θ ∈ Θ}, where Θ is a bounded subset of R D for some D, (A.2) ∥f θ -f θ ′ ∥ ∞ ≤ ℓ∥θ -θ ′ ∥ for some ℓ > 0, uniformly on Θ. (A.3)Conditions (A.2) and (A.3) cover e.g. the k-means problem of Example 1, as well as (non-)linear regression settings. For k-means, for instance, each query is parametrized by its cluster centers C = {q 1 , . . . , q k }, which can be viewed as a parameter (q 1 , . . . , q k ) ∈ R kd .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), it is natural to assume that 1 n |L(f )| ≥ c,P ∃f ∈ F : L S (f ) L(f ) -1 ≥ ε ≤ 2 exp 6D - c 2 ε 2 16AV , 0 ≤ ε ≤ 4AρmV 3c sup f ∈F ∥f ∥ ∞ • Assuming (A.2), (A.3), (A.4) and |S| ≤ B • m a.s. for some B > 0, we haveP ∃f ∈ F : L S (f ) L(f ) -1 ≥ ε ≤ 2 exp CD -D log ε - c 2 ε 2 16AV , 0 ≤ ε ≤ 4AρmV 3c sup f ∈F ∥f ∥ ∞ •Here A > 0 is a universal constant and C = C(Θ, B, ρ, ℓ, c) > 0 is some constant. ) for some δ > 0; see Section 3 for an example. Thus, the upper bound for the range of ε for which we could use our concentration result is O(m -δ ). Plugging in ε = m -α for α ≥ δ gives the upper bounds 2 exp(6D -C ′ m 1+δ-2α ) and 2 exp(CD + αD log m -C ′ m 1+δ-2α ) respectively (C and C ′ are some positive constants independent of m and n), which both converge to 0 as m → ∞ as long as α < (1 + δ)/2. In other words, the accuracy rate ε can be chosen to be as small as m -1/2-δ ′ /2 , for any 0 < δ ′ < δ, which is strictly smaller than the best accuracy rate m -1/2 of i.i.d. sampling. Remark 4.2. For i.i.d. sampling S with expected size m, P(x ∈ S) = m/n for all x ∈ X . For a DPP S with kernel K, one has P(x i ∈ S) = K ii . Thus, assuming that for all i, K ii ≥ ρ • m/n for some ρ > 0 means that every point in the dataset X should have a reasonable chance to be sampled. This also guarantees that the estimated loss L S (f ) = x∈S f (x)/K(x, x) will not blow up, where for x = x i ∈ X , we write K(x, x) for K ii . Remark 4.3. For the parametrized function spaces, the assumption |S| ≤ B • m a.s. is not strictly necessary, and is introduced here only for the sake of simplicity in presenting the results. A version of Theorem 4 without this assumption will be discussed in Appendix A. 4 . In fact, we only need n -1 x∈S K(x, x) -1 to be bounded with high probability, which follows from the condition K(x, x) ≥ ρ • m/n and the fact that |S| is highly concentrated around its mean m. Remark 4.4. However, we remark that the assumption |S| ≤ B • m a.s. holds for most kernels of interest; DPPs with projection kernels being typical 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 straightforward 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-valued functions, let F consist of f : X → R p . For each f ∈ F, we denote by L S (f ), L(f ) and V(f ) the vectors in R p whose i-coordinates are L S (f i ), L(f i ) andVar n -1 L S (f i ) 1/2 , respectively. Let ∥x∥ 2 ω := p i=1 ω 2 i |x i | 2 be a weighted norm on R p . Theorem 5. Let S be a DPP as in Theorem 4. Let V ≥ sup f ∈F max 1≤i≤p ω 2 i Var n -1 L S (f i ) . Assuming (A.1), then P ∃ f ∈ F : 1 n ∥L S (f ) -L(f )∥ ω ≥ ε ≤ 2p exp 6D - c 2 ε 2 16AV , where 0 ≤ ε ≤ 4AρmV 3c • (sup f ∈F max i=1,...,p ∥f i ∥ ∞ ) -1 .Application: Discretized multivariate OPE. 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 a wide class of linear statistics on X . To be more precise, in their setting, X = {x 1 , . . . , x n } is a random data set, where x i 's are i.i.d. samples from a distribution γ with support inside a d-dimensional hypercube; γ is a density estimator for γ and q(x)dx is a reference measure on that hypercube. The DPP S is then defined by the kernel K in Example 5 w.r.t. the empirical measure n -1 x∈X δ x . We normalize the kernel by setting K := n -1 K, so that S is a DPP with kernel K w.r.t. the counting measure on X . Then, under some mild assumptions on γ and q(x)dx, with high probability in the data set X , we have Var n -1 L S (f ) = O(m -(1+1/d) ) for any test function f satisfying some mild regularity conditions. For more details, we refer the reader to (Bardenet, Ghosh, et al., 2021) .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 a family of test functions on X satisfying regularity conditions as in Bardenet, Ghosh, et al., 2021. Then we can state: Theorem 6. For ε = O(m -1/d ), w.h.p. in the data set X , we have EQUATIONP S ∃f ∈ F : L S (f ) L(f ) -1 ≥ ε ≤ 2 exp CD -D log ε -C ′ ε 2 m 1+1/d ,(f )/L(f ) -1| ≤ m -( 1 2 + 1 2d ) -, ∀f ∈ F, where ( 1 2 + 1 2d) -denotes any positive number strictly smaller than 1 2 + 1 2d . Meanwhile, for i.i.d. sampling, the accuracy rate ε is at best m -1/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 dimensionally 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 m. 
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 6 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 ⊂ X of cardinality m. For the associated weight function ω in (2), we always take the inverse of the marginal probability of inclusion, i.e. ω(x) = 1/P(x ∈ S).The first two baselines use independent sampling. The uniform method returns m samples from X , uniformly and without replacement, and runs in O(m). The second method, sensitivity, is specific to the k-means problem. It corresponds to the classical sensitivity-based importance sampling coreset of Langberg and Schulman, 2010 described in Section 2. It runs in O(nk + nm).The rest of the methods use negative dependence. The third method, termed G-mDPP, uses an m-DPP sampler where the likelihood kernel is a Gaussian kernel, with adjustable bandwidth denoted by h. It is basically Algorithm 1 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 O(n 3 ) of performing SVD as a preprocessing, in addition to the usual O(nm 2 ) 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 a 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 γ to be a kernel density estimator (KDE) built on X , using the Epanechnikov kernel, with Scott's bandwidth selection method, as implemented in the scikit-learn package (Pedregosa et al., 2011) . When KDE estimation is precomputed as in our experiments, the method runs in O(nm 2 ), and O(n 2 + nm 2 ) otherwise. Note that there is no cubic power of n, as one can perform the eigenvalue thresholding in Example 1 by a reduced SVD of the m × n feature matrix (p k (x i )). The fifth method, termed Vdm-DPP, is Algorithm 2 of Tremblay et al., 2019, which runs in O(nm 2 ). 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 a stratified sampling baseline limited to the case where X ⊂ [-1, 1] d and X is "well-spread". It partitions [-1, 1] d into a grid of m bins, and then independently draws one element uniformly in the intersection of X with each bin. It is a special case of projection DPP, which runs in O(nm) and has obvious pitfalls, like requiring that X has a 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.The performance metric. To investigate the cardinality of a coreset for a given error, we let Q S denote the quantile function of sup |L S (f ) -L(f )|/L(f ), the supremum over all queries of the relative error. Intuitively, Q S (0.9) = 10 -2 means that 90% of the sampled coresets have a worst case relative error below 10 -2 . We shall look at how an estimated Q S (0.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 Q S (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] d ; see Figure 1a . We consider d = 2 for demonstration purposes, but we have observed similar results for other small dimensions. Figure 1b depicts our estimate of Q S (0.9) as a function of the coreset size m, in log-log format. The two i.i.d. baselines decrease as m -1/2 , as expected. The stratified baseline, intuitively well-suited to uniformly-spread datasets, outperforms all other methods with a m -1 rate, consistent with its known optimal variance reduction (Novak, 1988) . Finally, the m-DPP and the two DPPs also yield a faster decay, eventually outperforming the i.i.d. baselines as m 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 m -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 1c , we see that the rate of decay can go from i.i.d.-like to OPE-like as the bandwidth increases; this is expected from results like (Barthelmé et al., 2023) . Note that the color code of Figure 1c differs from other figures. In the uniform dataset of Fig. 1a , the sensitivity function is almost flat, which makes sensitivity behave like uniform. To give an edge to sensitivity, we now consider the trimodal dataset shown in Fig. 2a , with an OPE sample superimposed. The performance of sensitivity improves; see Figure 2b , while the determinantal samplers still outperform the independent ones thanks to a faster decay. For this dataset, it is not easy to stratify, and we thus do not show results for stratified.We note that the 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.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-DPP), compared to the two independent methods. However, the advantage progressively disappears as the dimension increases beyond 4 (unshown), as expected from the gain in variance of the discretized multivariate OPE, which becomes negligible when d ≫ 1; see Section 5 for suggestions on how to prove a dimension-independent decay. The source code used in this work is available at github.com/hsimonfroy/DPPcoresets, where DPP samplers are built upon the Python package DPPy (Gautier et al., 2019).  
discussion: 
 Limitations. Our paper is a theoretical contribution, and our approach has several limitations before it can be a 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 a good approximation to γ; see Section 3 and ( Bardenet, Ghosh, et al., 2021) . While Item 1) is usually deemed to be reasonable in a wide range of situations, we solve Item 2) by relying on a kernel density estimator, which is costly to manipulate. Another limitation is that the improvement over independent sampling is in 1/d and thus progressively vanishes as the dimension increases. Finally, a classical caveat is that although tractable, sampling a DPP still costs O(nm 2 ), provided the kernel is available in diagonalized form.Future work. The limitations above set up a research program. In particular, an intriguing observation in our empirical studies is the comparative performance of 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-DPPs, will be of great practical interest as they would bypass the need, e.g., for an approximation to the data-generating mechanism γ. The DPP called Vdm-DPP in Section 4, which is itself an OPE for a discrete measure, might be a bridge between OPEs and m-DPPs, as Vdm-DPP 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 a toolbox for machine learning. On the dependence of the rate to the dimension, we propose to investigate the impact of smoothness of the test functions on the rate: in numerical integration with mixtures of DPPs, smoothness does bring dimension-independent rates (Belhadji et al., 2020b) . Finally, in a more theoretical direction, extending concentration inequalities for linear statistics beyond the restricted range of ε appearing e.g. in Theorem 1 is a mathematically challenging problem, with potential learning-theoretic consequences.A Appendix / supplemental material A.1 Proof of Theorem 1We present here the proof for the general setting, i.e., when X is a Polish space and S is a DPP with a Hermitian kernel K w.r.t a background measure µ. By abuse of notation, we will also denote by K the integral operatorK : L 2 (X , µ) → L 2 (X , µ) , f (x) → X K(x, y)f (y)dµ(y). We denote by C k (φ), k ≥ 1 the cumulants of Λ(φ), i.e. log E[e tΛ(φ) ] = k≥1 C k (φ) k! t k , for t near 0. Note that C 1 (φ) = E[Λ(φ)], C 2 (φ) = Var [Λ(φ)].In general, we have the formula (see Johansson and Lambert, 2018)EQUATIONwhere Φ :L 2 (X , µ) → L 2 (X , µ) is the operator f (x) → φ(x)f (x).By the Macchi-Soshnikov theorem (Macchi, 1972; Soshnikov, 2000) , 0 ⪯ K ⪯ I, and we can writeEQUATIONHS , where ∥ • ∥ HS denotes the Hilbert-Schmidt norm of an operator. Lemma 1. For k ≥ 1, we have∥ √ I -KΦ k √ K∥ HS ≤ k∥φ∥ k-1 ∞ ∥ √ I -KΦ √ K∥ HS , where ∥φ∥ ∞ := sup x∈X |φ(x)|.Proof. One has∥ √ I -KΦ k √ K∥ 2 HS = Tr[ √ KΦ k (I -K)Φ k √ K] = Tr[Φ k (I -K)Φ k K] = Tr[Φ 2k K] -Tr[Φ k KΦ k K] = φ(x) 2k K(x, x)dµ(x) - φ(x) k K(x, y)φ(y) k K(y, x)dµ(x)dµ(y) = φ(x) 2k K(x, x) -K(x, y)K(y, x)dµ(y) dµ(x) + 1 2 (φ(x) k -φ(y) k ) 2 K(x, y)K(y, x)dµ(x)dµ(y).Since 0 ⪯ K ⪯ I, we have K 2 ⪯ K, which implies K(x, x) ≥ K(x, y)K(y, x)dµ(y) for µ-a.e.x. Thus, φ(x) 2k K(x, x) -K(x, y)K(y, x)dµ(y) dµ(x)≤ ∥φ∥ 2k-2 ∞ φ(x) 2 K(x, x) -K(x, y)K(y, x)dµ(y) dµ(x).On the other hand, by the symmetry of K, we have K(x, y)K(y, x) = |K(x, y)| 2 ≥ 0 for all x, y ∈ X . Note that|φ(x) k -φ(y) k | = |φ(x) -φ(y)| k-1 j=0 φ(x) j φ(y) k-1-j ≤ k∥φ∥ k-1 ∞ |φ(x) -φ(y)|.Combining all ingredients, we deduce that∥ √ I -KΦ k √ K∥ 2 HS ≤ k 2 ∥φ∥ 2k-2 ∞ ∥ √ I -KΦ √ K∥ 2 HS , as desired. Lemma 2. For k ≥ 3, we have |C k (φ)| k! ≤ 1 √ 2π e k k 3/2 ∥φ∥ k-2 ∞ C 2 (φ).Proof. We recall the formula (7) , observe thatk q=1 (-1) q+1 q k 1 ,...,kq ≥1 k1+...+kq=k k! k 1 ! . . . k q ! = 0.Then one can writeC k (φ) = n q=1 (-1) q+1 q k 1 ,...,kq ≥1 k1+...+kq=k k! k 1 ! . . . k q ! Tr[Φ k1 K . . . Φ kq K] -Tr[Φ k K] = n q=2 (-1) q+1 q k 1 ,...,kq ≥1 k1+...+kq=k k! k 1 ! . . . k q ! Tr[Φ k1 K . . . Φ kq K] -Tr[Φ k K] .For any k 1 , . . . , k q ≥ 1 such that k 1 + . . . + k q = k, we observe that|Tr[Φ k1 K . . . Φ kq-2 KΦ kq-1+kq K] -Tr[Φ k1 K . . . Φ kq-2 KΦ kq-1 KΦ kq K]| = |Tr[Φ k1 K . . . Φ kq-2 KΦ kq-1 (I -K)Φ kq K]| = |Tr[ √ KΦ k1 K . . . Φ kq-2 √ K √ KΦ kq-1 √ I -K √ I -KΦ kq √ K]| ≤ ∥ √ KΦ k1 K . . . Φ kq-2 √ K √ KΦ kq-1 √ I -K∥ HS • ∥ √ I -KΦ kq √ K∥ HS ≤ ∥ √ KΦ k1 K . . . Φ kq-2 √ K∥ op • ∥ √ KΦ kq-1 √ I -K∥ HS • ∥ √ I -KΦ kq √ K∥ HS ≤ ∥ √ KΦ k1 K . . . Φ kq-2 √ K∥ op • k q-1 k q ∥φ∥ kq-1+kq-2 ∞ ∥ √ I -KΦ √ K∥ 2 HS ≤ k q-1 k q ∥φ∥ k-2 ∞ C 2 (φ), here we used Lemma 1, the fact that 0 ⪯ K ⪯ I ,∥Φ∥ op = ∥φ∥ ∞ and the ∥ • ∥ op norm is submultiplicative. Since k j ≤ k for all 1 ≤ j ≤ q, using a telescoping argument gives|Tr[Φ k1 K . . . Φ kq K] -Tr[Φ k K]| ≤ qk 2 ∥φ∥ k-2 ∞ C 2 (φ).Hence|C k (φ)| ≤ k q=2 k 1 ,...,kq ≥1 k1+...+kq=k k! k 1 ! . . . k q ! k 2 ∥φ∥ k-2 ∞ C 2 (φ). Now observe that for k ≥ 3 k q=2 k 1 ,...,kq ≥1 k1+...+kq=k 1 k 1 ! . . . k q ! < k k k! ≤ e k √ 2πk • Thus, |C k (φ)| k! ≤ 1 √ 2π e k k 3/2 ∥φ∥ k-2 ∞ C 2 (φ).Combining all ingredients above, one can show that. Lemma 3. For |t| ≤ 1/(3∥φ∥ ∞ ), we have| log E[e tΛ(φ) ] -tE[Λ(φ)]| ≤ At 2 Var [Λ(φ)] ,where A > 0 is an universal constant.Proof. For |t| ≤ 1 3∥φ∥∞ , we have| log E[e tΛ(φ) ] -tE[Λ(φ)]| = k≥2 C k (φ) k! t k ≤ k≥2 |C k (φ)| k! |t| k ≤ |t| 2 C 2 (φ) 1 2 + k≥3 1 √ 2π e k k 3/2 ∥φ∥ k-2 ∞ |t| k-2 ≤ |t| 2 C 2 (φ) 1 2 + 1 √ 2π e 2 k≥3 k 3/2 (e/3) k-2 = At 2 Var [Λ(φ)] ,where A > 0 is some universal constant.We can finish the proof of Theorem 1 as follows.Proof of Theorem 1. Let ε > 0. We havelog P(Λ(φ) -E[Λ(φ)] ≥ ε) ≤ inf t log E[e tΛ(φ) ] -tE[Λ(φ)] -tε ≤ inf t -tε + t 2 A Var [Λ(φ)]where the infimum is taken on t ∈ (0, 1/(3∥φ∥ ∞ )].For 0 ≤ ε ≤ 2A Var[Λ(φ)] 3∥φ∥∞, choosingt 0 = ε 2A Var [Λ(φ)] ≤ 1 3∥φ∥ ∞ gives log P(Λ(φ) -E[Λ(φ)] ≥ ε) ≤ - ε 2 4A Var [Λ(φ)]as desired.Denote by Φ the diagonal matrix Diag(φ) ∈ R n×n . For each t ∈ R, we defineG t := I -exp(tΦ) = - ∞ k=1 t k k! Φ k .By the Campbell formula, we haveE[e tΛ(φ) ] = det[I -G t K], t ∈ R. By choosing t ≥ 0 small enough such that ∥G t K∥ op < 1, one can expand log det[I -G t K] = - ∞ k=1 1 k Tr[(G t K) k ].Observe that ∥G t ∥ op ≤ e |t|∥φ∥∞ -1 ≤ 2|t|∥φ∥ ∞ for all |t| ≤ 1/(3∥φ∥ ∞ ). From now on, we will consider t ≥ 0 such that0 ≤ t∥φ∥ ∞ M ≤ 1 3 ,where M := max(∥K∥ op , 1). This choice for t will particularly imply that ∥G t K∥ op ≤ 2/3.For k = 1, we have -Tr[G t K] = ∞ p=1 t p p! Tr[Φ p K] ≤ tE[Λ(φ)] + t 2 2 Tr[Φ 2 K] + p≥3 t p p! |Tr[Φ p K]| ≤ tE[Λ(φ)] + t 2 2 Tr[Φ 2 K] + p≥3 t p p! ∥φ∥ p ∞ ∥K∥ * ≤ tE[Λ(φ)] + t 2 2 Tr[Φ 2 K] + t 3 ∥φ∥ 3 ∞ ∥K∥ * .For k = 2, we have- 1 2 Tr[(G t K) 2 ] = - 1 2 p,q≥1 t p+q p!q! Tr[Φ p KΦ q K] = - t 2 2 Tr[ΦKΦK] - 1 2 p+q≥3 t p+q p!q! Tr[Φ p KΦ q K] ≤ - t 2 2 Tr[ΦKΦK] + 1 2 l≥3 t l l! 2 l ∥φ∥ l ∞ ∥K∥ op ∥K∥ * ≤ - t 2 2 Tr[ΦKΦK] + t 3 ∥φ∥ 3 ∞ ∥K∥ * ∥K∥ op . For k ≥ 3, we observe that |Tr[(G t K) k ]| ≤ ∥(G t K) k ∥ * ≤ ∥G t K∥ k-3 op ∥G t ∥ 3 op ∥K∥ 2 op ∥K∥ * ≤ 2 3 k-3 (2t∥φ∥ ∞ ) 3 ∥K∥ 2 op ∥K∥ * . Thus k≥3 1 k |Tr[(G t K) k ]| ≤ 8t 3 ∥φ∥ 3 ∞ ∥K∥ 2 op ∥K∥ * .Combining all ingredients, we deduce thatlog E[e tΛ(φ) ] ≤ tE[Λ(φ)] + t 2 2 Var [Λ(φ)] + t 3 ∥φ∥ 3 ∞ ∥K∥ * (1 + ∥K∥ op + 8∥K∥ 2 op ) ≤ tE[Λ(φ)] + t 2 2 Var [Λ(φ)] + 10t 3 ∥φ∥ 3 ∞ ∥K∥ * M 2 .Let ε > 0. We havelog P(Λ(φ) -E[Λ(φ)] ≥ ε) ≤ inf t log E[e tΛ(φ) ] -tE[Λ(φ)] -tε ≤ inf t -tε + t 2 2 Var [Λ(φ)] + t 3 • 10∥φ∥ 3 ∞ ∥K∥ * M 2where the infimum is taken on t ∈ (0, 1/(3∥φ∥ ∞ M )].For 0 ≤ ε ≤ Var[Λ(φ)] 2 40∥φ∥ 3 ∞ ∥K∥ * M 2 , we choose t 0 = ε Var [Λ(φ)] ≤ Var [Λ(φ)] 40∥φ∥ 3 ∞ ∥K∥ * M 2 ≤ 2M ∥φ∥ 2 ∞ ∥K∥ * 40∥φ∥ 3 ∞ ∥K∥ * M 2 < 1 3∥φ∥ ∞ M • This choice yields log P(Λ(φ) -E[Λ(φ)] ≥ ε) ≤ - ε 2 2 Var [Λ(φ)] + t 3 0 • 10∥φ∥ 3 ∞ ∥K∥ * M 2 .Note thatt 3 0 • 10∥φ∥ 3 ∞ ∥K∥ * M 2 = ε 3 Var [Λ(φ)] 3 • 10∥φ∥ 3 ∞ ∥K∥ * M 2 ≤ ε 2 4 Var [Λ(φ)] • This implies log P(Λ(φ) -E[Λ(φ)] ≥ ε) ≤ - ε 2 4 Var [Λ(φ)] as desired.Proof of Theorem 3. By a scaling argument, it suffices to prove for the case ω 1 = . . . = ω p = 1. We haveP(∥Λ(Φ) -E[Λ(Φ)]∥ 2 ≥ ε) = P p i=1 |Λ(φ i ) -E[Λ(φ i )]| 2 ≥ ε 2 = P p i=1 |Λ(φ i ) -E[Λ(φ i )]| 2 ≥ ε 2 p i=1 Var [Λ(φ i )] ∥V(Φ)∥ 2 2 ≤ p i=1 P |Λ(φ i ) -E[Λ(φ i )]| ≥ ε Var [Λ(φ i )] ∥V(Φ)∥ 2 •For each 1 ≤ i ≤ p, applying Theorem 1 givesP |Λ(φ i )-E[Λ(φ i )]| ≥ ε Var [Λ(φ i )] ∥V(Φ)∥ 2 ≤ 2 exp - ε 2 4A∥V(Φ)∥ 2 2 , ∀0 ≤ ε ≤ 2A∥V(Φ)∥ 2 Var [Λ(φ i )] 3∥φ i ∥ ∞ •The theorem follows.Using (A.4), we deduce thatL S (f ) L(f ) -1 ≤ 1 cn |L S (f ) -L(f )|, ∀f ∈ F.This impliesP ∃f ∈ F : L S (f ) L(f ) -1 ≥ ε ≤ P ∃f ∈ F : 1 n |L S (f ) -L(f )| ≥ cε .Thus, it suffices to bound the RHS. For each f ∈ F, let V ≥ Var n -1 L S (f ) , we apply Theorem 1 for the linear statistic L S (f ) = Λ(f /K) to obtainP 1 n |L S (f ) -L(f )| ≥ cε ≤ 2 exp - c 2 ε 2 4AV , ∀0 ≤ ε ≤ 2AnV 3c∥f /K∥ ∞ •Using K(x, x) ≥ ρm/n, we deduce that the above inequality holds for any 0 ≤ ε ≤ 2AρmV 3c∥f ∥∞ .Proof of Theorem 4: Assuming (A.1). We let F sym := {λf : |λ| ≤ 1, f ∈ F}, and let B be the convex hull of F sym . Since B is a symmetric convex body in F, there exists a norm ∥• ∥ F in F such that B is the unit ball in (F, ∥ • ∥ F ). Define L(f ) := 1 n L S (f ) -L(f ) , f ∈ F,then it is clear that L(f ) is linear in f . Moreover, for any f, g ∈ F, one has|L(f ) -L(g)| = |L(f -g)| = ∥f -g∥ F • L f -g ∥f -g∥ F ≤ ∥f -g∥ F sup h∈B |L(h)|.For each δ > 0, let B δ be a δ-net for (B, ∥ • ∥ F ). By definition of a δ-net, for any f ∈ B, there exists an f 0 ∈ B δ such that ∥ff 0 ∥ F ≤ δ. Thus, for every Let N (B, ∥ • ∥ F , 1/2) be the 1/2-covering number of B, thenP ∃f ∈ B : 1 n | LS (f ) -L(f )| ≥ cε ≤ N (B, ∥ • ∥ F , 1/2) • 2e -c 2 ε 2 /16AV ,for anyV ≥ sup f ∈B Var 1 n L S (f ) , 0 ≤ ε ≤ 4AρmV 3c sup f ∈B ∥f ∥ ∞ •Note that for a finite dimensional normed vector space, for 0 < δ < 1, one hasN (B, ∥ • ∥ F , δ) ≤ 3 δ dim F .This implies ≤ Var [L S (tλ 1 f 1 )] EQUATIONEQUATIONFrom ( 8), ( 9), (10) , the theorem follows.Proof of Theorem 4: Assuming (A.2), (A.3). We define L(θ) := 1 n (L S (f θ ) -L(f θ )), θ ∈ Θ. Then P ∃f ∈ F : By choosing B large, this event will have small probability. Meanwhile, on the event {|S| ≤ (B + 1)m}, we can use exactly the same argument as in the proof above.A.5 Proof of Theorem 5Proof of Theorem 5. It suffices to show for the case ω 1 = . . . = ω p = 1. For each f ∈ F, by applying Theorem 1 and an union bound argument, we haveP 1 n ∥L S (f ) -L(f )∥ ≥ ε ≤ 2p exp - c 2 ε 2 4AV , ∀0 ≤ ε ≤ 2AρmV 3c max i ∥f i ∥ ∞ •Using the same argument as in the proof of Theorem 4 under assumption (A.1) gives the result.Proof of Theorem 6. We remark that Var n -1 L S (f ) = O(m -(1+1/d) ) uniformly for all f ∈ F, w.h.p. in the data set X . Hence, Theorem 6 is a direct application of Theorem 4 with V = Cm -(1+1/d) for some constant C > 0. As we discussed in the Remark 4.1, the range for ε is O(m -1/d ). Thus, it suffices to check the conditions on K. Since K is a projection of rank m, |S| = m a.s. Moreover, we have n K(x, x) = K(x, x), 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).Note that we defined a coreset as a subset and not a sub-multiset of X , thus ignoring multiplicity. This is because we allow weights in (2), so that repeated items are unnecessary in a coreset.The link to a GitHub repository is temporarily hidden for anonymity. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

- When going from lipschitz (Peres and Pemantle) to linear functional concentration, what exactly changes which leads to the better bounds? 

- 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?

- What is an intuitive explanation of the fact that the range of $\epsilon$ got tighter in non-symmetric case? 

- Can there be chaining related improvements to further improve the provided bounds, as done in Bhatt and Bilmes 2021? 

- Is it possible to provide some experimental results with different choice of kernels including non-symmetric? 

- Writing Suggestion: It might improve readability of $\|\varphi\|_{\infty}$ is replaced by some constant bounding the loss function. 

References:
- Tighter m-DPP Coreset Sample Complexity Bounds, Bhatt and Bilmes 2021. Subset ML at ICML'21
questions: questions: Refer to the weakness.
limitations: limitations: Refer to the weakness.
paper_summary: paper_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.

To 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})$.
strength_weakness: strength_weakness: see the questions
questions: questions: - What is the time complexity of DPP-based coreset construction?
- The paper proposes some assumptions on the DPPs. Are these assumptions fair compared to previous methods?
limitations: limitations: none
paper_summary: paper_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. 
The superiority of DPP samples over uniform samples is demonstrated in a k-means application on toy data and MNIST data.
strength_weakness: strength_weakness: * 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. 
* 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).  
* 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.
questions: 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: limitations: yes, there is a dedicated limitations sections that I perceive as accurate
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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?

- 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.
questions: 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?

--
Thanks for the response. I increase my score to 5.
limitations: limitations: Yes

Comments: title: Thanks for the rebuttal, increasing score.
comment: Thank you for your responses. The authors have addressed my questions. I would like to raise my score.
Thank you very much for your positive response. Please let us know if you have further questions, or would like to have additional clarifications; we would be happy to furnish further details.
Thank you for your responses. The authors have addressed some of my questions. I would like keep my positive score.
Thank you for the clarifications. They make sense to me. I keep my positive score.
Thanks for responding to my questions! I believe this discussion can help the manuscript. I am raising my scores.