Automatic Loss Function Search for Predict-Then-Optimize Problems with Strong Ranking Property
Authors: Boshi Wang
Jialin Yi
Hang Dong
Bo Qiao
Chuan Luo
Qingwei Lin
Venue: ICLR 2022 Poster (2022)

Abstract: Combinatorial optimization problems with parameters to be predicted from side information are commonly seen in a variety of problems during the paradigm shift from reactive decision making to proactive decision making. Due to the misalignment between the continuous prediction results and the discrete decisions in optimization problems, it is hard to achieve a satisfactory prediction result with the ordinary $l_2$ loss in the prediction phase. To properly connect the prediction loss with the optimization goal, in this paper we propose a total group preorder (TGP) loss and its differential version called approximated total group preorder (ATGP) loss for predict-then-optimize (PTO) problems with strong ranking property. These new losses are provably more robust than the usual $l_2$ loss in a linear regression setting and have great potential to extend to other settings. We also propose an automatic searching algorithm that adapts the ATGP loss to PTO problems with different combinatorial structures. Extensive experiments on the ranking problem, the knapsack problem, and the shortest path problem have demonstrated that our proposed method can achieve a significant performance compared to the other methods designed for PTO problems.

Published as a conference paper at ICLR 2022
AUTOMATIC LOss FUNCTION SEARCH FOR SREDICT-THEN-PTIMIE PROBLEMS WITH STRONG RANKING PROPERTY
Boshi W Jialin ;i;; Hang Dong', Bo Qiao", Chuan Luo Qingwei Lin 'The Ohio State University, United States
LLondon School of Economics and Political Science, United Kingdom Microsoft Rescarch, China
wang. 23930@buckeyemail......... w.l...ss.eduu edu, 3.yi88lse.ac. uk, fhangdeng, boqiao, Chuan.luc, glinjemlcrosoft.com com
ABSTRACT
Combinatorial optimization problems with parameters to be predicted from side information are commonly seen in a variety of problems during the paradigm shifts from reactive decision making to proactive decision making. Due to the misalignment between the continuous prediction results and the discrete decisions in optimization problems, it is hard to achieve satisfactory prediction result with the ordinary le loss in the prediction phase. To properly connect the prediction loss with the optimization goal, in this paper we propose total group preorder (TGP) loss and its differential version called approximate total group preorder (ATGP) loss for predict-thennoplee erty. These new losses are provably more robust than the usual I2 loss in a linear regression setting and have great potential to extend to other settings. We also propose automatic searching algorithm that adapts the ATGP loss to PTO prob- lems with different combinatorial structures. Extensive experiments on the rank- ing problem, the knapsack problem, and the shortest path problem have demon- strated that our proposed method can achieve a significantly better performance compared to the other methods designed for PTO problems.
(PTO) problems with strong ranking prop-
INTRODUCTION
Many decision making processes under uncertainty in real world are solving combinatorial prob- lems with parameters unknown to the decision maker. A traditional method to address the uncer- tainty issue to add assumptions Alternatively, a recent approach is to predict the unknown parameters from the correlated features using machine learning methods and solve the combinatorial problems based on the predictions. This paradigm, which is called systematically (Elmachtoub & Grigas) (202I). For example. Google Maps estimates the travel times of roads in the traffic to compute a shortest path [Lau] 2020); Computer clusters predict the process- ing times and resource demands of computation tasks to make good job scheduling on servers (Mao) al. 2016); Hedge funds forecast the return rates of different stocks to optimize their portfolio in the next trading day [Thomson] 2021).
the distributions of parameters (Hentenryck & Bent 2006).
(PTO), has been widely employed in practice
However, the commonly used /2 loss function (i.e., la distance between predictions and true values) usually cannot achieve ideal decision results in predict-then-opiie
problems (Demirović et al. 2019). This misalignment between the loss in prediction and quality of the decision comes from the misalignment between the continuity on the prediction problem and the discontinuity on the structure of the combinatorial optimization problem.
A straightforward remedy of the above misalignment problem is to adjust the loss to reflect the dif- ference in objective values of the optimization solutions generated using the predicted and observed
"Equal contribution. Work done during internship in Microsoft Research Asia. "orresponning authors.

---

