Learning Multiple Initial Solutions to Optimization Problems

Concern 1: "While the empirical results indicate that the proposed framework may enhance optimization performance, the overall concept could be considered somewhat straightforward."

Thank you for your feedback. While our framework may seem straightforward, it uniquely fills a significant and novel gap in optimization initialization strategies. The area of learning to warm-start optimizers is indeed active [1]. However, existing approaches typically focus on a single initialization. To our knowledge, our work is the first to employ a single network to generate multiple diverse initializations for local optimizers. This advancement is particularly important for time-constrained non-convex optimization problems where multiple local minima are present.

[1] Brandon Amos. Tutorial on amortized optimization.

---

Concern 2: "A more substantial theoretical analysis could add depth to the work, as there is no clear indication that the neural network-generated initial states will consistently yield improved results. Consequently, the framework's contribution may seem limited in its novelty and theoretical rigor."

Without guarantees on the generator, it is difficult to make solid theoretical claims; conversely, with such guarantees, the problem would be significantly simplified and perhaps trivial. Most methods in this research field are heuristic-based, aiming to improve performance rather than provide formal guarantees. Nevertheless, as noted in lines 202-205, our approach allows for the inclusion of traditional initialization methods, such as warm-start heuristics, as part of the set of initializations, e.g., as the $(K+1)$-th initialization. This means our method does not risk degrading performance compared to established practices, effectively providing a safety net. Our contribution demonstrates that learning multiple diverse initializations can empirically enhance optimizer performance across various tasks and optimizers. We have provided extensive empirical evidence to support this.

---

Question 1: "For line 223, why is the pairwise distance loss defined as a function of ( \mathbf{x}^\star )? To encourage diversity, shouldn’t the pairwise loss be maximized instead? "

Thank you for catching this error and for your insightful question. You are correct—the pairwise distance loss should be defined between the predicted initial solutions $\hat{\mathbf{x}}_k^{\text{init}}$, and we aim to maximize this pairwise distance to promote diversity among them. The inclusion of $\mathbf{x}^\star$ in the loss function was a typographical error in the paper. In our experiments, we indeed considered the negative pairwise distances, effectively maximizing the distances between the predicted initial solutions. This encourages the model to output initializations that are different from each other, enhancing the exploration of the solution space by the optimizer. The error in the paper is solely a typo, and our implementation correctly reflects the intended formulation.

---

Question 2: "Could you elaborate what does problem instance stand for?"

Yes, we have detailed this in lines 291-293 of the paper:

"The problem instance parameters $\psi$ encompass the initial state $s_0$, and other domain-specific variables that parameterize the objective function or constraints, such as target states, reference trajectories, obstacle positions, friction coefficients, temperature, etc."

We appreciate your careful consideration of our work and hope that our responses have adequately addressed your feedback.

Concern 1: What function approximator was used to output the multiple initial guesses?

As described in lines 174-175, our method employs a neural network that outputs all $K$ initializations in a single forward pass, aligning with the mathematical definition in line 177.

---

Concern 2: What is the exact choice of $\Lambda$ used in the experiments?

In lines 190-191, we note that in our experiments, we use the objective function J as $\Lambda$, which is both natural and effective, as it directly aligns with our optimization goals. Furthermore, lines 192-194 explain how $\Lambda$ can be tailored to include additional criteria based on domain-specific requirements or further context from the problem instance $\psi$. In addition, we have added a section in the appendix (lines 1004-1042) that elaborates on the selection of $\Lambda$.

---

Concern 3: Is the distance function in Line 223 appropriate given possible differences in the scales of the dimensions of $x$, and is this assumption satisfied in the experimental problems?

Before training, all features are standardized (760-761).

---

Concern 4: Do the claims in Lines 259-262 consider latent models or energy-based models?

At the beginning of the example (lines 247-249), we confine the discussion to regression models or ensembles of regressors. We aimed to illustrate why explicitly promoting multimodality in multi-output regression models is essential.

---

Concern 5: What are the variations $\psi$ in the experimental domains, how much data is used for training, and how do you ensure that the training and evaluation setups do not overlap?

