General bounds on the quality of Bayesian coresets
Authors: Trevor Campbell
Venue: NeurIPS 2024 poster (2024)
Keywords: Bayesian
coreset
Kullback Leibler divergence
error bounds
Primary area: probabilistic_methods
TL;DR: This paper presents new general upper and lower bounds on the quality of Bayesian coresets.

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.

General bounds on the quality of Bayesian coresets
Trevor Campbell" Department of Statisties University of British Columbia trevor@stat.o ubc. ca
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 wide range of models, existing theoret- ical analysis of the posterior inferential error incurred by coreset approximations only apply in restrictive settings- i..., exponential family models, models with strong log- cog-ccncyvity and smoothness assumptions. This work presents general upper and lower bounds the Kullback-Leible (KL) divergence of coreset ap- proximations 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- log-likelihood functions to satisfy 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 theoretical explanation for the previously-observed poor empirical performance of importance sampling-basee construction methods. The upper bounds are used to analyze the performance of recent subsamplc-optimize methods. The flexibility of the theory is demonstrated in validation experiments involving multimodal, unidentifiable, heavy-tailed Bayesian posterior distributions.
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 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, Ch. 6-12, 2, Ch. 11- 12), limiting the utility of these methods when even a single pass is expensive. A wide range of MCMC methods that access only subset of data per iteration, e.g., via delayed acceptance [3-6], pseudomarginal or auxiliary variable methods [7-9], and basic subsampling [10-13), provide at most minor improvement over full-data MCMC [14-16]. On the other hand, methods including carefully constructed log- lig-likelihood function control variates can provide substantial gains [17-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, existing general theoretical guarantees for these methods again typically rely posterior normality assumptions [24, p. 141-144,25. (see (21,31] for a review).
"atrp://ttrevorcampboll..e
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 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 beavy 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]-whick] which involve replacing the full dataset during inference with sparse weighted subset- are are based on this notion of exploiting data redundancy. Empirical studies have coreset posterior approximations constructed from small
shown the existence of high-qualite fraction of the data, even in models that violate posterior normality assumptions and for which standard control variate techniques work poorly [33-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 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- ligliiklisoods satisfy 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-weightee 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 negligible improvement over full-data inference;
any construction algorithm requires a coreset size M > d when the lokeliieldoood function is determined by d parameters locally around a point of concentration (Corollary 4.3);
subsample-optimize coreset construction algorithms (e.g. [36-39]) achieve an asymptotically bounded error with a coreset size polylog.V in 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: 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 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 o, (see, c.g., [40, Sec. 3.3]), and their probabilistic variants Op. 2p. Pp. Op, Wp (see, c.g., [24, Sec. 2.2]). We use the same symbol Up to denote measure and its density T(.)) with respect to a specified dominating measure. We also regularly suppress integration variables and differential symbols in integrals throughout for notational brevity when these clear from context; for example, J f'TT exp({) is shorthand for J (d0f) exp(e(0)). Finally, the pushforward of measure by map 17 is denoted simply TyT.
2 Background
Define a target prohability distribution æ on a space θ comprised of a sum of N potentials bn : 0 - R, 1,...,A N and base distribution (d()).
1 T (dd) Z exp (E(0)) (d()).
E(O) Σ (O),
0 E θ
n=1
where the normalization constant Z is not known. In the Bayesian context, this distribution corre- sponds to Bayesian posterior distribution for statistical model with prior za and conditionally i..dd data X,, where (0) = (og The goal is to compute or approximate expectations under n; but the likelihood E (and its gradient) becomes expensive to evaluate when N is large. To

---

avoid this cost, Bayesian coresets [32-37] involve replacing the target with surrogate density
N
(dd) Z(w)
exp (0) To(d0).
(w) W. (n),(())
0 E θ
where RN, w 0 are set of weights, and ((w) is the new normalizing constant. If w has at most M < N nonzeros, the (MM) cost of evaluating En w,,6, (and its gradient) a significant improvement upon the original ((N) cost. In this work, the problem of coreset construction is formulated in the data-asymptotie limit; a coreset construction method should
run in (N) time and memory (or most O(N) with small leading constant),
produce a small coreset of size M = o(N),
produce a coreset with (1) posterior forward/reverse KL divergence as N + oo.
These three desiderata ensure that the effort spent constructing and sampling from the coreset posterior is worthwhile: the coreset provides meaningful reduction in computational cost compared with standard Markov chain Monte Carlo algorithms, and has bounded approximation error.
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 the analysis are to write all expectations in terms of distributions that do not depend on and to remove the difficult-to-come the tails of т and uw by restricting certain integrals to some small subset B C θ of the parameter space. Lemma 3. 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, define
influence of
KL(w)= == miLT(LTT)) (L(T||/T)))
and the decreasing, nonnegative function f IR. - R2,
log +x-1 0 0<r<1 x 1>
[(x)
0
Lemma 3.1 (Basic KL Lower Bound). For all measurable B C θ and coreset weights w, KL(w) 2 f(JB(w)) 2 0.
where
SB To exp [ Lw) + V VBo)..
(p = Vs mo exp(() J mo exp(lw)
Note that while the integrals in the fraction denominator in JB (w) range over the whole θ space, further lower bound on KL(w) (w) can obtained by restricting their domains arbitrarily. Also, crucially, the bound in Lemma 3.1 does not depend on T.. (B%), which would be difficult analyze without detailed knowledge
the tail behaviour of T. 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 Ey can be used), π concentrates on B (so that क (B²) Re 0), and iT and Th very different when restricted to B: the behaviour of the bound in this case is roughly (see the proof in Appendix A) [w)) & - log(1 1 TV (T, Tw))). Finally, note that Lemma 3.1 remains valid if one replaces l., with L. and with é c' for any constants c' that do not depend but may depend on the data and coreset weights w.
For the remainder of this section, consider the setting where θ is measurable subset of Rd for some E fix some Og E O, and assume each f,, is differentiable a neighbourhood 0g. Let
Wn
g VE(0o)
9u (o))
3

---

Theorems 3.3 and 3.5 characterize KL divergence lower bounds in terms of the sum of the coreset weights and the log- likelihhodd gradients 9. 9w- Intuitively for the full data set where all w, = 1 and w N, and an i.i.d. data generating process from the likelihood with parameter fo. the central limit theorem asserts under mild conditions that gu/ 2 O a rate of N- 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 gw / 2 0 occurs reasonably quickly but slower than N-1/2, while Theorem 3.5 strengthens the conclusion when 9w/" tu 3x O very slowly or not at all. The major benefit of Theorems 3.3 and 3.5 for analyzing coreset construction methods that they reduce the problem of analyzing posterior KI. divergence to the much easier problem of analyzing the 2-norm || ||2 of weighted sum of random vectors in R
Consider sequence + 0 as
+ oo, and for fixed matrix H 0
B = 60) ( 0o) - }
be a sequence of neighbourhoods around Po: these will appear in Assumptions 3.2 and 3.4 and Theo- rems 3.3 and 3.5 below. Note that throughout, all asymptotics will be taken as N - oo, 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 fo. that r + 0 slowly, and that π concentrates at Og at a usual rate. Note that Assumption 3.2 does not assume data are generated i..dd and places no conditions on the coreset construction algorithm.
Assumption 3.2. no has a density with respect to the Lebesgue measure, To(O)) > 0, each & (0) and no are twice differentiable in for sufficiently large N, and
sup BEB
(2((0) - H = (1), N
1 g N 1 -0 (N-1/2)
Nr² = w(1.
Two additional assumptions related to the coreset construction algorithm-namely that it works well enough that Σ,, wn, (0) 2 H and gw/u & 0 a rate faster than - 0-lead 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. If
sup BEB
v2 (0)
11 2
= o1),
or(r),
w
W
then
KL
min
log T (B").
Nw
9
9w
2
+ d log
(N w
N +
N
T
N max I7, 1/r2]
min (aa))))000 min 420
log T (B), log
N
9
9w
W
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 unable to make 2= P, at a rate faster than + (or perhaps 2u does not converge at we
#r all). In order to draw conclusions in this setting, we need a weak global assumption on the potential functions. function f : TR is L-smooth below at A if
L v0 θ f(0) 2 f(0)) f. (0--0))) 0b) 2 110 0
(1)
Note 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 taken at fg. Assumption 3.4 asserts that the potential functions are smooth below.
Assumption 3.4. There exist Lo.... LN. L > O such that log To is L smooth below at fo. for each [N] e, is L smooth below at G.. and N ΣN= L2 P L

---

