Be More Diverse than the Most Diverse: Optimal Mixtures of Generative Models via Mixture-UCB Bandit Algorithms

Authors: Parham Rezaei, Farzan Farnia, Cheuk Ting Li
Primary area: reinforcement learning
Keywords: Multi-Armed Bandits, Evaluation of generative models, Kernel-based evaluation scores, Mixture-UCB, Diversity in data generation

Abstract:
The availability of multiple training algorithms and architectures for generative models requires a selection mechanism to form a single model over a group of well-trained generation models. The selection task is commonly addressed by identifying the model that maximizes an evaluation score based on the diversity and quality of the generated data. However, such a best-model identification approach overlooks the possibility that a mixture of available models can outperform each individual model. In this work, we numerically show that a mixture of generative models on benchmark image datasets can indeed achieve a better evaluation score (based on FID and KID scores), compared to the individual models. This observation motivates the development of efficient algorithms for selecting the optimal mixture of the models. To address this, we formulate a quadratic optimization problem to find an optimal mixture model achieving the maximum of kernel-based evaluation scores including kernel inception distance (KID) and Rényi kernel entropy (RKE). To identify the optimal mixture of the models using the fewest possible sample queries, we view the selection task as a multi-armed bandit (MAB) problem and propose the *Mixture Upper Confidence Bound (Mixture-UCB)* algorithm that provably converges to the optimal mixture of the involved models. More broadly, the proposed Mixture-UCB can be extended to optimize every convex quadratic function of the mixture weights in a general MAB setting. We prove a regret bound for the  Mixture-UCB algorithm and perform several numerical experiments to show the success of Mixture-UCB in finding the optimal mixture of text and image generative models. The project code is available in the [Mixture-UCB Github repository](https://github.com/Rezaei-Parham/Mixture-UCB).

Decision: accept (poster)
Reviewer scores: 6, 6, 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1730758316106

thread_type:
official_review

<thread_object>
creator: reviewer_ncw5

<content>
summary:
This paper study online selection for generative models, in order to generate diverse samples. The authors formulated the problem as a mixture multi armed bandit problem and developed two algorithms for that: Mixture-UCB-CAB and Mixture-UCB-OGD. The authors developed theoretical guarantees for the Mixture-UCB-CAB algorithm. The authors conduct many experiments to show the efficacy of their developed methods.

strengths:
It's interesting to see the authors formulated the generative model selection problem as an online selection problem. The authors also developed two algorithms for this new setting and provide theoretical guarantees for one of them. Experimental results demonstrate the efficacy of the proposed algorithms.

weaknesses:
1. Since this is a new problem, can authors provide more motivations for online selection of generative models, e.g., how important is the ability to generate diverse samples? And how important is to save samples in the selection process.
2. The authors provide a convergence guarantee for Mixture-UCB-CAB in Thm 2. For comparison, what is the rate of convergence for the offline approach that randomly generate $T$ samples and then optimize over $\alpha$?
3. Does Thm 1 holds for all $\alpha$? Also, the guarantee in Thm 2 doesn't suffer the curse of dimensionality even if the algorithm is selection $\alpha \in R^m$; can authors explain why does that happen?
4. Compared to standard bandit problem where one gets an intermediate regret term at each round, it seems that the studied problems gets $O(t)$ (averaged) terms (the first Eq in Section 5), and all these terms are related to the previous selections $x_1, \cdots, x_{t-1}$. Can authors elaborate how do they deal with these terms in the analysis? What are some technical contributions?

questions:
See above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730942453152

thread_type:
official_review

<thread_object>
creator: reviewer_mqps

<content>
summary:
The main goal of this work is to maximize the diversity of generated samples by selecting not a single but a mixture of generative models. Formulating first a population loss of quadratic form that can translate into evaluation scores including kernel inception distance (KID) and Renyi kernel entropy (RKE), this article proposes two online algorithms based on continuum-armed bandit and gradient descent, to find the optimal mixture through minimizing an upper confidence bound of the quadratic population loss.  Experiments show that the proposed algorithms are efficient at approaching the optimal mixture.

strengths:
* This paper is well written and easy to follow.

* The theoretical framework underlying the proposed algorithms is well grounded.

* Extensive experiments were carried out to demonstrate the performance of the proposed algorithms.

weaknesses:
* According to the literature review of this article, there seems to be little interest in finding a good mixture of different generative models. Indeed, if the goal is to approach the target distribution, it makes more sense to select the single best generative model than to use a mixture of different generative models, which are usually trained in an independent manner, therefore unlikely to complement each other.

* It is true that when the objective is to find the single best generative model, the online approach can help prevent sampling from suboptimal models. However, as using a mixture of generative models requires sampling from all member models, the online approach seems to be less useful in this setting.

questions:
* Can the authors find some other works that also aim to find good mixtures of generative models, and compare their method to these works?

* Can the authors provide the quality scores Density (Naeem et al., 2020). and Precision (Kynkaanniemi et al., 2019) in the experiments that they conducted?

* Small question regarding Lines 257&259: is $\hat{L}(\mathbf{a};\mathbf{x}^{(t)})-(\mathbf{\epsilon}^{(t)})^{\rm T}\mathbf{a})$ a lower or upper bound of $L(\mathbf{a})$?



