SYMBOL: Generating Flexible Black-Box Optimizers through Symbolic Equation Learning

We appreciate the reviewer for the valuable feedback and the strong support for our paper. Your recognition of the paper's clarity, the novelty of SYMBOL, its state-of-the-art performance, and its good interpretability is highly encouraging. We hope that the following response, as well as the newly added results, will clear the remaining concerns.

---

[Teacher selection] We thank the reviewer for the insightful comment. Please refer to our response [Teacher selection in SYMBOL] in the “general response” above.

---

[Training distribution selection] We acknowledge the importance of task distribution $\mathbb{D}$ in facilitating generalization during the meta-learning stage of SYMBOL. To address the concern regarding the adequacy of using only 10 synthetic functions for meta-learning a universally effective policy, we have refined the description in “Training distribution $\mathbb{D}$” part in Section 4, and included additional details in Appendix B.4 of our revised paper. Our explanation is threefold:

1. The 10 synthetic functions we have selected encompass a broad spectrum of representative landscape features and optimisation challenges, as detailed in the newly added Table 7 in Appendix B.4. These features include uni/multi-modality, separability, smooth yet narrow ridges, and (a)symmetry, etc. In Appendix B.4, the added Figure 9 now includes visualizations of the fitness landscapes of these 10 functions. Through this diverse range and by incorporating fitness landscape analysis-based state representation (refer to Section 3.1 and Appendix A.1), SYMBOL learns not merely to solve specific tasks, but to adapt its update patterns to varying landscape features. This adaptability underpins its impressive generalization capabilities, as demonstrated in our experimental results.
2. We have also augmented the training distribution $\mathbb{D}$ by incorporating shifted and rotated versions of these functions, as outlined at the beginning of Section 4. This methodological augmentation enriches $\mathbb{D}$ with a multitude of diverse landscapes, thereby expanding its scope and ensuring robust generalization.
3. We would also like to note that these selected 10 functions have a longstanding history in the literature for evaluating the performance of BBO optimizers. Their proven ability to present diverse optimization properties makes them ideal for training SYMBOL, ensuring its efficacy in generalizing to a wide array of unseen, realistic tasks.

---

[Is training via RL the computational bottleneck?] We thank the reviewer for the insightful question. We agree that a detailed examination of the computational costs of SYMBOL’s different sub-routines during training is essential. In SYMBOL, there are three main sub-routines:

1. Update Rule Generation: This involves computing the contextual state representation, feeding the state into the SEG (State Encoding Generator) for generating pre-order traversals, and decoding these traversals into the corresponding update rules.
2. Lower-Level Optimization: After generating the update rule, SYMBOL applies this rule to update the candidate population and evaluates the objective values of the new generation.
3. Meta-Level PPO Training: Concurrently with the lower-level optimization, the collected trajectories are utilized to update the parameters in the SEG via reinforcement learning.

To quantify the computational demands, we measured the wall time for each of these sub-routines during training. The table below presents the consumed time and corresponding proportions for each subroutine, along with the total time, using SYMBOL-S as an example:

As the data reveals, lower-level optimization emerges as the primary computational bottleneck in SYMBOL. It's important to clarify that high computational costs are intrinsic to BBO (Black-Box Optimization) optimization in the MetaBBO domain. This is evident in the baseline methods we compare against in our paper (like LDE, DE-DDQN, Meta-ES, etc.).

To mitigate these costs, common practice involves parallel processing. Specifically, we simultaneously sample a batch of task instances and collect trajectories in parallel, significantly accelerating both the lower-level optimization and meta-level training processes. For more details on our approach to parallel processing, please refer to Appendix B.2.

We hope the above clarifications help, and we are happy to engage in further discussions. Thanks for taking your time and making contributions to our paper!

We appreciate the reviewer for the positive and valuable feedback. Thank you for acknowledging that our paper is easy to follow and that our SYMBOL is not only flexible, novel, and interpretable, but also showcases promising performance and impressive generalization abilities for future usage. We hope that the following response, as well as the newly added results, will clear the remaining concerns.

---

[Is the symbol set relevant to the teacher algorithm?] We would like to clarify that the current basis symbols set is essential to cover numerous update rules (e.g., those in DEs, PSOs, GAs, etc.), and we have opted for a simple yet effective symbol set that is sufficient to generate update rules covering various searching behaviors and exhibiting different extents of exploration and exploitation abilities. Experimental results in Section 4.3, Figure 5 consistently show SYMBOL achieves new state-of-the-art performance. Meanwhile, we note that our SYMBOL can work well even if the basis symbol set is not perfectly relevant to the teacher algorithm. For example, our SYMBOL-S could outperform the teacher CMA-ES even if our symbol set could not represent the covariance update processes in CMA-ES. Please refer to our response [Design of the symbol set] in the “general response” above for more discussions.

