Diff-BBO: Diffusion-Based Inverse Modeling for Black-Box Optimization

An interesting ablation study would be to add a factor weight 𝛽 in front of the epistemic uncertainty in Equation 8, and to vary this term. This would give an insight into how important uncertainty is in the acquisition process.

Good suggestion. We have conducted additional ablation studies on the factor weight $\beta$ for both discrete task (TFBind8) and continuous task (Ant), with $\beta \in \\{0.6, 0.8. 1.0, 1.2, 1.4\\}$. The results are averaged across three random runs, presented in Table A and Table B. The results show that when $\beta$ value is too low (e.g., $\beta=0.6$), the acquisition function struggles to dynamically determine which $y$ to condition on and keep selecting the highest $y$ with high likelihood. This fixed condition approach results in suboptimal solutions, aligning with our findings from the fixed-condition ablation study. Fine-tuning $\beta$ can also enhance performance; for instance, results in Table B (Ant) show that $\beta = 1.2$ outperforms $\beta = 1.0$.

Table A: TFBind8

Table B: Ant

We thank the reviewer for the constructive comments and thoughtful suggestions. We address the concerns as follows:

From a practical point of view, I am not sure that Theorems 2 and 3 are useful: they assume the 𝐿-smoothness of the function 𝑓. This function takes as input \x, which might be discrete, or an embedding of a discrete input like a molecule, and there is little to no chance to have 𝐿-smoothness in this case unless the embedding explicitly enforces that assumption.

We would like to clarify that our work does not assume L-smoothness; instead, we assume function $f$ satisfies Lipschitz continuity, which is a weaker and more realistic condition in practical settings. The definition of Lipschitz continuity, as provided in Appendix B, states that

$

    \left| f(\boldsymbol{x}^\prime) - f(\boldsymbol{x})\right| \leq L \Vert\boldsymbol{x}^\prime - \boldsymbol{x}\Vert, ~~\forall \boldsymbol{x}^\prime, \boldsymbol{x} \in \mathbb{R}^d.

$

Unlike L-smoothness, which involves a second-order differentiability condition, Lipschitz continuity only relates to the rate of change of $f$ and does not impose additional smoothness constraints. Under this definition, the input need not to be continuous (i.e. input can also be discrete). Lipschitz continuity is a mild and realistic assumption that is commonly satisfied in practical scenarios, even with deep neural networks [1][2]. Our empirical results on diverse tasks—including discrete ones like TFBind8 and TFBind10— also demonstrate that these theoretical guarantees translate into robust and effective optimization performance in practice.

This assumption is imposed for theoretical analyses. We do not assume a perfect diffusion model, which necessitates to bound the difference in the objective space ($f(\boldsymbol{x})$) with that in the design space ($\boldsymbol{x}$), so as to establish meaningful guarantees for the sub-optimality performance gap. It helps quantify how changes in the design space (given by samples generated from diffusion models) affect the objective values.

Furthermore, we would like to emphasize the takeaways of our theorems to form a better understanding for practitioners:

• Quantifying sub-optimality: Theorem 2 establishes that the expected sub-optimality gap is bounded. This means that Diff-BBO provides a principled way to ensure that the generated candidates are close to optimal in expectation.
• Controlling variance through uncertainty: Theorem 3 highlights that the variance of the sub-optimality gap is influenced by both aleatoric (inherent noise) and epistemic (model uncertainty) components. This decomposition underscores the importance of reducing epistemic uncertainty to stabilize the optimization outcomes and enhance reliability.
• Balancing exploration and exploitation: Theorem 4 provides a theoretical foundation for the design of our acquisition function, Uncertainty-aware Exploration (UaE), which balances targeting high objective values and minimizing epistemic uncertainty. This balance enables practitioners to efficiently explore the design space while ensuring reliable convergence to optimal solutions.