=======================================================================================================

**Update after rebuttal**

I would like to apologize for an important error that I made in the example presented in my last comment to the authors. I was so rushed to post this last comment before the discussion deadline to give the authors a chance to respond that I did not get to double check my math. As there is no other means for me to reach out to the authors, I have to rectify this error for the authors' information by editing my official review (at the suggestion of AC).

The error, which I realized after the deadline, came from the application of the FID formula. Under the assumption of Gaussian distributions, the FID is measured by 
$$d_{\rm F}\left(P_r,P_g\right)=\Vert\mu_r-\mu_g\Vert^2+{\rm tr}\left(\Sigma_r+\Sigma_g-2(\Sigma_r\Sigma_g)^{\frac{1}{2}}\right)$$
where $\mu_r,\mu_g$ and $\Sigma_r,\Sigma_g$ are respectively means and covariances of $P_r,P_g$.

As in my example, the covariances of the real distribution $\mathcal{N}(\mu_r,I)$ and the two generative models $\mathcal{N}(\mu_g,I),\mathcal{N}(\mu_{\tilde{g}},I)$ are identity matrices, the FIDs are simply distances between the means:
$$d_{\rm F}\left(\mathcal{N}(\mu_r,I),\mathcal{N}(\mu_g,I)\right)=\Vert\mu_r-\mu_g\Vert^2=\Vert\epsilon_g\Vert^2,$$
$$d_{\rm F}\left(\mathcal{N}(\mu_r,I),\mathcal{N}(\mu_{\tilde{g}},I)\right)=\Vert\mu_r-\mu_{\tilde{g}}\Vert^2=\Vert\epsilon_{\tilde{g}}\Vert^2.$$

The error occurred when I calculated the FID between $\mathcal{N}(\mu_r,I)$ and a mixture $\mathcal{M}=\alpha\mathcal{N}(\mu_g,I)+\tilde{\alpha}\mathcal{N}(\mu_{\tilde{g}},I)$ of the two generative models. While the mean of $\mathcal{M}$ is indeed $\alpha\mu_g+\tilde{\alpha}\mu_{\tilde{g}}$ as I said in my comment to the authors, the covariance, however, should be $I+\alpha\tilde{\alpha}(\mu_g-\mu_{\tilde{g}})(\mu_g-\mu_{\tilde{g}})^{\rm T}$, **not** $I$. 

Therefore, $d_{\rm F}\left(\mathcal{N}(\mu_r,I),\mathcal{M}\right)\approx\Vert\mu_r-\alpha\mu_g-\tilde{\alpha}\mu_{\tilde{g}}\Vert^2+\alpha\tilde{\alpha}\Vert\mu_g-\mu_{\tilde{g}}\Vert^2$ for large $\Vert\mu_g-\mu_{\tilde{g}}\Vert^2$, 
leading to
$$d_{\rm F}\left(\mathcal{N}(\mu_r,I),\mathcal{M}\right)\approx\Vert\alpha\epsilon_g+\tilde{\alpha}\epsilon_{\tilde{g}}\Vert^2+\alpha\tilde{\alpha}\Vert\epsilon_g-\epsilon_{\tilde{g}}\Vert^2.$$Then we have, for independent $\epsilon_g,\epsilon_{\tilde{g}}$, that
$$E\\{d_{\rm F}\left(\mathcal{N}(\mu_r,I),\mathcal{M}\right)\\}\approx\alpha^2E\\{\Vert\epsilon_g\Vert^2\\}+\tilde{\alpha}^2E\\{\Vert\epsilon_{\tilde{g}}\Vert^2\\}+\alpha\tilde{\alpha}E\\{\Vert\epsilon_g\Vert^2\\}+\alpha\tilde{\alpha}E\\{\Vert\epsilon_{\tilde{g}}\Vert^2\\}=\alpha E\\{\Vert\epsilon_g\Vert^2\\}+\tilde{\alpha}E\\{\Vert\epsilon_{\tilde{g}}\Vert^2\\},$$
which is always minimized by taking the single model with the smallest error.

