Predict-then-Optimize via Learning to Optimize from Features

We thank the reviewer for their review.

"I don’t think the LtOF approach can handle the issue of distribution shift."

The reviewer may have missed the main point in our description of the distribution shift, which specifically refers to a divergence between the training distribution of problem parameters for the LtO proxy, and the inputs encountered by the proxy as parametric predictions during subsequent training of the EPO model. We are not concerned, in this work, about a shift in the distribution of input features to the final prediction model, as studied e.g. in domain adaptation.

Recall that the distributional shift is not measured directly, but rather by its effect on the accuracy of the downstream solutions (regret). What ultimately matters in PtO is the regret incurred by downstream decisions. The fact that our LtOF implementations soundly outperform the two-stage baseline models, and are competitive with EPO models, shows in itself that the distributional shift issue has been effectively handled. The concept behind this is to close the loop between optimization proxy training and EPO prediction training. Since there are no longer two separate training processes, there can be no distributional shift between them to speak of.

"In fact, EPO can handle nonconvex optimization objectives by locally approximating..."

We appreciate the references provided on this point. We agree that it may be the case that some form of convex EPO adaptation could be constructed to provide another baseline for the nonconvex experiments. However, there is some subtlety and we disagree with the assertion that nonconvex problems in general admit useful convex approximations for EPO training.

For example the first cited work provided by the reviewer (Perrault) uses a convex QP approximation to the nonconvex model at its optimal point as an EPO surrogate. This technique is situational, and does not apply in general. If the objective Hessian is not positive semidefinite, the QP approximation will not be convex. As an example, consider PtO with a nonconvex QP as its optimization component; its Hessian is constant and non-Positive Semidefinite. So it does not admit a convex QP approximation anywhere. Also, it seems clear that our AC-OPF problem, with nonconvex constraints and linear objective, would not produce a useful differentiable QP surrogate. For one, it would be an LP (the Hessian is zero), which is known to be non-differentiable wrt the predicted objective coefficients. The citations to Amos 2017 and Agrawal 2019 also do not provide any evidence that a convex surrogate technique should work in general for nonconvex PtO.

While reasonable EPO alternatives have been contrived for some nonconvex models, it has not been systematically shown that there is a reliable method for doing so in general. So we disagree with the assumption that such techniques obviously exist, and need to be evaluated as baselines.

"Synthetic Datasets"

We incorporated real-world data from Nasdaq to populate the parameter dataset $\zeta$ of the first experiment, but we make clear in the paper that the underlying features $z$ are all generated synthetically. This is because synthetic data allows us to make a stronger evaluation by controlling the complexity of the feature mapping from $z$ to $\zeta$. By showing that LtOF outperforms the twostage methods to an increasing degree as the feature complexity increases, and is competitive with EPO where available, we can give stronger evidence that LtOF has an advantage in mitigating error propagation from parametric predictions to downstream decisions. The original "Smart Predict Then Optimize" of Elmachtoub 2017 uses synthetic data for both features and parameters, for the same reason. In contrast, several works use the "Warcraft Shortest Path" benchmark to make a visually appealing baseline, but in practice the ResNet feature extractor leads to very good two-stage performance, which does not allow for the advantage of the EPO methods to be fully expressed.

We thank the reviewer for their thoughtful and balanced feedback on the paper. The reviewers' suggestions about local approximation seem reasonable and may help inform future improvements to the paper.

Responding to one point:

Differentiating the KKT points in nonconvex optimization does sound like a reasonable suggestion to pursue for a baseline result, in principle. At the same time, several factors make it difficult to test, including that this method would be predicated on finding the globally optimal solution to a nonconvex problem, for each sample at each iteration of training, which makes the practicality of the experiment questionable. Together with the fact that such an approach hasn't been shown to work reliably in general, to the point that it is well-accepted as an effective solution for nonconvex PtO (it could reasonably doubted; gradients don't always coincide with descent directions in the nonconvex case), we think it's not quite appropriate that such a baseline be required.

We thank the reviewer for their review.

This idea seems simple to think of. What is the contribution of the paper?

The contribution of the paper is to show that by adapting Learning to Optimize methods to the Predict-Then-Optimize domain, we introduce an entirely new approach to PtO, which leads to high-accuracy solutions while retaining the benefits of LtO including increased speed and adaptability to various problem forms.

The fact that this can be done efficiently and without access to the typical toolset including optimization solvers or their derivatives, has not been demonstrated before and is of interest to many in the community. We are glad that the paper's presentation makes the idea seem "simple to think of". The reviewer should have to explain why this should be grounds for rejecting the paper. The work is novel.

