Year: 2021

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 a satisfactory prediction result with the ordinary l2 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 l2 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.

heading: 1 INTRODUCTION
text: Many decision making processes under uncertainty in real world are solving combinatorial problems with parameters unknown to the decision maker. A traditional method to address the uncertainty issue is to add assumptions on the distributions of parameters (Hentenryck & Bent, 2006). 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 predict-then-optimize (PTO), has been widely employed in practice systematically (Elmachtoub & Grigas, 2021). For example, Google Maps estimates the travel times of roads in the traffic to compute a shortest path (Lau, 2020); Computer clusters predict the processing times and resource demands of computation tasks to make good job scheduling on servers (Mao et al., 2016); Hedge funds forecast the return rates of different stocks to optimize their portfolio in the next trading day (Thomson, 2021).
However, the commonly used l2 loss function (i.e., l2 distance between predictions and true values) usually cannot achieve ideal decision results in predict-then-optimize problems (Demirović et al., 2019). This misalignment between the l2 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 difference in objective values of the optimization solutions generated using the predicted and observed parameters, called Smart “Predict, then Optimize” (SPO) loss (Elmachtoub & Grigas, 2021). However, 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-based deep learning algorithms. Besides, most solvers for combinatorial optimization problems are not differentiable, which cannot be directly incorporated with the widely adopted gradient-based learning approaches nowadays.
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;b; Pogančić 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-specific (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, an alternative approach is to find a good loss metric from a predefined search space in an automatic manner, which is 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 an appropriate search space and then conduct some search algorithms, e.g., reinforcement learning and genetic algorithm, to find a good metric. Li et al. (2019) and Li et al. (2021) 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 predict-then-optimize problems, there is no such evaluation metrics available except for SPO loss. Moreover, these metrics, which are designed for segmentation tasks in computer vision domain, are not suitable to evaluate the prediction results for the combinatorial optimization problems.
In this paper, we propose a framework of automatic loss function search called APOC (Automatic Prediction and Optimization Connector) to tackle a wide range of predict-then-optimize problems whose optimal solution is determined by the total group preorder of the parameters of the combinatorial 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: 1) 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 it to a differentiable approximated version, which is fitted using a family of Derivative-of-Guassian wavelet functions to capture the group comparison relationship among the items with variable sizes and weights; 3) We propose an effective method to automatically search for a differentiable surrogate loss based on 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.

heading: 2 RELATED WORK
text: Predict-then-optimize (PTO) problems capture a common pipeline of machine-learning-assisted optimization solvers: predicting the unknown parameters of the optimization problem from the contextual information and then optimizing based on the predicted parameters (Elmachtoub & Grigas, 2021). 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 originates 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, Wilder et al. (2019b) differentiates the K-means algorithm by assigning nodes to clusters according to a soft-min function. Pogančić 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 to approximate the value function of the optimization problem, so-called regret in decision theory (Bell, 1982). Elmachtoub & Grigas (2021) derives a convex upper bound on the regret of linear programming, called SPO+ loss. Wilder et al. (2019a) proposes the QTPL loss by adding a quadratic penalty term to the continuous 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 logarithmic barrier term, called IntOpt. 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., 2021).
Loss function guides the machine learning algorithms to produce good predictions for different tasks, which is usually designed with domain knowledge from experts (Masnadi-Shirazi & Vasconcelos, 2008; Bruch et al., 2019). 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 generalization and transfer-ability on different vision tasks. Wang et al. (2020) adopts both random search and reinforcement learning algorithms to search for loss functions on face recognition problems. Li et al. (2021) 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. (2021) for comprehensive survey on searching methods in AutoML. Natural questions are: 1) whether we can design a 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.

heading: 3 ATGP LOSS FOR PREDICT-THEN-OPTIMIZE PROBLEMS

