General bounds on the quality of Bayesian coresets

Authors: trevor  campbell
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:56:27

Abstract: Bayesian coresets speed up posterior inference in the large-scale data regime by approximating the full-data log-likelihood function with a surrogate log-likelihood based on a small, weighted subset of the data. But while Bayesian coresets and methods for construction are applicable in a wide range of models, existing theoretical analysis of the posterior inferential error incurred by coreset approximations only apply in restrictive settings---i.e., exponential family models, or models with strong log-concavity and smoothness assumptions. This work presents general upper and lower bounds on the Kullback-Leibler (KL) divergence of coreset approximations that reflect the full range of applicability of Bayesian coresets. The lower bounds require only mild model assumptions typical of Bayesian asymptotic analyses, while the upper bounds require the log-likelihood functions to satisfy a generalized subexponentiality criterion that is weaker than conditions used in earlier work. The lower bounds are applied to obtain fundamental limitations on the quality of coreset approximations, and to provide a theoretical explanation for the previously-observed poor empirical performance of importance sampling-based construction methods. The upper bounds are used to analyze the performance of recent subsample-optimize methods. The flexibility of the theory is demonstrated in validation experiments involving multimodal, unidentifiable, heavy-tailed Bayesian posterior distributions.

Main paper: 
 introduction: 
 Large-scale data is now commonplace in scientific and commerical applications of Bayesian statistics. But despite its prevalence, and the corresponding wealth of research dedicated to scalable Bayesian inference, there are still suprisingly few general methods that provably provide inferential results, within some reasonable tolerated error, at a significant computational cost savings. Exact Markov chain Monte Carlo (MCMC) methods require many full passes over the data [1, 2, , limiting the utility of these methods when even a single pass is expensive. A wide range of MCMC methods that access only a subset of data per iteration, e.g., via delayed acceptance [3] [4] [5] [6] , pseudomarginal or auxiliary variable methods [7] [8] [9] , and basic subsampling [10] [11] [12] [13] , provide at most a minor improvement over full-data MCMC [14] [15] [16] . On the other hand, methods including carefully constructed log-likelihood function control variates can provide substantial gains [17] [18] [19] . However, black-box control variate constructions for large-scale data often rely on assumptions such as posterior density differentiability and unimodality that do not hold in many popular models, e.g., those with discrete variables or multimodality. See [15, 20] for a survey of scalable MCMC methods. Parametric approximations via variational inference [21] or the Laplace approximation [22, 23] can be obtained scalably using stochastic optimization methods, but existing general theoretical guarantees for these methods again typically rely on posterior normality assumptions [24, p. 141-144,25-30] (see [21, 31] for a review).Although many existing methods rely on asymptotic normality or unimodality in the large-scale data regime, the problem of handling large-scale data in Bayesian inference does not fundamentally require this structure. Instead, one can more generally exploit redundancy in the data (i.e., the existence of good approximate sufficient statistics), which can be used to draw principled conclusions about a large data set based only on a small fraction of examples. Indeed, while approximate posterior normality often does not hold in models with latent discrete or combinatorial objects, weakly identifiable or unidentifiable parameters, persisting heavy tails, multimodality, etc., such models can and regularly do exhibit significant redundancy in the data that can be exploited for faster large-scale inference.Bayesian coresets [32] -which involve replacing the full dataset during inference with a sparse weighted subset-are based on this notion of exploiting data redundancy. Empirical studies have shown the existence of high-quality coreset posterior approximations constructed from a small fraction of the data, even in models that violate posterior normality assumptions and for which standard control variate techniques work poorly [33] [34] [35] [36] [37] . However, existing theoretical support for Bayesian coresets in the literature is limited. There exist no lower bounds on Bayesian coreset approximation error, and while upper bounds do exist, they currently impose restrictive assumptions. In particular, the best available theoretical upper bounds to date apply to exponential family models [36, 38] and models with strongly log-concave and locally smooth log-densities [37] .This article presents new theoretical techniques and results regarding the quality of Bayesian coreset approximations. The main results are two general large-data asymptotic lower bounds on the KL divergence (Theorems 3.3 and 3.5), as well as a general upper bound on the KL divergence (Theorem 5.3) under the assumption that the log-likelihoods satisfy a multivariate generalization of subexponentiality (Definition 5.2). The main general results in this paper lead to various novel insights about specific Bayesian coreset construction methods. Under mild assumptions,• common importance-weighted coreset constructions (e.g. [32] ) require a coreset size M proportional to the dataset size N (Corollary 4.1), even with post-hoc optimal weight scaling (Corollary 4.2), and thus yield a negligible improvement over full-data inference;• any construction algorithm requires a coreset size M > d when the log-likelihood function is determined by d parameters locally around a point of concentration (Corollary 4.3);• subsample-optimize coreset construction algorithms (e.g. [36] [37] [38] [39] ) achieve an asymptotically bounded error with a coreset size polylogN in a wide variety of models (Corollary 6.1).The paper includes empirical validation of the main theoretical claims on two models that violate common assumptions made in the literature: a multimodal, unidentifiable Cauchy location model with a heavy-tailed prior, and an unidentifiable logistic regression model with a heavy-tailed prior and persisting posterior heavy tails. Experiments were performed on a computer with an Intel Core i7-8700K and 32GB of RAM. Proofs of all theoretical results may be found in Appendix A.Notation. We use standard asymptotic growth symbols O, Ω, Θ, o, ω (see, e.g., [40, Sec. 3.3] ), and their probabilistic variants O p , Ω p , Θ p , o p , ω p (see, e.g., [24, Sec. 2.2] ). We use the same symbol to denote a measure π and its density π(•) with respect to a specified dominating measure. We also regularly suppress integration variables and differential symbols in integrals throughout for notational brevity when these are clear from context; for example, π exp(ℓ) is shorthand for π(dθ) exp(ℓ(θ)). Finally, the pushforward of a measure π by a map η is denoted simply ηπ.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The abstract and introduction state that the paper produces new general upper and lower bounds for Bayesian coreset approximations, that these bounds are applied to particular cases of interest, and that empirical results align with the theory. The paper does indeed contain these results, with proofs in the supplemental material, and empirical results in the figures do match the theory well.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
background: 
 Define a target probability distribution π on a space Θ comprised of a sum of N potentials ℓ n : Θ → R, n = 1, . . . , N and a base distribution π 0 (dθ),π(dθ) = 1 Z exp (ℓ(θ)) π 0 (dθ), ℓ(θ) = N n=1 ℓ n (θ), θ ∈ Θ,where the normalization constant Z is not known. In the Bayesian context, this distribution corresponds to a Bayesian posterior distribution for a statistical model with prior π 0 and conditionally i.i.d. data X n , where ℓ n (θ) = log p(X n |θ). The goal is to compute or approximate expectations under π; but the likelihood ℓ (and its gradient) becomes expensive to evaluate when N is large. To avoid this cost, Bayesian coresets [32] [33] [34] [35] [36] [37] involve replacing the target with a surrogate densityπ w (dθ) = 1 Z(w) exp (ℓ w (θ)) π 0 (dθ), ℓ w (θ) = N n=1 w n ℓ n (θ), θ ∈ Θ,where w ∈ R N , w ≥ 0 are a set of weights, and Z(w) is the new normalizing constant. If w has at most M ≪ N nonzeros, the O(M ) cost of evaluating n w n ℓ n (and its gradient) is a significant improvement upon the original O(N ) cost. In this work, the problem of coreset construction is formulated in the data-asymptotic limit; a coreset construction method should• run in o(N ) time and memory (or at most O(N ) with a small leading constant),• produce a small coreset of size M = o(N ),• produce a coreset with O(1) posterior forward/reverse KL divergence as N → ∞.These three desiderata ensure that the effort spent constructing and sampling from the coreset posterior is worthwhile: the coreset provides a meaningful reduction in computational cost compared with standard Markov chain Monte Carlo algorithms, and has a bounded approximation error.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: In the conclusions section of the work, two main limitations of the theory are mentioned: the need to perform case-by-case analysis of subexponentiality constants and alignment probabilities in Definition 5.2 and Corollary 6.1.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
lower bounds on approximation error: 
 This section presents lower bounds on the KL divergence of coreset approximations for general models and data generating processes. The first key steps in the analysis are to write all expectations in terms of distributions that do not depend on w, and to remove the difficult-to-control influence of the tails of π and π w by restricting certain integrals to some small subset B ⊆ Θ of the parameter space. Lemma 3.1, the key theoretical tool used in this section, achieves both of these two goals; note that the result has no major assumptions and applies generally in any setting that a Bayesian coreset can be used. For convenience, defineKL(w) := min{KL(π w ||π), KL(π||π w )},and the decreasing, nonnegative function f : R+ → R + , f (x) = -log x + x -1 0 ≤ x ≤ 1 0 x > 1.Lemma 3.1 (Basic KL Lower Bound). For all measurable B ⊆ Θ and coreset weights w,KL(w) ≥ f (J B (w)) ≥ 0,whereJ B (w) = B π 0 exp 1 2 (ℓ + ℓ w ) π 0 exp(ℓ) π 0 exp(ℓ w ) + π(B c ) .Note that while the integrals in the fraction denominator in J B (w) range over the whole Θ space, a further lower bound on KL(w) can be obtained by restricting their domains arbitrarily. Also, crucially, the bound in Lemma 3.1 does not depend on π w (B c ), which would be difficult to analyze without detailed knowledge of the tail behaviour of π w as a function of the coreset weights w. Although the bound in Lemma 3.1 applies generally, it is most useful when B is small (so that simple local approximations of ℓ and ℓ w can be used), π concentrates on B (so that π(B c ) ≈ 0), and π and π w are very different when restricted to B; the behaviour of the bound in this case is roughly (see the proof in Appendix A) f (J B (w)) ≈ -log(1 -TV(π, π w )). Finally, note that Lemma 3.1 remains valid if one replaces ℓ w with ℓ w -c and ℓ with ℓ -c ′ for any constants c, c ′ that do not depend on θ but may depend on the data and coreset weights w.For the remainder of this section, consider the setting where Θ is a measurable subset of R d for some d ∈ N, fix some θ 0 ∈ Θ, and assume each ℓ n is differentiable in a neighbourhood of θ 0 . Letw = n w n g = ∇ℓ(θ 0 ) g w = ∇ℓ w (θ 0 ).Theorems 3.3 and 3.5 characterize KL divergence lower bounds in terms of the sum of the coreset weights w and the log-likelihood gradients g, g w . Intuitively for the full data set where all w n = 1 and w = N , and an i.i.d. data generating process from the likelihood with parameter θ 0 , the central limit theorem asserts under mild conditions that g w /wp → 0 at a rate of N -1/2 . Theorems 3.3 and 3.5 below provide KL lower bounds when the coreset construction algorithm does not match this behavior. In particular, Theorem 3.3 provides results that are useful when g w /w p → 0 occurs reasonably quickly but slower than N -1/2 , while Theorem 3.5 strengthens the conclusion when g w /w p → 0 very slowly or not at all. The major benefit of Theorems 3.3 and 3.5 for analyzing coreset construction methods is that they reduce the problem of analyzing posterior KL divergence to the much easier problem of analyzing the 2-norm ∥ • ∥ 2 of a weighted sum of random vectors in R d .Consider a sequence r → 0 as N → ∞, and for a fixed matrix H ≻ 0 letB = {θ : (θ -θ 0 ) T H(θ -θ 0 ) ≤ r 2 }be a sequence of neighbourhoods around θ 0 ; these will appear in Assumptions 3.2 and 3.4 and Theorems 3.3 and 3.5 below. Note that throughout, all asymptotics will be taken as N → ∞, and various sequences (e.g., r and B) are implicitly indexed by N . To simplify notation, this dependence is suppressed. Assumption 3.2 makes some weak assumptions about the model and data generating process: it intuitively asserts that the potential functions are sufficiently smooth around θ 0 , that r → 0 slowly, and that π concentrates at θ 0 at a usual rate. Note that Assumption 3.2 does not assume data are generated i.i.d. and places no conditions on the coreset construction algorithm. Assumption 3.2. π 0 has a density with respect to the Lebesgue measure, π 0 (θ 0 ) > 0, each ℓ n (θ) and π 0 (θ) are twice differentiable in B for sufficiently large N , andsup θ∈B - 1 N ∇ 2 ℓ(θ) -H 2 = o p (1), g N 2 = O p N -1/2 , N r 2 = ω(1).Two additional assumptions related to the coreset construction algorithm-namely, that it works well enough that1 w n w n ∇ 2 ℓ n (θ)p → H and g w /wp → 0 at a rate faster than r → 0-lead to asymptotic lower bounds on the best possible quality of coresets produced by the algorithm, as well as lower bounds even after optimal post-hoc scaling of the weights. Theorem 3.3. Suppose Assumption 3.2 holds. Ifsup θ∈B - 1 w ∇ 2 ℓ w (θ) -H 2 = o p (1), g w w 2 = o p (r), then KL(w) ≥ O p (1)+Ω p (1) min -log π(B c ), N w N + w g N - g w w 2 2 +d log (N + w) 2 N max{w, 1/r 2 } min α≥0 KL(αw) ≥ O p (1)+Ω p (1) min -log π(B c ), d log N g N - g w w 2 2 .Theorem 3.3 is restricted to the case where the coreset algorithm is performing reasonably well. Theorem 3.5 extends the bounds to the case where the algorithm is performing poorly, in the sense that it is unable to make gw w p → 0 at a rate faster than r → 0 (or perhaps gw w does not converge to 0 at all). In order to draw conclusions in this setting, we need a weak global assumption on the potential functions. A functionEQUATIONNote that L-smoothness below is weaker than Lipschitz smoothness and does not imply concavity; Eq. ( 1) restricts the growth of the function only in the negative direction, and only when the expansion is taken at θ 0 . Assumption 3.4 asserts that the potential functions are smooth below.Assumption 3.4. There exist L 0 , . . . , L N , L > 0 such that log π 0 is L 2 0 -smooth below at θ 0 , for each n ∈ [N ] ℓ n is L 2 n -smooth below at θ 0 , and 1N N n=1 L 2 n p → L 2 .Theorem 3.5 uses Assumptions 3.2 and 3.4 and additional assumptions related to the coreset construction algorithm to obtain lower bounds in a setting that relaxes the "performance" conditions in Theorem 3.3: -1 w n w n ∇ 2 ℓ n (θ) no longer needs to converge to H in probability, and g w /w can converge to 0 slowly or not at all. Theorem 3.5. Suppose Assumptions 3.2 and 3.4 hold. If there exist α, β > 0 such thatP ∀θ ∈ B, - 1 w ∇ 2 ℓ w (θ) ⪰ αH → 1, P 1 w n w n L 2 n ≤ βL 2 → 1, g w w = ω p (r), then KL(w) ≥ O p (1) + Ω p (1) min -log π(B c ), d log N min g w w 2 ,1 .An important final note in this section is that while Theorems 3.3 and 3.5, as stated, require choosing Θ to be some measurable subset of R d and that the posterior π concentrates around some point of interest θ 0 ∈ R d , these results can be generalized to a wider class of models and spaces. In particular, Corollary 3.6 demonstrates that if Θ is arbitrary, but the potential functions ℓ n only depend on θ through some other function η : Θ → R d , that the conclusions of Theorems 3.3 and 3.5 still hold.Corollary 3.6. Suppose Θ is an arbitrary measurable space, and the potential functions take the form ℓ n (η(θ)) for some measurable function η : Θ → R d . Then if the assumptions of Theorems 3.3 and 3.5 hold for potentials (ℓ n ) N n=1 as functions on R d and pushforward prior ηπ 0 on R d , the stated lower bounds also hold for min{KL(π||π w ), KL(π w ||π)}.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Justification: Theoretical results are numbered, and proofs of all results are included in the appendix.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
lower bound applications: 
 In this section, the general theoretical results from Section 3 are applied to specific algorithms, Bayesian models, and data generating processes to explain previously observed empirical behaviour of coreset construction, as well as to place fundamental limits on the necessary size of coresets. Consider a setting where the data X n arise as an i.i.d. sequence drawn from some probability distribution ν, ℓ n (η(θ)) = log p(X n |η(θ)) for η : Θ → R d , η 0 = η(θ 0 ), and the following technical criteria hold (where E denotes expectation under the data generating process):(A1) E [∇ℓ n (η 0 )] = 0 and H = E -∇ 2 ℓ n (η 0 ) = E ∇ℓ n (η 0 )∇ℓ n (η 0 ) T ≻ 0. (A2) E ∥∇ℓ n (η 0 )∥ 2+δ 2 < ∞ for some δ > 0 and E ∥∇ 2 ℓ n (η 0 )∥ 2 F < ∞. (A3) On a neighbourhood of η 0 , ∥∇ 2 ℓ n (η) -∇ 2 ℓ n (η 0 )∥ 2 ≤ R(X n )∥η -η 0 ∥ 2 , E [R(X n )] < ∞.(A4) ηπ 0 is twice differentiable a neighbourhood of η 0 , and π(η 0 ) > 0.(A5) For all r → 0 such that r 2 = ω(log N/N ), -log ηπ(∥η -η 0 ∥ > r) = Ω p (N r 2 ).These conditions apply to a wide range of models, e.g., an unidentifiable, multimodal location model posterior with heavy tails on Θ = R, where the Bayesian model is specified byEQUATIONand the data are generated from the likelihood with parameter θ 0 = 5, and an unidentifiable logistic regression posterior with heavy tails on R 2 , where the Bayesian model is specified byEQUATIONthe covariates are generated via X n iid ∼ Unif({x ∈ R 2 : ∥x∥ 2 ≤ 1}), and the observations Y n are generated from the likelihood with parameter θ 0 = [1 6]T . See Proposition A.6 in Appendix A for the verification of (A1-5) for these two models. Example posterior log-densities for these models are displayed in Fig. 1 . A popular algorithm for coreset construction that has appeared in a wide variety of domains-e.g., Bayesian inference [32, 33, Section 4.1] , frequentist inference (e.g., [41] [42] [43] [44] [45] ), and optimization (see [46] for a recent survey)-involves subsampling of the data followed by an importance-weighting correction. The pseudocode is given in Algorithm 1. Note that E[w n ] = 1, and so E[ℓ w ] = ℓ; the coreset potential is an unbiased estimate of the exact potential. The advantage of this method is that it is straightforward and computationally efficient. If the sampling probabilities are uniform p n = 1 /N, then Algorithm 1 constructs a coreset in O(M ) time and O(M ) memory. Nonuniform probabilities p n require Ω(N ) time, as they require a pass over all N data points to compute each p n [32, 42] followed by sampling the coreset, e.g., via an alias table [47, 48] . However, empirical results produced by this methodology have generally been underwhelming, even with carefully chosen sampling probabilities; see, e.g., Figure 2 of [32] . Corollary 4.1 explains these poor results: Bayesian coresets constructed via Algorithm 1 must satisfy M ∝ N in order to maintain a bounded KL(w) in the data-asymptotic limit. In other words, such coresets do not satisfy the desiderata in Section 2. The only restriction is that there exist constants c, C > 0 such that for all N ∈ N, the sampling probabilitiesEQUATIONThe lower threshold ensures that the variance of the importance-weighted log-likelihood is not too large, while the upper threshold ensures sufficient diversity in the draws from subsampling. The condition in Eq. ( 4) is not a major restriction, in the sense that performance should deteriorate even further when it does not hold. The (p n ) N n=1 may otherwise depend arbitrarily on the data and model. Corollary 4.1. Given (A1-6), M → ∞, and M = o(N ), coresets produced by Algorithm 1 satisfyEQUATIONThe intuition behind Corollary 4.1 is that both the true posterior and the importance-weighted coreset posterior are asymptotically approximately normal with variance ∝ 1/N as N → ∞; however, the coreset posterior mean is roughly ∝ M -1/2 away from the posterior mean, because the subsample is of size M . The KL divergence between two Gaussians is lower-bounded by the inverse variance times the mean difference squared, yielding ≈ N/M as in Eq. ( 5).Given the intuition that the coreset posterior mean is far from the posterior mean relative to their variances, it is worth asking whether one can apply a small amount of effort to "correct" the importance-weighted coreset by scaling the weights (and hence the variance) down, as shown in Algorithm 2. Unfortunately, Corollary 4.2 demonstrates that even with optimal scaling, M ∝ N is still required in order to maintain a bounded KL divergence as N → ∞. 2) and (3). In particular, these figures show that the empirical rates of growth of KL as a function of N closely matches Ω p ( N M ) for importance-weighted coresets, and Ω p (log N M ) for the same with post-hoc scaling, for a wide range of coreset sizes M ∈ {log N,N , 1 /2N }. Thus, importance weighted coreset construction methods do not satisfy the desiderata in Section 2 for a wide range of models, and alternate methods should be considered.This section extends the minimum coreset size results from importance-weighted schemes to any coreset construction algorithm. In particular, Corollary 4.3 shows that under (A7)-a strengthening of (A3) and Assumption 3.4-and (A8)-which asserts that ∇ℓ 1 (η 0 ), . . . , ∇ℓ M (η 0 ) are linearly independent a.s. and satisfy a technical moment condition-at least d coreset points are required to keep the KL divergence bounded as N → ∞.(A7) Assumption 3.4 holds and there exists γ > 0 such that for all sufficiently large N ∈ N,∀η ∈ B, n ∈ [N ], -∇ 2 ℓ n (η) ⪰ γH and L 2 n < γ -1 L 2 .(A8) For all coreset sizes M < d, there exists a δ > 0 such thatE 1 T (G T G) -1 1 M +δ < ∞ G = [∇ℓ 1 (η 0 ) . . . ∇ℓ M (η 0 )] ∈ R d×M .Corollary 4.3. For a fixed coreset size M < d, given (A1-5,7,8),min w∈R N + :∥w∥ 0≤M KL(w) = Ω p (log N ).Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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: All details needed to reproduce the experimental results in Figure 2 Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
