Learning Multiple Initial Solutions to Optimization Problems

Authors: Elad Sharony, Heng Yang, Tong Che, Marco Pavone, Shie Mannor, Peter Karkus
Primary area: optimization
Keywords: optimization, initialization, optimal control, robotics, autonomous driving

Abstract:
Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications, such as robot control, autonomous driving, and portfolio management. The performance of local optimization methods in these settings is sensitive to the initial solution: poor initialization can lead to slow convergence or suboptimal solutions. To address this challenge, we propose learning to predict multiple diverse initial solutions given parameters that define the problem instance. We introduce two strategies for utilizing multiple initial solutions: (i) a single-optimizer approach, where the most promising initial solution is chosen using a selection function, and (ii) a multiple-optimizers approach, where several optimizers, potentially run in parallel, are each initialized with a different solution, with the best solution chosen afterward. We validate our method on three optimal control benchmark tasks: cart-pole, reacher, and autonomous driving, using different optimizers: DDP, MPPI, and iLQR. We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.

Decision: reject
Reviewer scores: 6, 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1730223701190

thread_type:
official_review

<thread_object>
creator: reviewer_m1fq

<content>
summary:
The paper introduces the Learning Multiple Initial Solutions framework, a neural network-based method for generating diverse initial solutions to improve local optimizer performance in time-sensitive tasks, such as robotics and autonomous driving. MISO supports both single-optimizer and multiple-optimizers configurations, allowing flexibility in selecting or parallelizing initial solutions.

strengths:
The paper introduces a framework that leverages a neural network to generate initial conditions for general optimization problems. This framework enhances optimization performance by selecting an initial condition that is generated by a neural network trained to encourage diversity while remaining close to the global optimum.

weaknesses:
While the empirical results indicate that the proposed framework may enhance optimization performance, the overall concept could be considered somewhat straightforward. 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.

questions:
For line 223, why is the pairwise distance loss defined as a function of $x^*$? To encourage diversity, shouldn’t the pairwise loss be maximized instead?
Could you elaborate what does problem instance $\psi$ stand for?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730431104075

thread_type:
official_review

<thread_object>
creator: reviewer_1rpu

<content>
summary:
The paper considers the problem of improving optimization solvers. The paper proposes to learn multiple initial solutions for the optimizers to improve its final performance. The authors argue the learning of initial solutions should consider both the distance to ground-truth optimal parameters and the dispersion among the multiple initial solutions to ensure coverage of the optimization landscape. Experiments show the proposed method improves the optimization performance with three different optimizers on three simulated tasks. Although the paper is sound and well-written, I find the method missing important details, its novelty questionable and the experiment domains relatively simple.

strengths:
1. The paper is very well written and easy to follow. 

2. The figures, especially Figure 1 and 2, help clearly illustrate the proposed approach vs. prior methods. 

3. The problem is well motivated and could be general for many tasks.

weaknesses:
1. Important details about the method is missing: Section 4 focuses on introducing the learning objective, i.e., the loss function, However, it is unclear to me what function approximator was used to output the multiple initial guesses for the optimization problems. Is it a neural network with randomness that will have a different output in each forward pass? Is it a neural network outputting all K guesses in one forward pass and the output is split into K guesses? Or other design? This is arguably the most important part of the method but is missing. 

1.1. The $\Lambda$ function is another important part of the method, but was very briefly described. According to Line 191 (“A reasonable choice”), the $\Lambda$ function is just chosen as the argmin of objective function? It is unclear what exactly is the choice of $\Lambda$ in the experiments. 

1.2. The distance function in Line 223 only makes sense if the norm of the different dimensions of the parameter x make sense. For example, if one dimension of x ranges from [0, 1] and another dimension ranges from [0, 10^5], the norm is not a good measure of difference. It is unclear whether this assumption is satisfied in the experimented problems. 

