Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims to solve combinatorial optimization problems with unknown parameters that need to be predicted from observations. It proposed a total group preorder loss and its differential version approximated total group preorder loss for predict-then-optimize (PTO) problems with strong ranking property. It studied a very interesting problem. 
main_review: My main comments are listed as follows:

1.	Regarding Definition 1 (Total group preorder): TGP© defines all pairs that satisfy the priority order with parameter c. The definition makes sense for the ranking problem. However, how does this definition fit into the shortest path/knapsack problem? That is, most combinatorial problems are constrained, then how to consider this group preorder? If we consider one feasible path as an element, then the number of elements increases exponentially. This is related to the comment below Definition 3. How can the curse of dimensionality be avoided?

2.	More details are needed for Algorithm 1: 
a.	What is the intuition behind Equation (6) and (7)? 
b.	Are there any connections between these two equations? Under what circumstances should Equation (6) be applied? 
c.	What is CLIP in Equation (7)? 
d.	In Section 4.1, how to determine D (the number of DoG filters used)? 
e.	How to choose \gamma and \sigma? How is \sigma related to the problem itself?

3.	How to avoid the overfitting problem in the TGP/ATGP framework?

4.	In the numerical experiments, Table 1 reports the SPO losses with baseline algorithms on the three PTO problem. Could you also report the computational time for different algorithms?

Minor: 

1.	In the proof of Lemma 1, “.” is missing in the last sentence.

2.	In the proof of Theorem 1, to make the notation consistent, I suggest to use A_{i,:} to denote its i-th row.

3.	In the proof of Theorem 1, change the notation for loss function $l$ to $\ell$;

4.	I am a bit confused by the proof of Lemma 2: the first term of X\hat{H}^{l_2} is XX^+ C^*. From the derivation, it gets that XX^+ C^* = XH^*=C^*, which implies that P_X C^* = C^*. If C^* is full rank, then P_X= I. Is it a reasonable conclusion? Why?

5.	The proof of Lemma 3 seems not rigorous. Could you use mathematical equation to prove this conclusion?


summary_of_the_review: Overall, this is an interesting paper. It may help to understand the paper if adding one or two examples other than ranking (constrained optimization problems such as shortest path/knapsack in the modeling section), to illustrate how the new notion of total group preorder and algorithm can be applied. The proofs need to be written in a clearer way.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors propose a novel loss function called the approximated total group preorder (ATGP) loss function, which aims to address the potential limitations of l2 loss in predict-then-optimize (PTO) problems.
The authors argue that the use of l2 loss in the prediction phase is "misaligned" with the final goal when the ultimate objective is to make discrete decisions in a combinatorial optimization setting.
While the so-called SPO (smart PTO) loss, recently proposed by Elmachtoub and Grigas (2021) provides a remedy, the authors note that it cannot be used with gradient-based learning algorithms.
The authors aim to rectify this issue by proposing a novel loss function called the total group preorder (TGP) loss - for better alignment - and then an algorithm for automatically searching for an approximate TGP (ATGP) loss function so that it is differentiable and therefore can take advantage of efficient gradient-based learning schemes.
main_review: Overall, the paper is well-written.
The proposed ideas are reasonable and they are presented in a logical manner.
Performance evaluation based on three examples - energy cost-aware scheduling based on historical energy price data, portfolio optimization based on SP500 data, and shortest path finding in Twitter ego network - demonstrate that the proposed ATGP loss and the APOC  (Automatic Prediction and Optimization Connector) algorithm may have potential advantages over other loss functions and algorithms.

One major concern regarding the paper is that the authors do not consider the rich literature on optimal decision making - especially, decision making under uncertainty - that has a very long history in operations research and other fields.
For example, the SPO loss shown on page 3 is conceptually identical to what is known as "regret" in decision theory.
Regret estimates the expected performance loss due to using a suboptimal predictor (or operator) instead of the optimal predictor (or operator), typically due to the fact that the true model parameters or the optimal predictor/operator are unknown (e.g., due to aleatoric and/or epistemic uncertainties).

Furthermore, if the predictor (or operator) is optimized to minimize the regret (or the SPO loss shown on page 3) over a class of possible predictors/operators, that leads to the so-called MOCU (mean objective cost of uncertainty) that quantifies the operational cost induced by model uncertainties.
Both regret and MOCU have been widely studied in problems such as optimal decision making, optimal experimental design, and active learning - especially in the presence of uncertainty.
However, the authors, unfortunately, do not discuss the relation of the presented work with the existing studies based on regret or MOCU.

Another concern is the limited performance validation of the proposed approach presented in the current paper.
For example, it is unclear whether the ablation study in Figure 4 clearly shows the advantage of the DoG wavelet for automatic search of ATGP, as the improvement does not seem to be significant when compared to the fully-connected network.
The results in Table 1 also show that the performance of the ATGP via APOC significantly depends on the choice of the optimization scheme (e.g., REINFORCE vs PPO2), since in most cases, not both schemes outperform the other alternatives.

Additional performance assessment results are needed to further validate the advantages of the proposed scheme and the above points should be clearly discussed with mentions about the potential limitations of the current method.

