# An Optimism-based Approach to Online Evaluation of Generative Models

Xiaoyan Hu  Department of Computer Science and Engineering, The Chinese
University of Hong Kong. Email Address<EMAIL_ADDRESS>Ho-
fung Leung Independent Researcher. Email Address<EMAIL_ADDRESS>Farzan Farnia11footnotemark: 1

###### Abstract

Existing frameworks for evaluating and comparing generative models typically
target an offline setting, where the evaluator has access to full batches of
data produced by the models. However, in many practical scenarios, the goal is
to identify the best model using the fewest generated samples to minimize the
costs of querying data from the models. Such an online comparison is
challenging with current offline assessment methods. In this work, we propose
an online evaluation framework to find the generative model that maximizes a
standard assessment score among a group of available models. Our method uses
an optimism-based multi-armed bandit framework to identify the model producing
data with the highest evaluation score, quantifying the quality and diversity
of generated data. Specifically, we study the online assessment of generative
models based on the Fréchet Inception Distance (FID) and Inception Score (IS)
metrics and propose the FID-UCB and IS-UCB algorithms leveraging the upper
confidence bound approach in online learning. We prove sub-linear regret
bounds for these algorithms and present numerical results on standard image
datasets, demonstrating their effectiveness in identifying the score-
maximizing generative model.

##  1 Introduction

Deep generative models have achieved astonishing results across a wide array
of machine learning datasets. Quantitative comparisons between generative
models, trained using different methods and architectures, are commonly
performed by evaluating assessment metrics such as Fréchet Inception Distance
(FID) [17] and Inception Score (IS) [37]. Due to the growing applications of
generative models to various learning tasks, the machine learning community
has continuously adapted evaluation methodologies to better suit the
characteristics of the newly introduced applications.

A common characteristic of standard evaluation frameworks for deep generative
models is their offline assessment process, which requires a full batch of
generated data for assigning scores to the models. While this offline
evaluation does not incur significant costs for moderate-sized generative
models, producing large batches of samples from large-scale models can be
costly. In particular, generating a large batch of high-resolution image or
video data could be expensive and hinder the application of existing
evaluation scores for ranking generative models.

In this work, we focus on the _online evaluation_ of generative modeling
schemes, where we consider a group of generative models and attempt to
identify the model with the best score by assessing the fewest number of
produced data. By limiting the number of generated samples in the assessment
process, online evaluation can save on the costs associated with producing
large batches of samples. Additionally, online evaluation can significantly
reduce the time and computational expenses required to identify a well-
performing model in assessing a large group of generative models.

To measure the performance of an online evaluation algorithm, we use the
regret notion widely-used in the online learning literature. In the online
learning task, the evaluation algorithm selects a generative model and
observes a mini-batch of samples generated by that model in each round. Our
goal is to minimize the algorithm’s regret, defined as the cumulative
difference between the scores of the selected models and the best possible
score from the model set. Therefore, the learner’s regret quantifies the cost
of generating samples from sub-optimal models. Our goal is to develop online
learning algorithms that result in lower regret values in the assessment of
generated data.

To address the described online evaluation of generative models, we utilize
the multi-armed bandit framework. In a standard multi-armed bandit problem,
the online learner seeks to identify the arm with the highest expected value
of a random score. While this formulation has been widely considered in many
learning settings, it cannot solve the online evaluation of generative models,
as standard IS and FID metrics do not simplify to the expectation of a random
variable and represent a non-linear function of the data distribution.

By deriving concentration bounds for the FID and IS scores, we propose the
optimism-based FID-UCB and IS-UCB algorithms to address the online assessment
of generative models. These algorithms apply the upper confidence bound (UCB)
approach using data-dependent bounds that we establish for the FID and IS
scores. Furthermore, we analytically bound the regret of the IS-UCB and FID-
UCB methods, demonstrating their sub-linear regret growth assuming a full-rank
covariance matrix of the embedded real data.

We discuss the results of several numerical applications of FID-UCB and IS-UCB
to standard image datasets and generative modeling frameworks. We compare the
performance of these algorithms with the greedy algorithm, which selects the
model with the highest estimated score, and a naive-UCB baseline that applies
the UCB algorithm with a data-independent upper confidence bound. Our
numerical results show a significant improvement in our proposed algorithms
compared to the greedy and naive-UCB baselines. Additionally, we analyze the
performance of FID-UCB with different image data embeddings, including
InceptionNet.V3 [40], CLIP [7], and DINOv2 [33]. Our empirical results
indicate satisfactory performance under these standard embeddings. The
following summarizes the main contributions of this work:

  * •

Proposing an online evaluation framework for generative models that aims to
minimize the regret of misidentifying the score-maximizing model from online
generated data.

  * •

Developing the FID-UCB and IS-UCB algorithms by applying the upper-confidence-
bound framework to our data-dependent estimation of the scores.

  * •

Proving sub-linear regret bounds for the proposed FID-UCB and IS-UCB
algorithms.

  * •

Demonstrating satisfactory empirical performance of FID-UCB and IS-UCB in
comparison to the greedy and naive-UCB baseline algorithms.

##  2 Related Work

Assessment of deep generative models. The evaluation of generative models has
been extensively studied in the literature. Several evaluation metrics are
proposed, including distance-based metrics such as Wasserstein critic [3],
Fréchet Inception Distance (FID) [17] and Kernel Inception Distance (KID) [5],
and diversity/quality-based metrics such as Precision/Recall [36, 27], density
and coverage [32], VENDI [13], and RKE [20]. In addition, the related works
develop metrics quantifying the generalizability of the generative models,
including the authenticity score [2], the FLD score [21], the Rarity score
[16], and the KEN score [45] measuring the novelty of the generated samples.
In this paper, we primarily focus on FID and Inception score, which have been
frequently used for evaluating generative models.

Role of embeddings in the quantitative evaluation results. Due to the high-
dimensionality of images, evaluation of the generated images mostly relies on
the embeddings extracted by pretrained networks on the ImageNet dataset, e.g.,
InceptionNet.V3 [40]. However, [32] shows that such pretrained-embeddings
could exhibit unexpected behaviors. Recently, several large pretrained models
have been proposed, including DINOv2 [33] and CLIP [7]. [39] shows that
DINOv2-ViT-L/14 enables more interpretable evaluation of generative models. In
addition, [28] demonstrates that FID scores computed based on the embedding
extracted by CLIP agree more with human-based assessments. In this paper, we
provide the numerical results for the mentioned embeddings extracted by
different pretrained models.

Online Learning using diversity-related evaluation metrics. Online learning is
a sequential decision-making framework where an agent aims to minimize a
cumulative loss function revealed to her sequentially. One popular setting is
the multi-armed bandit (MAB), whose study dates back to the work of [29, 41].
At each step, the agent chooses among several arms, each associated with a
reward distribution, and aims to maximize a pre-specified performance metric.
The primary concern of this body of literature considers maximizing the
expected return [1, 4, 6]. Recent works study performance metrics related to
the variance or entropy of the reward distribution, including the mean-
variance criterion [38, 47] in risk-sensitive MAB, and _informational MAB_
(IMAB) where the agent maximizes the entropy rewards [44]. However, to the
best of our knowledge, the evaluation of generative models has not been
exclusively studied in an online learning context.

Online training of generative models. Several related works focus on training
generative adversarial networks (GANs) [14] using online learning frameworks.
[15] proposes to train _semi-shallow_ GANs using the _Follow-the-Regularized-
Leader_ (FTRL) approach. [10] shows that optimistic mirror decent (OMD) can be
applied to address the limit cycling problem in training Wasserstein GANs
(WGANs). Also, the recent paper [34] studies the _no-regret_ behaviors of
large language model (LLM) agents. This reference proposes an unsupervised
training loss, whose minimization could automatically result in known no-
regret learning algorithms. On the other hand, our focus is on the evaluation
of generative models which does not concern the models’ training.

##  3 Preliminaries

###  3.1 Inception Score

Inception score (IS) is a standard metric for evaluating generative models,
defined as

$\textup{IS}:=\exp\left\\{\mathbb{E}_{X_{\textup{g}}\sim
p_{\textup{g}}}[\textup{KL}(p_{Y|X_{\textup{g}}}\|p_{Y_{\textup{g}}})]\right\\},$
(1)

where $X_{\textup{g}}\sim p_{\textup{g}}$ is a generated image,
$p_{Y|X_{\textup{g}}}$ is the conditional class distribution assigned by the
InceptionNet.V3 pretrained on ImageNet [40], and
$p_{Y_{\textup{g}}}=\mathbb{E}_{X_{\textup{g}}\sim
p_{\textup{g}}}[p_{Y|X_{\textup{g}}}]$ is the marginal class distribution.
Further, we have that
$\textup{IS}=\exp[I(X_{\textup{g}};Y_{\textup{g}})]=\exp[H(Y_{\textup{g}})-H(Y_{\textup{g}}|X_{\textup{g}})]$,
where $I(\cdot;\cdot)$ is the mutual information, and $H(\cdot)$ is the
Shannon entropy. A higher IS implies that the images generated by the model
have higher diversity, since $p_{Y_{\textup{g}}}$ would be more uniformly
distributed to increase $H(Y_{\textup{g}})$, and possess higher fidelity,
because $p_{Y|X_{\textup{g}}}$ is closer to a one-hot vector to enforce a
smaller $H(Y_{\textup{g}}|X_{\textup{g}})$.

###  3.2 Fréchet Inception Distance

Fréchet Inception Distance (FID) is another standard metric for evaluating
generative models. Let $f(x)\in{\mathbb{R}}^{d}$ denote the $d$-dimensional
feature of an image $x$, which is extracted by the InceptionNet.V3 embedding.
FID is the Fréchet distance [12] between the feature distributions of the
generated images $p_{f(X_{\textup{g}})}$ and the real images
$p_{f(X_{\textup{r}})}$, defined as

$\textup{FID}=\|\mu_{\textup{g}}-\mu_{\textup{r}}\|_{2}^{2}+\textup{Tr}[\Sigma_{\textup{g}}+\Sigma_{\textup{r}}-2(\Sigma_{\textup{g}}\Sigma_{\textup{r}})^{\frac{1}{2}}]$
(2)

assuming that
$p_{f(X_{\textup{g}})}={\mathcal{N}}(\mu_{\textup{g}},\Sigma_{\textup{g}})$
and
$p_{f(X_{\textup{r}})}={\mathcal{N}}(\mu_{\textup{r}},\Sigma_{\textup{r}})$
are Gaussian distributions.

##  4 Online Evaluation of Generative Models

In this section, we introduce the framework of online evaluation of generative
models, which is given in Protocol 1. We denote by ${\mathcal{G}}:=[G]$ the
set of generative models. For each generator $g\in[G]$, we denote by
$p_{g}\in\Delta({\mathcal{X}})$ its generative distribution over the space
${\mathcal{X}}$, which can be texts or images. Given an evaluation metric,
e.g., FID or IS, the corresponding _score_ of the generator $g\in[G]$ is
denoted by $\nu_{g}$. The evaluation proceeds in $T$ steps. At each step
$t\in[T]$, the evaluating algorithm ${\mathcal{A}}$ picks a generator
$g_{t}\in[G]$ and collects a batch of generated samples $\\{x_{t}^{j}\sim
p_{g}\\}_{j=1}^{b}$, where $b\in{\mathbb{N}}_{+}$ is the (fixed) batch size.
The evaluator aims to minimize the _regret_

$\textup{Regret}(T)=\sum_{t=1}^{T}(\nu^{*}-\nu_{g_{t}}),$ (3)

where $\nu^{*}:=\operatorname*{arg\,max}_{g\in[G]}\nu_{g}$ (if the higher the
score the better).

Regarding the challenges of online evaluation of generative models, note that
the empirical estimation of the score could be biased and generator-dependent.
In addition, the generative distribution typically lies in a high-dimensional
space, which makes it difficult to estimate the score from limited data.
Moreover, the evaluation metrics often incorporate higher-order information of
the generative distribution (e.g., computing FID requires the covariance
matrix). Hence, analyzing the concentration properties of the score estimation
would be challenging.

Protocol 1 Online Evaluation of Generative Models

0: step $T\in{\mathbb{N}}_{+}$, evaluation metric, a set
${\mathcal{G}}\leftarrow[G]$ of generators for evaluation, evaluator
${\mathcal{A}}$, batch size $b\in{\mathbb{N}}_{+}$

1: Initialize: estimated score $\widehat{\nu}_{g}$ and generated samples
${\mathcal{H}}_{g}\leftarrow\varnothing$ for each $g\in[G]$.

2: for step $t=1,2,\cdots,T$ do

3: Pick generator $g_{t}\sim{\mathcal{A}}$.

4: Generate a batch $\\{x_{t}^{j}\sim p_{g_{t}}\\}_{j=1}^{b}$ of samples from
$g_{t}$.

5: Update
${\mathcal{H}}_{g_{t}}\leftarrow{\mathcal{H}}_{g_{t}}\cup\\{x_{t}^{j}\\}_{j=1}^{b}$
and estimated score $\widehat{\nu}_{g_{t}}$.

6: end for

##  5 Online Evaluation based on Fréchet Inception Distance

In this section, we consider the online evaluation of generative models by
Fréchet Inception Distance (FID). Given $n\in{\mathbb{N}}_{+}$ generated
images $x^{1},\cdots,x^{n}\sim p_{g}$ queried from model $g$, the empirical
FID is computed by