---

[Whether the potential of SYMBOL is largely limited by the performance of MadDE] Thanks for raising this concern. According to our experiments, SYMBOL-G and SYMBOL-S both outperform MadDE, clearly demonstrating the potential of SYMBOL to exceed the employed teacher optimizer. However, SYMBOL-E, designed to independently discover novel optimizers without reliance on any particular teacher optimizer, underperforms MadDE. We acknowledge that navigating the complex landscapes of BBO tasks presents significant challenges for SYMBOL-E when learning solely from scratch, which deserves further exploration in the future. So far, SYMBOL-E's strength lies in scenarios where selecting an appropriate teacher optimizer is challenging.

---

[Can the exploration reward help the model learn a much better update rule?] Yes, it helps. Following the suggestions by the reviewer, we address this concern from the following two perspective.

i) When the teacher optimizer is relatively bad: In Section 4.3, we explored the use of a relatively less effective teacher, vanilla DE, within SYMBOL-S. Despite the limitations of the teacher optimizer, SYMBOL-S consistently outperformed it, as evidenced by the performance curves in Figure 5 (Section 4.3) and Figure 8 (Appendix C.1). This indicates the robustness of SYMBOL-S in surpassing teacher capabilities.

ii) When the optimization task is challenging for the teacher optimizer: In the context of more challenging tasks such as HPO-B and Protein-docking (Table 1, Meta Generalization part), SYMBOL exhibits impressive performance even when the teacher optimizer (MadDE) struggles. Both SYMBOL-E and SYMBOL-G show only limited improvements when used independently, yet SYMBOL-S significantly outperforms MadDE, underscoring that SYMBOL is not constrained by its teacher's performance. The synergy between exploration and imitation rewards in SYMBOL not only demonstrates robust generalization across diverse tasks but also ensures rapid convergence.

We appreciate the reviewer for the positive and valuable feedback. Thank you for acknowledging that our paper is well-written and that our proposed SYMBOL is novel and promising. We hope that the following response will clear the remaining concerns.

---

[Strategy in choosing a teacher optimizer] We thank the reviewer for the insightful comment. Please refer to our response [Teacher selection in SYMBOL] in the “general response” above.

---

[Training cost comparison between SYMBOL and baselines] We would like to clarify that the training time of SYMBOL and other MetaBBO baselines have been reported in Section 4.1, Table 1. For your convenience, we list the training time in the table below.

We hope the above clarifications help, and we are happy to engage in further discussions. Thanks for taking your time and making contributions to our paper!

We appreciate the reviewer for the positive and valuable feedback. Thank you for acknowledging that our SYMBOL is technically novel, reasonable, and could outperform other BBO and MetaBBO methods. We hope that the following response, as well as the newly added results, will clear the remaining concerns.

---

[Clarify the advantages and key differences of our SYMBOL] We thank the reviewer for the suggestion and apologize for any confusion. To the best of our knowledge, SYMBOL represents the initial endeavour to promote the automated discovery of BBO update rules through symbolic equation learning. Compared to existing MetaBBO techniques, our SYMBOL is more flexible (can generate novel update rules beyond hand-crafted rules dynamically depending on the search situation), more generalizable (owing to the leveraged fitness landscape analysis as robust state features), and more interpretable (the generated update rules are in closed form). Meanwhile, our SYMBOL archives new state-of-the-art performance among other BBO and recently developed MetaBBO methods. Concerning other MetaBBO works, two primary branches exist — one for auto-configuration and the other for candidate solution proposals, which are discussed as follows:

1. MetaBBO for Auto-Configuration: This branch involves a neural policy at the meta level that dictates configurations for the hand-crafted update rules in the lower-level optimizer, as seen in Table 1 with baselines like LDE, MELBA, and Meta-ES. Alternatively, some other works leverage the meta-level agent to select a proper hand-crafted update rule from a predetermined pool of rules, as done by the DEDDQN in Table 1. However, these methods may inherit potential limitations from the hand-crafted rules within the optimizer itself. SYMBOL minimizes dependence on hand-crafted rules and flexibly generates closed-form update rules upon a symbol set, enhancing the exploration capability of efficient update rules and consequently boosting the potential performance of the generated optimizers.
2. MetaBBO for Candidate Solution Proposal: This branch employs RNNs to auto-regressively propose the next generation of candidates end-to-end without explicit update rules. Specifically, the input is the position of the current candidate(s), and the output is the next candidate(s). However, these models may easily get overfitted, and their efficiency may be limited to low-dimensional BBOs only, raising generalization concerns. In contrast, SYMBOL incorporates fitness landscape analysis into the state representation, aiming to construct a generalizable model that can produce flexible update rules for various problems, ensuring a more robust optimization. Additionally, while existing works for candidate proposals are entirely "black-box" with limited interpretability, SYMBOL's generated rules are step-by-step transparent, allowing for easier analysis and understanding of the learned processes.

