FROM LOW TO HIGH-VALUE DESIGNS: OFFLINE OPTIMIZATION VIA GENERALIZED DIFFUSION

Thank you very much for your positive review and acceptance rating. We address your question regarding the time-complexity of our method in high-dimensional cases below:

The method needs to fit multiple Gaussian processes to generate synthetic data, which might have high time complexity in high-dimensional cases.

We note that fitting a GP requires (1) evaluating Eq. (5) and (2) differentiating the RHS of Eq. (5) with respect to each kernel parameter. Given n training data points in a $d$-dimensional space, the computational cost of (1) is $O(n^3 + dn^2)$ while that of (2) is $O(|$#kernel-parameter$|n^3) = O(n^3)$ since in our case, #kernel-parameter = 2 -- see lines 138-139.

Hence, the cost of fitting a GP is linear in $d$ which will allow our proposed method (L2HD) to scale well to high-dimensional cases. To see this, we have detailed below the running time of our algorithm and other baselines across our experimented datasets.

The reported running time shows that even with the GP fitting overhead, L2HD still runs faster than several baselines such as CMA-ES, MINS, and Tri-mentoring.

Furthermore, to avoid dealing with high-dimensional data, we can also adopt a similar approach used in BBDM which uses VQGAN to embed data into a lower-dimensional latent space first.

Besides, the reverse diffusion process also requires multiple denoising steps, which also increases the time complexity.

We agree that the reverse diffusion process might require thousands of denoising steps, increasing inference time complexity. But again, the complexity only scales linearly in the number of denoising steps, and similar to BBDM, we find that using 200 denoising steps is sufficient to guarantee good performance across all tasks. The corresponding processing time -- as reported in the above table -- therefore remains within range in comparison to those of the baselines.

We hope that our answer has addressed your concern. If so, we hope you would consider increasing the overall rating of our work. Otherwise, please let us know if you have any follow-up questions for us.

Take another example of Eq (3), the optimal solution x^* is a function of the unknown function g, and thus g(x^*) conditioned on the offline data is not Gaussian. It is the maximum of several Gaussian since x∗ is also a random variable.

We believe there is a misunderstanding that $x_*$ in Eq. (3) refers to the maxima of $g(x)$. It does not.

We ask the reviewer to please kindly read the sentence before Eq. (3) again which only says that $x_*$ is an unseen input.

We suspect the reviewer’s confusion is caused because we previously use $x_*$ to denote the maxima of $g(x)$ in Eq. (2) but we did not mean for $x_*$ to be particularly the maximizer in the context of Eq. (3).

We apologize for the overloaded notation and changed it to $x_\tau$ in the latest manuscript.

The two sections 2.1 and 2.2 are separate background reviews.

We assert that the use of the Gaussian process in this context is NOT to predict the value of the maximum output of $g(.)$. Instead, it is used to draw synthetic functions that are within a statistical neighborhood of the oracle function. As those sampled functions are within the statistical neighborhood of $g(.)$, their low- and high-value input regimes can be used to (approximately) represent those of the oracle, which provides training data for the BBDM.

Note that using the low- and high-value points from within the offline dataset is not helpful in this case because the offline dataset is drawn from the bottom 40th (or 50th) percentile of the full oracle dataset -- see Design-bench [6]. This is why we need to use GP. A similar GP approach to generate synthetic data for pre-training offline optimizer was previously investigated in [7].

[6] Trabucco, Brandon, Xinyang Geng, Aviral Kumar, and Sergey Levine. "Design-bench: Benchmarks for data-driven offline model-based optimization." In International Conference on Machine Learning, pp. 21658-21676. PMLR, 2022.

[7] Nguyen, Tung, Sudhanshu Agrawal, and Aditya Grover. "Expt: Synthetic pre-training for few-shot experimental design." Advances in Neural Information Processing Systems 36 (2023): 45856-45869.

The diffusion approach generates data outside of the distribution of the samples (outside of the distribution coverage) thus leading to critical generalization issues. This issue is not sufficiently addressed.

The specific data we used to train the BBDM guarantees that it will not generate data outside the distribution of the samples. To see this, note that the training data of the BBDM constitutes the low- and high-value inputs of synthetic functions which are sampled from a statistical neighborhood of the oracle. This statistical neighborhood is defined via fitting a GP posterior using the offline oracle data.

The sets of low- and high-value inputs from those sampled functions therefore represent sufficiently well the low- and high-value regimes of the oracle. A BBDM learned with such data will then help map from low-value inputs to high-value inputs of the oracle.

This can be verified by observing the performance of our method in the experiments. Had the BBDM produced inputs outside the high-value regime, it would have recommended low-value candidates, harming the overall performance. As our reported performance is superior to the baselines over multiple runs across various datasets, we can ascertain that our customized BBDM has not generated OOD data.

In other words, the OOD issue mentioned by the reviewer has indeed been addressed in our context via the sampling of synthetic data from GP posteriors fitted on offline oracle data. This approach is well-grounded, as it has been shown in [8] that a GP with an RBF kernel is a universal approximator, capable of modeling a wide range of functions. Furthermore, prior work [9] demonstrates the feasibility of generating pseudo-labels for unlabeled designs using a vast set of GP priors, achieving impressive results. In our case, we take this further by using GP posteriors, which are specifically fitted to the offline dataset, ensuring the synthesized functions are closely aligned with the target function on the observed data.

[8] Micchelli, Charles A., Yuesheng Xu, and Haizhang Zhang. "Universal Kernels." Journal of Machine Learning Research 7, no. 12 (2006).

[9] Nguyen, Tung, Sudhanshu Agrawal, and Aditya Grover. "Expt: Synthetic pretraining for few-shot experimental design." Advances in Neural Information Processing Systems 36 (2023): 45856-45869.

Thank you for your detailed review. We would like to your questions as below:

The originality of viewing the offline optimization as a distribution shift is not novel. See [a].

We would like to emphasize that (1) viewing offline optimization from the lens of a distribution shift between the offline and high-value input regimes is a well-known perspective (see [1], [2], [3], and [4]) that predates both our work and [a]; and (2) certainly, this does not represent the novelty of our work.

We also do not think any recent work in offline optimization -- including [a] -- is claiming to contribute to this well-known fact. Instead, the true novelty in existing offline optimization papers lies in their technical approaches to model and handling such distribution shifts, either empirically or theoretically.

Our contribution is that we pointed out that under the mild assumption, there exists a BBDM that maps between the offline and high-value input regimes, thus casting offline optimization as learning a BBDM.

On the other hand, the key contribution of [a] is learning a point-wise re-weighting function that transforms the offline input distribution into a distribution over the high-value input regime.

A quick comparison with [a] on TFBIND8 also shows that our approach has an empirical advantage over [a] and DDOM [5] which [a] is based on.

However, [a] presents a fantastic theoretical analysis.

Given the above, the approaches in our work and [a] are different and constitute orthogonal contributions. As such, while the solution perspective in [a] is novel and interesting, it does not cancel or subsume our contribution, which is equally novel.

We hope the reviewer would agree with us on this point.

On the assumption front, both our work and [a] adopt different assumptions that are technically useful but not necessarily universally true (more to this later).

[a] Zhang, Q., Zhou, R., Shen, Y. and Liu, T., 2024. From Function to Distribution Modeling: A PAC-Generative Approach to Offline Optimization. arXiv preprint arXiv:2401.02019.

[1] Trabucco, Brandon, Aviral Kumar, Xinyang Geng, and Sergey Levine. "Conservative objective models for effective offline model-based optimization." In International Conference on Machine Learning, pp. 10358-10368. PMLR, 2021.

[2] Trabucco, Brandon, Xinyang Geng, Aviral Kumar, and Sergey Levine. "Design-bench: Benchmarks for data-driven offline model-based optimization." In International Conference on Machine Learning, pp. 21658-21676. PMLR, 2022.

[3] Qi, Han, Yi Su, Aviral Kumar, and Sergey Levine. "Data-driven offline decision-making via invariant representation learning." Advances in Neural Information Processing Systems 35 (2022): 13226-13237.

[4] Yu, Sihyun, Sungsoo Ahn, Le Song, and Jinwoo Shin. "Roma: Robust model adaptation for offline model-based optimization." Advances in Neural Information Processing Systems 34 (2021): 4619-4631.

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

The derivations are not correct. The proposed method is not theoretically justified, merely a theoretically motivated heuristic. For example, the Assumption of Eq (13) cannot be justified given Eq (12), thus giving no evidence for Eq (14) as combining both equations. Thus the overall learning procedure lacks of justifications.

We respectfully disagree with the statement that our derivations are not correct. It is correct under the assumption stated in Eq. (13) which stipulates that:

(1) the distribution over the (true) optimal input can be reparameterized as a linear transformation of an isotropic Gaussian distribution; and

(2) such transformation is in turn characterized via a (learnable) linear function of the output of a T-step gradient ascent using the surrogate gradient.

Under this assumption, we show that there exists a BBDM that maps between the offline (low-value) and high-value input distributions. This is not an unreasonable assumption compared to that of [a] which stipulates that there is (1) diffusion model mapping from isotropic Gaussian to high-value input distribution, which is then (2) pointwise transformed into the offline distribution via a (learnable) re-weighting function.

I hope the reviewer will agree with us on these points.

Thank you very much for your positive feedback and detailed suggestions. We have addressed your concerns as follows:

This is a high-potential paper which could be much better written. I suggest a full review of the paper for readability. For example, the second line of the abstract is 4 lines long. The goal of the paper is not clear from reading the introduction.

To improve the clarity of the abstract and introduction, we have revised both sections with highlighted changes to clearly articulate the paper's objectives. For these updates, please refer to the latest version of our manuscript, which has been recently uploaded.

The results are strong. But note that the best of 128 samples is reported in Table 1. The algorithm itself may not have access to "best score". So while the algorithm reaches good results in best case, median or avg may have to be considered.

We would like to point out that in addition to the best case (100th percentile) result in Table 1, we have also provided results for the median (50th percentile) and 80th percentile in Tables 8 and 9 in Appendix B, which are referred to in lines 363-364 in the main text. These tables demonstrate that our method, L2HD, achieved state-of-the-art performance not only in the 100th percentile but also in the 80th and 50th percentiles with the highest rank. Furthermore, we have included additional violin plots in Appendix B.3 and Figure 2, illustrating that L2HD has a score distribution skewed towards higher-value regions compared to the other baselines.

Why use the brownian bridge diffusion process? How do other diffusion processes perform?

Our work has reformulated offline optimization as a distributional translation task, where the goal is to map a low-value distribution to a high-value distribution. This allows us to draw from powerful methods in the image-to-image translation community, and BBDM [1] is one such approach. In fact, we have shown in Section 3.1 that under a certain modeling assumption and parameterization, there exists a BBDM that maps between those distributions. Hence, BBDM is our natural choice. However, as far as a practical solution goes, any diffusion model capable of translating between two (implicit) distributions (i.e., those that are represented implicitly with a set of samples) could also be applied to our framework. Exploring potential uses of other diffusion processes is an interesting direction to extend our current work but it is orthogonal to the current scope. We will consider this in a potential follow-up of our work. Thank you very much for your suggestion.

[1] Li, Bo, Kaitao Xue, Bin Liu, and Yu-Kun Lai. "Bbdm: Image-to-image translation with brownian bridge diffusion models." In Proceedings of the IEEE/CVF conference on computer vision and pattern Recognition, pp. 1952-1961. 2023.

Section 3.1 what is the stochastic translation operator? why use terms before defining them?

The parameterized scaling and stochastic translation operator, $(\zeta_t, \delta_t)$, refers to the operations in Eq. (13) (Eq. (15) in our latest manuscript), where we scale the gradient sum by $\zeta_t$ and add Gaussian noise (translation) scaled by $\delta_t$​. To improve clarity and avoid confusion, we have revised the terms in our revised manuscript (from Eq. (13) to Eq. (15)).

The paper has spent a lot of space on Section 3.1 which comes without explanation of what the goal is. For example what is g in this setting? Are these the equivalents of the noise estimates in DDPM?

We would like to clarify that the goal of Section 3.1 is stated in lines 208-214 which is at the beginning of Section 3.1. We believe these lines provide sufficient context for the detailed content in the section, outlining the objectives and rationale behind the methodology discussed.

As stated in lines 101-105 in the Problem Definition section, $g(x)$ represents the black-box function, and $g(x; \omega)$ denotes the surrogate model trained to approximate this black-box function $g(x)$. Hence, they are not the equivalents of the noise estimates in DDPM.

Dear Reviewer c7rs,

To assist with your final assessment of our paper, we provide the following summary of our work:

Motivation:

• Black-box optimization fundamentally seeks a sequence of iterates $x_t$ that map from a low-value design ($x_T$) to a high-value design ($x_0$). A naive approach uses a surrogate-based gradient ascent (as shown in Eq. (12)), relying solely on offline data (e.g., oracle data from low-value regimes). However, this approach often hallucinates mapping targets instead of defining them properly.

Idea:

• To address this limitation, we assume that under the GP-based stochasticity of the oracle, the distribution of high-value designs can be derived from a transformation of isotropic Gaussian noise (Eq. (13)). This assumption imposes a constraint on the sequence of iterates, defining how the mapping target influences the dynamics (Eq. (15)).

Instead of learning Eq. (12) for offline optimization, we propose learning a transition dynamic that satisfies Eq. (15), which characterizes a family of Brownian bridge diffusion processes.

Technical Challenges:

• Learning the transition dynamics to generate iterates satisfying Eq. (15) is challenging, as it requires observing high-value samples from the oracle, which are unavailable.

However, we empirically find that high-value samples from functions similar to the oracle can also be used as effective surrogates to represent the oracle's high-value regime. Sampling such functions is feasible using the GP posterior distribution of the oracle.

Results:

• Our approach significantly outperforms the state-of-the-art methods, demonstrating its efficacy in offline black-box optimization.

—

Further Insights:

• Overall, our approach features a new connection between offline optimization and the Brownian bridge diffusion process which has not been previously explored. We believe this is a very new perspective that would be useful for future research development in offline optimization.