$\widetilde{\textup{FID}}_{g}^{n}=\|\widehat{\mu}_{g}^{n}-\mu_{\textup{r}}\|_{2}^{2}+\textup{Tr}[\widehat{\Sigma}_{g}^{n}+\Sigma_{\textup{r}}-2(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}],$
(4)

where

$\widehat{\Sigma}_{g}^{n}=\frac{1}{n}\sum_{i=1}^{n}(f(x^{i})-\widehat{\mu}_{g}^{n})(f(x^{i})-\widehat{\mu}_{g}^{n})^{\top},\qquad\widehat{\mu}_{g}^{n}=\frac{1}{n}\sum_{i=1}^{n}f(x^{i})$
(5)

are the empirical covariance matrix and the mean vector, respectively, and
$f(x^{i})\in{\mathbb{R}}^{d}$ is the feature of the $i$-th generated image
which is extracted by, e.g., the InceptionNet.V3. It has been shown that the
empirical FID (4) is biased differently depending on the generator, which
makes it difficult to compare different generators for a fixed sample size
[9]. Hence, the FID-based evaluation is typically performed for a large batch
of generated samples (e.g., $10\sim 50$k) to reduce the effect of the bias,
which can be sample-inefficient and costly for a large number of generators.

To enable sample-efficient online evaluation of generative models, we adapt
the optimism-based online learning framework to the FID score. To this end, we
first derive an optimistic FID score in the following theorem. We defer the
theorem’s proof to Appendix A.1.

######  Theorem 5.1 (Generator-dependent optimistic FID score).

Assume the covariance matrix $\Sigma_{\textup{r}}\succ\bm{0}$ is positive
definite. Then, with probability at least $1-\delta$, we have

$\widehat{\textup{FID}}_{g}^{n}=\widetilde{\textup{FID}}_{g}^{n}-{\mathcal{B}}^{n}_{g}\leq\textup{FID}_{g}.$
(6)

Here, the bonus is given by

$\displaystyle{\mathcal{B}}_{g}^{n}:=$ $\displaystyle
C^{n}_{g}\cdot\sqrt{\frac{2{\mathcal{I}}_{g}}{n}}\left(32\log\left(\frac{24d}{\delta}\right)\right)^{\frac{1}{4}}+\textup{Tr}[\Sigma_{g}]\sqrt{\frac{8}{n}\log\left(\frac{6d}{\delta}\right)}$
(7)
$\displaystyle+\textup{Tr}[\Sigma_{\textup{r}}^{\frac{1}{2}}]\sqrt{8\left(20\sigma_{g}^{2}\|\Sigma_{g}\|_{2}\sqrt{\frac{4\bm{r}(\Sigma_{g})+\log(3/\delta)}{n}}+\frac{2{\mathcal{I}}_{g}}{n}\sqrt{32\log\left(\frac{24d}{\delta}\right)}\right)},$

where
$C_{g}^{n}:=2(\|\mu_{g}-\mu_{\textup{r}}\|_{2}+\|\mu_{g}-\widehat{\mu}_{g}^{n}\|_{2}+\frac{1}{n}\sum_{i=1}^{n}\|f(x^{i})-\widehat{\mu}_{g}^{n}\|_{2})$,
${\mathcal{I}}_{g}:=\sum_{j=1}^{d}\sum_{l=1}^{d}|\Sigma_{g}[l,j]|$, and
$\bm{r}(\Sigma_{g}):=\frac{\textup{Tr}[\Sigma_{g}]}{\|\Sigma_{g}\|_{2}}$.

Algorithm 1 FID-UCB for Generative Model Evaluation

0: steps $T$, set of generative models ${\mathcal{G}}\leftarrow[G]$,
$\mu_{\textup{r}}$ and $\Sigma_{\textup{r}}$ of the real images, failure
probability $\delta$, batch size $b$, bonus function
$\\{{\mathcal{B}}^{n}_{g}\\}_{g\in[G]}$ given by Equation (7).

1: Initialize:
$\widehat{\textup{FID}}_{g}\leftarrow-\infty,{\mathcal{H}}_{g}\leftarrow\varnothing,n_{g}\leftarrow
0$ for each $g\in[G]$.

2: for step $t=1,2,\cdots,T$ do

3: Pick model
$g_{t}\leftarrow\operatorname*{arg\,min}_{g\in{\mathcal{G}}}\widehat{\textup{FID}}_{g}$.

4: Model $g_{t}$ generates batch samples $\\{x_{t}^{j}\in{\mathbb{R}}^{D}\sim
g_{t}\\}_{j=1}^{b}$.

5: Update
${\mathcal{H}}_{g_{t}}\leftarrow{\mathcal{H}}_{g_{t}}\cup\\{f(x_{t}^{j})\\}_{j=1}^{b}$
and visitation $n_{g_{t}}\leftarrow n_{g_{t}}+b$.

6: Update $\widehat{\mu}_{g_{t}}$ and $\widehat{\Sigma}_{g_{t}}$.

7: Compute the optimistic FID score
$\displaystyle\widehat{\textup{FID}}_{g_{t}}\leftarrow\|\widehat{\mu}_{g_{t}}-\mu_{\textup{r}}\|_{2}^{2}+\textup{Tr}\left[\widehat{\Sigma}_{g_{t}}+\Sigma_{\textup{r}}-2(\widehat{\Sigma}_{g_{t}}\Sigma_{\textup{r}})^{\frac{1}{2}}\right]-{\mathcal{B}}_{g_{t}}^{n_{g_{t}}}.$

8: end for

We remark that the bonus term (7) is: 1) _generator-dependent_ through
parameters including ${\mathcal{I}}_{g}$, $\sigma_{g}^{2}$,
$\textup{Tr}[\Sigma_{g}]$, and $\|\Sigma_{g}\|_{2}$, 2) _dimension-free_ in
the sense that the dimension $d$ only appears in the logarithmic term, which
facilitates a sample-efficient evaluation. In practice, these parameters can
be estimated from the queried data.

Based on Theorem 5.1, we propose FID-UCB in Algorithm 1 as an FID-based online
evaluation algorithm. At the beginning, the estimated FID scores are
initialized to be negative infinity (line 1), and hence each generator is
explored for at least one time. The evaluation proceeds iterative, where at
each iteration $t\in[T]$, the evaluator picks model $g_{t}$ with the lowest
estimated FID and queries a batch of images from the model (lines $3\sim 4$).
Then, the estimated FID of generator $g_{t}$ is updated (lines $5\sim 7$).
Next, we show that FID-UCB attains sub-linear regret bound. We defer the
theorem’s proof to Appendix A.2.

######  Theorem 5.2 (Regret of FID-UCB).

Under the same conditions in Theorem A.1, with probability at least
$1-\delta$, the regret of the UCB-FID algorithm after $T$ steps is bounded by

$\widetilde{O}\left(\max_{g}\left\\{G\cdot{\mathcal{I}}_{g}\cdot\log(T),\sqrt{G({\mathcal{I}}_{g}+\textup{Tr}[\Sigma_{g}])T},(\textup{Tr}[\Sigma_{\textup{r}}^{\frac{1}{2}}]\cdot\sigma_{g}\|\Sigma_{g}\|_{2}^{\frac{1}{2}}\bm{r}^{\frac{1}{4}}(\Sigma_{g}))\cdot
G^{\frac{1}{4}}T^{\frac{3}{4}}\right\\}\right),$ (8)

where logarithmic factors are hidden in the notation $\widetilde{O}(\cdot)$.

##  6 Online Evaluation based on Inception Score

In this section, we focus on evaluating generative models by Inception score
(IS), which is given by $\textup{IS}=\exp[I(X_{g};Y_{g})]$, where $X_{g}\sim
p_{g}$ is the generated image, and $Y_{g}$ is the class assigned by the
InceptionNet.V3. Given $n\in{\mathbb{N}}_{+}$ generated images
$x^{1},\cdots,x^{n}\sim p_{g}$ queried from a generator $g$, the empirical IS
is computed by

$\widetilde{\textup{IS}}_{g}^{n}=\exp\left\\{\widehat{H}^{n}(Y_{g})-\widehat{H}^{n}(Y_{g}|X_{g})\right\\},$
(9)

where

$\widehat{H}^{n}(Y_{g})=H\left(\frac{1}{n}\sum_{i=1}^{n}p_{Y|x^{i}}\right),\
\widehat{H}^{n}(Y_{g}|X_{g})=\frac{1}{n}\sum_{i=1}^{n}H(Y|x^{i}),$ (10)

are the empirical entropy of the marginal $d$-class distribution $p_{Y_{g}}$
and the conditional $d$-class distribution $p_{Y|X_{g}}$ ($d=1000$ for
InceptionNet.V3).

For any $j\in[d]$, let
$\widehat{V}^{n}(p_{Y|X_{g}}[j]):={\mathbb{V}}(p_{Y|x^{1}}[j],\cdots,p_{Y|x^{n}}[j])$
denote the sample variance for the probability that the generated sample is
assigned to the $j$-th class. To derive an optimistic IS, we first define the
_optimistic marginal class distribution_ denoted by

$\widehat{p}_{Y_{g}}^{n}:=\textup{Clip}_{e^{-1}}(\widetilde{p}^{n}_{Y_{g}},\bm{\epsilon}^{n}_{g})$
(11)

where $\bm{\epsilon}^{n}_{g}\in{\mathbb{R}}_{+}^{d}$ is a $d$-dimensional
vector whose $j$-th element is given by

$\bm{\epsilon}^{n}_{g}[j]:=\sqrt{\frac{2\widehat{V}^{n}(p_{Y|X_{g}}[j])}{n}\log\left(\frac{4d}{\delta}\right)}+\frac{7}{3(n-1)}\log\left(\frac{4d}{\delta}\right),$
(12)

and $\textup{Clip}_{e^{-1}}(p,\bm{\epsilon})$ is the following element-wise
operator

$\begin{cases}p[j]+\frac{e^{-1}-p[j]}{|e^{-1}-p[j]|}\bm{\epsilon}[j]&\textup{,
if }|e^{-1}-p[j]|\geq\bm{\epsilon}[j]\\\ e^{-1}&\textup{,
otherwise.}\end{cases}$ (13)

The optimistic marginal class distribution ensures that
${\mathcal{E}}(\widehat{p}_{Y_{g}}^{n}):=-\sum_{j}\widehat{p}_{Y_{g}}^{n}[j]\cdot\log(\widehat{p}_{Y_{g}}^{n}[j])\geq
H(Y_{g})$ with high probability (see Lemma B.1 in the Appendix B.3). Next, we
derive a generator-dependent optimistic IS in the following theorem. We defer
the theorem’s proof to Appendix B.1.

######  Theorem 6.1 (Generator-dependent Optimistic IS).

Let

$\widehat{\textup{IS}}^{n}_{g}:=\exp\left\\{{\mathcal{E}}\left(\widehat{p}_{Y_{g}}^{n}\right)-\widehat{H}^{n}(Y_{g}|X_{g})+\sqrt{\frac{2\widehat{V}^{n}(H(Y_{g}|X_{g}))}{n}\log\left(\frac{4}{\delta}\right)}+\frac{7C^{\prime}}{3(n-1)}\log\left(\frac{4}{\delta}\right)\right\\},$
(14)

where $\widehat{H}^{n}(Y_{g}|X_{g})$ is defined in Equation (10),
$\widehat{p}_{Y_{g}}^{n}$ the optimistic marginal class distribution (11),
parameter $C^{\prime}$ satisfies that $P(|H(Y_{g}|X_{g})|\leq C^{\prime})=1$,
and
$\widehat{V}^{n}(H(Y_{g}|X_{g}))={\mathbb{V}}(H(Y|x^{1}),\cdots,H(Y|x^{n}))$
is the empirical variance for the entropy of the conditional class
distribution. Then, with probability at least $1-\delta$, we have that
$\widehat{\textup{IS}}^{n}_{g}\geq\textup{IS}_{g}$.

0: steps $T$, set of generative models ${\mathcal{G}}\leftarrow[G]$, batch
size $b\in{\mathbb{N}}_{+}$, failure probability $\delta$, parameter
$C^{\prime}\geq\max_{g\in[G]}|H(Y|X_{g})|$.

1: Initialize:
$\widehat{\textup{IS}}_{g}\leftarrow\infty,\widehat{H}(Y_{g}|X_{g})\leftarrow
0,\widetilde{p}_{Y_{g}}\leftarrow\bm{0}^{d},n_{g}\leftarrow 0$ for each
$g\in[G]$.

2: for step $t=1,2,\cdots,T$ do

3: Pick model
$g_{t}\leftarrow\operatorname*{arg\,max}_{g\in{\mathcal{G}}}\widehat{\textup{IS}}_{g}$.

4: Model $g_{t}$ generates batch samples $\\{x_{t}^{j}\sim
p_{g_{t}}\\}_{j=1}^{b}$.

5: Update
$\displaystyle\widetilde{p}_{Y_{g_{t}}}\leftarrow\frac{N_{g}\cdot\widetilde{p}_{Y_{g}}+\sum_{j=1}^{b}p_{Y|x_{t}^{i}}}{n_{g_{t}}+b},\
\widehat{H}(Y_{g_{t}}|X_{g_{t}})\leftarrow\frac{N_{g}\cdot\widehat{H}(Y_{g_{t}}|X_{g_{t}})+\sum_{j=1}^{b}H(Y|x_{t}^{i})}{n_{g_{t}}+b}.$

6: Update visitation $N_{g_{t}}\leftarrow N_{g_{t}}+b$.

