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

Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-08-30 00:39:29

Abstract: Black-box optimization (BBO) aims to optimize an objective function by iteratively querying a black-box oracle in a sample-efficient way. While prior studies focus on forward approaches to learn surrogates for the unknown objective function, they struggle with steering clear of out-of-distribution and invalid inputs. Recently, inverse modeling approaches that map objective space to the design space with classifier-free conditional diffusion models have demonstrated impressive capability in learning the data manifold. They have shown promising performance in offline BBO tasks. However, these approaches require a pre-collected dataset. How to design the acquisition function for inverse modeling to actively query new data remains an open question. In this work, we propose diffusion-based inverse modeling for black-box optimization (Diff-BBO), an inverse approach leveraging diffusion models for online BBO problem. Instead of proposing candidates in the design space, Diff-BBO employs a novel acquisition function Uncertainty-aware Exploration (UaE) to propose objective function values. It leverages the uncertainty of a conditional diffusion model to generate samples in the design space. We demonstrate that using UaE results in optimal optimization outcomes, supported by both theoretical and empirical evidence.

Main paper: 
 introduction: 
 Practical problems in science and engineering often involve optimizing a black-box objective function that is expensive to evaluate, such as robotics (Tesch et al., 2013) and molecular design (Sanchez-Lengeling and Aspuru-Guzik, 2018) . How to achieve a near-optimal solution while minimizing function evaluations is thus a major challenge in black-box optimization (BBO). Prior works in BBO have largely focused on the online setting where a model can iteratively query the function during training (Turner et al., 2021; Zhang et al., 2021; Hebbal et al., 2019; Mockus, 1974) . Most existing algorithms belong to forward methods, including Bayesian optimization (BO) (Kushner, 1964; Mockus, 1974; Wu et al., 2023; Frazier, 2018) , bandit algorithms (Agrawal and Goyal, 2012; Karbasi et al., 2023) , and conditional sampling approaches (Brookes et al., 2019; Gruver et al., 2024; Stanton et al., 2022) . They build a surrogate model to approximate the black-box function and optimize sequentially.However, these approaches may face difficulties in scenarios where valid inputs represent a small subspace, such as valid protein sequences or molecular structures. Such optimization problems become exceptionally challenging, as the optimizer must navigate and avoid out-of-distribution and invalid inputs (Kumar and Levine, 2020) . Recently, a novel set of methods, termed inverse approaches, have been proposed to address this issue. These methods (Kumar and Levine, 2020; Krishnamoorthy et al., 2023; Kim et al., 2023; Fu and Levine, 2021) break the traditional paradigm by learning an inverse mapping from objective space back to the input (design) space. Leveraging the Submitted to Workshop on Bayesian Decision-making and Uncertainty, 38th Conference on Neural Information Processing Systems (BDU at NeurIPS 2024). Do not distribute.Figure 1 : Forward modeling vs inverse modeling for black-box optimization. (Top) Forward modeling approach using certain surrogate models (e.g., GPs) for forward modeling and acquisition functions (e.g., UCB, PI, and EI) to select x. (Bottom) Our inverse modeling approach using generative model (e.g., diffusion model) for inverse modeling and acquisition function (e.g., UaE) to select y.state-of-the-art generative models, such as diffusion models (Sohl-Dickstein et al., 2015; Song et al., 2020) , these approaches effectively capture data distributions in high-dimensional input space and facilitate optimization within the data manifold (Kong et al., 2024; Li et al., 2024) . They achieve high performance in offline optimization settings (Kumar and Levine, 2020; Lu et al., 2023; Wang et al., 2018) , assuming access to a fixed pre-collected dataset.Despite these advancements, the online setting of inverse modeling, particularly how to capture the uncertainty of the inverse model and design an acquisition function for data-efficient querying, remains an open question. In this paper, we propose Diff-BBO, an inverse approach for online black-box optimization. Our approach consists of a novel acquisition function design through the uncertainty quantification (UQ) of conditional diffusion model, which proposes the desired objective function values to strategically sample the design space and query the oracle function efficiently. We summarize our main contributions as follows:• We present Diff-BBO, an inverse modeling approach for efficient online black-box optimization (BBO) leveraging uncertainty of conditional diffusion models.• We design a novel acquisition function for BBO based on the uncertainty of conditional diffusion models. Theoretically, we prove that the balance between targeting higher objective values and minimizing epistemic uncertainty lead to optimal optimization outcomes.• We demonstrate that Diff-BBO achieves state-of-the-art performance with superior sample efficiency on Design-Bench and molecular discovery task in the online BBO setting. 
