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

Authors: Manh Cuong Dao, The Hung Tran, Phi Le Nguyen, Thao Nguyen Truong, Trong Nghia Hoang
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords: Diffusion Model, Probabilistic Method

Abstract:
This paper studies the black-box optimization task which aims to find the maxima of a black-box function using only a static set of its observed input-output data. This is often achieved via learning and optimizing a surrogate function using such offline dataset. Alternatively, it can also be framed as an inverse modeling task which maps a desired performance to potential input candidates that achieve it. Both approaches are limited by the limited amount of offline data. To mitigate this limitation, we introduce a new perspective which casts offline optimization as a diffusion process mapping between an implicit distribution of low-value inputs (i.e., offline data) and a superior distribution of high-value inputs (i.e., solution candidates). Such diffusion process can be learned using low- and high-value inputs sampled from synthetic functions that resemble the target function. These synthetic functions are constructed as the mean posterior of multiple Gaussian processes fitted with different parameterizations on the offline data, alleviating the data bottleneck. Experimental results demonstrate that our approach consistently outperforms previous methods, establishing a new state-of-the-art performance.

Decision: reject
Reviewer scores: 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1730574088052

thread_type:
official_review

<thread_object>
creator: reviewer_3wmn

<content>
summary:
This paper presents a new perspective on offline optimization, framing the optimization task as a distributional translation from low-value points to high-value points. It uses diffusion models to learn this translation. The paper shows the effectiveness of this new perspective through theoretical analysis and experimental validation.

strengths:
1. The new perspective of viewing the optimization problem as a diffusion translation problem is quite novel and intuitive.

2. The method proposed in this paper is direct and clear: It uses synthetic data from fitted gaussian process for data augmentation and then employs a diffusion model to learn the distributional translation from low-value to high-value regions.

3. The presentation of this paper is clear and well-structured.

4. The experiments are comprehensive.

weaknesses:
The method needs to fit multiple Gaussian processes to generate synthetic data, which might have high time complexity in high-dimensional cases. Besides, the reverse diffusion process also requires multiple denoising steps, which also increases the time complexity.

questions:
NA
</content>
</thread_object>

</thread>
<thread>
creation date:
1730619720901

thread_type:
official_review

<thread_object>
creator: reviewer_7uew

<content>
summary:
This paper considers the offline optimization problem, where offline (x, y) pairs are given, and the goal is to return samples x with better value. The paper proposes a distribution shifting approach by first learning the underlying function via a mean estimate of the Gaussian process under difference kernel functions and creating two sets of samples $X^+$ and $X^-$ by taking gradient ascent and gradient descent based on the estimated function starting from the offline samples. Then a diffusion model is learned via translating the data from $X^-$ to $X^+$ via assumed conditional Gaussian distribution. Experiments are conducted on the variance of benchmarks and the proposed method is compared to be comparable/superior to some offline linear optimization baselines.

strengths:
The problem of offline optimization is important and has many potentials. 

The experiments are presented clearly and the proposed method indeed has improvements compared to baselines.

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

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. 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. 

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. 

Overall, it is a work based on a wrong assumption/mathematics though has engineering improvement. 

