You will be provided with a reference and some statements. Please determine whether each statement is 'supported', 'unsupported', or 'unknown' with respect to the reference. Please note:
First, assess whether the reference contains any valid content. If the reference contains no valid information, such as a 'page not found' message, then all statements should be considered 'unknown'.
If the reference is valid, for a given statement: if the facts or data it contains can be found entirely or partially within the reference, it is considered 'supported' (data accepts rounding); if all facts and data in the statement cannot be found in the reference, it is considered 'unsupported'.

You should return the result in a JSON list format, where each item in the list contains the statement's index and the judgment result, for example:
[
    {
        "idx": 1,
        "result": "supported"
    },
    {
        "idx": 2,
        "result": "unsupported"
    }
]

Below are the reference and statements:
<reference>
Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities



Report GitHub Issue

×

Title:

Content selection saved. Describe the issue below:

Description:

Submit without GitHub

Submit in GitHub

arXiv is now an independent nonprofit!

Learn more

×

Back to arXiv

Why HTML?

Report Issue

Back to Abstract

Download PDF

Abstract

1
Introduction

Positioning with respect to other overview papers.

Paper organization.

2
Preliminaries

2.1
Problem Setting

2.2
Learning Paradigms

Prediction-focused learning (PFL).

Decision-focused learning (DFL).

Relationship between prediction and task losses.

Example.

Empirical risk minimization and bilevel form of DFL.

2.3
Challenges to Implement Decision-Focused Learning

Differentiation of CO mappings.

Computational cost.

2.4
Optimization Problem Forms

2.4.1
Convex Optimization

2.4.2
Linear Programming

2.4.3
Integer Linear Programming

2.4.4
Integer Nonlinear Programming

3
Review of Decision-Focused Learning Methodologies

3.1
Review of Gradient-Based DFL Methodologies

3.1.1
Analytical Differentiation of Optimization Mappings

Differentiating unconstrained relaxations.

Differentiating KKT conditions of quadratic programs

Differentiating optimality conditions of conic programs.

Solver unrolling and fixed-point differentiation.

Discussion.

3.1.2
Analytical Smoothing of Optimization Mappings

Analytical smoothing of linear programs.

Analytical smoothing of integer linear programs.

3.1.3
Smoothing by Random Perturbations

Implicit differentiation by perturbation.

Differentiation of blackbox combinatorial solvers (DBB).

Perturb-and-MAP.

Differentiable perturbed optimizers.

Implicit maximum likelihood estimation (I-MLE).

Discussion.

3.1.4
Differentiation of Surrogate Loss Functions

Smart “Predict, Then Optimize”.

Noise contrastive estimation.

Construction of
S
S
.

Approximation of a solver by a solution-cache.

DFL as a learning to rank (LTR) problem.

Learning efficient surrogate losses.

DFL as a learning to optimize problem.

3.2
Review of Gradient-Free DFL Methodologies

3.3
Other Aspects of Decision-Focused Learning

3.3.1
Prediction-Focused vs. Decision-Focused Learning

3.3.2
Multi-task Decision-Focused Learning

3.3.3
Predicting Parameters in the Constraints

3.3.4
Model Robustness in Decision-Focused Learning

3.3.5
Stochastic Optimization

3.3.6
Active Learning Algorithm for DFL

4
Applications of Decision-Focused Learning

Computer vision.

Fair Learning to Rank.

Route optimization.

Maritime transportation.

Power and energy systems.

Communication technology.

Solving non-linear combinatorial optimization problems.

5
Experimental Evaluation on Benchmark Problemsets

5.1
Problem Descriptions

5.1.1
Shortest Path Problem on a
5
×
5
5\times 5
grid

Formulation of the optimization problem.

Synthetic data generation process.

Predictive model.

5.1.2
Portfolio Optimization Problem

Formulation of the optimization problem.

Synthetic data generation process.

Predictive model.

5.1.3
Warcraft Shortest Path Problem

Formulation of the optimization problem.

Predictive model.

5.1.4
Energy-Cost Aware Scheduling Problem

Formulation of the optimization problem.

Data description.

Predictive model.

5.1.5
Knapsack Problem

Formulation of the optimization problem.

Data description.

Predictive model.

5.1.6
Diverse Bipartite Matching Problem

Data description.

Predictive model.

5.1.7
Subset Selections

Optimization problem formulation.

Predictive model.

5.2
Experimental Results and Analysis

Experimental setup and procedures.

Evaluation metric.

5.2.1
Comparative Evaluations

Shortest path problem on a
5
×
5
5\times 5
grid.

Portfolio optimization problem.

Warcraft shortest path problem.

Energy-cost aware scheduling.

Knapsack problem.

Diverse bipartite matching.

Learning subset selections.

5.2.2
Comparison on Runtime

5.2.3
Discussion

6
Future Research Directions

Generalizing DFL across related tasks.

Non-linear objective function.

Robust risk-sensitive DFL.

Decision-focused learning by zeroth-order gradient.

Bilevel Optimization Techniques for DFL.

Scalable DFL.

Theoretical guarantees.

Uncertainty in the constraints.

Extending DFL to multistage settings.

DFL with Real-World Multimodal Datasets.

7
Conclusion

A
Results on All Problem Instances

B
Learning Curves

C
Details about Hyperparameter Configuration

References