Correspondingly, we have refined our discussions in the second paragraph of the Introduction section and the second paragraph of the Related Works section.

---

[Representation ability of update rules] We thank the reviewer for the insightful comment. Please refer to our response [Design of the symbol set] in the “general response” above.

---

[Q1: Mention traditional MetaBBO works] We thank the reviewer for the suggestion. We have enriched the Related Work section. As introduced in [i], these traditional methods also adhere to the bi-level optimization paradigm. But in their paradigm, both the meta-level and lower-level components are implemented using traditional black-box optimizers. In addition, they generate a single strategy for the entire lower-level optimization process. Our SYMBOL differs in that a) it employs a learning-based RL-Agent as the meta-level method; b) it generates flexible update rules in the lower level; and c) it dynamically adjusts its strategy throughout the lower-level optimization process, adapting to changing conditions and ensuring greater flexibility.

References:

[1] Jonathan Ho, Stefano Ermon, "Generative Adversarial Imitation Learning", arXiv: 1606.03476

[Design of the symbol set] Reviewers #h4Ki and #ZLbt raised concerns regarding the representation ability of our symbol set. We value this insightful feedback and agree with the reviewers that the current basis symbol set could cover most essential update rules (e.g., those in DEs, PSOs, GAs, etc.) but not all complex ones (e.g., the covariance update processes in CMA-ES). However, we would like to clarify the following points:

1. The primary motivation of SYMBOL is to dynamically generate BBO update rules from scratch in a data-driven fashion, reducing dependence on conventional, intricate update rules. With the incorporation of teacher guidance for accelerated convergence in our SYMBOL-G and SYMBOL-S, our aim is not to directly replicate the specific complex update rules of teacher optimizers. Instead, we seek to emulate their search behaviors. This allows SYMBOL to discover unique, simpler, yet highly effective optimizers that can compete with, but not necessarily replicate, sophisticated optimizers like CMA-ES. As we stated in Section 3.1, our symbol set could cover numerous update rules (e.g., those in DEs, PSOs, GAs, etc.), but more importantly, could span beyond the existing hand-crafted space, offering flexibility to explore novel and effective update rules. Our meta-test and meta-generalization results demonstrate that effective update rules can be meta-learned from this symbol set, and new state-of-the-art optimization performance is achieved against the baselines.
2. Despite the current symbol set's inability to generate CMA-ES-type update rules, our study demonstrates that this simple symbol set is sufficient to generate update rules covering various searching behaviors and exhibiting different extents of exploration and exploitation abilities. Experimental results in Section 4.3, Figure 5 consistently show SYMBOL outperforming many teacher optimizers, including CMA-ES.
3. We acknowledge the challenge of designing an ideal symbol set. There is a balance between having enough symbols to represent complex equations and maintaining good equation construction efficiency. Our ablation studies, detailed in Table 9 and Appendix C.2, delve into the impact of altering the symbol set on SYMBOL's learning efficacy. As the first research effort on generative MetaBBO through symbolic equations, we have opted for a simple yet effective symbol set, and leave the exploration of more powerful symbol sets as important future works. Correspondingly, we have carefully refined our claims regarding the symbol set in Section 3.1 and outlined potential future works regarding this in the Conclusion section.

---

[Teacher selection in SYMBOL] Reviewers #VT1T and #hEPw raised questions regarding the teacher selection in our SYMBOL-G and SYMBOL-S. We would like to offer some clarifications:

1. SYMBOL is teacher-agnostic. Our model architecture, as detailed in Section 3.1, uses a contextual state representation that requires no information about the teacher optimizer. This design makes SYMBOL a generic, plug-and-play framework compatible with various teacher optimizers. Our experiments (Section 4.3 and Appendix C.1) demonstrate SYMBOL's effectiveness across different teacher optimizers (including DE, PSO, CMA-ES), where the performance consistently outperforms each teacher.
2. In most cases, selecting a teacher for SYMBOL is not hard.

• As we did in SYMBOL, one may select a proper optimizer that has been reported to have excellent performance in existing BBO benchmarks (e.g., COCO, IEEE CEC Competition Series). Note that such BBO benchmarks are proposed to examine an optimizer’s potential for complex, realistic tasks. In this paper, MadDE is chosen as the teacher optimizer since it shows superior optimization performance in our preliminary numerical tests.
• One may also seek proper teacher optimizers from the state-of-the-art results reported in the latest literature on targeted application scenarios. However, this requires expert-level knowledge and continuous follow-up in that domain.