1. Variations ( $\psi$ ): We provide a detailed description in lines 782-784.
2. Training Data Size: Approximately 500,000 training instances were used for each task. We've added this detail in line 758.
3. Training and Evaluation Separation: As highlighted in line 50, the evaluation set contains previously unseen problem instances; specifically, the evaluation set is generated from scenarios different from the test set. To further clarify that, we've included a description of the evaluation settings in the appendix (1058-1071).

---

Concern 6: I believe the two evaluation modes are just open-loop and closed-loop

We appreciate your suggestion. Indeed, in control settings, closed-loop and sequential evaluations are identical. However, the term closed-loop is not always applicable in general optimization, which is why we use a more general terminology. One-off evaluation, however, is not the same as open-loop control. We've added a section in the appendix (1044-1056) to clarify this subtle difference.

---

Concern 7: Did the authors constrain the optimization steps or budgets such that naïve optimizers could not find the optimal solution in time for the Cart-pole and Reacher tasks?

Yes, exactly. While Cart-pole and Reacher are classic benchmarks, optimally solving all instances under strict runtime constraints can become non-trivial [1]. To reflect these realistic conditions, we imposed limits on the optimizers in our experiments (detailed in lines 681-784). These constraints make the problems more difficult, emphasizing the importance of good initializations to find high-quality solutions quickly. Our settings are not arbitrarily strict but reflect practical scenarios, such as autonomous driving, where strict runtime constraints are essential. All baseline methods were evaluated under the same constraints to ensure fair comparison.

[1] Scokaert, et al. Suboptimal model predictive control.

---

Concern 8: "One arXiv paper [1] has done a similar approach on a more challenging racing task. Could the authors compare and state how the proposed method is still unique?"

Thank you for pointing out this related work. However, the paper [1] does not present novel concepts beyond existing research already cited (111-137). Key distinctions between our approach and [1] include:

1. Diverse Initializations: Unlike [1], which focuses on a single initialization, our method is designed to generate multiple diverse initializations. To the best of our knowledge, our work is the first to use a single network to learn multiple diverse initializations for local optimizers.
2. Broader Evaluation: The referenced paper evaluates their approach on a single racing task with a specific optimizer. In contrast, we demonstrate the effectiveness of our method across multiple tasks and various optimizers.
3. Innovative Methodology: Our approach introduces specialized loss functions to promote multimodality without relying on reinforcement learning.
4. Future Work: We propose integrating reinforcement learning to further enhance our method by predicting multiple initializations (472-473).

Thank you for your detailed comments. We hope that our responses have satisfactorily addressed your concerns.

We appreciate your positive feedback and are glad our clarifications addressed your concerns.

Regarding your follow-up:

• "[...] It is very important to know what architecture this neural network is [...] Sharing what neural network architecture enables outputting diverse initialization is the key of the paper. Would you agree? I actually found this answer in Supplementary A.3 Network Architecture."
• "I just thought the main paper could discuss the design of architecture for diffferent domains, which will be very helpful for practitioners."

We emphasize that the neural network architecture itself does not enable diverse predictions. The novelty of our work lies in the proxy training objectives and the selection function (lines 53, 80, 96, 210–211), which, we believe, are independent of specific architectures and thus broadly applicable.

To address your feedback, we've updated the revision to mention that architecture details are in the appendix (lines 174–175).

If there are remaining concerns preventing a higher score, please let us know, and we'd be happy to address them.

Concern 1: The proposed approach lacks theoretical guarantees.

Without guarantees on the generator, it is difficult to make solid theoretical claims; conversely, with such guarantees, the problem would be significantly simplified and perhaps trivial. Most methods in this research field are heuristic-based, aiming to improve performance rather than provide formal guarantees. Nevertheless, as noted in lines 202-205, our approach allows for the inclusion of traditional initialization methods, such as warm-start heuristics, as part of the set of initializations, e.g., as the $(K+1)$-th initialization. This means our method does not risk degrading performance compared to established practices, effectively providing a safety net. Our contribution demonstrates that learning multiple diverse initializations can empirically enhance optimizer performance across various tasks and optimizers. We have provided extensive empirical evidence to support this.