A proper solution to the distribution shift issue would use a pretrained proxy.

We do not understand this critique. What would be the point of using a pretrained proxy, if the distributional shift issue can be circumvented by jointly training the proxy?

There is no rigorous mathematical analysis.

A rigorous mathematical analysis would not be appropriate for the contribution of this paper. It describes a generic framework, and any particular analysis would depend on the LtO training method used. As such we support the paper's proposed framework by experimentally evaluating over several distinct LtO methods to show its general effectiveness. The LtO methods, in general, are also rarely supported by rigorous proofs and related papers tend not to focus on this aspect. We are not trying to make a contribution in the LtO domain.

"It suffers from the training cost because of getting various training samples..."

This is not true. It's important for the reviewers to note this: two out of three of our LtOF implementations (DC3 and PDL) are completely self-supervised and do not require precomputation of optimal solutions for their training sets. Please also see our response to Reviewer Q2Xf as it pertains to training set generation in their cited works [1],[2],and [3]. Those works all rely on precomputation of optimal solutions and require generating a plurality of surrogate training sets to support the overall training process. Our proposal is capable of avoiding this pitfall by self-supervised end-to-end learning of the prediction and proxy optimization components. We hope that understanding our contribution within this context can help the reviewer see why it is interesting and relevant.

Is there any further discussion? Any new variant of LtO for this?

The effectiveness of the framework in solving PtO problems is ultimately what matters. A "new variant" of Learning-to-Optimize is not needed to achieve this; we demonstrate the effectiveness of adapting several already-existing variants. This is the point of the paper: a whole new class of methods can be adapted to this PtO problem setting. Such suggestions seem to be focusing more on the appearance of the contribution being too simple, rather than the novelty and effectiveness of the contribution on the important problem which it solves.

The contribution has been made clear. Predict-Then-Optimize learning has primarily been based on modeling derivatives through optimization problems or the associated regret functions. By identifying a way to adapt existing LtO methods to this problem setting, the paper shows a way to accomplish the same task with high performance without using such derivatives at all. This change in perspective, among other advantages, brings with it a natural way to handle complex problems with nonconvex constraints in PtO, which was previously challenging.

Responding to:

"The way that LtO is used in the proposed approach is hardly novel.": This is a factual claim that's not appropriate in an open review without providing references to support it. Why not provide a reference to show where it has already been done?

"Training the proxy for the distribution of $\hat{\zeta}$ might free it from the distribution shift issue even not using LtOF.": This assumes the existence of a known distribution over $\hat{\zeta}$ on which to train. Finding a model which maps distribution $z$ to $\hat{\zeta}$ in a way that minimizes regret is the PtO problem itself. If this exists then the problem is already solved.

The main critique of this review seems to be that the paper is not novel because it combines existing frameworks in a way that "seems simple". But combining them in a new way, leading to new practical advantages, is by definition novel. This manner of critique is only possible in the absence of any discussion of the proposal's demonstrated advantages.

We appreciate that the reviewer points out the difficulty of the task which requires satisfaction of difficult, nonconvex constraints, and the novelty of the paper's solution which accomplishes this without access to optimization solvers or their derivatives.

"The contribution is kind of slight / the paper makes it seem straightforward."

The main idea is indeed straightforward in a way, and the paper is written to emphasize the important but widely unrecognized connection between Predict-Then-Optimize and Learning-to-Optimize. This insight, like many things, is only "obvious" once it has been explained and demonstrated. Ours is the first to demonstrate this connection, and evaluate the practical performance and potential advantages of adapting LtO in this way. Many in the community would be interested to see this connection illustrated and systematically evaluated.

"The EPO baselines do not seem strong."

The EPO baselines are correctly implemented. The hyperparameter tuning is described in the Appendix D. Figure 4 shows that each EPO baseline outperforms twostage method, for each feature mapping complexity $k$. The one exception is that best EPO is indeed outperformed by the best two-stage on k=1, but this is normal and shows the evaluations are correctly implemented. EPO approaches are only expected to outperform when the feature mapping is sufficiently complex. Otherwise the parametric predictions are so easy to learn that the two-stage can reach almost zero error. For k=1, the feature mapping is linear.

"More detail about the LtO methods and constraint violations."