methodology: 
 Let f : X → R denote the unknown ground-truth black-box function that evaluates the quality of any data point x, with X ⊆ R d . Our goal is to find the optimal point x * that maximizes f , The function value y to condition on is proposed by an acquisition function, which quantifies the quality of the generated x. The objective of the above optimization becomes:x * ∈ argmax x∈X f (x).max y k ∈R K k=1 f (x k ), x k ∼ p θ (• | y k , D), θ ∈ Θ.(1) D) . By querying the oracle to evaluatex j , we obtain the best possible reconstructed value ϕ k for the current iteration, and append all queried data pairs {x j , f (x j )} N j=1 to the training dataset D. Figure 1 summarizes the difference between the prior forward BBO methods and our proposed inverse modeling approach.In this section, we analyze the uncertainty of Diff-BBO, decomposing its uncertainty into aleatoric and epistemic uncertainty. Then we propose an acquisition function called Uncertainty-aware Exploration (UaE) based on it. We prove that by achieving a balance between high objective values and low epistemic uncertainty, UaE provides a near-optimal solution to the online BBO problem.Uncertainty Decomposition. We resort to the tools of Bayesian inference to solve the optimization problem defined in Equation (1). Given an observed value y of a sample x, the objective of Bayesian inference is to estimate the predictive distribution:EQUATIONBy Equation ( 2), we recognize that the uncertainty arises from two sources: uncertainty in deciding parameter θ from its posterior p(θ|D) and uncertainty in generating sample x from a fixed diffusion model p θ (x | y) after θ is chosen. We further provide a decomposition in terms of the aleatoric uncertainty and its epistemic counterpart. parameter θ i , ∀i ∈ [M ].Combining the above gives a practical way to decompose and estimate the two types of uncertainty, whish is formally described in Proposition 1.Proposition 1 (Uncertainty Decomposition). At each iteration k ∈ [K], the overall uncertainty in inverse modeling can be split into aleatoric and epistemic components, measured empirically as:EQUATIONUncertainty-aware Exploration. At each iteration k ∈ [K] of Dif-BBO algorithm, the acquisition function proposes an optimal scalar value y * k as follows: y * k = argmax y α(y, D), which is used to generate x in the design space using conditional difussion model.Note that to design an effective acquisition function for inverse modeling, we need to achieve a balance between high objective values y and low epistemic uncertainty. On the one hand, it is advantageous to focus on the regions in X whose corresponding y is of high values. As function evaluations are expensive to perform, we prefer to generate samples x conditioned on higher y, and only query the oracle for such promising samples to solve the black-box optimization task. On the other hand, we employ the epistemic uncertainty to gauge the error in the trained diffusion model.Specifically, it helps reduce the approximation error between y * k and the reconstructed function valuemax j∈[N ] f (x j ), where f (•) is the black-box oracle, andx j ∼ p θ (•|y * k , D), ∀j ∈ [N ].We introduce the Uncertainty-aware Exploration (UaE) as our designed acquisition function: Performance Analyses of UaE. We prove in Theorem 1 that by adopting UaE for inverse modeling to guide the selection of generated samples for solving BBO problems, we can obtain a near-optimal solution for the optimization problem defined in Equation (1). Detailed discussions and proofs can be found in Appendix C, Appendix D, and Appendix E.EQUATIONTheorem 1. Let Y be the constructed candidate set at each iteration k ∈ [K] in Algorithm 1. By adopting UaE as the acquisition function to guide the sample generation process in conditional diffusion model, Diff-BBO (Algorithm 1) achieves a near-optimal solution for the online BBO problem defined in Equation (1): As a result, equipped with the novel design of UaE, Diff-BBO is a theoretically sound approach utilizing inverse modeling to effectievely solve the online BBO problem.max y k ∈R K k=1 f (x k ), x k ∼ p θ (• | y k , D), θ ∈ Θ ⇒ max y k ∈Y K k=1 α(y k , D). 