Theorem 3,5 uses Assumptions 3.2 and 3.4 and additional assumptions related to the coreset con- struction algorithm to obtain lower bounds setting that relaxes the "performance" conditions in Theorem 3.3: En Wn, e (0) no longer needs to converge to H in probability, and gw/ to can converge to O slowly or not all.
Theorem 3.5. Suppose Assumptions 3.2 and 3.4 hold. If there exist a, 3 >> such that
P
YO B,
1 (m) = aH)
+, 1,
P
1
Σ
wnL BL2 1,
gw
up (p)r))
then
}
KL(w)) 2 (0(1))++ppp +
min log x (B"),
N min
An important final note in this section is that while Theorems 3.3 and 3.5, as stated, require choosing θ to be measurable subset of R& and that the posterior concentrates around some point of interest fg E Rd these results can be generalized to wider class of models and spaces. In particular, Corollary 3.6 demonstrates that if θ is arbitrary, but the potential functions f, only depend on through some other function
- R2, 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 e, (n))) for some measurable function dj - F. Then if the assumptions of Theorems 3.3 and 3.5 hold for potentials (f,, (L.) as functions Rd and pushforward prior 1yto Rdd, the stated lower bounds also hold for min (K[(T|| (T(w=ll=)).
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 setting where the data Xn arise an i.i.d. sequence drawn from distribution v, E, (m)( = log p( x.. (0)) for 7) θ + gd, 1oo = m70)), and the following technical criteria hold (where E denotes expectation under the data generating process):
probability
(AI) E (mo) = 0 and H/ = E | v (no) = E
0.
(A2) EE (1o) 12+1 for some ô and IE [mv)) 00.
(A3) On neighbourhood of 1oo | V (no) V R ((X,,, ,,)1 nol12. IE [R(X,)) < co.
(A4) 7app is twice differentiable a neighbourhood no. and ा (7o) > 0.
(A5) For all r such that 2 (log N/N), log no. > r) (Nr3)
These conditions apply to wide range of models, e.g., unidentifiable, multimodal location model posterior with heavy tails on θ R, where the Bayesian model specified by
0 Cauchy (0,
(X, N id
CouchyyO2,11
(2)
and the data are generated from the likelihood with parameter 0g = 5, and an unidentifiblle logistic regression posterior with heavy tails on IR2 where the Bayesian model is specified by
Cauchy (0,
Yn ind Bern
1 1 1
(3)
1 1+e - A0
the covariates are generated via X,, id (n E IR? ||ا|| S 1}), and the observations Y, are generated from the likelihood with parameter 0g [1 6)" 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.
5

---

Log 2040011 donets
-10
100
-35
-50
-25
3.0
30
-00 -15
-12
(b)
Figure 1: Example unnormalized posterior densities given 50 data points for (Ia) the Cauchy location model and (1b) the logistic regression model. The orange and blue dashed lines in (1b) indicate one-dimensional slices that are shown in the rightmost panels.
Algorithm 1 Importannc--wiighted coreset construction
Compute probabilities (Pn) (may depend on the data and model)
Draw I,,...; IM iid (attgoricallp1.... P.N For each n,, set W/ Mp. >M -m== 1T n.). return (w,)
Algorithm 2 Scaled importance-weighee coreset construction
Obtain coreset weights (wn), ) via Algorithm
Compute a = arg min,20 (I(Tawllm)
return (a" (,,w)
4.1 Minimum coreset size for importance-weighted coresets
A popular algorithm for coreset construction that has appeared in a wide variety of domains ..g..
Bayesian inference [32, 33, Section 4. 4.1], frequentist inference (e.g., [41 (41-45)), and optimization (see [46] for a recent survey) involves subsampling of the data followed by an importance-weighting correction. The pseudocode given Algorithm Note that [[[s,] coreset potential is an unbiased estimate of the exact potential. The advantage of this method is that it is straightforward and computationally efficient. the sampling probabilities are uniform Pn. i/n, then Algorithm constructs coreset in ((M) time and ( memory. Nonuniform probabilities Pn. require (2(NV) time, as they require a pass over all data points to compute each pa. [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].
and so [R[[,]] = 4; the
Corollary 4.1 explains these poor results: Bayesian coresets constructed via Algorithm must satisfy M x N in order to maintain bounded (I(w)) in the data-asymptotic limit. In other words, such coresets do not satisfy the desiderata Section The only restriction is that there exist constants C > 0 such that for all N E N, the sampling probabilities (px) ) satisfy
(A6)
0 < c min Np.. S max Np.. C < 00 0.S.
The lower threshold ensures that the variance of the Importance-weigghee log-likelihood is too large, while the upper threshold ensures sufficient diversity in the draws from subsampling. The condition in Eq. (4) further when it does not hold. The (pn W may otherwise depend arbitrarily on the data and model.
major restriction, in the sense that performance should deteriorate even
Corollary 4.1. Given (A1-6), M oc, and M oNN), coresets produced by Algorithm satisfy
N
KL (w) = 2p
(5)
M

---

The intuition behind Corollary 4.1 is that both the true posterior and the importance coreset posterior are asymptotically approximately normal with variance x 1/N as N - oo; however, the coreset posterior mean is roughly x M 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 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 small amount of effort "correct" the importance-weighteed 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 bounded KL divergence as N - xC.
Corollary 4.2. Given (Al-6), M - oc. and M = o(N), coresets produced by Algorithm satisfy
N min (aw))) = Sp log M) a30
Fig. 2 provides empirical confirmation of Corollaries 4.1 and 4.2 on the Cauchy location and logistic re- gression models in Eqs. (2) and (3). particular, these figures show that the empirical rates of growth of KL as a function of N closely matches Spp N 17 for importance-weighted coresets, and Ry (log 37 for the same with post-hoe scaling, for wide range of coreset sizes M flog N, vN 1/2NJ. Thus, importance weighted coreset construction methods do not satisfy the desiderata in Section 2 for wide range of models, and alternate methods should be considered.
4.2 Minimum coreset size for any coreset construction
This section extends the minimum coreset size results from importance-weighhee schemes to any coreset construction algorithm. In particular, Corollary 4.3 shows that under (A7)-a strengthening of (A3) and Assumption 3.4 (A8) independent a.s. and satisfy technical moment condition-at least d coreset points are required to keep the KL divergence bounded as N + co.
asserts that (7,)), VlM (no) are linearly
(A7) Assumption 3.4 holds and there exists y > such that for all sufficiently large N N,
Vn E B, n E [N],
-v) č yH and L > -
(A8) For all coreset sizes M < d, there exists 8 such that
E 1(("")"")~"1) M-6 <0 G = (V)(
Vens(1o)) e RdxM
Corollary 4.3, For a fixed coreset size M < d, given (AI-5,7,8),
min WERN WERN M
KL(w) (log N).
Upper bounds on approximation error
This section presents upper bounds on the KL divergence of coreset approximations, As in Section 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(TT.) [|T), (L(T([T.)).
Lemma 5.1 (Basic KL Upper Bound). For all coreset weights w,
KL(w)= inf 1 A>D A log / / Texp((11 2) -1),
where for all E [N], e, aln E= En. and Ewp = En Enunn
The upper bound Lemma 5.1 nonvacuous (i.e., finite) as long as there exists a > such that the Rényi divergence (T (T) [49, p. 3799] is finite. Note that as in Lemma 3.1. the bound in
7

---

M-sqniNi
M-2griN
Mimlog
10
107
Misumum
102
10a
10t
102
102
104
10a
107
104
Mmsort(N) (M]
M-cqrttN)
M-+1y2
M=W2
Mmtlog
1.0
2.5
Misuuum
Minimum
10
107
10
221
107
10
201
Figure 2: aepoortance-eighheee coreset quality, showing the minimum of the forward and reverse KL divergences on the vertical axis function of dataset size for 3 coreset sizes: log N (black), vN' (blue), and 1/2N (red). Dashed lines indicate predictions from the theory in Corollaries 4.1 and 4.2, solid lines indicate the mean over 10 trials, and error bars indicate standard error. The top row shows the quality of basic importance weighttd coresets (note that both horizontal and vertical axes are in log scale), while the bottom row shows the quality with optimal post-hoc scaling (note that only the horizontal axis model, while the right column corresponds to the logistic regression model. Sampling probabilities Pa. both models are set proportional to X2, thresholded to lie between 0.1/N and 10/N.
log scale). The left column corresponds to the Cauchy location
Lemma 5.1 remains valid one replaces E, with e,. and i with e' for any constants c, that do not depend on 0 but may depend on the coreset weights w and data.
More practical bounds necessitate assumption about the behaviour of the potentials (f,) Defi- nition 5.2 below asserts that the multivariate moment generating function of (e,) is bounded when the vector is close This definition is 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 E NxN, A > O, and monotone function h RR, - R4 such that lim h(x)) (x) = h(0) 0, the potentials (en) are (h, ( -l-ssubexponential if
f (Tex(((.) s exp(h(w> Aw)).
Yu E N TT Aw 1,
Theorem 5.3. If the potentials (
N are (h, A) subexpoennna, then
Ve E R
4(w - 1)" A(w - 1) 1, KL(w) I h44(ww1W))) A(w 1)).
Definition 5.2, the key assumption in Theorem 5.3, is satisfied by wide range of models when choosing h(x)) = x and A xx Cov () as demonstrated by Proposition 5,4. Because this case applics widely, let A-subexponential be shorthand for (h, -J-ssubexpomentialitt with h(x) z. Proposition 5.4. for all in ball centered at the origin, exp((..) < co, then there exists 0 such that the potentials ( are 3 Cov ((.)) ( -subexponential.

---

Algorithm 3 Subsample-optinize coreset construction
Compute probabilities (pm) (may depend on the data and model)
Draw 4,..... IM iid Categorical(pt.... pN), and set I {I,..... IM) Compute w* = arg win KL(TTwl s.t. Wn * 0 only if E I. return (w²)x=1
In other words, intuitively, if coreset construction algorithm produces weights such that Var (P.r E) is small, then KT(w)) is also small. That being said, the generality of Defnition 5.2 to allow arbitrary h, A is still helpful in obtaining upper bounds in specific cases; see, e.g.. Propositions A.1 and A.2.
Upper bound application: subsample-optimize coresets
A strategy to construct Bayesian coresets that has recently emerged in the literature, shown in Algorithm 3, is first subsample the data to select M data points, and subsequently optimize the weights for those selected data points [36-38]. The subsampling step serves to pick reasonably flexible basis of log-likelihood functions for coreset approximation, and avoids the slow greedy selection routines from earlier work [33-35]. The optimization step tunes the weights for the selected basis, avoiding the poor approximations of ceterrtance-weightiin methods. Indeed, Algorithm creates exact coresets Tw- with high probability in Gaussian location models [36, Prop. 3.1] and mnite-dimensional exponential family models [37, Thm. 4.1], and near-exact coresets with high probability in strongly log-concave models [37, Thm. 4.2] and Bayesian linear regression [38, Prop. 3].
Corollary 6.1 generalizes these results substantially, and demonstrates that coresets of size M = Oppolyogg(N7) (N) produced by the dobsample-optimiii method in Algorithm 3 maintain bounded KL divergence N oo. Two key assumptions are subexponentiality of the potentials and polynomial (in N) growth of Var );; these conditions are not stringent and should hold for wide range of Bayesian models and i.i.d. data generating processes. The last key assumption in Eq. (6) that a randomly-chon in Algorithm 3) is well-at well-aligned with the residual coreset error function. Similar alignment conditions have appeared in past results for more restrictive settings (see, c.g., (ō) in [37, Thm. 4.1]).
potential function ε,, I ~ Categorical(pt....
PNN) ) (with probabilities as
Corollary 6.1. Suppose there exist 8. and P,e such that the potential func- tions (Ln ) are B Cov (00x(((())) ( --ubeepponna with probability increasing to I as N + co. Var (E(O)) ON(Na), M = (log N)= and
P max{0 0, Corrx ( (0), E(O) -()-)(00)33 21 - -c((6))==)) (M (6)
(0) arg min Var, (2(0) g()))
I II,..,,Ix ld
Categorical(pI......
9 s...neef -1
Then Algorithum 3 produces a coreset with KI. (w) (1) as N + 00.
Fig. 3 confirms that subsample-optimize coresct construction methods applied to the logistic regres- sion 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.
7 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 draw novel conclusions regarding importance- 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), 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-cant case analysis.
and subsamplc-optimize coreset methods, which align with simulation

---

M-5 1 2log(A)
M-5 21optki
10"3
18
Moxmmum CL
10
10"1
Maximum
10"3
10
10-1
10-1
104
Datasel size
Dataset size
Figure 3: Subsample-optimize coreset quality, showing the maximum of the forward and reverse KL divergences on the vertical axis as function of dataset size N for coresets of size + 2 log N. Solid lines indicate the mean over 70 trials, and error bars indicate standard error. The left panel is for the Cauchy location model, while the right panel is for the logistic regression model. Sampling probabilities are uniform pn. 1/N, and coreset weights were optimized by nonnegative least squares for fog-likelihoodd discretized via samples from π [34, Eq. 4].
Acknowledgments and Disclosure of Funding
The author gratefully acknowledges the support of an NSERC Discovery Grant (RGPIN-2019-0390)
References
Christian Robert and George Casella. Monte Carlo Statistical Methods. Springer, 2nd edition, 2004.
Andrew Gelman, John Carlin, Hal Stem,, David Dunson, Aki Vehtari, and Donald Rubin. Bayesian data analysis. CRC Press, 3rd edition, 2013.
[3] Andrés Christen Colin Fox. Markov chain Monte Carlo using an approximation. Journal of Computational and Gruphical Statisticx, 14(4):795-810, 2005.
[4] Marco Banterle, Clara Grazian, Anthony Lee, and Christian P. Robert. Accelerating Mestipolis-Hatings algorithms by delayed acceptance. Foundations of Data Science, 1(2):103-13 108-128, 2019.
[5] Richard Payne and Bani Mallick. Bayesian big data classification: review with complements. 165553 2014.
[6] Chris Sherlock, Andrew Golightly, and Daniel Henderson. Adaptive, delayed-acceptaan MCMC for targets with expensive likelihoods. Journal of Computational and Graphical Statistics, 26(2):434 444, 2017.
[7] Arnaud Doucet, Michael Pitt, George Deligiannidis, and Robert Kohn. Efficiintt implementation of Markov chain Monte Carlo when using an unbiased likelihood estimator. Biometrika, 102(2):295-315 313, 2015.
[8] Dougal Maclaurin and Ryan Adams. Firefly Monte Carlo: exact MCMC with subsets of data. In Conference Uncertainty in Artificial Intelligence, 2014.
[9] Matias Quiroz, Minh-Ngoc Tran, Mattias Villani, Robert Kohn, and Khue-Dung Dang. The estimator for optimally tuned exact subsampling MCMC. Journal of Computational and Graphical Statisticx, 877 2021.
[10] Welling and Yee Whye Teh. Bayesian learning via stochastic gradient Langevin dynamies. In International Conference on Machine Learning, 2011.
[11] Sungjin Ahn, Anoop Korattikara, and Max Welling. Bayesian posterior sampling via stochastic gradient Fisher scoring. In International Conference on Machine Learning, 2012.
[12] Anoop Korattikara, Yutian Chen, and Max Welling. Austerity in MCMC land: cutting the Metropolis- Hastings budget. In International Conference Machine Learning, 2014.
10

---

[13] Tianqi Chen, Emily Fox, and Carlos Guestrin. Stochastic gradient Hamiltonian Monte Carlo. In Interna- tional Conference Machine Learning, 2015.
[14] James Johndrow, Natesh Pillai, and Aaron Smith. 12%15 2020.
No free lunch for approximate MCMC.
[15] Rémi Bardenet, Arnaud Doucet, and Chris Holmes. On Markov chain Monte Carlo methods for tall data. Journal of Machine Learning Research, 18:1-43, 2017.
[16] Tigran Nagapetyan, Andrew Duncan, Lconard Hasenclever, Schastian Vollmer, Lukasz Szpruch, and Konstantinos Zygalakis. The true cost of stochastic gradient Langevin dynamics. /706:/700..02200 2017.
[17] Jack Baker, Paul Fearnhead, Emily Fox, and Christopher Nemeth. Control variates for stochastic gradient MCMC. Statistics and Computing, 29:599-615, 615,, 2019.
[18] Christopher Nemeth and Paul Fearhhead. Stochastic gradient Markov Chain Monte Carlo. Journal of the American Statistical Association, 1 1666533)433--550 2021.
[19] Matias Quiroz, Robert Kohn, Mattias Villani, and Minh-Ngoc Tran. Speeding up MCMC hy efficient data subsampling. Journal of the American Statistical Association, 114(526)8831-853 2019.
[20] Matias Quiroz, Robert Kohn, and Khue-Dung Dang. Subsampling MCMC-an introduction for the survey statistician. Sankhya: The Indian Journal of Statistics, 80-A:S33- S69,,9999900 2018.
[21] David Blei, Alp Kucukelbir, and Jon McAuliffe. Variational inference: A review for statisticians. Journal of the American Statistical Association, (3X51188859-877 2017.
[22] Zhenming Shun and Peter McCullagh. Laplace approximation of high dimensional integrals. Journal of the Royal Statistical Sociery: Series B, 57(4))749-760, 1995.
[23] Peter Hall, Tung Pham, Matt Wand, and Shen S.J. Wang. Asymptotic normality and valid inference for gaussian variational approximation. The Annals of Statistics, (955)2502-22532, 2011.
[24] Aad van der Vaart. Asymptotic Statistics. Cambridge University Press, 2000.
[25] Yixin Wang and David Blei. Frequentist consistency of variational Bayes. Journal of the American Statistical Association, 1 114(57))1147-1161 2018.
[26] Badr-Eddine Chérief-Abaellatif and Pierre Alquier. Consistency of variational Bayes inference for
estimation and model selection mixtures. Electronic Journal of Statistics, 12:2995-3035, 2018
[27] Yun Yang. Debdeep Pati, and Anirban Bhattacharya. a-variational inference with statistical guarantees. The Annals of Statistics. 2018.
[28] Pierre Alquier and James Ridgway. Concentration of tempered posteriors and of their variational approxi- mations. The Annals of Statistics, 48(3):1475 1497, 2020.
[29] Zuheng Xu and Trevor Campbell. The computational asymptotics of Gaussian variational inference and the Laplace approximation. Statistics and Computing, 32(63), 2022.
[30] Jeffrey Miller. Asymptotic normality, concentration, and coverage of generalized posteriors. Journal of Machine Learning Research, 22:1-53, 2021.
[31] Cheng Zhang, Judith Bütepage, Hedvig Kjellström, and Stephan Mandt. Advances in variational inference. IEEE Transactions on Pattern Analysis and Machine Intelligence, (188):2008-2026, 2019.
[32] Jonathan Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable Bayesian logistic regression, In Advances in Neural Information Processing Systems, 2016.
[33] Trevor Campbell and Tamara Broderick. Automated scalable Bayesian inference via Hilbert coresets. Journal of Machine Learning Research, 20(15):1-38, 2019.
[34] Trevor Campbell and Boyan Beronov. Sparse variational inference: Bayesian coresets from scratch. In Advances in Neural Information Processing Systems, 2019.
[35] Trevor Campbell and Tamara Broderick. Bayesian coreset construction via greedy iterative geodesic ascent. In International Conference Machine Learning, 2018
[36] Naitong Chen, Zubeng Xu, and Trevor Campbell. Bayesian inference via sparse Hamiltonian flows. In Advances in Neural Information Processing Systems, 2022.

---

[37] Cian Naik. Jucith Rousseau, and Trevor Campbell. Fast Bayesian coresets via subsampling and quasi- Newton refinement. In Advances in Neural Information Processing Systems, 2022.
[38] Martin Jankowiak and Du Phan. Surrgatte likelihoods for variational annealed importance sampling. In International Conference Machine Learning, 2022.
[39] Naitong Chen and Trevor Campbell. Coreset Markov chain Monte Carlo. In International Conference on Artificial Intelligence and Statistics, 2024.
[40] Thomas Cormen, Charles I Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 4th edition, 2022.
[41] Ping Ma, Michael Mahoney, and Bin Yu. A statistical perspective on algorithmic leveraging. Journal of Machine Learning Research, 16:861-911, 2015.
[42] HaiYing Wang, Rong Zhu, and Ping Ma. Optimal subsampling for large sample logistic regression. Journal of the American Statistical Association, (3352)))82--844, 2018.
[43] Yaiging Wang. More efficient estimation for logistic regression with optimal subsamples. Journal of Machine Learning Research, 20:1-59, 2019.
[44] Mingyao Ai, Jun Yu, Huiming Zhang. and Hai Ying Wang. Optimal subsampling algorithms for big data regressions. Statistica Sinica, 31(2):799-77, 2021.
[45] Hai Ying Wang and Yanyuan Ma. Optimal subsampling for quantile regression in big data. Biometrika, 108(1):99-112,, 2021.
[46] Dan Feldman. Introduction core-sets: updated survey. arXiv:2011.0955 2020.
[47] Alastair Walker. New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letters, 1078):127-128, 1974.
[48] Alastair Walker. An efficient method for generating discrete random variables with general distributions. ACM Transactions Mathematical Software, 3(3):253 256., 1977.
[49] Tim van Erven and Peter Harrèmos. Rényi divergence and Kullback-Leible divergence. IEEE Transactions Information Theory, 60(7):3797-388 -8200 2014.
[50] Roman Vershynin. digeesdimessonnll probubility: an introduction with applications in data science. Cambridge University Press, 2020.
[51] Igor Vajda. Note on discrimination information and variation. IEEE Transactions on Information Theory, (6(6):771-73,3 1970.
[52] David Pollard. A user's guide to probability theory. Cambridge series in statistical and probabilistic mathematics. Cambridge University Press, 7 edition, 2002.
[53] Robert Keener. Theoretical statistics: topics for core course. Springer, 2010.
[54] Andre Bulinski. Conditional central limit theorem. Theory of Probubility its A111) 2017.
6344:633363,,
[55] Lorraine Schwartz, On Bayes procedures. Z. Waduxchheiniickketttheeeee und Verwandte Gebiete, 4: 4:10-26, 1965.
12

---

A Proofs
Proof of Lemma 3.1. By Vajda's inequality 151],
KL(w) 2 log + (T, aw) (TT(T, nw)
TV Nw)
1 (T,
1V log (1 - [V Tw)) TV(F,
2V 0.
The hound is monotone increasing in (T, Rw): therefore hecause the squared Hellinger distance satisfies the incquality [52, p. 61].
H² (T, 1 / (V= - v= S / - nul (V Tw),
we have that
KL(w) 2 - log (1 (T,, mw)) - (T, aw).
We substitute the value of the squared Hellinger distance to find that
KL(w)= 2 - log (f V (VTTTL))
VTw
122
Note that f ViiT S 1, so
KL(W) (w) 2 - log min(1, / VTTTe)
min(1,
//Rw') 12 0.
The bound is monotone decreasing in VTTw so we require an upper bound on VvTw To obtain the required bound, we split the integral into two parts one on the set B, and the other on B and then use the Cauchy-Sehwars Schwarz inequality to bound the part Dº Note that definition and mutually dominating. the density ratio Fw/ is well-defined and measurable.
B
Tue
B
v nm
T (B3)
I To exp (E - Ew)
+ v ((=)).
exp(E) f no exp(lw)
The result follows.
Proof of Lemma 5.1. We first consider the forward KL divergence. By definition,
/ (le e.) + log
To exp((ew
<L(>||=.)
TTo exp(())
/ (e - (w) + +lo Texpllw- E).
Since the KL is positive, for A O,
(L(T||TT)
1 A
/
xle (w)) 1+
x log xoss/eesee Texplla- (
1 1
f x(e (w) log f I mexp((l N)(ww - E))
< X
1
/ exx(((1 + x)(E -1),
log
by Jensen's incquality. Next consider the reverse KL divergence, For any À + 0.
S no exp(()
KL(TullT)
Tw + log i no exp((w)
3// Ner((eu log Texp(Co E).
13

---

By Jensen's inequality, for A > 0.
Tw exp(A(Ew 0) - log / Texp(ew -
[L(Tw||a) < X
log
1 log
S x eexp((1 + 1ew - 0) log Texp(ee - 2)
= A
Teexp(eo - 2)
1
T eexp((1 + Alwwu -)) 1
X log / xexp(lu - 1)
=
log
+
x(l - (w) + log / a Texp((1 + 1)w -()
S
= X log f x eexp((1 A) ())-
This is the same bound as in the forward KL. divergence case. Since the bound applies for all À > 0, we can take the infimum.
Prouf of Theorem 3.3. By replacing the integrals over the whole space θ in the denominator of Jn(w) in Lemma 3.1 with integrals over the subset B.
KL(w)= -log min(1, Js()) min(1, -
2 (1) - log (w)
(1) min GB(w), - log VIBB)
Gn(w) log J. ho (1)))())))(())))))))))))))))))) + Em + 2 log S no exp(E)
2 log no exp(Lw).
So to obtain the stated lower bound on the KL divergence, require upper bound on log Se exp((1/2) tw) and lower bounds on log fn No exp(E) and log fg no exp(lw). By Taylor's theorem, Assumption 3.2. and the assumption on 2L (0), for all 0 E B,
(()) ((fb) - 9² (e 0o) +
N (0- 0o) H( 0b)
Nop
(0 (0-0u)" 2 H 0a)
2
(7)
(0) em (0,) o 0o) + 2
v 10 0o) H - 0o)
< 1o, (1) (0 0n)² ( 0o).
2
We shift the exponential arguments in (n(w) by (1/2)(((0)) + (00)) note that no is continuous and positive around Oo, and and apply the Taylor expansions in Eq. (7) to obtain upper bound on the first term:
log mee (0-((())
< O,(1) log d (lotow)" (0-80) I-NNI (0-0g)" H(0-0g)
where (~ denotes a quantity that converges in probability as N + co. We can transform variables to C² (0- 0o), where H CC" is the Cholesky factorization of H, and subsequently complete the square:
log / Tue ( s 50p(1) + (~1)][(-- (gg + 9=)l 4(N + w)
(AXN+ m)
(o (N+
+ log
B
(8)
We can obtain lower bounds on the other two terms using a similar technique:
/ mOe (-e(0o) 20((1) (~11)IC 99l2"
(<)) |-- (11g 2, 20/2
log
log
2N
noe la (90) > 0,11) + (~ 1)l(c- 11 B
log
(80)
+ log
(10)
2
It remains to analyze the three log f terms. We bound the integral term in Eq. (8) with the integral over the whole space:
log /
(AANN 11...1 S0,(1) loggNN + w).
For the integral term in Eq. (9), note that since N = w() and [C - (2222, we have
(<1) !I...!?
log
|
14

---

log
14 (..)
||
(wijc- e|l
1=1|2202
log
(~11)2m
4/2
|x
/
لويل is- (odse to 12
NV
[~^1)2m
4/2
Pp(Nr
((~1)dT NV
4/2
log
NV
(Ng + Op(1).
2
the integral term in Eq. (10), we consider two cases: one where large, one where small. First assume wr > Sd log 2; then by a similar technique as used in the first lower bound, since ||C gu/ gu/Wil (r)..
(mdkm I!...1?
log
|01|gr2
~ 1)2TT
d/2
(~1)
min
/
(-13 12- (-1)0- (o1)0-1ow sw 1
> log
a
log
(~ 1>2m
d/2
-2d log
(~~ (~1144m
d/2)
d log w + O1().
When wr I 8d log 2, transform variables y 2/r to find that since ||C Tu gw/wil (r()..
log /
(m4)
11..11
d
logr 22
log 111
fnijer?
(- lou
vinl
2
to 2(-1)
(2+
( 2ow 11)
(Aurea)))
2 2
log r loge
2 log x² Op(1).
Therefore regardless of the value of w.
log |
(-1) 1...11
log Moggmaxfus (0,11/2)) + Op()).
So therefore combining all previous results,
GB(w) 2 +,(1) (~1)
gll
|C gu 11
(g 10-
gm )1
(N m)
log N max ( 17 1/r2)
N
(~1)
@ =/l²
N NIC
9wll 12
2g" H
(N + w)²
= =0,(1) +
log N max ( (T, 1/r*]
N(N + ())
( + 17
N + w
0,((1) + (~1)
Nw
C-1 9
C Ow
d log
(N + 7)
4
N + w
N
4
N max 1/r2]
(,(1)+0,p00
Nw
9
Iw l|
(N + m)² d dlog
N
N
N maxx (0, 1/r3)
We now consider the minimum over 2 0. Since neither (p()) (1) above depends on W. we have that
Naw g N a20
9wr ||
(N + axw) d d N m 1/r2)
min KL(aw)= 2 (p(1) + (,(1) min a29
log T (B"),
min
N + aw
On the 1/r branch of the objective function, the derivative in is always positive, and hence the minimum
occurs and
min(....) 2 dlog(Nr?)). <20
On aw branch of the objective function,
min Now
Su 2
+ dlog
(N + au7)
min
Naw
g
Fw |
d d
(N
+ d d N.
N + oz
N w
Naw
N + am N
Naw
15

---

For a, b > 0 and x 2 0, the function az b log is convex in with minimum at x" = b/a, and so
min(- ... 2 dl dog N a20
By assumption, | = (p(r)
and Fe
= Op(r). and henee the ouw branch has the asymptotic minimum:
min KL(aw) 2 0x(1) (2( min a20
log ((B)),
N/
9- [²)}
Proof of Theorem 3.5. By Lemma 3.1,
KL(w)= 2 log min(1, J (n)) min(1, (w:)
2 0p(1)) + min (omin(Ga(w)) Gn(()), log / (B=)}
1
2 log / To exp(e) +
Gs(w) - -log To exp((11 ew)) +
2 log exp(Lw).
Note that Gy in this proof subtly different from the GB used in the proof af Theorem 3.3; the latter two integrals are over the whole space (directly from Lemma 3.1), rather than We shift the exponential arguments in Gn(w) by (1/2)(((06) + (0o))) We first provide lower bounds on two of the integral terms via Assumption 3.4:
log
noe (r(0b) 2 O,(1) + log
((0t00) (10+a))"(0-0p) 00)- LONN+DE ||0-8011
where (~ 1) denotes quantity that converges in probability to 1, go V VlogTo(00) and 1 NL. Transforming variables via r = (' 0u).
N+1
log moe (-(0)) 0,(1) log
( (00t Fa/LL
(M41N+11]
04-00 (N+150
0+.00 (N+1)6
=0,(1) + log
= -,(1)+ (~1) + +1)
9
d log(N + +1)
2L
N N+11
2
2 0,(1)+ (~ 1)(N + 1)
g 90
d log(N + 1).
max L2 [g]
++1
Let 122 1 -,, Wr, 12 Using the same technique, with L
5L 1 1-1
and 1' 0o).
10
log / (wollo))( log (o0 (-))-1) 1010-0011
+
Iw + 90
0p((1)
log
11+1))0
21
+
20,(1) + T7 11
Iw + 9o
Sue Lg
log
(m+
2L
+
1)
= -0,(1) + 10 +
+ 9o
d log( a + 1)
2L
T7 +
2
w #+1
Im0 + 90 d log ( + 1).
2 01)) +
2 max L3)
+
2
For the upper bound on the first term, we use a local quadratic expansion around do, where Ho - 2 log (o()))
log The t1- (oo)))) < s0, log e (00 (-XX To) (N (N+ommll-aR) (0-00))
Because H > we have (N + at) 2Ho eventually; can transform variables to r CT (0 6o). where (N+aw)H42H5 CCT the Cholesky factorization, and subsequently complete the square. Note that N46+2
mmin(a, 1) H, AminnHof & Amin S Amaxe //aa maxx(a 1) H, Amn
16

---

log = =
Amin 0 HC-²3 O
d Amin H
7) > 0,
max(a, ) H, Amax
and therefore
log / Tue (..))
1
0x(1)+ [NI((N+++
CT + Iw + 2gu)
|
[x1)(+++2])
+ log
Nio
4
N Φ +
||x (2gr2
(1I)
Suppose first that @ + 1 S N/(44CC=11 ( L.}). In this case we bound the integral in Eq. (11) by integrating over the whole space:
log S/ Tee tl..) S (00(1)+
(I 1 +
g + gw + 2go
log(N
2).
4
N
+2
2
Combining this with the previous results yields
Ga(w)= 2 Op(1)
(~ + 0 + 2)
||-
9 + 9 + 2go
N 2
d (N + Φ 2)²
W +
Gw 90
(N + 1)
9 9 00
+ log
4 (N + 1)(w 1)
4 max B12,, Lg)
4 max (L2, L3)
N +
(N 1 + 2)
1 +
9m + 90
2| ( + 1)
2 (p)) + 4 log
(N + 1) + 1)
W +
max m 1g)
+ w +2
(N + 2)²
go + 90
2 00p1))+ log (N 1)( + 1)
max [.]]
+
Bounding the last term below by minimizing over w such that v S VN yields
Gs(w) 2 0p(1) + log / = 0,(1)+ log N.
Bounding (N +7 2)/(N 1) 2 and minimizing over such that v N yields
W7 +
9w + g0
GB(w)= 2 (1) log .
log( iT + 1)+
3max{BL2
L3)
1
0,(1) log .V
d
gw go
+
0, log .V
9- W
where the second line follows because for a, > O and x 2 0, the function or blogar ar is convex in with minimum at xx b/a. Therefore for w 1 N/(...).
(L 2 (1) + (1)dlog N Wiin
Next suppose v + 2 N/ (312 LE)). A second upper bound on Eq. (11) can be obtained by
taking the maximum of the integrand over the integration region ||0||| < r². Note that since llg | = up (p(r).
w = (N,(NN). g/N ONNN11/2) and N, (1) we have that [] + Iw + 2go)/(N + w + 2) = (p))), and so
(..)
log
0,(1)) + (~1)(N + 17 +2)
C- + gw 2go)
(~ +2)
(1
( (g + gw 2go)
-r)
+ log x
N +2
=1,(1) (N + w +
(~ ()V + w + 2)r
C-1 (g + + 2go)
+ d
log 2.
4
N w 2
2
So therefore combining this result with the previous bounds and minimizing over yields
Ga(w) 2 O,(1) + (~1)(N w 2)22² (~ क + 2)r C- fr 2go)
4
2
N N 4
17

---

d
log((N 1)( 1)r")
+ 4 4max Lg) -r)
17 +
9e + 90
+
(N +
g 9+ 90
4 4max L2 [g]
N +
2 O₂(1) 1og(N>>
[~1)
log log(ur (wrr))
(~ 1)
d (₂(1) log( (Nr²) d
(w1) Ny
d
log(r") )+ + d
log
d
77
(1) + log N
Dw
Combining with the earlier bound and noting that N (1min (p(1) yields the final result.
Proof of Covollary 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.
KL(w)= S inf log / a Texp((1+
2)(Bw E)
inf log Texp(((442(0-11) A>
Since (kn) are (f, (ubx) subexponnnnnt if
(w= A)F
A(w - 11 1,
then
f π eex((f S exp [((1 + 2)2 - 11 A(w 1)))
By assumption, the condition holds when À 1; the result follows.
Proof of Proposition 5.4. Let ((w) log π exp((=)) By the finiteness condition, [53, Theorem 2.4] asserts that C(w) is continuous, and has derivatives of all orders that can he obtained by passing differentiation through the integral within the set ||w||2 < a. Let U Cov. ((E.) and S spanfw Rx w" ( = 0 r-a.s... Note that = ker U: since w" Uw Var, (L)) w" Uw = 0 if and only n-a.s.; and since is symmetric positive semidefinite, w" Uw if and only if ker U.
w ""'(E, ((E,) Therefore ((w) is continuous, has derivatives of orders, derivatives can be passed through the integral within the set {w RN
|| a/2, u ker U}. For vector E ker U, and minimum positive eigenvalue X+ U,
1 ker U,
"Uw- a A+
-u x+ - 1ola S
Cww) is continuous, has derivatives of all orders, derivatives can be passed through integral within the set (w E R u² Uw s UUw
e²²1). ). By Taylor's 'sssss theorem, for any in this set, there exists distribution with density proportional to v exp(fur) for some w' on the segment from the origin to w such that
C(w) log f exxp(e=)
1 w/'"UU U Bnw (w" (()))
By definition of vie w E ker implies that w/ (E,) 0 a.s.. and hence Bn (ET) Therefore, for TT UU S u²
1 Uw
1 Emy [(w (i (E
((w) < z
Uw
1+
max to Uwi Ax wil 1f
6
W
1 1|/0||2 [all|||Enn (((a) (fa) @ (1m))
1
< w
Uw
1+ max
[[wllaS $ 6
A+
< w
1
UUw
1 + 12x
max |
Ban (Pa) @ (T.) @ (2))
where @ denotes outer products to form tensor. By continuity of derivatives of all orders within the neighbour- hood ||ll| a. the result follows by selecting sufficiently small
L
18

---

Proposition A.I. Suppose there exist E R, à > 0, and 0 < < 1 such that i S e and for all coreset
weights satisfying aw" Cov, ((e,((e))))) ((e.))==) 1)) I 1. ful ele
6. Then the potentials (f, ) are
(h, a ((en((()))==))) ))oo:((l)aaa))ssseeeeeeeeen subxxxxobbbxxiittalll..... with h(x) a ageer
Proof of Proposition A.I. A.I. Let E' = =t-c. c. Since E' s 0 and
|1ol S c|6"| + ó for some e < <1,5> 0.
f x Texp((n)= = =1 x(t,)²+
( 2(1-22) (10))((00))
k!!
s1+ T(Oo)²+ )² +
[e|e" + 8) 2 | 1 ((1-c)
k!!
kmd
=1+ / T((6)) + 7
c111++ (cle" + +8) [0e/e1 8)2
[ 2(-0))
(c(8) + 8)2(1-1)
s1+ 2
x((o))+ +
(e 2(1-))
=1+ / I((o)² + [ -)) 4 1 (2(--))
1
I((a)² 400 (S Txve" 1em 12) 1-c
P)
1
s1+ 2
S "ooee"
- -1+ 2 / (le))² +o (mmee") (((le)))) i-
-1+ 2 T((a)² + s (frodt (( (sxt(a))
expp li(w" Cova())w)).
where h(x) = 2
x
Proposition A.2. Suppose ④ = Rd, È G-strongly concave, and there exists I, < G, a >>>>0 O, and Og E θ such for all coreset weights satisfying aw"" Cov, Cov,((E.) ((v.((EE) S 1, En is L-Liscchitz smooth, and both [[)))( |I and (0o) are bounded. Then for any (L/G) < c 1, there exists e E R. ô >> such that the potentials (fn) are (h, Cov Covx((En)) b sl-e))))bepoooentii with the same h as in Proposition A.I.
Proof of Proposition A.2. Since E is G-strongly concave and Ew is L-Lipschitz smooth, we write
G
E(O)= - E(Ou) + Ve(00)) (0- 0o)
110 0ull
2
E(()) - || G 'V((6))
2/4
G
||0
Po - G -
[e)) / (0)) + Ven (0 0b) 0 0ol 2
So setting E(oo) + - (V((0)) /| implies { is nonpositive function as required. Then
IT. - <(E(0) 12 (0o)) + 2G |VE(0))] ++((()))) (I. + <| Doll L-cG cG 110 0011
For < a < G L. setting
Lta a
and then maximizing over || Gull yields
(0)) <|((0) el (0b))
[ vi. (8)) || | [ -oll a 210 1
2G
|V((0))1 + (I (8.)
+ < ( 2a
S (00) 2G
By the boundedness of (96) and (f., maximizing over w yields a value of < oc.
Lemma A.3. Let X1, X2,... be i..dd. random variables in R with R.X,, 0, and define the resampled sum
Ma X
SN
Mp
n=1
19

---

pN)). }}. with strictly positive resampling probabilities pi....a that may depend XI.... A...... XN and N. If there exists a 5 > such that N oc.
where (M....., Mx) Mulli(M, (pi..... .......))))))).......)))
(Np.)t+ Op(1),
[x,
1
Σ
x
S2((1,,
and M - co.
N
Npr
then
SN Σ Xu 4 N0.
M
N
N Σ Npa
Proof. We can rewrite
1 M
M
Xim
SN
Pr..
where Lm id Categorical(pt..... ,PN). Consider SN + BN where By is independent of Sv. Bx = =1 with probability UNMM)=T and BN = 0 otherwise. So if we set AN .x........,,,. [54, Cor. 3] asserts that
SN + BN ESS AN]
1(0,
N 00.
(NM)-(142) Var SN AN
as long as for all N large enough,
1 Xim |AN
Var
< x a.s.,
M prm
and as N + oo,
(M (1+5) + Σ m
E
Xim
E
Nsm LAN
245
|AN
M Pim
N7
300
((NM)
Var [Sx [Sx|AN)) (2+6)/2
Note that the conditional mean and variance have the form
XIm
E [Sv [AN] = E3
LAN
= Σ Xn
pmm
Var [SN [SN|
Var
Xim
An
1
Σ
Pn
Xn
Σ
Xn
M
pim
M
Pn
n
which implies that Var implies X., is finite almost surely. Next, note that
Xim
[Av]
a.s., since PI..... px are strictly nonnegative and E.X,,
3I Pim
(NM) (1+4) + EM
1 Xim XI plm
Nim
|An]
224
IAN
N7 Pim
(1+5) ((NM) (1+6) + Var (N][AN))(200))
(NM) (1+6) + 22-6 EM E
Xim
124
IAN
+ Σn X, 240
Ptm
((NM) (1+6) -(++) + Var [Sw] [AN)) (248)/2 (2N))22+))/2
M (3+2))) + 22+6 (1 Σ,
[X, 216
Xn
Xn (24))
(Np.))+z
(M-NN-334 N Σ. X2
E. (2+6)/2
Npr
The above expression converges in probability 0 by the technical assumptions in the statement of the result well the fact that N Σ. X,, " by the law of large numbers. Once again by the technical assumptions. Var [SN AN]] = 2p (N² so
Var [AN] (NM) (1+5) + Var [SN]AN]
Bx (NM) (NM)- (144)) + Var [SN]AN]
300
and hence by Slutsky's theorem.
SN E [NN[AN 1
N 00.
Var [NN[AN]
Using Slutsky's 's theorem again with 1/ Σ. Xn E. and rearranging yields the final result.
20

---

Lemma A.4. Suppose coresel weights are generated using the importance weighted construction in Algorithm I. Let V((p)) 9 (110) and H - E[ (11)] If conditions A(1-3) and (A6) in Section 4 hold,
M N)), and M- w (1). then
N 1 0 (N-1/²).
9w 87 = 0₂ (M
W 4 N
1,
and
1 N
1 v(((n) H
2 0.
1 Vee (1)
2 0.
sup 1
sup I1 10-
w
Proof. First, since w
En
Ma. Myn.
Ru N, and
Σ (MNDNN) )
N²
E
M
N²
Σ ((NDD) + Σ ((Npa) 1)((NDw)) -1)
M
mpttn
Σ Eu/NN-pil p.)))
N
Σ((Np))) -1 1)
M
Σ Pa (pn - -N3*
M
max(p=) N))2)
M
2²
O(1),
M
where the last line follows by assumption A6. Therefore by Chebyshev's inequality and M + 00, W/NN 4 1. Since the data are i.i.d., by conditions AI and A2, the central limit theorem holds for the sum of ((,(To) such that g/ N/ converges in distribution to a normal, and hence A6, Lemma A.3 holds such that for any E Rd.
| Op-N-1)3). By conditions A1, A2, and
$ gu + Ol(
VM
E. (L))).()))
Npn
Since condition A6 asserts that C >> Np. 2 <> the law of large numbers, condition AI, and M/N 0 imply that
VM N
5 Gv Op(
Summing over a basis of vectors l,..., ...... La shows that
M
|19=112 = M(L)MM
M
9w
0,(1).
w
This completes the first three results. Next, by condition A3, for sufficiently large N such that the neighbourhood contains the ball of radius around y/o
sup I no Sr
(((()) 1 (2((T)
N
< r N
Σ R(Xn)
Lw (n)
N ve (70)
< Σ (xK(
and
E
Σ R(Xn)
= r
1 Σ
W. R(Xx))
= rE (R(X)) +0,
that have that both
vi((n)
ve((m))
2 and
1 (m)
1 (2lm(m))
30
sup Sl
sup l
N
N
N
N
21

---

by Markov's inequality. Finally, by the bounded variance in A2, sampling probability bounds in A6. and M - oc, the variances & ei (710 and n (²((m) both converge 0 N oe, and since both of these quantities are unbiased estimates of E (x Chebyshev's inequality yields the desired convergence in probability.
Lemma A.5. Suppose (Xa) are N i.i.d random vectors in R Fix M E N. M < and define
X X1 X2 ... XM] RR If there exists 6 O such that
[ 1+ 00, where denotes vector of all entries, then as N 00,
Σ Wn
min
WERY
n=
wp N
M44633 6/2 3648
> 1 [win > 0f M.
x.1.
Proof. For any > O, by the union bound over subsets of [M] size M,
N
w² x xfxxx Xw
P
min WCRN
x
P
min
S
M
WER"
w 11"T w
N
P
max min w "x" Xw 1(11 w w11) =c WERM
M
N
maxx
X²
1x"
M
4
N
p
M
By Markov's 's incquality and (M) S (eN/M)
eeV
M+0R x
min WERN
S
s
M
eNe MI M M
x)
M-1033 Setting N
yields
) M
13/2 3--3
u cN
min
N
WERN
M
The right-hand hand side converges t N co, yielding the stated result.
Proof of Corollary 4.1 and Corollary 4.2. Set (log MM-1// Then since M = o(N). M = w(1), and assumptions (A1-3) and (A6) hold, Lemma A.4 holds. Note that ||9.///]| = O,,M -1/22) positive at уuu and twice differentiable by (A4), and N₂ = N/ log M = w1) since M = o(N). Thus the conditions of Theorem 3.3 are verified. Substitution into the right term in the minimum of Theorem 3.3 yields the stated lower bound of (NNM). For the left term in Theorem 3.3, define B {11 7u)" 7 H mu) < r
cr.()) syto
Then since H 0, r 0, and y² 1/ log M wlog N/N), (A5) guarantees that log())))
22 = (N/ log M). Therefore the minimum is Q2p (N/M), and we complete the proof by transferring from KL (r) on the y-pushforward model to KL(w) on the original model using Corollary 3.6.
M13//4
Proof of Corollary 4.3. Fix the 5 0 guaranteed by (A8), and set r 674 N tr#3
Note that Ny
w(1), na is positive Mo and twice differentiable by (A4), and by (A1-3) the results pertaining ( H ||, in Lemma A.4 hold; thus Assumption holds. By (A7),
2 ||2 and sup Assumption 3.4 holds well the conditions on 1 Vhe (8) and 1 Σ. w. L2 in Theorem 3.5. Finally by (A8), Lemma A.5 holds such that
@
9w
w/p
N
#++5/2
22

---

and hence || A = up(r). Therefore all conditions of Theorem 3.5 hold. For the left term in the minimum in
M436/8
Theorem 3.5. define B = {(1 - H (1 7o) - r²). Then since H > 0. + O, and r N
32
4/4 3770
wlog N//N.. (AS) guarantees that (B) (2p(Nr2) S2p
N
For the right term,
log
gur N
22 log N
244/22 1+**
(log.N)
@
The minimum of these two is from the right term, so
KL(w) = (log N). We complete the proof by transferring from (L(w)) on the 7-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 (AI-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, A E R. R + R,, rT() = 8 and
2(Zn -1))
(T) = log ग. - log( Zn 1)² 1)
Vl.(n) = (Zn - 11)2 +
(1) 2(2nn -2
(n) 41(Zn 7)) 3) Zm)
((Zn 11)2 1)2
((1) 2n 1)3
where Z, = X,. Property (A1) holds by routine interchange of differentiation and integration. Property (A2)
holds (for any 5 > 0) because Ve, (1) and & (1) are bounded functions of and X,, jointly. Property (A3)
holds (for any neighbourhood of qu) because (n)) holds because the pushforward of Cauchy(O, 1) through r)()= 6 has full support on R... In order to verify
bounded function of r and X, jointly. Property (A4)
assumption (A5), suppose there exists a sequence of bounded measurable functions o, (2, 2N) E (0, 1] of
the data and constants c' > 0 such that for all r + 0, r² wlog N/N).
Eyo Φ. o and sup
E1, 0.) 0
I || >r
The functions d, are similar to the test functions of Schwartz [55]. Then defining p = Tytt and po nno.
p(ln noll > r) $.u(11 noll r) + (1 or) noll > r)
< Φ, Φ. ( In moll >
o + J (1 &. ( poo
(((n)) no
Using the same proof technique as in Theorem 3.3, the denominator satisfies By assumption, there exists
log e ((m)))(n)))))))))))))))))))))( po(d)) 2 --5 log N + Oz(1).
> such that
B [st]] 0( (ev-)))) = or Ople
and a c/ O such that
Emo
(1 - 1
(1)) pm
E,,(1 60)
11n-nollsr
< sup
BBy(1 - 6r)
119- |2r
Ole -NN12
/ 1 (...)= -.
Therefore μ(Inn- - null 2 r) = ( -N. + N e- -in) = O, O,(celd
(od No
and since p2
wloggN N/VV) - log p(|ln - noo 2 r) = 2 as required by (A5). So complete the proof of (A5) we
need to find suitable d,. Fix > 0, and set
N
(Z, ..., 2x)
Pmp (1Z nol 11)
Σ
1[ nol _ cr
23

---

Under Pro- Hoeffding's inequality yields
Emo 0r Se- 2,2,,
And under Ps for 1|07 - noll > r, for small cnough > 0, Pno - 1ull S 1) P,(IZ - nol S 1) 2 2er. Thcrefore
E, (7 ........ ,.,)...NN)) = Pr.
Pro (12 - nol 11
1
Σ 1 7| - 70l 5 E
N
I Pr.
PG,lZ - qul 1 1)
Σ 1|
ml 5 1 -er
Pr
Σ 1 mol 1] P2 Too 1
N
which point can again apply Hoeffding's 's inequality, completing the result.
Lemma A.7. Fix vectors Mi,-... uN in separable Hilbert space with inner product denoted a h and norm denoted II [|. Let Ui....y UM be drawn from {ui,... .... ux) } with probabilities p1..... PNN either with or without replacement (if without replacement. probabilities are renormalized after every draw). Then for all 2 0.
Σ
M
M (MM.)) )
se- (12222)))))))) )M
min 2:20
Wen Unn
11
where
e(M,e) P max 0,
|
Uhr
(u
uu TM-11
2M
S
-M-1=
arg min #Coone PM
| - u/|
Proof. First note that it suffices to analyze case with replacement, since this case provides an upper bound on the case without replacement. 0i.-.., Usr with replacement, and one without replacement. First, draw an identical vector v for both copies. On each subsequent iteration m > 1, the "with replacement" copy first draws whether not it selects vector that was previously selected by the "without replacement" copy. If it does, it draws that vector independently; it does not. it selects the same vector as the "without replacement" copy. any case, 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 2 0 is greater for that copy. It therefore suffices to analyze the case with replacement.
demonstrate this, we couple two prohability spaces-one that draws
To obtain upper bound the probability when sampling with replacement, instead of minimizing over all jointly, suppose we use following iterative algorithm. Set æo At the first itcration, we draw vi and set the weight wn by optimizing over us
} }
min Wi U1 - u1l² ||u|2 1- max O, ||0 |||u|]| Wy 20
U1
Set = WiFl, and note that (u -u-mp v1) x1 = 0. Then at each subsequent iteration k, assume the previous iterate is optimized over all nonnegative weights, and hence satisfies (u xR-1) 1) -x-1 0. We draw another vector Up, and bound the erorr of the next iterate zy by optimizing over only the weight un for the new vector ek. Then
||u rull² 22= = min
< min |uck + Th-1 ull
50
|/u 24 112 (
max 0.
(u J4 1x-1)
V 1 L4
Therefore,
P
min #20
Σ Wmn Cmn
< x ||]l1
2 PP (in least K iterations, ||r= ull? < c1| ull?)
24