---

Concern 2: Unclear if constraints vary in experiments

As you correctly noted in Question 6, the environment parameters in the Reacher and Cart-pole tasks do not vary. We provided a comprehensive breakdown of each task (674-728) and referenced it within the experiment section (315-316).

---

Concern 3: Comparing to more examples

As detailed in our problem setup (144–154) and core concept (165–167), our research is task-agnostic. As such, rather than focusing on its nominal performance, we primarily concentrate on improving an optimizer's performance compared to that nominal performance. Using different tasks will primarily evaluate the optimizer's robustness and adaptability, which is not the focus of our work.

---

Concern 4: The choice of $\Lambda$ unclear and lacks motivation.

Thank you for your feedback. We have added a section in the appendix (1021-1049) that discusses choices for $\Lambda$, provides examples of how it can be designed to incorporate additional criteria such as safety constraints or robustness measures, and explains how $\Lambda$ can be learned or adapted based on the problem context.

---

Concern 5: "The second optimization pipeline is merely an extension of the first but is presented as a major contribution."

We appreciate your perspective but respectfully disagree. Unlike prior methods that predict only a single initialization, our approach seamlessly supports both single-optimizer and multiple-optimizers settings. This flexibility enables the utilization of multiple initial solutions in diverse ways, greatly enhancing the applicability and effectiveness of our method.

---

Question 1: The multiple-optimizers setting is always at least as good as the single-optimizer

Yes, our results show (415-416) that it does leads to consistently better results. However, our objective was not to compare these frameworks but rather to introduce two strategies for leveraging multiple predicted initial solutions. Parallelism in optimization is an active research area (128-140), yet most works still rely on a single-optimizer framework. Importantly, our results demonstrate that even when using a single optimizer, selecting an initialization from $K$ predictions significantly outperforms methods that rely on a single initialization.

---

Question 2: "winner-takes-all naming"

As detailed in lines 227-228, the Winner-Takes-All (WTA) method indeed selects the best prediction (the one with the lowest loss) and computes the loss using only that prediction. This is further defined mathematically in line 229, ensuring that the naming accurately reflects its functionality.

---

Question 3: Training loss over state sequences

To further clarify this point, we have elaborated the state loss section in the appendix (890-942) and added an explicit mathematical formulation of the loss functions in that state loss.

---

Question 4: sequential vs. closed-loop and one-off vs. open-loop

Thank you for this question. Indeed, in control settings, closed-loop and sequential evaluations are identical. However, the term closed-loop is not always applicable in general optimization, which is why we use a more general terminology. One-off evaluation, however, is not the same as open-loop control. We've added a section in the appendix (1044-1056) to clarify this subtle difference.

---

Question 5: Initial conditions in the one-off evaluation

We've included a description of the one-off setting evaluation in the appendix (1058-1071).

---

Question 6: Varying constraints and environment parameters in experiments

Similar to Concern 3. Introducing different constraints and obstacles would primarily evaluate the optimizer's robustness and adaptability, which is different from the focus of our current goals.

Thank you for your insightful review. We hope that our responses and revisions have adequately addressed your feedback.

Concern 1: (1) Diffusion Policies or action chunking transformers. (2) Ensembles of models are not very strong baseline.

While these are attractive alternatives, achieving fast inference times is due to strict runtime constraints (see lines 11, 29, 153, and 284). Our method efficiently generates multiple initial solutions, requiring little to no additional inference time. We chose ensembles as a baseline because they utilize the same architecture, allowing for a fair comparison of our proposed loss functions and selection strategies.

---

Concern 2: The method is only evaluated on 3 low-dimensional problems

As detailed in our problem setup (lines 144–154) and core concept (lines 165–167), our research is task-agnostic. As such, rather than focusing on its nominal performance, we primarily concentrate on improving an optimizer's performance compared to that nominal performance. Introducing different constraints and obstacles would primarily evaluate the optimizer's robustness and adaptability, which is not the focus of our work. In addition, as detailed in lines 287-288, since our method interacts with the optimizer rather than directly with the control task, it handles sequences of states and control inputs ($H \times S$, $H \times A$), which moves beyond simple state-action pairs.

