arXiv：cs.LG· Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu·· 4 小时前AI 评分41
FID 的样本最优估计：RTD 实现 O(d/ε²) 最优复杂度
Sample-Optimal Estimation of the Fr\'echet Inception Distance
AI 导读
研究者提出 Relative Taylor Debiasing（RTD）算法，将 FID 估计的样本复杂度降至 O(d/ε²) 并证明其最优。该工作还给出了经验 plug-in 估计器紧致的偏差 Θ(d²/n) 与方差 Θ(d/n + d²/n²) 界，并把 FID∞ 推广到任意 k 阶外推。
正文
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 $\epsilon$ 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 $\Theta(\frac{d^2}{n})$ bias and $\Theta(\frac{d}{n} + \frac {d^2} {n^2})$ variance bounds for the empirical plug-in estimator, establishing a $\gtrsim d^2$ sample complexity. (2) To debias the empirical plug-in estimator, we generalize the ${\rm FID}_\infty$ estimator of [CF20] to extrapolation methods of arbitrary order $k$. We further prove tight bias and variance bounds of $\Theta(\frac{d^{k + 2}}{n^{k + 1}})$ and $\Theta(\frac d n + \frac{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(\frac d {\epsilon^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$_\infty$ at 50K samples.
| Comments: | Our code is available at this https URL |
| Subjects: | Machine Learning (cs.LG); Computer Vision and Pattern Recognition (cs.CV); Data Structures and Algorithms (cs.DS); Statistics Theory (math.ST); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.07114 [cs.LG] |
| (or arXiv:2610.07114v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07114 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Yusong Zhu [view email]
[v1]
Mon, 5 Oct 2026 16:03:51 UTC (392 KB)
来源：arXiv：cs.LG · arxiv.org