Published as a conference paper at ICLR 2022
D1ta
APOC
Contertual
Porimeteciztion
Surrogate
Training
Model Training
Predkiee parammeters
Prediction Evaluation
nnew FTO
Solution
Prodiction
Comberotarial
Mocel
Solver
Figure I: Mechanism of our APOC algorithm.
parameters, called Smart "Predict, then Optimize" (SPO) loss [Elmachtoub & Grigas 2021). How- ).
ever, due to the combinatorial nature of the optimization problems, the SPO loss is usually piecewise flat and has multiple discontinued points. As a result, the derivatives of SPO loss is either zero or nonexistent, which prohibits the training of gradient- solvers for combinatorial optimization problems are not differentiable, which cannot be directly incorporated with the widely adopted gradient- based learning approaches nowadays.
deep learning algorithms. Besides, most
Current approaches to minimizing the SPO loss can be categorized into two classes. The first one is to differentiate the discrete optimization solver by approximating the objective with a certain family of functions, and this series of methods works when the combinatorial optimization problem is linear (Wilder et al.) 2019a by Pogančić et al. 2019). The other class of research tries to propose new surrogate loss functions for SPO loss, e.g., SPO+ loss for linear programming (Elmachtoub & Grigas 2021) and piecewise linear loss for dynamic programming (Stuckey et al., 2020). However, these surrogate loss functions are problem-specine (i.e., depending on the type of the combinatorial optimization problem) and require much domain knowledge from experts to design.
Instead of designing the surrogate loss metric for each optimization problem manually, alternative approach is to find good loss metric from predefined search space in an automatic manner, which inspired by the recent progress in automated machine learning (AutoML) (Zoph Le 2017 Pham
et al. 2018 Liu et al. 2018). These AutoML approaches usually define appropriate search space and then conduct some search algorithms, e.g. reinforcement learning and genetic algorithm, find good metric. [Li et al. (2019) Lid al. (202T) studied the automatic loss function search problem for computer vision tasks. They defined the search space by replacing the mainstream metrics for semantic segmentation with their differentiable approximations. However for pediet-then-optimizz problems, there is no such evaluation metrics available except for SPO loss. Morcover, these metrics, which are designed for segmentation tasks in computer vision domain, not suitable to evaluate the prediction results for the combinatorial optimization problems.
In this paper, propose a framework of automatic loss function search called APOC (Automatic Prediction and Optimization Connector) to tackle a wide range of predict-then-optimie problems whose optimal solution is determined by the total group preorder of the parameters of the combi- natorial problem, called strong ranking property (see for Definition 2 for details.). These problems have the same optimal solution for different sets of parameters, as long as those sets of parameters preserve the same total group preorders. The key idea is to build the proper search space in which different loss functions capture the partial comparisons between different groups of the parameters of the optimization problem.
Our contributions are summarized as follows: We theoretically prove that l2 loss is not an ideal choice in a linear regression setting of PTO problems: 2) We propose the total group preorder loss for PTO problems and relax to a differentiable approximated version, which fitted using a wavelet functions to capture the group comparison relationship
family of among the items with variable sizes and weights; 3) We propose an effective method to automatically search for differentiable surrogate loss based approximated group total preorders of items for PTO problems called APOC; 4) The proposed APOC method has been validated on three classic combinatorial problems with strong ranking property.
RELATED WORK
Predict-hhen-optimize (PTO) problems capture a common pipeline of machine- www.--aaannnnnssisttee optimization solvers: predicting the unknown parameters of the optimization problem from the con-
2

---

Published as a conference paper at ICLR 2022
textual information and then optimizing based on the predicted parameters (Elmachtoub & Grigas 2021). In practice, PTO problems have broad range of real-world applications Lau (2020): Mao
et al. 2016); Thomson (02T): Luo et al. (2020] 202I). However, many combinatorial optimization problems have piecewise flat value function landscapes which prohibit an end-to-end learning with
gradient-based prediction models.
One line of work is to differentiate the optimization solvers for specific problems and embed them as layers into the network architecture through which the gradients can be propagated, which orig- inates from the differentiable optimization (Amos, 2019). Grover et al. (2018) proposes a sorting network for ranking problems by relaxing the permutation matrix output by sorting algorithms to the unimodal row-stochastic matrix. For the node clustering problem, WWilder et al. (2019b) dif- ferentiates the K-means algorithm by assigning nodes to clusters according to soft-min function. Pogančić et al. (2019) interpolates the value of function of linear programming using piecewise linear functions and embeds as layers the solvers of linear programming.
The other line of work focuses on searching for a surrogate loss function approximate the value function the optimization problem, so-called regref in decision theory (Bell 1982). Elmachtoub & Grigas 202T) derives a convex upper bound on the regret of linear programming, called SPO+ loss. Wilder et al. (2199) proposes the QTPL loss by adding a quadratic penalty term to the con- tinuous relaxation of the regret such that results from differentiating over quadratic programs can be used. Mandi & Guns (2020) overcomes the non-differentiablity of the regret by adding a logarith- mic barrier term, called OntOpt. Stuckey et al. (2020) approximates the value function of dynamic programming problems as piecewise linear functions with learn-able parameters. Yoon et al. (2013) proposes mean objective cost of uncertainty (MOCU), the difference between the value functions of a robust solution and the optimal solution, to evaluate the uncertainty of parameters in decision making, e.g., experiment design (Boluki et al. 2018) and active learning (Zhao et al., 202T).
Loss function guides the machine learning algorithms to produce good predictions for different tasks, which is usually designed with domain knowledge from experts (Masnadi-Shiraal & Vas- concelos 2008; Bruch et al. (019). Automatic search of suitable loss function without domain knowledge has recently received much attention from the computer vision community. Li et al. (2019) uses reinforcement learning algorithms to learn better loss functions with good generaliza- tion and transfer-ability on different vision tasks. [Wang et al. (0200) adopts both random search and reinforcement learning algorithms to search for loss functions Li et al.] (202I) explores the possibility of searching loss function automatically from scratch for generic tasks, e-g., semantic segmentation, object detection, and pose estimation. However, the search spaces in these methods are specially designed for vision tasks and cannot be directly applied to PTO problems. Most work on automatic loss search follows the searching algorithms used in AutoML. We refer to He et al. (021) for comprehensive survey on searching methods in AutoML. Natural questions are: 1) whether we can design suitable search space for loss functions in PTO problems; and 2) whether there is a strategy to search adequate loss functions systematically for different optimization problems using techniques from AutoML.
face recognition problems.
ATGP LOSS FOR PREDICT-THEN-OTIIG PROBLEMS
3.1 MISALIGNMENT IN PREDICT-THENS THECCTTTEE--PPIMIZ PROBLEM
The problems we consider are the type of predict-then-optimee (PTO) problems in the following formulation. For an optimization problem in the following form
maximize U²(z)
subject to = E
where z is the decision variable, e E Rdd is the parameter of the objective function U, and Z the feasible set which does not depend on A decision maker needs to solve [ without knowing the exact value c. Instead, the decision maker will observe a feature vector r E IR* The goal of the decision maker is predict the value of and then optimize (I) based on the prediction é. To distinguish with the parameters of the prediction models (e.g., weights of neural networks), we call the PTO parameter.
Instead of focusing on the prediction error between c and é (e.g., 12 distance), the decision maker cares more about high-quality decision result generated from the prediction. |llmachoub & Grigas
3

---

Published as a conference paper at ICLR 2022
30
30
30
20
10
50
60
(a) SPO (blue) vs. la (green).
(b) SPO (blue) vs. TGP (red).
(c) SPO (blue) vs. ATGP (purple).
Figure 2: Comparing the SPO loss with different surrogate losses. The true item values to be ranked
are (4.9, 5.1) (dark star). Two predictions are (3, 7) (magenta triangle) and (6, 5) (orange triangle).
2021 characterizes this quantity by the Smart "Predict, then Optimize" (SPO) loss, which equals to the loss incurred by solving the optimization problem ① using è instead of the true parameter c.
(spo c) [U? - Ue(=" (e))
where: 2" (c) arg m Z U2(2) and U Uc))
Figure 2a shows the misalignment between the l2 distance (green) and the SPO loss (blue) in ranking PTO problem. In this ranking PTO problem, there are two items to be ranked. The true values of the items are c1 4.9 and c2 5.1, which are also the values to predict. The prediction denoted by the magenta triangle has lower SPO loss than the orange one, and therefore yields better solution. However, prediction model that minimizes the l2 distance will prefer the orange one (whose (2 distance is lower) and produce a worse solution with regard to the ranking task.
However, the SPO loss of most PTO problems is piecewise linear function due to the combinatorial structure in the objective function U2(2) and the solution map 2 (c) As a result, its derivatives in the predicted PTO parameter è is either models whose training is based on gradient descent algorithms.
nonexistent, which prohibits the usage of prediction
In this paper, we consider collection of combinatorial optimization problems with strong ranking property. For this collection of optimization problems, we propose the total group preorder (TGP) loss and its differentiable variant approximated total group preorder (ATGP) loss as the training targets in the prediction stage. The ATGP loss will approximate the SPO loss with smooth shape, which is friendly and effective for the gradient- based training manner, as is shown in Figure 2c
3.2 STRONG RANKING PROPERTY AND (A)TGP LOSS
The strong ranking property is stronger version of the ranking property proposed by Demirović jet al. (2019). The ranking property from Demirović et al. (2019) requires that two instances combinatorial optimization problem have the same solution if the pairwise orders of the parameters of two instances are the same, which captures the importance of total preorder to the optimality of the ranking problems. However, the total preorder is not sufficient find optimal solution for many combinatorial problems with group-wise comparisons in nature, e.g., knapsack problem with fixed item weights]] and shortest path problem. To extend this ranking property to these prob- lems, we propose a stronger version of ranking property which takes the group-wise preorder into consideration.
Definition (Total group preorder). For combinatorial optimization problem with parameter (cI,..., ca)), the total group preorder TGP(c) (A, B): non-empty subsets A, B C (l......d)
and A n B = such that EiEA Ci 2 Σjenn
For ranking problems of items with true weights 61 1,02 2, = 3, then the total group preorder is TGP(c) = {{{3), (1)). (13), (2)), ((2), (1)), ((3), (1, 2))} For many combinatorial
'The weights of items are fixed constants, as well as the capacity. The values of items are PTO parameters be estimated. Throughout this paper, focus this subset of knapsack problems.
4

