# Decision-Focused Learning: Foundations, State of the Art, Benchmark and
Future Opportunities

Jayanta Mandi<EMAIL_ADDRESS>
KU Leuven, Belgium James Kotary<EMAIL_ADDRESS>
University of Virginia, USA Senne Berden<EMAIL_ADDRESS>
KU Leuven, Belgium Maxime Mulamba<EMAIL_ADDRESS>
Vrije Universiteit Brussel, Belgium Víctor Bucarey<EMAIL_ADDRESS>
Universidad de O’Higgins, Chile Tias Guns<EMAIL_ADDRESS>
KU Leuven, Belgium Ferdinando Fioretto<EMAIL_ADDRESS>
University of Virginia, USA JM was affiliated to Vrije Universiteit Brussel,
Belgium during the submision of this article.JM and JK should both be
considered first authors.

###### Abstract

_Decision-focused learning_ (DFL) is an emerging paradigm that integrates
machine learning (ML) and constrained optimization to enhance decision quality
by training ML models in an end-to-end system. This approach shows significant
potential to revolutionize combinatorial decision-making in real-world
applications that operate under uncertainty, where estimating unknown
parameters within decision models is a major challenge. This paper presents a
comprehensive review of DFL, providing an in-depth analysis of both gradient-
based and gradient-free techniques used to combine ML and constrained
optimization. It evaluates the strengths and limitations of these techniques
and includes an extensive empirical evaluation of eleven methods across seven
problems. The survey also offers insights into recent advancements and future
research directions in DFL.

Code and benchmark: https://github.com/PredOpt/predopt-benchmarks

##  1 Introduction

Real-world applications frequently confront the task of decision-making under
uncertainty, such as planning the shortest route in a city, determining
optimal power generation schedules, or managing investment portfolios (?, ?,
?, ?, ?, ?). In such scenarios, estimating unknown parameters often poses a
significant challenge.

Machine Learning (ML) and Constrained Optimization (CO) serve as two key tools
for these complex problems. ML models estimate uncertain quantities, while CO
models optimize objectives within constrained spaces. This sequential process,
commonly referred to as _predictive_ and _prescriptive_ modeling, as
illustrated in Figure 1, is prevalent in fields like operations research and
business analytics (?). For instance, in portfolio management, the prediction
stage forecasts asset returns, while the prescriptive phase optimizes returns
based on these predictions. The terminology Predict-Then-Optimize problem will
be used in this survey paper to refer to the problem setting where the
uncertain parameter has to be predicted first, followed by solving the CO
problem using the predicted parameter to make a decision.

A commonly adopted approach to tackle Predict-Then-Optimize problems involves
handling these two stages—prediction and optimization—separately and
independently. This “two-stage” process first involves training an ML model to
create a mapping between observed features and the relevant parameters of a CO
problem. Subsequently, and independently, a specialized optimization algorithm
is used to solve the decision problem, which is specified by the predicted
problem parameters. The underlying assumption in this methodology is that
superior predictions would lead to precise predictive models and consequently,
high-quality decisions. Indeed, if the predictions of the parameters were
perfectly accurate, they would enable the correct specification of CO models
which can be solved to yield fully optimal decisions. However, ML models often
fall short of perfect accuracy, leading to suboptimal decisions due to
propagated prediction errors. Thus, in many applications, the predictive and
prescriptive modelings are not isolated but rather, deeply interconnected, and
hence should ideally be modeled jointly.

Figure 1: Decision-making under uncertainty involves both predictive and
prescriptive analytics. In the predictive stage, the uncertain parameters are
predicted from the features using an ML model. In the prescriptive stage, a
decision is prescribed by solving a CO problem using the predicted parameters.

This is the goal of the decision-focused learning (DFL) paradigm, which
directly trains the ML model to make predictions that lead to good decisions.
In other words, DFL integrates prediction and optimization in an end-to-end
system trained to optimize a criterion (i.e., a loss function) that is based
on the resulting decisions.

Since many ML models, including neural networks (NNs), are trained via
gradient-based optimization, the gradients of the loss must be backpropagated
through each constituent operation of the model. In DFL, the loss function is
dependent on the solution of the CO problem, thus the CO solver is _embedded_
as a component of the ML model. In this integration of prediction and
optimization, a key challenge is _differentiating through the optimization
problem_. An additional challenge arises from decision models operating on
discrete variables, which produce discontinuous mappings and hinder gradient-
based learning. Hence, examining _smooth_ surrogate models for these discrete
mappings, along with their differentiation, becomes crucial. These two
challenges are the core emphasis and central focal points in DFL.

This survey paper presents a comprehensive overview of decision-focused
learning and makes several key contributions. First, to navigate the complex
methodologies developed in recent years, the survey differentiates gradient-
based DFL methodologies from ‘gradient-free’ methodologies, which do not rely
on computing gradients for learning. Given their compatibility with neural
networks, which are the predominant ML architectures, there has been a greater
focus on gradient-based DFL methods. To facilitate a comprehensive
understanding of this field, we propose categorizing gradient-based learning
methods into four distinct classes: (1) analytical differentiation of
optimization mappings, (2) analytical smoothing of optimization mappings, (3)
smoothing by random perturbations, and (4) differentiation of surrogate loss
functions. This categorization, illustrated in Figure 4 lower in the paper,
serves as a framework for comprehending and organizing various gradient-based
DFL methodologies.

In the second part, this paper compiles a selection of problem-specific DFL
models, making them publicly available to facilitate broader access and usage.
As part of that, we benchmark the performance of the various methods on
_seven_ distinct problems. This provides an opportunity for comparative
understanding and assists in identifying the relative strengths and weaknesses
of each approach. The code and data used in the benchmarking are accessible
through https://github.com/PredOpt/predopt-benchmarks. Finally, this survey
looks forward and discusses open challenges and offering an outlook on
potential future directions in the field of DFL.

### Positioning with respect to other overview papers.

With the growing interest of the operations research (OR) and artificial
intelligence (AI) communities in integrating ML and CO, various survey,
review, and tutorial papers have emerged. ? (?) provide applications of
Predict-Then-Optimize problems in various fields of OR, but offer limited
discussion on DFL methodologies. DFL is also a part of a short review article
by ? (?), where the primary focus is on recent developments in differentiable
optimization to integrate CO problems into neural network architectures. The
tutorial by ? (?) introduces the notion of DFL to the OR community and
discusses methods that fall under our category of _differentiating surrogate
loss functions_ below. The PyEPO library (?) offers a common code base and an
implementation of a selected number of DFL techniques, along with a common
interface for benchmarking on various datasets. ? (?) also provide an overview
of the DFL techniques implemented in the library, but offer limited discussion
on the broader literature of existing DFL techniques. Finally the recent
survey by ? (?), which appeared online concurrently with the submission of
this article, proposes the umbrella term of _contextual stochastic
optimization_ and discusses three families of techniques namely decision rule
optimization, sequential learning and (stochastic) optimization and integrated
learning and (stochastic) optimization; with DFL belonging to the latter.

In contrast, our survey offers a distinct perspective by adopting an ML
oriented overview that extensively surveys gradient-based and gradient-free
DFL techniques for Predict-Then-Optimize problems, where uncertain parameters
appear in the objective function of the CO problems. The proposed
categorization of gradient-based DFL techniques into four classes allows for a
systematic discussion and comparison of the different methods. Moreover, this
article stands out as an experimental survey by performing comparative
evaluations of some widely-used DFL techniques on benchmark problems; thereby
highlighting the feasibility of implementing, comparing and deploying
practical DFL methods. The aim of this dual focus is to enhance understanding
of both specific DFL techniques while also showing empirical insights into
their effectiveness across various applications.

### Paper organization.

Following this introduction, the paper is structured as follows. Preliminary
concepts are discussed in Section 2, which introduces the problem setting and
explains the challenges in implementing DFL. The subsequent Section 3 offers a
comprehensive review of existing gradient-free and gradient-based DFL
methodologies for handling these challenges, further categorizing the
gradient-based methodologies into four distinct classes. Section 4 presents
interesting real-world examples of DFL applications. Section 5 brings forth
seven benchmark DFL tasks from public datasets, with a comparative evaluation
of eleven DFL techniques. Finally, the survey paper concludes by providing a
discourse on the current challenges and possible future directions in DFL
research.

##  2 Preliminaries

This section presents an overview of the problem setting, along with
preliminary concepts and essential terminology. Then, the central modeling
challenges are discussed, setting the stage for a review of current
methodologies in the design and implementation of DFL. Throughout the survey
paper, vectors are denoted by boldface lowercase letters, such as
$\mathbf{x}$, while scalar components within the vector $\mathbf{x}$ are
represented with a subscript $i$, denoting the $i^{\text{th}}$ item within
$\mathbf{x}$ as $x_{i}$. Similarly, the vectors $\mathbf{1}$ and $\mathbf{0}$
symbolize the vector of all-ones and all-zeros, respectively. Moreover,
$\mathbf{I}$ denotes an identity matrix of appropriate dimension.

###  2.1 Problem Setting

In operations research and business analytics, decisions are often
quantitatively modeled using CO problems. In many real-world applications, it
happens that some parameters of the CO problem are uncertain and must be
inferred from contextual data (hereafter referred to as _features_). The
settings considered in this survey paper involve estimating those parameters
through predictive inferences made by ML models, and subsequently, the final
decisions are modeled as the solution to the CO problems based on those
inferences. In this setting, the decision-making processes can be described by
_parametric_ CO problems, defined as,

$\displaystyle\mathbf{x}^{\star}(\mathbf{c})=\operatorname*{argmin}_{\mathbf{x}}$
$\displaystyle\;\;f(\mathbf{x},\mathbf{c})$ (1a) s.t.
$\displaystyle\;\;\bm{g}(\mathbf{x},\mathbf{c})\leq\mathbf{0}$ (1b)
$\displaystyle\;\;\bm{h}(\mathbf{x},\mathbf{c})=\mathbf{0}.$ (1c)

The goal of the CO problem above is to find _a_ solution
$\mathbf{x}^{\star}(\mathbf{c})\in\mathbb{R}^{n}$, which minimizes the
objective function $f$, subject to equality and inequality constraints as
defined by the functions $\bm{h}$ and $\bm{g}$. This _parametric_ problem
formulation defines $\mathbf{x}^{\star}(\mathbf{c})$ as a function of the
parameters $\mathbf{c}\in\mathbb{R}^{k}$.

CO problems can be categorized in terms of the forms taken by the functions
defining their objectives (1a) and constraints (1b-1c). These forms also
determine important properties of the optimization mapping
$\mathbf{c}\rightarrow\mathbf{x}^{\star}(\mathbf{c})$, when viewed as a
function from problem parameters to optimal solutions, such as its continuity,
differentiability, and injectivity.

In this survey paper, it is assumed that the constraints are fully known prior
to solving, i.e., $\bm{h}(\mathbf{x},\mathbf{c})=\bm{h}(\mathbf{x})$ and
$\bm{g}(\mathbf{x},\mathbf{c})=\bm{g}(\mathbf{x})$, indicating the constraints
do not depend on the parameter $\mathbf{c}$, which is uncertain. Rather the
dependence on $\mathbf{c}$ is restricted solely to the objective function.
This is the setting considered by almost all existing works surveyed. While it
is also possible to consider uncertainty in the constraints, this leads to the
possibility of predicting parameters that lead to solutions that are
infeasible with respect to the ground-truth parameters. The learning problem
has not yet been well-defined in this setting (unless a recourse action to
correct infeasible solutions is used (?, ?)). For this reason, in the
following sections, only $f$ is assumed to depend on $\mathbf{c}$, so that
$\bm{g}(\mathbf{x})\leq\mathbf{0}$ and $\bm{h}(\mathbf{x})=\mathbf{0}$ are
satisfied for all outputs of the decision model. For notational convenience,
the feasible region of the CO problem in (1), will be denoted by $\mathcal{F}$
(i.e., $\mathbf{x}\in\mathcal{F}$ if and only if
$\bm{g}(\mathbf{x})\leq\mathbf{0}$ and $\bm{h}(\mathbf{x})=\mathbf{0}$).

If the true parameters $\mathbf{c}$ are known exactly, the corresponding
‘true’ optimal decisions may be computed by solving (1). In such scenarios,
$\mathbf{x}^{\star}(\mathbf{c})$ will be referred to as the _full-information
optimal decisions_ (?). This paper, instead, considers problems where the
parameters $\mathbf{c}$ are unknown but can be estimated as a function of
observed features $\mathbf{z}$. The problem of estimating $\mathbf{c}$ falls
under the category of supervised ML problems. In this setting, a set of past
observation pairs $\\{(\mathbf{z_{i}},\mathbf{c_{i}})\\}_{i=1}^{N}$ is
available as a training dataset, $\mathcal{D}$, and used to train an ML model
$m_{\bm{\omega}}$ (with trainable ML parameters $\bm{\omega}$), so that
parameter predictions take the form
$\mathbf{\hat{\mathbf{c}}}=m_{\bm{\omega}}(\mathbf{z})$. Then, a decision
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$ can be made based on the predicted
parameters. $\mathbf{x}^{\star}(\mathbf{\hat{c}})$ is referred to as a
_prescriptive decision_. The overall learning goal is to optimize the set of
prescriptive decisions made over a distribution of features
$\mathbf{z}\sim\mathcal{Z}$, with respect to some evaluation criterion on
those decisions. Thus, while the ML model $m_{\bm{\omega}}$ is trained to
predict $\mathbf{\hat{c}}$, its performance is evaluated based on
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$. This paper uses the terminology
Predict-Then-Optimize problem to refer to the problem of predicting
$\mathbf{\hat{c}}$, to improve the evaluation of
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$.

###  2.2 Learning Paradigms

The defining challenge of the Predict-Then-Optimize problem setting is the gap
in modeling between the prediction and the optimization components: while
$m_{\bm{\omega}}$ is trained to predict $\mathbf{\hat{c}}$, it is evaluated
based on the subsequently computed $\mathbf{x}^{\star}(\mathbf{\hat{c}})$.
Standard ML approaches, based on the _empirical risk minimization_ (ERM) (?),
use standard loss functions $\mathcal{L}$, such as mean squared error or
cross-entropy, in order to learn to predict
$\mathbf{\hat{c}}=m_{\bm{\omega}}(\mathbf{z})$. The learning is supervised by
by the ground-truth $\mathbf{c}$. However, in principle, for Predict-Then-
Optimize problems, it is desirable to train $m_{\bm{\omega}}$ to make
predictions $\mathbf{\hat{c}}$ that optimize the evaluation criterion on
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$ directly. This distinction motivates
the definition of two alternative learning paradigms for Predict-Then-Optimize
problems.

##### Prediction-focused learning (PFL).