---

Question 1: How can the proposed loss be extended to leverage suboptimal optimizer solutions in higher-dimensional problems?

Thank you for this insightful question. In our current setting, we do not use optimal solutions but rather (near)-optimal solutions obtained from local optimizers with extended runtimes (lines 754-758). Nevertheless, if only suboptimal solutions are available, we can adapt our loss function to account for solution quality, e.g., by incorporating a weighting factor based on the suboptimality gap—if quantifiable—we can prioritize learning from higher-quality solutions while still leveraging all available data.

---

Question 2: Why was a particular optimizer chosen for each task?

Thank you for raising this point. We selected DDP for the cart-pole task based on [1], where this optimizer was introduced. MPPI was chosen for reacher-hard due to its additional control dimension [2], and iLQR as the standard optimizer for the nuPlan autonomous driving benchmark.

[1] Brandon Amos, et al. Differentiable MPC for end-to-end planning and control. [2] Yuval Tassa, et al. Deepmind control suite.

---

Question 3: A heterogeneous set of optimization methods / why were no experiments conducted on this?

As we mention on line 481, exploring a heterogeneous set of optimization methods is an exciting direction for future work. Incorporating different optimizers could be beneficial, as each optimizer has strengths and weaknesses and may perform differently depending on the problem characteristics. Using a heterogeneous set allows us to capitalize on these differences, potentially increasing the chances of finding diverse, high-quality solutions.

---

Question 4: "What is the total time required to get a 'best solution'? (Fig 1)"

In our experiments, the total time to achieve the best solution includes the neural network inference and the optimizer runtime, demonstrating that our approach is fast enough for real-time applications (lines 723-728). If you were specifically referring to $\Lambda$, the optimizers, by default, assign a scalar cost to each solution, making the selection of the minimum cost solution computationally negligible.

---

Question 5: Reporting the average number of additional iterations of the optimizers or the time to converge can potentially further highlight the quality of the learned initial solutions

While examining optimizer convergence could offer insights, metrics such as average additional iterations or convergence time are not particularly meaningful in our context. For instance, an optimizer might converge more quickly within the allocated budget but reach a suboptimal local minimum. In contrast, another optimizer might use the entire budget to find a better solution. Faster convergence does not necessarily equate to better performance. Additionally, there are no practical advantages to converging before the budget limit, as the optimizer would wait the remaining time until that solution is required. Furthermore, sample-based optimizers like MPPI operate with a fixed sample budget, eliminating the concept of iterations.

Our main emphasis is on the quality of solutions within the given computational constraints, which is directly reflected in the cost metrics we report. We demonstrate that our method scales efficiently and consistently with the number of predicted initial solutions $K$ (lines 855-888), and we find that all outputs remain effective even as $K$ increases (lines 946-953).

We thank you for your constructive feedback and hope our revisions meet your expectations and alleviate any remaining concerns.

Dear Arun Kumar Singh,

Thank you for sharing your preprint and for your interest in our research.

Since our work has been publicly available (https://arxiv.org/abs/2411.02158) since November 4, 2024—approximately three months prior to your January 31, 2025 preprint—we would appreciate it if you would cite our paper to acknowledge its contributions.

We will likewise include a citation to your preprint in forthcoming revisions.

Dear Anjian Li,

Thank you for sharing your work on DiffuSolve. While both of our studies aim to accelerate non‐convex trajectory optimization by providing high-quality initial guesses, there are notable differences in our approaches. DiffuSolve leverages a diffusion model that iteratively samples candidate solutions, whereas our method directly predicts multiple diverse initializations in a single forward pass. This design is particularly well-suited for applications with strict runtime constraints, where rapidly generating multiple promising initializations is critical.

We believe these complementary perspectives open exciting avenues for future research, including the potential for hybrid approaches that combine the strengths of both methods. Given the relevance of our respective contributions, we will include appropriate citations to your work in our next revision.