upper bounds on approximation error: 
 This section presents upper bounds on the KL divergence of coreset approximations. As in Section 3, the first step is to write all expectations in terms of distributions that do not depend on w. Lemma 5.1 does so without imposing any major assumptions; the result again applies generally in any setting that a Bayesian coreset can be used. For convenience, define KL(w) := max{KL(π w ||π), KL(π||π w )}.Lemma 5.1 (Basic KL Upper Bound). For all coreset weights w,KL(w) ≤ inf λ>0 1 λ log π exp (1 + λ)( lw -l) ,where for all n ∈ [N ], ln = ℓ n -πℓ n , l = n ln , and lw = n w n ln .The upper bound in Lemma 5.1 is nonvacuous (i.e., finite) as long as there exists a α > 1 such that the α Rényi divergence D α (π w ||π) [49, p. 3799] is finite. Note that as in Lemma 3.1, the bound in Lemma 5.1 remains valid if one replaces ℓ w with ℓ w -c and ℓ with ℓ -c ′ for any constants c, c ′ that do not depend on θ but may depend on the coreset weights w and data.More practical bounds necessitate an assumption about the behaviour of the potentials (ℓ n ) N n=1 . Definition 5.2 below asserts that the multivariate moment generating function of (ℓ n ) N n=1 is bounded when the vector is close to 0. This definition is a generalization of the usual definition of subexponentiality for the univariate setting (e.g., [50, Sec. 2.7] ). Theorem 5.3 subsequently shows that Definition 5.2 is sufficient to obtain simple bounds on KL. Definition 5.2. For A ∈ R N ×N , A ⪰ 0, and monotone function h :R + → R + such that lim x→0 h(x) = h(0) = 0, the potentials (ℓ n ) N n=1 are (h, A)-subexponential if ∀w ∈ R N : w T Aw ≤ 1, π exp lw ≤ exp h(w T Aw) . Theorem 5.3. If the potentials (ℓ n ) N n=1 are (h, A)-subexponential, then ∀w ∈ R N + : 4(w -1) T A(w -1) ≤ 1, KL(w) ≤ h(4(w -1) T A(w -1)).Definition 5.2, the key assumption in Theorem 5.3, is satisfied by a wide range of models when choosing h(x) = x and A ∝ Cov π (ℓ n ) N n=1 , as demonstrated by Proposition 5.4. Because this case applies widely, let A-subexponential be shorthand for (h, A)-subexponentiality with h(x) = x. Proposition 5.4. If for all w in a ball centered at the origin, π exp( lw ) < ∞, then there exists β > 0 such that the potentials (ℓ n ) N n=1 are β Cov π (ℓ n ) N n=1 -subexponential.(ℓ(θ)) = O p (N α ), M = (log N ) 1 1-ρ , and P max 0, Corr π ℓ I M (θ), ℓ(θ) -ℓ ⋆ M -1 (θ) 2 ≥ 1 -ϵ (ℓ n ) N n=1 = ω p (M -ρ ) (6) ℓ ⋆ M -1 (θ) = arg min g∈cone{ℓ I 1 ,...,ℓ I M -1 } Var π (ℓ(θ) -g(θ)) I 1 , . . . , I M iid ∼ Categorical(p 1 , . . . , p N ).Then Algorithm 3 produces a coreset with KL(w) = O p (1) as N → ∞.Fig. 3 confirms that subsample-optimize coreset construction methods applied to the logistic regression and Cauchy location models in Eqs. ( 2) and (3) (which both violate the conditions of past upper bounds in the literature) are able to provide high-quality posterior approximations for very small coresets-in this case, M ∝ log N .Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: All details needed to reproduce the experimental results in Figure 2 and 3 are included in the text. Algorithms used in the experiments exist in the cited literature.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. Guidelines:• The answer NA means that the paper does not include experiments. • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
