Divergence Frontiers for Generative Models: Sample Complexity, Quantization Effects, and Frontier Integrals
Authors: Lang Liu
Krishna Pillutla
Sean Welleck
Sewoong Oh
Yejin Choi
Zaid Harchaoui
Venue: NeurIPS 2021 Poster (2021)
Keywords: sample complexity
precision-recall
generative modeling
divergence frontiers

Abstract: The spectacular success of deep generative models calls for quantitative tools to measure their statistical performance. Divergence frontiers have recently been proposed as an evaluation framework for generative models, due to their ability to measure the quality-diversity trade-off inherent to deep generative modeling. We establish non-asymptotic bounds on the sample complexity of divergence frontiers. We also introduce frontier integrals which provide summary statistics of divergence frontiers. We show how smoothed estimators such as Good-Turing or Krichevsky-Trofimov can overcome the missing mass problem and lead to faster rates of convergence. We illustrate the theoretical results with numerical examples from natural language processing and computer vision.

Divergence Frontiers for Generative Models: Sample Complexity, Quantization Effects, and Frontier Integrals
Lang Liu' Sewoong Oh
Krishna Pillutla? Yejin Choi2.3
Sean Welleck Zaid Harchaoui"
Department of Statistics, University of Washington
2 Paul G. Allen School of Computer Science & Engineering, University of Washington 3 Allen Institute for Artificial Intelligence
Abstract
The spectacular success of deep generative models calls for quantitative tools to measure their statistical performance. Divergence frontiers have recently been proposed as an evaluation framework for generative models, due to their ability to measure the quality-diversio trade-off inherent to deep generative modeling. We establish asympllpiiiicc bounds on the sample complexity of divergence frontiers. We also introduce frontier integrals which provide summary statistics divergence frontiers. We show how smoothed estimators such as Good--Trrng can overcome the missing mass problem and lead to faster rates of convergence. We illustrate the theoretical results with numerical examples from natural language processing and computer vision.
1 Introduction
Deep generative models have recently taken giant leap forward in their ability model complex. high-dimensional distributions. Recent advances are able to produce incredibly detailed and realistic images [34, 51, 32), strikingly consistent and coherent text [50, 66. 6]. and music of near-human quality [16]. The advances in these models, particularly in the image domain, have been spurred by the development of quantitative evaluation tools which enable large-scale comparison of models, as well as diagnosing of where and why generative model fails [55. 38, 27, 54. 31].
Divergence frontiers quality and diversity in generative modeling with modern deep neural networks [54, 37, 59, 44, 49]. In particular, good generative model must not only produce high-quality samples that are likely under the target distribution but also cover the target distribution with diverse samples.
recently proposed by Djolonga al. [18] to quantify the trade-off between
While this framework is mathematically elegant and empirically successful [37, 49], the statistical properties of divergence frontiers are not well understood. Estimating divergence frontiers from data for large generative models involves approximations: (a) joint quantization of the model distribution and the target distribution into discrete distributions with quantization level k and (b) statistical estimation of the divergence frontiers based on the empirical estimators of the quantized distributions.
Djolonga et [18] argue that the quantization often introduces a positive bias, making the distribu- tions appear closer than they really are; while a small sample size can result in a pessimistic estimate of the divergence frontiers. The latter effect due to the missing mass of the samples, causing the two distributions to appear farther than they really are because the samples do not cover some parts of the distributions. The first consideration favors large k while the second favors small k.
35th Conference Neural Information Processing Systems (NeurIPS 2021).

---

