acceptodds
Under review as a conference paper at ICLR 2027

Sample-Optimal Estimation of the Fr\'echet Inception Distance

26 views

Abstract

The Fréchet Inception Distance (FID) is widely used to evaluate generative models, but its empirical plug-in estimator suffers from finite-sample bias [BS18, CF20]. We study the sample complexity of estimating FID to error between -dimensional Gaussians with bounded mean distance and covariances, when one distribution is known. 1. We establish tight finite-sample bias and variance bounds for the empirical plug-in estimator, establishing a sample complexity. 2. To debias the empirical plug-in estimator, we generalize the estimator of [CF20] to extrapolation methods of arbitrary order . We further prove tight bias and variance bounds of and for any order- extrapolation under our framework. 3. We introduce Relative Taylor Debiasing (RTD), a new, computationally efficient FID estimation algorithm based on U-statistics. We show that RTD achieves a sample complexity, and prove that this is optimal. We provide a complementary empirical evaluation of our new estimators. Our experiments on synthetic Gaussians demonstrate the predicted residual bias and empirically support the tightness of our bounds. On ImageNet with Inception embeddings, RTD achieves the lowest mean estimation error at the standard 50K sample budget, while our second-order variance-aware extrapolation estimator () uses only 10K samples to accuracy comparable to at 50K samples. Our code is provided in the supplementary material.

Primary area:
learning theory
Keywords:
Fréchet Inception Distance, Generative Model Evaluation, Minimax Estimation

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_p24vOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the sample complexity of estimating the Frechet Inception Distance, which is widely used in generative modeling settings as a measure of discrepancy between probability distributions. The first contribution is to show that the standard plug-in estimator for the FID has a sample complexity whose leading order term is O(d2n)O(\frac{d^2}{n}), which arises from the bias. The bias is controlled by representing the empirical covariance as a random perturbation H\mathbf{H} of the population covariance and controlling the term in the error of the plug-in estimator which is nonlinear in H\mathbf{H} using its resolvent representation. The authors then study another estimator, "FID-VALE", obtained by dividing the data into independent batches, taking a convex combination of plug-in estimates for the FID score using samples from each batch, and choosing the coefficients in such a way that the higher-order terms in the bias cancel out; this is a generalization of the FID∞\textrm{FID}_{\infty}. They prove canceling the first kk terms in the bias yields an estimator with O(dk+2nk+1)O(\frac{d^{k+2}}{n^{k+1}}) sample complexity. Finally, the authors introduce a third estimator, "FID-RTD", which arises from directly estimating higher-order terms in the expansion of the nonlinear-in-H\mathbf{H} term in the plug-in estimator. FID-RTD achieves a sample complexity of O(dn)O(\sqrt{\frac{d}{n}}), which is complemented by an information-theoretic lower bound of the same order. Experiments on both Gaussian distributions and image datasets illustrate the dimensional scaling of their estimates and the improvement yielded by FID-VALE and FID-RTD.

Critical strengths

FID is used ubiquitously in the evaluation of learned generative models, and any work that improves our understanding of its finite-sample behavior and informs the design of more statistically-efficient estimation methods is of high value to the ML community. The experimental results on FID-VALE and FID-RTD suggest that the methods introduced in this paper can be of immediate use in the evaluation of generative models.

The paper addresses a notable gap in the theory literature, the results are quite impressive, and I found the proof techniques to be quite elegant. I also applaud the authors for writing such a clear exposition of their results.

Critical weaknesses

Since the analysis is specialized to the BW distance, it seems unlikely that the techniques introduced in this work can be applied more broadly to study the sample complexity of other discrepancies which depend on higher-order moments. However, this is quite a minor weakness, if one at all.

Questions for authors

I am curious whether the dimensional-dependence of the sample complexity of the various estimators analyzed in the paper can be improved if the covariances AA and BB are assumed to possess some low-complexity structure (e.g., approximately low-rank covariances, distributions supported on a low-dimensional manifold, sparse graphical models, distributions which are invariant under a group action, etc). This seems like a challenging direction, since your proofs involve controlling the bias and variance of highly nonlinear functions of Wishart matrices, but I am curious nonetheless.

Minor comments:

  • I was confused by the following sentence in Sec 1.1: "This setting is particularly natural for FID, which by its very definition as a squared Wasserstein distance between moment-matched Gaussians, assumes the image embeddings are close to a Gaussian (else measuring this distance is ill-posed)." Does this simply mean that the FID score does not define a metric between non-Gaussian distributions?
  • In Problem 1, it may be worth to briefly comment on why you focus on the 1-sample problem.
Reviewer_xGUbOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how many samples are needed to accurately estimate the Fréchet Inception Distance (FID). It shows that the empirical plug-in estimator suffers from finite-sample bias, develops a theoretical characterization of this error, and proposes two improved estimators: FID-VALE and FID-RTD. The latter achieves the information-theoretically optimal sample complexity under the paper's assumptions. It also analyzes the bound for FID$_{\infty}$.

Critical strengths
  1. The paper provides a rigorous analysis of the finite-sample bias and variance of existing FID estimators, including empirical FID and FID∞\text{FID}_{\infty}. It introduces RTD, which achieves the information-theoretically optimal sample complexity of O(d/ϵ2)O(d/\epsilon^2), supported by a matching lower bound.

  2. The paper evaluates the proposed estimators across synthetic Gaussian settings and real-world ImageNet generative models. The experiments generally support the theoretical findings.