License: CC BY 4.0

arXiv:2307.13565v4 [cs.LG] 04 Sep 2024

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

\name
Jayanta Mandi
\email
jayanta.mandi@kuleuven.be

†
†
thanks:
JM was affiliated to Vrije Universiteit Brussel,
Belgium during the submision of this article.

Affiliation:
\addr
KU Leuven,
Belgium

\name
James Kotary
\email
jk4pn@virginia.edu

†
†
thanks:
JM and JK should both be considered first authors.

Affiliation:
\addr
University of Virginia,
USA

\name
Senne Berden
\email
senne.berden@kuleuven.be

Affiliation:
\addr
KU Leuven,
Belgium

\name
Maxime Mulamba
\email
maxime.mulamba@vub.be

Affiliation:
\addr
Vrije Universiteit Brussel,
Belgium

\name
Víctor Bucarey
\email
victor.bucarey@uoh.cl

Affiliation:
\addr
Universidad de O’Higgins,
Chile

\name
Tias Guns
\email
tias.guns@kuleuven.be

Affiliation:
\addr
KU Leuven,
Belgium

\name
Ferdinando Fioretto
\email
fioretto@virginia.edu

Affiliation:
\addr
University of Virginia,
USA

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
i
, denoting the
i
th
i^{\text{th}}
item within
𝐱
\mathbf{x}
as
x
i
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,

𝐱
⋆
​
(
𝐜
)
=
argmin
𝐱
\displaystyle\mathbf{x}^{\star}(\mathbf{c})=\argmin_{\mathbf{x}}

f
⁡
(
𝐱
,
𝐜
)
\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
𝐱
⋆
​
(
𝐜
)
∈
ℝ
n
\mathbf{x}^{\star}(\mathbf{c})\in\mathbb{R}^{n}
(
n
n
being the dimension of the decision variable
x
x
), which minimizes the objective function
f
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
𝐜
∈
ℝ
m
\mathbf{c}\in\mathbb{R}^{m}
.

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
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
{
(
𝐳
𝐢
,
𝐜
𝐢
)
}
i
=
1
N
\{(\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
𝝎
m_{\bm{\omega}}
(with trainable ML parameters
𝝎
\bm{\omega}
), so that parameter predictions take the form
𝐜
^
=
m
𝝎
​
(
𝐳
)
\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
𝝎
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
𝝎
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
𝐜
^
=
m
𝝎
​
(
𝐳
)
\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
𝝎
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.

M
​
S
​
E
​
(
𝐜
^
,
𝐜
)
=
1
N
​
‖
𝐜
−
𝐜
^
‖
2
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
​
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐜
)
f(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})
) comes close to the full-information optimal value
f
​
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
)
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}
:

𝑅𝑒𝑔𝑟𝑒𝑡
⁡
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐜
)
=
f
⁡
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐜
)
−
f
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
)
\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
​
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐜
)
f(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})
, since the term
f
​
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
)
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
M
​
S
​
E
​
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐱
⋆
)
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
C
.
This knapsack problem with unit weights can be formulated as follows:

𝐱
⋆
​
(
𝐜
)
=
argmax
𝐱
∈
{
0
,
1
}
𝐜
⊤
​
𝐱
​
s.t.
​
∑
i
x
i
≤
C
\mathbf{x}^{\star}(\mathbf{c})=\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.

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
2.5
and
3
3
respectively. The point
(
2.5
,
3
)
(2.5,3)
, marked with
✱
, represents the true item values.
In this case the true solution is
(
0
,
1
)
(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
)
(1.5,3)
, marked with
✚
, corresponds to predicting
1.5
1.5
and
3
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
)
(2.5,2)
, marked with
✖
, triggers the wrong solution
(
1
,
0
)
(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
)
(1.5,4)
, marked with
▲
, corresponds to overestimating the value of the second item to
4
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
)
(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
𝒟
≡
{
(
𝐳
𝐢
,
𝐜
𝐢
)
}
i
=
1
N
\mathcal{D}\equiv\{(\mathbf{z_{i}},\mathbf{c_{i}})\}_{i=1}^{N}
.
The desired objective of training is to learn a model,
m
𝝎
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
𝝎
⁡
1
N
​
∑
i
=
1
N
‖
m
𝝎
​
(
𝐳
𝐢
)
−
𝐜
𝐢
‖
2
,
\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:

min
𝝎
⁡
1
N
​
∑
i
=
1
N
(
f
⁡
(
𝐱
⋆
​
(
𝐜
^
𝐢
)
,
𝐜
𝐢
)
−
f
⁡
(
𝐱
⋆
​
(
𝐜
𝐢
)
,
𝐜
𝐢
)
)
\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)

s.t.
​
𝐜
^
𝐢
=
m
𝝎
​
(
𝐳
𝐢
)
;
𝐱
⋆
​
(
𝐜
^
𝐢
)
=
argmin
𝐱
∈
ℱ
f
​
(
𝐱
,
𝐜
^
𝐢
)
\displaystyle\texttt{s.t.}\;\;\mathbf{\hat{c}_{i}}=m_{\bm{\omega}}(\mathbf{z_{i}});\ \mathbf{\mathbf{x}^{\star}}(\mathbf{\hat{c}_{i}})=\argmin_{\mathbf{x}\in\mathcal{F}}f(\mathbf{x},\mathbf{\hat{c}_{i}})

