Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information

Summary

This paper considers the class of problems known as Smart Predict and Optimize (or Decision-Focused Learning) where the learning task consists in learning the parameters of an optimization model given some of their features. The difficulty comes from trying to include the optimization model into the learning pipeline, since it is hard to differentiate over the optimization model. The paper proposes to learn two optimization model: one to learn the objective of the optimization model and one to learn the coefficient of the optimization model. These are trained using an iterative algorithm that tries them in sequence. The paper applies this approach to the traditional benchmarks used in SPO and show that the approach has benefits overall.

Strengths

Algorithm 1 is the main contribution of the paper. It is an elegant way to solve SPO problems in general.

Weaknesses

1. The formalization really gets in the way in this paper. I will try to list these issues here 1.a The model M which approximates the solver should receive only one set of parameters. I do not understand why you would use c_\theta(y_i) and z_i in (3). It would be better to explain in detail the inputs of the model M 1.b In (4), the notation M_w(Y,Z;\theta^*) does not make any sense. M_w does not receive \theta^* in Algorithm 1. As a result, the bilevel model (4) does not make sense. 1.c why is the learning task expressed as min_{\theta,w} | M_w(c_theta(y)) - f(z) |? 2. Algorithm 1 is an ADMM approach to the optimization as shown above in fact. 3. I do not understand 4.1. The goal of SPO is to find the parameters of the optimization which is what c_\theta does? How is Model M useful on testing instances and model deployment? It does not compute any solution, just the objective. 4. In 4.2, you mention that you need Z to train M. This is contradictory with 4.1 where you are using it in unseen test instances. You do not have Z on unseen instances.

Questions

See above.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

The benefits on the portfolio optimization are computational only. This area seems to always consider the same three problems.

Summary

This paper proposes the a novel framework for learning the predicted value of an optimization task under limited information. Specifically, the goal is to learn $\mathcal{M}\_w(y, z) = f (g\_\theta (y), z)$ function where $y$ is the limited information, $z$ is the complete information, $f$ is the objective value of an optimization function to be maximized, and $g\_\theta$ is a way to generate a solution to the optimization problem based on the limited information $y$. In essence, there are 2 sets of interdependent parameters to learn -- $\theta$ and $w$, and the paper proposes an alternating update scheme for solving the joint problem. They then apply this framework to 2 classes of problems---Smart Predict-then-Optimize (SPO) and Mixed Integer Non-Linear Programming (MINLP)---and show that this method outperforms similar approaches in each class.

Strengths

* **Great exposition**: The paper is well written and easy to follow. * **Good experiments**: The paper uses domains from the literature and compares to relevant past work for each problem class. The experiments are well documented and seem reasonably expansive. * **Interesting connection**: I'm more familiar with the SPO literature, so the connection of learned surrogates to MINLP is quite interesting!

Weaknesses

The major weakness of this paper, imo, is that it doesn't document the **training considerations** for $\mathcal{M}_w$. The paper mentions in the conclusions that 'one potential drawback is the complexity of tuning M, requiring model selection and training', but there are no experiments about how hard/important tuning these parameters is. Specifically, it would be good to know: 1. Shah et al. [36] highlight the importance of *convex* surrogates for learning loss functions (because they have to be optimized over) and show specifically on a version of the Portfolio Optimization domain that neural networks performs poorly (Table 1 in their paper). However, in this paper $\mathcal{M}_w$ seems to be a neural network and performs well? Do you not observe this phenomenon of 'convexity being important for loss functions'? 1. There seems to be a recent follow up to [36] --> [A] which seems to do 1 iteration of your alternating update (with a 2-stage warm start) and seems to do well on the Portfolio Optimization domain, even better than the MDFL method (which seems to do much better than both LODLs and LANCER in this paper). Then: * How robust are your results to hyperparameter choices? * How important is it to perform repeated updates? (Is this what you mean by "epoch" in Figure 5? And if so, how much difference is there between 1 epoch with 10x the samples vs. 10 epochs with 1x the samples?) * Relatedly, how do those results change based on how good the initial guess of $\theta$ is? Do you need fewer updates if you warm-start $\theta$ from a 2-stage solution? 1. Why do you measure cost in terms of the number of calls to the BB optimizer in Figure 5? There seems to be a trade-off between (a) using more calls the BB optimizer but training a simple model (as in LODLs) vs. (b) using fewer calls to the BB optimizer but training a more complex model. Do the results look very different if you use wall-clock time? _References:_ [A] Shah S, Perrault A, Wilder B, Tambe M. Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize. arXiv preprint arXiv:2305.16830. 2023 May 26.

Questions