The intuitive reasoning behind this example is that a mixture of Gaussians is unlikely to match better the target Gaussian distribution than (the best) single Gaussians. The lack of discussion on the limitations and the risks of the mixture approach is my main criticism of this work.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731378818636

thread_type:
official_review

<thread_object>
creator: reviewer_guyr

<content>
summary:
In this paper, the authors focus on the online selection of generative models, and in particular, the optimal linear mixture among a set of such models.
The problem appears novel, and the authors make interesting connections to the maximization of some kernel-based scores and multi-armed bandit. 
Based on this, the authors propose Algorithms 1 and 2 to solve this online selection of mixture efficiently, with performance guarantee given in Theorem 1 and 2, respectively. (Although I have some concerns on the settings and theoretical results, see below).
These methods can be used for widely used kernel inception distance (KID) and Renyi kernel entropy (RKE), and are tested on realistic image and text data in Section 6.

strengths:
* The paper consider online selection of generative mixture models, which, to the best of knowledge, is a novel problem of interest.
* By making interesting connection to kernel-based scores and multi-armed bandit, the authors propose efficient methods to solve the above problem, with some theoretical guarantee. 
* Experiments on realistic data are provided, showing the practical applicability of the proposed approaches.

weaknesses:
* It would be great to discuss the limitation of the proposed approach, see below for my detailed comments/questions.
* some settings and theoretical results need clarification, see below for my detailed comments/questions.

questions:
Below are a few questions and/or comments.

1. The problem appears novel, so I believe it makes sense to better motivative it. For example, in which context are we interested in picking a model to generate a sample at each round, why it is of interest to use "the fewest possible sample queries"? How the proposed method performs in an offline setting, with respect to performance and/or scalability?
2. When summarizing the contribution of this paper, could the authors also provide (forward) pointers to the precise results? For example, "proposing an online learning framework in Section ??". I personally believe that this may facilitate the interested readers to quickly grasp the main contribution of the paper.
3. Is the working assumption of linearly mixed model somewhat restrictive? Is there something else in the literature, or even such linear combination is (the first time) proposed by the authors in this paper? In fact, on the top row of Figure 3, there is a linearly mixtured "dog" that appears a bit bizarre: is this due to some limitation of this linear mixture? 
4. I personally find Theorem 1 a bit surprising: To me, kernel matrix "estimation" problem plus some online selection problem, and solving the former problem in general requires a lot of samples to have a tight spectral norm control on the estimated kernel matrix. I believe that the authors avoid this issue by assuming/focusing on the case of bounded. Could the authors comment more on this? For example, does this bounded kernel/loss function setting limit the practical interest of the proposed methods? Also, could the authors comment on the observed sample size $n_i$ for the proposed OGD method to make sense? We do not see this in Theorem 2 and this has an impact on the computational complexity I believe?
5. a tiny side remark: Figure 3 appears in the main text but commented in the appendix.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731426507399

thread_type:
official_review

<thread_object>
creator: reviewer_pb52

<content>
summary:
This paper aims to solve the online selection task over a group of well-trained generation models. It explores the selection of a mixture of multiple generative models and formulate a quadratic optimization problem to optimize the kernel-based evaluation scores including kernel inception distance (KID) and Renyi kernel entropy (RKE). Specifically, it proposes an online learning approach called Mixture Upper Confidence Bound (Mixture-UCB). Theoretically, regret analysis is provided for one method (Mixture-UCB-CAB). Experimental results illustrate the effectiveness of the proposed method for text-based and image-based generative models.

strengths:
1. Overall, this paper is well-written and easy to follow.
2. The proposed method (Mixture-UCB) is somehow novel, although it is inspired by classical UCB in the multi-armed bandit setting.
3. Theoretical results about the regret bound are provided for the proposed Mixture-UCB-CAB. The proof seems right although I have not checked the proof line-by-line.
4. Empirical results illustrate the effectiveness of the proposed method in finding the optimal mixture of text-based and image-based generative models.

weaknesses:
1. I am afraid that the online selection of well-trained generative models might have few applications because it is already costly for the (large) generative model inference, then why do we need online selection rather than batch selection? Discussions about practical applications can be added.
2. Experimental results show that Mixture-UCB-OGD might be better than Mixture-UCB-CAB. However, theoretical guarantees about Mixture-UCB-OGD are missing. I know it might be more challenging and more detailed discussions can be added to clarify why.

questions:
In practice, FID metric is widely-used in the evaluation of generative models. Can this paper cover this metric and why?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732305067727

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Authors' General Response

