Pretrained Optimization Model for Zero-Shot Black Box Optimization

weakness 1

Thank you very much for your valuable suggestions. We think your suggestion can really help us enhance the readability of the paper. We have made the following changes to Section 3: 1) First, we briefly introduced the overall model architecture of POM and gave the overall model structure diagram; 2) Further, we introduced the core components of POM in detail. 3) Finally, we introduced the details of POM training and testing.

I hope our changes will be recognized by you!

weakness 2

In the paper, we have made a visual analysis of why POM achieves such excellent performance (see section 4.4). We found that both LMM and LCM can adaptively adjust their own optimization strategies to achieve a good balance between exploration and utilization. Specifically, in the LMM module, we found the following phenomenon (lines 284-289):

“ 1) Generally, superior individuals receive higher weights during LMM, showcasing POM's ability to balance exploration and exploitation as the population converges. 2) Across diverse function problems, POM dynamically generates optimization strategies, highlighting its adaptability and contributing to robust generalization. 3) Disadvantaged individuals exhibit a more uniform weight distribution, potentially aiding in their escape from local optima and enhancing algorithm convergence.”

In the LCM module, we found the following phenomenon (see lines 291-299):

“LCM displays the capacity to adaptively generate diverse strategies for individuals across different ranks in the population, revealing distinct patterns among tasks and rankings. Notably, top-ranking individuals within the top 20, such as those ranked 1st, 5th, and 18th, exhibit a flexible crossover strategy. The dynamic adjustment of crossover probability with population evolution aids in preserving dominant genes and facilitating escape from local optima. Conversely, lower-ranking individuals show an increasing overall probability of crossover, promoting exploration of disadvantaged individuals and enhancing the algorithm's exploration capability. LCM proficiently generates adaptive crossover strategies across tasks, individuals, and convergence stages, significantly boosting both convergence and exploration capabilities.”

POM has obtained strong optimization and generalization capabilities through pre-training, and has a very strong optimization efficiency. The performance of POM on all problems far exceeds the baselines of other manually designed optimization strategies (DE, ES, LSHADE, CMAES) and the baselines that obtain optimization capabilities through pre-training (LGA, LES), which proves the effectiveness and rationality of POM.

Question 1

The Bipedal Walker task is a very difficult robot control task with very sparse reward signals. This task is very challenging. We can find that LES almost directly failed on this task, while DE, ES, LGA and LSHADE all showed premature convergence. These poor-performing algorithms all exhibit a common characteristic: small variance. Both POM and CMAES, which perform best on this task, exhibit significantly higher variance than other algorithms, which implies that stronger exploration capabilities are required to solve this task. For example, when CMA-ES encounters an evolutionary failure, it will increase the standard deviation of the search distribution and explore better points from a larger space; POM will adaptively adjust the optimization strategy. Among them, the mask module enhances the randomness of POM and avoids the LMM module's over-reliance on outstanding individuals in the population, thus improving the exploration ability of POM.

We did observe in the experiment that there are a large number of failed evolutions in the population evolution process. It may be that after many consecutive generations of attempts, a new and better individual will suddenly be found. This results in a strong randomness in the convergence process, so the convergence curves of CMA-ES and POM appear to have relatively large variances.

limitations

Thank you very much for your comments! We have conducted a very detailed analysis of POM in the paper. We also pointed out the advantages and limitations of POM that we observed from the experiments. We have added a summary of limitations as follows:

"limitations

1. Model size: In the experiment, we found that the relationship between the model size and the performance of POM is not a strict linear relationship. Although the larger the model, the more difficult it is to train, there is still no very quantitative design criterion between model size, training data volume and training difficulty.
2. Time performance: We introduced an operation similar to the attention mechanism, whose time complexity is $O(n^2)$, which makes POM require a lot of time cost when processing large-scale populations. How to reduce and improve the time efficiency of POM is also worthy of further study."

We hope that our responses have adequately addressed the concerns you previously raised. Your further insights would be greatly appreciated, as they are instrumental in enhancing the quality of our work. We understand that you are busy, and we truly value the time and effort you put into this process. Thank you in advance for your continued support.

weakness 1

We do not claim that the current version of POM is the best design, but it does show excellent performance in experiments. We also do not emphasize that POM must be under the scheme of mutate and then crossover. We just design LMM and LCM modules for solution generation according to the needs of POM, and ensure that POM can be pre-trained end-to-end through gradient.

