DisCo-DSO: Coupling Discrete and Continuous Optimization for Efficient Generative Design in Hybrid Spaces

We thank the reviewer for her/his comments and suggestions. We will address the reviewer's comments in the following.

1. "Why is an autoregressive policy structure is necessary? ... this study appears to be focusing on optimizing a specific given problem. In such a case, wouldn't it be more efficient to explore the entire solution space rather than constructing solutions sequentially?" We would like to emphasize that DisCo-DSO is explicitly tailored for generative optimization scenarios where the solution is constructed sequentially. In this context, the sequential construction of the solution arises due to the following factors:

1. The length of the sequence is variable.
2. The order of the sequence is not predetermined but is determined by the model.
3. There exist prefix-dependent positional constraints (or priors) dictated by the specific problem at hand. For instance, in symbolic regression, the model should not be allowed to add a trigonometric operator if it has already done so in the past to avoid nested trigonometric operators.

The reviewer is right in that we are solving specific problem instances, but even then, the above factors are present. An autoregressive policy is well-suited to address these factors. We will clarify this in the camera-ready version of the paper.

2. "How is the order for selecting optimization variables determined, and does this order have the potential to affect the performance?" In this work, we are doing de novo design: we start from an empty set and let the model decide which and how many tokens (or building blocks) to add to the solution. The length of the solution is variable and the order in which the tokens are added is determined by the model. The ordering is a decision variable of the optimization problem (we can not fix it a priori). The reviewer is right that, in the tasks of symbolic regression and decision tree search, the order in which the tokens are added will affect the final design and thus the performance. The model should learn to add the tokens in the order that maximizes the reward. We will clarify this in the camera-ready version of the paper.

3. "How does this research differ from those studies involving MIPs?" The main differences between DisCo-DSO and approaches that use deep learning to solve MIP problems are the following:

1. The search space in DisCo-DSO is less structured than in MIP problems. The solutions in DisCo-DSO are variable length and the order in which the tokens are added is determined by the model. In MIP problems, the solutions are fixed length and the order is fixed.
2. In DisCo-DSO we have positional constraints that depend on the prefix of the solution. For instance, in symbolic regression, the model should not be allowed to add a trigonometric operator if it has already done so in the past to avoid nested trigonometric operators. In general MIP problems, the constraints are fixed and do not depend on the prefix of the solution.
3. In DisCo-DSO, discrete and continuous variables are linked. For instance, in decision tree search, we have the discrete variable $x_i < \beta$ and the continuous variable $\beta =5.3$, that jointly form the decision tree node $x_i < 5.3$. The search mechanism is designed to optimize both variables jointly. It is unclear if the approaches that use deep learning to solve MIP problems can handle this type of coupling. We will clarify this in the camera-ready version of the paper.

We will add a discussion about the differences between DisCo-DSO and approaches that use deep learning to solve MIP problems in the camera-ready version of the paper.

4. "It would be beneficial to solve a more diverse set of problems and provide statistical evidence to validate the performance". In this paper, we wanted to investigate the benefits of DisCo-DSO over the standard decoupled approach in generative optimization scenarios where the solution is constructed sequentially. For generality, we wanted to cover deterministic and stochastic optimization problems and also, different search spaces and semantics. We chose symbolic regression (deterministic optimization over the space of mathematical expressions) and decision tree policies in RL (stochastic optimization over the space of decision trees) as representative examples of these scenarios. The implementation of each of these tasks in non-trivial and required a significant amount of work. We believe that the results are conclusive and statistically significant, and show that DisCo-DSO outperforms the standard decoupled approach in terms of generalization over the test data and quality of solution per number of function evaluations.

We thank the reviewer for the comments and suggestions. We will address the reviewer's comments in the following.

"The concatenation of discrete and continuous variables into a single vector and the higher-level approach are very straightforward and their novelty seems limited." We agree with the observation that the concatenation of discrete and continuous variables into a single vector, along with the higher-level approach, may seem straightforward. However, we would like to highlight that the novelty of our approach lies in its application to the specific problem of optimization with generative models for hybrid spaces. The integration involves several challenges that we address in the paper, such as the need for prefix-dependent positional constraints, and the extension of the gradient update to handle the new search space. To the best of our knowledge, this is the first instance where such a concept has been systematically employed in this context. We believe this application of the idea adds a significant contribution to the field and opens up new avenues for research.