[1] Bartlett, Peter L., Dylan J. Foster, and Matus J. Telgarsky. "Spectrally-normalized margin bounds for neural networks." Advances in neural information processing systems 30 (2017).

[2] Fazlyab, Mahyar, et al. "Efficient and accurate estimation of lipschitz constants for deep neural networks." Advances in neural information processing systems 32 (2019).

This is a minor point, but I was wondering if a weight should be assigned to Δ in Equation (8) because (1) the two terms might be in different scales.

Good suggestion. We added a factor weight $\beta$ in front of the epistemic uncertainty in Equation 8 and conducted additional ablation studies for both discrete task (TFBind8) and continuous task (Ant), with $\beta \in \\{0.6, 0.8. 1.0, 1.2, 1.4\\}$. The results are averaged across three random runs, presented in Table A and Table B. The results show that when $\beta$ value is too low (e.g., $\beta=0.6$), the acquisition function struggles to dynamically determine which $y$ to condition on and keep selecting the highest $y$ with high likelihood. This fixed condition approach results in suboptimal solutions, aligning with our findings from the fixed-condition ablation study. Fine-tuning $\beta$ can also enhance performance; for instance, results in Table B (Ant) show that $\beta = 1.2$ outperforms $\beta = 1.0$.

Table A: TFBind8

Table B: Ant

Under a similar Lipschitz assumption, is it possible to derive surrogate approximation guarantees for the forward-based approach? If so, how does the inverse bound compare to the forward bounds?

We thank the reviewer for raising this question. While this is an intriguing direction, we would like to clarify the following points:

• Incomparable purposes: Forward approaches and our inverse modeling framework serve fundamentally different purposes, making a direct comparison of bounds less meaningful. Forward methods typically aim to model the unknown objective function $f$, while our approach focuses on inverse modeling to propose optimal candidates. Consequently, the theoretical results derived for our inverse approach are tailored to justify the design and validity of our acquisition function, Uncertainty-aware Exploration (UaE), rather than to compete with or replicate bounds from forward methods.
• Heuristic nature of forward acquisition functions: Most acquisition functions in forward approaches are based on heuristics, rather than bounds grounded in surrogate approximation guarantees. While forward-based methods are effective in practice, their theoretical guarantees are typically unavailable. The most aligned results are only available in bandit literature rather than the online black-box optimization literature, rendering highly-different problem domains. While deriving theoretical guarantees for forward-based approaches under similar assumptions could be interesting, such an exploration is far beyond the scope of this paper.
• The primary goal of our theoretical analysis is not to derive state-of-the-art tight bounds but to provide a sound justification for the design of UaE. Our results establish that UaE balances exploration and exploitation effectively, leveraging both the inherent properties of conditional diffusion models and the epistemic uncertainty to achieve robust optimization performance.

Furthermore, we would like to emphasize the takeaways of our theorems to form a better understanding for practitioners:

• Quantifying sub-optimality: Theorem 2 establishes that the expected sub-optimality gap is bounded. This means that Diff-BBO provides a principled way to ensure that the generated candidates are close to optimal in expectation.
• Controlling variance through uncertainty: Theorem 3 highlights that the variance of the sub-optimality gap is influenced by both aleatoric (inherent noise) and epistemic (model uncertainty) components. This decomposition underscores the importance of reducing epistemic uncertainty to stabilize the optimization outcomes and enhance reliability.
• Balancing exploration and exploitation: Theorem 4 provides a theoretical foundation for the design of our acquisition function, Uncertainty-aware Exploration (UaE), which balances targeting high objective values and minimizing epistemic uncertainty. This balance enables practitioners to efficiently explore the design space while ensuring reliable convergence to optimal solutions.

We thank the reviewer for the constructive comments and thoughtful suggestions. We address the concerns as follows:

in Theorem 2, the bound does not depend on the number of samples collected in each iteration 𝑁. Intuitively, a large 𝑁 might lead to over-conservative estimates and a small 𝑁 might renders the estimate too optimistic. Relating the this bound to 𝑁 may lead to insights into the choice of this important hyper-parameter. The current bound is independent of 𝑁, suggesting that it might be loose.

We did consider $N$ and assigned $N = 1$, as noted in Appendix B (line 861). We provide the clarification on the role of $N$ in our analysis and its implications for Theorem 4 below.

• Purpose of Theorem 2 and 3: Theorem 2 and 3 are designed to provide a general bound on the sub-optimality performance gap that holds under all circumstances, independent of specific hyperparameter choices such as $N$. This generality is necessary to support Theorem 4, which justifies the validity of our acquisition function, Uncertainty-aware Exploration (UaE). By providing a bound that does not depend on $N$, we ensure that Theorem 4 remains robust and valid for any $N$, including cases where only a single sample ($N = 1$) is used in each iteration.
• In our proofs, we assume $N = 1$ to simplify the analysis. This assumption aligns with the theoretical focus of Theorem 2 and 3 on providing a general bound.
• Problems with high-probability bounds: Extending the analysis to $N > 1$ would require incorporating high-probability bounds, which account for the variability introduced by multiple samples. While such bounds can provide additional insights, they do not always hold universally due to their dependence on specific statistical properties of the sampling process (e.g., tail bounds, variance). As a result, further assumptions will be required in order to have a tighter bound. However, as we explained earlier, this does not satisfy our purpose of supporting the claims of Theorem 4. Besides, when $N$ is small, the estimates may be overly optimistic due to insufficient exploration, whereas a large $N$ might lead to conservative estimates that dilute the benefits of targeted sampling. These trade-offs would require further assumptions and could complicate the generality of Theorem 4.
• Insights into practical hyperparameter choices: Although Theorem 2 provides a bound independent of $N$, its practical implications remain valid for guiding the design of the acquisition function.

this theorem assumes the existence of a perfect diffusion model. I suggest the authors add further discussion on the implication/validity of this assumption.

There may be a misunderstanding. Our theoretical analysis does not assume the existence of a perfect diffusion model. That’s why we need to introduce the Lipschitz continuity assumption to consider the sampling errors brought by the diffusion model. It ensures that the sub-optimality performance gap can be meaningfully bounded, even when the diffusion model does not perfectly reconstruct the target conditional values $y_k^*$ in each iteration $k$. In particular, we bound the error in the value space ($f(\boldsymbol{x})$) with that in the design space ($\boldsymbol{x}$), so as to establish meaningful guarantees for the sub-optimality performance gap and its variance. It helps quantify how changes in the input design space (given by samples generated from diffusion models) affect the objective values.

We thank the reviewer for the constructive comments and thoughtful suggestions. We address the concerns as follows:

An important part of the procedure is how is assembled the candidate set 𝑌 and its corresponding weights 𝑤. The paper does not specify a principled method for choosing or tuning these weights, which makes this important aspect somewhat empirical given that for too high weights, the model may focus excessively on unfeasibly high values of 𝑦 while too low weights might limit the search space.

Is there a systematic approach for choosing the weights 𝑤 for the candidate set 𝑌, or is this step largely empirical?

We would like to clarify that selecting the weights $w$ is equivalent to select the objective values $y$ since $y = w.\phi_k$ (line 240), where $\phi_k$ is a predetermined constant ($\phi_k$ is the maximum function value being queried in the current training dataset D (line 241-242)). We did provide a principled method for choosing $y$ (equivalently choosing weight $w$) using the acquisition function uncertainty-aware exploration (UaE). Specifically, we identify the optimal scalar value $y^*$ as $y^*= \text{argmax}_y \alpha(y,D)$, where $\alpha(y,D)= y- \text{epistemic}(y, D)$ (Eqn 8). We employ this acquisition function to ensure safe exploitation on high $y$ values. Additionally, Diff-BBO leverages the advantages of the diffusion model, utilizing the stochastic nature of the diffusion process to explore the design space. Therefore, low values of $y$ or $w$ do not limit the search space.