(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
d
​
ℒ
d
​
𝝎
\frac{d\mathcal{L}}{d\bm{\omega}}
,
by providing the required chain rule term
d
​
𝐱
⋆
​
(
𝐜
^
)
d
​
𝐜
^
\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:

d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐜
)
d
​
𝝎
=
d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐜
)
d
​
𝐱
⋆
​
(
𝐜
^
)
​
d
​
𝐱
⋆
​
(
𝐜
^
)
d
​
𝐜
^
​
d
​
𝐜
^
d
​
𝝎
\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,
d
​
𝐱
⋆
​
(
𝐜
^
)
d
​
𝐜
^
\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
≡
{
(
𝐳
𝐢
,
𝐜
𝐢
)
}
i
=
1
N
\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:

𝐜
^
=
m
𝝎
​
(
𝐳
)
\mathbf{\hat{c}}=m_{\mathbf{\bm{\omega}}}(\mathbf{z})

5:

ℒ
=
(
𝐜
^
−
𝐜
)
2
\mathcal{L}=(\mathbf{\hat{c}}-\mathbf{c})^{2}

6:

𝝎
←
𝝎
−
α
​
d
​
ℒ
d
​
𝐜
^
​
d
​
𝐜
^
d
​
𝝎
\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
≡
{
(
𝐳
𝐢
,
𝐜
𝐢
,
𝐱
⋆
(
𝐜
𝐢
)
}
i
=
1
N
\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:

𝐜
^
=
m
𝝎
​
(
𝐳
)
\mathbf{\hat{c}}=m_{\mathbf{\bm{\omega}}}(\mathbf{z})

5:

𝐱
⋆
​
(
𝐜
^
)
=
argmin
𝐱
∈
ℱ
f
​
(
𝐱
,
𝐜
^
)
\mathbf{x}^{\star}(\mathbf{\hat{c}})=\argmin_{\mathbf{x}\in\mathcal{F}}f(\mathbf{x},\mathbf{\hat{c}})

6:

ℒ
=
f
⁡
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐜
)
−
f
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
)
\mathcal{L}=f(\mathbf{x}^{\star}(\mathbf{\hat{c}}),\mathbf{c})-f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{c})

7:

𝝎
←
𝝎
−
α
​
d
​
ℒ
d
​
𝐱
⋆
​
(
𝐜
^
)
​
d
​
𝐱
⋆
​
(
𝐜
^
)
d
​
𝐜
^
​
d
​
𝐜
^
d
​
𝝎
\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:

𝐱
⋆
​
(
𝐜
)
=
argmin
𝐱
𝐜
⊤
​
𝐱
\displaystyle\mathbf{x}^{\star}(\mathbf{c})=\argmin_{\mathbf{x}}\mathbf{c}^{\top}\mathbf{x}

(8a)

s.t.
​
A
​
𝐱
=
𝐛
\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
]
[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
]
[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
n
list a permutation of sequential integers
[
n
]
[n]
which sorts the list. By smoothing the linear program, these basic operations can be differentiated and backpropagated (?).

Top-
k
k
selection.

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

Computing the maximum.

This is a special case of top-
k
k
selection where
k
=
1
k=1
. When the LP’s objective is regularized with the entropy term
H
⁡
(
𝐱
)
=
𝐱
⊤
​
log
⁡
𝐱
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.,
𝐱
∈
ℤ
k
\mathbf{x}\in\mathbb{Z}^{k}
where
ℤ
k
\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.

Figure 4
:
An overview of gradient-based DFL methodologies categorized into four classes.

3
Review of Decision-Focused Learning Methodologies

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
d
​
𝐱
⋆
​
(
𝐜
^
)
d
​
𝐜
^
\frac{d\mathbf{x}^{\star}(\mathbf{\hat{c}})}{d\mathbf{\hat{c}}}
or
d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
d
​
𝐜
^
\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
⁡
(
𝐜
)
=
argmin
𝐱
f
​
(
𝐜
,
𝐱
)
V(\mathbf{c})=\argmin_{\mathbf{x}}f(\mathbf{c},\mathbf{x})
, it can be shown that when all second derivatives of
f
f
exist,

d
​
V
​
(
𝐜
)
d
​
𝐜
=
−
f
𝐜𝐱
​
(
𝐜
,
V
​
(
𝐜
)
)
f
𝐱𝐱
​
(
𝐜
,
V
​
(
𝐜
)
)
\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
𝐜𝐱
f_{\mathbf{cx}}
is the second partial derivative of
f
f
with respect to
𝐜
\mathbf{c}
followed by
𝐱
\mathbf{x}
. This follows from implicit differentiation of the first-order optimality conditions

d
d
​
𝐱
​
f
​
(
𝐜
,
V
⁡
(
𝐜
)
)
=
0
\frac{d}{d\mathbf{x}}f(\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
​
(
𝐜
,
𝐱
)
≤
0
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
⁡
(
𝐜
,
𝐱
)
=
f
⁡
(
𝐜
,
𝐱
)
−
μ
​
∑
i
M
i
​
n
log
⁡
(
−
g
i
​
(
𝐜
,
𝐱
)
)
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
i
​
n
M_{in}
is the number of inequality constraints.
Then
argmin
𝐱
F
​
(
𝐜
,
𝐱
)
\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:

𝐱
⋆
=
argmin
𝐱
\displaystyle\mathbf{x}^{\star}=\argmin_{\mathbf{x}}

f
⁡
(
𝐱
)
\displaystyle\;\;f(\mathbf{x})

(12a)

s.t.

𝒈
⁡
(
𝐱
)
≤
0
\displaystyle\;\;\bm{g}(\mathbf{x})\leq 0

(12b)

𝒉
⁡
(
𝐱
)
=
0
\displaystyle\;\;\bm{h}(\mathbf{x})=0

(12c)

and assume that
f
f
,
g
g
and
h
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
) (?):

∇
f
(
𝐱
⋆
)
+
∑
i
w
i
∇
h
i
(
𝐱
⋆
)
+
∑
j
u
j
∇
g
j
(
𝐱
⋆
)
=
0
\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)