First, please notice the extended Related Work section in Appendix B, which gives more details about the LtO methods which we adapted in the paper. Also, it's important to remember that not all LtO methods are prone to constraint violations, so the issue does not affect LtOF in the most general case. However, the methods we evaluate in the paper are indeed prone to small constraint violations. The fact that projections must be hand-crafted in such situations is indeed a good point. On the other hand, projections are typically not nearly as difficult to implement as full optimization solvers or their derivatives. Also note that feasibility corrections are not always required; these methods allow for some parameter tuning, which can be used to reduce violations to zero, generally at some cost to optimality. For example, for LD and PDL the lagrange multiplier stepsizes can generally be increased past a threshold where constraint violations disappear. Also notice that in two of three experiments, DC3 incurs no violations in the first place and does not require a correction. On the other hand its regret post-correction is generally not as low as that of the other LtO methods.

We appreciate the reviewer's references to related works [1],[2], and [3]. We respond to their main critiques below.

"The paper is not novel/interesting in light of related works (cited)."

We first point out that existence of recent work in the area shows that the community is indeed interested in this research direction (PtO with optimization surrogates). Alternative approaches such as ours should also be accommodated, especially since each of the existing works cited by the reviewer has its own drawbacks, which we will partially summarize below.

Reference [4] cited by the reviewer is not based on surrogate learning, and is not comparable to our paper in its aims or approach. Of the remaining three works [1], [2], [3] advocated by the reviewer, [3] is not yet published, and [2] was just announced as accepted in NeurIPS. The fact that these works are yet unpublished or brand new, means that our paper should be considered as concurrent work. We will cite these works in the updated article, but to state that our paper is not novel or interesting in light of these works, and advocate rejection on that basis, is unfair.

It's also important to point out the differences in our proposal from the goals shared by [1],[2],[3]. Those works focus on learning surrogate loss functions for use in EPO training, in which the end product is a predictor of $\zeta$. Ours learns a joint prediction and optimization model. Our learned model functions like an LtO proxy, and outputs full optimal solutions directly. The main thing shared in common among ours and [1],[2],[3] seems to be the goal of training PtO without optimization in-the-loop.

It is important for all to note that our paper has relevance in light of the drawbacks of [3]. That paper tries to learn a surrogate loss function for PtO, which is then used in subsequent EPO training, free of optimization. Since that learned surrogate loss function is only valid on its training distributions, the method of [3] is also subject to the Distributional Shift effect discussed in our paper. As described in Section 6 of its ArXiv version, the paper [3] copes with the distributional shift effect by running many, differently parametrized mock training routines in parallel, from which predictions are sampled throughout training, and saved to later train the global surrogate loss function. Since there is no way to ensure that the resulting training set will produce a good surrogate loss, the paper [3] relies on a brute force method of guessing and testing surrogate losses trained by data sourced from the various mock training runs, which is waved away as a "hyperparameter" search, until good end task performance is found. The published paper [1], which is a prequel to [3], proposes to cope with the distributional shift by requiring to train a different "local surrogate loss" for each sample of each training set. Both are inefficient designs especially given that they require precomputation of optimal solutions over each training set made in the overall process (as detailed in Section 5 Paragraph 1 of [3]).

Our paper is particularly relevant in light of these drawbacks, because it explicitly demonstrates the distributional shift issue between surrogate training and EPO training, and tackles this problem directly by closing the loop between optimization surrogate and EPO prediction models using end-to-end learning. This allows the method to avoid resorting to "fine-tuning" the entire training set as suggested by the reviewer. The reviewer suggests that failing to pursue such an approach is a drawback of our paper, but it is not at all clear that any principled approach to surrogate-based EPO can be built upon such a concept. We use optimization rather than hyperparameter search to deal with the distributional shift, and the self-supervised variants shown in our paper are efficiently trainable without precomputation of training sets of optimal solutions. This is an important advantage which the reviewer does not recognize.

The works [1],[2],[3] may have good merit within their scope and may each offer certain advantages. There is room in the literature for all these different approaches. But the reviewer holds that those approaches are considered "novel/interesting" while ours is not. The reviewer should clarify the choice to reject on those grounds.

[1/2]

We'll give our response point-wise as well:

1. Benchmarking Against LODLs ([1]): We make no claim that [1] is concurrent work, it is surely prior. Our main point is that in light of its own admitted drawbacks, and since it is not directly comparable to LtOF in its goals (we learn optimizers and not loss functions, the advantages are different) makes it unreasonable to reject a paper based on failure to benchmark against it. Even [3], which has the same first author as [1], critiques the inefficient approach of [1], which requires the user to train entirely separate local surrogate loss functions for $**each sample**$ of the master training set. While [1] may have practical merit, it is not a stretch to call this a brute-force method. Computational resources are expensive, and this method [1] cannot be a required baseline for all surrogate learning proposals going forward.