7: Update the empirical variances $\widehat{V}(H(Y_{g_{t}}|X_{g_{t}}))$ and
$\widehat{V}(p_{Y|X_{g_{t}}}[j])$ for any $j\in[d]$.

8: Compute the estimated IS according to Equation (14).

9: end for

Algorithm 2 IS-UCB for Generative Model Evaluation

Based on Theorem 6.1, we propose IS-UCB in Algorithm 2, an optimism-based
online IS evaluation algorithm. In the following theorem, we derive the regret
bound of the IS-UCB algorithm, which shows that IS-UCB attains
$\widetilde{O}(\sqrt{T})$ regret. We present the theorem’s proof in Appendix
B.2.

######  Theorem 6.2 (Regret of IS-UCB).

With probability at least $1-\delta$, the regret of the IS-UCB algorithm after
$T$ steps is bounded by

$\textup{Regret}(T)\leq\widetilde{O}\left(e^{C}\cdot\max\left\\{dm,\left(\frac{d\log
d}{4}\right)^{2}\right\\}\sqrt{T}+dG\Delta^{-2}\log d\right),$ (15)

where $C:=O(de^{-1}+C^{\prime})$ is the upper bound of
$\widehat{\textup{IS}}_{g}^{n}$,
$m:=\max_{g\in[G],j\in[d]:p_{Y_{g}}[j]>0}\\{|u^{\prime}(p_{Y_{g}}[j])|\\}$,
$\Delta:=\min_{g\in[G],j\in[d]:p_{Y_{g}}[j]\neq
e^{-1}}\\{|p_{Y_{g}}[j]-e^{-1}|\\}$, and $u(x)=-x\log x$.

##  7 Experimental Results

Baseline methods. For both FID-based and IS-based evaluation, we compare the
performance of our proposed FID-UCB and IS-UCB with the following two
baselines, _naive-UCB_ and the _greedy algorithm_. Naive-UCB is a
simplification of FID-UCB and IS-UCB which is based on data-independent
dimension-based concentration bounds, which do not exploit the generated data
in evaluating the confidence bound. We present the exact estimators in
Appendix D. On the other hand, the greedy algorithm always picks the generator
with the lowest empirical FID (4) or the highest empirical IS (9). For all
these algorithms, we initialize the estimated FID to be $-\infty$ and the
estimated IS to be $+\infty$, and hence each generator will be explored at
least once.

Datasets and generators. We evaluate the above algorithms on standard image
datasets, including CIFAR10 [26], ImageNet [11], FFHQ [24], and AFHQ [8]. For
the first three datasets, we consider the evaluation of five pretrained
generative models/generated image data, i.e., $G=5$.111Pretrained models are
downloaded from the StudioGAN repository [22] (licensed under MIT license
(MIT)): https://github.com/POSTECH-CVLab/PyTorch-StudioGAN. Generated image
datasets are downloaded from dgm-eval repository [39] (licensed under MIT
license (MIT)): https://github.com/layer6ai-labs/dgm-eval. More details can be
found in Appendix D. For the FFHQ and AFHQ datasets, we consider the
evaluation of the variance-controlled generators. We synthesize $G=20$
generators based on the pretrained StyleGAN2-ADA model [23], which is
downloaded from the official repository (licensed under Nvidia Source Code
License).222https://github.com/NVlabs/stylegan2-ada-pytorch We apply the
standard truncation technique [27] to the random noise, where the truncation
parameters vary from 0.01 to 0.1. A small (great) truncation parameter can
lead to generated samples with low (high) diversity but high (low) quality.

Experimental setup and performance metrics. We report three performance
metrics at each step $t\in[T]$: 1) _total regret_ , i.e.,
$\textup{Regret}(t)$, 2) _average regret_ , i.e.,
$(1/t)\cdot\textup{Regret}(t)$, and 3) _optimal pick ratio_ , i.e., the ratio
$(1/t)\cdot\sum_{i=1}^{t}\bm{1}(g_{t}=g^{*})$ of picking the optimal model,
which has the lowest empirical FID score or the highest empirical IS score for
50k generated images. For all the experiments, we use a batch size of 5, and
the total evaluation step is $T=1,000$. Hence the total generated samples for
each trial is $5$k. Results are averaged over 20 trials. Due to the limited
space, we postpone parts of the results to Appendix C.

###  7.1 Empirical Results of Online FID-based Evaluation

Performance on pretrained generators under different embeddings. The results
are summarized in Figure 1, where each row and each column correspond to one
dataset and one performance metric, respectively. The results show that FID-
UCB (blue) outperforms naive-UCB (orange) and the greedy algorithm (green). We
observe that naive-UCB fails to distinguish between different generators and
makes uniform selections on the CIFAR10 and the ImageNet datasets, while FID-
UCB recognizes the optimal one. This shows that the generator-dependent
optimistic FID (6) can better exploit the properties of the generator, which
is key to the sample-efficient online evaluation. On the FFHQ dataset, all the
generators attain very similar FID scores (the largest gap is less than 0.7),
which may explain why FID-UCB has a similar performance to naive-UCB. We reran
these experiments using DINOv2-ViT-L/14-based [33] and CLIP-based [7]
embeddings. (The results are summarized in Figures 5 and 6 in Appendix C,
respective.) The numerical results show that FID-UCB can maintain satisfactory
performance over different embeddings.

CIFAR10 (G=5)

ImageNet (G=5)

FFHQ (G=5) Total regret Average regret Optimal pick ratio

Figure 1: Performance of FID-UCB, naive-UCB, and the greedy algorithm on
various datasets. The embeddings of the images are extracted by the pretrained
InceptionNet.V3.

Performance on variance-controlled generators. We summarize the results in
Figure 2. FID-UCB (blue) significantly outperforms naive-UCB and the greedy
algorithm. The results for DINOv2-based and CLIP-based FID are provided in
Figures 5 and 6 in Appendix C. We ran the evaluation on AFHQ Dog dataset, and
the results are presented in Figure 7 in the Appendix. Furthermore, we display
the generated images to visualize the quality and diversity of the samples
queried by different algorithms. The results suggest that FID-UCB consistently
queries images that are diverse and of high quality. In contrast, naive-UCB
kept querying a proportion of images from the collapsed generator (the one
with the smallest truncation parameter), and the greedy algorithm even stuck
to it.

FFHQ (G=20)

Figure 2: Performance of FID-UCB, naive-UCB, and the greedy algorithm for
evaluating the variance-controlled generators on the FFHQ dataset.

Step 500

Step 1000 FID-UCB Naive UCB Greedy

###  7.2 Results of Online IS-Based Evaluation

Performance on the pretrained generators. The results are summarized in Figure
3. IS-UCB (blue) attains significantly better performance than naive-UCB
(orange) and the greedy algorithm (green) on CIFAR10 and FFHQ datasets.

CIFAR10 (G=5)

Figure 3: Performance of IS-UCB, naive-UCB, and the greedy algorithm on
various datasets.

ImageNet (G=5)

FFHQ (G=5) Total regret Average regret Optimal pick ratio

Performance on variance-controlled generators. The results are summarized in
Figure 4. Generated samples are plotted in Figure 8 in the Appendix. The
results on the AFHQ Dog dataset are presented in Figure 9 in the Appendix.

FFHQ (G=20)

Figure 4: Performance of IS-UCB, naive-UCB, and the greedy algorithm for
evaluating the variance-controlled generators on the FFHQ dataset.

##  8 Conclusion

In this work, we studied an online learning problem aiming to identify the
generative model with the best evaluation score among a set of models. We
proposed the optimism-based FID-UCB and IS-UCB algorithms to address the
online learning task and showed satisfactory numerical results for their
application to image-based generative models. An interesting future direction
to our work is to explore the application of other online learning frameworks,
such as Thompson sampling, to address the online evaluation problem. Also,
while we mostly focused on standard image datasets for testing the proposed
algorithms, the application of the proposed FID-UCB and IS-UCB to text-based
and video-based generative models will be interesting for future studies. Such
an application only requires applying text and video-based embeddings, as in
Video IS [35], FVD [42], and FTD [19].