g
j
​
(
𝐱
⋆
)
≤
0
​
∀
j
\displaystyle g_{j}(\mathbf{x}^{\star})\leq 0\;\;\forall j

(13b)

h
i
​
(
𝐱
⋆
)
=
0
​
∀
i
\displaystyle h_{i}(\mathbf{x}^{\star})=0\;\;\forall i

(13c)

u
j
≥
0
​
∀
j
\displaystyle u_{j}\geq 0\;\;\forall j

(13d)

u
j
​
g
j
​
(
𝐱
⋆
)
=
0
​
∀
j
\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
f
is a convex quadratic function and the constraint functions
g
,
h
g,h
are linear over a continuous domain. In the most general case, each of
f
f
,
g
g
and
h
h
are dependent on a distinct set of parameters, in addition to the optimization variable
𝐱
\mathbf{x}
:

f
⁡
(
𝐜
,
Q
,
𝐱
)
=
1
2
​
𝐱
⊤
​
Q
​
𝐱
+
𝐜
⊤
​
𝐱
\displaystyle f(\mathbf{c},Q,\mathbf{x})=\frac{1}{2}\mathbf{x}^{\top}Q\mathbf{x}+\mathbf{c}^{\top}\mathbf{x}

(14a)

h
⁡
(
A
,
𝐛
,
𝐱
)
=
A
​
𝐱
−
𝐛
\displaystyle h(A,\mathbf{b},\mathbf{x})=A\mathbf{x}-\mathbf{b}

(14b)

g
⁡
(
R
,
𝐬
,
𝐱
)
=
R
​
𝐱
−
𝐬
\displaystyle g(R,\mathbf{s},\mathbf{x})=R\mathbf{x}-\mathbf{s}

(14c)

When
𝐱
∈
ℝ
n
\mathbf{x}\in\mathbb{R}^{n}
and the number of inequality and equality constraints are
M
i
​
n
M_{in}
and
M
e
​
q
M_{eq}
, respectively, a QP problem is specified by parameters
Q
∈
ℝ
n
×
n
Q\in\mathbb{R}^{n\times n}
,
𝐜
∈
ℝ
n
\mathbf{c}\in\mathbb{R}^{n}
,
R
∈
ℝ
n
×
M
i
​
n
R\in\mathbb{R}^{n\times M_{in}}
,
𝐬
∈
ℝ
M
i
​
n
\mathbf{s}\in\mathbb{R}^{M_{in}}
,
A
∈
ℝ
n
×
M
e
​
q
A\in\mathbb{R}^{n\times M_{eq}}
, and
𝐛
∈
ℝ
M
e
​
q
\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
,
𝐜
,
R
,
𝐬
,
A
,
𝐛
)
(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
d
​
𝐱
⋆
d
​
𝐜
\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:

𝐱
⋆
​
(
A
,
𝐛
,
𝐜
)
=
argmin
𝐱
\displaystyle\mathbf{x}^{\star}(A,\mathbf{b},\mathbf{c})=\argmin_{\mathbf{x}}

𝐜
⊤
​
𝐱
\displaystyle\;\;\mathbf{c}^{\top}\mathbf{x}

(15a)

s.t.

A
​
𝐱
−
𝐛
∈
𝒦
\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
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
,
𝐛
,
𝐜
)
(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
,
𝐛
,
𝐜
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
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
d
​
𝐱
⋆
​
(
𝐜
)
d
​
𝐜
\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

𝐱
t
+
1
​
(
𝐜
)
=
𝒰
⁡
(
𝐱
t
​
(
𝐜
)
,
𝐜
)
\mathbf{x}_{t+1}(\mathbf{c})=\mathcal{U}(\mathbf{x}_{t}(\mathbf{c}),\;\mathbf{c})

(16)

converge as
t
→
∞
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

(
𝐈
−
Φ
)
​
d
​
𝐱
⋆
d
​
𝐜
=
Ψ
,
(\mathbf{I}-\Phi)\frac{d\mathbf{x}^{\star}}{d\mathbf{c}}=\Psi,

(18)

which is a linear system to be solved for
d
​
𝐱
⋆
d
​
𝐜
\frac{d\mathbf{x}^{\star}}{d\mathbf{c}}
, in terms of
Φ
=
d
​
𝒰
d
​
𝐱
⋆
​
(
𝐱
⋆
​
(
𝐜
)
,
c
)
\Phi={{\frac{d\mathcal{U}}{d\mathbf{x}^{\star}}(\mathbf{x}^{\star}(\mathbf{c}),\;c)}}
,
Ψ
=
d
​
𝒰
d
​
𝐜
​
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
)
\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})