Apart from the questions in the weaknesses in the section above, I was wondering: 1. **Choice of domains**: I noticed that you have not used the domains from either SurCO or LODLs on which they report good performance. While this is not a weakness in itself, I can't help but wonder how well LANCER performs on those domains. Should LANCER always be the choice of learning method or is the answer more nuanced? 1. **Alternating updates**: Is it important to always do full updates in both spaces? Have you considered, perhaps, doing smaller updates? For example, in a recent paper, [B] seems to do some sort of meta-gradient update based on how $\theta$ would change in response to $w$. 1. **Re-using $\mathcal{M}_w$**: The fact that landscape surrogates can be 're-used' seems to suggest that $\mathcal{M}_w$ is learning something that is common across problem instances. Have you tried to analyze what it is that $\mathcal{M}_w$ is learning? From the experiments, I'm convinced that there exist reasonable domains for which its possible to get this method to work. However, it's not clear at the moment how easy this process is... I'm willing to raise my score to a 7 if the authors provide more detailed answers to the questions in the weaknesses section _References:_ [B] Sivasubramanian, Durga, et al. "Adaptive Mixing of Auxiliary Losses in Supervised Learning." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 8. 2023.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

I appreciate the inherent conflict of interest, but I think the paper could do a better job of documenting the limitations of their approach. For example, if the authors could answer (1) from the questions section above, that would help to better contextualize the advantages and limitations of this approach.

Summary

This paper presents a unified framework for "predict-then-optimize" and surrogate cost learning for Mixed Integer Nonlinear Programming (MINLP). These problems are cast as learning an optimizer g with f as the objective. Current solutions either suffer from scalability issues or the sparse gradient problem. To overcome these, the authors propose learning a smooth and tractable landscape surrogate to replace the compound function $f\circ g$. A neural network parameterizes the surrogate loss and it is learned through alternating optimization. This is done by alternately optimizing the target model c and landscape surrogate $\mathcal{M}$ in a manner similar to Generative Adversarial Networks (GANs). Experiments covering both linear and non-linear objectives demonstrate the efficacy of the proposed method under both "predict-then-optimize" and surrogate learning settings.

Strengths

The paper proposes the first unified framework for "predict-then-optimize" and surrogate learning. The method is straightforward, and empirical results appear promising in terms of both optimization performance and runtime.

Weaknesses

Directly utilizing a neural network to parameterize the landscape may not be a good idea. The complexity of a neural network typically surpasses the original objective f. A neural network can have extremely large number of local minimums and this approach could disrupt the convexity of the original optimization problem, leading to instability in the proposed method's learning procedure. In fact, in Shah et al., several parameterizations, including neural networks, were tested and found to often result in catastrophic outcomes. There's concern about this parameterization across various optimization objectives. While SurCo minimizes the original objective f, LANCER learns an additional surrogate loss. However, in experiment 5.2.2, LANCER significantly outperforms SurCo. The authors should provide more analysis and clarification on why employing such a surrogate loss can surpass the original loss. The paper lacks important implementation details. In 4.1, the authors mentioned the possibility of executing the theta-step during testing since c_{\theta} is available for unseen test data. It is unclear if this step was used during testing in the experiments. The supplementary material also does not provide details about the number of training iterations for this theta-step during testing. If this additional optimization step was used during testing, performance without this step should also be reported to pinpoint the source of the gains compared to SurCo. In fact, SurCo can also have this extra optimization step for the unseen test data. Furthermore, the paper does not provide any implementation details for the replay buffer trick discussed in 4.2, such as the number of points needed to be stored, which could significantly impact the training time. The unification of the "predict+optimization" problem and surrogate cost learning problem under optimization with partial information feels forced as half of the paper focuses on surrogate objective learning for MINLP where full information is available. Section 4 could benefit from restructuring. The main introduction of the proposed method precedes 4.1 and 4.2 and lacks a subsection title, while 4.1 and 4.2 focus on implementation details. Minor: Line 285: MDFL was proposed for combinatorial decision-focused learning and it is not the first DFL paper. A more accurate citation should be Donti et al. (2017).

Questions

Have different parameterizations of \mathcal{M} been tested and do they significantly affect performance? In 4.1, the paper said we can execute the theta-step at testing time since c_{\theta} for unseen test data. Did you try this step in your experiment? I did not find the number of training iterations of this theta-step at testing time in the supplementarial material. Was the replay buffer trick, as described in 4.2, used and how many points were needed to be stored? This could significantly impact training time but no implementation details are given in the experimental section or the supplementary material.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

Please refer to the Weaknesses section for a detailed discussion of the paper's limitations.

Summary