conclusions: 
 This article presented new general lower and upper bounds on the quality of Bayesian coreset approximations, as measured by the KL divergence. These results were used to draw novel conclusions regarding importance-weighted and subsample-optimize coreset methods, which align with simulation experiments on two synthetic models that violate the assumptions of past theoretical results. Avenues for future work include general bounds on the subexponentiality constant β in Proposition 5.4, as well as the alignment probability in Eq. ( 6), in the setting of Bayesian models with i.i.d. data generating processes. A limitation of this work is that both quantities currently require case-by-case analysis.  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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: This does not apply.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Proof of Lemma 3.1. By Vajda's inequality [51] ,KL(w) ≥ log 1 + TV(π, πw) 1 -TV(π, πw) - 2 TV(π, πw) 1 + TV(π, πw) ≥ -log (1 -TV(π, πw)) -TV(π, πw) ≥ 0.The bound is monotone increasing in TV(π, πw); therefore because the squared Hellinger distance satisfies the inequality [52, p. 61],H 2 (π, πw) = 1 2 √ π - √ πw 2 ≤ 1 2 |π -πw| = TV(π, πw),we have thatKL(w) ≥ -log 1 -H 2 (π, πw) -H 2 (π, πw).We substitute the value of the squared Hellinger distance to find thatKL(w) ≥ -log √ ππw + √ ππw -1 ≥ 0. Note that √ ππw ≤ 1, so KL(w) ≥ -log min{1, √ ππw } + min{1, √ ππw } -1 ≥ 0.The bound is monotone decreasing in √ ππw , so we require an upper bound on √ ππw . To obtain the required bound, we split the integral into two parts-one on the set B, and the other on B c -and then use the Cauchy-Schwarz inequality to bound the part on B c . Note that by definition π and πw are mutually dominating, so the density ratio πw/π is well-defined and measurable.√ ππw = B √ ππw + B c √ ππw = B √ ππw + π πw π 1Bc ≤ B √ ππw + π(B c ) = B π0 exp 1 2 (ℓ + ℓw) π0 exp(ℓ) π0 exp(ℓw) + π(B c ) .The result follows.Proof of Lemma 5.1. We first consider the forward KL divergence. By definition,KL(π||πw) = π(ℓ -ℓw) + log π0 exp(ℓw) π0 exp(ℓ) = π(ℓ -ℓw) + log π exp(ℓw -ℓ).Since the KL is positive, for λ > 0,KL(π||πw) ≤ 1 + λ λ π(ℓ -ℓw) + 1 + λ λ log π exp(ℓw -ℓ) ≤ 1 + λ λ π(ℓ -ℓw) + 1 λ log π exp((1 + λ)(ℓw -ℓ)) = 1 λ log π exp((1 + λ)( lw -l)),by Jensen's inequality. Next we consider the reverse KL divergence. For any λ ̸ = 0,KL(πw||π) = πw(ℓw -ℓ) + log π0 exp(ℓ) π0 exp(ℓw) = 1 λ πwλ(ℓw -ℓ) -log π exp(ℓw -ℓ).By Jensen's inequality, for λ > 0,KL(πw||π) ≤ 1 λ log πw exp(λ(ℓw -ℓ)) -log π exp(ℓw -ℓ) = 1 λ log π exp((1 + λ)(ℓw -ℓ)) π exp(ℓw -ℓ) -log π exp(ℓw -ℓ) = 1 λ log π exp((1 + λ)(ℓw -ℓ)) - 1 + λ λ log π exp(ℓw -ℓ) ≤ 1 + λ λ π(ℓ -ℓw) + 1 λ log π exp((1 + λ)(ℓw -ℓ)) = 1 λ log π exp((1 + λ)( lw -l)).This is the same bound as in the forward KL divergence case. Since the bound applies for all λ > 0, we can take the infimum.Proof of Theorem 3.3. By replacing the integrals over the whole space Θ in the denominator of JB(w) in Lemma 3.1 with integrals over the subset B,KL(w) ≥ -log min(1, JB(w)) + min(1, JB(w)) -1 ≥ Op(1) -log JB(w) ≥ Op(1) + min GB(w), -log π(B c ) GB(w) = -log B π0 exp((1/2)(ℓ + ℓw)) + 1 2 log B π0 exp(ℓ) + 1 2 log B π0 exp(ℓw).So to obtain the stated lower bound on the KL divergence, we require an upper bound on log B π0 exp((1/2)(ℓ+ ℓw)), and lower bounds on log B π0 exp(ℓ) and log B π0 exp(ℓw). By Taylor's theorem, Assumption 3.2, and the assumption onEQUATIONWe shift the exponential arguments in GB(w) by (1/2)(ℓ(θ0) + ℓw(θ0)), note that π0 is continuous and positive around θ0, and and apply the Taylor expansions in Eq. ( 7) to obtain an upper bound on the first term:log B π0e 1 2 (ℓ-ℓ(θ 0 )+ℓw -ℓw (θ 0 )) ≤ Op(1) + log B e 1 2 ((g+gw ) T (θ-θ 0 )- (∼1)(N +w) 4 (θ-θ 0 ) T H(θ-θ 0 ) ,where (∼ 1) denotes a quantity that converges in probability to 1 as N → ∞. We can transform variables to x = C T (θ -θ0), where H = CC T is the Cholesky factorization of H, and subsequently complete the square:log B π0e 1 2 (... ) ≤ Op(1) + (∼ 1)∥C -1 (g + gw)∥ 2 4(N + w) + log ∥x∥ 2 ≤r 2 e - (∼1)(N +w) 4x-EQUATION)We can obtain lower bounds on the other two terms using a similar technique:log B π0e ℓ-ℓ(θ 0 ) ≥ Op(1) + (∼ 1)∥C -1 g∥ 2 2N + log ∥x∥ 2 ≤r 2 e - (∼1)N 2x-(∼1)C -1 g N 2 (9) log B π0e ℓw -ℓw (θ 0 ) ≥ Op(1) + (∼ 1)∥C -1 gw∥ 2 2w + log ∥x∥ 2 ≤r 2 e - (∼1)w 2x-EQUATIONIt remains to analyze the three log . . . terms. We bound the integral term in Eq. ( 8) with the integral over the whole space:log ∥x∥ 2 ≤r 2 e -(∼1)(N +w) 4 ∥...∥ 2 ≤ Op(1) - d 2 log(N + w).For the integral term in Eq. ( 9), note that since N r 2 = ω(1) and ∥C -1 g/N ∥ = Op(N -1/2 ), we havelog ∥x∥ 2 ≤r 2 e -(∼1)N 2 ∥...∥ 2 = log e -(∼1)N 2 (... ) - ∥x∥ 2 >r 2 e -(∼1)N 2 ∥x- (∼1)C -1 g N ∥ 2 ≥ log (∼ 1)2π N d/2 -e - (∼1)N 4 min ∥x∥≥r x- (∼1)C -1 g N 2 e -(∼1)N 4 ∥x- (∼1)C -1 g N ∥ 2 = log (∼ 1)2π N d/2 -e -Ωp (N r 2 ) 4 (∼ 1)4π N d/2 = - d 2 log(N ) + Op(1).For the integral term in Eq. ( 10), we consider two cases: one where w is large, and one where it is small. First assume wr 2 > 8d log 2; then by a similar technique as used in the first lower bound, since ∥C -1 gw/w∥ = op(r),log ∥x∥ 2 ≤r 2 e -(∼1)w 2 ∥...∥ 2 ≥ log (∼ 1)2π w d/2 -e - (∼1)w 4 min ∥x∥≥r x- (∼1)C -1 gw w 2 e -(∼1)w 4 ∥x- (∼1)C -1 gw w ∥ 2 ≥ log (∼ 1)2π w d/2 -e -2d log 2(∼1) (∼ 1)4π w d/2 ≥ - d 2 log w + Op(1).When wr 2 ≤ 8d log 2, we transform variables y = x/r to find that since ∥C -1 gw/w∥ = op(r), So therefore combining all previous results,EQUATIONEQUATIONEQUATIONEQUATIONN w N + w C -1 g N - C -1 gw w 2 + d 4 log (N + w) 2 N max{w, 1/r 2 } = Op(1) + Ωp(1) N w N + w g N - gw w 2 + d log (N + w) 2 N max{w, 1/r 2 }.We now consider the minimum over α ≥ 0. Since neither Op(1) or Ωp(1) above depends on w, we have thatmin α≥0 KL(αw) ≥ Op(1) + Ωp(1) min -log π(B c ), min α≥0 N αw N + αw g N - gw w 2 + d log (N + αw) 2 N max{αw, 1/r 2 } .On the 1/r 2 branch of the objective function, the derivative in α is always positive, and hence the minimum occurs at α = 0, and somin α≥0 (. . . ) ≥ d log(N r 2 ).On the αw branch of the objective function, min α≥0 N αw N + αw g N - gw w 2 + d log (N + αw) 2 N αw ≥ min α≥0 N αw N + αw g N - gw w 2 + d log (N + αw) N αw + d log N.GB(w) = -log B π0 exp((1/2)(ℓ + ℓw)) + 1 2 log π0 exp(ℓ) + 1 2 log π0 exp(ℓw).Note that GB in this proof is subtly different from the GB used in the proof of Theorem 3.3; the latter two integrals are over the whole space (directly from Lemma 3.1), rather than B. We shift the exponential arguments in GB(w) by (1/2)(ℓ(θ0) + ℓw(θ0)). We first provide lower bounds on two of the integral terms via Assumption 3.4:log π0e ℓ-ℓ(θ 0 ) ≥ Op(1) + log e (g+g 0 ) T (θ-θ 0 )-(∼1)(N +1)L ′2 2 ∥θ-θ 0 ∥ 2 ,where (∼ 1) denotes a quantity that converges in probability to 1, g0 = ∇ log π0(θ0), andEQUATIONx-EQUATIONx-gw +g 0 (w+1)L ′ w 2 = Op(1) + w + 1 2L ′2 w gw + g0 w + 1 2 - d 2 log(w + 1) ≥ Op(1) + w + 1 2 max{βL 2 , L 2 0 } gw + g0 w + 1 2 - d 2 log(w + 1).For the upper bound on the first term, we use a local quadratic expansion around θ0, where H0 = -∇ 2 log π0(θ0),log B π0e 1 2 (ℓ-ℓ(θ 0 )+ℓw -ℓw (θ 0 )) ≤ Op(1) + log B e 1 2 ((g+gw +2g 0 ) T (θ-θ 0 )- (∼1)(N +w+2) 4 (θ-θ 0 ) T (N +αw)H+2H 0 N +w+2 (θ-θ 0 ) .Because H ≻ 0, we have (N + αw)H + 2H0 ≻ 0 eventually; we can transform variables to x = C T (θ -θ0), where x-EQUATIONSuppose first that w + 1 ≤ N/(4∥C -1 ∥ 2 max{βL 2 , L 2 0 }). In this case we bound the integral in Eq. ( 11) by integrating over the whole space:log B π0e 1 2 (... ) ≤ Op(1) + (∼ 1)∥C -1 ∥ 2 (N + w + 2) 4 g + gw + 2g0 N + w + 2 2 - d 2 log(N + w + 2).Combining this with the previous results yields GB(w) ≥ Op( 1)- (∼ 1)(N + w + 2) 4 ∥C -1 ∥ 2 g + gw + 2g0 N + w + 2 2 + d 4 log (N + w + 2) 2 (N + 1)(w + 1) + w + 1 4 max{βL 2 , L 2 0 } gw + g0 w + 1 2 + (N + 1) 4 max{L 2 , L 2 0 } g + g0 N + 1 2 ≥ Op(1) + d 4 log (N + w + 2) 2 (N + 1)(w + 1) + w + 1 4 gw + g0 w + 1 2 1 max{βL 2 , L 2 0 } - 2∥C -1 ∥ 2 (w + 1) N + w + 2 ≥ Op(1) + d 4 log (N + w + 2) 2 (N + 1)(w + w + 1 8 max{βL 2 , L 2 0 } gw + g0 w + 1 2 .Bounding the last term below by 0 and minimizing over w such that w ≤ Next suppose w + 1 ≥ N/(4∥C -1 ∥ 2 max{βL 2 , L 2 0 }). A second upper bound on Eq. ( 11) can be obtained by taking the maximum of the integrand over the integration region ∥x∥ 2 ≤ r 2 . Note that since ∥gw/w∥ = ωp(r), w = Ωp(N ), g/N = Op(N -1/2 ), and N r 2 = ωp(1), we have that ∥(g + gw + 2g0)/(N + w + 2)∥ = ωp(r), and soEQUATIONC -1 (g + gw + 2g0) N + w + 2 + d 2 log r 2 .So therefore combining this result with the previous bounds and minimizing over w yields Combining with the earlier bound and noting that N min{∥gw/w∥, 1} = ωp(1) yields the final result.EQUATIONEQUATIONProof of Corollary 3.6. The proof follows directly from Theorems 3.3 and 3.5 by the data processing inequality applied to KL(w).Proof of Theorem 5.3. By Lemma 5.1,KL(w) ≤ inf λ>0 1 λ log π exp (1 + λ)( lw -l) = inf λ>0 1 λ log π exp l(1+λ)(w-1) . Since (ℓn) N n=1 are (f, A)-subexponential, if (1 + λ) 2 (w -1) T A(w -1) ≤ 1, then π exp l(1+λ)(w-1) ≤ exp f ((1 + λ) 2 (w -1) T A(w -1)) .By assumption, the condition holds when λ = 1; the result follows.Proof of Proposition 5. w T U w ≤ α 2 λ+ 4 =⇒ v T U v ≤ α 2 λ+ 4 =⇒ ∥v∥2 ≤ α 2 ,and so C(w) is continuous, has derivatives of all orders, and derivatives can be passed through the integral within the set {w ∈ R N : w T U w ≤ α 2 λ + 4 }. By Taylor's theorem, for any w in this set, there exists a distribution νw with density proportional to π exp( lw ′ ) for some w ′ on the segment from the origin to w such thatC(w) = log π exp( lw) = 1 2 w T U w + 1 6 Eν w (w T ( ln) N n=1 ) 3 .By definition of νw, w ∈ ker U implies that w T ( ln) N n=1 = 0 νw-a.s. and hence 1 6 Eν w (w T ( ln)N n=1 ) 3 = 0. Therefore, for w T U w ≤ α 2 λ + 4 , C(w) ≤ 1 2 w T U w     1 + max w T U w≤ α 2 λ + 4 w⊥ker U 1 6Eν w (w T ( ln)N n=1 ) 3 w T U w     ≤ 1 2 w T U w 1 + max ∥w∥ 2 ≤ α 2 1 6 ∥w∥2 Eν w ( ln) N n=1 ⊗ ( ln) N n=1 ⊗ ( ln) N n=1 2 λ+ ≤ 1 2 w T U w 1 + α 12λ+ max ∥w∥ 2 ≤ α 2 Eν w ( ln) N n=1 ⊗ ( ln) N n=1 ⊗ ( ln) N n=1, where ⊗ denotes outer products to form a tensor. By continuity of derivatives of all orders within the neighbourhood ∥w∥2 < α, the result follows by selecting a sufficiently small α.Proposition A.1. Suppose there exist c ∈ R, α, δ > 0, and 0 < ϵ < 1 such that ℓ ≤ c and for all coreset weights w satisfying αw T Covπ((ℓn) N n=1 )w ≤ 1, | lw| ≤ ϵ|ℓ -c| + δ. Then the potentials (ℓn) N n=1 are (h, α Covπ((ℓn) N n=1 ))-subexponential with h(x) = 1 2 x + e δ+cϵ π 0 e ϵℓ x 1-ϵ . Proof of Proposition A.1. Let ℓ ′ = ℓ -c. Since ℓ ′ ≤ 0 and | lw| ≤ ϵ|ℓ ′ | + δ for some ϵ < 1, δ > 0, π exp( lw) = 1 + 1 2 π( lw) 2 + π ∞ k=3 1 k! ( lw) k-2(1-ϵ) ( lw) 2(1-ϵ) ≤ 1 + 1 2 π( lw) 2 + π ∞ k=3 1 k! (ϵ|ℓ ′ | + δ) k-2(1-ϵ) | lw| 2(1-ϵ) = 1 + 1 2 π( lw) 2 + π e ϵ|ℓ ′ |+δ -1 -(ϵ|ℓ ′ | + δ) -1 2 (ϵ|ℓ ′ | + δ) 2 (ϵ|ℓ ′ | + δ) 2(1-ϵ) | lw| 2(1-ϵ) ≤ 1 + 1 2 π( lw) 2 + πe ϵ|ℓ ′ |+δ | lw| 2(1-ϵ) = 1 + 1 2 π( lw) 2 + π0e (1-ϵ)ℓ ′ +δ | lw| 2(1-ϵ) π0e ℓ ′ ≤ 1 + 1 2 π( lw) 2 + e δ π0e ℓ ′ | lw| 2 1-ϵ π0e ℓ ′ = 1 + 1 2 π( lw) 2 + e δ π0e ℓ ′ -ϵ π( lw) 2 1-ϵ = 1 + 1 2 π( lw) 2 + e δ+cϵ π0e ℓ -ϵ π( lw) 2 1-ϵ ≤ exp h(w T Covπ(ℓ)w) ,where h(x) = 1 2 x + e δ+cϵ π 0 e ϵℓ x 1-ϵ .Proposition A.2. Suppose Θ = R d , l is G-strongly concave, and there exists L < G, α > 0, and θ0 ∈ Θ such that for all coreset weights w satisfying αw T Covπ((ℓn) N n=1 )w ≤ 1, lw is L-Lipschitz smooth, and both ∥∇ℓw(θ0)∥ and lw(θ0) are bounded. Then for any (L/G) < ϵ < 1, there exists c ∈ R, δ > 0 such that the potentials (ℓn) N n=1 are (h, α Covπ((ℓn) N n=1 ))-subexponential with the same h as in Proposition A.1.Proof of Proposition A.2. Since l is G-strongly concave and lw is L-Lipschitz smooth, we can writeℓ(θ) ≤ ℓ(θ0) + ∇ℓ(θ0) T (θ -θ0) - G 2 ∥θ -θ0∥ 2 = ℓ(θ0) + G 2 G -1 ∇ℓ(θ0) 2 - G 2 θ -θ0 -G -1 ∇ℓ(θ0) 2 | lw(θ)| ≤ | lw(θ0) + ∇ℓw(θ0) T (θ -θ0)| + L 2 ∥θ -θ0∥ 2 . So setting c = ℓ(θ0) + G 2 G -1 ∇ℓ(θ0) 2 implies ℓ -c is a nonpositive function as required. Then | lw(θ)| -ϵ|ℓ(θ) -c| ≤ | lw(θ0)| + ϵ 2G ∥∇ℓ(θ0)∥ 2 + (∥∇ℓw(θ0)∥ + ϵ∥∇ℓ(θ0)∥)∥θ -θ0∥ + L -ϵG 2 ∥θ -θ0∥ 2 .For 0 < a < G -L, setting ϵ = L+a G and then maximizing over ∥θ -θ0∥ yields| lw(θ)| -ϵ|ℓ(θ) -c| ≤ | lw(θ0)| + ϵ 2G ∥∇ℓ(θ0)∥ 2 + (∥∇ℓw(θ0)∥ + ϵ∥∇ℓ(θ0)∥)∥θ -θ0∥ - a 2 ∥θ -θ0∥ 2 ≤ | lw(θ0)| + ϵ 2G ∥∇ℓ(θ0)∥ 2 + (∥∇ℓw(θ0)∥ + ϵ∥∇ℓ(θ0)∥) 2 2a .By the boundedness of lw(θ0) and ∇ℓw(θ0), maximizing over w yields a value of δ < ∞.Lemma A.3. Let X1, X2, . . . be i.i.d. random variables in R with EXn = 0, and define the resampled sumSN = N n=1Lemma A.4. Suppose coreset weights are generated using the importance weighted construction in Algorithm 1. Let g = ∇ℓ(η0), gw = ∇ℓw(η0), and H = -E ∇2 ℓn(η0) . If conditions A(1-3) and (A6) in Section 4 hold, M = o(N ), and M = ω(1), theng N 2 = Θp N -1/2 , gw w 2 = Θp M -1/2 , w N p → 1,andsup ∥η-η 0 ∥ 2 ≤r - 1 N ∇ 2 ℓ(η) -H 2 p → 0, sup ∥η-η 0 ∥ 2 ≤r - 1 w ∇ 2 ℓw(η) -H 2 p → 0.Proof. First, since w = n Mn M pn , Ew = N , andE (w -N ) 2 = N 2 M 2 E n Mn (N pn) -1 -1 2 = N 2 M 2   n ((N pn) -1 -1) 2 EM 2 n + n̸ =n ′ ((N pn) -1 -1)((N p n ′ ) -1 -1)E[MnM n ′ ]   = N 2 M n ((N pn) -1 -1) 2 pn - n ′ (1/N -pn) 2 = 1 M n pn(p -1 n -N ) 2 ≤ 1 M max n (p -1 n -N ) 2 ≤ N 2 M O(1),where the last line follows by assumption A6. Therefore by Chebyshev's inequality and M → ∞, w/N p → 1. Since the data are i.i.d., by conditions A1 and A2, the central limit theorem holds for the sum of ∇ℓn(η0) such that g/ √ N converges in distribution to a normal, and hence g N = Θp(N -1/2 ). By conditions A1, A2, and A6, Lemma A.3 holds such that for anyt ∈ R d , √ M 1 N t T gw -1 N t T g 1 N n (t T ∇ℓn(η 0 )) 2 N pn = Θp(1).Since condition A6 asserts that C > N pn ≥ c > 0, the law of large numbers, condition A1, andM/N → 0 imply that √ M N t T gw = Θp(1).Summing over a basis of vectors t1, . . . , t d shows that√ M N ∥gw∥2 = Θ(1) √ M gw w 2 Θp(1).This completes the first three results. Next, by condition A3, for sufficiently large N such that the neighbourhood contains the ball of radius r around η0,sup ∥η-η 0 ∥ 2 ≤r 1 N ∇ 2 ℓ(η) - 1 N ∇ 2 ℓ(η0) 2 ≤ r 1 N n R(Xn) sup ∥η-η 0 ∥ 2 ≤r 1 N ∇ 2 ℓw(η) - 1 N ∇ 2 ℓw(η0) 2 ≤ r 1 N n wnR(Xn),andE r 1 N n R(Xn) = E r 1 N n wnR(Xn) = rE [R(X)] → 0,so that we have that bothsup ∥η-η 0 ∥ 2 ≤r 1 N ∇ 2 ℓ(η) - 1 N ∇ 2 ℓ(η0) 2 p → 0 and sup ∥η-η 0 ∥ 2 ≤r 1 N ∇ 2 ℓw(η) - 1 N ∇ 2 ℓw(η0)by Markov's inequality. Finally, by the bounded variance in A2, sampling probability bounds in A6, and M → ∞, the variances of 1 N ∇ 2 ℓw(η0) and 1 N ∇ 2 ℓ(η0) both converge to 0 as N → ∞, and since both of these quantities are unbiased estimates of E ∇ 2 ℓn(η0) , Chebyshev's inequality yields the desired convergence in probability.Lemma A.5. Suppose (Xn) N n=1 are N i.i.d. random vectors in R d . Fix M ∈ N, M < d and define X = X1 X2 . . . XM ∈ R d×M . If there exists δ > 0 such that E (1 T (X T X) -1 1) M +δ < ∞,where 1 denotes a vector of all 1 entries, then as N → ∞,     min w∈R N + N n=1 wnXn N n=1 wn 2 s.t. n 1[wn > 0] < M.      = ωp N -M +δ/2 M +δ .Proof. For any ϵ > 0, by the union bound over subsets of [N ] of size M ,P min w∈R N + • • • ≤ ϵ ≤ N M P min w∈R M w T X T Xw w T 11 T w ≤ ϵ ≤ N M P max λ min w∈R M w T X T Xw -λ(1 T w -1) ≤ ϵ = N M P max λ λ - λ 2 4 1 T (X T X) -1 1 ≤ ϵ = N M P 1 T (X T X) -1 1 ≥ ϵ -1 .By Markov's inequality and N M ≤ (eN/M ) M , P minw∈R N + • • • ≤ ϵ ≤ eN M M ϵ M +δ E (1 T (X T X) -1 1) M +δ = eN ϵ M +δ M M M E (1 T (X T X) -1 1) M +δ . Setting ϵ = N -M +δ/2 M +δ yields P min w∈R N + • • • ≤ N -M +δ/2 M +δ ≤ eN -δ 2M M M E (1 T (X T X) -1 1) M +δ .The right-hand side converges to 0 as N → ∞, yielding the stated result. = {(η -η0) T H(η -η0) ≤ r 2 }. Then since H ≻ 0, r → 0, and r 2 = N -M +3δ/4 M +δ = ω(log N/N ), (A5) guarantees that -log(ηπ)(B c ) = Ωp(N r 2 ) = Ωp N δ/4 M +δ . For the right term, log N gw w 2 = Ωp log N 1-M +δ/2 M +δ = Ωp(log N ).The minimum of these two is from the right term, soKL(w) = Ωp(log N ).We complete the proof by transferring from KL(w) on the η-pushforward model to KL(w) on the original model using Corollary 3.6.Proposition A.6. The models specified in Eqs.(2) and (3) satisfy assumptions (A1-5).Proof. The exact same technique applies to both models, so here we will just demonstrate it for the Cauchy model. In the Cauchy model, θ ∈ R, η : R → R+, η(θ) = θ 2 , andℓn(η) = -log π -log((Zn -η) 2 + 1) ∇ℓn(η) = 2(Zn -η) (Zn -η) 2 + 1 ∇ 2 ℓn(η) = 2(Zn -η) 2 -2 ((Zn -η) 2 + 1) 2 ∇ 3 ℓn(η) = 4((Zn -η) 2 -3)(η -Zn) ((η -Zn) 2 + 1) 3 ,where Zn = Xn. Property (A1) holds by routine interchange of differentiation and integration. Property (A2) holds (for any δ > 0) because ∇ℓn(η) and ∇ 2 ℓn(η) are bounded functions of η and Xn jointly. Property (A3) holds (for any neighbourhood of η0) because ∇ 3 ℓn(η) is a bounded function of η and Xn jointly. Property (A4) holds because the pushforward of Cauchy(0, 1) through η(θ) = θ 2 has full support on R+. In order to verify assumption (A5), suppose there exists a sequence of bounded measurable functions ϕr(Z1, . . . , ZN ) ∈ [0, 1] of the data and constants c, c ′ > 0 such that for all r → 0, r 2 = ω(log N/N ),Eη 0 ϕr = O e -cN r 2 and sup ∥η-η 0 ∥>r Eη(1 -ϕr) = O e -c ′ N r 2 .The functions ϕr are similar to the test functions of Schwartz [55] . Then defining µ = ηπ and µ0 = ηπ0, µ(∥η -η0∥ > r) = ϕrµ(∥η -η0∥ > r) + (1 -ϕr)µ(∥η -η0∥ > r) ≤ ϕr + (1 -ϕr)µ(∥η -η0∥ > r)= ϕr + ∥η-η 0 ∥>r (1 -ϕr)e ℓ(η)-ℓ(η 0 ) µ0 e ℓ(η)-ℓ(η 0 ) µ0 .Using the same proof technique as in Theorem 3.3, the denominator satisfieslog e ℓ(η)-ℓ(η 0 ) µ0(dη) ≥ - d 2 log N + Op(1).By assumption, there exists c > 0 such thatEη 0 [ϕr] = O e -cN r 2 =⇒ ϕr = Op(e -cN r 2 ),and a c ′ > 0 such thatEη 0 ∥η-η 0 ∥>r (1 -ϕr)e ℓ(η)-ℓ(η 0 ) µ0 = ∥η-η 0 ∥>r Eη(1 -ϕr)µ0 ≤ sup ∥η-η 0 ∥>r Eη(1 -ϕr) = O(e -cN r 2 ) =⇒ ∥η-η 0 ∥>r (. . . ) = Op e -cN r 2 . Therefore µ(∥η -η0∥ ≥ r) = Op e -cN r 2 + N d/2 e -c ′ N r 2= Op e (d/2) log N -c ′′ N r 2 ; and since r 2 = ω(log N/N ), -log µ(∥η -η0∥ ≥ r) = Ωp(N r 2 ) as required by (A5). So to complete the proof of (A5) we need to find a suitable ϕr. Fix ϵ > 0, and set ϕr(Z1, . . . , ZN) = 1 Pη 0 (|Z -η0| ≤ 1) - 1 N N n=1 1[|Zn -η0| ≤ 1] > ϵr .Under pη 0 , Hoeffding's inequality yields Eη 0 ϕr ≤ e -2N ϵ 2 r 2 .And under pη for ∥η -η0∥ > r, for small enough ϵ > 0, Pη 0 (|Z -η0| ≤ 1) -Pη(|Z -η0| ≤ 1) ≥ 2ϵr. ThereforeEη[1 -ϕr(Z1, . . . , ZN )] = Prη Pη 0 (|Z -η0| ≤ 1) - 1 N N n=1 1[|Zn -η0| ≤ 1] ≤ ϵr ≤ Prη Pη(|Z -η0| ≤ 1) - 1 N N n=1 1[|Zn -η0| ≤ 1] ≤ -ϵr = Prη 1 N N n=1 1[|Zn -η0| ≤ 1] -Pη(|Z -η0| ≤ 1) ≥ ϵr ,at which point we can again apply Hoeffding's inequality, completing the result.Lemma A.7. Fix vectors u, u1, . . . , uN in a separable Hilbert space with inner product denoted a • b and norm denoted ∥ ∥. Let v1, . . . , vM be drawn from {u1, . . . , uN } with probabilities p1, . . . , pN either with or without replacement (if without replacement, the probabilities are renormalized after every draw). Then for all ϵ ≥ 0,P   min w≥0 M m=1 wmvm -u 2 > ϵ M q(M,ϵ) 2 +1 ∥u∥ 2   ≤ e - 1-log(2) 2 M ,whereq(M, ϵ) = P 1 -max 0, vM ∥vM ∥ • (u -xM-1) ∥u -xM-1∥ 2 ≤ ϵ xM-1 = arg min x∈cone{v 1 ,...,v M -1 } ∥x -u∥ 2 .Proof. First note that it suffices to analyze the case with replacement, since this case provides an upper bound on the case without replacement. To demonstrate this, we couple two probability spaces-one that draws v1, . . . , vM with replacement, and one without replacement. First, draw an identical vector v1 for both copies.On each subsequent iteration m > 1, the "with replacement" copy first draws whether or not it selects a vector that was previously selected by the "without replacement" copy. If it does, it draws that vector independently; if it does not, it selects the same vector as the "without replacement" copy. In any case, at each iteration m, the vectors drawn by the "with replacement" copy are always a subset of the vectors drawn by the "without replacement" copy, and hence the minimum over w ≥ 0 is greater for that copy. It therefore suffices to analyze the case with replacement.To obtain an upper bound on the probability when sampling with replacement, instead of minimizing over all w ≥ 0 jointly, suppose we use the following iterative algorithm. Set x0 = 0. At the first iteration, we draw v1 and set the weight w1 by optimizing over w1 ≥ 0: minw 1 >0 ∥w1v1 -u∥ 2 = ∥u∥ 2 1 -max 0, v1 • u ∥v1∥∥u∥ 2 .Set x1 = w1v1, and note that (u -x1) • x1 = 0. Then at each subsequent iteration k, assume the previous iterate is optimized over all nonnegative weights, and hence satisfies (u -x k-1 ) • x k-1 = 0. We draw another vector v k , and bound the erorr of the next iterate x k by optimizing over only the weight w k for the new vectorv k . Then ∥u -x k ∥ 2 = min w 1 ,...,w k ≥0 k m=1 wmvm -u 2 ≤ min w k >0 ∥w k v k + x k-1 -u∥ 2 = ∥u -x k-1 ∥ 2 1 -max 0, v k • (u -x k-1 ) ∥v k ∥∥u -x k-1 ∥ 2 .Therefore,P   min w≥0 M m=1 wmvm -u 2 ≤ ϵ K ∥u∥ 2   ≥ P in at least K iterations, ∥x k -u∥ 2 ≤ ϵ∥x k-1 -u∥ 2 ≥ P in at least K iterations, 1 -max 0, v k • (u -x k-1 ) ∥v k ∥∥u -x k-1 ∥ 2 ≤ ϵ = K⊆[M ],|K|≥K P k ∈ K ⇐⇒ 1 -max 0, v k • (u -x k-1 ) ∥v k ∥∥u -x k-1 ∥ 2 ≤ ϵ ≥ K⊆[M ],|K|≥K q k (1 -q) M -k = M k=K M k q k (1 -q) M -k ,whereq = P 1 -max 0, vM • (u -xM-1) ∥vM ∥∥u -xM-1∥ 2 ≤ ϵ xM-1 = arg min x∈cone{v 1 ,...,v M -1 } ∥x -u∥ 2So for all 0 ≤ K ≤ M ,P   min w≥0 M m=1 wmvm -u 2 > ϵ K ∥u∥ 2   ≤ Binom(M, K -1, q).Using the Chernoff bound on the binomial CDF, for all K -1 ≤ M q,P   min w≥0 M m=1 wmvm -u 2 > ϵ K ∥u∥ 2   ≤ e -M K-1 M log K-1 M q +(1-K-1 M ) log 1-K-1 M 1-q = e -(K-1) log K-1 M q -(M -(K-1)) log M -(K-1) M (1-q) .Substituting K -1 = M q/2 yields = e M ((q/2) log 2-(1-q/2) log1-q/2 (1-q) ) ≤ e - 1-log(2) 2 M .Proof of Corollary 6.1. Since the potentials are β Covπ((ℓn) N n=1 ) subexponential, Theorem 5.3 guarantees that ∀w ∈ R N + : 4β(w -1) T Covπ((ℓn) N n=1 )(w -1) ≤ 1, KL(w) ≤ 4β(w -1) T Covπ((ℓn) N n=1 )(w -1). We apply Lemma A.7 with vectors ℓ1, . . . , ℓN (in equivalence classes specified up to a additive constant) and inner product between ℓi, ℓj defined by Covπ(ℓi, ℓj). In the notation of Lemma A.7, by assumption, ∥u∥ 2 = Op(N α ) and q(M, ϵ) = ωp(M -ρ ). Substituting M = (log N ) 1/(1-ρ) , we find thatP 4β(w -1) T Covπ((ℓn) N n=1 )(w -1) ≥ ϵ -ωp(log N )+α log N → 0.Combining this result with the KL bound above yields the final result.NeurIPS Paper ChecklistJustification: There are no new algorithms presented in this work; the experiments involve only existing methods for which public code is available. The code is not central to the contributions of the paper.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.p → 0 


Decision: The paper addresses the problem of evaluating the quality of Bayesian coreset approximations by deriving new general lower and upper bounds on the Kullback-Leibler (KL) divergence between coreset and full-data posteriors. These bounds are applied to analyze and draw conclusions about the performance of importance-weighted and subsample-optimize coreset methods, with results supported by simulation experiments. The theoretical contributions are strong, particularly the novel lower bounds that avoid strict assumptions. However, concerns were raised about the gap between upper and lower bounds (Reviewers jwKa and 2Qah) and the need for more empirical validation, especially with real-world data (Reviewers UnLw and 2Qah). There is also a suggestion to refine the presentation of technical notations (Reviewer vJwU) and clarify the implications of the lower bounds (Reviewers jwKa, 2Qah, and EUq5).

Reviews: review: paper_summary: paper_summary: This work contributes to the approximation theory of Bayesian coresets. It establishes asymptotic lower bounds (in KL divergence) of Bayesian coreset approximation that do not require posterior normality assumptions. It also provides an upper bound of the approximation (in KL divergence) when the potentials satisfy the generalized subexponentiality condition. The theories are applied to some recent coreset construction algorithms in the literature to corroborate their observed empirical performances.
strength_weakness: strength_weakness: - Since this manuscript studies both the lower and upper bounds of coreset approximation, a natural question that arises is how well do the lower and upper bounds match each other? Can the author(s) provide an example to see if there is a gap between these two bounds? That is, if we consider a specific set of subexponential potentials with a specific $f$ and $A$, can we show that its upper bound matches its lower bound when $N$ is sufficiently large? Or, are the lower and upper bounds incomparable? If these bounds are optimal, they can guide researchers in designing corset construction algorithms and greatly benefit the community. 
- In the second lower bound in Theorem 3.3, is there a trade-off between $N$ and $\|\frac{g}{N} - \frac{g_w}{\bar{w}}\|^2_2$ as $N \to \infty$ while $\|\frac{g}{N} - \frac{g_w}{\bar{w}}\|^2_2 \to 0$? If $\|\frac{g}{N} - \frac{g_w}{\bar{w}}\|^2_2 \to 0$ faster than $N \to \infty$, do we end up having a lower bound that's close to $0$? 
- It seems like the role of the sequence $r$ (i.e., how fast does $r \to 1$) is very significant in establishing the lower bound. Specifically, in Corollary 4.1, 4.2, and 4.3, $r$ is carefully chosen as shown in the proofs. I find it necessary to specify these choices of $r$ in the statements of Corollary 4.1, 4.2, and 4.3.
questions: questions: See weaknesses
limitations: limitations: Yes, the author(s) have addressed the limitations in the conclusion section.
paper_summary: paper_summary: The authors present general upper and lower bounds on the Kullback-Leibler (KL) divergence of coreset approximations. The lower bounds require only mild model assumptions typical of Bayesian asymptotic analyses, while the upper bounds require the log-likelihood functions to satisfy a generalized subexponentiality criterion that is weaker than conditions used in earlier work. The lower bounds are applied to explain the the poor performance of importance sampling-based construction methods. The upper bounds are used to analyze the performance of recent subsample-optimize methods.
strength_weakness: strength_weakness: The paper offers a theoretical explanation for the suboptimal performance of importance-weighted coreset construction, and the conclusions of Corollary 4.1 and 4.2 are further validated by simulation results (Figure 2). 
However, [32] presents extensive experimental results on real-world datasets, which raises questions about the effectiveness of the lower bounds in scenarios where the model is misspecified or when working with real-world data (where models are often misspecified to some extent).
questions: questions: 1. Could you please provide some discussions about whether the theories can be extended to misspecified regime?
2. Providing formal definitions for some notations such as $\Omega_p$ and $\omega_p$ would be helpful.
limitations: limitations: The paper clearly states its limitation.
paper_summary: paper_summary: The paper derives bounds on the quality of coresets, as measured by forward and reverse KL divergence. The lower bound is used to study importance weighted coresets, leading to the conclusion that importance weighting leads to a large (forward or reverse) KL divergence between the approximate posterior and the posterior unless $\Omega(N)$ points are sampled into the coreset. They also use these results to show that under additional conditions, any coreset must be of size at least $d$, where $d$ is the dimensionality of the parametric class to avoid a large KL divergence. The upper bound is used to show that coresets  of size $O(\log N)$ are sufficient to maintain bounded KL divergences for the subsample-optimize approach.
strength_weakness: strength_weakness: - Several statements are made in text that seem overly strong. For example, the authors claim that “handling large-scale data in Bayesian inference…”requires exploiting redundancy in the data”. This seems overly strong (without proof). Further, I think there are large-scale data problems in Bayesian inference that can be solved via exploring structure that cannot be solved via exploiting data redundancy. For example, the likelihood in Gaussian process inference with a regularly spaced one-dimensional data can be computed quickly by exploiting structure in the prior/posterior, but I don’t think would be well-addressed by coreset methods (since there is very little data redundancy). Of course, this isn’t really meant as a criticism of coresets, or to suggest this is the type of problem the authors try to solve. I simply think strong claims should be made specific and supported by results.
- (Minor) I find the notation used around measures to be somewhat confusing and I think unorthodox. For example, my understanding is that $\pi_0$ is a measure, but in assumption 3.2, it is also used for a density. Similarly, in assumption 3.2, using $\pi_0(d \theta)$ for the measure itself (without an integral) seems unusual. And the integration notation without a differential element seems unorthodox (I would expect either $d\pi$ or maybe $\pi(d\theta)$). I have also not seen the push forward measure written without either a $\\#$ or $\*$, or more directly as a composition. Perhaps the authors can point me to a standard reference using these notations.
- (Minor) The definition of f in Lemma 3.1 seems unnecessarily complicated. In particular, if $x \leq 1$, f is just 0. Defining f in cases would likely make it more interpretable if space allows.
questions: questions: - Could the authors provide proof that $L$ smoothness from below implies Lipschitz smoothness? At a minimum it seems differentiability is required in $L$-smoothness. But also it looks to me more like a Lipschitz condition on the derivate of f instead of f itself.
- The authors claim that (2) and (3) satisfy the earlier assumptions, but no reference is provided. I didn’t see a checking of assumptions in the appendix. Could the authors either include this, or point me to the correct section if it is already included?
- Line 191: “Nonuniform probabilities require at least $O(N)$ time and memory…”, should this be $\Omega(N)$? I’m not convinces at least $O(N)$ makes sense as a notion, since $O(N)$ includes, for example, constant time algorithms.
- In section 6, the authors make several references to “exact coresets” without previously introducing the concept. What is meant by this? Does this mean a coreset that results in exactly recovering the posterior, or something else?
- This is certainly beyond the scope of the current work, but I am curious. Are the approximation results presented strong enough to establish contraction for the approximate posterior produced by Bayesian coreset methods? (perhaps following a similar argument to Ray and Szabo, 2020 Theorem 5).

### Reference
Ray and Szabo. Variational Bayes for high-dimensional linear regression with sparse priors. 2020.
limitations: limitations: Limitations seem well-adressed.

### Other Comments:
Consider defining the various big-O etc notation used in a footnote or appendix. These are all reasonably standard, but some come up less than others and I think it would be useful for many readers. Relatedly, $\omega$ and $w$ are quite hard to tell apart. I don’t know if there is a fix for this, but perhaps it is worth considering.
paper_summary: paper_summary: This paper provides new lower and upper asymptotic bounds on the KL divergence between the true posterior and the posterior obtained from common classes of coreset construction algorithms, under milder assumptions than previously used.

My own research is in the area of Bayesian statistics but overall less theoretical. Yet, I could follow along thanks to the authors clear structure and writing. I did not have time to check all the proofs in detail but the authors gave me no reason to disbelieve their results.
strength_weakness: strength_weakness: I don’t see any major weaknesses. Of course, it would have been desirable to see the results illustrated on more complicated empirical examples, but I understand why the authors used the examples they did.
questions: questions: Can the authors provide more intuition on why (close to Eq 4) “The lower threshold ensures that the variance of the importance-weighted log-likelihood is not too large, while the upper threshold ensures sufficient diversity in the draws from subsampling.”?
limitations: limitations: The provided limitations appear sensible to me.
paper_summary: paper_summary: This paper studies the quality of posterior likelihood based on coreset, a subset of the full data. The quality is quantified through KL divergence between the posterior likelihoods based on coreset and full data, so the main theorems demonstrate the upper and lower bounds of KL which are of great concern.
strength_weakness: strength_weakness: 1. Tightness of the upper and lower bounds. I am not sure how different are the bounds from each other. If upper and lower bounds are different from each other, their applications might be limited.

2. There seem to be insufficient experimental results to support the results.
questions: questions: 1. Please describe the gaps between the upper and lower bounds of the KL divergence.

2. The paper seems to be related subsampling in frequent statistics. Is coreset method a Bayesian counterpart?
limitations: limitations: NA

Comments: title: Thanks for the comments and clarifications
Response
Thanks for response.
discussion
comment: I am pleased that the authors have thoroughly addressed my questions and concerns. I would like to strongly suggest accepting this paper.
Thanks to the authors for the detailed response to my comments, especially the clarification on Lipschitz smoothness versus Lipschitz continuity. I think it could be useful for the authors to add a definition for this in the appendix, although I don't think it is essential since this isn't the assumption they are working with directly. The questions I had were answered in detail and I will maintain my rating; I still feel the paper should be accepted.
Thanks. I will keep my (positive) score.
Thanks for your follow up!

> But I don’t agree with your response that lower bound implies low quality.

A *large* lower bound does indeed imply low quality. For example, in the case of our Cor 4.1, we prove that the KL must be lower bounded by (ignoring constants) $N/M$ for importance weighting methods; therefore in order to control the KL divergence, importance weighting methods must set $M\propto N$, as otherwise the KL grows without bound as $N\to\infty$. At this point we have shown that if one wants to maintain control of the KL, importance weighted coresets can yield at most a constant reduction in coreset size asymptotically in $N$.

> Lower bound is typically used to justify if the upper bound can be further improved.

We are not using lower bounds to prove sharpness of upper bounds in this paper; we are using lower bounds to show that some very popular algorithms perform poorly, and using upper bounds to analyze other algorithms to show that they work well.
KL divergence is a measure to examine the quality of a core set. Small upper bound implies good quality. This is what I agree with the author(s). 

But I don’t agree with your response that lower bound implies low quality. 

Lower bound is typically used to justify if the upper bound can be further improved. For instance, if you prove that that 

0.1<KL<0.2 

It is possible that your upper bound 0.2 is not sharp and could be further lowered. Of course it could be also that your lower bound is not sharp. But the lower bound 0.1 doesn’t mean that the core set is bad.
Dear Reviewer 2Qah,

Thank you very much for submitting your review report. The author(s) have posted responses to your review. Could you kindly provide comments on whether your concerns have been adequately addressed?

Best regards, AC
Thanks for the clarifying responses to my questions! I am happy to recommend accept.