## References

  * Agrawal [1995] Rajeev Agrawal.  Sample mean based index policies with o(log n) regret for the multi-armed bandit problem.  _Advances in Applied Probability_ , 27(4):1054–1078, 1995.  ISSN 00018678.  URL http://www.jstor.org/stable/1427934.
  * Alaa et al. [2022] Ahmed Alaa, Boris Van Breugel, Evgeny S. Saveliev, and Mihaela van der Schaar.  How faithful is your synthetic data? Sample-level metrics for evaluating and auditing generative models.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 290–306. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/alaa22a.html.
  * Arjovsky et al. [2017] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In Doina Precup and Yee Whye Teh, editors, _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 214–223. PMLR, 06–11 Aug 2017.  URL https://proceedings.mlr.press/v70/arjovsky17a.html.
  * Auer [2003] Peter Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _J. Mach. Learn. Res._ , 3(null):397–422, mar 2003.  ISSN 1532-4435.
  * Bińkowski et al. [2018] Mikołaj Bińkowski, Dougal J. Sutherland, Michael Arbel, and Arthur Gretton.  Demystifying MMD GANs.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=r1lUOzWCW.
  * Bubeck and Cesa-Bianchi [2012] Sébastien Bubeck and Nicolò Cesa-Bianchi.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems, 2012.
  * Cherti et al. [2023] Mehdi Cherti, Romain Beaumont, Ross Wightman, Mitchell Wortsman, Gabriel Ilharco, Cade Gordon, Christoph Schuhmann, Ludwig Schmidt, and Jenia Jitsev.  Reproducible scaling laws for contrastive language-image learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2818–2829, 2023.
  * Choi et al. [2020] Yunjey Choi, Youngjung Uh, Jaejun Yoo, and Jung-Woo Ha.  Stargan v2: Diverse image synthesis for multiple domains.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020.
  * Chong and Forsyth [2020] Min Jin Chong and David Forsyth.  Effectively unbiased fid and inception score and where to find them, 2020.
  * Daskalakis et al. [2018] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.  Training GANs with optimism.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=SJJySbbAZ.
  * Deng et al. [2009] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  ImageNet: A Large-Scale Hierarchical Image Database.  In _CVPR09_ , 2009.
  * Dowson and Landau [1982] D.C Dowson and B.V Landau.  The fréchet distance between multivariate normal distributions.  _Journal of Multivariate Analysis_ , 12(3):450–455, 1982.  ISSN 0047-259X.  doi: https://doi.org/10.1016/0047-259X(82)90077-X.  URL https://www.sciencedirect.com/science/article/pii/0047259X8290077X.
  * Friedman and Dieng [2023] Dan Friedman and Adji Bousso Dieng.  The vendi score: A diversity evaluation metric for machine learning.  _Transactions on Machine Learning Research_ , 2023.  ISSN 2835-8856.  URL https://openreview.net/forum?id=g97OHbQyk1.
  * Goodfellow et al. [2014] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 27. Curran Associates, Inc., 2014.  URL https://proceedings.neurips.cc/paper_files/paper/2014/file/5ca3e9b122f61f8f06494c97b1afccf3-Paper.pdf.
  * Grnarova et al. [2018] Paulina Grnarova, Kfir Y Levy, Aurelien Lucchi, Thomas Hofmann, and Andreas Krause.  An online learning approach to generative adversarial networks.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=H1Yp-j1Cb.
  * Han et al. [2023] Jiyeon Han, Hwanil Choi, Yunjey Choi, Junho Kim, Jung-Woo Ha, and Jaesik Choi.  Rarity score : A new metric to evaluate the uncommonness of synthesized images.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=JTGimap_-F.
  * Heusel et al. [2017] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/file/8a1d694707eb0fefe65871369074926d-Paper.pdf.
  * Hoeffding [1963] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  _Journal of the American Statistical Association_ , 58(301):13–30, 1963.  ISSN 01621459.  URL http://www.jstor.org/stable/2282952.
  * Iyer and Hou [2023] Srikrishna Iyer and Teng Teck Hou.  Gat-gan : A graph-attention-based time-series generative adversarial network, 2023.
  * Jalali et al. [2023] Mohammad Jalali, Cheuk Ting Li, and Farzan Farnia.  An information-theoretic evaluation of generative models in learning multi-modal distributions.  In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, _Advances in Neural Information Processing Systems_ , volume 36, pages 9931–9943. Curran Associates, Inc., 2023.  URL https://proceedings.neurips.cc/paper_files/paper/2023/file/1f5c5cd01b864d53cc5fa0a3472e152e-Paper-Conference.pdf.
  * Jiralerspong et al. [2023] Marco Jiralerspong, Joey Bose, Ian Gemp, Chongli Qin, Yoram Bachrach, and Gauthier Gidel.  Feature likelihood score: Evaluating the generalization of generative models using samples.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=l2VKZkolT7.
  * Kang et al. [2023] MinGuk Kang, Joonghyuk Shin, and Jaesik Park.  StudioGAN: A Taxonomy and Benchmark of GANs for Image Synthesis.  _IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI)_ , 2023.
  * Karras et al. [2020] Tero Karras, Miika Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila.  Training generative adversarial networks with limited data.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 12104–12114. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/8d30aa96e72440759f74bd2306c1fa3d-Paper.pdf.
  * Kazemi and Sullivan [2014] Vahid Kazemi and Josephine Sullivan.  One millisecond face alignment with an ensemble of regression trees.  In _2014 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 1867–1874, 2014.  doi: 10.1109/CVPR.2014.241.
  * Koltchinskii and Lounici [2017] Vladimir Koltchinskii and Karim Lounici.  Concentration inequalities and moment bounds for sample covariance operators.  _Bernoulli_ , 23(1):110 – 133, 2017.  doi: 10.3150/15-BEJ730.  URL https://doi.org/10.3150/15-BEJ730.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Kynkäänniemi et al. [2019] Tuomas Kynkäänniemi, Tero Karras, Samuli Laine, Jaakko Lehtinen, and Timo Aila.  Improved precision and recall metric for assessing generative models.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/0234c510bc6d908b28c70ff313743079-Paper.pdf.
  * Kynkäänniemi et al. [2023] Tuomas Kynkäänniemi, Tero Karras, Miika Aittala, Timo Aila, and Jaakko Lehtinen.  The role of imagenet classes in fréchet inception distance.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=4oXTQ6m_ws8.
  * Lai and Robbins [1985] T.L Lai and Herbert Robbins.  Asymptotically efficient adaptive allocation rules.  _Advances in Applied Mathematics_ , 6(1):4–22, 1985.  ISSN 0196-8858.  doi: https://doi.org/10.1016/0196-8858(85)90002-8.  URL https://www.sciencedirect.com/science/article/pii/0196885885900028.
  * Lounici [2014] Karim Lounici.  High-dimensional covariance matrix estimation with missing observations.  _Bernoulli_ , 20(3):1029–1058, 2014.  ISSN 13507265.  URL http://www.jstor.org/stable/42919424.
  * Maurer and Pontil [2009] Andreas Maurer and Massimiliano Pontil.  Empirical bernstein bounds and sample variance penalization, 2009.
  * Naeem et al. [2020] Muhammad Ferjad Naeem, Seong Joon Oh, Youngjung Uh, Yunjey Choi, and Jaejun Yoo.  Reliable fidelity and diversity metrics for generative models.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 7176–7185. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/naeem20a.html.
  * Oquab et al. [2024] Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, Mahmoud Assran, Nicolas Ballas, Wojciech Galuba, Russell Howes, Po-Yao Huang, Shang-Wen Li, Ishan Misra, Michael Rabbat, Vasu Sharma, Gabriel Synnaeve, Hu Xu, Hervé Jegou, Julien Mairal, Patrick Labatut, Armand Joulin, and Piotr Bojanowski.  Dinov2: Learning robust visual features without supervision, 2024.
  * Park et al. [2024] Chanwoo Park, Xiangyu Liu, Asuman Ozdaglar, and Kaiqing Zhang.  Do llm agents have regret? a case study in online learning and games, 2024.
  * Saito et al. [2020] Masaki Saito, Shunta Saito, Masanori Koyama, and Sosuke Kobayashi.  Train sparsely, generate densely: Memory-efficient unsupervised training of high-resolution temporal gan.  _International Journal of Computer Vision_ , 128(10–11):2586–2606, May 2020.  ISSN 1573-1405.  doi: 10.1007/s11263-020-01333-y.  URL http://dx.doi.org/10.1007/s11263-020-01333-y.
  * Sajjadi et al. [2018] Mehdi S. M. Sajjadi, Olivier Bachem, Mario Lucic, Olivier Bousquet, and Sylvain Gelly.  Assessing generative models via precision and recall.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper_files/paper/2018/file/f7696a9b362ac5a51c3dc8f098b73923-Paper.pdf.
  * Salimans et al. [2016] Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, Xi Chen, and Xi Chen.  Improved techniques for training gans.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 29. Curran Associates, Inc., 2016.  URL https://proceedings.neurips.cc/paper_files/paper/2016/file/8a3363abe792db2d8761d6403605aeb7-Paper.pdf.
  * Sani et al. [2012] Amir Sani, Alessandro Lazaric, and Rémi Munos.  Risk-aversion in multi-armed bandits.  In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.  URL https://proceedings.neurips.cc/paper_files/paper/2012/file/83f2550373f2f19492aa30fbd5b57512-Paper.pdf.
  * Stein et al. [2023] George Stein, Jesse Cresswell, Rasa Hosseinzadeh, Yi Sui, Brendan Ross, Valentin Villecroze, Zhaoyan Liu, Anthony L Caterini, Eric Taylor, and Gabriel Loaiza-Ganem.  Exposing flaws of generative model evaluation metrics and their unfair treatment of diffusion models.  In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, _Advances in Neural Information Processing Systems_ , volume 36, pages 3732–3784. Curran Associates, Inc., 2023.  URL https://proceedings.neurips.cc/paper_files/paper/2023/file/0bc795afae289ed465a65a3b4b1f4eb7-Paper-Conference.pdf.
  * Szegedy et al. [2016] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 2818–2826, 2016.  doi: 10.1109/CVPR.2016.308.
  * Thompson [1933] William R. Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3/4):285–294, 1933.  ISSN 00063444.  URL http://www.jstor.org/stable/2332286.
  * Unterthiner et al. [2019] Thomas Unterthiner, Sjoerd van Steenkiste, Karol Kurach, Raphaël Marinier, Marcin Michalski, and Sylvain Gelly.  FVD: A new metric for video generation, 2019.  URL https://openreview.net/forum?id=rylgEULtdN.
  * Wainwright [2019] Martin J. Wainwright.  _High-Dimensional Statistics: A Non-Asymptotic Viewpoint_.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
  * Weinberger and Yemini [2023] Nir Weinberger and Michal Yemini.  Multi-armed bandits with self-information rewards.  _IEEE Transactions on Information Theory_ , 69(11):7160–7184, 2023.  doi: 10.1109/TIT.2023.3299460.
  * Zhang et al. [2024] Jingwei Zhang, Cheuk Ting Li, and Farzan Farnia.  An interpretable evaluation of entropy-based novelty of generative models.  In _International Conference on Machine Learning (ICML 2024)_ , 2024.
  * Zhivotovskiy [2022] Nikita Zhivotovskiy.  Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle, 2022.
  * Zhu and Tan [2020] Qiuyu Zhu and Vincent Tan.  Thompson sampling algorithms for mean-variance bandits.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 11599–11608. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/zhu20d.html.

##  Appendix A Proofs in Section 5: FID Evaluation

###  A.1 Proof of Theorem 5.1: Optimistic FID Score

###### Proof.

The proof of Theorem 5.1 is based on Theorem A.1 and Lemma A.2 in the
Appendix. Specifically, Inequality (16) in Theorem A.1 in Appendix A.3
decomposes the estimation error of the empirical FID score (4) into the errors
in estimating the mean (i.e., $\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}$) and the
covariance matrix (i.e., $\|\widehat{\Sigma}_{g}^{n}-\Sigma_{g}\|_{2}$). Next,
Lemma A.2 in Appendix A.4 derives generator-dependent concentration errors for
the mean and the covariance matrix. Combining ∎

###  A.2 Proof of Theorem 5.2: Regret of FID-UCB

###### Proof.

Recall that $g_{t}$ denotes the generator picked at the $t$-th step. For
convenience, we denote by $\widehat{\textup{FID}}_{g_{t}}$ the optimistic FID
of generator $g_{t}$ computed at step $t$. We denote by $n_{t}$ the _number of
images_ generated by model $g_{t}$ after $t$ steps. First, by Theorem A.2 and
a union bound over $T$ steps, with probability at least $1-\delta$, we have
that $\textup{FID}_{g}\geq\widehat{\textup{FID}}_{g}$ for any step $t\in[T]$
and $g\in[G]$. Hence, we have that

$\textup{Regret}(T)=\sum_{t=1}^{T}\left(\textup{FID}_{g_{t}}-\textup{FID}^{*}\right)\leq\sum_{t=1}^{T}\left(\textup{FID}_{g_{t}}-\widehat{\textup{FID}}_{g_{t}}\right).$

By the definition of $\widehat{\textup{FID}}_{g_{t}}$, we further derive that

$\displaystyle\textup{Regret}(T)\leq$
$\displaystyle\sum_{t=1}^{T}\left(\textup{FID}_{g_{t}}-\widetilde{\textup{FID}}_{g_{t}}^{n_{t}}+{\mathcal{B}}^{n_{t}}_{g_{t}}\right)\leq
2\sum_{t=1}^{T}{\mathcal{B}}^{n_{t}}_{g_{t}},$

where ${\mathcal{B}}^{n}_{g}$ is the bonus function given by Equation (7).
Therefore, the regret is further bounded by

$\displaystyle\widetilde{O}\left(\max_{g}\left\\{G\cdot{\mathcal{I}}_{g}\cdot\log(T),\sqrt{G({\mathcal{I}}_{g}+\textup{Tr}[\Sigma_{g}])\cdot
T},(\textup{Tr}[\Sigma_{\textup{r}}^{\frac{1}{2}}]\cdot\sigma_{g}\|\Sigma_{g}\|_{2}^{\frac{1}{2}}\bm{r}^{\frac{1}{4}}(\Sigma_{g}))\cdot
G^{\frac{1}{4}}T^{\frac{3}{4}}\right\\}\right),$

where logarithmic factors are hidden in the notation $\widetilde{O}(\cdot)$.
Here, we use the fact that

$\displaystyle\sum_{t=1}^{T}\frac{1}{n_{t}^{\alpha}}\leq\frac{(2b)^{\alpha}}{1-\alpha}\sum_{g=1}^{G}(n_{g}(T))^{1-\alpha}\leq\frac{(2b)^{\alpha}}{1-\alpha}G^{\alpha}T^{1-\alpha}\text{,
where }0\leq\alpha<1,$ $\displaystyle\sum_{t=1}^{T}\frac{1}{n_{t}}\leq
2b\sum_{g=1}^{G}\log(n_{g}(T))\leq 2bG\log(T),$

where $b$ is the batch size, and $n_{g}(T)$ is the number of images generated
by model $g$ at the last step $T$. ∎

###  A.3 Concentration of Empirical FID (4)

######  Theorem A.1 (Concentration of empirical FID (4)).

Assume the covariance matrix $\Sigma_{\textup{r}}\succ\bm{0}$ is positive
strictly definite, and we denote by
$\Sigma_{\textup{r}}=Q_{\textup{r}}^{\top}\Lambda_{\textup{r}}Q_{\textup{r}}$
its eigendecomposition. Then, with probability at least $1-\frac{\delta}{3}$,
we have that

$\displaystyle\left|\widetilde{\textup{FID}}_{g}^{n}-\textup{FID}_{g}\right|\leq$
$\displaystyle\underbrace{(\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}+2\|\mu_{g}-\mu_{\textup{r}}\|_{2})\cdot\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}}_{\text{(1)
error of
$\|\widehat{\mu}_{g}^{n}-\mu_{\textup{r}}\|_{2}^{2}$}}+\underbrace{\textup{Tr}[\Sigma_{\textup{r}}^{\frac{1}{2}}]\sqrt{8\|\Sigma_{g}-\widehat{\Sigma}_{g}^{n}\|_{2}}}_{\text{(2)
error of
$2\textup{Tr}[(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}]$}}$
(16)
$\displaystyle+\underbrace{\textup{Tr}(\Sigma_{g})\sqrt{\frac{8}{n}\log\left(\frac{6d}{\delta}\right)}+\|\mu_{g}-\widehat{\mu}_{g}^{n}\|_{2}\cdot\left(\|\mu_{g}-\widehat{\mu}_{g}^{n}\|_{2}+\frac{2}{n}\sum_{i=1}^{n}\|f(x^{i})-\widehat{\mu}_{g}^{n}\|_{2}\right)}_{\text{(3)
error of $\textup{Tr}[\widehat{\Sigma}_{g}^{n}]$}}.$

###### Proof.

Recall that for any generator $g$, we have that

$\displaystyle\textup{FID}_{g}=\|\mu_{g}-\mu_{\textup{r}}\|_{2}^{2}+\textup{Tr}[\Sigma_{g}+\Sigma_{\textup{r}}-2(\Sigma_{g}\Sigma_{\textup{r}})^{\frac{1}{2}}],$
$\displaystyle\widetilde{\textup{FID}}_{g}^{n}=\|\widehat{\mu}_{g}^{n}-\mu_{\textup{r}}\|_{2}^{2}+\textup{Tr}[\widehat{\Sigma}_{g}^{n}+\Sigma_{\textup{r}}-2(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}].$

(1) Bound
$\|\mu_{g}-\mu_{\textup{r}}\|_{2}^{2}-\|\widehat{\mu}_{g}^{n}-\mu_{\textup{r}}\|_{2}^{2}$.
Note that

$\left|\|\widehat{\mu}_{g}^{n}-\mu_{\textup{r}}\|_{2}-\|\mu_{g}-\mu_{\textup{r}}\|_{2}\right|\leq\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}.$

We derive

$\displaystyle\left|\|\mu_{g}-\mu_{\textup{r}}\|_{2}^{2}-\|\widehat{\mu}_{g}^{n}-\mu_{\textup{r}}\|_{2}^{2}\right|$
(17) $\displaystyle\leq$
$\displaystyle(\|\mu_{g}-\mu_{\textup{r}}\|_{2}+\|\widehat{\mu}_{g}^{n}-\mu_{\textup{r}}\|_{2})\cdot\left|\|\mu_{g}-\mu_{\textup{r}}\|_{2}-\|\widehat{\mu}_{g}^{n}-\mu_{\textup{r}}\|_{2}\right|$
$\displaystyle\leq$
$\displaystyle(2\|\mu_{g}-\mu_{\textup{r}}\|_{2}+\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2})\cdot\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}.$

(2) Bound
$\textup{Tr}[(\Sigma_{g}\Sigma_{\textup{r}})^{\frac{1}{2}}-(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}]$.
By Theorem A.3 in Appendix A.5, if the covariance matrix $\Sigma_{\textup{r}}$
is positive strictly definite, then it holds that