weakness 2

The problems you mentioned just prove the rationality of the POM module design.

1. mask

The reason for introducing mask is explained in detail in lines 121-126. Its function is to limit the information exchange within the population, prevent the population from quickly converging to the optimal individual, resulting in loss of diversity. This design is similar to the dropout operation of deep neural networks. Without the dropout operation, the neural network will easily fall into the local optimum and overfit on the training set.

It is worth noting that the role of mask is to make LCM and LMM work better. mask is like a catalyst, while LCM and LMM can be likened to reactants. We cannot say that the catalyst itself is more important than the reactants.

2. NOTTRAIN and NO LMM

NOTRAIN performs better than NO LMM, which means LMM is a very core component. If LMM is lost, the trained model performance is not as good as NOTRAIN.

weakness 3

The experimental results of BBOB (d=100 ,optimal solutions disturbed), Bipedal Walker and Enduro proved the excellent performance of POM. These experimental results have been able to verify the optimization and generalization capabilities of POM. We further show the experimental results of BBOB(d=500, disturbed).

We hope our reply will be recognized by you.

weakness 4

POM does not overfit the training set, and experimental results show that POM exhibits generalization capabilities far beyond its training distribution.

weakness 5

Thank you for your valuable comments. We have added these references in the Related Work section, which makes our related work more complete （see Section 2, LLM for Optimization）.

“

LLaMoCo [38] and EoH [39] use LLM to generate code to solve optimization problems, but the performance of LLaMoCo depends on carefully designed instructions and prompts, and EoH has expensive evaluation costs.

”

Question 1

We think your suggestion is very correct and reasonable. In fact, in all BBOB-related experiments, we performed corresponding projections or rotations on the objective function. We only removed the deviation from the optimal solution in the main experimental part.

Question 2

The implementation of these baseline methods is described in detail in Appendix section D, and their parameter settings are described in detail in Appendix section E.

Question 3

They were not trained on the same training set. We did not need to train LES and LGA, as they claim to be trained models that can be used out of the box. Second, the training frameworks of LES and LGA are not open source, so we could not train them. Third, the training task sets of LES and LGA contain many BBOB functions, which is beneficial to them. Even so, their performance is not as good as POM.

Q1

We deeply apologize for the oversight in the configuration of our experimental code, which led to an error where the standard deviations were identical in the experimental results provided during the rebuttal period. We have rerun the experiment and obtained the correct mean values (and standard deviations), as shown in the table below. We are pleased to report that the performance of the POM method remains significantly superior to the best baselines, which is consistent with our previous conclusions. We are very grateful for the careful review by the reviewers.

Q2

We did not utilize the default projections and rotations provided in the original problem set because we aimed to test the model's performance on a broader range of scenarios on the BBOB benchmark. Consequently, we strictly adhered to the standard BBOB procedure to generate a series of BBOB function parameters, including projections and rotations.

We've carefully reviewed your feedback, addressed all queries, added the refs, and made revisions as per your suggestions. Your further review and acceptance of the updated manuscript would be highly valued.

Weaknesses 1

We have included references to [1-3] in the related work section of the POM due to their significant contributions.

"TNPs [40], ExPT [41] and LICO78 [ 42] use transformer to solve BBO problems and have achieved good results. TNPs requires contextual information of the target problem, and neither ExPT nor LICO can be directly used to solve tasks with different dimensions from the training task."

Howerver, we respectfully disagree with your viewpoint for the following reasons:

In [1], it is mentioned: "the number of evaluation points $N$ and the number of context points $m$ are generated from the same uniform distribution as in training." And there are three experimental tasks in [1]. When solving these tasks, [1] is retrained separately. These might imply that [1] may not be suitable for addressing Zero-shot Optimization problems.

In Section 2.1 of [2], it is mentioned that “during the adaptation phase, one can use the pretrained model to optimize any objective function $f$ in the same domain $X \subseteq \mathbb{R}^d$ .” In section 4.3 of [3], it is mentioned that “after training, a single LICO model can be used for optimizing various objective functions within the domain $X \subseteq \mathbb{R}^d$ .” This could suggest that references [2-3] may not be directly applicable to our particular context.

POM overcomes these limitations.