---

(u 2x-1)
2 P
in at least K itcrations, - max 0.
Se
1| I1| - x사-1 1|
(u x6- 1)
2 6
E
PKEK = - max
0, 1i u xィ
KE(,)
Σ
(1-1) M
M Σ km
M
q" 9) a)
where
0, UM (u xM-1)
q = 1 max
|uuss 1|u 2M
J.M
arg min
| ull
Econne PI....
So for all 0 E K & M.
M
min
Σ
Wen Um
||u1??
Binom(M, K 1,9).
m=11
Using the Chernoff bound on the binomial CDF, for all K -15 Mg.
M
K-1 log
K-1 32q
+(1
K-1
1og
P
min
Σ
Wm Um
th ||ll
Se
m==1
(K-1)) log K-1 (M-(K-
M-(K-1)
Substituting K 1-1 M2/2 yields
1-9/2,
-2 (2-loo(()
S e
Proof of Corollary 6.1. Since the potentials are 3 (( subexponential, Theorem 5.3 guarantees that
Vi E R 43(w - 1)T Cov ((E.) 1) S 1,
KT(ww) S 4,( - 1)" Cov ((f.)))))( - 1).
We apply Lemma A.7 with vectors f1,..., Ex (in equivalence classes specified up to additive constant) and inner product between &,, Ej defined by Cov=(f,, ),). In the notation of Lemma A.7, by assumption, ||a|] (N") and q(M, e) = (M) Substituting M (log 1(1-()p)) we find that
P 4,36 w - 1)" Cov, ((e, ((..)== - 1) 2 (lg N) log N) + 0.
Combining this result with the KL bound above yields the final result.
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract 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.
Justification:
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 results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long clear that these goals are not attained by the paper.
2. Limitations
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 encouraged create 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- speciffecfiiinnnnn 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., 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, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
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, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Theoretical results are numbered, and proof' all results are included the appendix.
Guidelines:
26

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should he 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 encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in core 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.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper 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 experimental results Figure 2 and 3 are included the text. Algorithms used the experiments exist the cited literature.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making paper reproducible important, regardless 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 novel architecture, describing the architecture fully might suffice, the contribution is specific model and empirical evaluation, may necessary to either make 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 hosted model (e.g., in the of large language model), releasing of model checkpoint, or other means that are appropriate to research performed.
While NeurIPS does not require releasing code, the conference does require 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 new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should deseribe the architecture clearly and fully.
(c) the contribution a new model (c.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 (c.g.. with open-source dataset instructions for how 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.. registered users), but it should be possible for other rescarchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions faithfully reproduce the main experimental results, described supplemental material?
Answer: [No]
Justification: There are no new algorithms presented in this work; the experiments involve only existing methods for which public code available. The code not central the contributions of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines guidder/Codeeubbieessooolo..... for more details.
27

---

While we encourage the release of code and data, we understand that this might not be possible. "No" acceptable answer. Papers cannot be rejected simply for not including code, unless this central to the contribution (e.g.. for a new open-soure benchmark).
The instructions should contain the exact command and environment needed the results. See the NeurlPS code and data submission guidelines (https: /nips cc cc/public/
reproduce
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 omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/Detail
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparamcters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details needed to reproduce the experimental results Figure 2 and 3 are included the text. Algorithms used in the experiments exist in the cited literature.
Guidelines:
The answer NA mcans 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.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate informa- tion about the statistical significance of the experiments?
Answer: [Yes]
Justification: All empirical results show the mean over number of trials, as well error hars indicating standard error.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims the paper.
factors 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 library function, bootstrap. etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are of range (c.g. negative error rates). error bars reported in tables plots, The authors should explain in the text how they calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Answer: [Yes]
28

---

Justification:
These details are not important for this paper. as there are no new methods or algorithms presented claims related computational performance. However, the introduction does list that simulations were performed on desktop computer with a Core processor and 32GB RAM.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, every respect, with the NeurlPS Code of Ethics https: //erriip/ cc/puublic/hhhiccsuu.el........
Answer: [Yes]
Justification:
This paper presents a new theoretical analysis of error bounds for Bayesian corescts methods. It does not present any new methodology or data with potential harmful consequenees.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g., if there is special considcration duc to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is potential negative societal impact of this work. The paper provides new theory regarding existing methodology.
Guidelines:
The answer NA means that there is no societal impact of the work performed. the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considcrations (c.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considcrations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is a direct path to any negative applications. the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deopfakes for disinformation. On the other hand, it not needed point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms could arise when technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated relcase of models, providing defenses in addition to attacks, mechanisms for monitor- ing misuse, mechanisms to monitor how system learns from feedback time, improving the efficiency accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
29

---

Answer: [NA]
Justification:
This does not apply.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines restrictions access the model implementing safety filters.
Datascts that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
This does apply.
Guidelines:
The answer means that the paper does not use existing assets.
authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the
is used and, if possible, include URL..
The name of the license (e.g.. g.. CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g.. website), the copyright and terms of service of that source should be provided.
assets released, the license, copyright information, and terms of the package should he provided. For popular datasets, paperewi thcode. com/dataset. has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's
creators.
13. New Assets
introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Are
Answer: [NA]
Justification:
This does not apply.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/mooel as part of their sub- missions via structured templates. This includes details about training. license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
This does not apply.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
30

---

Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least minimum wage country data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does 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?
Question:
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 TRB approval, you should clearly state this the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere to the NeurlPS Code of Ethics the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review,
31


Reviews:
[{"review_id": "AcVB3Uyz9b", "reviewer": "Reviewer_jwKa", "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.", "questions": "See weaknesses", "limitations": "Yes, the author(s) have addressed the limitations in the conclusion section.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "-  I must preface this review by saying that this paper is not in my expertise. However, as someone unfamiliar with Bayesian corset, I found it well-written, has a good flow, and I believe it presents very solid theoretical results.\n- The theoretical results are novel, presenting the first established lower bound for coreset approximation in the literature.\n- The upper bound of coreset approximation in this work relaxes the assumptions found in previous studies. I appreciate the author(s) providing examples of subexponential potentials in Propositions A.1 and A.2.", "weaknesses": "- 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. \n- 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$? \n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, thank you for your efforts reviewing the manuscript. We're very glad you found it understandable and interesting despite not being in your area!\n\n> 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 [...]\n\nThis is a really great question! The short answer is that the upper and lower bounds aren’t meant to be comparable. They’re tools to show whether an algorithm is working well or poorly. The upper bounds should be used to demonstrate that an algorithm is working well, while the lower bounds should be used to demonstrate that an algorithm is working poorly (much like the applications of our results in the paper in Cor 4.1,4.2,4.3, and 6.1).\n\nFor the lower bounds: essentially, you should think of the lower bounds as a “test for poor functioning” of a coreset construction. Roughly, the bounds in Theorem 3.3 and 3.5 say that any reasonable coreset construction algorithm must be good enough to well-approximate the score at the true parameter $g_w/\\bar w \\approx g/N$. We apply these results in Cor 4.1, 4.2 to show that importance-weighted coresets do not pass the test. If an algorithm passes the test (e.g., $\\|g/N - g_w/\\bar w\\| \\to 0$ quickly enough) the lower bounds don’t say much. The really nice thing about the lower bound “test” is that it makes the analysis quite simple: it reduces the problem of understanding minimum KL divergence to just a 2-norm comparison of two vector empirical averages $g/N$ and $g_w/\\bar w$. \n\nFor the upper bounds: Theorem 5.3 asserts that as long as you know the coreset construction algorithm is working at least somewhat well (  $(w-1)^TA(w-1) \\leq 1$ ), then you can bound the maximum KL divergence. We believe the upper bounds will be relatively tight in this regime, although we have not worked on a proof of this fact. The reason we believe this to be true is that the quadratic Taylor expansion of the KL divergence around $w=1$ is roughly $(w-1)^T \\mathrm{Cov}(\\dots) (w-1)$, which matches Theorem 5.3 with $A = \\mathrm{Cov}(\\dots)$ and $f(x) = x$, so the gap between the result in Theorem 5.3 and the true KL should be a cubic remainder term that decays quickly.\n\nNote that in our work we have encountered cases where the bounds do indeed coincide (ignoring constants), e.g. importance weighted constructions for Gaussian location models, for which both upper and lower bounds yield KL rates of $N/M$; but we believe these cases to be very limited and not of general interest.\n\nWe will be sure to include discussion related to this point in the revised manuscript.\n\n> In the second lower bound in Theorem 3.3, is there a trade-off between $N$ and $\\|g/N - g_w/\\bar w\\|$ as $N\\to\\infty$ while $\\|g/N - g_w/\\bar w\\| \\to 0$? If $\\|g/N - g_w/\\bar w\\|\\to 0$ faster than $N\\to\\infty$, do we end up having a lower bound that's close to 0?\n\nCorrect! Indeed, the lower bounds in Theorem 3.3 are most useful when $\\|g/N - g_w/\\bar w\\|\\to 0$ slower than $1/\\sqrt{N}$. In this case, the lower bound increases to infinity, which shows that the coreset construction algorithm is not good enough to be useful in practice. If $\\|g/N - g_w/\\bar w\\| \\to 0$ faster than that, the lower bound in Theorem 3.3 does not say anything of interest.\n\n> 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.\n\nIndeed you are right – choosing $r$ carefully is critical to the proofs. $r$ must be small enough that the quadratic log-likelihood Taylor expansions we use in the proofs are accurate, but large enough that $\\pi$ concentrates on $B$ quickly. But the choice of $r$ should not appear in the statements of Cor 4.1, 4.2, and 4.3, as it is not part of the conclusion of these results. Instead, we would be happy to put it as a remark in the text either before / after the corollary statements.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WXbzFi7ESS", "reviewer": "Reviewer_UnLw", "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.", "questions": "1. Could you please provide some discussions about whether the theories can be extended to misspecified regime?\n2. Providing formal definitions for some notations such as $\\Omega_p$ and $\\omega_p$ would be helpful.", "limitations": "The paper clearly states its limitation.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper is well-written, and the main technical results are clearly presented.\n2. The paper addresses several gaps in the analysis of Bayesian coreset such as providing a theoretical explanation for the previously-observed poor empirical performance of importance sampling-based construction methods through a lower bound on KL divergence.\n3. To the best of my knowledge, the theorems are sound and the derivations are accurate.", "weaknesses": "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). \nHowever, [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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our manuscript! We appreciate your kind words about its clarity, novelty, and significance.\n\n> The paper offers a theoretical explanation for the suboptimal performance of importance-weighted coreset construction [...] however, [the results in] [32] [...] raises questions about the effectiveness of the lower bounds in scenarios where the model is misspecified [...] \n> Could you please provide some discussions about whether the theories can be extended to misspecified regime?\n\nThis is a great point to raise! However, we disagree that [32] conflicts with our results. In fact, the results in [32] motivated our hunt for lower bounds to explain the (surprisingly poor) empirical results in that paper.\n\nThe experimental results in [32] do not consider scaling in $N$, as all experiments have a fixed value of $N$. So it is not possible to draw conclusions about the validity of the proposed lower bounds—which are all asymptotic in $N$—based on these results. However, the results in Figure 2 of [32] do demonstrate that the importance-weighted coreset construction performs just as poorly as basic uniform subsampling (in terms of posterior approximation error, Poly MMD^3), perhaps with a small constant improvement. This agrees with our Cor 4.1.\n\nThe main theoretical result in [32] is Theorem 3.2, which says that $M$ proportional to $\\bar m_N / \\epsilon^2$ suffices to produce a uniform log-likelihood approximation with $|L - \\tilde L| \\leq \\epsilon |L|$. But note that $|L|$ is the total log-likelihood function, which scales with the number of data $N$ (it is possible to improve this by centering the log-likelihood function so that $|L|$ scales pointwise like $\\sqrt{N}$). So $\\epsilon$ must be *at most* $O(1/\\sqrt{N})$ to keep the KL divergence controlled as $N\\to\\infty$, and hence $N \\propto M$ (since $\\bar m_N \\sim 1$ per Lemma 3.1 in [32]). This result in [32] is an upper bound; our lower bound proves that one cannot do better than $N\\propto M$ using importance-weighting.\n\nRegarding misspecification specifically: note that the goal of a Bayesian coreset construction is to approximate the total log-likelihood function with a weighted subset sum. While the model itself may or may not be useful when misspecified, Bayesian coreset construction (and the theory in this paper) is agnostic to this. Essentially, as long as the data are truly generated conditionally iid from *some* process, the theoretical results in our work should hold for the chosen log-likelihood function, prior, and (possibly unknown) data generating process. But we leave a careful investigation of misspecification for future work. We are happy to mention this as a limitation of the present paper in the revision.\n\n> Providing formal definitions for some notations such as Ω𝑝 and 𝜔𝑝  would be helpful.\n\nAgreed; thank you for the suggestion! We will be sure to include a brief definition of each asymptotic notation used in the paper in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Nt7EBNReEc", "reviewer": "Reviewer_vJwU", "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.", "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.\n- 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?\n- 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.\n- 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?\n- 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).\n\n### Reference\nRay and Szabo. Variational Bayes for high-dimensional linear regression with sparse priors. 2020.", "limitations": "Limitations seem well-adressed.\n\n### Other Comments:\nConsider 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.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The corollaries of the main results have consequences for the choice of method for coreset construction that seem insightful.\n- Conditions are carefully stated throughout the main text and examples are given to show that the conditions assumed in results do not exclude all interesting cases.", "weaknesses": "- 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.\n- (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.\n- (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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, thank you for your very thorough review!\n\n> Several statements are made in text that seem overly strong. [...]\n\nThis is a fair comment. We were thinking mostly of parametric models with conditionally independent data, where competing methods rely on asymptotic normality (either explicitly or implicitly) to achieve scalability. We are happy to adjust the writing to remove unjustified claims.\n\n> (Minor) I find the notation used around measures to be somewhat confusing [...]\n\nAnother good point — we were sloppy in a few places. We generally prefer the bare symbol, e.g. $\\pi_0$, to denote measures, with an argument $\\pi_0(\\theta)$ to denote density, and $\\int (\\dots) \\pi_0(\\mathrm{d}\\theta)$ for integration. We will go through the paper and make sure that the notation is consistent.\n\nFor pushforwards, we find the # notation unnecessary; we will stick with just prepending the map. But we will make notation explicitly clear in a new notation section (also explaining asymptotic convergence notation as mentioned elsewhere).\n\n> (Minor) The definition of f in Lemma 3.1 seems unnecessarily complicated. [...]\n\nWe agree and will edit this in the revision. As a very minor clarification, note that f is 0 when x >= 1, not <= 1.\n\n> Could the authors provide proof that 𝐿 smoothness from below implies Lipschitz smoothness? [...]\n\nWe believe there might be a terminology confusion here. Just in case: Lipschitz smoothness refers to functions $f$ for which $\\|\\nabla f(x) - \\nabla f(y)\\| \\leq L \\|x-y\\|$ (for twice differentiable functions, equivalent to $\\| \\nabla^2 f \\|_2 \\leq L$). This is different from Lipschitz continuity.\n\nFurther, note that the statement in the paper was not that $L$-smoothness below implies Lipschitz smoothness; it was the converse. At Line 145 the paper states that $L$-smoothness below is weaker than Lipschitz smoothness. Specifically, $L$-Lipschitz smoothness implies $L$-smoothness below trivially, because $L$-Lipschitz smoothness implies that the growth of $f$ is no faster than $\\frac{L}{2}\\|\\theta-\\theta_0\\|^2$ in *either direction for all $\\theta_0$*, while $L$-smoothness below only implies a bound on lower growth for a single $\\theta_0$.\n\nWhile responding to this comment we noticed that the statement re: strong concavity is wrong. $L$-smoothness below isn’t weaker than strong concavity, it just doesn’t imply it (or even concavity). The corrected statement should read “$L$-smoothness below is weaker than Lipschitz smoothness, and does not imply concavity”.\n\n> The authors claim that (2) and (3) satisfy the earlier assumptions, but no reference is provided. [...]\n\nYou are correct – it was not in the submission. When preparing the manuscript we did verify these properties, but felt the verification was straightforward (these assumptions are routine in the Bayesian asymptotics literature). But you’re right that it should be included, and it will be in the revision. We include a sketch of the verification here:\n\n(A1) There are no issues with interchanging differentiation and integration in either model, and in these cases it is a standard result from statistics that the expected score is 0 and the expected negative Hessian is the expected score outer product.\n\n(A2) We can bound terms both by looking at the expected Frobenius norm with a $(1+\\delta)$ power. The Hessian in both models is bounded globally, and hence the Frobenius expectation is finite for any $\\delta > 0$.\n\n(A3) The log-likelihood is 3 times differentiable in both models, so the Hessian is locally Lipschitz. Since the Hessians are bounded globally in both models, $R$ can be chosen to be bounded and hence has a finite expectation.\n\n(A4) The priors in both models are twice differentiable and strictly positive everywhere.\n\n(A5) Both models are parametric, identifiable under the $\\eta(\\theta)$ pushforward, and the likelihoods are continuous in total variation as a function of $\\eta$. The condition follows from results from Bayesian asymptotics (e.g. Lemma 10.3 of Asymptotic Statistics by van der Vaart, with conditions of Theorem 10.1 verified using Lemma 10.6). \n\nWe will add a full proof of each statement in the appendix, and add commentary in the text for readers about how to prove specifically (A5), which is the only condition that requires more than just routine derivation.\n\nUpon reviewing this we also noticed a typo in (A2) – $\\theta_0$ should be $\\eta_0$. We will fix this in the revision.\n\n> Line 191: “Nonuniform probabilities require at least 𝑂(𝑁) time and memory…”, should this be Ω(𝑁)? I’m not convinces at least 𝑂(𝑁) makes sense as a notion, since 𝑂(𝑁)includes, for example, constant time algorithms.\n\nCorrect! Good catch, thank you; this will be fixed in the revision.\n\n> 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?\n\nCorrect, an “exact coreset” is one that recovers the full data posterior. We will clarify this point in the revision.\n\n> 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? [...]\n\nIt’s a very interesting question. The general upper bounds presented in this work in Section 5 should be strong enough to achieve this, but the application in Cor 6.1 just demonstrates $KL = O_p(1)$, which isn’t enough. However, one should be able to modify the proof technique for Cor 6.1 to have slightly more stringent conditions to achieve $KL = o_p(1)$, at which point Theorem 5 of Ray & Szabo should be applicable. \n\n> Consider defining the various big-O etc notation used in a footnote or appendix [...]\n\nAgreed; thank you for the suggestion. We will be sure to include a brief definition of each asymptotic notation used in the paper in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G1iVFqGTev", "reviewer": "Reviewer_EUq5", "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.\n\nMy 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.", "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": "The provided limitations appear sensible to me.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper provides important new insights on the asymptotic performance we can can expect from Bayesian coreset approaches. It is very well written and provides good intuition about their theorems, thus facilitating understanding of the results even for readers you do not have the time or background to go through all the technicalities of the theorems. The two empirical examples are simple but provide good intuition through relating the empirical results with the theory.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your efforts reviewing the manuscript!\n\n> 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.\n\nMuch appreciated!\n\n> 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.”?\n\nGreat question. At the core, it’s because Cor 4.1 and 4.2 are based on a conditional central limit theorem in Lemma A.3. If the $p_n$ are too small, the variance of the importance-weighted sum (which depends on $1/p_n$) will grow too quickly to satisfy the CLT. If the $p_n$ are too large, the number of unique points drawn will grow too slowly for the empirical average to satisfy the CLT (consider the extreme case where there is one datapoint with $p_n = 1$; the empirical average will just be of a single data point, which of course cannot satisfy a CLT). We will clarify the writing here in the revision.\n\nAs a side comment, (A6) probably isn't strictly necessary to achieve the results in Cor 4.1 and 4.2; we could perhaps use another technique not based on the CLT for cases where $p_n$ is asymptotically very small or very large. But we found (A6) to capture all cases of practical interest and so were satisfied with it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kTatNEokBV", "reviewer": "Reviewer_2Qah", "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.", "questions": "1. Please describe the gaps between the upper and lower bounds of the KL divergence.\n\n2. The paper seems to be related subsampling in frequent statistics. Is coreset method a Bayesian counterpart?", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The Bayesian coreset approach is interesting and has been studied recently. Upper and lower bounds of the KL divergence are interesting and useful.", "weaknesses": "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.\n\n2. There seem to be insufficient experimental results to support the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your efforts reviewing the manuscript!\n\n> 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.\n> Please describe the gaps between the upper and lower bounds of the KL divergence.\n\nThis is a really great question! Reviewer jwKa had the same question, so we duplicate our response here.\n\nThe short answer is that the upper and lower bounds aren’t meant to be comparable. They’re tools to show whether an algorithm is working well or poorly. The upper bounds should be used to demonstrate that an algorithm is working well, while the lower bounds should be used to demonstrate that an algorithm is working poorly (much like our usage of our results in the paper in Cor 4.1,4.2,4.3, and 6.1).\n\nFor the lower bounds: essentially, you should think of the lower bounds as a “test for poor functioning” of a coreset construction. Roughly, the bounds in Theorem 3.3 and 3.5 say that any reasonable coreset construction algorithm must be good enough to well-approximate the score at the true parameter $g_w/\\bar w \\approx g/N$. We apply these results in Cor 4.1, 4.2 to show that importance-weighted coresets do not pass the test. If an algorithm passes the test (e.g., $\\|g/N - g_w/\\bar w\\| \\to 0$ quickly enough) the lower bounds don’t say much. The really nice thing about the lower bound “test” is that it makes the analysis quite simple: it reduces the problem of understanding minimum KL divergence to just a 2-norm comparison of two vector empirical averages. \n\nFor the upper bounds: Theorem 5.3 asserts that as long as you know the coreset construction algorithm is working at least somewhat well (  $(w-1)^TA(w-1) \\leq 1$ ), then you can bound the maximum KL divergence. We believe the upper bounds will be relatively tight in this regime, although we have not worked on a proof of this fact. The reason we believe this to be true is that the quadratic expansion of the KL divergence around $w=1$ is roughly $(w-1)^T \\mathrm{Cov}(\\dots) (w-1)$, which matches Theorem 5.3 with $A = \\mathrm{Cov}(\\dots)$ and $f(x) = x$, so the gap between the result in Theorem 5.3 and the true KL should be a cubic remainder term that decays quickly.\n\nNote that in our work we have encountered cases where the bounds coincide (ignoring constants), e.g. importance weighted constructions for Gaussian location models, for which both upper and lower bounds yield KL rates of $N/M$; but we believe these cases to be very limited and not of general interest.\n\nWe will be sure to include discussion related to this point in the revised manuscript.\n\n> There seem to be insufficient experimental results to support the results.\n\nPlease note that this is a theoretical paper; the proofs suffice to support the key contributions of the work. While experimental results are not necessary, we believe that the simulations involving models that violate the conditions of past work are illustrative and add some intuition, support, and clarity to the meaning of the theoretical results. \n\n> The paper seems to be related subsampling in frequent statistics. Is coreset method a Bayesian counterpart?\n\nYes, it is somewhat related to subsampling methods (e.g., work by HaiYing Wang at UConnecticut and collaborators in recent years). However, building good Bayesian coresets to obtain posterior KL control is a much harder problem in general. In the frequentist work we’ve seen, the goal is to find optimal subsampling weights that minimize some error criterion for point estimates. The lower bounds in our work (Cor 4.1, 4.2) show that *there does not exist any (reasonable) setting* of subsampling weights that yield a good Bayesian coreset; more careful tuning of the weights is required. This is essentially because Bayesian coresets need to approximate the full posterior distribution well, not just a single point estimate.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you to all the reviewers for their efforts reviewing our manuscript. We have responded to each reviewer in the comment section below their review. Please let us know if there are any further questions!

Meta-review: 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).
Decision: Accept (poster)