A straightforward approach to this supervised ML problem is to train the model
to generate accurate parameter predictions $\mathbf{\hat{c}}$ with respect to
ground-truth values $\mathbf{c}$. This paper introduces the term _prediction-
focused learning_ to refer to this approach (also called two-stage learning
(?)) because the model is trained with a focus on the accuracy of the
parameter predictions preceding the decision model. Here, the training is
agnostic of the downstream CO problem. At the time of making the decision, the
pre-trained model’s predictions $\mathbf{\hat{c}}$ are passed to the CO
solvers which solve (1) to return $\mathbf{x}^{\star}(\mathbf{\hat{c}})$.
Typical ML losses, such as the mean squared error (MSE) or binary cross
entropy (BCE), are used to train the prediction model in this case.

$MSE\;(\mathbf{\hat{c}},\mathbf{c})=\frac{1}{N}\|\mathbf{c}-\mathbf{\hat{c}}\|^{2}$
(2)

Such loss functions, like Eq. (2), which measure the prediction error of
$\mathbf{\hat{c}}$ with respect to $\mathbf{c}$, are referred to as prediction
losses. Algorithm 1 illustrates PFL with MSE loss.

##### Decision-focused learning (DFL).

By contrast, in decision-focused learning, the ML model is trained to optimize
the evaluation criteria which measure the quality of the resulting decisions.
As the decisions are realized after the optimization stage, this requires the
integration of prediction and optimization components, into a composite
framework which produces full decisions. From this point of view, generating
the predicted parameters $\mathbf{\hat{c}}$ is an intermediary step of the
integrated approach, and the accuracy of $\mathbf{\hat{c}}$ is not the primary
focus in training. The focus, rather, is on the error incurred after
optimization. A measure of error with respect to the integrated model’s
prescriptive decisions, when used as a loss function for training, is
henceforth referred to as a task loss. The essential difference from the
aforementioned prediction loss is that it measures the error in
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$, rather than in $\mathbf{\hat{c}}$.

The objective value achieved by using the predicted
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$ is generally suboptimal with respect to
the true objective parameters $\mathbf{c}$. Often, the end goal is to generate
predictions $\mathbf{\hat{c}}$ with an optimal solution
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$ whose objective value in practice
(i.e., $f(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})$) comes close to
the full-information optimal value
$f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{c})$. In such cases, a salient
notion of task loss is the _regret_ , defined as the difference between the
full-information optimal objective value and the objective value realized by
the prescriptive decision. Equivalently, it is the magnitude of suboptimality
of the decision $\mathbf{x}^{\star}(\mathbf{\hat{c}})$ with respect to the
optimal solution $\mathbf{x}^{\star}(\mathbf{c})$ under ground-truth
parameters $\mathbf{c}$:

$\mathit{Regret}\;(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})=f(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})-f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{c})$
(3)

Note that minimizing regret is equivalent to minimizing the value of
$f(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})$, since the term
$f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{c})$ is constant with respect to the
prediction model. While regret may be considered the quintessential example of
a task loss, other task losses can arise in practice. For example, when the
ground-truth target data are observed in terms of decision values
$\mathbf{x}^{\star}$, rather than parameter values $\mathbf{c}$, they may be
targeted using the typical training loss functions such as
$MSE\;(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{x}^{\star})$.

##### Relationship between prediction and task losses.

As previously mentioned, an ML model is trained without considering the
downstream CO problem in prediction-focused learning for Predict-Then-Optimize
tasks; still the ML model is evaluated at test time on the basis of its
resulting CO problem solutions. This is based on an underlying assumption that
generating accurate predictions with respect to a standard prediction loss
will result in good prescriptive decisions. Note that zero prediction loss
always implies zero task loss, since $\mathbf{\hat{c}}=\mathbf{c}$ implies
$\mathbf{x}^{\star}(\mathbf{\hat{c}})=\mathbf{x}^{\star}(\mathbf{c})$.
However, in practice, it is impossible to learn an ML model that makes no
prediction error on any sample. The model error can only be minimized in one
metric, and the minimization of the prediction error and the resulting
decision error do not in general coincide (?). Furthermore, the prediction
loss and the task loss are, in general, not continuously related. These
principles are illustrated by the following example.

##### Example.

The shortcomings of training with respect to prediction errors can be
illustrated with a simple CO problem. For this illustration, consider a
knapsack problem (?). The objective of the knapsack problem is to select a
maximal-value subset from an overall set of items, each having its own value
and unit weight, subject to a capacity constraint, which imposes that the
number of selected items cannot be higher than the capacity $C$. This knapsack
problem with unit weights can be formulated as follows:

$\mathbf{x}^{\star}(\mathbf{c})=\operatorname*{argmax}_{\mathbf{x}\in\\{0,1\\}}\mathbf{c}^{\top}\mathbf{x}\;\;\texttt{s.t.}\sum_{i}x_{i}\leq\mathit{C}$
(4)

In a Predict-Then-Optimize variant of this knapsack problem, the item weights
and knapsack capacity are known, but the item values are unknown and must be
predicted using observed features. The ground-truth item value $\mathbf{c}$
implies the ground-truth solution $\mathbf{x}^{\star}(\mathbf{c})$.
Overestimating the values of the items that are chosen in
$\mathbf{x}^{\star}(\mathbf{c})$ (or underestimating the values of the items
that are not chosen) increases the prediction error. Note that these kind of
prediction errors, even if they are high, do not affect the solution, and thus
do not affect the task loss either. On the other hand, even low prediction
errors for some item values may change the solution, affecting the task loss.
That is why after a certain point, reducing prediction errors does not
decrease task loss, and sometimes may increase it. DFL aims to address this
shortcoming of PFL: by minimizing the task loss directly, prediction errors
are implicitly traded off on the basis of how they affect the resulting
decision errors.

$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$4.5$$5$$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$4.5$$5$Value
of Item 1Value of Item 2 Figure 2: An illustrative numerical example with a
knapsack problem with two items to exemplify the discrepancy between
prediction error and regret. The figure illustrates that two points can have
the same prediction error but different regret. Furthermore, it demonstrates
that overestimating the values of the selected items or underestimating the
values of the items that are left out does not change the solution, and thus
does not increase the regret, even though the prediction error does increase.

The discrepancy between the prediction loss and the task loss has been
exemplified in Figure 2 for a very simple knapsack problem with only two
items. For this illustration, assume that both the items are of unit weights
and the capacity of the knapsack is one, i.e., only one of the two items can
be selected. The true values of the first and second items are $2.5$ and $3$
respectively. The point $(2.5,3)$, marked with ✱, represents the true item
values. In this case the true solution is $(0,1)$, which corresponds to
selecting only the second item. It is evident that any prediction in the blue
shaded region leads to this solution. For instance, the point $(1.5,3)$,
marked with ✚, corresponds to predicting $1.5$ and $3$ as values of the two
items respectively and this results in selecting the second item. On the other
hand, the point $(2.5,2)$, marked with ✖, triggers the wrong solution $(1,0)$,
although the squared error values of ✚ and ✖ are identical. Also, note that
overestimating the value of the second item does not change the solution. For
instance, the point $(1.5,4)$, marked with ▲, corresponds to overestimating
the value of the second item to $4$ while keeping the value of the first item
the same as the point in ✚. This point is positioned directly above the point
in ✚ and still stays in the blue-shaded region. Similarly, the point
$(0.5,3)$, marked with ▼, results from underestimating the value of the first
item and is in the blue shaded region too. Although these two points have
higher values of squared error than the point marked with ✖, they trigger the
right solution, resulting in zero regret.

##### Empirical risk minimization and bilevel form of DFL.

The minimization of either the expected prediction loss in PFL or the expected
task loss in DFL, can be expressed as an Empirical Risk Minimisation (ERM)
problem over a training dataset
$\mathcal{D}\equiv\\{(\mathbf{z_{i}},\mathbf{c_{i}})\\}_{i=1}^{N}$. The
desired objective of training is to learn a model, $m_{\bm{\omega}}$, that
minimizes the _expected loss_. However, as the joint probability distribution
of $(\mathbf{z},\mathbf{c})$ is often unknown, ERM minimizes the empirical
loss instead, i.e., ERM minimizes the average loss, calculated over
$\mathcal{D}$.

Note that ERM typically involves making a point prediction $\mathbf{\hat{c}}$
to minimize expected loss. However, besides point predictions, it is also
possible to estimate the distribution of $\mathbf{\hat{c}}$. The advantage of
distributional estimation is that it allows the decision-maker to consider
extreme cases of the parameter distribution, leading to more robust decisions.
However, minimizing distributionally robust loss (?) is inherently more
challenging than ERM, even for standard ML problems. As a result, most of the
surveyed works focus on minimizing expected task loss in DFL. Hence, learning
techniques for minimizing _expected_ task loss are the main focus in this
survey paper.

The respective ERM problems below assume the use of the MSE and regret loss
functions for PFL and DFL respectively, but the principles described here hold
for a wide range of alternative loss functions. PFL, by minimizing the
prediction error with respect to the ground-truth parameters directly, takes
the form of a standard regression problem:

$\min_{\bm{\omega}}\frac{1}{N}\sum_{i=1}^{N}\|m_{\bm{\omega}}(\mathbf{z_{i}})-\mathbf{c_{i}}\|^{2},\\\
$ (5)

which is an instance of unconstrained optimization. In the case of DFL, it is
natural to view the ERM as a bilevel optimization problem:

$\displaystyle\min_{\bm{\omega}}\frac{1}{N}\sum_{i=1}^{N}\Big{(}f(\mathbf{x}^{\star}(\mathbf{\hat{c}_{i}}),\mathbf{c_{i}})-f(\mathbf{x}^{\star}(\mathbf{c_{i}}),\mathbf{c_{i}})\Big{)}$
(6a)
$\displaystyle\texttt{s.t.}\;\;\mathbf{\hat{c}_{i}}=m_{\bm{\omega}}(\mathbf{z_{i}});\
\mathbf{\mathbf{x}^{\star}}(\mathbf{\hat{c}_{i}})=\operatorname*{argmin}_{\mathbf{x}\in\mathcal{F}}\mathbf{\hat{c}_{i}}^{\top}\mathbf{x}.$
(6b)

The outer-level problem (6a) minimizes task loss on the training set while the
inner-level problem (6b) computes the mapping
$\mathbf{c}\to\mathbf{x}^{\star}(\mathbf{c})$. Solving (6) is computationally
more challenging than solving (5) in the prediction-focused paradigm. In both
cases, optimization by stochastic gradient descent (SGD) is the preferred
method for training neural networks.

Algorithms 1 and 2 compare the gradient descent training schemes for PFL and
DFL. Algorithm 1 is a standard application of gradient descent, in which the
derivatives of Line 6 are generally well-defined and can be computed
straightforwardly (typically by automatic differentiation (?)). Line 7 of
Algorithm 2 shows that direct differentiation of the mapping
$\mathbf{c}\to\mathbf{x}^{\star}(\mathbf{c})$ can be used to form the overall
task loss gradient $\frac{d\mathcal{L}}{d\bm{\omega}}$, by providing the
required chain rule term
$\frac{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}{d\mathbf{\hat{c}}}$. However,
this differentiation is nontrivial as the mapping itself lacks a closed-form
representation. Furthermore, many interesting and practical optimization
problems are inherently nondifferentiable and even discontinuous as functions
of their parameters, precluding the direct application of Algorithm 2 to
optimize (6) by gradient descent. The following subsections review the main
challenges of implementing Algorithm 2.

###  2.3 Challenges to Implement Decision-Focused Learning

##### Differentiation of CO mappings.

When considering gradient-based learning techniques, one needs to minimize the
task loss by backpropagating the error over it. Hence, the partial derivatives
of the task loss with respect to the prediction model parameters $\bm{\omega}$
must be computed to carry out the parameter update at Line 7 of Algorithm 2.
Since the task loss $\mathcal{L}$ is a function of
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$, the gradient of $\mathcal{L}$ with
respect to $\bm{\omega}$ can be expressed in the following terms by using the
chain rule of differentiation:

$\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})}{d\bm{\omega}}=\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})}{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}\frac{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}{d\mathbf{\hat{c}}}\frac{d\mathbf{\hat{c}}}{d\bm{\omega}}$
(7)

The first term in the right side of (7), can be computed directly as
$\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})$ is typically a
differentiable function of $\mathbf{x}^{\star}(\mathbf{\hat{c}})$. A deep
learning library (such as PyTorch (?)) computes the last term by representing
the neural network as a computational graph and applying automatic
differentiation (autodiff) in the reverse mode (?). However, the second term,
$\frac{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}{d\mathbf{\hat{c}}}$, may be
nontrivial to compute given the presence of two major challenges: (1) The
mapping $\mathbf{\hat{c}}\to\mathbf{x}^{\star}(\mathbf{\hat{c}})$, as defined
by the solution to an optimization problem, _lacks a closed form_ which can be
differentiated directly, and (2) for many interesting and useful optimization
models, the mapping is _nondifferentiable_ in some points, and has zero-valued
gradients in others, precluding the straightforward use of gradient descent.
As shown in the next subsection, even the class of linear programming
problems, widely used in decision modeling, is affected by both issues.
Section 3 details the various existing approaches aimed at overcoming these
challenges.

Algorithm 1 Gradient-descent in prediction-focused learning

Input: training data D$\equiv\\{(\mathbf{z_{i}},\mathbf{c_{i}})\\}_{i=1}^{N}$
Hyperparams: $\alpha$\- learning rate

1: Initialize $\bm{\omega}$.

2: for each epoch do

3: for each instance $(\mathbf{z},\mathbf{c})$ do

4: $\mathbf{\hat{c}}=m_{\mathbf{\bm{\omega}}}(\mathbf{z})$

5: $\mathcal{L}=(\mathbf{\hat{c}}-\mathbf{c})^{2}$

6:
$\bm{\omega}\leftarrow\bm{\omega}-\alpha\frac{d\mathcal{L}}{d\mathbf{\hat{c}}}\frac{d\mathbf{\hat{c}}}{d\bm{\omega}}$

7: end for

8: end for

Algorithm 2 Gradient-descent in decision-focused learning with regret as task
loss

Input: $\mathcal{F}$, training data D
$\equiv\\{(\mathbf{z_{i}},\mathbf{c_{i}},\mathbf{x}^{\star}(\mathbf{c_{i}})\\}_{i=1}^{N}$;
Hyperparams: $\alpha$\- learning rate

1: Initialize $\bm{\omega}$.

2: for each epoch do

3: for each instance $(\mathbf{z},\mathbf{c},\mathbf{x}^{\star}(\mathbf{c}))$
do

4: $\mathbf{\hat{c}}=m_{\mathbf{\bm{\omega}}}(\mathbf{z})$

5:
$\mathbf{x}^{\star}(\mathbf{\hat{c}})=\operatorname*{argmin}_{\mathbf{x}\in\mathcal{F}}f(\mathbf{x},\mathbf{\hat{c}})$

6:
$\mathcal{L}=f(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})-f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{c})$