At the same time, we found these related papers, which also gave us a lot of inspiration.

• Probing the Decision Boundaries of In-context Learning in Large Language Models.
• ClimaX: A foundation model for weather and climate.
• Temporal predictive coding for model-based planning in latent space.

Weaknesses 2

Appendix A provides an overview of the background knowledge related to population-based optimization. Owing to constraints on space, we have chosen to include this information in the appendix rather than the main text. Section 3 meticulously outlines the specifics of POM, thereby ensuring that the reproduction of POM is feasible without a priori knowledge of population-based optimization techniques.

Weaknesses 3

Sec. 3.2 details POM's structure and mechanism for reproducibility. Eq. (6) and (10) present specialized model designs, not standard multi-head attention or feed-forward layers, including weights, activations, and normalization.

Weaknesses 4

POM does not have the conflict you claim. The usage of POM is similar to CMA-ES. It can directly optimize the target task without any metadata. POM learns general optimization strategies instead of fitting a specific optimization task. It only needs to input the fitness of the population and some features within the population to adaptively generate optimization strategies.

Weaknesses 5

We introduced the concepts of Zero-shot Optimization and Few-shot Optimization in section 3.1 (L87-L90).

The experiment in Section 4.2 verified the performance of POM in the Zero-shot Optimization scenario (see Fig. 2, 3 and the corresponding appendix for the results). In this section, we directly used the trained POM to solve the target problem.

In Section 4.3 Fine-tuning Test, we further verified the performance of POM in the Few-shot Optimization scenario. Here, we fine-tune POM using a small number of simulated functions of the target task. The experimental results are shown in Fig. 6.

The trained POM can be directly used to handle new target tasks, which is described in detail in Algorithm 2 (line 167).

Weaknesses 6

This is the advantage of POM. The baselines include two algorithms (LES and LGA) pre-trained by Meta-BBO. Although they have also been pre-trained, their performance are far inferior to POM. POM can obtain superior performance through pre-training, while baselines cannot.

Question 1

The concept of Zero-shot Optimization introduced in section 3.1 is as follows:

“Definition 1 Zero-shot Optimization. An optimizer is applied directly to solve $f$ without any tuning.”

The references [1-3] mentioned in Q1 cannot achieve zero-shot optimization. For details, see the reply to Q1.

Question 2

The details of these designs are described in detail in section 3.2.

LMM: The role of LMM is to generate a set of candidate solutions $\mathbf{V}^t$ based on the population $\mathbf{X}^t$. Therefore, the input of LMM is based on fitness information, that is, $\mathbf{H}^t$ (see lines 107-118 for details). The input information of LMM does not include the solution $\mathbf{x}$, because $\mathbf{x}$ will have different dimensions and follow different distributions under different tasks. If the input information includes $\mathbf{x}$, POM will not be able to generalize to different task dimensions.

LCM: The input of LCM needs to take into account the fitness information $[\hat{f}_i^t,\hat{r}^t_i]$ of $\mathbf{x}^t_i$. Intuitively, if $\mathbf{x}^t_i$ has a low fitness and a poor ranking in the population, then its genes are likely to be eliminated and should not enter the offspring. At the same time, LCM should take into account the cosine similarity between $\mathbf{x}^t_i$ and its candidate solutions $\mathbf{v}^t_i$. Intuitively, if the similarity between $\mathbf{x}^t_i$ and its candidate solution $\mathbf{v}^t_i$ is very low, selecting more genes of the candidate solution $\mathbf{v}^t_i$ into the offspring individuals helps encourage the exploration of the model.

We hope that our responses have adequately addressed the concerns you previously raised. Your further insights would be greatly appreciated, as they are instrumental in enhancing the quality of our work. We understand that you are busy, and we truly value the time and effort you put into this process. Thank you in advance for your continued support.

Q4: Can the authors explain why POM does not have the conflicting issue I mentioned in the original review...

Conflicts between optimization objectives do not necessarily lead to conflicts in optimization strategies. POM focuses on learning the mapping from the ranking information of individuals within a population to the search strategies, rather than adopting a fixed optimization strategy to suit all tasks.

Specifically, the LMM module adaptively generates the strategy matrix $\mathbf{S}^t$ using the population's ranking information ($\hat{r}^t_i$) and the information representing their relative advantages $\hat{f}_i^t$ (normalized from $f(\mathbf{x}_i^t)$, representing individual $i$. Note that we can convert all problems to minimization problems by adding a negative sign).