"Why are you comparing your method against the baselines you define as opposed to using baselines from the literature in the case of symbolic regression (Figure 3)?" The paper already contains well-established baselines for symbolic regression. In particular:

1. "Decoupled-GP-BFGS": This baseline corresponds to a standard implementation of Genetic Programming for symbolic regression à la Koza, 1994. This represents the current most common approach to symbolic regression in the literature.
2. "Decoupled-RL-BFGS": This baseline corresponds exactly to the method "Deep Symbolic Regression" from Petersen et al., 2021. We use the same codebase and the same hyperparameters. We will clarify this in the camera-ready version of the paper.

We want to emphasize that the main contribution of the paper is not the application of DisCo-DSO to symbolic regression, but rather the investigation of the coupled discrete-continuous optimization approach in generative optimization scenarios where the solution is constructed sequentially. Nevertheless, following the reviewer's suggestion, we have computed results for two recent deep learning approaches to symbolic regression: Kamienny et al., 2022 and Biggio et al., 2021. These are the results that we obtained for a similar number of function evaluations (note that their code does not natively report the number of function evaluations) for Kamienny et al., 2022:

and for Biggio et al., 2021 (note that this system only supports $\leq 3$ dimensions):

We can see that the coupled approach of DisCo-DSO still outperforms or gives comparable results to these baselines. We will add these results together with a discussion about the differences between DisCo-DSO and these baselines in the camera-ready version of the paper.

References:

• John R Koza. Genetic programming as a means for programming computers by natural selection. Statistics and computing, 4:87–112, 1994.\
• Brenden K. Petersen et al. Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients. ICLR 2021, Virtual Event, Austria, May 3-7, 2021.\
• Pierre-Alexandre Kamienny, St´ephane d’Ascoli, Guillaume Lample, and Franc¸ois Charton. End-to- end symbolic regression with transformers. arXiv preprint arXiv:2204.10532, 2022.\
• Luca Biggio, Tommaso Bendinelli, Alexander Neitz, Aurelien Lucchi, and Giambattista Parascan- dolo. Neural symbolic regression that scales. In International Conference on Machine Learning, pp. 936–945. PMLR, 2021.

We highly appreciate the reviewer's comments and suggestions. Her or his comments show that the reviewer has read the paper carefully and understood the main contributions of the paper. We will address the reviewer's comments in the following.

"However, it seems that this approach also may have misleading rewards for the skeleton or continuous solution if neither are optimal. It may shy away from high quality discrete solutions even though there may be one setting of continuous variables which are highly performant" Our results in symbolic regression and decision tree search do not suggest that the model is shying away from high quality discrete solutions. On the contrary, the results show that a coupled approach outperforms a decoupled approach in terms of generalization over the test data and quality of solution per number of function evaluations.

The reviewer is right that there could be a situation where DisCo-DSO produce the optimal discrete skeleton and fail to find the optimal continuous solution (this could also happen in a decoupled approach). However, the opposite is often true in decoupled approaches: we find a poor discrete skeleton and we make it work by overfitting the continuous parameters to the data. This can have the effect of confusing the model and lead to a suboptimal solution. As we show in the experiments in the paper, this effect is catastrophic in terms of generalization over the test data (parsimony of the produced solutions) and wasted function evaluations.

"It is also unclear how this approach may work on more complicated discrete-continuous settings where the feasible region may be more complex such as in solving mixed integer linear programming" We would like to emphasize that DisCo-DSO is explicitly tailored for generative modeling scenarios where :

1. The length of the solution is variable.
2. The order of the solution is not predetermined but is determined by the model.
3. There exist prefix-dependent positional constraints (or priors) dictated by the specific problem at hand. Standard mixed integer linear programming problems problems do not satisfy these conditions.

That said, we believe that DisCo-DSO can be extended to mixed integer linear programming problems using the $\text{const}(\beta)$ operator (similar to symbolic regression). We could then use rejection sampling to sample from the feasible region. Although interesting, we believe that this is beyond the scope of this paper. We will clarify this in the camera-ready version of the paper.