comment:
We thank the reviewers for their constructive and thoughtful feedback. An updated paper has been submitted (changes are highlighted in blue). Here we address a common question from the reviewers. Responses to the other comments of the reviewers are posted under each review.

**1-Motivations behind the online selection of generative models** 

     
We argue that the combination of generative models is inherently an online learning problem. Generating samples from a model is costly, in terms of computational time and resources, and perhaps monetary cost for commercial models, e.g. Dall-E and Flux 1.1 Pro. Therefore, we should naturally generate a small number of samples from each model and evaluate them, before we decide which model to use next, and keep using the new samples to guide our selection of the next model to use. This is similar to how a human would act when given a number of generative models that are costly to use. This paper proposes an algorithm to automate this process, with a tight bound on its regret (see updated discussion after Theorem 2).

An offline two-stage method (where we first generate a fixed large number of samples from each model in Stage 1, and then use them to compute the mixture distribution for the remaining samples in Stage 2) can be suboptimal since we are not discarding the obviously suboptimal arms in the middle of Stage 1, and we are not utilizing the information in the new samples in Stage 2 to update the mixture distribution.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732529749808

thread_type:
official_review

<thread_object>
creator: reviewer_x3ew

<content>
summary:
Given a group of generative models, this paper studies the problem of improving the diversity (and quality) of generated outputs by combining them into an (optimal) mixture. The authors present the Mixture-UCB framework, encompassing two specific algorithms, Mixture-UCB-CAB and Mixture-UCB-OGD, designed by iteratively optimizing a quadratic objective (wrt the mixture weights) on kernel-based eval metrics and efficiently formulating the mixture of models under an online bandit setting. Specific metrics include Kernel Inception Distance (KID) and Rényi Kernel Entropy (RKE). Theoretical regret bounds have provided adequate support for Mixture-UCB-CAB, and experimental evaluations demonstrate the advantages of both algorithms across various datasets and model types.

strengths:
1. The paper is generally well-written and well-structured, with clear definitions and visualizations.
2. The focus on mixtures of generative models to achieve superior diversity (and quality) appears innovative and addresses a limitation in traditional model selection approaches, which aim to find only a single best-performing model. Being able to customize the support size of the mixture is a good plus. 
3. The theoretical analysis for Mixture-UCB-CAB is well-formulated and provides near-optimal guarantees (i.e., up to logarithmic factors of $m$ and $T$).
4. The diverse experiments demonstrate the algorithms' practical applications and performance gains, especially in exciting domains such as text-to-image generation.

weaknesses:
1. While Mixture-UCB-OGD seems computationally more efficient than Mixture-UCB-CAB, the absence of a theoretical guarantee akin to Theorem 2 for CAB leaves an open question about its convergence and reliability.
2. Linear mixtures show their ability to enhance diversity. Still, the data distributions might produce mixtures that lack coherence, as some of the visual examples hint at (e.g., in Figure 3, the mixture model generated both realistic and unrealistic car images). In other words, optimizing the single diversity metric may not capture users' needs (e.g., a model that can generate images of cars with different sizes, poses, coloring styles, and backgrounds may be more natural to be said "diverse").
3. The mixture model approach may not be suitable for memory-efficient use cases, such as deployment on end devices like smartphones or smart home modules. Storing, updating, and switching among multiple generative models (e.g., this might require loading new parameters into memory) could significantly increase memory requirements and other costs, making the approach impractical for some critical applications. A possible mitigation strategy could be distilling a mixture of large models into a single, smaller-scale model, thereby retaining the benefits of the mixture while reducing resource needs.

questions:
Could the authors kindly consider the weaknesses highlighted above and share any thoughts, feedback, or responses they might have? Also, I wonder about the typical scenarios where the mixture models fail to improve diversity or quality.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper addresses the problem of online selection to obtain a mixture of generative models. 
To minimize the number of sample queries needed to form the optimal mixture model, the authors propose the Mixture Upper Confidence Bound (Mixture-UCB) online learning approach, by maximizing kernel-based evaluation scores such as the Kernel Inception Distance (KID) and Renyi Kernel Entropy (RKE). 
Both theoretical results (e.g., regret bounds) and empirical results are provided to demonstrate the effectiveness of the proposed method.

Following the rebuttal phase, the reviewers reached a consensus that the (novel) problem under study is well-motivated and that the contribution of this work is significant. 
As such, I recommend accepting the paper. 
However, **please update** the final submission to reflect the discussions with all reviewers (and particularly Reviewers x3ew and mqps), including a discussion of the potential limitations (of the setting, and/or of the proposed approach).