7:
$\bm{\omega}\leftarrow\bm{\omega}-\alpha\frac{d\mathcal{L}}{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}\frac{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}{d\mathbf{\hat{c}}}\frac{d\mathbf{\hat{c}}}{d\bm{\omega}}$

8: end for

9: end for

##### Computational cost.

Another major challenge in DFL is the computational resources required to
train the integrated prediction and optimization model. Note that Line 5 in
Algorithm 2 evaluates $\mathbf{x}^{\star}(\mathbf{\hat{c}})$. This requires
solving and differentiating the underlying CO problem for each observed data
sample, in each epoch. This imposes a significant computational cost even when
dealing with small-scale and efficiently solvable CO problems, but can become
an impediment in the case of large and (NP-)hard optimization problems.

Figure 3: In decision-focused learning, the neural network model is trained to
minimize the task loss

###  2.4 Optimization Problem Forms

The effectiveness of solving an optimization problem depends on the specific
forms of the objective and constraint functions. Considerable effort has been
made to develop efficient algorithms for certain optimization forms. Below,
the readers are provided an overview of the key and widely utilized types of
optimization problem formulations.

####  2.4.1 Convex optimization

In convex optimization problems, a convex objective function is to be
optimized over a convex feasible space. This class of problems is
distinguished by the guarantee that any locally optimal solution is also
globally optimal (?). Since many optimization problems converge provably to
local minima, convex problems are considered to be reliably and efficiently
solvable as opposed to _nonconvex_ problems. Despite this, convex optimization
mappings still impose significant computational overhead on Algorithm 2 since
most convex optimizations are orders of magnitude more complex than
conventional neural network layers (?). Like all parametric optimization
problems, convex ones are implicitly defined mappings from parameters to
optimal solutions, lacking a closed form that can be differentiated directly.
However as detailed in Section 3.1.1, they can be canonicalized to a standard
form, which facilitates automation of their solution and backpropagation by a
single standardized procedure (?).

The class of convex problems is broad enough to include some that yield
mappings $\mathbf{x}^{\star}(\mathbf{\hat{c}})$ that are differentiable
everywhere, and some that do not. The _linear programs_ , which are convex and
form nondifferentiable mappings with respect to their objective parameters,
are notable examples of the latter case and are discussed next.

####  2.4.2 Linear programming

Linear Programs (LPs) are convex optimization problems whose objective and
constraints are composed of affine functions. These programs are predominant
as decision models in operations research, and have endless industrial
applications since the allocation and transfer of resources is typically
modeled by linear relationships between variables (?). The parametric LPs
considered in this survey paper take the following form:

$\displaystyle\mathbf{x}^{\star}(\mathbf{c})=\operatorname*{argmin}_{\mathbf{x}}\mathbf{c}^{\top}\mathbf{x}$
(8a) $\displaystyle\text{s.t.}\;\;A\mathbf{x}=\mathbf{b}$ (8b)
$\displaystyle\mathbf{x}\geq\mathbf{0}$ (8c)

Compared to other classes of convex problems, LPs admit efficient solution
methods, even for large-scale problems (?, ?). From a DFL standpoint, however,
LPs pose a challenge, because the mapping
$\mathbf{c}\rightarrow\mathbf{x}^{\star}(\mathbf{c})$ is nondifferentiable.
Although the derivatives of mapping (8) are defined almost everywhere, they
provide no useful information for gradient descent training. To see this,
first note the well-known fact that a linear program always takes its optimal
value at a vertex of its feasible set (?). Since the number of vertices in any
such set is finite, (8) maps a continuous parameter space to a discrete set of
solutions. As such, it is a piecewise constant mapping. Therefore its
derivatives are zero almost everywhere, and undefined elsewhere. Prevalent
strategies for incorporating linear programs in DFL thus typically rely on
differentiating smooth approximations to the LP, as detailed in Section 3.1.2.

Many OR problems, such as the allocation and planning of resources, can be
modeled as LPs. Also many prototypical problems in algorithm design (e.g.,
sorting and top-k selection) can be formulated as LPs with continuous
variables, despite admitting only discrete integer solutions, by relying on
the total unimodularity of the constraint matrices (?). In what follows, some
examples of machine learning models of LPs and how they might occur in a
Predict-Then-Optimize context are given.

Shortest paths.

Given a directed graph with a given start and end node, the goal in the
shortest path problem is to find a sequence of arcs of minimal total length
that connects the start and the end node. The decision variables are binary
indicators of each edge’s inclusion in the path. The linear constraints ensure
$[0,1]$ bounds on each indicator, as well as flow balance through each node.
These flow balance constraints capture that, except for the start and end
node, each node has as many incoming selected arcs as outgoing selected arcs.
For the start node, there is one additional outgoing selected arc, and for the
end node, there is one more incoming selected arc. The parameters in the
linear objective represent the arc lengths. In many realistic settings—as well
as in several common DFL benchmarks (?, ?)—these are unknown, requiring them
to be predicted before a shortest path can be computed. This motivating
example captures the realistic setting in which the shortest route between two
locations has to be computed, but in which the road traversal times are
uncertain (due to unknown traffic conditions, for example), but can be
predicted from known features (such as day of the week, time of day and
weather conditions).

Bipartite matching.

Given a bipartite graph with weighted arcs, where the weights are unknown and
must be predicted, the task is to choose a subset of arcs so that each node is
involved in at most one selected arc, maximizing the total weight. The
variables lie in $[0,1]$ indicating the inclusion of each edge and the weights
are the objective parameters. The constraints ensure that each node is
involved at most once in a selected arc. With a complete bipartite graph,
matchings can be construed as permutations, which can be employed in tasks
such as learning to rank (?).

Sorting and Ranking.

The sorting of any list of predicted values can be posed as a linear program
over a feasible region whose vertices correspond to all of the possible
permutations of the list. The related ranking, or argsort problem assigns to
any length-$n$ list a permutation of sequential integers $[n]$ which sorts the
list. By smoothing the linear program, these basic operations can be
differentiated and backpropagated (?).

Top-$k$ selection.

Given a set of items and item values that must be predicted, the task is to
choose the subset of size $k$ with the largest total value in selected items.
In addition to $[0,1]$ bounds on the indicator variables, a single linear
constraint ensures that the selected item indicators sum to $k$. A prevalent
example can be found in multilabel classification (?, ?).

Computing the maximum.

This is a special case of top-$k$ selection where $k=1$. When the LP’s
objective is regularized with the entropy term
$H(\mathbf{x})=\mathbf{x}^{\top}\log\mathbf{x}$, the mapping from predicted
values to optimal solutions is equivalent to a softmax function (?).

Max-flow/ min-cut.

Given a network with predefined source and sink nodes, and predicted flow
capacities on each arc, the task is to find the maximum flow rate that can be
channeled from source to sink. Here the predicted flow capacities occupy the
right-hand side of the linear constraints, which is not in line with the DFL
problem formulation introduced in subsection 2.1. However, in the min-cut
problem—which is the dual linear program of the max-flow problem—the flow
capacities are the parameters in the objective function. The max-flow problem
can thus be cast as an equivalent min-cut problem allowing DFL techniques to
predict the flow capacities.

####  2.4.3 Integer linear programming

Integer Linear Programs (ILPs) are another mainstay in OR and AI research.
ILPs differ from LPs in that the decision variables $\mathbf{x}$ are
restricted to integer values, i.e., $\mathbf{x}\in\mathbb{Z}^{k}$ where
$\mathbb{Z}^{k}$ is the set of integral vectors of appropriate dimensions.
Like LPs, ILPs are challenging to use in DFL because they yield discontinuous,
nondifferentiable mappings. Computationally however, they are more challenging
due to their NP-hard complexity, which may preclude the exact computation of
the mapping $\mathbf{\hat{c}}\rightarrow\mathbf{x}^{\star}(\mathbf{\hat{c}})$
at each step of Algorithm 2. Their differentiation is also significantly more
challenging, since the discontinuity of their feasible regions prevents many
smoothing techniques that can be applied in DFL with LPs.

The following examples include ILPs in Predict-Then-Optimize problems.

Knapsack.

The knapsack problem (4), discussed earlier, has been used to compose
benchmark problems in several papers about DFL (?, ?, ?). Given are weights of
a set of items, as well as a capacity. The items also have associated values,
which have to be predicted from features. The optimization task involves
selecting a subset of the items that maximizes the value of the selected
items, whilst ensuring that the sum of the associated weights does not exceed
the capacity.

Travelling salesperson problem.

In the travelling salesperson problem, the list of cities, and the distances
between each pair of cities, is given. The goal is to find a path of minimal
length that visits each city exactly once. In the Predict-Then-Optimize
setting, the distances between the cities first have to be predicted (?) from
observable empirical data.

Combinatorial portfolio optimization.

Portfolio optimization involves making optimal investment decisions across a
range of financial assets. In the combinatorial Predict-Then-Optimize variant,
the decisions are discrete, and must be made on the basis of the predicted
next period’s increase in the value of several assets (?).

Diverse bipartite matching.

Diverse bipartite matching problems are similar to the bipartite matching
problems described in 2.4.2, but are subject to additional diversity
constraints (?, ?, ?). In this variant, edges have additional properties. The
diversity constraints enforce lower and upper bounds on the proportion of
edges selected with a certain property. These changes preclude an LP
formulation, by breaking the total unimodularity property possessed by the
standard bipartite matching LP.

Energy-cost aware scheduling.

Energy-cost aware scheduling involves scheduling a set of tasks across a set
of machines minimizing the overall energy cost involved. As future energy
costs are unknown, they first have to be predicted (?).

####  2.4.4 Integer nonlinear programming

In integer nonlinear programming, variables are defined over an integer domain
whiles the objective function and/or the constraints are nonlinear. Performing
DFL on integer nonlinear programs faces similar challenges as in performing
DFL on ILPs: their implicitly defined mappings
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$ result in zero-valued gradients almost
everywhere. Additionally, because of their nonlinear nature, many of the
techniques developed for DFL with ILPs, which assume linearity, do not
directly translate to integer nonlinear programs (?, ?). To the best of our
knowledge, no DFL technique has specifically been developed for or tested on
integer nonlinear programs. The most closely related work is (?), which
employs approximate ILP surrogates for integer nonlinear programs, which are
then used to compose a DFL training procedure using known techniques for
differentiation through the ILP surrogate model.

##  3 Review of Decision-focused Learning Methodologies

Objective Function Constraint Functions Decision Variables CO Solver
Analytical Differentiation of Optimization Mappings Strictly Convex Convex
Continuous Primal-Dual Solver Analytical Smoothing of Optimization Mappings
Linear Linear Continuous/ Discrete Primal-Dual Solver Smoothing by Random
Perturbations Linear in the Predicted Parameter Not limited to specific form
Continuous/ Discrete Solver agnostic Differentiation of Surrogate Loss
Functions Linear in the Predicted Parameter Not limited to specific form
Continuous/ Discrete Solver agnostic Utilize Figure 4: An overview of
gradient-based DFL methodologies categorized into four classes.

Gradient-based learning is a popular learning approach in ML, and likewise,
gradient-based DFL techniques have been extensively studied, with the added
benefit that (deep) neural networks can be used as the underlying ML model.
However, other ML frameworks, such as tree-based methods or search-based
methods, do not require gradients at all and can side-step the issue of zero-
valued gradients altogether. Hence, DFL methodologies can be classified into
two broad categories: I. Gradient-based DFL, and II. Gradient-free DFL. First,
gradient-based DFL will be surveyed, followed by gradient-free DFL.

###  3.1 Review of Gradient-based DFL Methodologies

This subsection will describe several DFL techniques which address the
challenge of differentiating an optimization mapping for DFL in gradient-based
training. In essence, different approaches propose different smoothed
surrogate approximations of
$\frac{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}{d\mathbf{\hat{c}}}$ or
$\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))}{d\mathbf{\hat{c}}}$,
which is used for backpropagation. This paper proposes the first
categorization of existing gradient-based DFL techniques into the following
four distinct classes:

Analytical Differentiation of Optimization Mappings:

Techniques in this category aim to compute exact derivatives for
backpropagation by differentiating the optimality conditions for certain
optimization problem forms, for which the derivative exists and is non-zero.

Analytical Smoothing of Optimization Mappings:

These approaches deal with combinatorial optimization problems (for which the
analytical derivatives are zero almost everywhere) by performing smoothing of
combinatorial optimization problems, which results in approximate problems
that can be differentiated analytically.

Smoothing by Random Perturbations:

Techniques under this category utilize implicit regularization through
perturbations, constructing smooth approximations of optimization mappings.

Differentiation of Surrogate Loss Functions:

Techniques under this category propose surrogate loss functions of specific
task loss such as regret. These surrogate losses reflect the quality of the
decisions and they provide easy-to-compute gradients or subgradients for
gradient-based training.

Figure 4 presents key characteristics of these four methodology classes,
highlighting the types of problems that can be addressed within each class.
Next, each category is thoroughly described.

####  3.1.1 Analytical Differentiation of Optimization Mappings

As discussed before, differentiating through parametric CO problems comes with
two main challenges. First, since CO problems are complex, implicitly defined
mappings from parameters to solutions; computing the derivatives is not
straightforward. Second, since some CO problems result in piecewise-constant
mappings, their derivatives are zero almost everywhere, and do not exist
elsewhere.

This subsection pertains to CO problems for which the second challenge does
not apply, i.e., problems that are smooth mappings. For these problems, all
that is required to implement DFL is direct differentiation of the mapping in
Eq. (1).

##### Differentiating unconstrained relaxations.

An early work discussing differentiation through constrained argmin problems
in the context of machine learning is (?). It first proposes a technique to
differentiate the argmin of a smooth, unconstrained convex function. When
$V(\mathbf{c})=\operatorname*{argmin}_{\mathbf{x}}f(\mathbf{c},\mathbf{x})$,
it can be shown that when all second derivatives of $f$ exist,

$\frac{dV(\mathbf{c})}{d\mathbf{c}}=-\frac{f_{\mathbf{cx}}(\mathbf{c},V(\mathbf{c}))}{f_{\mathbf{xx}}(\mathbf{c},V(\mathbf{c}))}$
(9)

where $f_{\mathbf{cx}}$ is the second partial derivative of $f$ with respect
to $\mathbf{c}$ followed by $\mathbf{x}$. This follows from implicit
differentiation of the first-order optimality conditions

$\frac{df}{d\mathbf{x}}(\mathbf{c},V(\mathbf{c}))=0$ (10)

with respect to $\mathbf{c}$, and rearranging terms. Here the variables
$\mathbf{c}$ are the optimization problem’s defining parameters, and the
variables $\mathbf{x}$ are the decision variables.