heading: 3.1 MISALIGNMENT IN PREDICT-THEN-OPTIMIZE PROBLEM
text: The problems we consider are the type of predict-then-optimize (PTO) problems in the following formulation. For an optimization problem in the following form
maximize z Uc(z) subject to z ∈ Z (1)
where z is the decision variable, c ∈ Rd is the parameter of the objective function U , and Z is the feasible set which does not depend on c. A decision maker needs to solve (1) without knowing the exact value of c. Instead, the decision maker will observe a feature vector x ∈ Rk. The goal of the decision maker is to predict the value of c and then optimize (1) based on the prediction ĉ. To distinguish with the parameters of the prediction models (e.g., weights of neural networks), we call c the PTO parameter.
Instead of focusing on the prediction error between c and ĉ (e.g., l2 distance), the decision maker cares more about a high-quality decision result generated from the prediction. Elmachtoub & Grigas (2021) characterizes this quantity by the Smart “Predict, then Optimize” (SPO) loss, which equals to the loss incurred by solving the optimization problem (1) using ĉ instead of the true parameter c.
`SPO(ĉ, c) = E [U∗c − Uc(z∗(ĉ))]
where z∗(c) = arg maxz∈Z Uc(z) and U∗c = Uc(z ∗(c)).
Figure 2a shows the misalignment between the l2 distance (green) and the SPO loss (blue) in a 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 a lower SPO loss than the orange one, and therefore yields a better solution. However, prediction model that minimizes the l2 distance will prefer the orange one (whose l2 distance is lower) and produce a worse solution with regard to the ranking task.
However, the SPO loss of most PTO problems is a piecewise linear function due to the combinatorial structure in the objective function Uc(z) and the solution map z∗(c). As a result, its derivatives in the predicted PTO parameter ĉ is either zero or nonexistent, which prohibits the usage of prediction models whose training is based on gradient descent algorithms.
In this paper, we consider a 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.

heading: 3.2 STRONG RANKING PROPERTY AND (A)TGP LOSS
text: The strong ranking property is a stronger version of the ranking property proposed by Demirović et al. (2019). The ranking property from Demirović et al. (2019) requires that two instances of a 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 to find an optimal solution for many combinatorial problems with group-wise comparisons in nature, e.g., knapsack problem with fixed item weights1 and shortest path problem. To extend this ranking property to these problems, we propose a stronger version of ranking property which takes the group-wise preorder into consideration. Definition 1 (Total group preorder). For a combinatorial optimization problem with parameter c = (c1, . . . , cd), the total group preorder TGP(c) = { (A,B) : non-empty subsets A,B ⊂ {1, . . . , d}
and A ∩B = ∅ such that ∑ i∈A ci ≥ ∑ j∈B cj } .
For a ranking problems of 3 items with true weights c1 = 1, c2 = 2, c3 = 3, then the total group preorder is TGP(c) = {({3}, {1}), ({3}, {2}), ({2}, {1}), ({3}, {1, 2})}. For many combinatorial optimization problems, it suffices to know the total group preorder of the parameters to yield the optimal solution. Definition 2 (Strong ranking property). A combinatorial optimization problem satisfies strong ranking property if for any two instances P and P ′ with parameters c and c′ respectively, TGP (c) = TGP (c′) =⇒ P and P ′ have the same solution.
1The weights of items are fixed constants, as well as the capacity. The values of items are PTO parameters to be estimated. Throughout this paper, we focus on this subset of knapsack problems.
The strong ranking property indicates that the prediction algorithm only needs to 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 ĉ and that under the true parameter c. Definition 3 (TGP loss).
`TGP(ĉ, c | L) = ‖sign(Lĉ)− sign(Lc)‖22 (2)
where sign(x) is a point-wise sign function and L is a matrix whose elements can be any real numbers, called TGP matrix. To capture the complete TGP, we need L to be ( 2d
2
) ×d 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 the number of rows in L and let each row of L act as a linear filter that extracts out a group-wise comparison within c so that each L represents a subset of TGP; as a result, different optimization problems will have different TGP matrices.
Note that TGP loss is not differentiable because the sign function on ĉ is not differentiable, we derive a differentiable version of it by replacing the sign function with hyperbolic tangent function, called approximated total group preorder (ATGP) loss. Definition 4 (ATGP loss).
`ATGP(ĉ, c | L, γ) = ‖tanh(γLĉ)− sign(Lc)‖22 (3)
where γ is a temperature hyperparameter that controls the degree that the TGP loss is approximated to and tanh is a point-wise hyperbolic tangent function.
Lemma 1. For any ĉ, c ∈ Rd and TGP matrix L, we have
lim γ→+∞
`ATGP(ĉ, c | L, γ) = `TGP(ĉ, c | L)
Here the hyperbolic tangent function is used to approximate the sign function with a differentiable functional form. Figure 2c visualizes the ATGP loss for the ranking PTO problem with TGP matrix L = [1,−1] and γ = 0.9.

heading: 3.3 ROBUSTNESS OF ATGP LOSS
text: Despite of the difficulty on theoretically proving the non-optimum of the commonly used l2 loss in the prediction stage, we can prove in a simple setting with linear regression as the prediction algorithm that the ATGP loss is generally better than the traditional l2 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 to rank with linear regression Suppose there is a set of training examples{( x(i), c(i) ) : i ∈ S } in the training set S identically and independently sampled from some dis-
tribution D. Each example has a feature vector x(i) ∈ Rk and a vector c(i) ∈ Rd of 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 of items using a linear regression model, i.e., compute a matrix H ∈ Rd×k such that for a new pair (x, c) ∼ D, the linear estimator Hx predicts a score for each response variable in c given x. The decision maker will rank the items according to the predicted values Hx. An example is routing recommendation in which the feature vector x encodes the context information like weather, time, temperature and c ∈ Rd 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 c̄(i) = H∗x(i). The noisy response variables that we actually observe are c(i) = c̄(i) + ε(i) where ε(i) is the noise i.i.d. over each sample i. For a loss function `, we denote its empirical risk minimizing estimator Ĥ` = arg minH ∑ i∈S `(Hx (i), c(i)),
so the predicted values given feature x(i) would be ĉ(i)` = Ĥ`x. We define the robustness of a loss function as the minimum level of noise such that there exists at 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 robustnessR(`) of a loss function ` is defined to be
R(`) = inf ε {‖ε‖22 : ∃i ∈ S s.t. TGP(ĉ (i) ` ) 6= TGP(c̄ (i))} (4)
We show that as long as the sample that’s most easily corrupted does not share the same lowdimensional subspace of other samples, the robustness of ATGP loss function is no lower than the l2 loss. Theorem 1. Let i∗ be the index of the ground truth optimization parameter which is most sensitive to noise perturbation, i.e., infε{‖ε‖22 : TGP(c̄(i
∗) + ε) 6= TGP(c̄(i∗))} ≤ infε{‖ε‖22 : TGP(c̄(j) + ε) 6= TGP(c̄(j))},∀j ∈ S. If the linear space expanded by all feature vectors except i∗ has low rank structure (i.e., rank ( {x(i) : i ∈ S/{i∗}} ) < k) and x(i
∗) doesn’t belong to this space, then there exists a TGP matrix L such that
R (`ATGP) ≥ R (`l2)
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.