=
argmin
𝐱
𝐜
⊤
​
𝐱
+
μ
​
∥
𝐱
∥
2
2
\displaystyle=\argmin_{\mathbf{x}}\mathbf{c}^{\top}\mathbf{x}+\mu\lVert\mathbf{x}\rVert^{2}_{2}

(19a)

=
argmin
𝐱
∥
𝐱
−
(
−
𝐜
μ
)
∥
2
2
\displaystyle=\argmin_{\mathbf{x}}\lVert\mathbf{x}-\Big(\frac{-\mathbf{c}}{\mu}\Big)\rVert^{2}_{2}

(19b)

where the above equality follows from expanding the square and cancelling constant terms, which do not affect the
argmax
\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
(
−
𝐜
μ
)
\Big(\frac{-\mathbf{c}}{\mu}\Big)
onto the feasible polytope, which results in a continuous mapping
𝐜
→
𝐱
⋆
​
(
𝐜
)
\mathbf{c}\to\mathbf{x}^{\star}(\mathbf{c})
. ? (?) then train models in decision-focused paradigm 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
⁡
(
𝐱
)
=
∑
i
x
i
​
log
⁡
x
i
H(\mathbf{x})=\sum_{i}x_{i}\log x_{i}
and the binary entropy function
H
b
​
(
𝐱
)
=
H
⁡
(
𝐱
)
+
H
⁡
(
𝟏
−
𝐱
)
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
H
smooths an LP for differentiable sorting and ranking, and ? (?) propose a way to differentiate using
H
b
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 as follows:

𝐱
⋆
​
(
𝐜
)
=
argmin
𝐱
𝐜
⊤
​
𝐱
−
μ
​
∑
i
=
1
dim
(
𝐱
)
log
⁡
(
x
i
)
\displaystyle\mathbf{x}^{\star}(\mathbf{c})=\argmin_{\mathbf{x}}\mathbf{c}^{\top}\mathbf{x}-\mu\sum_{i=1}^{\dim(\mathbf{x})}\log(x_{i})

(20a)

s.t.
​
A
​
𝐱
=
𝐛
\displaystyle\text{s.t.}\;\;A\mathbf{x}=\mathbf{b}

(20b)

While this method, in this sense,
is similar to the approach of ? (?), it 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
μ
\mu
, 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
𝜽
1
\bm{\theta}_{1}
is conditionally dependent on another variable
𝜽
2
\bm{\theta}_{2}
and the final loss
ℒ
\mathcal{L}
is defined on the variable
𝜽
1
\bm{\theta}_{1}
. Let
p
⁡
(
𝜽
𝟏
|
𝜽
𝟐
)
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
𝜽
1
\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
𝜽
2
\bm{\theta}_{2}
.
? (?) proposes that the derivative of
ℒ
\mathcal{L}
with respect to
𝜽
2
\bm{\theta}_{2}
can be approximated by the following finite difference method:

d
​
L
d
​
𝜽
𝟐
≈
1
δ
(
𝔼
[
𝜽
𝟏
|
(
𝜽
𝟐
+
δ
d
d
​
𝜽
𝟏
(
ℒ
(
𝔼
[
𝜽
𝟏
|
𝜽
𝟐
]
)
)
]
−
𝔼
[
𝜽
𝟏
|
𝜽
𝟐
]
)
\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
d
d
​
𝜽
𝟏
​
[
ℒ
​
(
𝔼
​
[
𝜽
𝟏
]
)
]
\frac{d}{d\bm{\theta_{1}}}[\mathcal{L}(\mathbb{E}[\bm{\theta_{1}}])]
is the derivative
ℒ
\mathcal{L}
with respect to
𝜽
1
\bm{\theta}_{1}
at
𝔼
⁡
[
𝜽
𝟏
]
\mathbb{E}[\bm{\theta_{1}}]
.
Notice that the first term in (
21
) is the conditional mean after perturbing the parameter
𝜽
2
\bm{\theta}_{2}
where the magnitude of the perturbation is modulated by the derivative of
ℒ
\mathcal{L}
with respect to
𝜽
1
\bm{\theta}_{1}
.
Taking inspiration from this proposition,
by defining a conditional distribution
p
​
(
𝐱
⋆
​
(
𝐜
^
)
|
c
^
)
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
⁡
(
𝐱
|
𝐜
)
=
{
1
𝐱
=
𝐱
⋆
​
(
𝐜
)
0
otherwise
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
)
𝔼
𝐱
∼
p
⁡
(
𝐱
|
𝐜
)
​
[
x
|
c
]
=
𝐱
⋆
​
(
𝐜
)
\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
),
d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
d
​
𝐜
^
\frac{d\mathcal{L}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))}{d\mathbf{\hat{c}}}
can be approximated in the following way:

d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
d
​
𝐜
^
≈
∇
(
D
​
B
​
B
)
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
=
(
𝐱
⋆
​
(
𝐜
^
+
δ
​
d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
d
​
𝐱
⋆
​
(
𝐜
^
)
)
−
𝐱
⋆
​
(
𝐜
^
)
)
\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
𝐜
^
+
δ
​
d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
d
​
𝐱
|
𝐱
=
𝐱
⋆
​
(
𝐜
^
)
\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:

d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
d
​
𝐜
^
≈
−
d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
d
​
𝐱
⋆
​
(
𝐜
^
)
\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
⁡
(
θ
1
|
θ
2
)
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
τ
​
(
𝐱
|
𝐜
)
=
{
exp
(
−
f
(
𝐱
,
𝐜
)
/
τ
)
∑
𝐱
′
∈
ℱ
exp
(
−
f
(
𝐱
′
,
𝐜
)
/
τ
)
𝐱
∈
ℱ
0
otherwise
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
(
𝐱
,
𝐜
)
/
τ
)
\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
τ
→
0
\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
,
ϵ
)
(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
𝜼
​
∼
i.i.d.
​
Gumbel
​
(
0
,
ϵ
)
\bm{\eta}\overset{\text{i.i.d.}}{\sim}\text{Gumbel}(0,\epsilon)
,

ℙ
[
𝐱
=
argmax
𝐱
′
−
f
(
𝐱
′
,
𝐜
~
)
]
=
p
ϵ
(
𝐱
|
𝐜
)
\mathbb{P}[\mathbf{x}=\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
⁡
(
𝐱
|
𝐜
)
p(\mathbf{x}|\mathbf{c})
.
In particular, they use the reparameterization trick (?, ?) to generate samples from
p
⁡
(
𝐱
|
𝐜
)
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
⁡
(
−
ν
⁡
(
𝜼
)
)
\exp(-\nu(\bm{\eta}))
for a twice-differentiable function
ν
\nu
.
Moreover, they propose to multiply the random variable
𝜼
\bm{\eta}
with a temperature parameter
ϵ
>
0
\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
+
ϵ
​
𝜼
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
⁡
(
𝐱
|
𝐜
)
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
ϵ
→
0
\epsilon\to 0
,
𝐱
ϵ
⋆
​
(
𝐜
)
→
𝐱
⋆
​
(
𝐜
)
\mathbf{x}^{\star}_{\epsilon}(\mathbf{c})\to\mathbf{x}^{\star}(\mathbf{c})
.
Like before,
𝐱
ϵ
⋆
​
(
c
)
\mathbf{x}^{\star}_{\epsilon}(c)
can be estimated by Monte Carlo simulation by sampling i.i.d. random noise
𝜼
(
m
)
\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})

=
1
M
​
∑
m
=
1
M
𝐱
⋆
​
(
𝐜
+
ϵ
​
𝜼
(
m
)
)
\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

d
​
𝐱
¯
ϵ
⋆
​
(
𝐜
)
d
​
𝐜
=
1
ϵ
​
1
M
​
∑
m
=
1
M
𝐱
⋆
​
(
𝐜
+
ϵ
​
𝜼
(
m
)
)
​
ν
′
​
(
𝜼
(
m
)
)
⊤
\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
d
​
𝐱
⋆
​
(
𝐜
)
d
​
𝐜
\frac{d\mathbf{x}^{\star}(\mathbf{c})}{d\mathbf{c}}
by
d
​
𝐱
¯
ϵ
⋆
​
(
𝐜
)
d
​
𝐜
\frac{d\bar{\mathbf{x}}^{\star}_{\epsilon}(\mathbf{c})}{d\mathbf{c}}
to implement the backward pass.
As mentioned before, if
ϵ
→
0
\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:

∇
ℒ
F
​
Y
​
(
𝐱
⋆
​
(
𝐜
^
)
)
=
−
(
𝐱
¯
ϵ
⋆
​
(
𝐜
^
)
−
𝐱
⋆
​
(
𝐜
)
)
\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:

d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
d
​
𝐜
^
≈
∇
(
I
​
M
​
L
​
E
)
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
=
(
𝐱
⋆
​
(
𝐜
^
+
δ
​
d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
d
​
𝐱
⋆
​
(
𝐜
^
)
+
ϵ
​
𝜼
γ
)
−
𝐱
⋆
​
(
𝐜
^
+
ϵ
​
𝜼
γ
)
)
\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
ϵ
>
0
\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
𝜼
γ
=
0
\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
d
​
ℒ
​
(
𝐱
⋆
​
(
𝐜
^
)
)
d
​
𝐱
⋆
​
(
𝐜
^
)
\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
d
​
𝐱
⋆
​
(
𝐜
^
)
d
​
𝐜
^
\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.

ℒ
S
​
P
​
O
+
​
(
𝐱
⋆
​
(
𝐜
^
)
)
=
2
​
𝐜
^
⊤
​
𝐱
⋆
​
(
𝐜
)
−
𝐜
⊤
​
𝐱
⋆
​
(
𝐜
)
+
max
𝐱
∈
ℱ
⁡
{
𝐜
⊤
​
𝐱
−
2
​
𝐜
^
⊤
​
𝐱
}
\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
ℒ
S
​
P
​
O
+
\mathcal{L}_{SPO+}
for a linear predictive model.
However, they note that directly minimizing
ℒ
S
​
P
​
O
+
\mathcal{L}_{SPO+}
is prohibitive for complex predictive models such as NNs.
Hence, they derive the following useful subgradient of
ℒ
S
​
P
​
O
+
​
(
𝐱
⋆
​
(
𝐜
^
)
)
\mathcal{L}_{SPO+}(\mathbf{x}^{\star}(\mathbf{\hat{c}}))
:

𝐱
⋆
​
(
𝐜
)
−
𝐱
⋆
​
(
2
​
𝐜
^
−
𝐜
)
∈
∂
ℒ
S
​
P
​
O
+
\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
𝐱
⋆
​
(
2
​
𝐜
^
−
𝐜
)
\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
S
. In other words, the following ratio is maximized:

max
⁡
∑
𝐱
′
∈
S
𝐜
^
⁡
p
τ
​
(
𝐱
⋆
​
(
𝐜
)
|
𝐜
^
)
p
τ
​
(
𝐱
′
|
𝐜
^
)
\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
𝐱
′
∈
S
\mathbf{x}^{\prime}\in S
is a negative example.
Because the probability
p
τ
​
(
𝐱
⋆
​
(
𝐜
)
|
𝐜
^
)
p_{\tau}(\mathbf{x}^{\star}(\mathbf{c})|\mathbf{\hat{c}})
is defined as in (
25
), when
τ
=
1
\tau=1
, maximizing (
33
) corresponds to minimizing the following loss:

ℒ
N
​
C
​
E
​
(
𝐜
^
,
𝐜
)
=
∑
𝐱
′
∈
S
f
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
^
)
−
f
⁡
(
𝐱
′
,
𝐜
^
)
\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
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
^
)
≤
f
⁡
(
𝐱
′
,
𝐜
^
)
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
ℒ
N
​
C
​
E
​
(
𝐜
^
,
𝐜
)
\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
S
according to the current model:

ℒ
M
​
A
​
P
​
(
𝐜
^
,
𝐜
)
\displaystyle\mathcal{L}_{MAP}(\mathbf{\hat{c}},\mathbf{c})

=
max
𝐱
′
∈
S
⁡
f
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
^
)
−
f
⁡
(
𝐱
′
,
𝐜
^
)
\displaystyle=\max_{\mathbf{x}^{\prime}\in S}f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{\hat{c}})-f(\mathbf{x}^{\prime},\mathbf{\hat{c}})

=
f
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
^
)
−
f
⁡
(
𝐱
′
,
𝐜
^
)
​
where
​
𝐱
′
=
argmin
𝐱
∈
S
f
​
(
𝐱
,
𝐜
^
)
\displaystyle=f(\mathbf{x}^{\star}(\mathbf{c}),\mathbf{\hat{c}})-f(\mathbf{x}^{\prime},\mathbf{\hat{c}})\text{ where }\mathbf{x}^{\prime}=\argmin_{\mathbf{x}\in S}f(\mathbf{x},\mathbf{\hat{c}})

(35)

Note that whenever
𝐱
⋆
​
(
𝐜
^
)
∈
S
\mathbf{x}^{\star}(\mathbf{\hat{c}})\in S
, it holds that
ℒ
M
​
A
​
P
​
(
𝐜
^
,
𝐜
)
=
f
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
^
)
−
f
⁡
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐜
^
)
\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

ℒ
N
​
C
​
E
​
(
𝐜
^
,
𝐜
)
=
∑
𝐱
′
∈
S
𝐜
^
⊤
​
(
𝐱
⋆
​
(
𝐜
)
−
𝐱
′
)
\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

ℒ
M
​
A
​
P
​
(
𝐜
^
,
𝐜
)
=
𝐜
^
⊤
​
(
𝐱
⋆
​
(
𝐜
)
−
𝐱
′
)
\mathcal{L}_{MAP}(\mathbf{\hat{c}},\mathbf{c})=\mathbf{\hat{c}}^{\top}(\mathbf{x}^{\star}(\mathbf{c})-\mathbf{x}^{\prime})
, where
𝐱
′
=
argmin
𝐱
∈
S
f
​
(
𝐱
,
𝐜
^
)
\mathbf{x}^{\prime}=\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:

ℒ
N
​
C
​
E
(
𝐜
^
−
𝐜
)
​
(
𝐜
^
,
𝐜
)
=
∑
𝐱
′
∈
S
(
𝐜
^
−
𝐜
)
⊤
​
(
𝐱
⋆
​
(
𝐜
)
−
𝐱
′
)
\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)

ℒ
M
​
A
​
P
(
𝐜
^
−
𝐜
)
​
(
𝐜
^
,
𝐜
)
=
max
𝐱
′
∈
S
⁡
(
𝐜
^
−
𝐜
)
⊤
​
(
𝐱
⋆
​
(
𝐜
)
−
𝐱
′
)
\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
S
.

Forming
S
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
S
by caching all the optimal solutions in the training data. That is why they name
S
S
as ‘solution cache’.
While training, more feasible points are gradually added to
S
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
s
​
o
​
l
​
v
​
e
p_{solve}
.
Intuitively, the
p
s
​
o
​
l
​
v
​
e
p_{solve}
hyperparameter determines the proportion of instances for which the CO problem is solved during training.
Experimentally, it has been reported that
p
s
​
o
​
l
​
v
​
e
=
5
%
p_{solve}=5\%
of the time is often adequate, which translates to solving for only
5
%
5\%
of the predicted instances.
This translates to reducing the computational cost by approximately
95
%
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
⊂
ℱ
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
ℒ
N
​
C
​
E
\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
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
S
similarly to how
𝐜
\mathbf{c}
ranks them.
In the
pairwise
approach,
𝐱
⋆
​
(
𝐜
)
\mathbf{x}^{\star}(\mathbf{c})
and any
𝐱
′
∈
S
\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
Θ
>
0
\Theta>0
. The pairwise loss is formally defined in the following form:

ℒ
Pairwise
​
(
𝐜
^
,
𝐜
)
=
∑
𝐱
′
∈
S
max
⁡
(
0
,
Θ
+
(
f
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
^
)
−
f
⁡
(
𝐱
′
,
𝐜
^
)
)
)
\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.

ℒ
PairwiseDifference
​
(
𝐜
^
,
𝐜
)
=
∑
𝐱
′
∈
S
(
(
f
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
^
)
−
f
⁡
(
𝐱
′
,
𝐜
^
)
)
−
(
f
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
)
−
f
⁡
(
𝐱
′
,
𝐜
)
)
)
2
\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
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
τ
​
(
𝐱
|
𝐜
)
p_{\tau}(\mathbf{x}|\mathbf{c})
can be interpreted as a probability measure of
𝐱
∈
ℱ
\mathbf{x}\in\mathcal{F}
being the minimizer of
f
⁡
(
𝐱
,
𝐜
)
f(\mathbf{x},\mathbf{c})
in
ℱ
\mathcal{F}
for a given
𝐜
\mathbf{c}
.
However, as mentioned before, direct computation of
p
τ
​
(
𝐱
|
𝐜
)
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
⊂
ℱ
S\subset\mathcal{F}
.
This probability measure finally is used to define a listwise loss—the cross-entropy loss between
p
τ
​
(
𝐱
|
𝐜
)
p_{\tau}(\mathbf{x}|\mathbf{c})
and
p
τ
​
(
𝐱
|
𝐜
^
)
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:

ℒ
Listwise
(
𝐜
^
,
𝐜
)
=
(
−
1
|
S
|
∑
𝐱
′
∈
S
p
τ
(
𝐱
′
|
𝐜
)
log
p
τ
(
𝐱
′
|
𝐜
^
)
)
\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
ℒ
S
​
P
​
O
+
​
(
𝐱
⋆
​
(
𝐜
^
)
)
\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
ℒ
S
​
P
​
O
+
​
(
𝐱
⋆
​
(
𝐜
^
)
)
\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:

𝑅𝑒𝑔𝑟𝑒𝑡
⁡
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐜
)
=
max
𝐱
⋆
​
(
𝐜
^
)
∈
𝒳
⋆
​
(
𝐜
^
)
⁡
f
⁡
(
𝐱
⋆
​
(
𝐜
^
)
,
𝐜
)
−
f
⁡
(
𝐱
⋆
​
(
𝐜
)
,
𝐜
)
\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
c
^
i
\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 studi

[The evaluation harness truncated this reference: showing the first 120000 of 245608 characters.]
</reference>

<statements>
1. A rigorous comparison across the three portfolio modeling paradigms requires isolating the three core stages of the asset management pipeline: return prediction, risk measurement, and the mathematical mechanics of asset allocation
2. Decision-Focused Learning (DFL) embeds differentiable convex optimization layers (such as CVXPYLayers or OptNet) directly within the neural network
3. In this setup, the forward pass solves a constrained optimization problem via a quadratic or cone solver, while the backward pass computes analytic gradients through the KarushKuhnTucker (KKT) conditions or tangent-space projections
4. This end-to-end structure trains the predictive network directly on downstream decision regret rather than generic statistical error metrics, ensuring allocations respect hard operational constraints
5. In the Integrated Modern Hybrid Framework, the Asset Allocation Engine uses end-to-end differentiable convex optimization layers (CVXPYLayers / DFL)
6. A major structural inefficiency in modern quantitative workflows stems from the decoupled "Predict-then-Optimize" pipeline
7. Once trained, these predictions are passed to a downstream quadratic optimizer to solve for portfolio weights
8. This decoupled setup creates a fundamental misalignment: minimizing MSE treats forecast errors symmetrically across all assets, ignoring the structure of the downstream optimization problem
9. Decision-Focused Learning (DFL) addresses this disconnect by training predictive models directly on downstream decision regret
10. By differentiating through the optimization solver, DFL aligns predictive training with portfolio performance
11. The development of differentiable convex optimization layers (e.g., CVXPYLayers, OptNet) enables the end-to-end integration of machine learning predictors with constrained optimization solvers
12. In this setup, a neural network predicting return parameters \(\hat{y}\) is linked directly to a downstream solver that optimizes portfolio weights subject to operational constraints
13. This allows gradients to flow backwards from realized economic regret directly into the network weights
14. Because this layer is implemented using differentiable convex programming (e.g., CVXPYLayers), downstream portfolio regret is differentiated analytically across the solver’s KKT conditions
15. The resulting gradients flow backward through the optimization layer, updating the weights of the Module 1 attention network directly
16. This end-to-end integration bridges the gap between predictive statistical modeling and execution-ready portfolio construction
17. Guarantees hard constraint satisfaction and aligns predictive training with regret
18. Finally, differentiable convex optimization layers enforce portfolio constraints, penalize transaction turnover, and propagate downstream economic regret directly back into the neural feature extractors
</statements>

Begin the assessment now. Output only the JSON list, without any conversational text or explanations.