experiments: 
 To validate the efficacy of Diff-BBO, we conduct experiments on six real-world online black-box optimization tasks for both continuous and discrete optimization tasks.Dataset. We restructured 5 real-world tasks from Design-Bench including 3 continuous and 2 discrete tasks. In D'Kitty and Ant Morphology, the goal is to optimize for the morphology of robots. In Superconductor, the aim is to optimize superconducting material with a high critical temperature. TFBind8 and TFBind10 are discrete tasks to find a DNA sequence with maximum affinity to bind with a specified transcription factor. We also include a Molecular Discovery task to optimize compound's activity against a biological target with therapeutic value. For each task, we arrange the offline dataset from Krishnamoorthy et al. (2023) in ascending order based on objective values and select data from the 25th to the 50th percentile as the initial training dataset. We prioritize data with lower objective scores to better observe performance differences across each baseline. Each optimization iteration is allocated 100 queries to the oracle function (batch size N = 100), with a total of 16 iterations conducted. More details of the dataset are provided in Appendix F.1.Baselines. We compare Diff-BBO with 10 baselines, including Bayesian optimization (BO), trust region BO (TuRBO) (Eriksson et al., 2019) , local latent space Bayesian optimization (LOL-BO) (Maus et al., 2022) , likelihood-free BO (LFBO) (Song et al., 2022) , evolutionary algorithms (Brindle, 1980; Real et al., 2019) , conditioning by adaptive sampling (CbAS) (Brookes et al., 2019) , and random sampling. For BO approaches, we include Gaussian Processes (GP) with Monte Carlo (MC)-based batch expected improvement (EI), MC-based batch upper confidence bound (UCB) (Wilson et al., 2017) , and joint entropy search (JES (Hvarfner et al., 2022) as the acquisition functions.For LFBO, we use EI and probability of improvement (PI) as the acquisition functions.Results. Figure 2 illustrates the performance across six datasets for all baselines and our proposed algorithm. Notably, Diff-BBO consistently outperforms other baselines in both discrete and continuous settings. Specifically, in the Ant and Dkitty tasks, Diff-BBO demonstrates a significant lead over all baseline methods, starting from the very first iteration of the online optimization process. This remarkable performance can be attributed to Diff-BBO's diffusion model-based inverse modeling approach, which effectively learns the data manifold in the design space from the initial dataset, even when the initial dataset lacks data with high objective function values. 
conclusion: 
 In this paper, we introduced Diff-BBO, an inverse modeling approach for online black-box optimization that leverages the uncertainty of conditional diffusion models. By utilizing the novel acquisition function UaE, Diff-BBO strategically proposes objective function values to improve sample efficiency.We did extensive empirical evaluations to show the superior performance of Diff-BBO. Theoretically, we prove that using UaE leads to optimal optimization solutions. 
 
 Appendix: A Diff-BBO algorithm Algorithm 1: Diff-BBO Input: Initial dataset D = {x, y}, total number of iterations K, candidate feasible range C, oracle function f (•), batch size N 1 Initialization: Conditional diffusion model p θ (x|y) 2 for k = 1, 2, • • • K do 3 Train the conditional diffusion model with D 4 Construct a candidate set Y = {y : 0 ≤ y ≤ C} 5 y * k = argmax y∈Y α(y, D) 6 Generate {x j } N j=1 where x j ∼ p θ (x | y * k , D) 7 Query the oracle function f (•) with generated samples {x j } N j=1 8 D ← D ∪ {x j , f (x j )} N j=1 9 ϕ k ← max (f (x)) s.t. x ∈ D Output: Reconstructed {ϕ k } K k=1Diffusion Models (Sohl-Dickstein et al., 2015; Song et al., 2020) are probabilistic generative models that learn distributions through an iterative denoising process. These models consist of three components: a forward diffusion process that produces a series of noisy samples by adding Gaussian noise, a reverse process to reconstruct the original data samples from the noise, and a sampling procedure to generate new data samples from the learned distribution. Let the original sample be x 0 and t be the diffusion step. For conditional diffusion models, a conditional variable y is added to both the forward process as q (x t |x t-1 , y) and reverse process asp θ (x t-1 | x t , y) , ∀t ∈ [T ].The reverse process begins with the standard Gaussian distribution p(x T ) = N (0, I), and denoises x t to recover x 0 through the following Markov chain with reverse transitions:p θ (x 0:T |y) = p(x T ) T t=1 p θ (x t-1 | x t , y) , x T ∼ N (0, I), p θ (x t-1 | x t , y) = N (x t-1 ; µ θ (x t , t, y), Σ θ (x t , t, y)) .During training, Σ θ is empirically fixed, and µ θ is reparametrized by a trainable denoise function ϵ θ (x t , t, y), which is used to estimate the noise vector ϵ that was added to input x t , and is trained by minimizing a reweighted version of the evidence lower bound (ELBO):L dif = E x0∼q(x),y,ϵ∼N (0,I),t∼U (0,T ),xt∼q(xt|x0,y) w (t) ∥ϵ -ϵ θ (x t , t, y)∥ 2 2 .(5)Note that the loss in Equation ( 5) (Ho et al., 2020) for ϵ θ is denoising score matching for all time step t, which estimates the gradient of the log probability density of the noisy data (a.k.a.score function): ϵ θ (x t , t, y) ≈ -σ t ∇ x log p(x | y). We further denote the score function ass θ (x t , y, t) := -ϵ θ (x t , t, y) /σ t .Instead of learning a fixed deterministic θ from a deterministic neural network, we are interested in learning its Bayesian posterior to further understand and improve the model's performance as well as its reliability with uncertainty quantification. In Bayesian settings, we consider the model parameters θ ∈ Θ, where Θ is the parameter space, and maintain its posterior distribution p(θ|D), which is learned from training data D. By choosing θ from its posterior, essentially we sample a score function s θ (x t , y, t) from the probability distribution p(s θ | x t , y, t, D) = N (s θ (x t , y, t), Σ s θ (x t , y, t)), whose expected value is s θ (x t , y, t), and variance is a diagonal covariance matrix Σ s θ (x t , y, t).Specifically, we adopt classifier-free guidance as in (Ho and Salimans, 2022) where L cdif = E x0,y,ϵ,t,xt,λ w (t) ∥ϵ -ϵ θ (x t , t, (1 -λ)y + λ∅)∥x 0 ∼ q(x), ϵ ∼ N (0, I), t ∼ U(0, T ), x t ∼ q(x t | x 0 ), λ ∼ Bernoulli(p uncond ),Here, let us first consider the problem of how to capture the uncertainty for a fixed diffusion model.In fact, the uncertainty in generating x can be explicitly traced through the denoising process. More Var(x t-1 ) = 1 4 Var(x t ) + Var(s θ (x, y, t)) + 1 2 (E [x t • s θ (x t , y, t)] -E[x t ] • E[s θ (x t , y, t)]) + I, E(x t-1 ) = 1 2 E(x t ) + E(s θ (x, y, t)),where • is the Hadamard product, and I is the identity matrix. Similarly, in continuous-time process, the uncertainty can be captured as follows:EQUATIONNevertheless, performing exact Bayesian inference for uncertainty quantification when training diffusion models requires non-trivial efforts and can be computationally demanding. Hence, we introduce a practically-efficient uncertainty decomposition based on Equation (2).It can be shown that the conditional diffusion model can be represented by the Ornstein-Uhlenbeck (OU) process, which is a time-homogeneous continuous-time Markov process:EQUATION)where γ is the relaxation rate, σ is the strength of fluctuation, and w t is the standard Wiener process (a.k.a., Brownian motion). Both γ and σ are time-invariant. In particular, setting γ = 1 and σ = √ 2,we are able to establish that Denoising Diffusion Probabilistic Model (DDPM) is equivalent to OU process observed at discrete times. In the remaining text, we consider SDEs for general score-based diffusion models. The SDE of the forward process in conditional diffusion model can then be written as:EQUATIONwhere g(t) is a nondecreasing weighting function that controls the speed of diffusion in the forward process and g(t) > 0. For simplicity of analysis, we fix g(t) = 1 for all t ∈ [T ].The generation process of a conditional score-based diffusion model can be viewed as a particular discretization of the following reverse-time SDE:EQUATIONIn practice, the unknown ground truth conditional score ∇ xt log p(x t |y) needs to be estimated with score networks. Let such estimator denoted by s θ (x, y, t), then the conditional sample generation is to simulate the following backward SDE:EQUATIONIn Bayesian settings, we sample a score function s θ (x t , y, t) from the probability distribution p(s θ |x t , y, t, D) = N (s θ (x t , y, t), Σ θ (x t , y, t)) with expected value s θ (x t , y, t), and diagonal covariance Σ θ (x t , y, t).In this section, we quantify the uncertainty of a single conditional diffusion model in both discretetime and continuous-time reverse process for Theorem 2.We first proof the first statement of Theorem 2. We consider the Euler discretization of Equation ( 11), which leads to:EQUATION)We thus have,EQUATIONHere Cov (x t , s θ (x, y, t)) is the element-vise covariance between x t and s θ (x, y, t). Note that we only need to consider the correlation between x t and s θ (x, y, t) at the same time step. As a result, to estimate Cov (x t , s θ (x, y, t)), we have,EQUATION)where • is the Hadamard product and the third equality is by tower's rule. Substituting Equation ( 15) back to Equation (13) completes the proof of the first part of Theorem 2.We now proof the second statement of Theorem 2. To perform the uncertainty quantification for the continuous-time reverse process, we posit the following assumption.Assumption 1. For valid t ∈ [0, T ], the generating process x t in Equation ( 10) is integrable and has finite second-order moments.With Assumption 1, integrating Equation ( 10) with respect to t yields: x 0 = x T - T t=0 1 2 x t +which gives V 1 = T t=0 T s=0 1 4 Cov(x s , x t ) - 1 2 Cov(x s , s θ,t ) - 1 2 Cov(x t , s θ,s ) + Cov(s θ,t , s θ,s ) ds dt.When s ̸ = t, score functions s θ,t and s θ,s are independent, and similarly, x t and s θ,s are also independent. As a result, the above equation can be further simplified asV 1 = T t=0 T s=0 1 4 Cov(x s , x t ) - 1 2 Cov(x s , s θ,t ) ds dt - T t=0(Cov(x t , s θ,t ) + Cov(s θ,t , s θ,t )) dt.Combining all the above results together completes the proof of the second statement of Theorem 2.To quantify the quality of generated samples, we theoretically analyze the sub-optimality performance gap between y * k and reconstructed value at each iteration. In particular, Theorem 3 and Theorem 4 demonstrate that such sub-optimality gap can be effectively handled in inverse modeling, with proofs deferred to Appendix D.1. We first show that by using conditional diffusion model, the expected error of the sub-optimality performance gap is zero.Theorem 3. At each iteration k ∈ [K], define the sub-optimality performance gap asEQUATION)Assume that there exists some θ * ∼ p(θ|D) that produces a predictive distribution p θ * (• | D) such that it is able to generate a sample x * that perfectly reconstructs y * k . Suppose function f is L-Lipschitz and each sample is σ-subGaussian, it can be shown thatE [∆(p θ , y * k )] ≤ c 1 L √ dσ,where c 1 is some universal constant and the empirical estimator E [∆(p θ , y * k )] is unbiased.Theorem 3 suggests that in expectation, the reconstructed function value max j∈[N ] f (x j ) is able to accurately recover the provided conditional information y * k . Hence, in order to obtain a reasonable estimator for the optimization problem, the remaining concern goes to the variance of the gap defined in Equation ( 18), which is further evaluated in Theorem 4. EQUATIONwhere c 2 is some universal positive constant.Theorem 4 shows that the variance of the sub-optimality performance gap can be upper bounded by the epistemic uncertainty of diffusion model. Therefore, our proposed acquisition function achieves the balance between high objective value and low epistemic uncertainty.In this section, we study the behavior of the sub-optimality gap of our algorithm by proving Theorem 3 and Theorem 4. We first introduce the notation that is used throughout this section and the next section. Then we present the main lemmas along with their proofs. Finally, we combine the lemmas to prove our main results. EQUATION)For simplicity of analysis, we consider N = 1, and let the generated sample at the k-th iteration bex k in the remaining text. We remark that all proofs go through smoothly for general N with more nuanced notations, and do not affect the conclusions being drawn. To proceed with the proofs in this section, we first state the formal assumptions for the black-box function f (•) and sample x.Assumption 2. The scalar black-box function f is L-Lipschitz in x:|f (x ′ ) -f (x)| ≤ L∥x ′ -x∥, ∀x ′ , x ∈ R d . Assumption 3. Each generated sample x ∈ R d is σ-subGaussian. That is, there exists σ ∈ R such that for any v ∈ R d with ∥v∥ = 1, v T (x -E[x]) is σ-subGaussian, and its moment generating function is bounded by:E[exp λv T (x -E[x]) ] ≤ exp σ 2 λ 2 2 , ∀λ ∈ R, v ∈ S d-1 ,where S := {v ∈ R d : ∥v∥ = 1} is the (d -1) unit sphere.Before proceeding with the proofs of main theorems, we present our main lemmas.Lemma D.1. At each iteration k ∈ [K], under fixed parameters θ and θ * , forEQUATIONEQUATION)Proof of Lemma D.1. To bound E [∥x * -x k ∥], by triangle inequality,E x k ,x * [∥x * -x k ∥] = E [∥x * -E[x * ] + E[x k ] -x k + E[x * ] -E[x k ]∥] ≤ E [∥x * -E[x * ]∥] + E [∥x k -E[x k ]∥] + E [∥E[x * ] -E[x k ]∥] .Under assumption 3, by Lemma D.3, we have,E x k ,x * [∥x * -x k ∥] ≤ 8 √ dσ + ∥E[x * ] -E[x k ]∥ .Applying triangle inequality completes the step. In addition, it can be easily seen thatEQUATION)Proof of Lemma D.2. By definition of variance,EQUATION)Expanding the first term leads toEQUATIONwhere the last equality is due to the independece between x * and x k .Under Assumption 3 and by Lemma D.4, we haveE[∥x * ∥ 2 ] = E[∥x * -E[x * ] + E[x * ]∥ 2 ] = E[(x * -E[x * ]) T (x * -E[x * ])] + ∥E[x * ]∥ 2 = tr(E[(x * -E[x * ])(x * -E[x * ])] T ) + ∥E[x * ]∥ 2 ≤ Cdσ 2 + ∥E[x * ]∥ 2 .Here, the second equality holds as the cross terms vanish due to the fact thatE[x * -E[x * ]] = 0.Similarly,E[∥x k ∥ 2 ] ≤ Cdσ 2 + ∥E[x k ]∥ 2 .Substituting the above two results back to Equation ( 25),EQUATION)Substituting Equation ( 26) back to Equation ( 24) and applying Lemma D.1 leads toVar x k ,x * (∥x * -x k ∥) ≤ 2Cdσ 2 + ∥E[x k ] -E[x * ]∥ 2 -(8 √ dσ + ∥E[x * ] -E[x k ]∥) 2 ≤ c 3 dσ 2 .With the above results, we are ready to prove Theorem 3 and Theorem 4.Theorem 3. At each iteration k ∈ [K], define the sub-optimality performance gap asEQUATIONAssume that there exists some θ * ∼ p(θ|D) that produces a predictive distribution p θ * (• | D) such that it is able to generate a sample x * that perfectly reconstructs y * k . Suppose function f is L-Lipschitz and each sample is σ-subGaussian, it can be shown thatE [∆(p θ , y * k )] ≤ c 1 L √ dσ,where c 1 is some universal constant and the empirical estimatorE [∆(p θ , y * k )] is unbiased.Proof of Theorem 3. Recall that we consider the case where N = 1, and denote x k the generated sample in the k-th iteration, i.e. E [∆(p θ , y * k )] = E [|f (x * ) -f (x k )|] ≤ LE [∥x * -x k ∥] .By Lemma D.1, we have E [∆(p θ , y * k )] ≤ 8L √ dσ + E θ,θ * [∥E[x * ] -E[x k ]∥] .EQUATIONwhere c 2 is some universal positive constant.Proof of Theorem 4. At every iteration k ∈ [K], let the target function value on which the conditional diffusion model conditions be y * k . The statement needs to hold for each conditional diffusion model in the ensemble, and thus for simplicity of notation, the subscript i of θ i is dropped in the remaining proof. With the existence of θ * ∼ p(θ | D), we havey * k = f (x * ), where x * ∼ p θ * (•|y * k , D). Recall that f (x k ) is achieved by x k ∼ p θ (•|y * k , D), where θ ∼ p(θ | D), and N = 1.Thus, by Eve's law, the overall variance of ∆(p θ , y * k ) can be decomposed as:Var (∆(p θ , y * k )) = Var (|y * k -f (x k )|) = Var (|f (x * ) -f (x k )|) = E θ,θ * [Var x k ,x * (|f (x * ) -f (x k )| | θ, θ * )] T1 + Var θ,θ * (E x k ,x * [|f (x * ) -f (x k )| | θ, θ * ]) T2 .In particular, the first term T 1 corresponds to the aleatoric component and the second term T 2 corresponds to the episdemic component. We then proceed to bound the above two terms separately.Step 1: bound T 1 . Under Assumption 2,Var x k ,x * (|f (x * ) -f (x k )| | θ, θ * ) ≤ L 2 Var x k ,x * (∥x * -x k ∥ | | θ, θ * ).Under Assumption 3 and by Lemma D.2,EQUATION)Step 2: bound T 2 . Under Assumption 2,T 2 ≤ L 2 Var θ,θ * (E x k ,x * [∥x * -x k ∥ | | θ, θ * ]))By Lemma D.1,Var θ,θ * (E x k ,x * [|f (x * ) -f (x k )| | θ, θ * ]) ≤ Var θ,θ * E θ,θ * 8 √ dσ + ∥E x * [x * ] -E x k [x k ]∥ ≤ Var θ,θ * (∥E x * [x * ] -E x k [x k ]∥) .Then by property of variance, we haveVar θ,θ * (∥E x * [x * ] -E x k [x k ]∥) = E θ,θ * ∥E x * [x * ] -E x k [x k ]∥ 2 -E θ,θ * ∥E x * [x * ] -E x k [x k ]∥ 2 .From the proof of Lemma D.2, we haveE θ,θ * ∥E x * [x * |θ * ] -E x k [x k |θ]∥ 2 = E θ * [E x * [∥x * ∥ 2 |θ * ]] + E θ [E x k [∥x k ∥ 2 |θ]] -2E θ,θ * [E x k [(x k |θ)] T E x * [x * |θ * ]] = 2(E θ [E x k [∥x k ∥ 2 |θ]] -E θ,θ * [E x k [(x k |θ)] T E x * [x * |θ * ]])Combining the above results, we haveEQUATIONCombining Equation ( 27) and Equation ( 28) completes the proof:Var (∆(p θ , y * k )) ≤ c 3 L 2 dσ 2 + 2L 2 Var θ (E x [∥x k ∥]).Lemma D.3. Let x ∈ R d be a σ-subGaussian ramdom vector, thenEQUATIONLemma D.4. Let x ∈ R d be a σ-subGaussian ramdom vector, then its variance satisfies:EQUATION)where C is some positive constant.Proof of lemma D.4. By definition of sub-Gaussian vector, for any direction u ∈ R d with ∥u∥ = 1,E exp(λu T (x -E[x])) ≤ exp λ 2 σ 2 2 , ∀λ ∈ R.This implies that the second moment in any direction u satisfies:E u T ((x -E[x])(x -E[x]) T ) ≤ σ 2 .Therefore, the maximum eigenvalue of the covariance matrix is upper-bounded by Cσ 2 , where C is some positive constant. Var[x] = tr E (x -E[x])(x -E[x]) T ≤ Cdσ 2 .E [f (x k )] = E [E [f (x k )|θ]] = θ x k f (x k )p θ (x k |y * k , D)p(θ|D) dx k dθ = θ x k f (x k )p θ (x k |y * k , D) dx k p(θ|D) dθ.Note that both the true parameter θ * and the chosen parameter θ are drawn from the same posterior distribution p(θ | D), we haveθ x f (x)p θ (x|y * k , D) dx p(θ|D) dθ = θ * x f (x)p θ * (x|y * k , D) dx p(θ * |D) dθ * .As a result, we have E [f (x k )] = θ * x * f (x * )p θ * (x * |y * k , D) dx * p(θ * |D) dθ * = E [E [f (x * )|θ * ]] = E [f (x * )] .max y k ∈R K k=1 f (x k ), x k ∼ p θ (• | y k , D), θ ∈ Θ ⇒ max y k ∈Y K k=1 α(y k , D).Proof of Theorem 1. Following Theorem 4, we can express the function evaluation as follows,f (x k ) = y k -(y k -f (x k )), ∀k ∈ [K].The overall objective of the optimization problem defined in Equation ( 1) can then be further decomposed asmax y k ∈R K k=1 f (x k ), x k ∼ p θ (• | y k ), θ ∈ Θ ⇔ max y k ∈R K k=1 y k -(y k -f (x k )), x k ∼ p θ (• | y k ), θ ∈ Θ ⇒ max y k ∈R K k=1 y k -∆(p θ , y k ).By Theorem 4, which shows ∆(p θ , y * k ) can be effectively upper bounded the epidemic uncertainty, we therefore have maxy k ∈R K k=1 f (x k ), x k ∼ p θ (• | y k ), θ ∈ Θ ⇒ max y k ∈Y K k=1 y k -∆ episdemic (y k , D)Essentially, our chosen acquisition function allows Diff-BBO to maximize the lower bound of the original optimization problem.F.1 Dataset Details.DesignBench (Trabucco et al., 2022 ) is a benchmark for real-world black-box optimization tasks. For continuouse tasks, we use Superconductor, D'Kitty Morphology and Ant Morphology benchmarks. For discrete tasks, we utilize TFBind8 and TFBind10 benchmarks. We exclude Hopper due to the domain is known to be buggy, as explained in Appendix C in (Krishnamoorthy et al., 2023) .We also exclude NAS due to the significant computational resource requirement. Additionally, we exclude the ChEMBL task because the oracle model exhibits non-trivial discrepancies when queried with the same design.• Superconductor (materials optimization). This task involves searching for materials with high critical temperatures. The dataset comprises 17,014 vectors, each with 86 components that represent the number of atoms of each chemical element in the formula. The provided oracle function is a pre-trained random forest regression model.• D'Kitty Morphology (robot morphology optimization). This task focuses on optimizing the parameters of a D'Kitty robot, including the size, orientation, and location of the limbs, to make it suitable for a specific navigation task. The dataset consists of 10,004 entries with a parameter dimension of 56. It utilizes MuJoCO (Todorov et al., 2012) , a robot simulator, as the oracle function.• Ant Morphology (robot morphology optimization). Similar to D'Kitty, this task aims to optimize the parameters of a quadruped robot to maximize its speed. It includes 10,004 data points with a parameter dimension of 60. It also uses MuJoCO as the oracle function.• TFBind8 (DNA sequence optimization). This task seeks to identify the DNA sequence of length eight with the highest binding affinity to the transcription factor SIX6 REF R1. The design space comprises sequences of nucleotides represented as categorical variables. The dataset size is 32,898, with a dimension of 8. The ground truth is used as a direct oracle since the affinity for the entire design space is available.• TFBind10 (DNA sequence optimization). Similar to TFBind8, this task aims to find the DNA sequence of length ten that exhibits the highest binding affinity with transcription factor SIX6 REF R1. The design space consists of all possible nucleotide sequences. The dataset size is 10,000, with a dimension of 10. The ground truth is used as a direct oracle since the affinity for the entire design space is available.Molecular Discovery. A key problem in drug discovery is the optimization of a compound's activity against a biological target with therapeutic value. Similar to other papers (Eckmann et al., 2022; Jeon and Kim, 2020; Lee et al., 2023; Noh et al., 2022) , we attempt to optimize the score from AutoDock4 (Morris et al., 2009) , which is a physics-based estimator of binding affinity. The oracle is a feed-forward model as a surrogate to AutoDock4. The surrogate model is trained until convergence on 10,000 compounds randomly sampled from the latent space (using N (0, 1)) and their computed objective values with AutoDock4. We construct our continuous design space by fixing a random protein embedding and randomly sampling 10,000 molecular embedding of dimension 32.For each task, we arrange the offline dataset from Krishnamoorthy et al. (2023) in ascending order based on objective values and select data from the 25th to the 50th percentile as the initial training dataset. We prioritize data with lower objective scores to better observe performance differences across each baseline. The overview of all the task statistics is provided in Table 1 . We train our model on NVIDIA A100 GPU and report the average performance over 3 random runs along with standard deviation for each task. For discrete tasks, we follow the procedure in Krishnamoorthy et al. (2023) where we convert the d-dimensional vector to a d × c one hot vector regarding c classes. We then approximate logits by interpolating between a uniform distribution and the one hot distribution using a mixing factor of 0.6. We jointly train a conditional and unconditional model with the same model by randomly set the conditioning value to 0 with dropout probability of 0.15.For each task, we fix the learning rate at 0.001 with batch size of 256. We use 5 ensemble models to estimate the uncertainty for our acquisition function. We set hidden dimensions to 1024 and gamma to 2. We use 10% of the available data at each iteration as validation set during training.In this section, we conduct ablation studies to investigate the impact of our designed acquisition function, UaE. We compare Diff-BBO with the fixed condition approach. Instead of using UaE to dynamically determine which y to condition on, the fixed condition approach always generates new samples conditioned on w • ϕ k (Line 9 of Algorithm 1) with a fixed weight w. As shown in Figure 4 , Diff-BBO consistently outperforms the fixed condition approach. This demonstrates that our acquisition function is effective in identifying the optimal y for conditioning.Furthermore, we evaluate the effect of batch size, aka the number of queries per iteration on Diff-BBO on the Superconductor task. As shown in Figure 5 , we compare the objective function score over number of function evaluations. We can see the performance of our approach remains similar when the batch size becomes small, suggesting remarkable robustness across different batch sizes. Hence, Diff-BBO is a highly-scalable inverse modeling approach that can efficiently leverage parallelism to handle larger computational loads without compromising performance.Optimization techniques can address various real-world problems, including drug and material design. Our method enhances sample-efficient online black-box optimization, potentially accelerating solutions in these areas. However, caution is needed to prevent misuse, such as optimizing drugs to enhance harmful side effects.,(6) 