Critical weaknesses

My main concerns are regarding the mismatch between experiments and theoretical analysis:

  1. Although VALE is introduced as a proposed estimator in the controlled Gaussian experimental setup (Line 328), Tab.2 and Fig.2 and Figs.4–7 report only OLSk\text{OLS}_k and RTD. The differences between VALE and OLS are not sufficiently clear. A comparison between VALE and OLS under the same experimental settings would help demonstrate the benefits of variance-aware weighting.

2(a). In Fig.2, OLS2\text{OLS}_2 and OLS3\text{OLS}_3 have similar trend to RTD. It makes me wonder whether RTD is preferable to OLSk\text{OLS}_k. RTD needs pilot samples (Line 293), which leads to higher computational cost. In the controlled experiments, I will expect to see the obvious advantage of RTD.

2(b). Similarly, given the close performance between FID∞\text{FID}_{\infty} and RTD in Fig.3, it would be useful to clarify why RTD provides a substantial advantage over the existing FID∞\text{FID}_{\infty} estimator.

Questions for authors

The proposed method fails at small sample sizes. It contradicts the paper's claim of sample efficiency.

1(a). In Tab.6, RTD exhibits substantial instability at small sample sizes. What is the reason? There is no failure-case analysis in the paper.

1(b). Moreover, for the controlled case, the sample size starts at 50K. Could it also fail like the ImageNet case with a size of 10K?

Reviewer_BRPpOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates the sample complexity of estimating the Fréchet Inception Distance (FID), defined as the squared 2-Wasserstein distance between Gaussian distributions fitted to image features. The analysis considers a dd-dimensional setting where the mean and covariance of the source Gaussian are known, while those of the target Gaussian are estimated from samples.

The authors first establish tight nonasymptotic bias and variance bounds for the standard plug-in FID estimator. They then generalize the previously proposed bias-corrected estimator FID∞\mathrm{FID}_\infty to higher-order extrapolation methods. In particular, they introduce Variance-Aware Linear Extrapolation (VALE), which eliminates bias terms up to order (k) while controlling variance. The resulting bias bound scales as dk+2/nk+1d^{k+2}/n^{k+1}, while the variance remains of the same order as that of the plug-in estimator.

The authors further propose Relative Taylor Debiasing (RTD), which combines higher-order Taylor expansions with U-statistics and achieves the minimax-optimal estimation rate of O(d/n)O(\sqrt{d/n}). Synthetic experiments support the theoretical bias analysis, while image experiments suggest that RTD achieves the lowest mean estimation error and that second-order extrapolation provides accuracy comparable to FID∞\mathrm{FID}_\infty with substantially fewer samples.

Critical strengths
  1. The paper provides a rigorous statistical analysis of the finite-sample behavior of the plug-in estimator for the squared 2-Wasserstein distance between Gaussian distributions. In particular, the tight bias and variance bounds help explain why the standard estimator requires a relatively large sample size for accurate estimation.
  2. A key contribution is the development of statistically efficient bias-corrected estimators, together with computational methods for implementing them. VALE extends existing extrapolation-based approaches to higher orders, while RTD achieves the minimax-optimal estimation rate. These contributions could be valuable for evaluating generative models when only limited samples are available.
Critical weaknesses
  1. Although the paper's main contributions are theoretical, the key results are not stated formally in the main text, with precise theorem statements appearing only in the appendix. Including the main guarantees and their assumptions in the main text would help readers better understand the theoretical contributions and the proposed estimators.
    • While I understand that the term "relative" in RTD refers to the construction of B~\widetilde B from pilot samples, this construction could be explained more clearly in the main text.
    • According to the bias and variance bounds in Proposition 7, the condition m≥C′(d+L)m \ge C'(d+L), for a sufficiently large constant C′C', appears necessary to control the power series following L1702. However, this requirement is not explicitly discussed in the main text. It may also help explain the relatively large estimation error of RTD when using only 10K samples in Table 6.
  2. My main concern is whether the image experiments sufficiently validate the theoretical contributions. The theoretical results focus on estimating the squared 2-Wasserstein distance between Gaussian distributions, assuming that one distribution is known. Although this quantity corresponds to FID when applied to Gaussian approximations of image features, real image feature distributions are not necessarily Gaussian. Since FID is defined through the first two moments even for non-Gaussian feature distributions, the theoretical guarantees do not automatically extend to this setting. It would be helpful to clarify the extent to which the Gaussian assumptions are essential and how the theoretical results relate to practical FID estimation. Alternatively, the paper could place greater emphasis on estimating Wasserstein distances between Gaussian distributions.
Questions for authors
  1. Second-order VALE frequently achieves lower estimation error in both the Random Gaussian Families experiment (Figure 2) and the image experiments (Tables 3 and 6). Could the authors provide some theoretical intuition for why second-order extrapolation performs particularly well? Given the consistency of this observation, it would be interesting to understand whether it reflects a favorable bias-variance tradeoff.
  2. Although RTD provides accurate estimates in challenging settings, Figure 2 shows that its errors are larger than those of VALE across nearly all dimensions. Could the authors clarify the factors contributing to this behavior, particularly the effects of the pilot sample size and truncation order? Moreover, while RTD achieves the minimax-optimal rate, I wonder whether its finite-sample performance is affected by potentially large constants in the theoretical bounds, including terms such as (d)j(d)_j arising from higher-order tensor calculations.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.