A diffusion model requires a large dataset to effectively learn the data manifold in the design space. If the function 𝑓 is expensive to evaluate, building a large dataset may be computationally expensive. Most of the experiments are run with a relatively high number of evaluations. How would the method perform on a smaller dataset?

Could the method perform effectively with a smaller accumulated dataset, as opposed to the relatively high number of evaluations used in the experiments?

We agree that training a deep generative model such as diffusion model requires a relatively large dataset in learning the data distribution. However, this data requirement is only required at the initial stage. Meanwhile Diff-BBO does not demand high-quality data for the initial training set. In our experimental setup, we only include the data with below-average objective scores from the offline dataset of design-bench in the initial training set (line 427-429). This mirrors a common scenario in real-world experimental design tasks, where preexisting and unoptimized data is available in databases. At the active learning stage, The experiment results shows that Diff-BBO is much more sample-efficient compared with other baselines (shown on Figure 3). Furthermore, we conducted an ablation study (shown on Figure 5) to verify that Diff-BBO is robust w.r.t the varying batch sizes, ranging from 25 to 200.

Diffusion models are usually susceptible to mode collapse, where generated samples fail to cover the full distribution of the data. Was this observed? This could cause Diff-BBO to overlook potentially optimal regions in the design space.

Was this issue of mode collapse observed in Diff-BBO? If so, how does it impact the model’s ability to explore potentially optimal regions in the design space?

We did not encounter the mode collapse issue when using the conditional diffusion model. It is also important to note that prior studies indicate that diffusion models are more robust against mode collapse compared to other generative models, such as GANs [1][2][3]. The stochastic nature of the diffusion process enables the model to cover the data distribution more comprehensively. As a result, it can capture the diversity of the dataset and generate versatile samples. This capability is particularly beneficial for our Diff-BBO algorithms to enhance the exploration of the design space.

[1] Ulhaq, Anwaar, and Naveed Akhtar. "Efficient diffusion models for vision: A survey." arXiv preprint arXiv:2210.09292 (2022)

[2] Croitoru, Florinel-Alin, et al. "Diffusion models in vision: A survey." IEEE Transactions on Pattern Analysis and Machine Intelligence 45.9 (2023): 10850-10869.

[3] Kazerouni, Amirhossein, et al. "Diffusion models in medical imaging: A comprehensive survey." Medical Image Analysis 88 (2023): 102846.

Why do the experimental tasks of online BBO methods use offline BBO benchmarks? Is it because there is no suitable benchmark for online BBO?

There may be a misunderstanding. We did not use offline BBO benchmarks. Instead, we restructured 5 high-dimensional real-world tasks in biology, materials science, and robotics from Design-Bench to facilitate online black-box optimization. At each iteration, the online BBO algorithms query the oracle function to generate new data instead of using the Design-Bench offline dataset. We also included the new molecular discovery task. The details are provided in Section 6.1 and Appendix D.1. The reason we compared Diff-BBO with other baselines on these tasks is to verify the effectiveness of Diff-BBO on real-world science and engineering problems where the valid data represent a small subspace in the high-dimensional design space as we mentioned in Section 1 (line 41-44).

“They struggle with steering clear of out-of-distribution and invalid inputs” is often discussed in offline BBO instead of in online BBO. The reason why this paper presents it here for online setting should be discussed.

The challenge of steering clear of out-of-distribution and invalid inputs does not depend on whether it is in an offline or online BBO setting. Indeed, it depends on the design space. When the design space is high-dimensional and valid designs constitute a small subset of this space, such optimization problems become exceptionally difficult, since the optimizer must avoid out-of-distribution and invalid inputs [9]. Consider an example of online BBO on this type of design space using Gaussian Processes. Once the designed acquisition function proposes a candidate in the design space, the forward surrogate model lacks the capability to determine whether this candidate is valid without explicit constraint information.

