Sample-Optimal Estimation of the Fréchet Inception Distance
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 [BSAG18, CF20]. We study the sample complexity n of estimating FID to error ε between d-dimensional Gaussians with bounded mean distance and covariances, when one distribution is known. Our contributions are threefold. (1) We establish tight finite-sample Θ(d2/n) bias and Θ(d/n + d2/n2) variance bounds for the empirical plug-in estimator, establishing a ≳ d2 sample complexity. (2) To debias the empirical plug-in estimator, we generalize the FID∞ estimator of [CF20] to extrapolation methods of arbitrary order k. We further prove tight bias and variance bounds of Θ((dk + 2)/(nk + 1)) and Θ(d/n + d2/n2) for any order-k extrapolation under our framework. (3) We introduce Relative Taylor Debiasing (RTD), a new, computationally efficient FID estimation algorithm using debiasing techniques inspired by U-statistics. We show that RTD achieves an O(d/ε2) sample complexity, and prove that this is optimal. We provide a complementary empirical evaluation of our new estimators. Our experiments on synthetic Gaussians validate the predicted residual bias and 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 (VALE2) uses only 10K samples to achieve accuracy comparable to FID∞ at 50K samples.
Related
- Error analysis and optimal sample allocation for randomized unbiased estimation: the single term estimator
- High-precision fault inception time detection in active distribution networks using Euclidean distance and Gaussian filtering
- Central Limit Theorems for Sample Fréchet Means of Manifold-Valued Markov Chains
- Gaussian Fluctuations of the Gradient of the Fréchet Function and Nonstandard Asymptotics of Sample Fréchet Means
- Finite-Sample Bounds for Fréchet Means of Dependent Data in Metric Spaces with Curvature Bounded Above
BibTeX
@misc{chen2026sampleoptimal,
title = {{Sample-Optimal Estimation of the Fréchet Inception Distance}},
author = {Ziyun Chen and Jerry Li and Kevin Tian and Yusong Zhu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07114},
eprint = {2610.07114},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07114},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sample-Optimal Estimation of the Fréchet Inception Distance
AU - Ziyun Chen
AU - Jerry Li
AU - Kevin Tian
AU - Yusong Zhu
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.07114
UR - https://arxiv.org/abs/2610.07114
AB - The Fréchet Inception Distance (FID) is widely used to evaluate generative models, but its empirical plug-in estimator suffers from finite-sample bias [BSAG18, CF20]. We study the sample complexity n of estimating FID to error ε between d-dimensional Gaussians with bounded mean distance and covariances, when one distribution is known. Our contributions are threefold. (1) We establish tight finite-sample Θ(d^2/n) bias and Θ(d/n + d^2/n^2) variance bounds for the empirical plug-in estimator, establishing a ≳ d^2 sample complexity. (2) To debias the empirical plug-in estimator, we generalize the FID_∞ estimator of [CF20] to extrapolation methods of arbitrary order k. We further prove tight bias and variance bounds of Θ((d^k + 2)/(n^k + 1)) and Θ(d/n + d^2/n^2) for any order-k extrapolation under our framework. (3) We introduce Relative Taylor Debiasing (RTD), a new, computationally efficient FID estimation algorithm using debiasing techniques inspired by U-statistics. We show that RTD achieves an O(d/ε^2) sample complexity, and prove that this is optimal. We provide a complementary empirical evaluation of our new estimators. Our experiments on synthetic Gaussians validate the predicted residual bias and 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 (VALE_2) uses only 10K samples to achieve accuracy comparable to FID_∞ at 50K samples.
ER -