P
R Q
P
R R
KL(Q
R
= Ra
R
R
KL(P|I
Figure 1: Left: Comparing two distributions P and Q. Here, RA AP (1- XjQ is the interpolation between P and Q for À E (0. 1) and R' denotes some arbitrary distribution. Right: The corresponding divergence frontier (black curve) between P and Q. The interpolations R, for A (0, 1) make up the frontier, while all other distributions such as R' must lie above the frontier.
In this paper, we are interested in answering the following questions: (a) Given two distributions, how many samples are needed to achieve desired estimation accuracy, or in other words, what is the sample complexity of the estimation procedure; (b) Given a sample size budget, how to choose the quantization level to balance the errors induced by the two approximations; (c) Can we have estimators better than the naïve empirical estimator.
Outline. We review the defimitions divergence frontiers and propose novel statistical summary Sec. 2. We establish non-asymptotic bounds for the estimation of divergence frontiers in Sec. 3, and discuss the choice of the quantization level by balancing the errors induced by the two approximations. We show how smoothed distribution estimators, such as the add-constant estimator and the Good- Turing estimator, improve the estimation accuracy in Sec. 4. Finally, we demonstrate in Sec. 5, through simulations on synthetic data as well generative adversarial networks on images and transformer-bawer language models on text, that our bounds exhibit the correct dependence of the estimation error on the sample size and the support size k.
Related work. The most widely used metries for generative models include Inception Score [55], Fréchet Inception Distance [27], and Kernel Inception Distance [4]. The former two are extended to conditional generative models in [2]. They summarize the performance by single value and thus cannot distinguish different failure cases, i.e., low quality and low diversity. Motivated by this limitation, Sajjadi et al. [54] propose a metric to evaluate the quality of generative models using two separate components: precision and recall. This formulation is extended in [59] to arbitrary probability measures using a density ratio estimator, while alternative definitions based on non- parametric representations of the manifolds of the data were proposed in [37]. These notions are generalized by the divergence frontier framework of Djolonga MAUVE, an area-under-thee the--uureve summary based on divergence frontiers for neural text generation. They find that MAUVE correlates well with human judgements on how close the machine generated text and the human text are.
[18), Pillutla al. [49] propose
Another line related work is the estimation of functionals of discrete distributions; see [62] for an overview. In particular, estimation of KL divergences has been studied by [8, 67, 7, 24] in both fixed and large alphabet regimes. These results focus on the expected L, and Lg risks and require additional assumptions on the two distributions such as boundedness of density ratio which is not needed in our results. Recently, Sreekumar al. [60] investigated modern way estimate f-divergences using neural networks. On the practical side, there is a new line of successful work that uses deep neural networks to find data-dependent quantizations for the purpose of estimating information theoretic quantities from samples [53, 23).
Notation. Let P(X)) be the space of probability distributions on some measurable space X. For
any P. Q E P(Y), let (L(P)(Q) be the Kullback- (KL) divergence between P and Q For X E (0, 1), define the interpolated KL divergence KLx(PIIQ) = KL(PIJAP (1 X)Q). For partition& S ;= {S,.... S.) of X. we define Ps the quantized version of P so that Ps E P(S) with Ps(S:) P(S;) for any i E [k] = (1....,

---

2 Divergence frontiers
Divergence frontiers compare distributions P and Q using frontier of statistical divergences. Each point on the frontier compares the individual distributions against a mixture of the two. By sweeping through mixtures, the curve interpolates between measurements of two types of costs. Fig. illustrates divergence frontiers, which we formally introduce below.
Evaluating generative models via divergence frontiers. Consider generative model Q E P(x) which attempls to model the target distribution P E P(X)). It has been argued in [54, 37] that one must consider two types of costs to evaluate Q with respect P: (a) type I cost (loss in precision), which is the mass of Q that has low or zero probability mass under P. and (b) a type II cost (loss recall), which is the mass of P that Q does not adequately capture.
Suppose P and Q are form distributions supports. Then, the type I cost the mass of Supp(Q) Supp (P). or equivalently, the mass of Supp(R) RR) \ Supp(P), P). We measure this using the surrogate KL(Q] RR), which is large if there exists a such that Q(a) is large but R(a) small. Likewise, the type II cost measured by KI, (I).P) When P and Q are not constrained to be uniform, it is not clear what the measure R should be. Djolonga et al. [18] propose to vary R over all possible probability measures and consider the Pareto frontier of the multi-objective optimization ming (KL(PI)R) (R). (L (R) This leads to curve called the divergence frontier, and is reminiscent of the precision-recall curve in binary classification. See [15, 13. 14, 19] and references therein trade-off curves in machine learning.
their supports, and R is uniform the union of their
Formally, be shown that the divergence frontier F(P, Q) of probability measures P and Q is carved out by mixtures Rx = XP + (1 x)Q for À E (0, 1) (cf. Fig. 1). It admits the closed-form
F Q) = (KL(P|RA). (IP.))((KL(P(BBB))
(L) : A (0.1))
Practical computation of divergence frontiers. In practical applications, P is complex, high- dimensional distribution which could either be discrete, as natural language processing, or continu- ous, as in computer vision. Likewise, Q is often a deep generative model such as GPT-3 for text and GANs for images. It is infeasible compute the divergence frontier F(P, Q) directly because we only have samples from and the integrals or sums over Q are intractable.
Therefore, the recipe used by practitioners [54, 18, 49] has been to (a) jointly quantize and Q over a partition S = {S ) of X' to obtain discrete distributions Ps (P(S.)) and Qs (())).) (b) estimate the quantized distributions from samples to get Ps and Qs. and (c) compute F Ps, Qs). In practice, the best quantization schemes are data-dependent transformations such as k-means clustering or lattice-typ type quantization of dense representations of images or text [53].
Statistical summary of divergence frontiers. In the minimax theory of hypothesis testing, where the goal is also to study two lypes of errors (yet different from the ones considered here), it is common to theoretically analyze their linear combination; see, e.g.. [30, Sec. 1.2] and [9, Thm. 7]. In the same spirit, consider linear combination of the two costs, quantified by the KL divergences,
(P,P, Q) = XKL(P| RA) + (1 (Q)
(1)
Note that R2 is exactly the minimizer of the linearized objective XKI + (1 A)KL(Q) according to [18, Props. 1 and 2]. LA is also known as the A-skew Jensen- Shannon Divergence [46].
The linearized cost LA depends on the choice of X. To remove this dependency, we define novel integral summary, called the frontier integral FI(P, Q) of two distributions and Q as
FI FI(P.Q) == (x(PQ))
(2)
We can interpret the frontier integral as the average lincarized cost over À E (0, 1). While the length of the divergence frontier can be unbounded as shown in Appx. H. the frontier integral is always bounded in [0, 1]. Moreover, it is symmetric divergence with FI(P, Q) = iff P Q (Appx. B). In practice, can be estimated using the same recipe as the divergence frontier.
Error decomposition. In Sec. 3, we decompose the error in estimating the frontier integral into two components: the statistical error of estimating the quantized distribution and the quantization

---

0.3
R& P
0.3
2 P
H
0.2
Krichevsky Trofimos
0.2
0.1
Missing mass
8 10
10
Figure 2:
The empirical estimator with missing mass and the Frichevsky-Trofimee estimator.
error. Our goal is to derive rate of convergence for the overall estimation error. To control the statistical error, we use a different treatment for the masses that appear in the sample and the ones that never appear (i.e., the missing mass). We obtain high probability bound well bound for its expectation, leading to upper bounds for its sample complexity and rate of convergence. These results carry over to the divergence frontiers as well. As for the quantization error, we construct a distribution- dependent quantization scheme whose error A combination of these two bounds sheds light on the optimal choice of the quantization level. In Sec. 5, we verify empirically the tightness of the rates synthetic and real data.
most O(k- 1), where k the quantization level.
3 Main results
In this section, we summarize our main theoretical results. The results hold for both the linearized cost La and the frontier integral FI, we focus Fl here due to space constraints. For P. Q E P(X), let {-,)== and {Y.) be i.i.d, samples from P and Q, respectively, and denote by P. and Qn the respective empirical measures of and Q. The two samples are assumed to have the same size n for simplicity. We denote by C' an absolute constant which can vary from line to line. The precise statements and proofs can be found the Appendix.
We are interested in deriving a non-asymptotic bound for the absolute error of the empirical estimator, i.e., |F Pn. Q.) FI(P, Q) When both and Q are supported on a finite alphabet with & items, natural strategy is to exploit the smoothness properties of Fl, giving a naïve upper bound O k/n) on the absolute error, where I. = log 1 //p. with p. cuppe)upp(P) P(a) reflecting the smoothness of FI. The dependency have a finite support and short tail. However, in many real- world applications, the distributions can either be supported on countable set or have long tails [11, 64). By considering the missing mass in the sample, are able to obtain a high probability bound that is independent of p..
Sample complexity for the frontier integral.
p. requires P to
Theorem 1. Assume that P and Q are discrete and let k = m [Supp(P)]. (uup e NU [oo). For any 8 E (0, 1), holds that, with probability at least 1 6,
FI((P,. (..)F.((P..) sc cc((
[
log 1/5
a. + an(l)) logn Ba(P) B. Ba((2)
(3)
where an (P((P) EmEx PPla) and 3P(P) = B[ (a)=0 P(a) max {1, (1/P(a)))}
Furthermore, if the support size xc, then (P) S / /k/n and Bn(P) k log n/n. In particular, with probability at least 6.
FI(P - - SC
log 1/8
k 71
log n
(4)
Before discuss the bounds in Thm. let introduce the missing mass problem. This problem
first studied by Good and Turing [21]. where the eponymous Good-Turing estimator was proposed to estimate the probability that new observation drawn from fixed distribution has never appeared before, in other words, is missing in the current sample: see Fig. (left) for an illustration. The Good-TTrrig estimator has been widely used in language modcling [33, 12, 11] and studied in theory [41, 48, 47]. An inspiring result coming from this line of work is that the missing mass in sample of size n concentrates around its expectation [40], which itself decays as (k/nn) when the distribution is supported on & items [3].

---

p(n)
0.10
q(2)
Sep m2d
Siaaft) Saaa
0.66
7g
0.2
11
0.00
T6
25
Figure 3: Left: Tail decay of three distributions. Middle: Oracle quantization into 3 bins: blue, yellow and red. Bin is given by the set {x f(p(z)/q(z)) e [T)]. Right: The generator and conjugate generator of KL, at 1/2.
There are several merits Thm. 1. First, (3) holds for any distributions with countable support. Second, it does not depend on p.. and is adapted to the tail behavior of P and Q. For instance, if P is defined as P(a) x a=2 for E [k], then (P)))
(P) x (log k)/ vn, which is much better than / k/n ni (4) in terms of the dependency on k. This phenomenon is also demonstrated empirically in Sec. 5, Third, it captures a parametric rate of convergence, i.c., O(n 112),, up to a logarithmic factor. In fact, this rate is not improvable in related problem of estimating KL(PIIQ), even with the assumption that P/Q bounded [7]. The bound in (4) a distribution-fres bound, assuming & is finite. Note that it also gives an upper bound on the sample complexity by setting the right hand side of (4) to be and solving for n, this is roughly O(( (((Vlog log 1/8 + vk) (2))
The proof of Thm. relies on two new results: (a) a concentration bound around E[FI(P,, Qn)]. which can be obtained by McDiarmid's inequality, and (b) an upper bound for the statistical error, i.c., E FI Qn) - FI(P, Q) which is upper bounded by
O ([an(P) + a, (Q)) logn n- + (P) + Bn (Q)) S O(lV k/n) logn).
(5)
The concentration bound gives the term n 1 log 1/6. The statistical error bound is achieved by splitting the masses of and Q into two parts: one that appears in the sample and one that never appears. The first part can be controlled by Lipschitz-like property of the frontier integral, leading
to the term a,, (P) + an (Q), and the second part, (P) + B,, (Q), falls into the missing mass framework. addition, the rate k/n for 3n shown here matches the rate for the missing mass.
Statistical consistency of the divergence frontiers. While Thm. establishes the consistency of the frontier integral, it is also of great interest to know whether the divergence frontier itself can be consistently estimated. In fact, similar bounds hold for the worst-case eтror of F(P m. Qn).
Corollary 2. Under the same assumptions in Thm. 1, the bounds in (3) and (4) hold for
sup XE(Aa.1 Aoo
[[(KL(P.))..)) (L(
(KL(P) Rx), KL(Q) RR)))
where Rex = XP, u, (1 2)Qn. with C replaced by Ca for any do (0, In particular, Xa is chosen X, o(1) and A w( /k/nlog n), then the expected worst-case error above converges to zero at rate OA,²² O Vk)nlogn).
The truncation in Cor. is necessary without imposing additional assumptions, since (L(()))xx) is close to KL(PIQ Q) for small À and it is known that the minimax quadratic risk of estimating the KL divergence over all distributions with & bins is always infinity [7].
Upper bound for the quantization error. Recall from Sec. 2 that computing the divergence frontiers in practice usually involves quantization step. Since every quantization will inherently introduce positive bias in the estimation procedure. it is desirable to control the error, which we call the quantization error, induced by this step. We show that there exists a quantization scheme with error proportional to the inverse its level. We implement this scheme and empirically verify this rate in Appx. G; certain regimes appear to show even faster convergence.
Let X' be an arbitrary measurable space and S be a partition of X. The quantization error of S is the difference [F[(Ps. Qs) - FI Q)) It can be shown that there exists a distribution-dependee partition St with level St = & whose quantization error is no larger than the inverse of its level, i.e.,
FI(P, Q) FI(Ps., Qs.) S Ck-
(6)

---

The key idea behind the construction of this partition is visualized in Fig. 3 (middle). Combining this bound with the bounds in (5) leads to the following bound for the total estimation error.
Theorem 3. Assume that Ss is a partition of X such that |Sx| = k 2 2. Then the total error E FI. Qse.)) FI(P. Q) upper bounded by
(a,) + a., (Q)) logn + (P) + (Q) (FI(P.Q) FI(Ps. Qs.)].
(7)
Moreover, if the quantization envor satisfies the bound (6), we have
E FI[ Qs...) Q) sc sc [C[(//n + k/n)
logn 1/k
(8)
Based on the bound in (8), good choice of l is ((12/3) which balances between the two types of errors. We illustrate in Sec. 5 that this choice works well in practice. This balancing is enabled by the existence of good quantizer with distribution-free bound in (6). In practice, this suggests data-dependent quantizer using nonparametric density estimators. However, directions such as kernel density estimation [42, 26, 28] and nearesl-neighhor methods [1] have not mel empirical success, they suffer from the curse of dimensionality common in nonparametric estimation. In particular, [63, 57, 58] propose quantized divergence estimators but only prove asymptotic consistency, and little progress has been made since then. On the other hand, modern dala-dependent quantization techniques based on deep neural networks can successfully estimate properties of the density from high dimensional data [53, 23]. Theoretical results for those techniques could complement our analysis. We leverage these powerful methods to scale our approach real data in Sec. 5.
4 Towards better estimators and interpolated f f-divergences
Smoothed distribution estimators. When the support size & is large, the statistical performance of the empirical estimator considered in the previous section can improved. To overcome this challenge, practitioners often use more sophisticated distribution estimators such as the Good-Turin estimator [21, 47] and add-constant estimators [35, 5J. We focus the add-constant estimator defined below and state here its estimation error when is applied to estimate the frontier integral from data. Again, this result also holds for the linearized cost Lx. We investigate and compare the performance of various distribution estimators in Sec. 5.
For notational simplicity, we assume that P and are supported on a common finite alphabet with size k < co. Note that this is true for the quantized distributions Ps and Qs. For any constant b >> O, the add-constant estimator of P is defined as P.. (a) (N, + b) (n + kb) for each a E Supp(P). where N. { X1 = a}} is the number of times appears in the sample.
Thanks the smoothing, there is mass missing in the add-constant estimator. This effect is illustrated for the Krichevsky-Trofimov Trofimov (add-1/2) estimator Fig. 2. As result, we can directly utilize the smoothness properties of the frontier integral to get the following bound.
Proposition 4. Under the same assumptions as in Thm. 3, we have
FI (P..., Qs...ss -I((P.
sc n(a, + (Q))
+ Tn. (P) + mm log (n/b
(9)
71 n bk:
where Tn. (P) (n + -kk Eaex IP(a) 1/kl, It can be further upper bounded by Vnk+be log (n/b + k) up to a multiplicative constant.
n bh
Let us compare the bounds in Prop. 4 with the ones in Thm. 3. For the distribution-dependeed bound, the term a,, (P) log n in (7) is improved by a factor 12/(1 + bk) in (9). The missing mass term B, (P) is replaced by the total variation distance between P and the uniform distribution on [k] with factor bk/(n bk)). The improvements in both two terms are most significant when k/n ' large. As for the distribution-fres bound, when k/n s/niix is small, the bound in Prop. 4 scales the same as the one in (8); when k/n is large (i.e., bounded away from O or diverging), it scales O log (k/n) + k-)) while the one in (8) scales as O(k log n //////-- -1). Given the improvement, it would be an interesting venue for future work to consider adaptive estimators in the spirit of [20].

---

(n) 10=1100 10
(6) n= 2 10"
(c) 10 == 10"
(d) A 10" 10
Absolute ertor
05
10
28
0.5
10
2.
Sample size
Support
Tail decay
Tail docay
Monte Carlo
Oracle bound
Bound
Figure 4: Statistical error of the estimated frontier integral synthetic data. (a): Zipf(2) and Zipf(2) x 10²; (c): Dir(1) and 7ipf(r) with 10 and
with & 109; (b): 7ip and 7ipf(2) with n 10 (d): (2) and Zrpf(r) with k = 102 and n = 10a. The bounds are scaled by 100.
Generalization to f-divergences. Estimation of the x² divergence is useful for variational infer- ence [17] and GAN training [39, 61]. More generally, estimating f-divergences from samples fundamental problem in machine learning and statistics [45, 29, 10, 52]. We extend our previous results to estimating general f f-divergences (which satisfy some regularity assumptions) using the same two-step procedure of quantization and estimation of multinomial distributions from samples.
We start by reviewing definition f-divergences. Let f (0) + R nonnegative and convex function with f(1) = 0. Let P,Q E P(X') be dominated by some measure E P(X') with densities p and q, respectively. The f-divergence generated by f is defined
p(x)
(y()))
((x)f
du(x).
((x:)
with the convention that f(0) = f(0+) and = pf where -0 E [0, oo] for (t) = (1(/t).. We call f the conjugate generator to An illustration of the generator to KL1/2 can be found Fig. (right). Note that the conjugacy here is unrelated but is based on the perspective transform. The function f also generates an f-divergence, which is the conjugate divergence to Dy since D--
convex conjugacy
referred
D)(Q))P)-
The quantization error bound (6) holds for all f-divergences which are bounded, i.c. ff
cc. The high probability bounds in Thm. also hold for f-divergences, under some regularity logt for small t, which guarantees that f is approximately Lipschitz and cannot vary too fast; (b) (t) and (()))"((t) are bounded, which is a technical assumption that helps control the variation of f around zero. The interpolated x² divergence, defined analogously the interpolated KL divergence, satisfies these conditions.
assumptions: (a) [f'(t)) logt and [()))(tt]
In the Appendix, we prove all the results for general f f-divergences and show that both the frontier integral and the linearized cost are f-divergences satisfying the regularity conditions, recovering Thm. 1 and Thm. 3 as special cases.
5 Experiments
We investigate the empirical behavior of the divergence frontier and the frontier integral on both synthetic and real data. Our main findings are: (a) the statistical error bound approximately reveals the rate of convergence
empirical estimator; (b) the smoothed distribution estimators improve the estimation accuracy; (c) the quantization level suggested by the theory works well empirically. The results for the divergence frontier and the frontier integral are almost identical. We focus the latter here due to space constraints. In all the plots, we visualize the average absolute error computed from 100 repetitions with shaded region denoting one standard deviation around the mean. More details and additional results, including the ones for the divergence frontier, are deferred to Appx. G. The code to reproduce the experiments is available online!.
5.1 Experimental setup
We work with synthetic data in the case when k = |X| oo well as real image and data.
'htpps: /ttpttttttttt//t////////tttttt www.///o/o/oi//iee.eoooe https//bb.....mmmaaaaaa////eerer frontier-bont bounds.

---

Images (R 128)
2048)
Images (n 1000)
(d) 10000)
Absolute arror
16
18
12'
10"
167
12a
101
1P
Sample size
Sample size
Support size
Support size
Monte Carlo
Oraele bound
Bound
Figure 5: Statistical error of the estimated frontier integral on real data. (a): Image data (CIFAR-10) with l 128: (b): Text data (WikiText- 103) with 2048; (c): Image data (CIFAR-10) with
n 1000; (d): Text data (WikiText-10) with n = 10000. The bounds are scaled by 30.
Synthetic Data. Following the experimental settings in [47], we consider three types distributions: (a) the Zipf(r) distribution with r E {0, 1, 2) where P(i) o i-" Note that Zipf(r) is regularly varying with index -r; see, e.g.. [56, Appx. BJ. (b) the Step distribution where P(i) 1/2 for the first half bins and P(i) = 3/2 for the second half bins. (c) the Dirichlet distribution Dir(a) with a E (1/2, 1); see Fig. 1 (left) for an illustration. In total, there are 6 different distributions, giving different pairs of (P, Q). For each pair (P. Q), we generate i.i.d. samples of size from each of them, and estimate the divergence frontier as well as the frontier integral from these samples.
Real Data. We consider two domains: images and text. For the image domain, we train a Style- GAN2 [32] on the CIFAR-IO dataset [36] using the publicly available code² with default hyperparam- eters. To evaluate the divergence frontiers, we use the test set of 10k images as the target distribution P and we sample 10k images from the generative model the model distribution Q. For the text domain, we fine-tune a pretrained GPT-2 [50] model with 124M parameters (i.e., GPT-2 small) on the Wikitext- 103 dataset [43]. We use the open-source HuggingFace Transformers library [65] for training, and generate 10k 500-token completions using top-p sampling and 100-token prefixes.
We take the following steps compute the frontier integral. First, we represent each image/text by its features [27, 54, 37). Second, we learn a diw-emmesiioall feature embedding which maintains the neighborhood structure of the data while encouraging the features to be uniformly distributed on the unit sphere [53]. Third, we quantize these embeddings on a uniform lattice with & bins. For each support size k, this gives us quantized distributions Ps, and Qs.- Finally, we sample n i.i.d. observations from cach of these distributions and consider the empirical distributions Ps and Qs..n as well as the smoothed distribution estimators computed from these samples.
Performance Metric. We are interested in the estimation of the frontier integral FI(P,Q) using estimators FI(P.., Q.. for the empirical estimator well the smoothed distribution estimator. We measure the quality of estimation using the absolute error, which is defined as [FI(P,, Qn) FI(P, Q) For the real data, measure the error of estimating FI(Ps,, Qs.) by FI(Ps, na Qs..)).
5.2 Tightness of the Statistical Bound
We investigate the tightness of the statistical error bound of Thm. with respect to the sample size n and the support size k. in order to verify the validity of the theory in practically relevant settings.
We estimate the expected absolute error E]FI(P,,. Q.) - FI(P, from a Monte Carlo estimate using 100 random trials. We compare it with the following bounds in' Thm. 1:
(a) Bound: the distribution independent bound (v k//n k/n) log
(b) Oracle Bound:
the distribution dependent bound (a,(() + a, ax (Q)) + (x + (,(Q). We assume that the quantities a, and 8, defined in Thm. are known.
PILL LpL : / iigihuub Luub. com/ wom/NVlen wilbbs/ / (uylegan2-ada-ppve Lorch. "Specifically, we use the expected bound of Prop. 16 (Appx. D). from which Thm. I is derived.

---

(n) 1 10
(b) n= x 10"
(c) 10", - 10"
(d) A 10" 10
Absolute arTor
65
10
0.5
10
36
Sample size
Support
Tail decay
Tail docay
Empirical
Bracas-Saucr
Good- Good-Turing Turing
Krichovaky-Trofee Trofimov
Laplace
Figure 6: Statistical error with smoothed distribution estimators synthetic data. (a): Zipf and Dir (1 (2) with 10s; (b): (0) and (2r(1/2) with n 2 10 (c): Dir(1) and (rp with
k = 10 and n = 10": (d): (ip and (r) with k = 10 and n 10*.
Images (k- 128)
(b) Text 2048)
(c) Imanges (1 1000)
(d) Text (i 10000)
Absolute error
10'
10
1s*
wf
Sample size
Sample
Support
Support size
Empirical
Bracss-Sauer
Good-Turing
Beabeevsk-TTrofimee
Laplace
Figure 7: Statistical error with smoothed distribution estimators on real data. (a): Image data (CIFAR- 10) with & 128; (b): Text data (WikiText- 103) with 2048; (c): Image data (CIFAR-10) with n = 1000; (d): Text data (WikiTexl-1033 with n = 10000. The bounds are scaled by 15.
We fix k. plot each of these quantities in log-log plot with varying n and compare their slopes.* 4 We then repeat the experiment with n fixed and k varying. We often scale the bounds by constant for easier visual comparison of the slopes; this only changes the intercept and leaves the slope unchanged.
Thm. 1 is tight for synthetic data. Fig. 4 gives the Monte Carlo estimate and the bounds of the statistical error for various synthetic data distributions. In Fig. 4(a), we observe that the bound has approximately the same slope as the Monte Carlo estimate, while the oracle bound has a slightly worse slope. In Fig. 4(b), we observe that the oracle bound captures the correct rate for k 300, while the distribution-indeeeedeee both bounds capture the right rate over a wide range of tail decay. The oracle bound is tighter for fast decay, where the setribution-indeeeddee
bound captures the correct rate small k. For the right
plots,
bounds o,,, (Q) and 3,((Q) can be very pessimistie.
Thm. is somewhat tight for real data. Fig. contains the analogous plot for real data, where the observations are similar. In Fig. 5(b), we see that the oracle bound captures the right rate for small sample sizes where k/n n > 1. However, for large n, the distribution-indeeeddde matching the slope of the Monte Carlo estimate. The same is true for Fig. 5(c), where the oracle bound is better for large k. For parts (a) and (d), however, both bounds do not capture the right slope of the Monte Carlo estimate; Thm. is not tight upper bound in this case.
bound is better at
5.3 Effect of Smoothed Distribution Estimators
We now show that smoothed estimators can lead improved estimation over the naïve empirical estimator and thus improved sample complexity as shown in Prop. 4. This is practically significant in the context of generative models, since one can have an equally good estimate of the divergence frontier with fewer samples using smoothed estimators [54, 18).
Concretely, compare the Monte Carlo estimates of the absolute error FI Q.) Q) for the plug-in estimate (denoted "Empirical") with the corresponding estimates for smoothed estimators.
A log-log plot of the function f(x cr" is a straight line with slope which thus captures the degree.

---

Absolute arror
16'
10
10
of Sample size
I0 Sample size
Sample size
Sample size
Figure Total error with quantization level oc /r on 2-dimensional continuous data. (a): (0, 12) and (1, (b): (0, 12) and (0,, 512); (c): (0 I2) and (4 /2) (multivariate t- distribution with 4 degrees of freedom); (d): (0, I2) and (0 5I2).
We consider 4 smoothed estimators in [47]: the (modified) Sood-Turing estimator, well as three add-constant estimators: the Laplace, Krichevsky- Trafimov and Braess-Sauer estimators.
Smoothed estimators are more efficient than the empirical estimator. We compare the smoothed estimators to the empirical one in Fig. 6 on symthetic data and Fig. 7 on real data. In general, the smoothed distribution estimators reduces the absolute error. For parts (a) and (b) of Fig. 6, the Good-Turing and the Krichevsky-Trooiime and (d). the Good-Turine estimator is adapted to various regimes of tail-decay, outperforming the empirical estimator. The Krichevsky-Troofmee and Braess- -auess estimators, on the other hand, exhibit small absolute error for particular decay regimes. The results are similar for real data in Fig. 7.
estimators have the best absolute error. For parts (c)
Practical guidance on choosing smoothed estimator. While the smoothed estimators offer a marked improvement when k/n is large (that is, close to 1). the best estimator is problem-dependenn As a rule of thumb, we suggest the Krichevsky- Triffevsky-Trofimov estimator which works well in the large k/n regime but is still competitive when k /n small (i.e., large n.).
5.4 Quantization Error
Next, we study the effect of the quantization level k on the total error. We consider simple 2- dimensional synthetic setting where the distributions Q are either the multivariate normal t-distributions. We use data-driven quantization with k-means to obtain a quantization Sg: each component of the partition is the region corresponding
cluster. Finally, plot the absolute error [E[ P. Q) FI FI(Ps,... Qs,.n)l. where the FI(P, Q) is computed using numerical integration and the expectation is estimated with Monte Carlo simulations.
The choice k = (n3//3 works the best. We compare k: = // for r = 2, in Fig. 8. For small n., 2 3 all perform similarly, but 3 clearly outperforms other choices for > 10 While our theory does not directly apply for data-dependent partitioning schemes, the choice & 1/33/3) suggested by Thm. 3 nevertheless works well in practice.
6 Conclusion
In this paper, we study the statistical behavior of the divergence frontiers and the proposed integral summary estimated from data. We decompose the estimation error into two components, the statistical error and the quantization error, conform with the approximation procedure commonly used in practice. We establish non-asymplotic bounds on both of the two errors. Our bounds shed light on the optimal choice of the guantization level k- k-they suggests that the two errors can be balanced at k = 133). We also derive new concentration inequality for the frontier integral, which provides the sample complexity of achieving a small error in high probability. Finally, we demonstrate both theoretically and empirically that the use of smoothed distribution estimators can improve the estimation accuracy. All the results can be generalized to large class of interpolation-base divergences. Provided new theoretical results modern data-dependent quantization schemes using deep neural networks, would be an interesting direction for future work to specialize our bounds to such quantization schemes. Extending our results to 3-divergences could also be interesting.
f-
10

---

The authors would like to thank J. Thickstun for fruitful discussions, Part of this work was done while Z. Harchaoui was visiting the Simons Institute for the Theory of Computing. This work was supported by NSF DMS-2134012, NSF CCF-2019844, the CIFAR program "Learning in Machines and Brains", and faculty research awards.
Acknowledgments.
References
[1] M. Alamgir, G. I Lugosi, and U. von Luxburg. Density-preserving quantization with application to graph downsampling, In COLT, 2014.
[2] Y. Benny, T. Galanti, S. Benaim, and L.. Wolf. Evaluation metrics for conditional image generation. International Journal of Computer Vision, 129(5), 2021.
[3] D. Berend and A. Kontorovich. The missing mass problem. Statistics & Probability Letters, 82
(6), 2012.
[4] M. Binkowski, D. J. Sutherland, M. Arbel, and A. Gretton. Demystifying MMD GANs. ICLR, 2018.
[5] D. Braess and T. Sauer. Bernstein polynomials and learning theory. Journal of Approximation Theory, 128(2), 2004.
[6] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss -oss,, G. Krueger, T. Henighan, Child, A. Ramesh, D. M. Ziegler. J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei.
Language models are few-shot learners. NeurIPS, 2020.
[7] Y. Bu, S. Zou, Y. Liang, and V. V. Veeravalli. Estimation of KL divergence: Optimal minimax rate. IEEE Transactions on Information Theory, 64(4), 2018.
[8] H. Cai, S. Kulkarni, and S. Verdú. Universal divergence estimation for finite-alphaber sources.
IEEE Transactions on Information Theory, 52(8), 2006.
[9] T. T. Cai, X. J. Jeng, and Jin. Optimal detection of heterogeneous and heteroscedastic mixtures. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 73(5), 2011.
[10] L. Chen, C. Tao, R. Zhang, R. Henao, and L. Carin. Variational inference and model selection with generalized evidence bounds. ICML, 2018.
[11] S. F. Chen and J. Goodman. An empirical study of smoothing techniques for language modeling. Computer Speech Language, 13(4), 1999.
[12] K. W. Church and W. A. Gale. comparison of the enhanced Good-Turing and deleted estimation methods for estimating probabilities of English bigrams. Computer Speech & Language, 5, 1991.
[13] S. Clémençon and N. Vayatis. Nonparametric estimation of the precision-recall curve. In ICML. pages 192- 2009.
[14] S. Clémençon and N. Vayatis. Overlaying classifiers: practical approach to optimal scoring. Constructive Approximation, 92:619-648, 2010.
[15] C. Cortes and M. Mohri. Confidence intervals for the area under the ROC curve. NeurlPS. volume 17, 2005.
[16] P. Dhariwal, H. Jun, C. Payne, J. W. Kim, A. Radford, and I. Sutskever. Jukebox: A generative model for music. arXiy Preprint, 2020.
[17] A. B. Dieng, D. Tran, R. Ranganath, J. W. Paisley, and D. M. Blei. Variational inference via x upper bound minimization. In NeurlPS, 2017.
[18] J. Djolonga, M. Lucic, M. Cuturi, O. Bachem, O. Bousquet, and S. Gelly. Precision-recall curves using information divergence fromtiers. In AISTATS, 2020.
[19] P. Flach. Machine Learning: The Art and Science of Algorithmms That Make Sense of Data. Cambridge University Press, 2012.
[20] A. Goldenshluger and O. Lepski. Structural adaptation via Lo norm oracle inequalities. Proba- bility Theory and Related Fields, 143, 2009.
11

---

[21] J. Good. The population frequencies of species and the estimation of population parameters. Biometrika, 40(3-4), 1953.
[22] L. Györfi and T. Nemetz. f-dissimilarity: A generalization of the affinity of several distributions. Annals of the Institute of Statistical Mathematics, 30, 1978.
[23] P. Hämäläinen, T. Saloheimo, and A. Solin. Deep residual mixture models, arXiv Preprint, 2020.
[24] Y. Ham, J. Jiao, and Weissman. Minimax estimation of divergences between discrete distributions. IEEE Journal on Selected Areas in Information Theory, 1(3), 2020.
[25] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, 2016.
[26] A. Hegde, D. Erdogmus, T. Jehn-Schiolee Y. N. Rao, and J. C. Principe. Vector-quantizatoon by density matching in the minimum Kullback-Leibler divergence sense. In IJCNN, 2004.
[27] M. Heusel, H. Ramsauer. T. Unterthiner, B. Nessler, and S. Hochreiter. GANs trained by two time-scale update rule converge to local Nash equilibrium. NeurIPS, 2017.
[28] M. V. Hulle. Faithful representations with topographic maps. Neural Networks, 12(6), 1999.
[29] D. J. Im, H. Ma. G. W. Taylor, and K. Branson. Quantitatively evaluating GANs with divergences proposed for training. In ICLR, 2018.
[30] Y. Ingster and I. Suslina. Nonparametric Goodness-of-Fil Testing Under Gaussian Models. Springer, 2003.
[31] T. Karras, S. Laine, and Aila. A style-based generator architecture for generative adversarial networks. In CVPR, 2019.
[32] T. Karras, M. Aittala, J. Hellsten, S. Laine, J. Lehtinen, and T. Aila. Training generative adversarial networks with limited data. In NeurIPS, 2020.
[33] S. M. Katz. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions Acoustics Speech and Signal Processing, 35(3), 1987.
[34] D. P. Kingma and P. Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. In NeurlPS, 2018.
[35] R. E. Krichevsky and V. K. Trofimov. The performance of universal encoding. IEEE Transac- tions on Information Theory, 27(2), 1981.
[36] A. Krizhevsky and Hinton. Learning multiple layers of features from tiny images. Technical Report, 2009.
[37] T. Kynkäänniemi, T. Karras, S. Laine, Lehtinen, and Aila. Improved precision and recall metric for assessing generative models. In NeurIPS, 2019.
[38] D. Lopez-Paz and M. Oquab. Revisiting classificr two-sample tests. In ICLR, 2017.
[39] X. Mao, Q. Li, H. Xic, R. Y. K. Lau, Z. Wang, and S. P. Smollcy. Least squares generative adversarial networks. In ICCV, 2017.
[40] D. Mcallester and L. Ortiz. Concentration incqualities for the missing mass and for histogram rule error. Journal of Machine Learning Research, 4, 2003.
[41] D. A. McAllester and R. F. Schapire. On the convergence rate of Good-Turing estimators. In COLT, 2000.
[42] P. Meinicke and H. Ritter. Quantizing density estimators. In NewrlPS, 2002.
[43] S. Merity, C. Xiong, J. Bradbury, and R. Socher. Pointer sentinel mixture models. In ICLR, 2017.
[44] M. Naeem, S. J. Oh, Y. Uh, Y. Choi, and J. Yoo. Reliable fidelity and diversity metrics for generative models. In /CML, 2020.
[45] X. Nguyen, M. Wainwright, and M. I. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56 (11), 2010.
[46] F. Nielsen and R. Bhatia. Matrix Information Geometry. Springer, 2013.
12

---

[47] A. Orlitsky and A. T. Suresh. Competitive distribution estimation: Why is Good-Turing good. In NeurIPS, 2015.
[48] A. Orlitsky, N. P. Santhanam, and J. Zhang. Always Good Turing: Asymptotically optimal probability estimation. In FOCS, 2003.
[49] K. Pillutla, S. Swayamdipta, R. Zellers, J. Thickstun, S. Welleck, Y. Choi, and Z. Harchaoui. Mauve: Measuring the gap between neural lext and human text using divergence frontiers. NeurlPS, 2021.
[50] A. Radford, Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever. Language models are unsupervised multitask learners. OpenA/ Blog, 2019.
[51] A. Razavi, van den Oord, and O. Vinyals. Generating diverse high-fidelity images with VQ-VAE-2. In NeurlPS, 2019.
[52] K. Rubenstein, O. Bousquet, Djolonga, C. Riquelme, and Tolstikhin. Practical and consistent estimation of f-divergences. In NeurlPS, 2019.
[53] A. Sablayrolles, M. Douze, C. Schmid, and H. Jégou. Spreading vectors for similarity search. In ICLR, 2019.
[54] M. Sajjadi, Bachem, M. Lucic, O. Bousquet, and Gelly. Assessing generative models via precision and recall. In NeurIPS, 2018.
[55] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, and X. Chen. Improved techniques for training GANs. In NeurlPS, 2016.
[56] G. R. Shorack. Probability for Statisticians. Springer, 2000.
[57] J. Silva and S. Narayanan. Universal consistency of data-driven partitions for divergence estimation. ISIT, 2007.
[58] J. Silva and S. S. Narayanan. Information divergence estimation based on data-dependent partitions. Journal of Statistical Planning and Inference. 140(11). 2010.
[59] L. Simon, R. Webster, and J. Rabin. Revisiting precision recall definition for generative modeling. ICML, 2019.
[60] S. Sreekumar, Z. Zhang, and Z. Goldfeld. Non-asymptotic performance guarantees for neural estimation of f-divergences. AISTATS, 2021.
[61] C. Tao, I.. Chen, R. Henao, J. Feng, and L. Carin. Chi-square generative adversarial network. In ICML, 2018.
[62] S. Verdú. Empirical estimation of information measures: A literature guide. Entropy, 21(8).
2019.
[63] Q. Wang, S. R. Kulkarni, and S. Verdú. Divergence estimation of continuous distributions based on data-dependent partitions. JEEE Transactions on Information Theory, 51(9), 2005.
[64] Y. Wang, D. Ramanan, and M. Hebert. Learning to model the tail. In NeurIPS, 2017.
[65] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, J. Davison, S. Shlcifer, P. von Platen, C. Ma, Y. Jernite, J. Plu, C. Xu, T. L. Scao, S. Gugger, Drame, Q. Lhoest, and A. M. Rush. Transformers: State-of-the-art natural language processing. In EMNLP, 2020.
[66] R. Zellers, A. Holtzman, Rashkin, Y. Bisk, Farhadi, F. Roesner, and Y. Choi. Defending against neural fake news. In NeurIPS, 2019.
[67] 7. Zhang and Grabchak. Nonparametric estimation Küllback-Leee divergence. Neural
Computation, 26(11).200 2014.
13


Reviews:
[{"review_id": "nQIshrhwCD0", "reviewer": "Reviewer_vaVk", "summary": "This works studies an evaluation metric for comparing two distributions with possibly non-overlap support. The metric called \"divergence frontier\" was proposed in Djolonga et al. This work proved non-asymptotic bounds for quantized estimator of the metric, suggesting a good quantization level (number of bins k ~ n^{1/3}. It also suggests using smoothed empirical distribution estimators (add-constant/Good-Turing) to improve the estimation accuracy. The experiments are difficult to understand due to low clarity.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of this paper is the theoretical analysis of empirical estimators of the \"divergence frontier\" metric and \"frontier integral\" (scalar summary of the former). The results are sensible, though I did not follow the proof in every detail. \n\nI find the experiment section extremely difficult to understand. What is \"distribution-free bound\" and \"distribution-dependent bound (oracle bound)\"? Could you just refer to equations that appeared before? Besides, I would suggest the authors to revise the whole section and be clear about the hypothesis being checked and the conclusions drawn from the results. Currently this section only includes descriptions of Figures, mostly showing the decay of absolute error of different estimators and sample sizes. It is unclear to me how these results help justify the sample complexity in (6) and (7), nor did I see the suggested quantization level \"n^{1/3}\" play a role.\n\nAnother thing I find unclear is the definition frontier integral. It is unclear to me why there is a \\lambda and 1 - \\lambda weighting for the two terms and I have no geometric intuition about this integral. Could it be explained using Figure 1 (right)?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "RdIILF1zX3E", "reviewer": "Reviewer_cCnu", "summary": "The paper proposes the frontier integral to measure the precision and recall for evaluate the fitted density model, and provide the complexity bound  for the quantized pluged in estimator. It also shows the smoothing technique can improve the bound.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The frontier integral is a natural extension to the previously proposed \"divergence frontiers\".\n\nClarity: The paper is clearly written and well organized. \n\nQuality:\nThe complexity analysis is sound and the benefit of the smoothing technique is reasonable and intuitive.  I do agree the proposed measurement is valuable for low-dimensional problems.\n\nHowever, if the goal is to evaluate the high-dimensional image and text generative model, my major concern is the practical usefulness of the measure. \nMajor:\n1. The goal for the measure is to evaluate the generative model, which usually has high dimensions. The proposed quantization estimation is not very practical in high-dimensional space. Therefore, in practice, the author uses some pre-trained networks to project the original distribution to low dimensional space: 4d for images and 5d for text. Dimension 4 is much lower than the intrinsic dimension of the data/model distribution, which will largely underestimate (under-represent) the support of the original distribution, so will recall in the representation space will still reflect the recall in the original space? The performance seems to depend heavily on the feature extractor,  experiments need to be done to show that if the final evaluation will reflect the recall and precision in the original space.\n\n2. For the GAN model which doesn't allow a density (or when the data distribution lies on a low-dimensional manifold), the proposed measure seems no longer well-defined, so is the GAN experiment still meaningful?\n\nMinor:\nThe KL and RKL seem reasonable to measure the precession and recall due to their moment/mode-matching proterioes. What's the benefit to generalize to other f-divergence?\n\n\nSignificance: If the frontier integral is a practically significant measurement for the evaluation of the low-dimensional generative model. However, it is not clear that the proposed method is practically useful for the high-dimension model.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the limitations are mentioned in the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours "}, "extra_text": {}}, {"review_id": "P-XK2DXrZyk", "reviewer": "Reviewer_qoxT", "summary": "Inspired by the framework of divergence frontiers, the authors introduce a new \"integral summary\" called the frontier integral (FI, eqn (1)) and analyze its statistical properties for the KL case, and also briefly the more general f-divergence case. They experimentally show how traditional smoothing techniques (which help with the low-probability bins) affect the error in estimating the FI.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors start by defining the frontier integral and focus most of the paper on it. I find this confusing in that the motivation given in the abstract and the introduction is that of analyzing the frontier, but the paper mainly focuses on the quantity they have introduced. It is not clear to me how one can interpret this quantity in terms of precision / recall, or if it has any implications on them. Even if the FI is introduced solely as a theoretical gadget which would imply bounds on the precision / recall estimates, that does not seem to be the case. Just from the title I expected results that statistically compare the precision-recall curves, but I do not see anything like tha in the paper. The only connection I see is on lines 170-177, which is a result about the convergence of the KL divergence after truncation and seems like an independent result. There is further no mention of the implications of their quantization results on the estimated precision / recall. The paper could be significantly improved if the authors provide further discussion on this point. As it stands now, this makes it hard for me to evaluate the significance of the results.\n\nThe authors focus on the KL-divergence, which is absolutely fine, but then they briefly skim over possible generalization to arbitrary f-divergences (paragraph starting on line 227). If the results indeed generalize to arbitrary f-divergences, I do not understand why the authors don't present their results from that point of view. I feel that this result (if the regularity assumptions are easy to state) should be given more attention.\n\nI find it hard how to parse Theorem 2, as it assumes the discretization satisfies a bound, which one cannot guarantee in practice. You could improve it by depending perhaps explicitly on the right hand side of (5).\n\nThe authors then move on to analyze the behaviour of smoothed estimators, in particular those based on pseudo-counts. I find this particularly useful as empty bins (in P / Q) do happen in practice and smoothing is absolutely necessary. I suggest the authors to include the values of b used in the experiments together with the corresponding names of the estimators.\n\nThe experimental results are a bit hard to understand, as the Monte-Carlo estimator is competitive in many scenarios, and there is no clear order among the methods (when we also consider those in the appendix). This is not a strong criticism, high dimensional estimation is hard, it's just that I would recommend the authors to provide some rules of thumb that practicioners can apply.\n\nWhat I think would make the experimental results **really convincing** is to compute the precision-recall curves instead of the FI, and see how do the different strategies you suggest impact that. I think this should be relatively straightforward to do and would make the paper significantly stronger if improvements in FI also make the empirical precision-recall curves closer to the theoretical ones.\n\n### Minor comments\n- In l272 you claim that the bounds are divided by 100. Why is this done and what does it mean? Are you plotting bound / 100 everywhere? Should we add 2 orders of magnitude in the plots?\n- I do not understand how the text dataset is created (what are the prefixes, which distributions are being compared). Could you please elaborate more?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not mention any (negative) societal impacts of the work, but this is primarily a theoretical contribution.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission proposes a new integral summary, frontier integral, for generative model evaluation, extending on recent work on divergence frontiers. All reviewers expressed concern about high dimensions. However, the theoretical contributions are of interest to the community, the authors have addressed most concerns in the reviews, and the high-dimension issue is a limitation of most related work and not just this paper. Overall, good paper. Accept!
Decision: Accept (Poster)