This type of optimization problem is common in real-world science and engineering tasks. We conducted 6 such tasks and verified that Diff-BBO utilizing the conditional diffusion model for inverse modeling can capture data distributions in the design space, facilitate optimization within the data manifold, and therefore outperforms state-of-the-art forward approaches in terms of sample efficiency.

[9] Kumar, Aviral, and Sergey Levine. "Model inversion networks for model-based optimization." Advances in neural information processing systems 33 (2020): 5126-5137.

Superconductor, Ant and D’Kitty and so on are high dimensional problem. So, it would be better if this paper could compare with more high dimensional Bayesian optimization in recent years rather than simple black-box optimization.

We have already compared Diff-BBO against multiple state-of-the-art black-box optimization baselines. For high-dimensional Bayesian optimization baselines, we included Trust Region BO (TuRBO) [1] and Local Latent Space Bayesian optimization (LOL-BO) [2]. For acquisition function design, we included Joint Entropy Search (JEE) [3]. We also included Likelihood-free BO (LFBO) [4] and Conditioning by adaptive sampling (CbAS) [5] approaches. The details are provided in Section 6.2.

the paper does not sufficiently explore prior work in offline BBO. Expanding the discussion to include them could provide a more comprehensive literature review and motivation support.

The problem setting of our paper is online BBO. The research focus significantly diverges between online BBO and offline BBO. Online BBO aims to improve the sample efficiency of the sequential decision making algorithm. In contrast, offline BBO assumes access to a fixed pre-collected dataset (line 53-55) and focuses on the surrogate modeling design.

We mentioned the offline BBO setting in our paper primarily to contextualize the inverse surrogate modeling approach using deep generative models, which was originally introduced in the offline setting. However, the offline BBO setting itself is not directly relevant to our approach. Additionally, we have already discussed both inverse surrogate modeling and offline BBO [6][7][8][9][10][11][12][13] in the introduction and related work. We are happy to include additional relevant offline BBO references should there be any omissions.

[1] Eriksson, David, et al. "Scalable global optimization via local Bayesian optimization." Advances in neural information processing systems 32 (2019).

[2] Maus, Natalie, et al. "Local latent space bayesian optimization over structured inputs." Advances in neural information processing systems 35 (2022): 34505-34518.

[3] Hvarfner, Carl, Frank Hutter, and Luigi Nardi. "Joint entropy search for maximally-informed Bayesian optimization." Advances in Neural Information Processing Systems 35 (2022): 11494-11506.

[4] Song, Jiaming, et al. "A general recipe for likelihood-free Bayesian optimization." International Conference on Machine Learning. PMLR, 2022.

[5] Brookes, David, Hahnbeom Park, and Jennifer Listgarten. "Conditioning by adaptive sampling for robust design." International conference on machine learning. PMLR, 2019.

[6] Fu, Justin, and Sergey Levine. "Offline model-based optimization via normalized maximum likelihood estimation." arXiv preprint arXiv:2102.07970 (2021).

[7] Kong, Lingkai, et al. "Diffusion models as constrained samplers for optimization with unknown constraints." arXiv preprint arXiv:2402.18012 (2024).

[8] Krishnamoorthy, Siddarth, Satvik Mehul Mashkaria, and Aditya Grover. "Diffusion models for black-box optimization." International Conference on Machine Learning. PMLR, 2023.

[9] Kumar, Aviral, and Sergey Levine. "Model inversion networks for model-based optimization." Advances in neural information processing systems 33 (2020): 5126-5137.

[10] Li, Zihao, et al. "Diffusion model for data-driven black-box optimization." arXiv preprint arXiv:2403.13219 (2024).

[11] Lu, Huakang, et al. "Degradation-Resistant Offline Optimization via Accumulative Risk Control." ECAI 2023. IOS Press, 2023. 1609-1616.