The LCM module uses the population's ranking information ($\hat{r}^t_i$), the relative advantage information of individuals within the population $\hat{f}_i^t$, and the similarity information between parent and offspring $sim_i^t$ to adaptively generate the crossover strategy.

This means that POM is not fitting a specific problem $f$, nor is it searching for an optimal $\mathbf{x}^* \in \mathbb{R}^d$ in its solution space. Instead, it searches for optimal POM strategy parameters $\mathbf{\theta}^*$ in the strategy space through these training tasks. Therefore, even if there are conflicting objective functions, it does not affect the performance of POM. Furthermore, the training algorithm proposed by POM, MetaGBT, integrates gradient information from a set of tasks, making the training process more stable and easier.

Let's simulate the situation you mentioned. Suppose there is a function $f(\mathbf{x})=\sum_i{x_i}$, with task one being $f_1=\mathop{\arg\max}\limits_{\mathbf{x}}f(\mathbf{x})$ and task two being $f_2=\mathop{\arg\min}\limits_{\mathbf{x}}f(\mathbf{x})$. Clearly, these two tasks are in direct conflict.

Assuming that at the current moment, the populations for both tasks are the same, they are in the following state:

Finally, after performing selection between $\mathbf{X}$ and $\mathbf{U}$, the resulting population is:

The average fitness for Task 1 improved from 13.25 to 17.8175, demonstrating an enhancement in the performance of Task 1. Conversely, the average fitness for the population of Task 2 decreased from 13.25 to 8.9025, which also indicates an improvement in the performance of Task 2.

This shows that even with conflicting objective functions, Their optimization strategies do not necessarily conflict. This demonstrates that POM learns a universal optimization strategy, and there is no conflict as you claimed.

First and foremost, I would like to express my sincere gratitude for your comments and suggestions regarding our manuscript submitted to NeurIPS 2024. We have diligently revised our paper in accordance with your feedback.

We earnestly hope that you will reconsider our revised manuscript and appreciate the improvements made. If you find that our efforts and the results now meet the standards of the conference, we kindly request that you consider increasing the score of our paper. We highly value your assessment and look forward to your final approval.

Thank you once again for your valuable time and expertise.

Q1: I still believe the writing can be significantly improved for...

Thank you for your valuable suggestions, which have helped us improve the expression of our paper. To better introduce the background knowledge and clarify the motivation behind the design of POM, we have followed your advice and added the following content in Section 3 before detailing the mechanism of POM (see Section 3.2 for details).

" 3.2 Classic Population Optimization Algorithm In this section, we use Differential Evolution (DE) as an example to review classic evolutionary algorithms. DE [20,43] is a prominent family within evolutionary algorithms (EAs), known for its advantageous properties such as rapid convergence and robust performance [44,45]. The optimization strategy of DE primarily involves mutation and crossover operations.

The classic DE/rand/1 crossover operator is illustrated in Eq. (1) (additional examples are listed in Appendix A.2). Each mutation strategy can be viewed as a specific instance of Eq. (2); Further details are provided in Appendix A.2. Additionally, we represent the mutation strategy in a matrix form, as shown in Eq. (3). The matrix $\mathbf{S}$ evolves with the generation index t, indicating that the mutation strategy adapts across different generations. Consequently, we propose a module to enhance the performance of the mutation operation, which leverages the information from the population of the tth generation to generate $\mathbf{S}^t$. This serves as the motivation for our design of the LMM.

$\mathbf{v}\_i^t = \mathbf{x}\_{r1}^t+F\cdot(\mathbf{x}\_{r2}^t-\mathbf{x}\_{r3}^t)$     (1)

In the crossover phase at step t, DE uses a fixed crossover probability $cr_i^t$ ∈ [0,1] for each individual $\mathbf{x}_i^t$ in the population, as shown in Eq. (9). The crossover strategy for the entire population can then be expressed as a vector $\mathbf{cr}^t = (cr_1^t, cr_2^t, ..., cr_N^t)$. Our goal is to design a module that adaptively generates $\mathbf{cr}^t$ using the information from the population. This approach allows for the automatic design of the crossover strategy by controlling the parameter cr. This serves as the motivation for our design of LCM.