summary_of_the_review: The paper deals with an interesting problem and the proposed method is well-motivated and presented in a logical manner.
The experimental results based on three different datasets show that the proposed method may have potential advantages over other existing schemes.
However, despite the conceptual similarity between SPO loss (which the TGP/ATGP tried to improve) and regret/MOCU in decision theory, the authors do not discuss the relation of their work to the rich existing literature on regret and MOCU.
Furthermore, additional performance evaluation results are needed to clearly demonstrate the robustness and benefits of the proposed scheme.
Including discussions on potential limitations of the current method (if any) would strengthen the paper.

---

The evaluation has been updated after reviewing the authors' response.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies a problem where the goal is to solve an optimization problem, but key parameters of the optimization problem (like a road network’s edge weights) are unknown and can only be predicted from historical data. This line of research is called “predict then optimize.” For the prediction step, the first thing one might try would be to minimize a standard loss function like the l2 loss, but this loss function may not necessarily lead the downstream optimization problem to return the highest quality solutions. This paper studies a way to learn a good loss function for the downstream optimization problem at hand.

To give an example, if the optimization problem is to rank a set of elements, even if one can predict the elements’ values with low l2-error, the resulting ranking might be totally incorrect.
Motivated by this example, this paper’s results apply to combinatorial optimization problems that satisfy a “strong ranking property,” which essentially means that the optimization problem’s solution only depends on group-wise comparisons of the problem’s parameters (rather than on the specific values of the parameters themselves).

Let $c \in R^d$ be the true parameters and $\hat{c}$ be the learned parameters. The authors propose that the loss function one should optimize should ideally have the form $||sign(L\hat{c}) - sign(Lc)||$, where $L$ is a matrix of size ${2^d \choose 2} \times d$ that allows for all $2^d \choose 2$ group-wise comparisons between all groups of parameters. Since this ideal loss function is computationally intractable, the authors propose replace $sign$ with $\tanh$. Then, they propose fixing the number of rows of $L$ and parameterizing the matrix using a set of discretized Derivative-of-Gaussian filters, which they optimize using the reinforcement learning algorithm REINFORCE [Williams ‘92] (the details here are a bit unclear to me).

They evaluate their algorithm for three problems: a scheduling problem, portfolio optimization, and shortest path. They compare against a number of different predict-then-optimize algorithms from prior research and show that their algorithm has much better losses on the problems studied.
main_review: Here are some of the paper’s strengths and weaknesses:

(+) I thought that the motivation and the illustration with Figure 2 was compelling. Combinatorial optimization problems can be very sensitive: perturbing the problem’s parameters by just a little bit can cause the solution to change by a lot. Therefore, naively optimizing a standard loss function to predict the problem’s parameters can lead to poor downstream results for the optimization task.

(+/-) I think that the “strong ranking property” is promising, but it could be fleshed out. When it is first described in Section 1, it’s very abstract and hard to grasp what it means. The ranking example in Section 3.1 helps, but I think that it comes too late. Moreover, it’s never really explained why certain combinatorial problems have this property, so the reader has to trust that it’s a useful property and that the problems in the experiments section satisfy the property. A few fleshed-out examples and explanations would be helpful.

(-) The theoretical results leave something to be desired, since they show that for a very specific example, optimizing using the proposed approach is weakly better than optimizing using the l2 loss. This would, of course, be more compelling if the authors could provide an example where the proposed approach is better than using the l2 loss by some non-zero margin.

(-) The applied approach to representing $L$ using discretized Derivative-of-Gaussian filters seemed a bit ad hoc and I didn’t really understand the deeper intuition behind why this might be a good approach.

More detailed comments:
- Figure 2: It was a little hard to tell where the stars and triangles lie on the x-y axes.
- Definition 3: At first, it was a bit hard to grasp what L is supposed to represent. Maybe this could be explained earlier, and with an example.
- Equation (3): Should sign be tanh?
summary_of_the_review: Overall, my recommendation is “weak accept” because I think the motivation is compelling and the “strong ranking property” seems to open up this predict-then-optimize framework to important combinatorial optimization problems (though I’m not very familiar with prior research on this specific topic). As I mentioned in the main review, there are a lot of ways the paper could be fleshed out to increase it’s potential impact.
review_title: null

Meta-review: This paper studies the problem called "Predict, then Optimize (PTO)", where the goal is to predict some unknown parameters in the objective function and then optimize the function. The paper focus on special case of PTO where the goal is to learn the unknown parameters corresponding to some combinatorial ordering of the data. The paper argues that traditional methods which perform the ranking after minimizing the objective can be very unstable, and proposes a new alternative loss called ATGP loss. The goal of the loss is to ensure that the total group preorder of the learned solution is as consistent with the observation as possible after fitting the data. 

The paper shows some property of the new loss and claims that it can be better than naive regression then ranking approach on learning to rank with linear regression problem, however, the theorem only shows that the robustness bar of TGP loss is larger or EQUAL to that of the naive approach, not exactly higher -- Thus, such an argument is not really convincing.  The authors also proposed a heuristic algorithm to minimize a smoothed version of the proposed loss. 

However, the proposed objective is still interesting on its own, and the experimental result looks promising. Thus, this paper is a borderline accept paper at this conference.
Decision: Accept (Poster)