This technique is then extended to find approximate derivatives to constrained
optimization problems with inequality constraints
$g_{i}(\mathbf{c},\mathbf{x})\leq 0$, by first relaxing the problem to an
unconstrained problem, by means of the log-barrier function

$F(\mathbf{c},\mathbf{x})=f(\mathbf{c},\mathbf{x})-\mu\sum_{i}^{M_{in}}\log(-g_{i}(\mathbf{c},\mathbf{x}))$
(11)

where $M_{in}$ is the number of inequality constraints. Then
$\operatorname*{argmin}_{\mathbf{x}}F(\mathbf{c},\mathbf{x})$ is
differentiated with respect to $\mathbf{c}$ for some choice of the scaling
factor $\mu$. Since this approach relies on approximations and requires
hyperparameter tuning for the factor $\mu$, subsequent works focus on
differentiating CO problems directly via their own global conditions for
optimality, as discussed next.

##### Differentiating KKT conditions of quadratic programs

More recent approaches are based on differentiating the optimality conditions
of a CO problem directly, i.e., without first converting it to an
unconstrained problem. Consider an optimization problem and its optimal
solution:

$\displaystyle\mathbf{x}^{\star}=\operatorname*{argmax}_{\mathbf{x}}$
$\displaystyle\;\;f(\mathbf{x})$ (12a) s.t.
$\displaystyle\;\;\bm{g}(\mathbf{x})\leq 0$ (12b)
$\displaystyle\;\;\bm{h}(\mathbf{x})=0$ (12c)

and assume that $f$, $g$ and $h$ are differentiable functions of $\mathbf{x}$.
The Karush–Kuhn–Tucker (KKT) conditions are a set of equations expressing
optimality conditions for a solution $\mathbf{x}^{\star}$ of problem (12) (?):

$\displaystyle\nabla f(\mathbf{x}^{\star})+\sum_{i}w_{i}\nabla
h_{i}(\mathbf{x}^{\star})+\sum_{j}u_{j}\nabla g_{j}(\mathbf{x}^{\star})=0$
(13a) $\displaystyle g_{j}(\mathbf{x}^{\star})\leq 0\;\;\forall j$ (13b)
$\displaystyle h_{i}(\mathbf{x}^{\star})=0\;\;\forall i$ (13c) $\displaystyle
u_{j}\geq 0\;\;\forall j$ (13d) $\displaystyle
u_{j}g_{j}(\mathbf{x}^{\star})=0\;\;\forall j$ (13e)

OptNet is a framework developed by ? (?) to differentiate through optimization
mappings that are convex quadratic programs (QPs) by differentiating through
these KKT conditions. In convex quadratic programs, the objective $f$ is a
convex quadratic function and the constraint functions $g,h$ are linear over a
continuous domain. In the most general case, each of $f$, $g$ and $h$ are
dependent on a distinct set of parameters, in addition to the optimization
variable $\mathbf{x}$:

$\displaystyle
f(\mathbf{c},Q,\mathbf{x})=\frac{1}{2}\mathbf{x}^{\top}Q\mathbf{x}+\mathbf{c}^{\top}\mathbf{x}$
(14a) $\displaystyle h(A,\mathbf{b},\mathbf{x})=A\mathbf{x}-\mathbf{b}$ (14b)
$\displaystyle g(R,\mathbf{s},\mathbf{x})=R\mathbf{x}-\mathbf{s}$ (14c)

When $\mathbf{x}\in\mathbb{R}^{k}$ and the number of inequality and equality
constraints are $M_{in}$ and $M_{eq}$, respectively, a QP problem is specified
by parameters $Q\in\mathbb{R}^{k\times k}$, $\mathbf{c}\in\mathbb{R}^{k}$,
$R\in\mathbb{R}^{k\times M_{in}}$, $\mathbf{s}\in\mathbb{R}^{M_{in}}$,
$A\in\mathbb{R}^{k\times M_{eq}}$, and $\mathbf{b}\in\mathbb{R}^{M_{eq}}$. The
optimal solution $\mathbf{x}^{\star}$ can be implicitly differentiated with
respect to each of the parameters $(Q,\mathbf{c},R,\mathbf{s},A,\mathbf{b})$,
by directly differentiating the KKT conditions of optimality (13). This
produces a linear system of equations, which can be solved for the desired
gradients $\frac{d\mathbf{x}^{\star}}{d\mathbf{c}}$. Later, ? (?) extended the
technique of ? (?), by also computing the QP problem’s second order
derivatives. This enables training with gradient boosting models, which
require the gradient as well as the Hessian matrix of the loss.

##### Differentiating optimality conditions of conic programs.

Another class of problems with a parametric canonical form are the conic
programs, which take the form:

$\displaystyle\mathbf{x}^{\star}(A,\mathbf{b},\mathbf{c})=\operatorname*{argmax}_{\mathbf{x}}$
$\displaystyle\;\;\mathbf{c}^{\top}\mathbf{x}$ (15a) s.t.
$\displaystyle\;\;A\mathbf{x}-\mathbf{b}\in\mathcal{K}$ (15b)

where $\mathcal{K}$ is a nonempty, closed, convex cone.

A framework for differentiating the mapping (15) for any $\mathcal{K}$ is
proposed by ? (?), which starts by forming the homogeneous self-dual embedding
of (15), whose parameters form an askew-symmetric block matrix composed of
$A$, $\mathbf{b}$, and $\mathbf{c}$. Following the technique proposed by ?
(?), the solution to this embedding is expressed as the problem of finding a
zero of a mapping containing a skew-symmetric linear function and projections
onto the cone $\mathcal{K}$ and its dual. The zero-value of this function is
implicitly differentiated, in a similar manner to the KKT conditions of a
quadratic program (?). The overall mapping (15) is viewed as the composition
of a function that maps $(A,\mathbf{b},\mathbf{c})$ onto the skew-symmetric
parameter space of the self-dual embedding, the rootfinding problem that
produces a solution to the embedding, and a transformation back to a solution
of the primal and dual problems. The overall derivative is found by a chain
rule applied over this composition.

Subsequent work by ? (?) leverages the above-described differentiation of cone
programs to develop a more general differentiable convex optimization
solver—cvxpylayers. It is well known that conic programs of the form (15) can
provide canonical representations of convex programs (?). The approach
described by ? (?) is based on this principle; that a large class of
_parametric_ convex optimization problems can be recast as equivalent
parametric cone programs, with an appropriate choice of the cone
$\mathcal{K}$. A major benefit of this representation is that it allows a
convex program to be separated with respect to its defining parameters
($A,\mathbf{b},\mathbf{c}$) and its structure $\mathcal{K}$, allowing a
generic procedure to be applied for solving and differentiating the
transformed problem with respect to $A$, $\mathbf{b}$ and $\mathbf{c}$.

To transform convex programs to cone programs (15), the framework of ? (?) is
utilized, which is based on two related concepts. First is the notion of
_disciplined convex programming_ , which assists the automation of cone
transforms by imposing a set of rules or conventions on how convex programs
can be represented. Second is the notion of _graph implementations_ , which
represent functions as optimization problems over their epigraphs, for the
purpose of generically representing optimization problems and assisting
conversion between equivalent forms. The associated software system called cvx
allows for disciplined convex programs to be converted to cone programs via
their graph implementations. Subsequently, the transformed problem is solved
using conic optimization algorithms, and its optimal solution is converted to
a solution of the original disciplined convex program. Differentiation is
performed through each operation and combined by the chain rule. The
transformation of parameters between respective problem forms, and the
solution recovery step, are differentiable by virtue of being affine mappings
(?). The intermediate conic program is differentiated via the methods of ?
(?).

##### Solver unrolling and fixed-point differentiation.

While the methods described above for differentiation through CO problems are
generic and applicable to broad classes of problems, other practical
techniques have been proven effective and even advantageous in some cases. A
common strategy is that of solver _unrolling_ , in which the solution to (1)
is found by executing an iterative optimization method on the computational
graph of its preceding predictive model. The optimization mapping (1) is then
backpropagated simply by automatic differentiation through each step of the
algorithm, thus avoiding the need to explicitly model
$\frac{d\mathbf{x}^{\star}(\mathbf{c})}{d\mathbf{c}}$ (?). While this approach
leads to accurate backpropagation in many cases, it suffers disadvantages in
efficiency due to the memory and computational resources required to store and
apply backpropagation over the entire computational graph of an algorithm that
requires many iterations (?). A comprehensive survey of algorithm unrolling in
image processing applications is provided by ? (?).

Another way in which a specific solution algorithm may provide gradients
though a corresponding optimization mapping, is by implicit differentiation of
its fixed-point conditions. Suppose that the solver iterations

$\mathbf{x}_{t+1}(\mathbf{c})=\mathcal{U}(\mathbf{x}_{t}(\mathbf{c}),\;\mathbf{c})$
(16)

converge as $t\rightarrow\infty$ to a solution
$\mathbf{x}^{\star}(\mathbf{c})$ of the problem (1), then the fixed-point
conditions

$\mathbf{x}^{\star}(\mathbf{c})=\mathcal{U}(\mathbf{x}^{\star}(\mathbf{c}),\;\mathbf{c})$
(17)

are satisfied. Assuming the existence of all derivatives on an open set
containing $\mathbf{c}$ to satisfy the implicit function theorem, it follows
by implicit differentiation with respect to $\mathbf{c}$ that

$(\mathbf{I}-\Phi)\frac{d\mathbf{x}^{\star}}{d\mathbf{c}}=\Psi,$ (18)

which is a linear system to be solved for
$\frac{d\mathbf{x}^{\star}}{d\mathbf{c}}$, in terms of
$\Phi={{\frac{d\mathcal{U}}{d\mathbf{x}^{\star}}(\mathbf{x}^{\star}(\mathbf{c}),\;c)}}$,
$\Psi=\frac{d\mathcal{U}}{d\mathbf{c}}(\mathbf{x}^{\star}(\mathbf{c}),\;\mathbf{c})$
and identity matrix $\mathbf{I}$.

The relationship between unrolling and differentiation of the fixed-point
conditions is studied by ? (?), showing that backpropagation of (1) by
unrolling (16) is equivalent to solving the linear system (18) by fixed-point
iteration. The convergence rate of the backward pass in unrolling is
determined by that of solving the linear system (18) in such a manner, and can
be calculated in terms of the spectral radius of $\Phi$.

##### Discussion.

In contrast to most other differentiable optimization methods surveyed in this
survey paper, the analytical approaches in this subsection allow for the
backpropagation of coefficients that specify the constraints as well as the
objective function. For example, ? (?) propose parametric quadratic
programming layers whose linear objective parameters are predicted by previous
layers, and whose constraints are learned through the layer’s own embedded
parameters. This is distinct from most cases of DFL, in which the CO problems
have fixed constraints and no trainable parameters of their own.

Furthermore, the techniques surveyed in this subsection are aimed at computing
the exact gradients of parametric optimization mappings. However, many
applications of DFL contain optimization mappings that are discontinuous and
piecewise-constant. Such mappings, including parametric linear programs (8),
have gradients that are zero almost everywhere and thus do not supply useful
descent directions for SGD training. Therefore, the techniques of this
subsection are often applied after regularizing the problem analytically with
smooth functions, as detailed in the next subsection.

####  3.1.2 Analytical Smoothing of Optimization Mappings

To differentiate through combinatorial optimization problems, the optimization
mapping first has to be smoothed. While techniques such as noise-based
gradient estimation (surveyed in Section 3.1.3) provide smoothing and
differentiation simultaneously, analytical differentiation first incorporates
smooth analytical terms in the optimization problem’s formulation, and then
analytically differentiates the resulting optimization problem using the
techniques discussed in Section 3.1.1.

##### Analytical smoothing of linear programs.

Note that while an LP problem is convex and has continuous variables, only a
finite number of its feasible solutions can potentially be optimal. These
points coincide with the vertices of its feasible polytope (?). Therefore the
mapping $\mathbf{x}^{\star}(\mathbf{\hat{c}})$ in (8), as a function of
$\mathbf{\hat{c}}$, is discontinuous and piecewise constant, and thus requires
smoothing before it can be differentiated through. An approach to do so was
presented in ? (?), which proposes to augment the linear LP objective function
with the Euclidean norm of its decision variables, so that the new objective
takes the following form

$\displaystyle\mathbf{x}^{\star}(\mathbf{c})$
$\displaystyle=\operatorname*{argmax}_{\mathbf{x}}\mathbf{c}^{\top}\mathbf{x}-\mu\lVert\mathbf{x}\rVert^{2}_{2}$
(19a)
$\displaystyle=\operatorname*{argmin}_{\mathbf{x}}\lVert\mathbf{x}-\frac{\mathbf{c}}{\mu}\rVert^{2}_{2}$
(19b)

where the above equality follows from expanding the square and cancelling
constant terms, which do not affect the $\operatorname*{argmax}$. This
provides an intuition as to the effect of such a quadratic regularization: it
converts a LP problem into that of projecting the point
$\frac{\mathbf{c}}{\mu}$ onto the feasible polytope, which results in a
continuous mapping $\mathbf{\hat{c}}\to\mathbf{x}^{\star}(\mathbf{\hat{c}})$.
? (?) then train decision-focused models by solving and backpropagating the
respective quadratic programming problem using the OptNet framework (?), in
order to learn to predict objective parameters with minimal regret. At test
time, the quadratic smoothing term is removed. ? (?) refers to such regret-
based DFL with quadratically regularized linear programs as the _Quadratic
Programming Task Loss_ method (QPTL).

Other forms of analytical smoothing for linear programs can be applied by
adding different regularization functions to the objective function. Other
regularization terms for LPs include the entropy function
$H(\mathbf{x})=\sum_{i}x_{i}\log x_{i}$ and the binary entropy function
$H_{b}(\mathbf{x})=H(\mathbf{x})+H(\mathbf{1}-\mathbf{x})$. To differentiate
the resulting smoothed optimization problems, the framework of ? (?) can be
used. Alternatively, problem-specific approaches, without employing this
framework, have also been proposed. For example, ? (?) propose a method for
problems where $H$ smooths an LP for differentiable sorting and ranking, and ?
(?) propose a way to differentiate using $H_{b}$ for multilabel classification
problems. Both works propose fast implementations for both the forward and
backward passes of the respective optimization problems.

In a related approach, ? (?) propose a general, differentiable LP solver based
on log-barrier regularization. For a parametrized LP of standard form (8),
gradients are computed for the regularized form in which the constraints
$\mathbf{x}\geq\mathbf{0}$ are replaced with log-barrier approximations:

$\displaystyle\mathbf{x}^{\star}(\mathbf{c})=\operatorname*{argmin}_{\mathbf{x}}\mathbf{c}^{\top}\mathbf{x}+\lambda\sum_{i}x_{i}$
(20a) $\displaystyle\text{s.t.}\;\;A\mathbf{x}=\mathbf{b}$ (20b)

While similar in this sense to (?), this method exploits several efficiencies
specific to linear programming, in which the log-barrier term serves a dual
purpose of rendering (20) differentiable and also aiding its solution (?).
Rather than forming and solving this regularized LP problem directly, the
solver uses an interior point method to produce a sequence of log-barrier
approximations to the LP’s homogenous self-dual (HSD) embedding. Early
stopping is applied in the interior point method, producing a solution to (20)
for some $\lambda$, which serves as a smooth surrogate problem for
differentiation. A major advantage of this technique is that it only requires
optimization of a linear program, making it in general more efficient than
direct solution of a regularized problem as in the approaches described above.

##### Analytical smoothing of integer linear programs.

To differentiate through ILPs, ? (?) propose to simply drop the integrality
constraints, and to then smooth and differentiate through the resulting LP
relaxation, which is observed to give satisfactory performance in some cases.
? (?) later extended this work by using a more systematic approach to generate
the LP relaxation of the ILP problem. They use the method of cutting planes to
discover an LP problem that admits the same solution as the ILP. Subsequently,
the method of ? (?) is applied to approximate the LP mapping’s derivatives.
Although this results in enhanced performance with respect to regret, there
are some practical scalability concerns, since the cut generation process is
time consuming but also must be repeated for each instance in each training
epoch.

Although this subsection primarily surveys the smoothing of LPs and ILPs, as
these are the focal points of this paper, note that differentiable relaxation
of other optimization problems has also received attention recently. For
example, differential relaxations of MAXSAT (?, ?) and submodular optimization
problems (?, ?) have been developed to embed these problems into neural
networks.

####  3.1.3 Smoothing by Random Perturbations

A central challenge in DFL is the need for smoothing operations of non-smooth
optimization mappings. In contrast to the DFL techniques surveyed in the
previous subsection, which perform the smoothing operation by adding explicit
regularization functions to the objective functions of optimization problems,
this subsection focuses on techniques that use implicit regularization through
perturbations. These techniques construct smooth approximations of the
optimization mappings by adopting a probabilistic point of view. To introduce
this point of view, the CO problem in this section is not viewed as a mapping
from $\mathbf{c}$ to $\mathbf{x}^{\star}(\mathbf{c})$. Rather, it is viewed as
a function that maps $\mathbf{c}$ onto a probability distribution over the
feasible region $\mathcal{F}$. From this perspective,
$\mathbf{x}^{\star}(\mathbf{c})$ can be viewed as a random variable,
conditionally dependent on $\mathbf{c}$. The motivation behind representing
$\mathbf{x}^{\star}(\mathbf{c})$ as a random variable is that the rich
literature of likelihood maximization with latent variables, in fields such as
Probabilistic Graphical Models (PGMs) (?), can be exploited.

##### Implicit differentiation by perturbation.

One seminal work in the field of PGMs is by ? (?). This work contains an
important proposition, which deals with a setup where a variable
$\bm{\theta}_{1}$ is conditionally dependent on another variable
$\bm{\theta}_{2}$ and the final loss $\mathcal{L}$ is defined on the variable
$\bm{\theta}_{1}$. Let $p(\bm{\theta_{1}}|\bm{\theta_{2}})$ and
$\mathbb{E}[\bm{\theta_{1}}|\bm{\theta_{2}}]$ be the conditional distribution
and the conditional mean of $\bm{\theta}_{1}$. The loss $\mathcal{L}$ is
measured on the conditional mean $\mathbb{E}[\bm{\theta_{1}}|\bm{\theta_{2}}]$
and the goal is to compute the derivative of $\mathcal{L}$ with respect to
$\bm{\theta}_{2}$. ? (?) proposes that the derivative of $\mathcal{L}$ with
respect to $\bm{\theta}_{2}$ can be approximated by the following finite
difference method:

$\frac{dL}{d\bm{\theta_{2}}}\approx\frac{1}{\delta}\Bigg{(}\mathbb{E}[\bm{\theta_{1}}|\big{(}\bm{\theta_{2}}+\delta\frac{d}{d\bm{\theta_{1}}}\big{(}\mathcal{L}(\mathbb{E}[\bm{\theta_{1}}|\bm{\theta_{2}}]\big{)}\big{)}]-\mathbb{E}[\bm{\theta_{1}}|\bm{\theta_{2}}]\Bigg{)}$
(21)

where $\frac{d}{d\bm{\theta_{1}}}[\mathcal{L}(\mathbb{E}[\bm{\theta_{1}}])]$
is the derivative $\mathcal{L}$ with respect to $\bm{\theta}_{1}$ at
$\mathbb{E}[\bm{\theta_{1}}]$. Notice that the first term in (21) is the
conditional mean after perturbing the parameter $\bm{\theta}_{2}$ where the
magnitude of the perturbation is modulated by the derivative of $\mathcal{L}$
with respect to $\bm{\theta}_{1}$. Taking inspiration from this proposition,
by defining a conditional distribution
$p(\mathbf{x}^{\star}(\mathbf{\hat{c}})|\hat{c})$, one can compute the
derivative of the regret with respect to $\mathbf{\hat{c}}$ in the context of
DFL.

To perfectly represent the deterministic mapping
$\mathbf{c}\rightarrow\mathbf{x}^{\star}(\mathbf{c})$, the straightforward
choice is to define a Dirac mass distribution, which assigns all probability
mass to the optimal point and none to other points, i.e.,

$p(\mathbf{x}|\mathbf{c})=\begin{cases}1&\mathbf{x}=\mathbf{x}^{\star}(\mathbf{c})\\\
0&\text{otherwise}\end{cases}$ (22)

##### Differentiation of blackbox combinatorial solvers (DBB).

Note that with the distribution in (22) $\mathbb{E}_{\mathbf{x}\sim
p(\mathbf{x}|\mathbf{c})}[x|c]=\mathbf{x}^{\star}(\mathbf{c})$. Hence, using
conditional probability in the proposition in (21),
$\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))}{d\mathbf{\hat{c}}}$
can be approximated in the following way:

$\displaystyle\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\mathbf{\hat{c}}}))}{d\mathbf{\hat{c}}}\approx\nabla^{(DBB)}\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))=\Bigg{(}\mathbf{x}^{\star}\Big{(}\mathbf{\hat{c}}+\delta\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))}{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}\Big{)}-\mathbf{x}^{\star}\Big{(}\mathbf{\hat{c}}\Big{)}\Bigg{)}$
(23)

The gradient computation technique proposed by ? (?) takes the form of (24).
They interpret it as substituting the jump-discontinuous optimization mapping
with a piece-wise linear interpolation. It is a linear interpolation of the
mapping $\mathbf{\hat{c}}\rightarrow\mathbf{x}^{\star}(\mathbf{\hat{c}})$
between the points $\mathbf{\hat{c}}$ and
$\mathbf{\hat{c}}+\delta\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\mathbf{\hat{c}}}))}{d\mathbf{x}}|_{\mathbf{x}=\mathbf{x}^{\star}(\mathbf{\hat{c}})}$.
? (?) call this ‘differentiation of blackbox’ (DBB) solvers, because this
approach considers the CO solver as a blackbox oracle, i.e., it does not take
into consideration how the solver works internally.

In a subsequent work, ? (?) propose to treat the CO solver as as a negative
identity matrix while backpropagating the loss, i.e., they propose the
following approximation of the derivative:

$\displaystyle\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\mathbf{\hat{c}}}))}{d\mathbf{\hat{c}}}\approx-\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))}{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}$
(24)

However, they notice that such an approach might run into unstable learning
for scale-invariant optimization problems such as LPs and ILPs. To negate this
effect, they suggest multiplying the cost vector with the matrix of the
invariant transformation. In the case of LPs and ILPs this can be achieved by
normalizing the cost vector through projection onto the unit sphere.

##### Perturb-and-MAP.

However, at this point it is worth mentioning that ? (?) assumes, in his
proposition, that the distribution $p(\theta_{1}|\theta_{2})$ in (21) belongs
to the exponential family of distributions (?). Note that the distribution
defined in (22) is not a distribution of the exponential family. Nevertheless,
a tempered softmax (?) distribution belonging to exponential family can be
defined to express the mapping in the following way:

$p_{\tau}(\mathbf{x}|\mathbf{c})=\begin{cases}\frac{\exp(-f(\mathbf{x},\mathbf{c})/\tau)}{\sum_{\mathbf{x}^{\prime}\in\mathcal{F}}\exp(-f(\mathbf{x}^{\prime},\mathbf{c})/\tau)}&\mathbf{x}\in\mathcal{F}\\\
0&\text{otherwise}\end{cases}$ (25)

In this case, the log unnormalized probability mass at each
$\mathbf{x}\in\mathcal{F}$ is proportional to
$\exp(-f(\mathbf{x},\mathbf{c})/\tau)$, the exponential of the negative of the
tempered objective value. The idea behind (25) is to assign a probability to
each feasible solution such that solutions with a better objective value have
a larger probability. The parameter $\tau$ affects the way in which objective
values map to probabilities. When $\tau\to 0$, the distribution becomes the
argmax distribution in (22), when $\tau\to\infty$, the distribution becomes
uniform. In other words, the value of $\tau$ determines how drastically the
probability changes because of a change in objective value. Good values for
$\tau$ are problem-dependent, and thus tuning $\tau$ is advised.

Note that (21) deals with conditional expectation. As in the case of the
tempered softmax distribution, the conditional expectation is not always equal
to the solution to the CO problem, it must be computed first to use the finite
difference method in (21). However, computing the probability distribution
function in (25) is not tractable, as the denominator (also called the
partition function) requires iterating over all feasible points in
$\mathcal{F}$. Instead, ? (?) propose a novel approach, known as _perturb-and-
MAP_ , to estimate the probability using perturbations. It states that the
distribution of the maximizer after perturbing the log unnormalized
probability mass by i.i.d. Gumbel$(0,\epsilon)$ noise has the same exponential
distribution as (25). To make it more explicit, if
$\tilde{\mathbf{c}}=\mathbf{c}+\bm{\eta}$, where the perturbation vector
$\bm{\eta}\overset{\text{i.i.d.}}{\sim}\text{Gumbel}(0,\epsilon)$,

$\mathbb{P}[\mathbf{x}=\operatorname*{argmax}_{\mathbf{x}^{\prime}}-f(\mathbf{x}^{\prime},\tilde{\mathbf{c}})]=p_{\epsilon}(\mathbf{x}|\mathbf{c})$
(26)

The perturb-and-MAP framework can be viewed as a method of stochastic
smoothing (?). A smoothed approximation of the optimization mapping is created
by considering the average value of the solutions of a set of _nearby
perturbed_ points. With the help of (26), the conditional distribution and
hence the conditional mean can be approximated by Monte Carlo simulation.

##### Differentiable perturbed optimizers.

? (?) propose another approach for perturbation-based differentiation. They
name it differentiable perturbed optimizers (DPO). They make use of the
perturb-and-MAP framework to draw samples from the conditional distribution
$p(\mathbf{x}|\mathbf{c})$. In particular, they use the reparameterization
trick (?, ?) to generate samples from $p(\mathbf{x}|\mathbf{c})$. The
reparameterization trick uses a change of variables to rewrite $\mathbf{x}$ as
a _deterministic function_ of $\mathbf{c}$ and a random variable $\bm{\eta}$.
In this reformulation, $\mathbf{x}$ is still a random variable, but the
randomness comes from the variable $\bm{\eta}$. They consider $\bm{\eta}$ to
be a random variable having a density proportional to $\exp(-\nu(\bm{\eta}))$
for a twice-differentiable function $\nu$. Moreover, they propose to multiply
the random variable $\bm{\eta}$ with a temperature parameter $\epsilon>0$,
which controls the strength of perturbing $\mathbf{c}$ by the random variable
$\bm{\eta}$. In summary, first $\mathbf{c}$ is perturbed with random
perturbation vector $\epsilon\bm{\eta}$, where $\bm{\eta}$ is sampled from the
aforementioned density function, and then the maximizer of the perturbed
vector $c+\epsilon\bm{\eta}$ is viewed as a sample from the conditional
distribution, i.e.,
$\mathbf{x}^{\star}_{\epsilon}(\mathbf{c})=\mathbf{x}^{\star}(\mathbf{c}+\epsilon\bm{\eta})$
is considered as a sample drawn from $p(\mathbf{x}|\mathbf{c})$ for given
values of $\mathbf{c}$ and $\epsilon$. They call
$\mathbf{x}^{\star}_{\epsilon}(\mathbf{c})$ a _perturbed optimizer_. Note
that, for $\epsilon\to 0$,
$\mathbf{x}^{\star}_{\epsilon}(\mathbf{c})\to\mathbf{x}^{\star}(\mathbf{c})$.
Like before, $\mathbf{x}^{\star}_{\epsilon}(c)$ can be estimated by Monte
Carlo simulation by sampling i.i.d. random noise $\bm{\eta}^{(m)}$ from the
aforementioned density function. The advantage is that the Monte Carlo
estimate is _continuously_ differentiable with respect to $\mathbf{c}$. This
Monte Carlo estimate $\bar{\mathbf{x}}^{\star}_{\epsilon}(\mathbf{c})$ can be
expressed as:

$\displaystyle\bar{\mathbf{x}}^{\star}_{\epsilon}(\mathbf{c})$
$\displaystyle=\frac{1}{M}\sum_{m=1}^{M}\mathbf{x}^{\star}\Big{(}\mathbf{c}+\epsilon\bm{\eta}^{(m)}\Big{)}$
(27)

Moreover, its derivative can be estimated by Monte Carlo simulation too

$\frac{d\bar{\mathbf{x}}^{\star}_{\epsilon}(\mathbf{c})}{d\mathbf{c}}=\frac{1}{\epsilon}\frac{1}{M}\sum_{m=1}^{M}\mathbf{x}^{\star}(\mathbf{c}+\epsilon\bm{\eta}^{(m)})\nu^{\prime}(\bm{\eta}^{(m)})^{\top}$
(28)

where $\nu^{\prime}$ is the first order derivative of $\nu$. They can
approximate $\frac{d\mathbf{x}^{\star}(\mathbf{c})}{d\mathbf{c}}$ by
$\frac{d\bar{\mathbf{x}}^{\star}_{\epsilon}(\mathbf{c})}{d\mathbf{c}}$ to
implement the backward pass. As mentioned before, if $\epsilon\to 0$, the
estimation will be an unbiased estimate of $\mathbf{x}^{\star}(\mathbf{c})$.
However, in practice, for low values of $\epsilon$, the variance of the Monte-
Carlo estimator will increase, leading to unstable and noisy gradients. This
is in line with the smoothing-versus-accuracy trade-off mentioned before. ?
(?) use this DPO framework to differentiate any CO problem with linear
objective. For a CO problem with discrete feasible space, they consider the
convex hull of the discrete feasible region. Furthermore, ? (?) construct the
Fenchel-Young loss function and show for Fenchel-Young loss function, the
gradient can be approximated in the following way:

$\displaystyle\nabla\mathcal{L}^{FY}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))=-\big{(}\bar{\mathbf{x}}^{\star}_{\epsilon}(\mathbf{\hat{c}})-\mathbf{x}^{\star}(\mathbf{c})\big{)}$
(29)

In a later work, ? (?) extend the perturbation approach, where they consider
multiplicative perturbation. This is useful when the cost parameter vector is
restricted to be non-negative, such as in the applications of shortest path
problem variants. The work of ? (?) can also be viewed as an extension of the
DPO framework. They introduce stochastic softmax tricks (SST), a framework of
Gumbel-softmax distributions, where they propose differentiable methods by
sampling from more complex categorical distributions.

##### Implicit maximum likelihood estimation (I-MLE).

The _perturb-and-MAP_ framework is also used by ? (?). However, they do not
sample noise from the Gumbel distribution, rather they report better results
when the noise $\bm{\eta}^{\gamma}$ is sampled from a _Sum-of-Gamma_
distribution with hyperparameter $\gamma$. Combining the finite difference
approximation (21) with the perturb-and-MAP framework, the gradient takes the
following form:

$\displaystyle\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))}{d\mathbf{\hat{c}}}\approx\nabla^{(IMLE)}\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))=\Bigg{(}\mathbf{x}^{\star}\Big{(}\mathbf{\hat{c}}+\delta\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))}{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}+\epsilon\bm{\eta}^{\gamma}\Big{)}-\mathbf{x}^{\star}\Big{(}\mathbf{\hat{c}}+\epsilon\bm{\eta}^{\gamma}\Big{)}\Bigg{)}$
(30)

where $\delta$ is the step size of the finite difference approximation and
$\epsilon>0$ is a temperature parameter, which controls the strength of noise
perturbation. Clearly, (30) turns into (24) when there is no noise
perturbation, i.e., if $\bm{\eta}^{\gamma}=0$. A later work (?) extends I-MLE
by adaptively selecting $\delta$ based on the ratio between the norm of the
parameter $\mathbf{\hat{c}}$ and the norm of
$\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))}{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}$.

##### Discussion.

One major advantage of the techniques explained in this subsection is that for
gradient computation, they call the CO solver as a ‘blackbox oracle’ and only
use the solution returned by it for gradient computation. In essence, these
techniques are not concerned with how the CO problem is solved. The users can
utilize any techniques of their choice—constraint programming (CP) (?),
Boolean satisfiability (SAT) (?) or linear programming (LP) and integer linear
programming (ILP) to solve the CO problem.

####  3.1.4 Differentiation of Surrogate Loss Functions

The techniques explained in the preceding subsections can be viewed as
implementations of differentiable optimization layers, which solve the CO
problem in the forward pass and return useful approximations of
$\frac{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}{d\mathbf{\hat{c}}}$ in the
backward pass. Consequently, those techniques can be used to introduce
optimization layers _anywhere in a neural network architecture_ , and can be
combined with arbitrary loss functions. In contrast, the techniques that will
be introduced next can only be used to differentiate regret (3)—a specific
task loss. Hence, models can only be trained in an end-to-end fashion using
these techniques when the CO problem occurs in the final stage of the
pipeline, as in the case of Predict-Then-Optimize problems. Also note that the
computation of the regret requires both the ground-truth cost vector
$\mathbf{c}$; as well as ground-truth solution
$\mathbf{x}^{\star}(\mathbf{c})$. If $\mathbf{c}$ is observed,
$\mathbf{x}^{\star}(\mathbf{c})$ can be computed. However, if only
$\mathbf{x}^{\star}(\mathbf{c})$ is observed, $\mathbf{c}$ cannot directly be
recovered. Hence, the techniques that will be discussed next are not suitable
when the true cost vectors $\mathbf{c}$ are not observed in the training data.

##### Smart “Predict, Then Optimize”.

? (?) develop Smart “Predict, Then Optimize” (SPO), a seminal work in DFL. As
the gradient of the regret with respect to cost vector $\mathbf{\hat{c}}$ is
zero almost everywhere, SPO instead uses a surrogate loss function that has
subgradients which are useful in training. They start by proposing a convex
surrogate upper bound of regret, which they call the SPO+ loss.

$\mathcal{L}_{SPO+}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))=2\mathbf{\hat{c}}^{\top}\mathbf{x}^{\star}(\mathbf{c})-\mathbf{c}^{\top}\mathbf{x}^{\star}(\mathbf{c})+\max_{\mathbf{x}\in\mathcal{F}}\\{\mathbf{c}^{\top}\mathbf{x}-2\mathbf{\hat{c}}^{\top}\mathbf{x}\\}$
(31)

? (?) directly minimize $\mathcal{L}_{SPO+}$ for a linear predictive model.
However, they note that directly minimizing $\mathcal{L}_{SPO+}$ is
prohibitive for complex predictive models such as NNs. Hence, they derive the
following useful subgradient of
$\mathcal{L}_{SPO+}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))$:

$\displaystyle\mathbf{x}^{\star}(\mathbf{c})-\mathbf{x}^{\star}(2\mathbf{\hat{c}}-\mathbf{c})\in\partial\mathcal{L}_{SPO+}$
(32)

This subgradient is used in the backward pass for training NNs. While this
technique proposes a surrogate loss function, one could also view the solving
of $\mathbf{x}^{\star}(2\mathbf{\hat{c}}-\mathbf{c})$ as solving of
$\mathbf{\hat{c}}$ perturbed by the deterministic perturbation vector
$\mathbf{\hat{c}}-\mathbf{c}$.

From a theoretical point of view, the SPO+ loss has the Fisher consistency
property with respect to the regret under certain distributional assumptions.
A surrogate loss function satisfies the Fisher consistency property if the
function that minimizes the surrogate loss also minimizes the true loss in
expectation (?). Concretely, this means that minimizing the SPO+ loss
corresponds to minimizing the regret in expectation. While training ML models
with a finite dataset, an important property of considerable interest would be
_risk bounds_ (?). ? (?) develop risk bounds for SPO+ loss and show that low
excess SPO+ loss risk translates to low excess regret risk. Furthermore, ? (?)
develop worst-case generalization bounds of the SPO loss.

The SPO framework is applicable not only to LPs, but to _any CO problems where
the cost parameters appear linearly in the objective function_. This includes
QPs, ILPs and MILPs. ? (?) empirically investigated how the framework performs
on ILP problems. However, as these problems are much more computationally
expensive to solve than the ones considered by ? (?), they compared the
standard SPO framework with a variant in which, it is significantly cheaper to
solve the CO problem during training. To be specific, they consider LP
relaxations of the ILPs. These LP relaxations are obtained by considering the
continuous relaxation of the ILPs, i.e., they are variants of the ILPs in
which the integrality constraints are dropped. Using the LP relaxations
significantly expedite training, without any cost: ? (?) did not observe a
significant difference in the final achieved regret between these two
approaches, with both of them performing better than the prediction-focused
approach. However, one should be cautious to generalize this result across
different problems, as it might be dependent on the integrality gap between
the ILP and its LP relaxation.

Next, within this category, a different type of DFL techniques is being
surveyed. In these DFL techniques, the surrogate loss functions are supposed
to reflect the decision quality, but their computations do _not_ involve
solving the CO problems, thereby avoiding the zero-gradient problem.

##### Noise contrastive estimation.

One such approach is introduced by ? (?). Although their aim is still to
minimize regret, computation of
$\nabla_{\mathbf{\hat{c}}}\mathit{Regret}\;(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})$
has been avoided by using a surrogate loss function. In their work, the CO
problem is viewed from a probabilistic perspective, as in (25). However,
instead of maximum likelihood estimation, the noise contrastive estimation
(NCE) (?) method is adopted. NCE has been extensively applied in many
applications such as language modeling (?), information retrieval (?) and
entity linking (?). Its basic idea is to learn to discriminate between data
coming from the true underlying distribution and data coming from a noise
distribution. In the context of DFL, this involves contrasting the likelihood
of ground-truth solution $\mathbf{x}^{\star}(\mathbf{c})$ and a set of
negative examples $S$. In other words, the following ratio is maximized:

$\max_{\mathbf{\hat{c}}}\sum_{\mathbf{x}^{\prime}\in
S}\frac{p_{\tau}(\mathbf{x}^{\star}(\mathbf{c})|\mathbf{\hat{c}})}{p_{\tau}(\mathbf{x}^{\prime}|\mathbf{\hat{c}})}$
(33)

where $\mathbf{x}^{\prime}\in S$ is a negative example. Because the
probability $p_{\tau}(\mathbf{x}^{\star}(\mathbf{c})|\mathbf{\hat{c}})$ is
defined as in (25), when $\tau=1$, maximizing (33) corresponds to minimizing
the following loss:

$\displaystyle\mathcal{L}_{NCE}(\mathbf{\hat{c}},\mathbf{c})=\sum_{\mathbf{x}^{\prime}\in
S}f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{\hat{c}})-f(\mathbf{x}^{\prime},\mathbf{\hat{c}})$
(34)

In other words, this approach learns to predict a $\mathbf{\hat{c}}$ for which
ground-truth solution $\mathbf{x}^{\star}(\mathbf{c})$ achieves a good
objective value, and for which other feasible solutions $\mathbf{x}^{\prime}$
achieve worse objective values. Note that when
$f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{\hat{c}})\leq
f(\mathbf{x}^{\prime},\mathbf{\hat{c}})$ for all
$\mathbf{x}^{\prime}\in\mathcal{F}$, it holds that
$\mathbf{x}^{\star}(\mathbf{c})=\mathbf{x}^{\star}(\mathbf{\hat{c}})$, and
thus the regret is zero. Also note that computing
$\mathcal{L}_{NCE}(\mathbf{\hat{c}},\mathbf{c})$ does not involve computing
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$, circumventing the zero-gradient
problem.

As an alternative to NCE, ? (?) also introduce a maximum a posteriori (MAP)
approximation, in which they only contrast the ground-truth solution with the
most probable negative example from $S$ according to the current model:

$\displaystyle\mathcal{L}_{MAP}(\mathbf{\hat{c}},\mathbf{c})$
$\displaystyle=\max_{\mathbf{x}^{\prime}\in
S}f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{\hat{c}})-f(\mathbf{x}^{\prime},\mathbf{\hat{c}})$
$\displaystyle=f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{\hat{c}})-f(\mathbf{x}^{\prime},\mathbf{\hat{c}})\text{
where }\mathbf{x}^{\prime}=\operatorname*{argmin}_{\mathbf{x}\in
S}f(\mathbf{x},\mathbf{\hat{c}})$ (35)

Note that whenever $\mathbf{x}^{\star}(\mathbf{\hat{c}})\in S$, it holds that
$\mathcal{L}_{MAP}(\mathbf{\hat{c}},\mathbf{c})=f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{\hat{c}})-f(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{\hat{c}})$.
This is also known as self-contrastive estimation (SCE) (?) since the ground-
truth is contrasted with the most likely output of the current model itself.

Also note that for optimization problems with a linear objective, the losses
are
$\mathcal{L}_{NCE}(\mathbf{\hat{c}},\mathbf{c})=\sum_{\mathbf{x}^{\prime}\in
S}\mathbf{\hat{c}}^{\top}(\mathbf{x}^{\star}(\mathbf{c})-\mathbf{x}^{\prime})$
and
$\mathcal{L}_{MAP}(\mathbf{\hat{c}},\mathbf{c})=\mathbf{\hat{c}}^{\top}(\mathbf{x}^{\star}(\mathbf{c})-\mathbf{x}^{\prime})$,
where $\mathbf{x}^{\prime}=\operatorname*{argmin}_{\mathbf{x}\in
S}f(\mathbf{x},\mathbf{\hat{c}})$. In order to prevent the model from simply
learning to predict $\mathbf{\hat{c}}=\mathbf{0}$, the following alternate
loss functions are proposed for these kinds of problems:

$\displaystyle\mathcal{L}_{NCE}^{(\mathbf{\hat{c}}-\mathbf{c})}(\mathbf{\hat{c}},\mathbf{c})=\sum_{\mathbf{x}^{\prime}\in
S}(\mathbf{\hat{c}}-\mathbf{c})^{\top}(\mathbf{x}^{\star}(\mathbf{c})-\mathbf{x}^{\prime})$
(36)

$\displaystyle\mathcal{L}_{MAP}^{(\mathbf{\hat{c}}-\mathbf{c})}(\mathbf{\hat{c}},\mathbf{c})=\max_{\mathbf{x}^{\prime}\in
S}(\mathbf{\hat{c}}-\mathbf{c})^{\top}(\mathbf{x}^{\star}(\mathbf{c})-\mathbf{x}^{\prime})$
(37)

##### Construction of $S$.

Forming $S$ by sampling points from the feasible region $\mathcal{F}$ is a
crucial part of using the contrastive loss functions. To this end, ? (?)
proposes to construct $S$ by caching all the optimal solutions in the training
data. That is why they name $S$ as ‘solution cache’. While training, more
feasible points are gradually added to $S$ by solving for some of the
predicted cost vectors. However, in order to avoid computational cost, the
solver call is not made for each predicted cost during training. Whether to
solve for a predicted cost vector is decided by pure random sampling, i.e., is
based on a biased coin toss with probability $p_{solve}$. Intuitively, the
$p_{solve}$ hyperparameter determines the proportion of instances for which
the CO problem is solved during training. Experimentally, it has been reported
that $p_{solve}=5\%$ of the time is often adequate, which translates to
solving for only $5\%$ of the predicted instances. This translates to reducing
the computational cost by approximately $95\%$, since solving the CO problems
represents the major bottleneck in terms of computation time in DFL training.

##### Approximation of a solver by a solution-cache.

Furthermore, ? (?) propose a solver-free training variant for any DFL
technique that treats the CO solver as a blackbox oracle. Such techniques
include the aforementioned I-MLE, DBB, SPO. In this solver-free
implementation, solving the CO problem is substituted with a cache lookup
strategy, where the minimizer within the cache $S\subset\mathcal{F}$ is
considered as a proxy for the solution to the CO problem (i.e., the minimizer
within $\mathcal{F}$). This significantly reduces the computational cost as
solving an CO problem is replaced by a linear search within a limited cache.
Such an approximation can be useful in case the CO problem takes long to
solve.