$\left|\textup{Tr}[(\Sigma_{g}\Sigma_{\textup{r}})^{\frac{1}{2}}]-\textup{Tr}\left[(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}\right]\right|\leq\textup{Tr}[\Sigma_{\textup{r}}^{\frac{1}{2}}]\sqrt{2\|\Sigma_{g}-\widehat{\Sigma}_{g}^{n}\|_{2}}.$
(18)

(3) Bound $\textup{Tr}[\Sigma_{g}-\widehat{\Sigma}_{g}^{n}]$.  Note that

$\displaystyle\left|\textup{Tr}[\Sigma_{g}-\widehat{\Sigma}_{g}^{n}]\right|$
$\displaystyle=$
$\displaystyle\left|\mathbb{E}[\textup{Tr}[(f(X_{g})-\mu_{g})(f(X_{g})-\mu_{g})^{\top}]]-\frac{1}{n}\sum_{i=1}^{n}\textup{Tr}[(f(x^{i})-\widehat{\mu}_{g}^{n})((f(x^{i})-\widehat{\mu}_{g}^{n}))^{\top}]\right|$
$\displaystyle=$
$\displaystyle\left|\mathbb{E}[\|f(X_{g})-\mu_{g}\|_{2}^{2}]-\frac{1}{n}\sum_{i=1}^{n}\|f(x^{i})-\widehat{\mu}_{g}^{n}\|_{2}^{2}\right|$
$\displaystyle\leq$
$\displaystyle\left|\mathbb{E}[\|f(X_{g})-\mu_{g}\|_{2}^{2}]-\frac{1}{n}\sum_{i=1}^{n}\|f(x^{i})-\mu_{g}\|_{2}^{2}\right|+\left|\frac{1}{n}\sum_{i=1}^{n}(\|f(x^{i})-\mu_{g}\|_{2}^{2}-\|f(x^{i})-\widehat{\mu}_{g}^{n}\|_{2}^{2})\right|.$
(19)

Next, we bound the two terms in the last inequality. Let
$Z_{g}:=f(X_{g})-\mu_{g}\sim{\mathcal{N}}(0,\Sigma_{g})$. For the first term,
we have that

$\|f(X_{g})-\mu_{g}\|_{2}^{2}=\|Z_{g}\|_{2}^{2}=(\Sigma_{g}^{-\frac{1}{2}}Z_{g})^{\top}\Sigma_{g}(\Sigma_{g}^{-\frac{1}{2}}Z_{g})=(Q_{g}\Sigma_{g}^{-\frac{1}{2}}Z_{g})^{\top}\Lambda_{g}(Q_{g}\Sigma_{g}^{-\frac{1}{2}}Z_{g}),$

where we denote by $\Sigma_{g}:=Q_{g}^{\top}\Lambda_{g}Q_{g}$ the
eigendecomposition of $\Sigma_{g}$. Note that the random vector
$Q_{g}\Sigma_{g}^{-\frac{1}{2}}Z_{g}$ has distribution ${\mathcal{N}}(0,I)$.
We have that

$\|f(X_{g})-\mu_{g}\|_{2}^{2}=\sum_{j=1}^{d}\lambda_{j}U_{j}^{2},$

where $\lambda_{j}$’s are the eigenvalues of $\Sigma_{g}$,
$U_{i}\sim{\mathcal{N}}(0,1)$ are independent standard normal, and hence
$U_{i}^{2}$’s are independent Chi-square random variables. Therefore, we have
that

$\displaystyle\left|\mathbb{E}[\|f(X_{g})-\mu_{g}\|_{2}^{2}]-\frac{1}{n}\sum_{i=1}^{n}\|f(x^{i})-\mu_{g}\|_{2}^{2}\right|$
$\displaystyle=$
$\displaystyle\left|\sum_{j=1}^{d}\lambda_{j}\left(\frac{1}{n}\sum_{i=1}^{n}(U_{j}^{i})^{2}-\mathbb{E}[U_{j}^{2}]\right)\right|$
$\displaystyle\leq$
$\displaystyle\left(\sum_{j=1}^{d}\lambda_{j}\right)\cdot\max_{j=1,\cdots,d}\left|\frac{1}{n}\sum_{i=1}^{n}(U_{j}^{i})^{2}-1\right|$
$\displaystyle\leq$
$\displaystyle\textup{Tr}(\Sigma_{g})\sqrt{\frac{8}{n}\log\left(\frac{6d}{\delta}\right)},$
(20)

where the last inequality holds with probability at least $1-\frac{\delta}{3}$
by Lemma E.5. In addition, for the second term, we derive that

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}(\|f(x^{i})-\mu_{g}\|_{2}^{2}-\|f(x^{i})-\widehat{\mu}_{g}^{n}\|_{2}^{2})\right|$
$\displaystyle=$
$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}(\|f(x^{i})-\mu_{g}\|_{2}+\|f(x^{i})-\widehat{\mu}_{g}^{n}\|_{2})(\|f(x^{i})-\mu_{g}\|_{2}-\|f(x^{i})-\widehat{\mu}_{g}^{n}\|_{2})\right|$
$\displaystyle\leq$
$\displaystyle\|\mu_{g}-\widehat{\mu}_{g}^{n}\|_{2}\cdot\left(\frac{1}{n}\sum_{i=1}^{n}(\|f(x^{i})-\mu_{g}\|_{2}+\|f(x^{i})-\widehat{\mu}_{g}^{n}\|_{2})\right)$
$\displaystyle\leq$
$\displaystyle\|\mu_{g}-\widehat{\mu}_{g}^{n}\|_{2}\cdot\left(\|\mu_{g}-\widehat{\mu}_{g}^{n}\|_{2}+\frac{2}{n}\sum_{i=1}^{n}\|f(x^{i})-\widehat{\mu}_{g}^{n}\|_{2}\right).$
(21)

Putting all together.  Therefore, combining Inequalities (17), (18), and (19),
with probability at least $1-\frac{\delta}{3}$, it holds that

$\displaystyle\left|\widetilde{\textup{FID}}_{g}^{n}-\textup{FID}_{g}\right|\leq$
$\displaystyle\underbrace{(\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}+2\|\mu_{g}-\mu_{\textup{r}}\|_{2})\cdot\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}}_{\text{(1)
error of
$\|\widehat{\mu}_{g}^{n}-\mu_{\textup{r}}\|_{2}^{2}$}}+\underbrace{\textup{Tr}[\Sigma_{\textup{r}}^{\frac{1}{2}}]\sqrt{8\|\Sigma_{g}-\widehat{\Sigma}_{g}^{n}\|_{2}}}_{\text{(2)
error of
$2\textup{Tr}[(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}]$}}$
$\displaystyle+\underbrace{\textup{Tr}(\Sigma_{g})\sqrt{\frac{8}{n}\log\left(\frac{6d}{\delta}\right)}+\|\mu_{g}-\widehat{\mu}_{g}^{n}\|_{2}\cdot\left(\|\mu_{g}-\widehat{\mu}_{g}^{n}\|_{2}+\frac{2}{n}\sum_{i=1}^{n}\|f(x^{i})-\widehat{\mu}_{g}^{n}\|_{2}\right)}_{\text{(3)
error of $\textup{Tr}[\widehat{\Sigma}_{g}^{n}]$}},$

which concludes the proof. ∎

###  A.4 Concentration of Mean Vector and Covariance Matrix

######  Lemma A.2 (Concentration of mean vector and covariance matrix).

Under the same conditions in Theorem A.1, with probability at least
$1-\frac{2\delta}{3}$, we have that

$\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}\leq\sqrt{\frac{2{\mathcal{I}}_{g}}{n}}\left(32\log\left(\frac{24d}{\delta}\right)\right)^{\frac{1}{4}},\text{
where }{\mathcal{I}}_{g}:=\sum_{j=1}^{d}\sum_{l=1}^{d}|\Sigma_{g}[l,j]|$ (22)

and

$\left\|\Sigma_{g}-\widehat{\Sigma}_{g}^{n}\right\|_{2}\leq
20\sigma_{g}^{2}\|\Sigma_{g}\|_{2}\sqrt{\frac{4\bm{r}(\Sigma_{g})+\log(3/\delta)}{n}}+\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}^{2},$
(23)

where $\sigma_{g}^{2}:=\max_{i\in[d]}\Sigma_{g}[i,i]$ is the largest variance
for the elements in $f(X_{g})$, and
$\bm{r}(\Sigma_{g})=\frac{\textup{Tr}[\Sigma_{g}]}{\|\Sigma_{g}\|_{2}}$ is the
effective rank of $\Sigma_{g}$.

###### Proof.

1\. Concentration of mean vector.  Note that $\Sigma_{g}^{\frac{1}{2}}Z$ where
$Z\sim{\mathcal{N}}(0,I)$ has a multivariate ${\mathcal{N}}(0,\Sigma_{g})$
distribution, which is the same as $f(X_{g})-\mu_{g}$. We have that

$\displaystyle\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}=\left\|\frac{1}{n}\sum_{i=1}^{n}(\Sigma_{g}^{\frac{1}{2}}Z_{i})\right\|_{2}=\left\|\frac{1}{n}\sum_{i=1}^{n}Z_{i}\right\|_{\Sigma_{g}},$

where $\|y\|_{\Sigma_{g}}:=\sqrt{\langle y,\Sigma_{g}y\rangle}$ is the matrix
norm. Let $\widehat{Z}:=\frac{1}{n}\sum_{i=1}^{n}Z_{i}$ denote the mean
vector. We further obtain that

$\left\|\widehat{Z}\right\|_{\Sigma_{g}}^{2}=\textup{Tr}\left((\widehat{Z})^{\top}\Sigma_{g}\widehat{Z}\right)=\textup{Tr}\left(\Sigma_{g}\widehat{Z}(\widehat{Z})^{\top}\right)=\textup{Tr}(\Sigma_{g}D)+\textup{Tr}(\Sigma_{g}M),$
(24)

where $D:=\textup{diag}(\widehat{Z}(\widehat{Z})^{\top})$ and
$M=\widehat{Z}(\widehat{Z})^{\top}-D$. For the first term, note that each
diagonal element has the same distribution
$\frac{1}{n^{2}}(\sum_{i=1}^{n}z_{i})^{2}$, where
$z_{1},\cdots,z_{n}\sim{\mathcal{N}}(0,1)$ are i.i.d standard Gaussian. Then,
with probability at least $1-\frac{\delta}{6}$, we have that

$\textup{Tr}(\Sigma_{g}D)\leq\|D\|_{2}\textup{Tr}(\Sigma_{g})\leq\textup{Tr}(\Sigma_{g})\left(\frac{1}{n}\sqrt{32\log\left(\frac{12d}{\delta}\right)}\right),$
(25)

where the first inequality holds by that $\Sigma_{g}$ is PSD, and the second
inequality holds by Lemma E.10. For the second term,

$\displaystyle\textup{Tr}(\Sigma_{g}M)=$
$\displaystyle\sum_{j=1}^{d}\sum_{l=1,l\neq j}^{d}\Sigma_{g}[l,j]\cdot
M_{j,l}$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{d}\sum_{l=1,l\neq
j}^{d}\Sigma_{g}[l,j]\cdot\left(\frac{\sum_{i=1}^{n}z_{j,i}}{n}\right)\left(\frac{\sum_{i=1}^{n}z_{l,i}}{n}\right)$
$\displaystyle\leq$ $\displaystyle\sum_{j=1}^{d}\sum_{l=1,l\neq
j}^{d}|\Sigma_{g}[l,j]|\cdot\max_{j,l}\left|\left(\frac{\sum_{i=1}^{n}z_{j,i}}{n}\right)\left(\frac{\sum_{i=1}^{n}z_{l,i}}{n}\right)\right|$

where $z_{j,1},\cdots,z_{j,n},z_{l,1},\cdots,z_{l,n}\sim{\mathcal{N}}(0,1)$
are i.i.d standard Gaussian. By Lemma E.11, with probability at least
$1-\frac{\delta}{6}$, it holds that

$\textup{Tr}(\Sigma_{g}M)\leq\left(\sum_{j=1}^{d}\sum_{l=1,l\neq
j}^{d}|\Sigma_{g}[l,j]|\right)\frac{1}{n}\sqrt{8\log\left(\frac{24d}{\delta}\right)}$
(26)

Combining Inequalities (25) and (26), we conclude that with probability at
least $1-\frac{\delta}{3}$, it holds that

$\|\widehat{\mu}_{g}^{n}-\mu_{g}\|^{2}_{2}\leq\left(\sum_{j=1}^{d}\sum_{l=1}^{d}|\Sigma_{g}[l,j]|\right)\left(\frac{2}{n}\sqrt{32\log\left(\frac{24d}{\delta}\right)}\right)$
(27)

2\. Concentration of sample covariance matrix.  we have that

$\displaystyle\left\|\Sigma_{g}-\widehat{\Sigma}_{g}^{n}\right\|_{2}$
$\displaystyle=$
$\displaystyle\left\|\Sigma_{g}-\frac{1}{n}\sum_{i=1}^{n}(f(x^{i})-\widehat{\mu}_{g}^{n})(f(x^{i})-\widehat{\mu}_{g}^{n})^{\top}\right\|_{2}$
$\displaystyle=$
$\displaystyle\left\|\Sigma_{g}-\frac{1}{n}\sum_{i=1}^{n}(f(x^{i})-\mu_{g}+\mu_{g}-\widehat{\mu}_{g}^{n})(f(x^{i})-\mu_{g}+\mu_{g}-\widehat{\mu}_{g}^{n})^{\top}\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\left\|\Sigma_{g}-\frac{1}{n}\sum_{i=1}^{n}(f(x^{i})-\mu_{g})(f(x^{i})-\mu_{g})^{\top}\right\|_{2}+\left\|(\mu_{g}-\widehat{\mu}_{g}^{n})(\mu_{g}-\widehat{\mu}_{g}^{n})^{\top}\right\|_{2},$
(28)