Decision: Scores for this work are borderline. The actual text of the reviews is significantly more positive then the scores, praising the work for exploring a novel way to use generative models in this setting. In general it seeks the reviewers feel the work is incomplete: one asks for a major revision of the work. However, it is clear that such a revision would probably move the paper from workshop-paper to conference-paper level in terms of comprehensiveness. I therefore conclude the work is sufficiently far along in its present form to warrant acceptance at the workshop.

Reviews: review: title: title: Review for Diff-BBO: Diffusion-Based Inverse Modeling for Black-Box Optimization
main_review: main_review: Summary
The study presents Diff-BBO, a novel diffusion-based inverse modeling approach to solve black-box optimization (BBO) problems online. It introduces the Uncertainty-aware Exploration (UaE) acquisition function, which leverages uncertainty in diffusion models to propose objective function values, resulting in sample-efficient optimization. The method is validated through theoretical analyses and empirical evaluations, showing superior performance over baseline methods in various continuous and discrete optimization tasks.

Strengths
1.	Introduces a new inverse modeling technique leveraging diffusion models, which contrasts with traditional forward approaches, providing a fresh perspective in the BBO domain.
The proposed UaE acquisition function strategically balances exploration and exploitation, optimizing sample efficiency in an online setting.
2.	Demonstrates state-of-the-art performance across multiple benchmarks, consistently outperforming baselines in both discrete and continuous tasks.