---

Published as a conference paper at ICLR 2022
optimization problems, it suffices to know the total group preorder of the parameters to yield the optimal solution.
Definition (Strong ranking property). A combinatorial optimization problem satisfies strong rank- ing property if for any two instances P and P' with parameters and c' respectively, TGP (c) TGP (c) = P and P' have the same solution.
The strong ranking property indicates that the prediction algorithm only needs learn the preorders between different sets of groups in PTO parameters. Inspired by the strong ranking property, we propose the TGP loss function which captures the difference between the TGP under predicted PTO parameter è and that under the true parameter Definition 3 (TGP loss).
( ([sgn((L)) sign(Le)]1
where sign(x) is a point-wise sign function and L is matrix whose elements can be any real numbers, called TGP matrix.
To capture the complete TGP, we need be (5") which needs exponentially growing memory as the number of PTO parameter d increases. However, this can be avoided by noticing that the optimal solutions of different optimization problems are determined by different subset of its TGP, e.g. [({3), {1)), ((3), (2),, ([2). (1})) for the ranking problem mentioned above. Instead, we fix number of rows in L and let each row of act as linear filter that extracts out a group-wise that each L represents subset of TGP; result, different optimization problems will have different TGP matrices.
comparison within
Note that TGP loss is not differentiable because the sign function is not differentiable, we derive a differentiable version by replacing the sign function with hyperbolic tangent function, called approximated total group preorder (ATGP) loss.
Definition 4 (ATGP loss).
CxGr (è, e L,7) = =]ttnn((yL)) sign(L)))
where y a temperature hyperparameter that controls the degree that the TGP loss is approximated to and tanh is point-wise hyperbolic tangent function.
Lemma 1. For any è, c. E Id and TGP matrix L, we have
lATOP (C, e L, = eTop(C, L) +
lim
Here the hyperbolic tangent function is used to approximate the sign function with differentiable functional form. Figure 2c visualizes the ATGP loss for the ranking PTO problem with TGP matrix [1, [1] and 7 0.9.
3.3 ROBUSTNESS OF ATGP LOSS
Despite of the difficulty on theoretically proving the non-optimum of the commonly used l2 loss in the prediction stage, we can prove in simple setting with linear regression as the prediction algorithm that the ATGP loss is generally better than the traditional lg loss for the ranking problem. Specifically, ATGP loss is more robust to noise added to the observation of the PTO parameters in the training data set.
Learning rank with linear regression Suppose there is of training examples (()))) i E S) in the training set identically and independently sampled from some dis- tribution D. Each example has a feature vector (()) E R² and vector (ii) E Rd response variables. Here the response variables are the values of d items that the decision maker aims to rank. The decision maker predicts the value items using a linear regression model, i.e., compute matrix H d such that for new pair (I,c) D. the linear estimator Hæ predicts score for each response variable in e given x. The decision maker will rank the items according to the predicted values Hr. An example is routing recommendation in which the feature vector encodes
5