heading: 4 ADAPTIVE ATGP LOSS FUNCTION SEARCH WITH APOC
text: To search for the proper ATGP loss functions for different optimization problems, we propose a search algorithm called APOC (Automatic Prediction and Optimization Connector), following the spirit of AutoML (Zoph & Le, 2017; Pham et 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 set of discretized Derivative-of-Gaussian (DoG) filters, which are wavelet filters widely used for edge detection in computer vision (Kennedy & Basu, 1999; Zhang et al., 2020). The wavelet filters can well capture the weighted group-wise comparison among the items with variable group size and are updated based on the prediction quality induced by them.

heading: 4.1 SEARCH SPACE AND WAVELET FILTER
text: Recall that for the PTO parameter c, we want tanh(γLc) ≈ sign(Lc) to approximately capture different group-wise comparisons between the entries of c. To this end, we parameterize the TGP matrix L by a set of sliding discretized Derivatives-of-Gaussian (DoG) filters. Each filter has a reception field which will select a subset of entries of c, and assigns weights to 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 c with a stride of 1. We denote by G(x, a) the probability density function of Gaussian distribution with mean zero and standard deviation a, then the weight of filter i with parameter (ni, ai) assigned to the j-th item in the reception field is
Fi,j = ν(j;ni, ai)/ √∑d r=1 ν2(r;ni, ai) where ν(j;ni, ai) = ∂ni ∂xni G(x, ai) |x=j (5)
Consequently, these sliding filters can detect different group-wise comparison patterns and encodes them into tanh(γLc).
For representing the TGP matrix L, we use θ to denote the parameters (n1, a1, . . . , nD, aD) 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 θ, which saves the computation cost greatly and makes it not necessarily dependent on the size of c.

heading: 4.2 PARAMETER OPTIMIZATION
text: Algorithm 1 shows the details of our approach. Specifically, at each round t, we explore the loss function space by creating M trajectories, each trajectory with a set of DoG filter parameter µm sampled independently from a truncated normal distribution Ntruncated(θt−1, σ2I). The truncated normal distribution has support on [0,+∞). We denote the probability density function of µ ∼ Ntruncated(θ, σ2I) as π(µ | θ). For each loss function `m, the prediction model is then trained to minimizes `m using stochastic gradient descent (SGD) and the learned model fŵ makes predictions on the validation set {ĉ(i) : i ∈ V }. We evaluate the current policy by calculating the negative total SPO loss of fŵ on the validation set Rmt = − ∑ i∈V `SPO(ĉ (i), c(i)).
The sampling policy can be updated with commonly used reinforcement learning algorithms. Two classic algorithms are listed here in our work, and other policy updating algorithms are also applicable. The first one we have used is REINFORCE algorithm (Williams, 1992)
θt ← θt−1 + η
M M∑ m=1 [Rmt ∇θ log π(µm | θt−1)] (6)
Besides, the PPO2 algorithm (Schulman et al., 2017) has also been applied:
θt ← arg max θ
1
M M∑ m=1 [ min ( π(µm | θ) π(µm | θt−1) Rmt ,CLIP ( π(µm | θ) π(µm | θt−1) , 1− , 1 + ) Rmt )] (7)
Algorithm 1: Automatic Prediction and Optimization Connector (APOC) Input: gradient-based prediction model fw, initial loss parameters θ0, number of search iterations T , number of samples per iteration M , exploration ratio σ; Output: final loss parameters θ∗, final prediction model parameters w∗;
1 for each t ∈ [1, T ] do 2 for each m ∈ [1,M ] do 3 Sample DoG filter parameters µm from the truncated normal distributionNtruncated(θt−1, σ2I); 4 Compute the ATGP loss function `m which is parameterized by µm Train the prediction model
ŵ = argminw ∑ i∈S ` m(fw(x
(i)), c(i)); 5 Evaluate the model on the validation set ĉ(i) = fŵ(x(i)) for all i ∈ V ; 6 Compute the reward Rmt = − ∑ i∈V `SPO(ĉ (i), c(i));
7 Update θt according to REINFORCE (6) or PPO2(7); 8 θ∗ = θT , w∗ = argminw ∑ i∈S ` ∗(fw(x (i)), c(i)) where `∗ is the ATGP loss parameterized by θ∗.
Following the common practice in policy gradient algorithms, we subtract a baseline value fromRmt to reduce the variance of the gradient estimator (Schulman et al., 2015). Here we use the averaged reward from all M trajectories as the baseline value.

heading: 5 EXPERIMENTS
text: The proposed APOC method is applied to three predict-then-optimize problems with real-world datasets to validate its performance over the state-of-the-art methods. 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.

heading: 5.1 DATASET DESCRIPTION
text: Energy Cost-Aware Scheduling This dataset contains two years of 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 a 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 we formulate the optimization problem as a 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 k ∈ {5, 10, 15}. The data set contains 37872 instances. Knapsack Formulation of Portfolio Optimization We use the historical daily price and volume data from 2004 to 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 in which the decision maker needs to choose stocks based on 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.

heading: 5.2 EXPERIMENTAL SETTINGS
text: Baseline methods We compare with the follow PTO methods. l2 distance: two-stage method with conventional l2 regression. QPTL/IntOpt: exerts quadratic/log-barrier 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 2.
Experiment settings For each experiment, we use the same prediction model architecture and train/validation/test splits across different methods for fair comparisons. We use Adam optimizer for parameter training across all experiments, where hyperparameters (learning rate & ATGP temperature γ) are obtained by grid search using the validation performance. For Energy Cost-Aware Scheduling, the prediction model is instantiated to be a 4-layer neural network (hidden layer sizes of 500-300 with ReLU as activation function) with learning rate 5×10−5 and γ = 5.0. For Shortest Path, the prediction model is a 4-layer network (hidden layer sizes of 100-100 with ReLU as activation function) with learning rate 5×10−4 and γ = 3.0. For Portfolio Optimization, we use a 5-layer neural network (hidden layer sizes of 100-100-100 with ReLU as activation function) with learning rate 5× 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) package for differentiable optimization.

