Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

I 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.

Another 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)?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

The 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.

I 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).

The 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.

The 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.

What 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.

### Minor comments
- 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?
- I do not understand how the text dataset is created (what are the prefixes, which distributions are being compared). Could you please elaborate more?
limitations_and_societal_impact: The authors do not mention any (negative) societal impacts of the work, but this is primarily a theoretical contribution.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: Originality: The frontier integral is a natural extension to the previously proposed "divergence frontiers".

Clarity: The paper is clearly written and well organized. 

Quality:
The 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.

However, if the goal is to evaluate the high-dimensional image and text generative model, my major concern is the practical usefulness of the measure. 
Major:
1. 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.

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

Minor:
The 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?


Significance: 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.
limitations_and_societal_impact: Yes, the limitations are mentioned in the paper.
review_title: null

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)