where the last inequality holds by the triangle inequality of the L2 norm of
the matrix. Note that the zero-mean random vector $f(X_{g})-\mu_{g}$ has a
multivariate ${\mathcal{N}}(0,\Sigma_{g})$ distribution (under the assumption
of FID). For the first term, we evoke Lemma E.7. Then, with probability at
least $1-\frac{\delta}{3}$, it holds that

$\left\|\Sigma_{g}-\frac{1}{n}\sum_{i=1}^{n}(f(x^{i})-\mu_{g})(f(x^{i})-\mu_{g})^{\top}\right\|_{2}\leq
20\sigma_{g}^{2}\|\Sigma_{g}\|_{2}\sqrt{\frac{4\bm{r}(\Sigma_{g})+\log(3/\delta)}{n}}.$
(29)

For the second term, we have that

$\displaystyle\left\|(\mu_{g}-\widehat{\mu}_{g}^{n})(\mu_{g}-\widehat{\mu}_{g}^{n})^{\top}\right\|_{2}=\|\mu_{g}-\widehat{\mu}_{g}^{n}\|_{2}^{2},$

which concludes the proof. ∎

###  A.5 Dimension-free Concentration of
$\textup{Tr}[(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}]$

######  Theorem A.3 (Dimension-free concentration of
$\textup{Tr}[(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}]$).

Under the same conditions in Theorem A.1, we have that

$\left|\textup{Tr}[(\Sigma_{g}\Sigma_{\textup{r}})^{\frac{1}{2}}]-\textup{Tr}[(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}]\right|\leq\textup{Tr}[\Sigma_{\textup{r}}^{\frac{1}{2}}]\sqrt{2\|\Sigma_{g}-\widehat{\Sigma}_{g}^{n}\|_{2}}.$
(30)

###### Proof.

Let $\eta=\|\Sigma_{g}-\widehat{\Sigma}_{g}^{n}\|_{2}$. We have that

$\displaystyle\textup{Tr}[(\Sigma_{g}\Sigma_{\textup{r}})^{\frac{1}{2}}]-\textup{Tr}[(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}]$
$\displaystyle\leq$
$\displaystyle\textup{Tr}\left[\sqrt{B^{\top}(\Sigma_{g}-\widehat{\Sigma}_{g}^{n}+\widehat{\Sigma}_{g}^{n}+\eta
I)B}\right]-\textup{Tr}\left[\sqrt{B^{\top}\widehat{\Sigma}_{g}^{n}B}\right]$
$\displaystyle\leq$
$\displaystyle\textup{Tr}\left[\sqrt{B^{\top}(\Sigma_{g}-\widehat{\Sigma}_{g}^{n}+\eta
I)B}+\sqrt{B^{\top}\widehat{\Sigma}_{g}^{n}B}\right]-\textup{Tr}\left[\sqrt{B^{\top}\widehat{\Sigma}_{g}^{n}B}\right]$
$\displaystyle\leq$ $\displaystyle\textup{Tr}\left[\sqrt{2\eta
B^{\top}B}\right]=\textup{Tr}[\Sigma_{\textup{r}}^{\frac{1}{2}}]\sqrt{2\eta},$

where the first inequality holds by Lemma E.10, the second inequality holds by
Lemma E.11 and the fact that both matrices
$B^{\top}(\Sigma_{g}-\widehat{\Sigma}_{g}^{n}+\eta
I)B\succeq\bm{0},B^{\top}\widehat{\Sigma}_{g}^{n}B\succeq\bm{0}$ are PSD, and
the last inequality holds by Lemma E.10 and $B^{\top}(2\eta I)B\succeq
B^{\top}(\Sigma_{g}-\widehat{\Sigma}_{g}^{n}+\eta I)B$. By the same analysis,
we can also derive that

$\textup{Tr}[(\widehat{\Sigma}_{g}^{n}\Sigma_{\textup{r}})^{\frac{1}{2}}]-\textup{Tr}[(\Sigma_{g}\Sigma_{\textup{r}})^{\frac{1}{2}}]\leq\textup{Tr}\left[\sqrt{2\eta
B^{\top}B}\right]=\textup{Tr}[\Sigma_{\textup{r}}^{\frac{1}{2}}]\sqrt{2\eta},$

which concludes the proof. ∎

##  Appendix B Proofs in Section 6: IS Evaluation

###  B.1 Proof of Theorem 6.1: Generator-Dependent Optimistic IS

###### Proof.

By Lemma B.2, we have that with probability at least $1-\frac{\delta}{2}$,
${\mathcal{E}}(\widehat{p}_{Y_{g}}^{n})\geq H(Y_{g})$. To show Theorem 6.1, it
suffices to show that

$H_{g}(Y_{g}|X_{g})\geq\widehat{H}^{n}(Y_{g}|X_{g})-\sqrt{\frac{2\widehat{V}_{g}^{n}(H(Y_{g}|X_{g}))}{n}\log\left(\frac{4}{\delta}\right)}-\frac{7C^{\prime}}{3(n-1)}\log\left(\frac{4}{\delta}\right)$

with probability at least $1-\frac{\delta}{2}$, which holds by Theorem E.4.
Therefore, we conclude the proof. ∎

###  B.2 Proof of Theorem 6.2: Regret of IS-UCB

###### Proof.

By Theorem 6.1 and union bound over $T$ steps, with probability at least
$1-\delta$, it holds that $\widehat{\textup{IS}}_{g}\geq\textup{IS}_{g}$ for
all steps $t\in[T]$ and $g\in[G]$, where $\widehat{\textup{IS}}_{g}$ is given
by Equation (14). For convenience, we denote by
$\widehat{\textup{IS}}_{g_{t}}$ the optimistic IS of generator $g_{t}$
computed at the $t$-th step. Hence, we have that

$\textup{IS}^{*}-\textup{IS}_{g_{t}}\leq\widehat{\textup{IS}}_{g_{t}}-\textup{IS}_{g_{t}}=e^{{\mathcal{E}}\left(\widehat{p}_{Y_{g_{t}}}\right)-\widehat{H}(Y_{g_{t}}|X_{g_{t}})+{\mathcal{B}}_{g_{t}}}-\textup{IS}_{g_{t}},$

where

${\mathcal{B}}_{g_{t}}:=\sqrt{\frac{2\widehat{V}_{g}^{n}(H(Y_{g}|X_{g}))}{n}\log\left(\frac{4}{\delta}\right)}+\frac{7C^{\prime}}{3(n-1)}\log\left(\frac{4}{\delta}\right).$

Let ${\mathcal{T}}_{1},{\mathcal{T}}_{2}\subset[T]$ be two disjoint set of
steps such that ${\mathcal{T}}_{2}=[T]\backslash{\mathcal{T}}_{1}$.
Specifically, ${\mathcal{T}}_{1}$ contains steps where no element of the
empirical marginal class distribution $\widetilde{p}_{Y_{g_{t}}}$ is clipped
to $e^{-1}$, i.e.,
$|e^{-1}-\widetilde{p}_{Y_{g_{t}}}[j]|\geq\bm{\epsilon}_{g_{t}}[j]$ for all
$[j]\in d$. Let
$\textup{IS}^{*}=\operatorname*{arg\,max}_{g\in[G]}\textup{IS}_{g}$ denote the
optimal Inception score. Hence, we have that

$\textup{Regret}(T)=\sum_{t\in{\mathcal{T}}_{1}}(\textup{IS}^{*}-\textup{IS}_{g_{t}})+\sum_{t\in{\mathcal{T}}_{2}}(\textup{IS}^{*}-\textup{IS}_{g_{t}}).$

Recall $u(x)=-x\log x$ for $x\in{\mathbb{R}}_{+}$. For the first part, we
further derive that

$\displaystyle\sum_{t\in{\mathcal{T}}_{1}}(\textup{IS}^{*}-\textup{IS}_{g_{t}})$
$\displaystyle\leq$
$\displaystyle\sum_{t\in{\mathcal{T}}_{1}}\left(\exp\\{{\mathcal{E}}\left(\widehat{p}_{Y_{g_{t}}}\right)-\widehat{H}(Y_{g_{t}}|X_{g_{t}})+{\mathcal{B}}_{g_{t}}\\}-\exp\\{H(Y_{g})-H(Y_{g}|X_{g})\\}\right)$
$\displaystyle\leq$ $\displaystyle
e^{C}\cdot\sum_{t\in{\mathcal{T}}_{1}}\left({\mathcal{E}}\left(\widehat{p}_{Y_{g_{t}}}\right)-\widehat{H}(Y_{g_{t}}|X_{g_{t}})+{\mathcal{B}}_{g_{t}}-H(Y_{g})+H(Y_{g}|X_{g})\right)$
$\displaystyle\leq$ $\displaystyle
e^{C}\cdot\sum_{t\in{\mathcal{T}}_{1}}\left(\sum_{j=1}^{d}\left(u(\widehat{p}_{Y_{g_{t}}}[j])-u(p_{Y_{g_{t}}}[j])\right)+2{\mathcal{B}}_{g_{t}}\right)$
$\displaystyle\leq$ $\displaystyle
O\left(e^{C}\cdot\sum_{t\in{\mathcal{T}}_{1}}\left(m\cdot\sum_{j=1}^{d}|\widehat{p}_{Y_{g_{t}}}[j]-p_{Y_{g_{t}}}[j]|+{\mathcal{B}}_{g_{t}}\right)\right)$
$\displaystyle\leq$ $\displaystyle
O\left(e^{C}\cdot\sum_{t\in{\mathcal{T}}_{1}}\left(m\cdot\sum_{j=1}^{d}\bm{\epsilon}_{g_{t}}[j]+{\mathcal{B}}_{g_{t}}\right)\right)$
$\displaystyle\leq$
$\displaystyle\widetilde{O}\left(e^{C}\cdot\sum_{t=1}^{T}\left(\max\left\\{dm,\frac{d\log
d}{2}\right\\}\sqrt{\frac{1}{N_{g_{t}}}}+\frac{C^{\prime}}{N_{g_{t}}}\right)\right),$
(31)

where
$m=\max_{g\in[G],j\in[d]:p_{Y_{g}}[j]>0}\\{|u^{\prime}(p_{Y_{g}}[j])|\\}$, and
$C=O(de^{-1}+C^{\prime})$ is the upper bound of
${\mathcal{E}}(\widehat{p}_{Y_{g_{t}}})-\widehat{H}(Y_{g_{t}}|X_{g_{t}})+{\mathcal{B}}_{g_{t}}$.
For the second part, note that the number of steps where at least one element
of $\widetilde{p}_{Y_{g_{t}}}$ is clipped to at most
$\widetilde{O}(G\Delta^{-2})$, where
$\Delta=\min_{g\in[G],j\in[d]:p_{Y_{g}}[j]\neq
e^{-1}}\\{|p_{Y_{g}}[j]-e^{-1}|\\}$. Therefore, we have that

$\textup{Regret}(T)\leq\widetilde{O}\left(dG\Delta^{-2}\log
d+e^{C}\cdot\max\left\\{dm,\left(\frac{d\log
d}{4}\right)^{2}\right\\}\sqrt{T}\right),$

which concludes the proof. ∎

###  B.3 Optimistic marginal class distribution

######  Theorem B.1 (Optimistic marginal class distribution).

Let $\widetilde{p}^{n}_{Y_{g}}:=\frac{1}{n}\sum_{i=1}^{n}p_{Y_{g}|x^{i}}$
denote the empirical marginal class distribution. Let

$\widehat{p}_{Y_{g}}^{n}=\textup{Clip}_{e^{-1}}\left(\widetilde{p}^{n}_{Y_{g}},|\widetilde{p}^{n}_{Y_{g}}-p_{Y_{g}}|\right),$

where $\textup{Clip}_{e^{-1}}(p,\bm{\epsilon})$ is the following element-wise
operator

$\begin{cases}p[j]+\frac{e^{-1}-p[j]}{|e^{-1}-p[j]|}\bm{\epsilon}[j]&\textup{,
if }|e^{-1}-p[j]|\geq\bm{\epsilon}[j]\\\ e^{-1}&\textup{,
otherwise.}\end{cases}$

for any vectors $p,\bm{\epsilon}\in{\mathbb{R}}^{d}_{+}$. Then, we have that
${\mathcal{E}}(\widehat{p}_{Y_{g}}^{n})\geq H(Y_{g})$.

###### Proof.

Note that the function $u(z)=-z\log z$ is concave and attains maximum at
$z=e^{-1}$. It suffices to show that $u(\widehat{p}_{Y_{g}}[j])\geq
u(p_{Y_{g}}[j])$ for all $j\in[d]$. If
$|e^{-1}-\widehat{p}_{Y_{g}}^{n}[j]|<|\widetilde{p}^{n}_{Y_{g}}[j]-p_{Y_{g}}[j]|$,
then $\widehat{p}_{Y_{g}}[j]=e^{-1}$, which ensures that
$u(\widehat{p}_{Y_{g}}[j])\geq u(p_{Y_{g}}[j])$. In addition, if
$|e^{-1}-\widehat{p}_{Y_{g}}^{n}[j]|\geq|\widetilde{p}^{n}_{Y_{g}}[j]-p_{Y_{g}}[j]|$,
then