Technique |  CO Problem Forms | Computation of Gradient |  Differentiable Optimization Layer
---|---|---|---
OptNet (?) | Convex QPs |  Implicit differentiation of KKT conditions | ✔
Cvxpylayers (?) |  Convex problems |  Implicit differentiation of HSD of conic programs | ✔
Fold-opt (?) |  Convex and nonconvex problems |  Implicit differentiation based on unrolling | ✔
QPTL (?) | LPs, ILPs |  Implicit differentiation after transforming into QPs by adding regularizer | ✔
Intopt (?) | LPs, ILPs |  Implicit differentiation of HSD of (relaxed) LPs by adding log-barrier relaxation | ✔
Mipaal (?) | ILPs |  Conversion of ILPs into LPs by method of cutting planes before applying QPTL | ✔
DBB (?) |  Optimization problems with a linear objective |  Differentiation of linear interpolation of optimization mapping | ✔
Negative identity (?) |  Optimization problems with a linear objective |  Treating the CO solver as negative identity mapping | ✔
I-MLE (?) |  Optimization problems with a linear objective |  Finite difference approximation with perturb-and-MAP | ✔
DPO (?) |  Optimization problems with a linear objective |  Differentiation of perturbed optimizer | ✔
FY (?) |  Optimization problems with a linear objective |  Differentiation of perturbed Fenchel-Young loss | ✘
SPO (?) |  Optimization problems with a linear objective |  Differentiation of surrogate SPO+ loss | ✘
NCE (?) |  Generic optimization problems |  Differentiation of surrogate contrastive loss | ✘
LTR (?) |  Generic optimization problems |  Differentiation of surrogate LTR loss | ✘
LODL (?) |  Generic optimization problems |  Differentiation of a learned convex local surrogate loss | ✘

Table 1: A concise overview of gradient modeling techniques in key DFL
techniques that use gradient-based learning.

##### DFL as a learning to rank (LTR) problem.

In a later work, ? (?) observe that $\mathcal{L}_{NCE}$ (34) can be derived by
formulating DFL as a pairwise learning to rank task (?). The learning to rank
task consists of learning the implicit order over the solutions in $S$ invoked
by the objective function values achieved by the solutions with respect to
$\mathbf{c}$. In other words, it involves learning to predict a
$\mathbf{\hat{c}}$ that ranks the solutions in $S$ similarly to how
$\mathbf{c}$ ranks them. In the pairwise approach,
$\mathbf{x}^{\star}(\mathbf{c})$ and any $\mathbf{x}^{\prime}\in S$ are
treated as a pair and the model is trained to predict $\mathbf{\hat{c}}$ such
that the ordering of each pair is the same for $\mathbf{c}$ and
$\mathbf{\hat{c}}$. The loss is considered to be zero if
$\mathbf{\hat{c}}^{\top}\mathbf{x}^{\star}(\mathbf{c})$ is smaller than
$\mathbf{\hat{c}}^{\top}\mathbf{x}^{\prime}$ by at least a margin of
$\Theta>0$. The pairwise loss is formally defined in the following form:

$\displaystyle\mathcal{L}_{\text{Pairwise}}(\mathbf{\hat{c}},\mathbf{c})=\sum_{\mathbf{x}^{\prime}\in
S}\max\left(0,\Theta+(f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{\hat{c}})-f(\mathbf{x}^{\prime},\mathbf{\hat{c}}))\right)$
(38)

Another loss function is formulated by considering the difference in
differences between the objective values at the true optimal
$\mathbf{x}^{\star}(\mathbf{c})$ and non-optimal $\mathbf{x}^{\prime}$ with
$\mathbf{c}$ and $\mathbf{\hat{c}}$ as the parameters.

$\displaystyle\mathcal{L}_{\text{PairwiseDifference}}(\mathbf{\hat{c}},\mathbf{c})=\sum_{\mathbf{x}^{\prime}\in
S}\bigg{(}\big{(}f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{\hat{c}})-f(\mathbf{x}^{\prime},\mathbf{\hat{c}})\big{)}-\big{(}f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{c})-f(\mathbf{x}^{\prime},\mathbf{c})\big{)}\bigg{)}^{2}$
(39)

Further, motivated by the listwise learning to rank task (?), a loss function
is proposed by ? (?) where the ordering of all the items in $S$ is considered,
rather than the ordering of pairs of items. ? (?) define this listwise loss
based on a _top-one probability_ measure. The top-one probability of an item
is the probability of it being the best of the set. Note that such
probabilistic interpretation in the context of DFL is already defined in
Section 3.1.3. ? (?) make use of the tempered softmax probability defined in
(25). Recall that this $p_{\tau}(\mathbf{x}|\mathbf{c})$ can be interpreted as
a probability measure of $\mathbf{x}\in\mathcal{F}$ being the minimizer of
$f(\mathbf{x},\mathbf{c})$ in $\mathcal{F}$ for a given $\mathbf{c}$. However,
as mentioned before, direct computation of $p_{\tau}(\mathbf{x}|\mathbf{c})$
requires iterating over all feasible points in $\mathcal{F}$, which is
intractable. Therefore ? (?) compute the probability with respect to
$S\subset\mathcal{F}$. This probability measure finally is used to define a
listwise loss—the cross-entropy loss between $p_{\tau}(\mathbf{x}|\mathbf{c})$
and $p_{\tau}(\mathbf{x}|\mathbf{\hat{c}})$, the distributions obtained for
ground-truth $\mathbf{c}$ and predicted $\mathbf{\hat{c}}$. This can be
written in the following form:

$\displaystyle\mathcal{L}_{\text{Listwise}}(\mathbf{\hat{c}},\mathbf{c})=\bigg{(}-\frac{1}{|S|}\sum_{\mathbf{x}^{\prime}\in
S}p_{\tau}(\mathbf{x}^{\prime}|\mathbf{c})\log
p_{\tau}(\mathbf{x}^{\prime}|\mathbf{\hat{c}})\bigg{)}$ (40)

The main advantage of (34), (35), (38), (39) and (40) is that they are
differentiable and can be computed directly by any neural network library via
automatic differentiation. Also note that the computation and differentiation
of the loss functions are solver-free, i.e., they need not solve the CO
problem to compute the loss or its derivative.

##### Learning efficient surrogate losses.

Another research direction without optimization in the loop focuses on
minimizing the computational burden of solving the CO problems repeatedly.
This is achieved by devising efficiently computable and differentiable
surrogate losses that approximate and substitute the true task loss. In this
regard, ? (?) propose to learn a surrogate of the regret function using
parametric local losses. Due to the difficulty of learning a single convex
surrogate function to estimate regret, a convex local surrogate is learned for
each data point in training, based on other points sampled around these data
points. By design, the surrogate losses are automatically differentiable, and
thus they eliminate the need for a differentiable optimization solver. In
subsequent work, ? (?) extended on this, by improving the sample efficiency of
learning the surrogate losses, and by introducing a manner of producing
surrogate losses that are faithful to the true regret also outside of the
local neighbourhoods around the training examples.

##### DFL as a learning to optimize problem.

DFL is viewed as an extension of learning to optimize (LtO) by ? (?). In LtO,
the goal is to train an ML model as an approximate CO solver, which maps the
parameters of a CO problem to its optimal solution. ? (?) show that the
technique of LtO can be applied to the DFL setting, by treating the feature
variables $\mathbf{z}$ as inputs to the LtO model, which predicts
$\mathbf{x}^{\star}(\mathbf{c})$. The resulting LtO models function as joint
prediction and optimization models, whose training is consistent with regret
minimization on the DFL task.

### Discussion

So far, in this subsection, an extensive overview of different gradient-based
DFL techniques has been provided. For the ease of the readers, a summary of
some of the key DFL techniques, discussed so far, have been provided in Table
1. The second column of Table 1 highlights the form of the CO problem
applicable to the technique. Note that although some techniques are generally
applicable to any CO problem forms, most techniques have been evaluated so far
using CO problems with linear objective functions. The third column summarizes
the gradient computation technique. The fourth column indicates whether that
particular technique is compatible with any generic task loss. Techniques,
termed as implementations of _differentiable optimization layers_ , can be
embedded in any stage of an NN architecture. The other techniques are
applicable where optimization is the final stage of the pipeline (such as in
Predict-Then-Optimize problem formulations) and a particular loss (most often
regret) is used as the task loss.

###  3.2 Review of Gradient-free DFL Methodologies

The techniques reviewed so far implement DFL by gradient descent training,
which is the go-to approach for training neural networks. Next, we review DFL
techniques, which do not rely on gradient-based training. Note that, since
these techniques do not utilize gradient-based training, the predictive models
in most cases consist of either tree-based methods or explicitly specified
models such as linear models.

First of all, as $\mathcal{L}_{SPO+}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))$ is
a convex loss function, it can be minimzed outside gradient-based training if
the predicive model is linear. Firstly, since
$\mathcal{L}_{SPO+}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))$ is a convex loss
function, it can be minimized using any convex solver without using gradient-
based training _if_ the predictive model is linear. ? (?) extend SPO
considering the predictive model to be a decision tree or ensemble of decision
trees. Such models can be learned by recursive partitioning with respect to
the regret directly, and thus do not require the use of the SPO+ surrogate
loss function introduced by ? (?). Alternatively, the tree learning problem
can be posed as a MILP and be solved by an off-the-shelf solver. ? (?)
formulate the problem of minimizing regret as a mixed-integer linear program
(MILP) for a linear predictive model. They start from the bilevel optimization
formulation, introduced in (6a) and (6b). First, the transition points where
the solution of the lower level program (6b) changes are identified, and then
the solution space is exhaustively partitioned, and for each partition the
solution is annotated. This paves the way to construct a MILP formulation of
the outer program (6a). This MILP problem is solved to learn the parameters
$\bm{\omega}$ of the linear predictive model. The resulting model is
guaranteed to be globally optimal, which is not the case for gradient-based
methods that might get stuck in a local optimum. However, their method is
limited to ML models that are linear and optimization problems that are binary
MILPs.

? (?) consider linear ML models and represent the objective function of the CO
problem as a piece-wise linear function of the ML parameters. In this proposed
technique, the ML parameters are updated via a coordinate descent algorithm,
where each component of the cost vector is updated at a time to minimize the
regret keeping other components fixed. This technique requires identifying the
_transition points_ , where regret changes, as a function of each component of
the cost parameter. ? (?) consider CO problems that can be solved by dynamic
programming and identify the transition points using dynamic programming. In a
later work, ? (?) extend this technique by employing a ‘divide-and-conquer’
algorithm to identify the transition points for CO problems whose objective
function is a bilinear function of the decision variables and the predicted
parameters. This development generalizes the previous work (?) to cover a much
broader class of CO problems and offers a substantial speed improvement. The
‘branch & learn’ approach (?) also extends the approach by ? (?) by developing
a recursive algorithm, allowing to tackle CO problems that can be solved by
recursion.

###  3.3 Other Aspects of Decision-Focused Learning

In the following, some aspects related to DFL, that have not yet been
discussed in this survey paper so far, will be highlighted. To begin with, it
should be noted that certain CO problems may have _multiple non-unique optimal
solutions_ for a given cost vector. This can occur for an LP when the cost
vector of an LP is parallel to one of the faces of the feasible polyhedron.
Moreover, problems involving symmetric graphs, whose solution can be
transformed into other solutions through automorphisms (?), exhibit multiple
optimal solutions. If the predicted cost vector has multiple non-unique
optimal solutions, each of these solutions result in different values of
regret. In such scenarios, ? (?) propose to consider the worst-case regret. If
the set of optimal solutions of $\mathbf{\hat{c}}$ is be represented by
$\mathcal{X}^{\star}(\mathbf{\hat{c}})$, the worst-case regret can be defined
in the following form:

$\mathit{Regret}\;(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})=\max_{\mathbf{x}^{\star}(\mathbf{\hat{c}})\in\mathcal{X}^{\star}(\mathbf{\hat{c}})}f(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})-f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{c})$
(41)

Having addressed the possibility of the presence of multiple non-unique
optimal solutions in a CO problem, the focus now turns to other important
facets of DFL.

####  3.3.1 Prediction-focused vs. Decision-focused learning

DFL methodologies are expected to deliver lower regret than a PFL approach in
Predict-Then-Optimize problems, as the ML model is directly trained to achieve
low regret. However, as discussed before, the implementation of DFL poses
significant challenges. In fact, practitioners may be tempted to resort to a
PFL approach to circumvent the computational costs associated with DFL, when
dealing with real-world Predict-Then-Optimize problems. To motivate adoption
of DFL methodologies among practitioners, it is crucial to investigate
scenarios where DFL methodologies outperform the PFL approach. To this end, ?
(?) conduct a theoretical comparison of the limiting distributions of the
optimality gaps between the two approaches in the context of stochastic
optimization. They show the PFL approach that does not consider the CO problem
while training the model asymptotically outperforms the integrated prediction
and optimization approach, employed by DFL methodologies, _if_ the underlying
prediction model is well-specified. This is intuitive, as a well-specified
model tends to produce highly accurate predictions, which can contribute to
the success of the PFL approach. In such cases, the DFL methodologies might
perform worse than PFL since training in DFL involves _approximate_ gradients
(because the true gradient is zero almost everywhere), whereas the gradient is
well-defined for a PFL approach. On the other hand, they show that if the
model is not well-specified, a PFL approach performs suboptimally compared to
the DFL approach. Hence, it is recommended to use DFL when there exists
aleatoric or epistemic uncertainty. As most real-world settings include
various sorts of uncertainty—both aleatoric and epistemic—DFL methodologies
are expected to outperform the PFL approach. In a separate work, ? (?) show
that the suboptimality of PFL becomes more pronounced in the presence of
correlations between the predicted parameters.

####  3.3.2 Multi-task decision-focused learning

In most DFL works, a single task is considered. For instance, in the shortest
path benchmark considered by ? (?), the grid structure and the start and end
nodes are the same in all instances. However, one often has to deal with
multiple tasks at once, in which it would be convenient to make decision-
focused predictions, without having to train a separate model for each task. A
first step in this direction was recently taken by ? (?). They propose a way
of training a model in a decision-focused way with respect to multiple tasks
at once by considering two kinds of architectures. The first is a regular
multi-layer perceptron that outputs a single vector $\mathbf{\hat{c}}$ which
is used in the different tasks. The different resulting task losses then get
aggregated to inform the update to weights $\bm{\omega}$, i.e., the weights
$\bm{\omega}$ are trained to produce a $\mathbf{\hat{c}}$ that generally works
well for the different tasks considered. The second architecture is a multi-
headed one, consisting of one or more shared first layers, followed by a
dedicated head for every task. This produces a different vector $\hat{c}_{i}$
for every task. Their results show that they can train a model that can make
effective decision-focused predictions for multiple tasks at once, and that
this is particularly beneficial when not that many training data are
available. However, a remaining limitation is that the model can still not be
trained with the aim of generalizing to new tasks.