[12] Trabucco, Brandon, et al. "Design-bench: Benchmarks for data-driven offline model-based optimization." International Conference on Machine Learning. PMLR, 2022.

[13] Wang, Handing, et al. "Offline data-driven evolutionary optimization using selective surrogate ensembles." IEEE Transactions on Evolutionary Computation 23.2 (2018): 203-216.

We thank the reviewer for the constructive comments and thoughtful suggestions. We address the concerns as follows:

The core difference between the main idea of the proposed method (the inverse method) and LLAMBO [1] should be explicitly discussed. While there are differences in the specific implementation details compared to LLAMBO.

Thanks for sharing the LLAMBO paper. We have included it in the related work of our revised manuscript (line 88-90). Diff-BBO and LLAMBO are fundamentally different approaches in terms of surrogate model and acquisition function design, which can be well illustrated in Figure 1.

• LLAMBO utilizes LLMs to improve Bayesian optimization. It belongs to forward surrogate modeling to estimate the likelihood $p(y|x,D)$ or $p(y \leq \tau|x,D)$, whereas Diff-BBO belongs to inverse surrogate modeling. This involves directly modeling the posterior $p(x|y,D)$ using the conditional diffusion model.
• LLAMBO is proposed to deal with hyperparameter tuning problems where there are no validity concerns in the design space, meaning that every combination of hyperparameters in the hyperparameter space is valid. Diff-BBO is proposed to deal with the science and engineering tasks where the design space is high-dimensional and valid designs constitute a small subset of this space.
• LLAMBO's acquisition function is a function of $x$. The goal is to find the optimal $x$ in the design space. Conversely, the acquisition function in Diff-BBO is a function of $y$. The goal is to find the optimal objective $y$ for conditional sampling.

this approach appears to be more of an aggregation of the previous methods. Specifically, the inverse approach was originally utilized in MINS [2], while the conditional diffusion model was incorporated in DDOM [3].

Our paper presents three main contributions that distinguish Diff-BBO from LLAMBO, MINS, and DDOM:

• We design an acquisition function Uncertainty-aware Exploration (UaE) for inverse modeling. Theoretically, we prove that Diff-BBO using UaE achieves a near-optimal solution in online black-box optimization.
• We propose Diff-BBO, an inverse modeling approach for online black-box optimization that utilizes a conditional diffusion model, providing both empirical significance and theoretical guarantees.
• We provide an uncertainty decomposition into epistemic uncertainty and aleatoric uncertainty for conditional diffusion model. We rigorously analyze how uncertainty propagates throughout the denoising process of conditional diffusion model.

We would like to emphasize the takeaways of our theorems to form a better understanding for practitioners:

• Quantifying sub-optimality: Theorem 2 establishes that the expected sub-optimality gap is bounded. This means that Diff-BBO provides a principled way to ensure that the generated candidates are close to optimal in expectation.
• Controlling variance through uncertainty: Theorem 3 highlights that the variance of the sub-optimality gap is influenced by both aleatoric (inherent noise) and epistemic (model uncertainty) components. This decomposition underscores the importance of reducing epistemic uncertainty to stabilize the optimization outcomes and enhance reliability.
• Balancing exploration and exploitation: Theorem 4 provides a theoretical foundation for the design of our acquisition function, Uncertainty-aware Exploration (UaE), which balances targeting high objective values and minimizing epistemic uncertainty. This balance enables practitioners to efficiently explore the design space while ensuring reliable convergence to optimal solutions.

Thanks for the feedback and I have read the rebuttal.

The rebuttal addresses some of my concerns. However, the concerns of experiments in the review have not been fully addressed.

Besides, from the rebuttal, it involves many issues: online optimization, offline optimization, OOD, high-dimension optimization, and constrained optimization, which makes the motivation and presentation of this paper become more unclear. The evidence and experiments in the current version cannot fully support these issues and motivations.

Best regards