$\widehat{p}_{Y_{g}}^{n}[j]=\widetilde{p}^{n}_{Y_{g}}[j]+\frac{e^{-1}-\widetilde{p}^{n}_{Y_{g}}[j]}{|e^{-1}-\widetilde{p}^{n}_{Y_{g}}[j]|}|\widetilde{p}^{n}_{Y_{g}}[j]-p_{Y_{g}}[j]|=\begin{cases}\widetilde{p}^{n}_{Y_{g}}[j]+|\widetilde{p}^{n}_{Y_{g}}[j]-p_{Y_{g}}[j]|,&\textup{
if }p_{Y_{g}}[j]<e^{-1}\\\
\widetilde{p}^{n}_{Y_{g}}[j]-|\widetilde{p}^{n}_{Y_{g}}[j]-p_{Y_{g}}[j]|,&\textup{
otherwise.}\end{cases}.$

The first case ensures that $p_{Y_{g}}[j]<\widehat{p}_{Y_{g}}^{n}[j]\leq
e^{-1}$, and the second case ensures that
$p_{Y_{g}}[j]>\widehat{p}_{Y_{g}}^{n}[j]\geq e^{-1}$. Both cases satisfy that
$u(\widehat{p}_{Y_{g}}^{n}[j])\geq u(p_{Y_{g}}[j])$. Therefore, we have that
$H(Y_{g})={\mathcal{E}}(p_{Y_{g}})=\sum_{j=1}^{d}u(p_{Y_{g}}[j])\leq\sum_{j=1}^{d}u(\widehat{p}_{Y_{g}}^{n}[j])={\mathcal{E}}(\widehat{p}_{Y_{g}}^{n})$,
which concludes the proof. ∎

###  B.4 Data-dependent optimistic marginal class distribution

######  Lemma B.2 (Optimistic marginal class distribution).

Let $x^{1},\cdots,x^{n}\sim p_{g}$ be $n$ generated images from generator $g$.
Define $\bm{\epsilon}^{n}_{g}\in{\mathbb{R}}_{+}^{d}$ denote the error vector
whose $j$-th element is given by

$\bm{\epsilon}^{n}_{g}[j]=\sqrt{\frac{2\widehat{V}^{n}(p_{Y|X_{g}}[j])}{n}\log\left(\frac{4d}{\delta}\right)}+\frac{7}{3(n-1)}\log\left(\frac{4d}{\delta}\right),$

where
$\widehat{V}^{n}(p_{Y|X_{g}}[j])={\mathbb{V}}(p_{Y|x^{1}}[j],\cdots,p_{Y|x^{n}}[j])$
is the empirical variance for the $j$-th class density. Then, with probability
at least $1-\frac{\delta}{2}$, we have that

$\widehat{p}_{Y_{g}}^{n}=\textup{Clip}_{e^{-1}}\left(\widetilde{p}^{n}_{Y_{g}},\bm{\epsilon}^{n}_{g}\right)$

satisfies that ${\mathcal{E}}(\widehat{p}_{Y_{g}}^{n})\geq H(Y_{g})$.

###### Proof.

It suffices that show that
$\bm{\epsilon}_{g}^{n}[j]\geq|\widehat{p}_{Y_{g}}^{n}[j]-p_{Y_{g}}[j]|$ with
probability at least $1-\frac{\delta}{2}$. We evoke Theorem E.4 and conclude
the proof. ∎

##  Appendix C Additional Experimental Results

###  C.1 Results of FID-Based Online Evaluation

#### 1\. Embeddings Extracted by DINOv2 [33].

We run FID-UCB, naive UCB, and the greedy algorithm where the feature of an
image is extracted by DINOv2-ViT-L/14. The pretrained weights are downloaded
from the official repository (licensed under Apache License
2.0).333https://github.com/facebookresearch/dinov2/tree/main The results are
summarized in Figure 5.

CIFAR10 (G=5)

ImageNet (G=5)

FFHQ (G=5)

FFHQ (G=20) Total regret Average regret Optimal pick ratio

Figure 5: Performance of FID-UCB, naive UCB, and the greedy algorithm on
various datasets, where the last row corresponds to the evaluation of the
variance-controlled generators. The embeddings of the images are extracted by
the pretrained DINOv2-ViT-L/14 model.

#### 2\. Embeddings Extracted by CLIP [7].

We run FID-UCB, naive UCB, and the greedy algorithm where the feature of an
image is extracted by CLIP. The pretrained weights are downloaded from the
official repository.444https://github.com/mlfoundations/open_clip. Copyright
(c) 2012-2021 Gabriel Ilharco, Mitchell Wortsman, Nicholas Carlini, Rohan
Taori, Achal Dave, Vaishaal Shankar, John Miller, Hongseok Namkoong, Hannaneh
Hajishirzi, Ali Farhadi, Ludwig Schmidt. The results are summarized in Figure
6. We note that in the FFHQ dataset, FID-UCB attains a low optimal pick ratio
as the optimal generator and the second-best one attains almost the same CLIP-
based FID.

CIFAR10 (G=5)

ImageNet (G=5)

FFHQ (G=5)

FFHQ (G=20) Total regret Average regret Optimal pick ratio

Figure 6: Performance of FID-UCB, naive UCB, and the greedy algorithm on
various datasets, where the last row corresponds to the evaluation of the
variance-controlled generators. The embeddings of images are extracted by the
pretrained CLIP model.

#### 3\. Results on AFHQ Dog dataset.

The results are summarized in Figure 7.

AFHQ Dog (G=20)

Figure 7: Performance of FID-UCB, naive UCB, and the greedy algorithm for
evaluating the variance-controlled generators on AFHQ Dog dataset. The
embeddings of images are extracted by InceptionNet.V3.

###  C.2 Results of IS-Based Online Evaluation

#### 1\. Diversity and quality of the generated samples.

We examine the diversity and quality of the generated samples queried by IS-
UCB, naive UCB, and the greedy algorithm (i.e., experiment in Figure 4). The
results are summarized in Figure 8.

Step 500

Step 1000 IS-UCB Naive UCB Greedy

Figure 8: Generated images queried by IS-UCB, naive UCB, and the greedy
algorithm.

#### 2\. Results on AFHQ Dog dataset.

The results are summarized in Figure 9.

AFHQ Dog (G=20)

Figure 9: Performance of IS-UCB, naive UCB, and the greedy algorithm for
evaluating the variance-controlled generators on AFHQ dataset.

##  Appendix D Additional Experimental details

#### 1\. Additional experiment setups.

All the experiments are run on a single Nvidia GeForce RTX 3090 GPU. For FID-
based evaluation, each trial takes at most 2 hours to finish, depending on the
dataset and the embedding pretrained model. For IS-based evaluation, each
trial takes less than 30 minutes to finish.

#### 2\. List of pretrained generative models/generated image data.

For the CIFAR10 dataset, we compare pretrained models including SNGAN, ACGAN,
BigGAN, ContraGAN, and BigGAN-CR. For the ImageNet dataset, we compare
pretrained models including StyleGAN3, SNGAN, BigGAN, ContraGAN, and ReACGAN.
The pretrained weights are downloaded from the StudioGAN repository [22]. For
the FFHQ dataset, we compare StyleSwin, StyleNAT, StyleGAN2-ADA, StyleGAN-XL,
and LDM, where we utilize the generated image datasets downloaded from the
dgm-eval repository [39].

#### 3\. Implementation details of naive UCB for FID-based evaluation.

In FID-based evaluation, naive UCB upper bounds the error in estimating the
mean vector by

$\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}=\sqrt{\sum_{j=1}^{d}(\widehat{\mu}_{g}^{n}[j]-\mu_{g}[j])^{2}}\leq\sigma_{g}\sqrt{\frac{d}{n}\log\left(\frac{2d}{\delta}\right)}$

which holds by the assumption of FID score that
$f(X_{g})\sim{\mathcal{N}}(\mu_{g},\Sigma_{g})$, with probability at least
$1-\delta$. In addition, the error in estimating the covariance matrix is
bounded by

$\|\widehat{\Sigma}_{g}^{n}-\Sigma_{g}\|_{2}\leq\|\widehat{\mu}_{g}^{n}-\mu_{g}\|_{2}^{2}+\|\Sigma_{g}\|_{2}\left(2\sqrt{\frac{d}{n}}+2\sqrt{\frac{1}{2n}\log\left(\frac{2}{\delta}\right)}+\left(\sqrt{\frac{d}{n}}+\sqrt{\frac{1}{2n}\log\left(\frac{2}{\delta}\right)}\right)^{2}\right)$

which follows from the exact same derivation in Inequality (28) and holds with
probability at least $1-\delta$ (see Lemma E.6). Compared to the generator-
dependent error bounds utilized by FID-UCB (i.e., Inequalities (27) and (29)),
these bounds are dimension-dependent and do not fully exploit the properties
of the generator. Finally, by the exact same analysis in the proof of Theorem
5.1, the following estimated FID

$\displaystyle\widehat{\textup{FID}}_{g}^{n}=$
$\displaystyle\widetilde{\textup{FID}}_{g}^{n}-C_{g}^{n}\cdot\sigma_{g}\sqrt{\frac{d}{n}\log\left(\frac{6d}{\delta}\right)}-\textup{Tr}[\Sigma_{g}]\sqrt{\frac{8}{n}\log\left(\frac{6d}{\delta}\right)}$
(32)
$\displaystyle-\textup{Tr}[\Sigma_{\textup{r}}^{\frac{1}{2}}]\sqrt{8\left(\|\Sigma_{g}\|_{2}\left(2\sqrt{\frac{d}{n}}+2\sqrt{\frac{1}{2n}\log\left(\frac{6}{\delta}\right)}+\left(\sqrt{\frac{d}{n}}+\sqrt{\frac{1}{2n}\log\left(\frac{6}{\delta}\right)}\right)^{2}\right)+\frac{d\sigma_{g}^{2}}{n}\log\left(\frac{6d}{\delta}\right)\right)}$

lower bounds $\textup{FID}_{g}$ with probability at least $1-\delta$.

#### 4\. Implementation details of naive UCB for IS-based evaluation.

In IS-based evaluation, naive UCB uses Hoeffding-type bonus terms.
Specifically, the error vector in defining the optimistic marginal class
distribution is given by $e_{g}^{n}$, whose $j$-th element is defined as

$e_{g}^{n}[j]:=\sqrt{\frac{1}{2n}\log\left(\frac{4d}{\delta}\right)},$

which ensures that
${\mathcal{E}}(\textup{Clip}_{e^{-1}}(\widetilde{p}_{Y_{g}}^{n},e_{g}^{n}))\geq
H(Y_{g})$ with probability at least $1-\frac{\delta}{2}$. In addition, the
concentration error of $\widehat{H}^{n}(Y_{g}|X_{g})$ is bounded by

$H_{g}(Y_{g}|X_{g})\geq\widehat{H}^{n}(Y_{g}|X_{g})-C^{\prime}\sqrt{\frac{1}{2n}\log\left(\frac{4}{\delta}\right)}$

which holds with probability at least $1-\frac{\delta}{2}$. Therefore, the
estimated IS is given by

$\widehat{\textup{IS}}_{g}^{n}:=\exp\left\\{{\mathcal{E}}\left(\textup{Clip}_{e^{-1}}\left(\widetilde{p}_{Y_{g}}^{n},e_{g}^{n}\right)\right)-\widehat{H}^{n}(Y_{g}|X_{g})+C^{\prime}\sqrt{\frac{1}{2n}\log\left(\frac{4}{\delta}\right)}\right\\}$
(33)

By the exact same analysis in the proof of Theorem 6.1, it can be shown that
$\widehat{\textup{IS}}_{g}^{n}\geq\textup{IS}_{g}$ with probability at least
$1-\delta$.

#### 5\. Additional implementation details of FID-UCB

To compute the bonus term (7), we need to estimate the following parameters:
1) $\|\mu_{g}-\mu_{\textup{r}}\|_{2}$: we set it to be a constant, e.g., 0.5;
2) ${\mathcal{I}}_{g}$: we estimate this term using the truncated covariance
matrix with parameter $\tau$, which is denoted by
$\textup{truncate}_{\tau}(\widehat{\Sigma}_{g}^{n})$. The $(i,j)$-th element
of the truncated covariance matrix is $\widehat{\Sigma}_{g}^{n}[i,j]$ if
$\widehat{\Sigma}_{g}^{n}[i,j]\geq\tau$ and is zero otherwise. In the
experiments, we observe that a truncation parameter that is $5\sim 10\%$ of
the operator norm $\|\Sigma_{\textup{r}}\|_{2}$, i.e.,
$0.05\cdot\|\Sigma_{\textup{r}}\|_{2}\leq\tau\leq
0.1\cdot\|\Sigma_{\textup{r}}\|_{2}$, attains satisfying performance; 3)
$\|\Sigma_{g}\|_{2}$: we estimate this term by
$\max_{j\in[d]}(\widehat{\sigma}_{j}^{n})^{2}+O(\sqrt{\log(1/\delta)/n})$,
where $(\widehat{\sigma}_{j}^{n})^{2}$ is the sample variance for the $j$-th
entry of the embedding $f(X_{g})$. This avoids the computation for the
eigendecomposition of the sample covariance matrix $\widehat{\Sigma}_{g}^{n}$.
The intuition is that when $\Sigma_{g}$ is diagonal, the operator norm
$\|\Sigma_{g}\|_{2}$ coincides with the largest per-entry variance; 4)
$\textup{Tr}[\Sigma_{g}]$: while a direct approach is to estimate it by
$\textup{Tr}[\widehat{\Sigma}_{g}^{n}]$, we found that a better performance
can be attained by using
$O(\textup{Tr}[\textup{truncate}_{\tau}(\widehat{\Sigma}_{g}^{n})\cdot\Sigma_{\textup{r}}])$,
where we utilize the fact that
$\|\Sigma_{\textup{r}}^{-1}\|_{2}\cdot\textup{Tr}[\Sigma_{g}\Sigma_{\textup{r}}]\geq\textup{Tr}[\Sigma_{g}]\geq\frac{\textup{Tr}[\Sigma_{g}\Sigma_{\textup{r}}]}{\|\Sigma_{\textup{r}}\|_{2}}$.