2. "We tried several things that did not work": In the response above it's mentioned that we specifically tried iterative retraining of the proxy based on out-of-distribution samples collected in prior training. It didn't yield any positive result, so there is no clear reason to document this in the paper. There is also no clear conceptual reason why it should work in the first place, so inclusion of such a thing in our paper would be out of place. Yet the reviewer states failure to include such results as a main reason for maintaining their score (see point (b) above).

3. The fact that we demonstrate a method that beats the only accepted baseline (two-stage) on nonconvex problems is therefore clearly valuable as a contribution of our paper. No valid convex differentiable approximation of the AC-OPF problem has yet been suggested in this review, yet failure to benchmark against it is still used to justify rejection.

4. It's ok, thank you for the correction.

Note that the reviewer still insists on the baselines suggested by rTig, but we have explained in our response to rTig why this cannot work on our AC-OPF example. Their suggested convex QP approximation is not even differentiable in our case (it has zero Hessian).

The reviewer concludes above that the main drawbacks of the paper are failure to benchmark against nonconvex surrogates, LODLs ([1]), and an unspecified "LtO + heuristics to mitigate distribution shift". We believe that our response here shows that none of those critiques are reasonable. We have directly refuted the existence of a differentiable convex QP surrogate to evaluate as a baseline for nonconvex AC-OPF, and it's not even specified what "heuristics" are being asked for. The issue with LODLs is addressed above. To maintain a score of 3 on such grounds does seems unjustified.

It seems clear that we have incorporated an effective solution to the distributional shift issue, which is interesting and novel in context of the reviewer's cited works, and yields practical advantages, but this fact is still not really acknowledged. It's also not refuted.

In particular, could you please respond to the following questions:

• Would you agree that the works [1],[2],[3] all face a very similar distributional shift issue as in our paper, and propose to mitigate the issue in different ways?
• The solution proposed in [1] is inefficient to the degree that a follow-up paper [3] was warranted, implying that surrogate learning in PtO is still an open problem. Is that fair to say?
• You confidently suggest that "fine-tuning" the dataset is an obvious solution to the distributional shift issue, to the degree that our pre-trained proxy EPO is characterized as a Strawman. This is because that is the solution proposed in [3]. Is that correct?
• We point out that the "fine-tuning" approach of [3] essentially mitigates the distributional shift effect by hyperparameterization of the entire data generation process of the surrogate's training routine. Meaning that entire training sets must be generated for the surrogate loss in a guess-and-test manner, until good performance on the end task is found. Is it fair to say that there is still room for improvement in this aspect, for future work?
• Your critique does not address the core contribution of the paper, which is to identify the distributional shift as the main impediment to surrogate learning for PtO, and then mitigate the issue with an end-end learning-to-optimize solution. Would you please give an explanation of why our solution is not "novel/interesting" in context of the proposed solutions in [1] and [3], given your close familiarity with those works?

"The paper does not compare against EPO with pretrained proxy."

This is not correct, please see Table 2 which lists the regret incurred by EPO training with pretrained proxy, also referenced in the distributional shift discussion of Section 3 Page 4. As for the suggestion that the distributional shift can be alleviated by "fine tuning" the training set: we tried several such things which did not work, including iteratively retraining the proxy with out-of-distribution samples encountered in EPO training. There is no reliable way to anticipate the parametric predictions encountered during EPO training and use them to pretrain the LtO proxy in advance. Cited work [3] attempts something similar and resorts to inefficient "hyperparameterization" of the entire dataset generation to get good results as explained above. There is no "straw man" here.

"Two out of three experiments do not use reasonable baselines."

The reviewer refers to the experiments in which we use nonconvex optimization components. First we point out that two-stage models are universally considered to be standard baselines, especially in the absence of a well-established EPO alternative for nonconvex problems. It is not always easy to beat the two-stage method, and doing so systematically on an array of increasingly complex datasets demonstrates that our method greatly improves error generalization from predictions to downstream decisions. This is the main goal in PtO. Please also see our response to Reviewer rTig with regards to nonconvex EPO alternatives. For problems with nonconvex constraints, there is no well-established EPO alternative such that new papers should be rejected for failing to test against it.

"This suggests that LtOF is not able to learn how to make good decisions."

The reviewer should substantiate this critique. The end regret of the solutions after feasibility restoration is substantially less than one percent in each case, and as low as $0.1$ percent. Why does this prompt the assertion that the model cannot learn good decisions?

"What about interpretability, fairness, etc."

These are tangential issues that distract from a discussion about our paper's core contributions. Same can be said of the remark on optimal planning at test time. These aspects are irrelevant with respect to the canonical PtO problem setting which we are studying. Will the reviewer address any flaws with the core contribution of the paper, specifically our solution to the distributional shift problem in relation the works they cited, or the actual performance of our methods?

[2/2]