Weaknesses
1.	The performance of the Diff-BBO algorithm heavily depends on the quality of the initial training dataset. If the dataset is too limited or skewed, it could hinder the optimization process.
2.	While the UaE function is theoretically proven to balance objective values and uncertainty, the proofs could benefit from a clearer discussion of limitations, assumptions, or failure cases in real-world BBO problems.

Recommendation
This paper demonstrates strong potential in advancing the field of black-box optimization through diffusion-based inverse modeling. Despite some concerns regarding dataset dependency, model limitations, and computational demands, its innovative approach and promising results suggest it should be considered for major revision. Improvements to the theoretical exposition and additional empirical evaluations could further strengthen the work's contribution to the field.
title: title: This paper presents Diff-BBO, a diffusion-based inverse modeling approach for black-box optimization (BBO). While the idea of applying diffusion models in BBO is interesting, the paper suffers from significant clarity issues, making it difficult to follow. The theoretical contributions, such as uncertainty-aware exploration (UaE), are not well-explained, and the empirical validation is weak, with limited benchmarks and marginal improvements over existing methods. Additionally, the paper does not address the practical scalability of the approach, reducing its significance in real-world applications. Overall, the contribution is promising but requires substantial improvement in presentation and empirical justification.
main_review: main_review: Quality

The paper is well-structured and presents a novel approach to Black-Box Optimization (BBO) using diffusion-based inverse modeling. The methodology and theoretical contributions are sound, with solid backing from empirical and theoretical analyses. The clarity of the paper is slightly hindered by a dense mathematical presentation, but it is sufficient for an audience familiar with the field of machine learning, especially in the domain of generative models and optimization.