A related topic is studied by ? (?), which focuses on DFL in the context of
fair multiobjective optimization. In the presence of multiple objective
functions, many applications call for pareto-optimal solutions which are
‘fair’ with respect to the competing objective functions. In such cases, it is
common to optimize the Ordered Weighted Average (OWA) of those functions,
which guarantees ‘equitably efficient’ solutions (?). Incorporating OWA
optimization in DFL faces a unique challenge, since the OWA objective itself
is nondifferentiable. ? (?) mitigate by replacing the OWA function by its
smooth Moreau envelope approximation. This yields a differentiable approximate
OWA optimization, and enables joint DFL learning of each individual objective
function’s parameters to minimize regret of their fair OWA aggregation.

####  3.3.3 Predicting parameters in the constraints

The majority of the works in DFL aim to predict parameters in the objective
function and assume that the feasible space is known. However, in many
applications the unknown parameters occur in the constraints as well as in the
objectives. When the parameters in the constraints are predicted and
prescribed decisions are made using the predicted parameters, one major issue
is that the prescribed decisions might turn out to be _infeasible_ with
respect to the true parameters. In this case, task loss to minimize the
suboptimality of the prescribed decisions is not enough, but it should also
penalize if the prescribed decisions become infeasible. Hence DFL methods for
such problems entails a few additional considerations. The first consideration
deals with quantifying the extent of infeasibility when the prescribed
decisions become infeasible with respect to the true parameters. In this
regard, ? (?) propose to add artificial slack variables with high penalty
costs in the objective function to penalize infeasible decisions. ? (?)
introduce the notion of _post-hoc_ regret. In _post-hoc_ regret a non-negative
penalty is added to regret to account for correcting the infeasible solutions
into feasible ones. This idea of such a corrective actions shares a
fundamental resemblance to the concept of recourse actions in stochastic
programming (?).

The next consideration is computing the gradients of this task loss with
respect to the parameters in the constraints. Some of the techniques discussed
in Section 3.1.1 can be utilized for this purpose. For example, the gradient
can be obtained by solver unrolling. ? (?) compute the gradient by unrolling a
LP. As the parameters in the constraints are also present in the the KKT
conditions (13), it is possible to compute the gradients for optimization
problems, with differentiable constraint functions by differentiating the KKT
conditions using the techniques discussed in Section 3.1.1.

? (?) provide an ERM formulation for predicting parameters in both the
objective function and constraints of an LP. For parameters in the objective
function, the ERM accounts for suboptimality of the decision and for
parameters within the constraints, the ERM formulation considers the
feasibility of optimal points observed in the training data. This ERM
formulation takes the form of a non-linear optimization program and they
propose to compute the derivative of the predicted parameters by considering
its sequential quadratic programming (SQP) approximation. For packing and
covering LPs, ? (?) compute the derivative of _post-hoc_ regret with respect
to the predicted parameters in the constraints by considering the Lagrangian
relaxation of the LP when the corrective action is linear. ? (?) extend this
approach by treating the correction action also as an LP.

The task of computing the gradients of the task loss with respect to the
parameters in the constraints is particularly challenging for combinatorial
optimization problems, which often involve discrete feasible space. For
combinatorial optimization problems, it might happen that no constraints are
active at the optimal point. So, slight changes in the parameters in the
constraints do not change the optimal solution, leading to the problem of zero
gradients. Hence, coming up with meaningful gradients for back-propagation is
more challenging for combinatorial optimization problems. If either the CO
problem or the corrective action is an ILP, ? (?) consider the corresponding
LP relaxation. ? (?) develop a differentiable optimization layer for ILPs that
considers the downstream gradient of the solution as an input and returns the
directions of updating the parameters in the backward pass. They update the
parameters along the directions so that the Euclidean distance between the
solution of the updated parameter and the updated solution with the downstream
gradient is minimized. For ILPs, ? (?) view the task of constraint learning
from the lens of learning hyperplanes, which is common in classification
tasks. Such an approach requires negative samples. However, the negative
samples in this setting must also include infeasible points, which is not the
case for the solution-cache approach reviewed in Section 3.1.4. In the realm
of gradient-free methods, ? (?) apply ‘branch & learn’ (?) to minimize _post-
hoc_ regret considering CO problems, solvable by recursion.

####  3.3.4 Model robustness in decision-focused learning

The issue of model robustness arises often in deep learning. As has been shown
in many works, it is often possible for malicious actors to craft inputs to a
neural network in such a way that the output is manipulated (evasion attacks)
(?), or to generate training data which cause adverse effects on the
performance of the trained model (poisoning attacks). As a subset of ML, some
adversarial settings also apply in DFL.

Evasion attacks, despite being the most commonly studied adversarial attacks,
do not generalize straightforwardly to DFL since they inherently pertain to
classification models with finite output spaces. On the other hand, it is
shown by ? (?) that effective poisoning attacks can be made against DFL
models. The paper shows that while such attacks can be effective, they are
computationally expensive due to the optimization which must be repeatedly
evaluated to form the attacks. On the other hand, it is also demonstrated that
poisoning attacks designed against two-stage models can be transferred to
fully integrated DFL models.

Separately, ? (?) study robustness of decision-focused learning under label
noise. The paper provides bounds on the degradation of regret when test-set
labels are corrupted by noise relative to those of the training set. An
adversarial training scheme is also proposed to mitigate this effect. The
robust training problem is equivalent to finding the equilibrium solution to a
Stackelberg game, in which a figurative adversary applies label noise that is
optimized to raise regret, while the main player seeks model parameters that
minimize regret.

####  3.3.5 Stochastic optimization

Settings in decision-focused learning based on stochastic optimization models
are studied by ? (?). In contrast to more typical settings, the downstream
decision model is considered to be a stochastic optimization problem. In this
formulation, it is only possible to predict parameters of a random
distribution that models the parameters of an optimization problem. For
instance, the mean and variance of load demands in a power scheduling problem
could be modeled as parameters of the optimization problem. Their work shows
how such problems can be converted to DFL with deterministic decision models
and solved using the techniques described in this survey article. To this end,
it also introduces an effective technique for approximating the derivatives
through arbitrary convex optimization problems, by forming and differentiating
their quadratic programming approximations, as computed by sequential
quadratic programming. A more elaborate relation to stochastic optimization is
provided by ? (?) within the context of contextual stochastic optimization.

####  3.3.6 Active learning algorithm for DFL

Active learning concerns ML problems where labeled data are scarce or
expensive to obtain. To address the challenge of limited training data, active
learning algorithms choose the most informative instances for labeling (?). ?
(?) study active learning in DFL paradigm. To identify the features for which
knowing the cost parameter is most beneficial for training, they propose to
use the notion of ‘distance to degeneracy’ (?). Distance to degeneracy
measures how far the predicted cost vector is from the set of cost vectors
that have multiple optimal solutions. They argue that if distance to
degeneracy is higher at a datapoint, there is more certainty regarding the
solution (of the CO problem); hence they propose to acquire the label of a
datapoint if its distance to degeneracy is lower than a threshold.

We end this section with a remark that DFL can be extended to address
optimization problems beyond the ‘classical’ CO problem. For instance, ? (?)
embed $K$-means clustering as a layer in a neural network by differentiating
through the clustering layer, using DFL techniques. ? (?) employ DFL approach
to predict the parameters of Markov decision processes (MDPs).

##  4 Applications of Decision-Focused Learning

The Predict-Then-Optimize problem occurs in many real-world applications, as
optimal decisions can be found by solving CO problems and due to the presence
of uncertainty, some parameters of the CO problems must be estimated. Having
seen the development of DFL for Predict-Then-Optimize problems in the
preceding section, practical uses of DFL in various application domains will
be presented below. As this survey paper reviews DFL techniques, which predict
cost parameters in Section 3, the applications presented below are related
specifically to the task of predicting only the cost parameters.

##### Computer vision.

The DBB framework (?) (reviewed in Section 3.1.3) has been employed in many
interesting computer vision applications. ? (?) use for differentiating rank-
based metrics such as precision and recall, whereas ? (?) and ? (?) use it for
differentiating bipartite matching in deep graph and multi-graph matching
problems respectively in the application of semantic keypoint matching of
images. ? (?) use DBB to differentiate through a multiway cut combinatorial
optimization problem for graph partitioning allowing them to perform end-to-
end panoptic segmentation of images.

##### Fair Learning to Rank.

In learning to rank (LTR), a machine learning model must produce rankings of
documents in response to users’ search queries, in which those most relevant
to a given query are placed in the highest ranking positions. In this setting,
the relevance of documents to queries is often measured empirically by
historical user click rates (?). In fair learning to rank (FLTR), this
relevance-based matching must be performed subject to strict constraints on
the relative exposure between predefined groups. Due to the difficulty of
enforcing such constraints on the outputs of a machine learning model, many
FLTR frameworks resort to a two-stage approach in which prediction of query-
document relevance scores is learned by a typical LTR model without
constraints on fairness of exposure. At test time, the predicted relevance
scores inform the objective of a separate fair ranking optimization program
(?). ? (?) use DFL to unify the prediction of relevance scores with the
subsequent optimization of fair rankings, in an end-to-end model trained by
SPO which learns to map user queries directly to the fair ranking policies
that optimize user relevance. The result is a FLTR model which outperforms
previous penalty-based models in terms of both user relevance and fairness,
with the ability to directly control their trade-offs by modifying the
fairness constraints of the optimization layer.

##### Route optimization.

? (?) present an interesting application, where DFL is used to combat the
challenge of wildlife trafficking. They consider the problem of predicting the
flight trajectory of traffickers based on a given pair of source and
destination airports. It is framed as a shortest path problem in a graph,
where each node is an airport. In the prediction stage, the probability of
using a directed edge $(i,j)$ to leave the node $i$ is predicted. In the
optimization stage, the most likely path from the source to the destination is
found by solving a shortest path problem where the negative log probabilities
are used as edge weights. In this Predict-Then-Optimize formulation, the
probabilities are predicted via DFL, using the DBB framework for gradient
computation.

Solving a shortest path problem by considering the negative log probabilities
as edge weights has also been explored by ? (?). In their work, the objective
is to prescribe most preferred routing in a capacitated vehicle routing
problem (CVRP) (?) for last-mile delivery applications. A high probability
value for the edge $(i,j)$ indicates that it is the preferred edge to leave
the node $i$. However, they do not observe any advantage of the DFL paradigm
over the PFL paradigm and attribute this to the lack of training data
instances (fewer than $200$ instances). DFL is used for last-mile delivery
applications by ? (?) too. However, there the objective is to minimize total
travel time. In the prediction stage, the travel times of all the edges are
predicted and in the optimization stage, the CVRP is solved to minimize the
total travel time. The underlying model is trained using the SPO framework to
directly minimize the total travel time.

##### Maritime transportation.

The inspection of ships by port state control has been framed as a Predict-
Then-Optimize problem by ? (?). Due to limited number of available personnel,
the objective is to identify non-compliant ships that are more likely to be
detained, and then select those ships for inspection. A ship can be found to
be non-compliant by port state control in multiple categories. If a ship is
found to be non-compliant for a category, a ‘deficiency number’ will be
recorded for the ship in that category. In the prediction stage, a linear
model is built to identify deficiency numbers of the ships in all the
categories and in the optimization stage, a CO problem is solved to select
ships maximizing the total ‘deficiency number’. Given the scale of the CO
problem at hand, training with standard SPO framework becomes prohibitive.
Therefore, they employ pairwise-comparison based loss function, similar to Eq.
(38) to implement DFL. Ship maintenance activities by ship owners have been
framed as Predict-Then-Optimize problems by ? (?). The ship owners have to
schedule regular maintenance activities to remain compliant. However, as
maintenance activities are expensive, the objective of identifying categories
that may warrant immediate detentions by the port state control, has been
considered. To do so, in the prediction stage, a random forest model is built
to predict the deficiency number (likelihood of non-compliance) for each
category. In the optimization stage, a CO problem is formulated considering
maintenance cost and detention cost to determine whether maintenance activity
should be scheduled for each category. The random forest models are trained to
directly minimize regret using SPOTs (?).

##### Power and energy systems.

? (?) provide a use-case of DFL in renewable power system application. In
their work, the prediction stage involves the task of generating wind power
forecasts. As these forecasts are further used in power system energy
scheduling, the predictive ML model is directly trained with the objective of
minimizing power system operating costs using cvxpylayers (?). ? (?) observe
that electricity prices are set by regulators by optimizing social welfare
while maintaining a constant energy balance. They formulate this optimization
as a Mixed-Integer Quadratic Program (MIQP) problem and embed the CO problem
into the training loop of an electricity price forecasting framework, which
outperforms the conventional price forecasting approach. By analytically
differentiating the CO problem, they derive a step function as the derivative,
which is used for training the ML model in DFL paradigm. ? (?) consider
another Predict-Then-Optimize problem in power system applications, where
electricity prices are predicted in the prediction stage and the optimization
stage deals with optimal energy storage system scheduling to maximize
arbitrage benefits. Lower values of regret have been reported in their work,
when the prices are predicted using the SPO framework.

##### Communication technology.

DFL is applied to mobile wireless communication technology applications by ?
(?). Fluid antenna systems (?) are one of the recent developments in mobile
wireless communication technology. However, its effectiveness depends on the
position of the radiating element, known as the port. ? (?) frame the port
selection problem as a Predict-Then-Optimize problem, where in the prediction
stage signal-to-noise ratio for each position of the port is predicted and
then the optimal position of the port is decided in the optimization stage.
They use LSTM as the predictive model and report the SPO framework is very
effective for such port selection applications.

##### Solving non-linear combinatorial optimization problems.

? (?) study the problem of learning a linear surrogate optimizer to solve non-
linear optimization problems. The objective is to learn a surrogate linear
optimizer whose optimal solution is the same as the solution to the non-linear
optimization problem. Learning the parameters of the surrogate linear
optimizer entails backpropagating through the optimizer, which is implemented
using cvxpylayers (?).

Further, interested readers are referred to the artcle by ? (?) for more
applications of Predict-Then-Optimize problems in various areas within OR.

##  5 Experimental Evaluation on Benchmark Problemsets

DFL recently has received increasing attention. The methodologies discussed in
Section 3 have been tested so far on several different datasets. Because a
common benchmark for the field has not yet been set up, comparisons among
techniques are sometimes inconsistent. In this section, an effort is made to
propose several benchmark test problems for evaluating DFL techniques. Then
some of the techniques explained in Section 3 are compared on these test
problems.

Problem |  Constraint Functions | Decision Variables | CO SOlver | Predictive Model
---|---|---|---|---
Shortest path problem on a $5\times 5$ grid | Linear | Continuous | OR-Tools | Linear
Portfolio optimization | Quadratic | Continuous | Gurobi | Linear