3. Fallback Strategy: SYMBOL-E. Acknowledging the potential challenges in teacher selection for emerging optimization tasks, we introduced SYMBOL-E. This strategy allows for meta-learning an effective policy from scratch, without relying on any teacher optimizer, thus providing a feasible alternative when the teacher optimizer is strictly not available.

Thank you for your interest in and recognition of SYMBOL, as well as for participating in the discussion. We highly value your comments and would like to provide the following clarification.

1. The distinctions between [1] and SYMBOL are summarized as follows:

• Although both utilize symbolic regression techniques, the frameworks of [1] and SYMBOL are markedly different. Specifically, [1] follows a two-phase distillation framework: it first trains a numerical L2O model (such as RNN-Opt in our paper's baselines) by maximizing its performance on the training tasks, and then utilizes a GP-based symbolic regression method to search for symbolic update rules that best match the input and output pairs generated by the meta-learned L2O model for distillation. In contrast, SYMBOL meta-learns novel and effective update rules in a unified, end-to-end manner without a second phase of searching. Notably, SYMBOL is positioned as a generative approach rather than a distillation framework.
• The targeted tasks of [1] and SYMBOL are different. Both phases in [1] rely on gradient information and are dedicated to discovering a gradient descent algorithm. On one hand, it's essential to note that gradient information is not accessible for the black-box optimization (BBO) tasks we focus on, whereas SYMBOL incorporates gradient-free state representation as the input to generate BBO update rules. On the other hand, SYMBOL auto-regressively generates flexible update rules at each optimization step according to different optimization statuses, without limiting its behavior like a gradient descent algorithm.

---

2. The studies [2]-[4] have a similar methodology to the RNN-Opt [5] compared in our paper. These works require gradient information during training and limit the training problem sets to be differentiable. However, our SYMBOL approach focuses on more general scenarios where gradients cannot be used during training. In our paper, we compare our SYMBOL to more related works, such as DEDDQN[6], LDE[7], and Meta-ES[8], in the experimental varification. We also include RNN-Opt [5] as an external reference, and our results show that it generally underperforms our SYMBOL as well as [6]-[8]. Nevertheless, we will include these valuable works into our final version of paper, in the Related Works section.

---

3. Among the four works you mentioned, [2] has difficulty generalizing across different problem dimensions; [3] cannot generalize across different population sizes due to the pre-defined entries of parameters; and both [3] and [4] require re-training on unseen tasks, limiting their generalization across different tasks. In comparison, our SYMBOL approach is carefully designed to overcome these limitations and generalize effectively across various task distributions, dimensions, population sizes, and optimization horizons, as illustrated in Table 1 in Section 4.1 of our paper.

---

4. Regarding the problem dimensions, we would like to clarify:

• Although the COCO benchmarks, HPO tasks and Protein-Docking tasks in our paper possess no more than $20$ dimensions, their intricate optimization properties challenge the searching ability of BBO optimizers. They are widely used for evaluating BBO optimizers and MetaBBO methods (such as the baselines adopted in our paper: Meta-ES[8], MelBa[9], etc). The results in our paper show that SYMBOL achieves significant improvement against the MetaBBO baselines.
• From our aspects, a potential advantage of SYMBOL concerning different problem dimensions locates at the utilization of fitness landscape analysis based features as input, which is a fixed dimensional vector. Compared against the coordinate-wised input in [1]-[4], this design makes the SEG network in SYMBOL easily generalized to solve high dimensional tasks without additional overhead for processing the input.

---

We hope the above responses addressed your concerns.

[1] "Symbolic Learning to Optimize: Towards Interpretability and Scalability" (https://arxiv.org/abs/2203.06578).

[2] "Learning to Optimize in Swarms" (https://arxiv.org/abs/1911.03787).

[3] "B2Opt: Learning to Optimize Black-box Optimization with Little Budget" (https://arxiv.org/abs/2304.11787)

[4] "DECN: Automated Evolutionary Algorithms via Evolution Inspired Deep Convolution Network" (https://arxiv.org/pdf/2304.09599.pdf)

[5] “Meta-Learning for Black-box Optimization”, (https://arxiv.org/abs/1907.06901).

[6] “Deep reinforcement learning based parameter control in differential evolution”, (https://dl.acm.org/doi/abs/10.1145/3321707.3321813).

[7] “Learning adaptive differential evolution algorithm from optimization experiences by policy gradient”, (https://arxiv.org/abs/2102.03572).

[8] “Discovering Evolution Strategies via Meta-Black-Box Optimization”, (https://dl.acm.org/doi/abs/10.1145/3583133.3595822).

[9] “Meta-learning of Black-box Solvers Using Deep Reinforcement Learning”, (https://openreview.net/forum?id=9pO8hSVu0J).