heading: 5.3 RESULTS
text: This subsection shows the evaluated performance of our algorithm on the three PTO problems described above. The goal is three-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) to validate the effectiveness of our proposed DoG filters by an ablation study.
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.
Hyperparameter sensitivity In our searching algorithm, there are two key hyperparameters: the temperature parameter γ ∈ (0,+∞) and the exploration ratio σ ∈ (0,+∞). Each hyperparameter stands for a trade-off in the searching process. Lower temperature γ gives a smoother ATGP loss which is beneficial to the training of the prediction model but as Lemma 1 states, the ATGP loss with higher temperature γ approximates the true TGP loss closer. The exploration ratio σ 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 σ tends to explores a larger area of the parameter space. We present the influences of these two hyperparameters to our searching algorithm in Figure 4. The results show that the proposed method is generally robust and insensitive to these hyperparameters.
Ablation Study To understand the contribution of the DoG wavelet filter, we conduct an ablation study that compares the performance of our APOC algorithm with the searching algorithm in which the TGP matrix is parameterized by a fully connected dense layer. As is shown in right panel of Figure 4, the wavelet filter yields a significant decrease in the SPO loss on the test set.

heading: 6 CONCLUSION
text: To tackle the disalignment between prediction loss and optimization goal in PTO problems, we propose to use the differentiable ATGP loss which captures the total group preorder. A corresponding APOC method is further proposed to automatically search for a good surrogate loss with wavelet filters to capture the group-wise comparison of different sizes and weights. The method is well validated on three different PTO problems and shows great potential for more PTO problems. Starting from the limitations of this work, the following directions are expected for future work. The first one is to extend the scope of APOC framework to PTO problems beyond the ones with strong ranking property. Besides, it is also worth exploring how to reduce the searching time of the iterations within APOC framework.
REPRODUCIBILITY STATEMENT
Source code We have made the source code for the proposed APOC available in the following repository: https://github.com/AutoPredOptConnector/APOC .
Proof of Lemma 1 and Theorem 1 We have attached the complete proof of Lemma 1 and Theorem 1 in the Appendix.

Review summaries:
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.

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. 

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.