"...or in other cases where the continuous space may be more decoupled from the discrete space such as in cases where there are many continuous decisions that need to be made but not all of them have a corresponding discrete decision". DisCo-DSO would support this case by using the $\text{const}(\beta)$ operator (similar to symbolic regression). Note that $\beta$ does not need to be related to a discrete decision. The relation is only established by the ${\tt eval}$ operator. For instance, consider the fully continuous problem of finding the maximum of a function $f(\boldsymbol{x})$ with $\boldsymbol{x} \in \mathbb{R}^n$. In this case, we will have $\mathcal{L}= \hat{\mathcal{L}}=\{\text{const}(\beta)\}$. DisCo-DSO will produce skeletons $\langle \text{const}(\beta_1), \dots, \text{const}(\beta_n) \rangle$ and the $\beta_i$'s will be stochastically optimized by standard expectation–maximization. We will clarify this in the camera-ready version of the paper.

Application to real world use cases of symbolic regression. The objective of the experiments in the symbolic regression task was to investigate the sample efficiency of DisCo-DSO compared to traditional decoupled approaches. We believe that those conclusions will be valid regardless of the origin of the data.

"How does this method avoid the issue of poor or misleading rewards for the right discrete skeleton?" Our empirical evaluation in symbolic regression and decision tree search suggests that DisCo-DSO does not suffer from this issue, but rather outperforms decoupled approaches in terms of generalization over the test data and quality of solution per number of function evaluations. See above for more details.

"Is it possible to generate continuous decisions that are unrelated to discrete decisions and thus uncoupled?" We addressed this question above. The short answer is yes. We will clarify this in the camera-ready version of the paper.

We thank the reviewer for her/his comments. The "summary" and "strengths" sections that the reviewer compiled show that the reviewer has read the paper carefully and understood the main contributions of the paper. We will address the reviewer's comments in the following.

"In my opinion, this work has a moderate impact on a specific sub-area of generative modeling". We believe that the field of optimization with generative models is a very important area of research with many real-world applications, whose importance is only going to increase in the future. We believe that our method can have a significant impact in this field by providing a rather simple and effective way to optimize generative models in hybrid spaces.

Comparison with prior work. We want to clarify that the baseline Petersen et al., 2021 is present in each experiment under the alias "Decoupled-RL-BFGS". Our work builds upon the openly available codebase of Petersen et al., 2021, accessible at https://github.com/dso-org/deep-symbolic-optimization, establishing a direct one-to-one correspondence between Petersen et al., 2021, and "Decoupled-RL-BFGS". We regret any lack of clarity in our initial presentation and commit to explicitly addressing this correspondence in the forthcoming camera-ready version.

The reviewer cites baseline studies by Kamienny et al., 2022; Sahoo et al., 2018; Biggio et al., 2021; and Landajuela et al., 2021. Please note that the method in Landajuela et al., 2021 corresponds to Petersen et al., 2021 (but applied to the symbolic policy discovery for RL). Thus, this method is already present in our paper under the alias "Decoupled-RL-BFGS".

We compile results on our validation benchmark for Kamienny et al., 2022 using the codebase provided by the authors. These are the results that we obtained for a similar number of function evaluations (note that their code does not natively report the number of function evaluations, so we had to estimate it):

Following the reviewer's suggestion, we also consider Biggio et al., 2021 as a baseline. However, we were not able to directly apply their method to our validation benchmark, as their system only supports $\leq 3$ dimensions. We then just report the subsets of the validation benchmark that are supported by their system. These are the results that we obtained for a similar number of function evaluations (note that their code does not natively report the number of function evaluations and we had to estimate it):

We can see that the coupled approach of DisCo-DSO still outperforms or gives comparable results to these baselines (note that the results of Biggio et al., 2021 are only comparable for $\leq 3$ dimensions). We will add these results together with a discussion about the differences between DisCo-DSO and these baselines in the camera-ready version of the paper.

Choice of autoregressive model. The reviewer raises an interesting point. To address it, we have repeated the experiments in Symbolic Regression (Task 4.2) using different autoregressive models of different sizes. Specifically, we consider a GRU and a LSTM recurrent cell with 16, 32, and 64 hidden units. The results are shown in the following table:

We observe that the results show little difference between the different models architectures and sizes. This trend is consistent with results in the RL literature, where often the choice size of the policy network has little effect on the performance of the algorithm, as long as the network is large enough to capture the complexity of the problem. We will add this discussion in the camera-ready version of the paper.

Organization and structure. We will add paragraph titles to the sections mentioned by the reviewer in the camera-ready version of the paper.