##  Appendix E Auxiliary Lemmas

######  Lemma E.1 (Concentration of Gaussian random variable).

Let $X_{1},\cdots,X_{n}\sim{\mathcal{N}}(\mu,\sigma^{2})$. Then, it holds that

${\mathbb{P}}\left(\left|\frac{1}{n}\sum_{i=1}^{n}X_{i}-\mu\right|>\epsilon\right)<\exp\left(-\frac{n\epsilon^{2}}{2\sigma^{2}}\right)$

Equivalently, with probability at least $1-\delta$, we have that

$\left|\frac{1}{n}\sum_{i=1}^{n}X_{i}-\mu\right|\leq\sqrt{\frac{\sigma^{2}}{2n}\log\left(\frac{2}{\delta}\right)}.$

######  Lemma E.2 (Hoeffding’s inequality).

Let $Z,Z_{1},\cdots,Z_{n}$ be i.i.d. random variables with values in $[0,1]$
and let $\delta>0$. Then with probability at least $1-\delta$ in
$(Z_{1},\cdots,Z_{n})$ we have that

$\mathbb{E}Z-\frac{1}{n}\sum_{i=1}^{n}Z_{i}\leq\sqrt{\frac{1}{2n}\log\left(\frac{1}{\delta}\right)}.$
(34)

A drawback of Hoeffding’s inequality is that the confidence interval is
distribution-agnostic, and always scales with order $O(\sqrt{1/n})$. For
distribution with small variance, the following [18, Bennett’s inequality]
provides a tighter concentration error.

######  Lemma E.3 (Bennett’s inequality).

Under the conditions of Theorem E.2, with probability at least $1-\delta$ in
$(Z_{1},\cdots,Z_{n})$ we have that

$\mathbb{E}Z-\frac{1}{n}\sum_{i=1}^{n}Z_{i}\leq\sqrt{\frac{2{\mathbb{V}}Z}{n}\log\left(\frac{1}{\delta}\right)}+\frac{1}{3n}\log\left(\frac{1}{\delta}\right),$
(35)

where ${\mathbb{V}}Z$ is the variance
${\mathbb{V}}=\mathbb{E}(Z-\mathbb{E}Z)^{2}$.

When the exact variance is unknown, [31] provide a purely data-dependent bound
with similar properties as Bennett’s inequality.

######  Lemma E.4 (Restatement of [31, Theorem 4]).

Under the conditions of Theorem E.2, we have that with probability at least
$1-\delta$ in the i.i.d vector $\bm{Z}=(Z_{1},\cdots,Z_{n})$ that

$\mathbb{E}Z-\frac{1}{n}\sum_{i=1}^{n}Z_{i}\leq\sqrt{\frac{2V_{n}(\bm{Z})}{n}\log\left(\frac{2}{\delta}\right)}+\frac{7}{3(n-1)}\log\left(\frac{2}{\delta}\right),$

where $V_{n}(\bm{Z}):=\frac{1}{n(n-1)}\sum_{1\leq i<j\leq n}(Z_{i}-Z_{j})^{2}$
is the sample variance.

######  Lemma E.5 (Concentration of Chi-square variables).

Let $Z_{1},\cdots,Z_{n}\sim{\mathcal{N}}(0,1)$ be i.i.d standard normal. Then,
it holds that

${\mathbb{P}}\left(\left|\frac{1}{n}\sum_{i=1}^{n}Z_{i}^{2}-1\right|>\epsilon\right)\leq
2e^{-n\epsilon^{2}/8}.$

Equivalently, with probability at least $1-\delta$, we have that

$\left|\frac{1}{n}\sum_{i=1}^{n}Z_{i}^{2}-1\right|\leq\sqrt{\frac{8}{n}\log\left(\frac{2}{\delta}\right)}$

######  Lemma E.6 (Restatement of [43, Example 6.3]).

Let $\bm{X}\in{\mathbb{R}}^{n\times d}$ be a random matrix from the
$\Sigma$-Gaussian ensemble, i.e., each row vector $x_{i}$ is drawn i.i.d. from
a multivariate ${\mathcal{N}}(0,\Sigma)$ distribution. Then, with probability
at least $1-\delta$, we have that

$\|\widehat{\Sigma}-\Sigma\|_{2}\leq\|\Sigma\|_{2}\left(2\sqrt{\frac{d}{n}}+2\epsilon+\left(\sqrt{\frac{d}{n}}+\epsilon\right)^{2}\right),\textup{
where }\epsilon=\sqrt{\frac{1}{2n}\log\left(\frac{2}{\delta}\right)},$ (36)

where $\widehat{\Sigma}=\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top}$ is the
sample covariance matrix.

######  Lemma E.7 (Dimension-free concentration of sample covariance matrix
[30, 25, 46]).

Let $X_{1},\cdots,X_{n}$ are i.i.d zero-mean and sub-Gaussian random vectors
with parameter at most $\sigma^{2}$, whose covariance matrix is given by
$\Sigma$. Let

$\bm{r}(\Sigma):=\frac{\textup{Tr}(\Sigma)}{\|\Sigma\|_{2}}$ (37)

denote the _effective rank_. Then, with probability at least $1-\delta$, the
sample covariance matrix satisfies that

$\left\|\frac{1}{n}\sum_{i=1}^{n}X_{i}X_{i}^{\top}-\Sigma\right\|_{2}\leq
20\sigma^{2}\|\Sigma\|_{2}\sqrt{\frac{4\bm{r}(\Sigma)+\log(1/\delta)}{n}}$
(38)

whenever $n\geq 4\bm{r}(\Sigma)+\log(1/\delta)$.

######  Lemma E.8.

Let $A,B\in{\mathbb{S}}^{d}$ be positive semi-definite (PSD) matrices. Then,
we have that

$\textup{Tr}(\sqrt{A+B})\geq\max\\{\textup{Tr}(\sqrt{A}),\textup{Tr}(\sqrt{B})\\}$
(39)

###### Proof.

Since $A+B\succeq A$ and $A+B\succeq B$, by Courant-Fischer min-max theorem,
it holds that $\lambda_{i}(A+B)\geq\lambda_{i}(A)$ and
$\lambda_{i}(A+B)\geq\lambda_{i}(B)$ for their $i$-th largest eigenvalues,
which concludes the proof. ∎

######  Lemma E.9.

Let $A,B\in{\mathbb{S}}^{d}$ be positive semi-definite (PSD) matrices. Then,
we have that

$\textup{Tr}[\sqrt{A+B}]\leq\textup{Tr}[\sqrt{A}]+\textup{Tr}[\sqrt{B}].$ (40)

###### Proof.

First, we assume that both matrices $A$ and $B$ are positive strictly
definite. Then,

$\displaystyle\textup{Tr}(\sqrt{A+B})=$
$\displaystyle\textup{Tr}[(A+B)^{-\frac{1}{4}}(A+B)(A+B)^{-\frac{1}{4}}]$
$\displaystyle=$
$\displaystyle\textup{Tr}[(A+B)^{-\frac{1}{4}}A(A+B)^{-\frac{1}{4}}]+\textup{Tr}[(A+B)^{-\frac{1}{4}}B(A+B)^{-\frac{1}{4}}]$
$\displaystyle=$
$\displaystyle\textup{Tr}[\sqrt{A}(A+B)^{-\frac{1}{2}}\sqrt{A}]+\textup{Tr}[\sqrt{B}(A+B)^{-\frac{1}{2}}\sqrt{B}]$
$\displaystyle\leq$
$\displaystyle\textup{Tr}[\sqrt{A}]+\textup{Tr}[\sqrt{B}],$

where the last inequality holds by
$A^{-\frac{1}{2}}\succeq(A+B)^{-\frac{1}{2}}$ and
$B^{-\frac{1}{2}}\succeq(A+B)^{-\frac{1}{2}}$ (see Lemma E.12). For general
PSD matrices $A$ and $B$, note that

$\displaystyle\textup{Tr}(\sqrt{A+B+\epsilon
I})\leq\textup{Tr}(\sqrt{A+\epsilon I})+\textup{Tr}(\sqrt{B+\epsilon I})$

holds for any $\epsilon>0$ by our previous analysis. Since the trace map is
continuous, ∎

######  Lemma E.10.

Let $z_{1},\cdots,z_{n}\sim{\mathcal{N}}(0,1)$ are i.i.d standard Gaussian.
Then, with probability at least $1-\delta$, it holds that

$\left(\frac{1}{n}\sum_{i=1}^{n}z_{i}\right)^{2}\leq\sqrt{\frac{32}{n^{2}}\log\left(\frac{2}{\delta}\right)}.$

###### Proof.

Note that $\frac{1}{\sqrt{n}}\sum_{i=1}^{n}z_{i}\sim{\mathcal{N}}(0,1)$. By
Lemma E.5, we have that

$\displaystyle{\mathbb{P}}\left(\left|\left(\frac{1}{n}\sum_{i=1}^{n}z_{i}\right)^{2}-\frac{1}{n}\right|>\epsilon\right)=$
$\displaystyle{\mathbb{P}}\left(|U^{2}-1|>n\epsilon\right)\leq
2\exp\left(-\frac{n^{2}\epsilon^{2}}{8}\right)$

where $U^{2}\sim\chi^{2}_{1}$ is a chi-square random variable. Hence, with
probability at least $1-\delta$, it holds that

$\left|\left(\frac{1}{n}\sum_{i=1}^{n}z_{i}\right)^{2}-\frac{1}{n}\right|\leq\sqrt{\frac{8}{n^{2}}\log\left(\frac{2}{\delta}\right)},$

which concludes the proof. ∎

######  Lemma E.11.

Let $z_{1},\cdots,z_{n},u_{1},\cdots,u_{n}\sim{\mathcal{N}}(0,1)$ be i.i.d
standard Gaussian. Then, with probability at least $1-\delta$, it holds that

$\displaystyle\left|\left(\frac{\sum_{i=1}^{n}z_{i}}{n}\right)\left(\frac{\sum_{i=1}^{n}u_{i}}{n}\right)\right|<\frac{1}{n}\sqrt{8\log\left(\frac{4}{\delta}\right)}.$

###### Proof.

Note that $\frac{1}{\sqrt{n}}\sum_{i=1}^{n}z_{i}\sim{\mathcal{N}}(0,1)$.

$\displaystyle\left(\frac{\sum_{i=1}^{n}z_{i}}{n}\right)\left(\frac{\sum_{i=1}^{n}u_{i}}{n}\right)=\frac{1}{n}\left(\frac{\sum_{i=1}^{n}z_{i}}{\sqrt{n}}\right)\left(\frac{\sum_{i=1}^{n}u_{i}}{\sqrt{n}}\right)=\frac{1}{n}ZU,$

where $Z,U\sim{\mathcal{N}}(0,1)$ are i.i.d standard Gaussian. Observe that

$ZU=\frac{1}{4}(Z+U)^{2}-\frac{1}{4}(Z-U)^{2}\sim\frac{1}{2}Q-\frac{1}{2}R,$

where $Q:=\frac{1}{2}(Z+U)^{2},R:=\frac{1}{2}(Z-U)^{2}\sim\chi_{1}^{2}$ are
i.i.d Chi-square distributed with 1 degree of freedom (since
$\frac{1}{\sqrt{2}}(Z+U)$ and $\frac{1}{\sqrt{2}}(Z-U)$ are i.i.d standard
Gaussian). Hence, by Lemma E.5 and a union bound, with probability at least
$1-\delta$,

$\displaystyle\left|\left(\frac{\sum_{i=1}^{n}z_{i}}{n}\right)\left(\frac{\sum_{i=1}^{n}u_{i}}{n}\right)\right|=$
$\displaystyle\left|\frac{1}{2}Q-\frac{1}{2}R\right|\leq\frac{1}{2}\left|Q-1\right|+\frac{1}{2}\left|R-1\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{n}\sqrt{8\log\left(\frac{4}{\delta}\right)},$

which concludes the proof. ∎

######  Lemma E.12.

Let $A,B$ denote two PSD matrices such that $A\succeq B$. Then, their inverse
$B^{-1}\succeq A^{-1}$.

###### Proof.

It suffices to show that $\sqrt{A}B^{-1}\sqrt{A}\succeq I$. Since
$\sqrt{A}B^{-1}\sqrt{A}=(\sqrt{A}B^{-\frac{1}{2}})(\sqrt{A}B^{-\frac{1}{2}})^{\top}$
shares the same eigenvalues with
$(\sqrt{A}B^{-\frac{1}{2}})^{\top}(\sqrt{A}B^{-\frac{1}{2}})=B^{-\frac{1}{2}}AB^{-\frac{1}{2}}\succeq
I$, which concludes the proof. ∎