`This paper is concerned with an amortized optimization scheme for challenging variants of canonical decision problems such as MINLPs and nonlinear portfolio selection. The authors propose a method with two components, a target mapping $c_\theta$ that maps partially observed problem descriptions $\mathbf y$ to full descriptions $\mathbf z$ that are passed to a traditional solver $g$ (e.g. an MILP solver), and a landscape estimator $M_w$ (i.e. a value function) that estimates the objective value attained by $g(c_\theta(\mathbf y))$ w.r.t. some distribution of training instances. Together $g(c_\theta(\mathbf y))$ can be seen as a policy mapping problem descriptions to optimal decisions. This is an empirical paper, with proof of concept results on several variants of canonical decision problems.

Strengths

Amortized optimization is a common technique across machine learning. For example, LANCER bears striking similarity to actor-critic methods for RL, which amortizes the evaluation of an actor (i.e. policy) $\pi_\theta$ into a critic (i.e. value estimate) $Q_w$, and likewise the policy amortizes the optimization problem $a^*(s) = \mathrm{argmax}_a Q_w(s, a)$. The main difference is the objective value in RL (i.e. the policy returns) are not directly observed, and so $Q_w$ is trained by fitted Q-iteration (i.e. the Bellman backup operator) instead of a supervised loss as proposed in this paper. While the technique proposed in this paper is not new, it is the first time I have seen it combined with traditional optimization solvers like MILPs, which are very underutilized by the ML community. Hence the concept of the paper is very intuitive, and has as much if not more potential for impact than RL papers, which are routinely published in NeurIPS proceedings but as yet have not appeared to have significant impact on industrial optimization problems.

Weaknesses

Like many other solutions to bilevel optimization problems (including actor-critic algorithms), LANCER is not guaranteed to converge w.r.t. $\mathbf w$ or $\mathbf \theta$. Although it is not discussed in the paper, I suspect that LANCER is likely unstable if the hyperparameters are not chosen carefully. If this is not the case, please provide evidence in the rebuttal. The connections to other amortized optimization methods in ML generally is not a weakness in my opinion, however I think the related work and discussion could be greatly improved by placing this work in context with other methods like actor-critic RL algorithms and amortized Bayesian inference algorithms to name a few.

Questions

- How sensitive is LANCER to hyperparameters in terms of performance and stability? - Do you think it may be necessary to regularize $c_\theta$ to better explore the space of possible target mappings (similar to entropy-regularized policies in RL e.g. soft actor-critic)?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

- While LANCER appears more sample efficient in terms of black-box sample efficiency is does seem a bit slower than the baselines (although it does find better solutions). Hence in latency-sensitive applications it may not be the best choice - Like Offline RL the generalization of LANCER to unseen problems will depend heavily on the support of that particular problem configuration in the training set. For out-of-distribution problems LANCER's performance is likely greatly diminished. Determining LANCER's sensitivity to distribution shift is an interesting research question.

Rebuttal

I read the rebuttal. I believe the formalization is probably correct this time. I will check further. There are a lot of mistakes and unclear statements in this paper, as seen in the rebuttal. But I believe that the algorithm is interesting.

Acknowledgement

Thanks for the thorough response! While there are areas for improvement that could likely increase the impact of the paper, I remain very supportive of acceptance. I'm very happy to see that your method does not appear too sensitive to hyperparameters. I really believe the practical impact of this paper could be significant. After reading some of the responses from the other reviewers, I think a challenge you are facing is the way new methods are tend to be held to a bit of a double standard compared to existing methods. Virtually all the criticisms you are facing also apply to every deep RL paper, and yet dozens of RL papers are happily accepted to major ML conferences every year. As you reflect on the relationship of your work to the field of ML as a whole you may find this tutorial on amortized optimization [1] provides a helpful perspective. You cite other papers by the same author several times in your paper so you may already be aware of it. In any case, I hope you find the exercise productive. My comment on the runtime of Lancer was primarily based on Figure 4, which seems to indicate LANCER has the longest runtime of the methods considered. How do you explain this apparent inconsistency? [1] Amos, Brandon. "Tutorial on amortized optimization." Foundations and Trends® in Machine Learning 16.5 (2023): 592-732. https://arxiv.org/abs/2202.00665

Response to Rebuttal

Thank you for the clarifications. I'm not convinced that the landscape surrogate is doing anything significantly different from other surrogate losses at a high-level (as long as $\mathbf{g^*}$ in LODLs and $\mathbf{g}$ in this paper are the same), but at the same time I think this paper addresses some key shortcomings of learning surrogate losses (sample efficiency and heuristic sampling). The experiments are quite thorough and seem to clearly show that the proposed improvements improve on past work. I think this paper is a very useful addition to the literature. I raise my score to 7.

Thanks for the rebuttal

Thanks for the detailed clarification. I have also read other reviewers. I will adjust my score accordingly.