2. The claims in Line 259-262 may not be true. It depends on how the ensemble of models are learned. If the models themselves are multimodal such as latent models or energy-based models, they could represent multimodal behavior. 

3. Missing information in the experiments: 

3.1. What are the variations \psi for the experiment domains? This is completely missing and how do the authors make sure the training setup and evaluation setup do not overlap? Otherwise, the initial solution learning is just memorizing the best solutions for the tasks. 

3.2. How much data is used to train in the experiments? 

3.3. I believe the two evaluation modes in Line 359-367 are just open-loop and closed-loop. Should the authors use these well-accepted naming conventions instead? 

3.4. Because Cartpole and Reacher are relatively simple domains, it is surprising to see just naïve optimizers cannot solve these problems very well. Did the authors constrain the optimization steps to certain budget such that optimal solution was not found in time? 

4. One arXiv paper has done a similar approach on a more challenging racing task [1]. I understand it is an arXiv paper recently and the authors might have missed it, but it seems the paper has even accomplished what this paper proposes in future work (reinforcement learning tuning for the initial guess). Could the authors compare and state how the proposed method is still unique? 

[1] Li, Z., Chen, L., Paleja, R., Nageshrao, S., & Gombolay, M. (2024). Faster Model Predictive Control via Self-Supervised Initialization Learning. arXiv preprint arXiv:2408.03394.

questions:
See weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730644452462

thread_type:
official_review

<thread_object>
creator: reviewer_lsk9

<content>
summary:
The authors present an approach for computing multiple initializations for a downstream optimization task. The authors employ a winner-takes-all and pairwise distance loss to ensure multimodality of the initializations. This way, the produced initializations achieve better coverage and are more representative of a landscape with multiple optima.

strengths:
The paper is easy to read and well-motivated. The presented approach is relevant, interesting and seemingly novel.

weaknesses:
The proposed approach does not have any theoretical guarantees.

It is unclear if the experimental section considers varying constraints and environment parameters outside the autonomous driving example. The paper would also benefit from comparing to more well-known control examples, e.g., from Mujoco.

The choice of \Lambda beyond the optimization problem is somewhat unclear and lacks motivation.

The second optimization pipeline is merely an extension of the first, though it is presented as one of the major contributions.

questions:
At first sight, the second approach presented by the authors seems to always be at least as good as the first one. The only limitation seems to be that it is more computationally expensive because multiple optimizers are used. 

Why would any function other than J be used to specify \Lambda? It feels to me like J is simply poorly chosen if \Lambda is specified using any other criterion.

The name for the winner-takes-all is somewhat confusing. Intuitively, the name indicates that the best solution is used to compute the loss, not the worst.

In lines 299/300, what do the authors mean by "training loss over either control, state, or state-control sequences"? Does this mean that they use a distance metric for L_reg that takes the state into account? I would be helpful to have an explicit mathematical formulation in the appendix.

Is the difference between one-off and sequential evaluation the same as open-loop and closed-loop control? How are the initial conditions selected for the one-off evaluation?

As I understood it, the environment parameters do not vary between evaluations in the reacher and cart-pole settings. It would interesting to see how the approach performs, e.g., with varying constraints, obstacles and environment parameters (weight, arm length, etc.)
</content>
</thread_object>

</thread>
<thread>
creation date:
1730671698266

thread_type:
official_review

<thread_object>
creator: reviewer_dukr

<content>
summary:
The paper introduces a method for learning a set of candidate initial solutions to warm-start optimal control problems. It proposes a series of objectives that encourage learning multimodal solutions, using a transformer architecture as a backbone to predict K control trajectories. The proposed method is evaluated on 3 different sequential optimization tasks and yields performance improvements over the presented baselines.

strengths:
- The problem setting is relevant for the community. The proposed method outperforms the presented baselines on 3 different tasks and the trained neural network architecture achieves fast inference rates, which are suitable for closed-loop control.