Clarity

The paper lacks clear explanations and guidance for the reader. The heavy reliance on mathematical formulations without providing intuitive insights makes it difficult to understand the core contributions and their significance. Important sections, such as the design of the uncertainty-aware exploration (UaE) acquisition function, are not sufficiently explained, making it challenging for the reader to grasp how this method improves upon existing BBO techniques. More visual aids or simplified examples would help significantly in conveying the core ideas.

Originality

The use of diffusion models for inverse modeling in BBO is an interesting idea, but it is not sufficiently differentiated from other generative models already used in optimization tasks. The paper does not provide a strong case for why diffusion models are superior to other state-of-the-art methods like Gaussian processes or Bayesian optimization techniques. Additionally, the novelty of the uncertainty-aware exploration (UaE) function is underdeveloped and lacks sufficient comparison to existing methods that balance exploration and exploitation in optimization.

Significance

The practical impact of the proposed Diff-BBO method is questionable. While some benchmarks are presented, the results are not comprehensive, and the performance improvements over baselines are marginal in some cases. Furthermore, the paper lacks real-world application examples or discussions of how this method could be practically implemented in large-scale or high-dimensional optimization problems, which limits its significance in advancing the field of BBO.

Conclusion

(1) The idea of applying diffusion models in inverse modeling for BBO has potential if more thoroughly developed and explained.

(2)Some theoretical contributions, such as uncertainty decomposition, are mathematically sound.

(3) The paper presents a potentially interesting approach, but it falls short in terms of clarity, originality, and empirical significance. Substantial revisions are needed, particularly in providing better explanations, stronger empirical comparisons, and addressing the method's practical scalability.