Q2: Moreover, the methodology section is a bit too verbal and mathy, and some equations are unnecessary. I do not see a difference between Eq (6) and (10) and the standard feed forward and attention layers.

In this section, we present detailed formulas to ensure the reproducibility of POM, which are also crucial for elucidating the mechanism of POM. We will then discuss in detail the differences between these formulas and the standard self-attention and feed-forward layers.

The difference between Eq (6) and standard self-attention

A. Self-Attention

1. Input Transformation:

   $\mathbf{Q}= \mathbf{X}\mathbf{W}^Q, \quad \mathbf{K} = \mathbf{X}\mathbf{W}^K, \quad \mathbf{V} = \mathbf{X}\mathbf{W}^V$

2. Attention:

   $\text{Self-Attention}(\mathbf{Q}, \mathbf{K}, \mathbf{V}) = \text{softmax}\left(\frac{\mathbf{Q}\mathbf{K}^T}{\sqrt{d_k}}\right)\mathbf{V}$

3. Output:

   $\text{Output} = \text{Self-Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})$

B. Eq. (6)

1. Input Transformation:

2. Attention:

   $\text{LMM-Attention}(\mathbf{Q}, \mathbf{K}, \mathbf{X})= \text{mask}\left(\text{softmax}\left( \text{Tanh}\left(\frac{\mathbf{Q}\mathbf{K}^T}{\sqrt{d_k}}\right)\right),r_{\text{mask}}\right)\mathbf{X}$

3. Output:

   $\text{Output} = \text{LMM-Attention}(\mathbf{Q}, \mathbf{K}, \mathbf{X})$

The differences between Eq (6) and standard self-attention are evident as follows:

1. No Calculation of V: In Eq (6), we do not compute $\mathbf{V}$; instead, we use $\mathbf{X}$ in the attention calculation. This approach is crucial for achieving good performance in our optimization task, whereas standard self-attention struggles to adapt to our problem scenario.

2. Different Processing of Input Information: We introduce the Tanh activation function and a bias term, which helps enhance the performance of POM. This is a significant departure from the standard self-attention mechanism.

3. Attention Matrix Mapping and Masking: For the computed attention matrix, we apply the Tanh function to map it to the range $[-1,1]$. Additionally, we use a random mask operation, setting elements to zero with a probability of $r_{mask}$.

In summary, there are several key differences between our approach and standard self-attention. These differences are crucial for the performance of POM, and it is essential to detail them thoroughly. This is not a shortcoming but rather a necessary distinction.

2 Eq (10) and feed forward layer

A. feed forward $\text{Output} = \mathbf{W}_2 \cdot \text{ReLU}(\mathbf{W}_1 \cdot \mathbf{X} + \mathbf{b}_1) + \mathbf{b}_2$

B. Eq (10) $\mathbf{cr}^t = \text{sigmoid}\left(\text{layernorm}\left(\tanh\left(\mathbf{Z}^t \times \mathbf{W_{c1}} + \mathbf{b_{c1}}\right) | \mathbf{\tau}\right) \times \mathbf{W_{c2}} + \mathbf{b_{c2}}\right)$

It is worth noting that, although the two are very similar in form, Eq (10) provides a detailed implementation scheme. Any modifications to Eq (10), such as replacing the sigmoid function with ReLU, result in a significant decline in POM's performance. This is because we rely on the sigmoid function to map the output to the range $[0,1]$, representing probability values. Changes to other activation functions or hyperparameters in Eq (10) also lead to performance degradation.

Q3: Regarding the baselines, TNP, ExPT, and LICO can all be used for zero-shot optimization because they do not require further fine-tuning after pretraining. However, they do require the new objective to lie in the same dimension/domain as the pretraining tasks.

It is clear that TNP, ExPT, and LICO require retraining in different dimensional scenarios when faced with tasks of varying dimensions. This does not align with the definition of Zero-shot Optimization, which is "an optimizer that can be directly applied to solve a continuous black-box optimization problem $f$ without any tuning."

"Definition 1 Zero-shot Optimization : Zero-shot optimization refers to an optimizer that is applied directly to solve a continuous black-box optimization problem $f$ without any tuning. This means that the optimizer does not require any contextual information about $f$ and can be directly used to handle problems of any dimensionality."