- The paper is well-written overall and presents multiple ablations for the different loss functions that were introduced. The experiments also indicate that the trained model captures the multimodality of the solution space, to some degree, depending on the hyperparameter K that denotes the fixed number of initial solutions that are predicted.

weaknesses:
- Using ensembles of models is not a very strong baseline for multimodality. Diffusion Policies [1] or action chunking transformers [2] might be stronger baselines. Even if they do not have such a fast inference time as the proposed method, it would further strengthen the paper to position the method with respect to such baselines. 
- The method is only evaluated on 3 low-dimensional problems and it is unclear how its performance will scale or degrade in more complex settings. 

[1] Cheng Chi et al, Diffusion Policy: Visuomotor Policy Learning via Action Diffusion.
[2] Tony Zhao et al. Learning Fine-Grained Bimanual Manipulation with Low-Cost Hardware.

questions:
- As mentioned by the authors, finding optimal solutions for higher dimensional problems might be challenging. In that setting, the optimizers are more likely to provide only suboptimal solutions within a time budget.  How could the proposed loss be extended to leverage the potentially suboptimal generated by the optimizers in a more complex setting?

- Is there any specific reason why a specific optimizer wash was chosen for each task? The paper mentions a trivial generalization to a setting with a heterogeneous set of optimization methods. But no experiments are reported. Would a heterogeneous set of optimization methods increase the chances of finding multimodal solutions and thus help with scalability to more complex settings? 

- What is the total time required to get a  "best solution"? (Fig 1). The inference time of the network might be fast but if the predicted initial solutions are not close to a local optimum, the optimizers might require multiple iterations to converge. Reporting the average number of additional iterations of the optimizers or the time to converge after warm-starting can potentially further highlight the quality of the learned initial solutions.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731673221343

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We thank all the reviewers for their thoughtful feedback and for recognizing the relevance of our problem setting, our experimental results' strength, and our paper's quality. We have carefully considered all the comments and believe that the concerns raised were minor and have been adequately addressed in our responses and revisions.

We hope our clarifications have resolved any uncertainties and strengthened the paper. If you feel that your concerns have been addressed, we would appreciate it if you could reflect this in your score or respond if there are any remaining concerns.
</content>
</thread_object>

</thread>
<thread>
creation date:
1738748316180

thread_type:
public_comment

<thread_object>
creator: ~arun_kumar_singh1

<content>
title:
A closely related work

comment:
Hi

We have been working towards generating multiple solutions to an optimization problem with applications to swarm trajectory generation.

This is a pre-print of our work that leverages variational models with trajectory optimization to produce diverse solutions. Hope you find our work useful and if so, please cite us in your future works.

Swarm-Gen: Fast Generation of Diverse Feasible Swarm Behaviors
https://arxiv.org/html/2501.19042v1.
</content>
</thread_object>

</thread>
<thread>
creation date:
1739381909401

thread_type:
public_comment

<thread_object>
creator: ~anjian_li1

<content>
title:
A related work

comment:
Dear authors,

We have been exploring a similar approach for accelerating non-convex optimization using amortization. In our recent paper DiffuSolve, we used a diffusion model to sample from the distribution of local optima, which were then used as diverse initial guesses to warm-start the solver in parallel. Given the similarities between our topics and approaches, we would appreciate it if you could acknowledge our work in your paper. Thank you.

DiffuSolve: Diffusion-based Solver for Non-convex Trajectory Optimization
[https://arxiv.org/abs/2403.05571](https://arxiv.org/abs/2403.05571)
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper presented a novel framework for predicting multiple initial solutions for sequential black-box optimization problems.
The authors introduced two strategies to predict initial solutions called single-optimizer and multiple-optimizers (not necessarily running in parallel), for the chosen of the best one-step optimizer.
As a neural network driving approach, the proposed method does not have any theoretical analysis, which is ok. The authors evaluated three distinct sequential optimization tasks in simulation, without comparison to any decision-transformer line of algorithms.
The improvement of either theoretical or empirical performance are welcome.