[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.

questions:
In the paper, notation $\omega$ is used in multiple places. Is it a random variable indicating the randomness of the underlying function and offline data? In Eq (12) and follows, is it $\omega^*$ or $\omega$?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730833164058

thread_type:
official_review

<thread_object>
creator: reviewer_c7rs

<content>
summary:
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. 

The paper seeks to learn surrogate parameterized functions which learn the data distribution. Using these surrogates, the data is augmented, and this augmented data can then be used to train a model. The issue with such augmentation is that both the (x,y) pairs must be learnt, and predicting the x may lead to OOD generations. This is usually solved through inverse mappings, or search. This paper proposes ideas from Brownian bridge diffusion, which was previously proposed in computer vision to extend to tasks in the Design Bench.

strengths:
- The use of diffusion in design tasks is quite novel. 
- 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.

weaknesses:
- Why use the brownian bridge diffusion process? How do other diffusion processes perform?
- Section 3.1 what is the stochastic translation operator? why use terms before defining them?
- 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? What is the reason for the specific form in equation 13? Please rewrite thsi section with what you are attempting in this section. While reading this section, it is extremely unclear what the mathematics is leading towards, and hence why a stochastic translation is required.
- There is no algorithm section translating the mathematics of Section 3 into the experiments of Section 4. I do not see what was the optimization implemented, or how it was obtained.
- The paper does not report running times of the algorithms. Given diffusion can be significantly costlier it is worth reporting the wall-clock time.
- The paper reports max score in Table 1, but without external evaluation, it is not clear that the algorithm may know what is best. Hence this is not the expected performance. Can  you also show the mean score?

questions:
- Why do you set the value of zeta to t/T? and delta_t to zeta_t(1-zeta_t)?

### Suggestions:

- Could you consider revising your abstract? The goal of the paper was not immediately clear.
- Please consider a rewrite of section 3.1. Start with what the optimization function is. Then follow through with the derivations on how it was obtained. Please mention how this is used in an algorithm.
- Happy to raise my score given some changes to the manuscript.

### Typos
- Line 233: "as follows"
</content>
</thread_object>

</thread>
<thread>
creation date:
1733213438830

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Comprehensive Resolution of All Post-Rebuttal Concerns.

comment:
Dear Area Chair and Reviewers,

We would like to express our sincere gratitude to the Area Chair for coordinating the review process and to the reviewers for their detailed reviews.

1. We are particularly thankful to Reviewer **3WMn** for the acceptance score.

2. We are thankful that Reviewer **c7rs** gave us excellent and good ratings for soundness and contributions, respectively. We believe the reviewer’s overall rating of 5 is mainly regarding the presentation, which has been thoroughly fixed following the detailed feedback from the reviewer. We still hope the reviewer would be able to confirm if our latest revision (uploaded to OpenReview) is sufficient before the author-reviewer discussion closes. We have put in a lot of effort to revise the paper and your feedback on the revision would mean a lot to us.

3. We also appreciate Reviewer **7UEw**’s critical review of our paper. Given the discussion, we understand that the single remaining concern of the reviewer is that our assumption in Eq. (13) is self-contradicting due to the misunderstanding that the derivative of a GP-distributed function might not be distributed by a GP, which would invalidate the Gaussian assumption in Eq. (13). We clarified that this is indeed a misunderstand as the derivative of a GP-distributed function is also distributed by a GP, which is explicitly stated in the first sentence of Section 9.4 of the Gaussian process for Machine Learning (GPML) textbook by Carl Edward Rasmussen and Chris Williams.

    We have also provided a mathematical prove that there is no contradiction in Eq. (13) using this fact — please see our second to last message to Reviewer **7UEw**.

4. We also emphasize that our assumption is equivalent to assuming that the mapping between the oracle’s low- and high-value input distributions follows a Brownian bridge diffusion process. This is a single assumption and if it were indeed self-contradictory, it would imply a fundamental flaw in the concept of the Brownian bridge diffusion process which is implausible.
     
     In addition, we hope Reviewer **7UEw** will consider give credit to our significant empirical results. We believe this result is solid and the use of Brownian bridge diffusion in offline optimization is truly the first of its kind. Usually, a model based on conflicting assumption will not perform well across multiple datasets. This is certainly not the case here.

---

## Summary of Responses

1. **Clarity Improvements:**
   - Revised the abstract and introduction to better articulate the paper’s objectives, with highlighted changes for transparency.
   - Improved Section 3.1 to enhance the clarity of our approach. *(c7rs)*

2. **Performance Comparison:**
   - Reported wall-clock times for all baselines, demonstrating that L2HD outperforms several baselines, including CMA-ES, MINS, and Tri-mentoring. *(c7rs, 3WMn)*

3. **Addressing Novelty and Assumption Concerns:**
   - Clarified the novelty of our contributions and established mathematically that there is no contradiction in our assumption. *(7UEw)*

---

Overall, based on the above, we strongly believe that our rebuttal has effectively addressed all concerns raised.

We sincerely thank the Area Chair and reviewers for their time and effort in evaluating our paper. We hope the final assessment reflects the strengths and contributions of our work.

Best regards,

The Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a method for offline black box optimization, where it can be challenging to learn a surrogate function that generalizes to out-of-distribution designs. The authors propose using a Brownian bridge diffusion model to transform "low-valued" data (i.e., input/output pairs where the output is suboptimal) into "high-valued" data (input/output pairs where the output is optimal).

The approach proposed by this paper is novel and demonstrates positive results. The primary issue with this paper is in the presentation. The goal of the paper is not immediately clear from the abstract and introduction; the methods section was initially confusing, and one reviewer had trouble determining if the method was valid. While the authors made an effort to improve the presentation during the revision period, this paper would benefit from another round of reviewing. Given that most reviewers cited presentation issues in their review, I hope that the authors put in additional effort towards improving the clarity of their manuscript, as focusing on the writing will ultimately lead to a publication with a higher impact.