---

Published as a conference paper at ICLR 2022
the context information like weather, time, temperature and R is the congestion levels of the d routes within a map. The goal is to find the n routes with the least congestion levels.
Let the ground truth linear transformation from the feature points to response variables be H", and the ground truth response variables be z(*) = H ( The noisy response variables that we actually observe are c( = o(0) + e(0) where e($) is the noise i..d. over each sample i. For loss function L, we denote its empirical risk minimizing estimator H₃ arg minH Eies ((Hx()) c(0),
so the predicted values given feature (+()) would be / Hę.. We define the robustness of a loss function as the minimum level noise such that there exists least one sample where the predicted values have different total group preorder as the ground truth values, which intuitively stands for the minimum efforts to "corrupt" the system.
Definition 5 (Robustness). The robustness R()) of a loss function is defined to be
R(() = inf[ e S.s... TGP(( + ))P(
(4)
We show that as long as the sample that's most easily corrupted does not share the same low- dimensional subspace of other samples, the robustness of ATGP loss function no lower than the loss.
Theorem 1. Let be the index of the ground truth optimization parameter which is most sensitive to noise perturbation, i.e., inf 11==1: TGP(((") ++) + TGP())))) S infeAllell2 TGP + e) + TGP()()), Vj S. the linear space expanded by all feature vectors except it has low rank structure (i.e., rank ([x() :i S/(ii)) k) and x.1²) doesn't t belong this space, then there exists TGP matrix L such that
R (CATGP) 2 R (E12)
The choice of TGP matrix L depends on the specific type of the optimization problem U. A TGP matrix suitable for top-n ranking problem may perform badly on the knapsack problem and shortest path problem. To solve this, we propose a searching algorithm to automatically find the suitable TGP matrices for different optimization problems with strong ranking property.
ADAPTIVE ATGP LOss FUNCTION SEARCH WITH APOC
To search for the proper ATGP loss functions for different optimization problems, propose search algorithm called APOC (Automatic Prediction and Optimization Connector). following the spirit of AutoML (Zoph & Le 2017 Pham al., 2018 Li et al. 2021). To make the size of the searching space for the TGP matrix stable and preserve the flexibility of comparing items, we parameterize the rows of TGP matrix with a of discretized Derivative-of-Gaass
(DoG) filters, which are wavelet filters widely used for edge detection in computer vision (Kennedy & Basu 1999] Zhang al. 2020). The wavelet filters can well capture the weighted group-wiss comparison among the items with variable group size and are updated based on the prediction quality induced by them.
4.1 SEARCH SPACE AND WAVELET FILTER
Recall that for the PTO parameter c, we want Lanh(7Le) As sign(Le) to approximately capture different group-wise comparisons between the entries of c. To this end, we parameterize the TGP matrix L by set of sliding discretized Derivatives-o--Gausss reception field which will select subset of entries of c. and assigns weights the selected entries in the reception field, as is shown in Figure 3 The inner product between the selected entries in the reception field and the weights form an entry in Lc. The reception field will slide along e with stride of I. We denote by G(I, a) the probability density function of Gaussian distribution with mean zero and standard deviation a, then the weight of filter with parameter (n; a;) assigned to the j-th item in the reception field is
(DoG) filters. Each filter has
Fr, = (3==((mm,a))) En_, (rr; where v ni, as)
gr. G(x, az) l==)
(5)
Ora.

---

Algorithm shows the details of our approach. Specifically, at each round L, we explore the loss function space by creating M trajectories, each trajectory with set of DoG filter parameter μt' sampled independently from a truncated normal distribution Numuncteed (0,-1, o²1). The truncated Published as a conference paper at ICLR 2022
(n,, a) (1,
(b) (n,a) (3, 1)
(c) (n, a) (5. 7)
Figure 3: Three DoG filters with the reception field 40 items.
Thus, these filters can detect group-wise comparison patterns and encode them into tanh(ryC)).
For representing the TGP matrix L, we denote the parameters (mi ( D. ap) of all D DoG filters used. With our wavelet filter representation approach, the search of an adequate TGP matrix over the entire matrix space degenerates to finding the optimal 6 which saves the computation cost greatly and makes it not necessarily dependent on the size of c.
4.2 PARAMETER OPTIMIZATION
normal distribution has support [0, +oo). We denote the probability density function of Nunucaued (6, I² as TH 0). For each loss function 8mm the prediction model is then trained to minimizes t using stochastic gradient descent (SGD) and the learned model La makes predictions {a(0) :ic Vj. We evaluate the current policy by calculating the negative total SPO loss of fa the validation set RtTh Σiev (E c.
on the validation set
The sampling policy can be updated with commonly used reinforcement learning algorithms. Two classic algorithms listed here in work, and other policy updating algorithms also appli- cable. The first one we have used is REINFORCE algorithm (Williams) 1992)
0, - 0,
Σ
[ g log T(p" " (c-1))
(6)
M
Besides, the PPO2 algorithm (Schulman et al. 2017) has also been applied:
02 arg 1 M
Σ min
T( 0) (ppm
R. CLIP
(H4" ()
1
e, +e R,m
(7)
1,-1)
TT( (r-1)"
Algorithm 1: Automatic Prediction and Optimization Connector (APOC)
Input: gradient-based based prediction model Sw. initial loss parameters Oo, number of search iterations T', number of samples per iteration M, exploration ratio o; Output: final loss parameters 8", final prediction model parameters w";
for each E [1, T do
for each E [1, M] do
Sample DoG filter parameters n from truneated normal distribution Aimoncane (0, o² I): Compute the ATGP loss function 8m which is parameterized by μ Train the prediction model
@ = arg min Σies (Sw (z) ());
Evaluate the model on the validation set a(1) = fa((! for all i V.;
Compute the reward 12. Σ.ev (200)2(0),))))
Update according to REINFORCE
PPO2 7
8" Gr. w" arg min Eies (f., (x. (l where e is the ATGP loss parameterized by 0*.
Following the common practice in policy gradient algorithms, subtract baseline value from R. to reduce the variance of the gradient estimator (Schulman et al. 2013). Here we use the averaged reward from all M trajectories as the baseline value.

---

Published as a conference paper at ICLR 2022
5 EXPERIMENTS
The proposed APOC method is applied to three predict-then-optimize problems with real-world datasets to validate its performance. Those three PTO problems contain optimization problems with different representative combinatorial structures, i.e., ranking, knapsack, and shortest path problem. Empirically, our experimental results demonstrate that significant performance gains can be achieved against some previously proposed algorithms by finding a better loss for the prediction phase.
5.1 DATASET DESCRIPTION
Energy Cost-Aware Scheduling This dataset contains two years historical energy price data from the day-head market of the Irish Single Electricity Market Operator (SEM-O), The energy prices for each half-hour of a day need to be predicted with some given feature data (Simonis et al.) including estimates of the temperature, wind speed, CO2 intensity, etc. We need to select subset of 48 half-hours in one day based on the predicted prices to schedule the machines to minimize the total expenditure of the day. Here formulate the optimization problem as top-k ranking problem, where the order of the top-k half-hours in a day determines the minimal total expenditure of the day. We evaluate algorithms with & (5, 10, 15). The data contains 37,872 instances.
Knapsack Formulation of Portfolio Optimization We use the historical daily price and volume data from 2004 2017 from partition SP500 of the Quandl WIKI dataset (QUANDL 2020). The task is to predict the future returns for a set of 505 candidate stocks, and generate daily portfolios based on the predictions. The optimization problem is formulated as a knapsack problem which the decision maker needs to choose stocks based estimated returns to maximize the total expected reward under the fixed budget. The data set provides 150 instances.
Shortest Path We use the processed data from Mandi & Guns (2020) where the goal is to find the shortest path of the given source-destination pairs on a Twitter ego network (McAuley & Leskovec 2012). The network consists of 231 nodes and 2861 edges where the edge weights need to be predicted using node and edge features, with 115 instances in total.
5.2 EXPERIMENTAL SETTINGS
Baseline methods We compare with the follow PTO methods. l2 distance: two-stage method with conventional la regression. QPTL/IntOpt: exerts quadratic/log-bariee regularization on the solution parameters to obtain non-zero gradient for differentiable training. SPO+: uses continuous convex surrogate of the SPO loss function for sub-gradient based training. NeuralSort: differentiably relaxing the permutation matrix in sorting problems. DiffOpt: a recent method which approximates the gradient by the solution difference with perturbed prediction parameters. The outlines of these methods are discussed in Section
For each experiment, we use the same prediction model architecture and train/validation/eest splits across different methods for fair comparisons. We use Adam optimizer for parameter training across all experiments, where hyperparameters (learning rate, ATGP temperature 7) are obtained by grid search using the validation performance. For Energy Cost-Aware Scheduling, the prediction model is instantiated to be 4-layer neural network (hidden layer sizes of 500-300 with ReI.U as activation function) with learning rate 5 x 10-5 and = 5.0. For Shortest Path, the prediction model is 4-layer network (hidden layer sizes of 100-100 with ReLU activation function) with learning rate 5 x 10-4 and = 3.0. For Portfolio Optimization, we use 5-layer neural network (hidden layer sizes of 100- 100-000-100 with ReLU as activation function) with learning rate 5 x 10-5, = 3.0. We use Gurobi optimizer to solve all combinatorial optimization problems and use CVXPY (Diamond & Boyd 2016 Agrawal et al. 2018) and QPTH (Amos & Kolter 2017)
Experiment settings
for differentiable optimization.
5.3 RESULTS
This subsection shows the evaluated performance of our algorithm on the three PTO problems de- scribed above. The goal is fhree-fold: 1) to demonstrate that our algorithm outperforms the previous proposed algorithms by a significant margin; 2) to analyze the sensitivity of our algorithm to the hyperparameters: 3) validate the effectiveness of our proposed DoG filters by ablation study.
8

---

Published as a conference paper at ICLR 2022
163
wirdst fullconreded
143
140
123
-20
1p.5
40
92
Sum
Sam
10
Etergy Coal Soll-Aoure Schedulling
Figure 4: Left and mid panel show the performance Algorithm| on Energy Cost-Aware Schedul- ing problem with different 7 (fixing 0.2) and different (fixing 7 1.0), respectively. The right panel shows the ablation study on the DoG wavelet filter parameterization (7 = 1.0, o = 0.2), with black segments showing the (5%, 95%) percentile interval.
Performance Comparison The results in Table 1 show that our proposed APOC algorithm yields significantly lower SPO losses than other algorithms on all three PTO problems. For Energy Cost- Aware Scheduling and shortest path problem, the ATGP loss function searched by REINFORCE algorithm induces better predictions while PPO2 algorithm is better on knapsack problem.
Table Comparison SPO losses with baseline algorithms on the three PTO problems. "_" means either the algorithm is inapplicable or cannot achieve a result in satisfying range with our best efforts.
Energy Cost-Aware Scheduling
Algorithm
Knapsack
Shortest Path
top-5
top-15
top-25
l2 distance
53.84
80.75
51.17
26.57
223
QPTL
68.86
110.34
74.31
27.14
197
IntOpt
27.06
92
SPO+
47.27
65.26
44,93
26.03
138
NeuralSort
52.69
73.23
45.43
Dit1Opt
50.28
71.86
57.06
27.21
APOC-REINFOREE
42.59
53.97
40.81
25.70
63.87
APOC-PPO2
49.50
66.80
55.56
24.93
78.03
Hyperparameter sensitivity In our algorithm, there are two key hyperparameters: the tempera- ture parameter y E (0, +oo) and the exploration ratio E (0, (00) Each hyperparameter stands for a trade-off the searching process. Lower temperature gives smoother ATGP loss which beneficial to the training of the prediction model but as Lemma states, the ATGP loss with higher approximates the true TGP loss closer. The exploration ratio a balances a classic exploration- exploitation trade-off in the searching algorithm. Sampling policy with smaller exploits the feedback more from the last step while the policy with larger a explores a larger area of the param- eter space. We present the influences of and show that the proposed method generally robust and insensitive to these hyperparameters.
searching algorithm in Figure The results
Ablation Study To understand the contribution of the DoG wavelet filter, conduct ablation study that compares the performance of our APOC algorithm with the searching algorithm in which the TGP matrix is parameterized by fully connected dense layer. As is shown in right panel of Figure 4 the wavelet filter yields significant decrease in the SPO loss on the test set.
6 CONCLUSION
To tackle the disalignment between prediction loss and optimization goal in PTO problems, we pro- pose to use the differentiable ATGP loss which captures the total group preorder. A corresponding APOC method is further proposed to automatically search for good surrogate loss with wavelet filters to capture the group- wise comparison of different sizes and weights. The method is well val- idated on three different PTO problems and shows great potential for more PTO problems. Starting from the limitations of this work, the following directions expected for future work: 1) extend the scope of APOC framework to PTO problems beyond the ones with strong ranking property, 2) explore how reduce the searching time of the iterations within APOC framework.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
Source code We have made the source code for the proposed APOC available the following repository:
Proof of Lemma and and Theorem We have attached the complete proof of Lemmal and Theorem iin the Appendix.
REFERENCES
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 60, 2018.
Brandon Amos. Differentiable optimization-baste based modeling for machine learning. PhD thesis, PhD thesis. Camegie Mellon University, 2019.
Brandon Amos and Zico Kolter. Optnet: Differentiable optimization layer in neural networks. In International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
David E Bell. Regret in decision making under uncertainty. Operations research, 30(5):961-981 1982.
Shahin Boluki, Xiaoning Qian, and Edward R Dougherty. Experimental design via generalized mean objective cost of uncertainty. IEEE Access, 7:2223-2230, 2018.
Sebastian Bruch, Xuanhui Wang, Michael Bendersky, and Mare Najork. An analysis of the softmax cross entropy loss for learning-to-rank with binary relevance. In Proceedings of the 2019 ACM SIGIR International Conference on Theory of Information Retrieval, pp. 75-78, 2019.
Emir Demirović, Peter Stuckey, James Bailey, Jeffrey Chan, Christopher Leckie, Kotagiri Ra- mamohanarao, and Tias Guns. Predict+ optimise with ranking objectives: Exhaustively learning linear functions. In Proceedings of the Twenty-Eige International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 1078-1093 1088- International Joint Conferences on Artificial Intelligence, 2019.
Steven Diamond and Stephen Boyd. CVXPY: A Python-emhedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 2021.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations, 2018.
Xin He, Kaiyong Zhao, and Xiaowen Chu. Automl: survey of the state-of-the-art. Knowledge- Based Systems, 212:106623 2021.
Pascal Van Hentenryck and Russell Bent. Online stochastic combinatorial optimization. The MIT Press, 2006.
Lesa M. Kennedy and Mitra Basu, A gaussian derivative operator for authentic edge detection and accurate edge localization. Int. J. Pattern Recognit. Artif. Intell., 13(3):367-380, 1999.
Johann Lau. Google maps 101: How ai helps predict traffic and determine routes, Sep 2020. URL
100-101-10 101-how-
helps predict w and www.aanddddddeee www.rddeeeeinee routesss
Chuming Li, Xin Yuan, Chen Lin, Minghao Guo, Wei Wu, Junjie Yan, and Wanli Ouyang. Am-lfs: Automl for loss function search. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 8410-841 8419, 2019.
Hao Li, Chenxin Tao, Xizhou Zhu, Xiaogang Wang, Gao Huang, and Jifeng Dai. Auto seg seg-loss: Searching metric surrogates for semantic segmentation. In International Conference on Learning Representations, 2021.
10

---

Published as a conference paper at ICLR 2022
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In
International Conference on Learning Representations, 2018.
Chuan Luo, Bo Qiao, Xin Chen, Pu Zhao, Randolph Yao, Hongyu Zhang. Wei Wu, Andrew Zhou, and Qingwei Lin. Intelligent virtual machine provisioning in cloud computing. In Proceedings of IJCA/ 2020, pp. 1495-1502, 2020.
Chuan Luo, Bo Qiao, Wengian Xing, Xin Chen, Pu Zhao, Chao Du, Randolph Yao, Hongyu Zhang, Wei Wu, Shaowei Cai, Bing He, Saravanakumar Rajmohan, and Qingwei Lin. Correlation-awee aware heuristic search for intelligent virtual machine provisioning in cloud systems. In Proceedings of AAAI 2021, pp. 12363-12372, 2021.
Jayanta Mandi and Tias Guns. Interior point solving for ip-based prediction+ optimisation Advances in Neural Information Processing Systems, 33:7272-7288 2020.
Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula. Resource management with deep reinforcement learning. Proceedings of the 15th ACM workshop on hot topics in networks, pp. 50-56, 2016.
Hamed Masnadi-Shirazi and Nuno Vasconcelos. On the design of loss functions for classification: theory, robustness to outliers, and savagehoost. In Proceedings of the 2 2 International Confer- ence on Neural Information Processing Systems, pp. 1049-1056, 2008.
Julian McAuley and Jure Leskovec. Learning to discover social circles in ego networks. NIPS, volume 2012, pp. 548-56. Citeseer, 2012.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International Conference on Machine Learning, pp. 4095- 4104. PMLR, 2018
Marin Vlastelica Pogančic, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differ- entiation of blackbox combinatorial solvers. In International Conference on Learning Represen- tations, 2019.
QUANDL. WIKI various end-of-day data. 2020. URL httpps:/www.uuaaa..coomm//////// WIKI
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Picter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv: /20600380 02438, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Helmut Simonis, Barry O'Sullivan, Deepak Mehta, Barry Hurley, and Milan De Cauwer. CSPLib problem 059: Energy-cost aware scheduling.
prob059
Peter J Stuckey, Tias Guns, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, Jeffrey Chan, et al. Dynamic programming for predict+ optimise. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1444-1444 1451, 2020.
Amy Thomson. Man Group-Oxford quants say their AI can predict stock moves. Bloomberg Tech- nology, Jun 2021.
Xiaobo Wang, Shuo Wang, Cheng Chi, Shifeng Zhang, and Tao Mei. Loss function search for face recognition. International Conference on Machine Learning, pp.
PMLR, 2020.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 1658-1665, 2019a.
Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe. End to end learning and optimization graphs. Advances in Newral Information Processing Systems, $2:4672-4633 2019b.
11

---

Published as a conference paper at ICLR 2022
Ronald J Williams. Simple statistical srudieet-following algorithms for connectionist reinforcement learning. Machine leamning, 8(3-4):229-2 256, 1992.
Byung-Jun Yoon, Xiaoning Qian, and Edward R Dougherty. Quantifying the objective cost of uncertainty in complex dynamical systems. IEEE Transactions on Signal Processing, (1)):2255 2266, 2013.
Guoyong Zhang, Jinping Liu, Jie Wang. Zhaohui Tang, Yongfang Xie, Junbin He, Tianyu Ma, and Jean Paul Niyoyita. Fogdbed: Fractional-order gaussian derivatives- based edge-relevant structure detection using caputo-fabrizio definition. Digit. Signal Process., 98: 102639, 2020.
Guang Zhao, Edward Dougherty, Byung-Jun Yoon, Francis J Alexander, and Xiaoning Qian. Bayesian active learning by soft mean objective cost of uncertainty. In International Conference Artificial Intelligence and Statistics, pp. 3970-3978. PMLR, 2021.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. Interna- tional Conference on Learning Representations, 2017.
12

---

Published as a conference paper at ICLR 2022
APPENDIX
PROOF OF LEMMA 1
Proof. Notice that the sign function is the derivative of a "V"-shape function:
sign(x) = 1 1x>0 1050
!
arg max 0)
0
arg max
where arg max(2, 0) 01 if x and [0, 1jT otherwise. can use softmax function to approximate the argmax, i.e.
arg max(xxx,0) 0)= =
lim
e
+00
and
2y0
27
22
T
tanh(2z)
Combined all equalities together, we have sign(x) + tanh tanh(ya)).
2 PROOF OF THEOREM
Notations. For matrix A, A, refers to its i-th row and A.; refers to its i-th column, ((A) denotes the column space of A and PA the orthogonal projection matrix onto C(A). A+ denotes the pseudo-inverse of A; ||Al|= = V., A4ll is the Frobenius norm A.
For convenience of introducing our proof, describe our data model and assumption in matrix notations. Let = |S| be the number samples, we can row-stack the feature vectors to be matrix X P Also let the ground truth linear regression parameter matrix be H' E & (H* is transposed here compared to the main text since we re viewing the feature/response variables as row vectors instead of column vectors), the row-stack matrix of ground truth response values is C* XH We observe C = C + E where E' is the noise matrix and the noise level is defined to be ||
For certain loss metric I, the minimizer is denoted by
A' = arg min 1(H H. C)
H
and the prediction denoted by
=XI
Any specific optimization problem with strong ranking property corresponds to subset of its total group pre-orders. We formalize this with the following definition.
Definition 6. A function is called sub-order function if it maps vector subset of its total group pre-orders. We will also call {(a the sub-orders of induced by f-
Now sub-order function would specify the optimization problem at hand. Each sub-order func- tion would also correspond TGP matrix whose rows compares the sub-groups induced by f: denote this matrix by Ly. Take Ranking problems for example, f(a) = fRanking (a) would map a to the subset of (G) where the elements (41 U2) satisfy [ng] = |2yl = 1, and Ly would matrix that maps vector to another vector of its pairwise differences.
Now for sample matrix A and label matrix B, the two loss metrics whose robustness to noise we aim compare
& (A, B) = || B 1
EXTOP (A, B) = |anhh() Ly - sign B)
Given sub-order function and vector define (a(a) to be the minimum perturbation a to change a's sub-orders induced by f: similarly for a matrix which consists of row-stack of samples.
13

---

which is immediate Published as a conference paper at ICLR 2022
Definition 7. For vector matrix A,
A (()) min ||cl2 s.t. f(a) + f(a+a) +
(A) min ()
Let us reformulate the assumption for Theorem 1 with the above notations.
Assumption 1 (Reformulated). The feature matrix X has low rank structure (meaning the samples belong to a linear subspace of less than k-dimension) except for the sample indexed by g which can induce different sub-orders with minimum perturbation, i.e., ,y(C)) (C
Validity and Intuition of Assumption 1 it is easy to construct data models which satisfies this assumption; details the end of the document. This assumption says that the sample which is most likely outlier in the dataset does not share the low-rank structure of other samples. Considering the low-rank structure of most real world datasets and the nature outliers, this assumption is very likely to hold intuitively. We also believe conclusion where the low-rank linear subspace in this assumption is replaced by low low-dimensional manifolds.
be extended to non-linear settings
Proof for Theorem L We're re now ready to present the proof of Theorem | consequence of Lemma and Lemma below.
Lemma 2. Under Assumption we have
R(G)) (s((o)
Proof. For loss the solution is given by
ft'2 = X
(9)
and thus
XII = +XX+X
(10)
Let U xx be a orthogonal basis for L(X), then Px UUT. Let orthogonal basis of the complement of L(X) be U- U Ufull then forms an orthonormal basis of N
Let normal vector of the subspace in Assumption be ā E I and let the index for the special sample be g. Then (C = 4y and also â" I, 0 for + g. a" xg * Now, we can scale to a s.t. a²xg- = 1. Therefore we now have
Xa=
where eg is the g-th standard basis (one-hot) vector. Now eg E C(X) L(U) and thus basis vectors in U are all perpendicular to eg. This means the g-th entry of any basis vector in U is 0. Since any row of Jf has unit norm, the g-th row of U must have unit norm, which also indicates that the g-th row of Px UUT has unit norm. Let the g-th row of Px be p R="
Now, we can find a matrix E s.t. Px E changes the sub-orders exactly the g-th row of C*, The noise level of such matrix E would then be an upper bound on R(i,)) Denote c* =Cg- be the pair in f(c*) with smallest lo; - c5l. We simply need to find E, E.g E E with minimum || 1 + || s.t. of + + E E. cg + --pEE... It can be easily seen that the optimal solution is given by
C.. Let (i.j)
c cf
-
E =
pt E.
2
2
and thus the minimum noise level is
(c
- c3
A ,)(C,) ,,(C") R((b))
2
by which our proof is done.
Lemma 3. Ay(C*) & R(EATGP).
14

---

Published as a conference paper at ICLR 2022
Proof. The proof of this lemma is rather simple; recall that the ATGP loss seeks to find H which minimizes EXTOP(X C* + E) = taan(n Ly sig + E) Now as long as E doesn't change the sub-orders in C' rows, sign (C + EE) intact under the noise E, and thus would still give the optimal solution. Therefore the minimum noise level which changes the sub-order in at least one of C' 's rows would always be lower bound for (LATGG).
, so LXTGP remains
This bound should have a large gap with the best bound since the decision boundary usually shouldn't t change lot even when corrupt portion of the samples. Here only corrupt one sample.
Example of constructing data that satisfies Assumption 1 Generating X which satisfies the requirement is straightforward. Now let H1, H2 E IR be nearly orthogonal vectors of Zg.. Randomly generate H3, ..., Hn and flip their signs s.t.
out of them have Hf zg O the rest have Hf > 0. This ensures that HI g. H 2g are the k-th and k + 1-th biggest items in Cy.:- By genericity, they are the closest pair in all pairs of entries of C and therefore A&(C") = AO(Cg).
15


Reviews:
[{"review_id": "jiKGtW97ovK", "reviewer": "Reviewer_AESs", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is well-written.\nThe proposed ideas are reasonable and they are presented in a logical manner.\nPerformance 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.\n\nOne 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.\nFor example, the SPO loss shown on page 3 is conceptually identical to what is known as \"regret\" in decision theory.\nRegret 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).\n\nFurthermore, 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.\nBoth 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.\nHowever, the authors, unfortunately, do not discuss the relation of the presented work with the existing studies based on regret or MOCU.\n\nAnother concern is the limited performance validation of the proposed approach presented in the current paper.\nFor 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.\nThe 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.\n\nAdditional 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.\n", "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.\nThe 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.\nWhile 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.\nThe 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.", "summary_of_the_review": "The paper deals with an interesting problem and the proposed method is well-motivated and presented in a logical manner.\nThe experimental results based on three different datasets show that the proposed method may have potential advantages over other existing schemes.\nHowever, 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.\nFurthermore, additional performance evaluation results are needed to clearly demonstrate the robustness and benefits of the proposed scheme.\nIncluding discussions on potential limitations of the current method (if any) would strengthen the paper.\n\n---\n\nThe evaluation has been updated after reviewing the authors' response.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bhd-AFmCRON", "reviewer": "Reviewer_8c8S", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My main comments are listed as follows:\n\n1.\tRegarding 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?\n\n2.\tMore details are needed for Algorithm 1: \na.\tWhat is the intuition behind Equation (6) and (7)? \nb.\tAre there any connections between these two equations? Under what circumstances should Equation (6) be applied? \nc.\tWhat is CLIP in Equation (7)? \nd.\tIn Section 4.1, how to determine D (the number of DoG filters used)? \ne.\tHow to choose \\gamma and \\sigma? How is \\sigma related to the problem itself?\n\n3.\tHow to avoid the overfitting problem in the TGP/ATGP framework?\n\n4.\tIn 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?\n\nMinor: \n\n1.\tIn the proof of Lemma 1, “.” is missing in the last sentence.\n\n2.\tIn the proof of Theorem 1, to make the notation consistent, I suggest to use A_{i,:} to denote its i-th row.\n\n3.\tIn the proof of Theorem 1, change the notation for loss function $l$ to $\\ell$;\n\n4.\tI 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?\n\n5.\tThe proof of Lemma 3 seems not rigorous. Could you use mathematical equation to prove this conclusion?\n\n", "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. ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "L4Vg3r_fvYT", "reviewer": "Reviewer_R87E", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Here are some of the paper’s strengths and weaknesses:\n\n(+) 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.\n\n(+/-) 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.\n\n(-) 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.\n\n(-) 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.\n\nMore detailed comments:\n- Figure 2: It was a little hard to tell where the stars and triangles lie on the x-y axes.\n- 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.\n- Equation (3): Should sign be tanh?", "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.\n\nTo 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.\nMotivated 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).\n\nLet $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).\n\nThey 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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

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)