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

Introduction

• When prediction and optimization are trained separately, imperfect predictions can propagate into suboptimal decisions, motivating joint modeling of the interconnected stages.Perfectly accurate parameter predictions would enable optimal decisions, but machine-learning models often fall short of perfect accuracy.Source: §1 · p. 2
• DFL integrates machine learning and constrained optimization in an end-to-end system trained to make predictions that lead to good decisions.The decision-based loss depends on the solution of the constrained optimization problem.Source: §1 · p. 2
• DFL’s central technical challenges are differentiating through constrained optimization and learning with discrete decision mappings that are discontinuous.The survey emphasizes smooth surrogate models for discrete mappings and their differentiation.Source: §1 · pp. 2–3
• The survey organizes gradient-based DFL into four classes: analytical differentiation, analytical smoothing, random-perturbation smoothing, and surrogate-loss differentiation.It also distinguishes gradient-based methods from gradient-free methods, which do not compute gradients for learning.Source: §1 · p. 3
• The survey takes an ML-oriented view of DFL for Predict-Then-Optimize problems, reviews gradient-based and gradient-free techniques, and benchmarks methods on seven problems.It also discusses open challenges and future directions; the benchmark code and data are made publicly available.Source: §1 · pp. 3–4

2. Preliminaries

• The preliminaries establish notation: bold lowercase letters denote vectors, subscripts identify components, and 1, 0, and I denote all-ones, all-zeros, and identity matrices.The section introduces foundational concepts and terminology before discussing modeling challenges and DFL methodologies.Source: §2 · p. 4

2.1 Problem Setting

• The Predict-Then-Optimize setting estimates uncertain CO parameters from features, then solves the CO problem using those predictions; training is judged by the resulting prescriptive decisions.When true parameters are known, the corresponding solutions are called full-information optimal decisions.Source: §2.1 · pp. 4–5
• The surveyed setting assumes constraints are known and parameter-independent, restricting uncertainty to the objective; uncertain constraints can yield infeasible decisions and require recourse to define learning.The cited recourse work is Hu, Lee, & Lee (2023c, 2023a).Source: §2.1 · p. 5

2.2 Learning Paradigms

• PFL trains on parameter-prediction losses such as MSE or BCE, whereas DFL trains on task losses such as regret, the objective-value gap from the full-information optimum.Minimizing regret is equivalent to minimizing the realized objective value because the full-information optimum is constant with respect to the prediction model.Source: §2.2 · pp. 5–6
• DFL trains the integrated prediction-and-optimization model to improve decision quality, treating predicted parameters as an intermediate step rather than the primary training target.Its task loss measures error in the resulting decision x⋆(ĉ), unlike prediction loss, which measures error in ĉ.Source: §2.2 · p. 6
• The two-item knapsack illustration shows that equal squared prediction errors can produce different decisions, while larger errors can leave the optimal decision unchanged and incur zero regret.Overestimating selected-item values or underestimating unselected-item values can increase prediction error without changing the solution.Source: Figure 2 · p. 7, §2.2 · pp. 7–8

2.3 Challenges to Implement Decision-Focused Learning

• DFL can be formulated as bilevel optimization, but differentiating the CO solution mapping is difficult because it lacks a closed form and may be nondifferentiable or have zero gradients.The outer problem minimizes task loss; the inner problem computes the parameter-to-optimal-solution mapping.Source: §2.2 · pp. 8–9, §2.3 · p. 9
• Each training sample and epoch requires solving and differentiating the CO problem, creating substantial cost that can impede training on large or NP-hard problems.The passage notes that this burden can arise even for small-scale, efficiently solvable problems.Source: §2.3 · p. 10

2.4.1 Convex Optimization

• Convex problems guarantee that local optima are global and are reliably solvable, but optimization layers add substantial overhead and lack directly differentiable closed-form mappings.Canonicalization enables standardized solution and backpropagation procedures, while convex mappings may or may not be differentiable everywhere.Source: §2.4.1 · p. 11

2.4.2 Linear Programming

• LPs model resource allocation and uncertain shortest paths, where predicted arc lengths determine the route.Linear relationships represent resource allocation; shortest-path benchmarks predict unknown arc lengths from features such as time and weather.Source: §2.4.2 · pp. 11–12
• LP solution mappings are piecewise constant, with zero derivatives almost everywhere and undefined derivatives elsewhere, so DFL commonly differentiates smooth approximations.LPs attain optima at feasible-set vertices, mapping continuous objective parameters to a finite set of solutions.Source: §2.4.2 · p. 11
• Sorting and ranking and top-k selection have LP formulations, while entropy-regularized maximum computation maps predicted values to a softmax.Smoothing sorting LPs enables differentiation and backpropagation; top-k selection also appears in multilabel classification.Source: §2.4.2 · p. 12
• Max-flow capacities appear on the constraint right-hand side, but the dual min-cut formulation places them in the objective for DFL prediction.The max-flow form does not match the DFL formulation described in the paper.Source: §2.4.2 · pp. 12–13

2.4.3 Integer Linear Programming

• ILPs yield discontinuous, nondifferentiable mappings, and their NP-hard complexity can make exact solution at every training step infeasible.Their discontinuous feasible regions also prevent many smoothing techniques used for LPs.Source: §2.4.3 · p. 13
• Knapsack and travelling salesperson problems illustrate ILP predict-then-optimize tasks requiring predicted item values or city-to-city distances.Knapsack selects value-maximizing items subject to capacity; travelling salesperson seeks a shortest route visiting each city once.Source: §2.4.3 · p. 13

2.4.4 Integer Nonlinear Programming

• Integer nonlinear programs have zero-valued gradients almost everywhere, and no DFL technique is specifically developed or tested for them; one approach uses approximate ILP surrogates.The surrogate supports a DFL training procedure using existing techniques for differentiation through ILPs.Source: §2.4.4 · p. 14

• Gradient-based DFL is extensively studied and enables neural-network models, while tree-based and search-based methods can avoid gradients altogether.Source: §3 · pp. 14–15
• DFL methodologies are classified as gradient-based or gradient-free, with the review surveying them in that order.Source: §3 · p. 15

3.1 Review of Gradient-Based DFL Methodologies

• The paper categorizes gradient-based DFL into four classes: analytical differentiation, analytical smoothing, random perturbations, and surrogate loss differentiation.Each class constructs a different gradient or smoothed approximation for backpropagation through optimization.Source: §3.1 · p. 15

3.1.1 Analytical Differentiation of Optimization Mappings

• Exact analytical gradients differentiate optimization mappings through optimality conditions, but piecewise-constant mappings have zero gradients almost everywhere and often require smoothing.For quadratic programs, differentiating KKT conditions yields a linear system for gradients; fixed-point backpropagation is equivalent to solving such a system by iteration, with convergence tied to the spectral radius.Source: §3.1.1 · pp. 15, 16, 18, 19

3.1.2 Analytical Smoothing of Optimization Mappings

• Analytical smoothing makes combinatorial mappings differentiable by regularizing their optimization problems, with approaches for LPs and ILPs differing in their transformations and computational costs.Quadratic regularization smooths LP mappings for regret-based training, while cutting-plane LP relaxations for ILPs can improve regret but require time-consuming instance-specific cut generation each epoch.Source: §3.1.2 · pp. 19–20

3.1.3 Smoothing by Random Perturbations

• Random perturbation methods treat optimization solutions probabilistically to smooth mappings; black-box differentiation interpolates between solutions, while perturb-and-MAP estimates distributions without enumerating feasible points.Negative-identity backpropagation can destabilize learning on scale-invariant LPs and ILPs, for which cost-vector normalization is suggested.Source: §3.1.3 · pp. 20–22
• Perturbed optimization estimates a differentiable solution mapping by Monte Carlo sampling; for DPO, smaller temperatures reduce smoothing bias but can produce higher-variance, noisy gradients.Berthet et al. (2020) use reparameterized perturbations; as the temperature approaches zero, the estimate is unbiased, but its variance increases.Source: §3.1.3 · pp. 22–23
• Niepert, Minervini, and Franceschi (2021) use Sum-of-Gamma noise in I-MLE, while later work adapts its finite-difference step and other methods extend perturbations multiplicatively or through Gumbel-softmax distributions.Multiplicative perturbation is useful when cost parameters are non-negative; I-MLE’s finite-difference form reduces to its no-noise form when the perturbation is zero.Source: §3.1.3 · pp. 23–24
• Perturbation-based methods treat the CO solver as a black-box oracle, using its returned solutions for gradients without depending on whether the problem is solved by CP, SAT, LP, or ILP.This lets users choose their preferred solver technology.Source: §3.1.3 · p. 24

3.1.4 Differentiation of Surrogate Loss Functions

• Regret-surrogate methods require observed ground-truth costs and a final-stage CO problem; SPO+ provides a convex upper bound with useful subgradients for training neural networks despite regret’s zero gradient almost everywhere.Under stated distributional assumptions, SPO+ is Fisher consistent; low excess SPO+ risk translates to low excess regret risk, and worst-case generalization bounds have also been developed.Source: §3.1.4 · pp. 24–25
• For linear-cost CO problems including ILPs and MILPs, Mandi et al. (2020) found LP-relaxation training faster than standard SPO, with no significant final-regret difference and both outperforming prediction-focused training, though results may depend on the integrality gap.The relaxation drops integrality constraints; the authors caution against generalizing the result across problems.Source: §3.1.4 · p. 25
• Mulamba et al. (2021) use noise-contrastive and MAP losses to compare the ground-truth solution with negative examples, avoiding solver calls to compute the loss; their solution cache can cut solver use by about 95% when solving 5% of predictions.The cache also approximates a black-box solver with a lookup over stored feasible solutions for methods such as I-MLE, DBB, and SPO.Source: §3.1.4 · pp. 25–26
• Mandi et al. (2022) formulate DFL as pairwise or listwise ranking over cached solutions, and these losses are differentiable and solver-free to compute and differentiate.The listwise loss compares distributions over the cache under true and predicted costs.Source: §3.1.4 · p. 28
• Shah et al. (2022, 2024) learn differentiable local regret surrogates, with later work improving sample efficiency and fidelity beyond training neighborhoods; Kotary et al. (2023a) instead frame DFL as learning to optimize with regret-consistent joint prediction and optimization models.Local convex surrogates are learned per training point from nearby samples; the learning-to-optimize model takes features as input and predicts the optimal solution.Source: §3.1.4 · pp. 28–29

• Most gradient-based DFL techniques have been evaluated on CO problems with linear objectives, although some are generally applicable to any CO problem form.Table 1 summarizes the CO problem form applicable to each technique.Source: Discussion · p. 29
• Differentiable optimization-layer techniques can be embedded at any stage of a neural-network architecture, while other techniques apply when optimization is the pipeline’s final stage.The latter, including Predict-Then-Optimize formulations, use a particular task loss, most often regret.Source: Discussion · p. 29
• Table 1 compares gradient-based DFL techniques by applicable CO problem form, gradient computation method, and compatibility with generic task losses.Source: Discussion · p. 29

3.2 Review of Gradient-Free DFL Methodologies

• Because these methods avoid gradient-based training, their predictive models are usually tree-based or explicitly specified, such as linear models.The review contrasts them with gradient-descent DFL, described as the go-to approach for neural-network training.Source: §3.2 · p. 29
• Linear predictors can minimize convex LSPO+ with a convex solver, while decision trees can be learned directly against regret or through a MILP.Elmachtoub, Liang, and McNellis (2020) describe tree learning without the SPO+ surrogate introduced by Elmachtoub and Grigas (2022).Source: §3.2 · p. 29
• MILP training of linear predictors can guarantee global regret optimality, but is limited to linear models and binary MILPs.Jeong, Jaggi, Butler, and Sanner (2022) identify lower-level solution transition points, partition the solution space, and formulate the outer problem as a MILP.Source: §3.2 · pp. 29–30
• Coordinate descent updates linear-model cost components to reduce regret by locating transition points, using dynamic programming for problems solvable by that method.Demirović et al. (2020) represent the combinatorial optimization objective as piecewise linear in the ML parameters.Source: §3.2 · p. 30
• Later transition-point methods broaden the problem scope through divide-and-conquer for bilinear objectives and recursive search for problems solvable by recursion.Guler et al. (2022) report substantial speed improvement; Hu, Lee, Lee, and Zhong (2022) develop the “branch & learn” approach.Source: §3.2 · p. 30

3.3 Other Aspects of Decision-Focused Learning

• Worst-case regret evaluates the worst outcome among multiple optimal solutions for a predicted cost vector, which can arise in LPs or symmetric-graph problems.The definition takes the maximum regret over the set of optimal solutions for the predicted cost vector.Source: §3.3 · p. 30

3.3.1 Prediction-Focused vs. Decision-Focused Learning

• PFL asymptotically outperforms DFL with a well-specified prediction model, whereas DFL is recommended under model misspecification or aleatoric or epistemic uncertainty (Elmachtoub, Lam, Zhang, and Zhao, 2023).The cited work attributes this contrast partly to DFL’s approximate gradients when the true gradient is zero almost everywhere; Cameron, Hartford, Lundy, and Leyton-Brown (2022) find PFL’s suboptimality more pronounced with correlated predicted parameters.Source: §3.3.1 · pp. 30–31

3.3.2 Multi-task Decision-Focused Learning

• Shared-output and multi-headed architectures enable decision-focused predictions across multiple tasks, particularly with limited training data, but do not yet generalize to new tasks.For fair multiobjective DFL, Dinh, Kotary, and Fioretto (2024) smooth the nondifferentiable OWA objective with its Moreau envelope, enabling joint learning of objective parameters to minimize regret of their fair aggregation.Source: §3.3.2 · p. 31

3.3.3 Predicting Parameters in the Constraints

• When unknown parameters affect constraints, DFL must penalize infeasibility and compute gradients with respect to those parameters, challenges that are especially difficult for combinatorial problems.Proposals include high-cost slack variables, post-hoc regret for corrective actions, solver unrolling, KKT differentiation, SQP approximations, Lagrangian relaxation, LP relaxations, differentiable ILP layers, hyperplane learning, and branch & learn.Source: §3.3.3 · pp. 32–33

3.3.4 Model Robustness in Decision-Focused Learning

• Poisoning attacks can affect DFL models and transfer from two-stage models, but are computationally expensive; adversarial training can also address regret degradation from test-label noise (Kinsey, Tuck, Sinha, and Nguyen, 2023; Johnson-Yu, Wang, Finocchiaro, Taneja, and Tambe, 2023).The label-noise method bounds regret degradation and formulates robust training as a Stackelberg game between a noise-choosing adversary and a regret-minimizing learner.Source: §3.3.4 · p. 33

3.3.5 Stochastic Optimization

• Stochastic optimization can be converted to DFL with deterministic decision models by predicting distribution parameters and differentiating quadratic-program approximations (Donti, Kolter, and Amos, 2017).The survey also notes a broader relation to contextual stochastic optimization.Source: §3.3.5 · p. 33

3.3.6 Active Learning Algorithm for DFL

• DFL active learning acquires labels when distance to degeneracy is below a threshold, while DFL techniques also extend beyond classical CO to K-means clustering and MDP parameter prediction.Liu, Grigas, Liu, and Shen (2023) use distance to degeneracy to identify datapoints where knowing the cost parameter is most beneficial; examples beyond classical CO are described by Wilder, Ewing, Dilkina, and Tambe (2019b) and Wang, Shah, Chen, Perrault, Doshi-Velez, and Tambe (2021).Source: §3.3.6 · p. 34

Computer vision

• Computer-vision applications use DBB to differentiate rank-based metrics, bipartite matching, and multiway cuts for image matching and panoptic segmentation.The cited applications include semantic keypoint matching in deep graph and multi-graph matching, and graph partitioning for end-to-end panoptic segmentation.Source: §4 · p. 34

Fair Learning to Rank

• Fair learning to rank uses DFL to unite relevance prediction and fair-ranking optimization, but solving the ranking linear program throughout training requires significant computation.Kotary et al. (2022) use SPO; a more efficient approach based on optimizing ordered weighted averages is also described.Source: §4 · pp. 34–35

Route optimization

• Route-optimization applications use DFL for wildlife-trafficking paths and last-mile delivery, though one CVRP study found no DFL advantage with fewer than 200 training instances.For delivery, Chu et al. (2023) train with SPO to minimize total travel time; Mandi et al. (2021) report the limited-data finding for their routing objective.Source: §4 · p. 35

Maritime transportation

• In maritime applications, DFL selects ships for inspection or schedules maintenance by predicting deficiency numbers and optimizing inspection or maintenance decisions.Yang et al. (2022) use a pairwise-comparison loss because standard SPO is prohibitive at the problem scale; Tian et al. (2023) train random forests to minimize regret using SPOTs.Source: §4 · p. 35

Power and energy systems

• Power and energy applications use DFL for wind-powered energy scheduling, electricity-price forecasting, and energy-storage scheduling to maximize arbitrage benefits.Wahdany et al. (2023) train to minimize operating costs using cvxpylayers; Tschora et al. (2023) report better performance than conventional price forecasting, and Sang et al. (2022) report lower regret with SPO.Source: §4 · p. 36

Communication technology

• For mobile wireless fluid antenna systems, DFL predicts port-position signal-to-noise ratios and selects the optimal port; the SPO framework is reported effective.Chai et al. (2022) use an LSTM predictive model for port selection.Source: §4 · p. 36

Solving non-linear combinatorial optimization problems

• DFL can learn a linear surrogate optimizer whose optimal solution matches that of a nonlinear optimization problem.Ferber et al. (2023b) learn the surrogate parameters by backpropagating through an optimizer implemented with cvxpylayers.Source: §4 · p. 36

5. Experimental Evaluation on Benchmark Problemsets

• Without a common DFL benchmark, comparisons among techniques tested on different datasets can be inconsistent.The paper notes that a common benchmark had not yet been established.Source: §5 · p. 36
• The section proposes several benchmark test problems for evaluating DFL techniques.Source: §5 · p. 36
• It compares selected techniques discussed earlier on the proposed test problems.Source: §5 · p. 36

5.1 Problem Descriptions

• All test problems are established in DFL literature, use publicly available datasets, and have linear objective functions; Table 2 summarizes their optimization problems and predictive models.The problems all combine prediction and optimization.Source: §5.1 · pp. 36–37, Table 2 · p. 37

5.1.1 Shortest Path Problem on a 5 × 5 grid

• The 5 × 5 grid problem predicts edge costs from features to find a minimum-cost path from southwest to northeast using north- or east-directed edges.It has 25 nodes and 40 edges; experiments vary model-misspecification degree Deg across 1, 2, 4, 6, and 8, with 1,000 training and 10,000 test samples per setting.Source: §5.1.1 · pp. 37–38

5.1.2 Portfolio Optimization Problem

• The portfolio problem predicts asset returns and maximizes total portfolio value subject to a risk constraint on return variance.The covariance matrix is assumed independent of features; synthetic experiments use Deg values 1, 4, 8, and 16.Source: §5.1.2 · pp. 38–39

5.1.3 Warcraft Shortest Path Problem

• Warcraft shortest paths use terrain images to predict pixel costs and find a minimum-cost route between opposite corners, allowing moves to eight neighboring pixels.A modified ResNet18 CNN predicts positive pixel costs, avoiding negative cycles in the resulting edge weights.Source: §5.1.3 · p. 39

5.1.4 Energy-Cost Aware Scheduling Problem

• The scheduling problem predicts next-day energy prices to minimize costs when assigning noninterruptible tasks to machines under time and resource constraints.Each day is an instance with 48 half-hour slots, and the SEMO data provides eight features for each slot.Source: §5.1.4 · p. 40

5.1.5 Knapsack Problem

• The knapsack problem predicts item values while weights and capacity are known, selecting a maximum-value subset subject to capacity.Instances use 48 half-hour items with correlated weights and values and capacities of 60, 120, or 180.Source: §5.1.5 · p. 41

5.1.6 Diverse Bipartite Matching Problem

• Diverse bipartite matching predicts citation-edge likelihoods between article sets while requiring minimum proportions of same-field and cross-field pairings.The data comprise 27 instances of 100 nodes, split into two sets of 50.Source: §5.1.6 · p. 42

5.1.7 Subset Selections

• Subset selection predicts binary top-k selections rather than underlying problem parameters, so training uses task loss instead of regret and excludes methods requiring ground-truth parameters.Three datasets contain 1,000 samples each, with selection sizes n = 25, 50, or 100 and k equal to one fifth of n.Source: §5.1.7 · pp. 42–43

5.2.1 Comparative Evaluations

• On synthetic shortest paths, PF leads when Deg 1 matches the data process, but FY leads at Deg 8 and DFL methods generally improve on PF when its model is misspecified.FY also leads at Deg 6, closely followed by SPO, I-MLE, and QPTL; I-MLE leads at Deg 4, while PF and SPO lead at Deg 2. HSD has higher regret and variance than other DFL approaches, outperforming PF only at Deg 6 and 8.Source: Figure 5 · p. 45, Shortest path problem on a 5 × 5 grid · p. 46
• On portfolio optimization with quadratic constraints, SPO slightly outperforms PF except at Deg 1, while DBB, I-MLE, FY, and QPTL perform worse than PF.HSD is not applicable to this problem; at Deg 16, MAP, Pairwise, and Pairwise(diff) outperform SPO, and Listwise has lower average regret than SPO. Absolute rather than relative regret is reported because relative regret can be infinite when the optimal portfolio has zero return.Source: Shortest path problem on a 5 × 5 grid · pp. 46–47, Figure 6 · p. 46
• On Warcraft shortest paths, DFL methods outperform PF, with Listwise leading at sizes 12, 18, and 30; HSD and QPTL were not run because of computational burden.The size-30 results also identify MAP as a leading method; the discussion notes that black-box solvers such as Dijkstra’s enable these evaluations, unlike the unavailable HSD and QPTL runs.Source: Figure 7 · p. 47, Warcraft shortest path problem · p. 48, §5.2.3 · p. 53
• Scheduling favors FY, SPO, I-MLE, Pairwise(diff), and MAP, whereas knapsack winners vary by capacity: QPTL at 60 and DBB at 120 and 180.HSD and QPTL perform poorly in scheduling, where the relaxed LP may fail to capture integrality; Listwise and Pairwise also underperform PF. In knapsack, MAP, LTR losses, and FY can perform poorly at higher capacities.Source: Figure 8 · p. 48, Warcraft shortest path problem · p. 49, Figure 9 · p. 49
• Diverse matching has high relative regret across techniques; I-MLE leads at 10%, QPTL, I-MLE, and HSD at 25%, while subset-selection methods perform similarly overall.In the third matching instance, several DFL methods outperform PF; on subset selection, DBB performs worst, HSD is most sensitive to training-set choice, and QPTL and I-MLE have marginal advantages.Source: Warcraft shortest path problem · pp. 49–50, Figure 10 · p. 50, Figure 11 · p. 51

5.2.2 Comparison on Runtime

• PF has the lowest training time; SPO, DBB, I-MLE, and FY take almost 100 times longer, while cache-based Listwise, Pairwise, Pairwise(diff), and MAP are significantly faster than other DFL methods.These runtime comparisons use scheduling, and absolute times are subject to system overhead. For its hardest instance, solving the ILP can take longer than solving and differentiating the QP with cvxpylayers.Source: Figure 12 · p. 51, §5.2.2 · p. 52

5.2.3 Discussion

• No single DFL technique performs best across all experiments, while SPO is robust across test problems without winning every comparison.The discussion identifies problem-specific winners rather than an overall winner.Source: §5.2.3 · p. 52
• QPTL performs robustly when an LP relaxation approximates the ILP well, but can perform poorly when the relaxation differs substantially; Pairwise(diff) stands out among LTR losses for lower variance.MAP is consistent across most problems but has higher regret at knapsack capacity 180 and matching rates of 25%; it performs well in portfolio optimization.Source: §5.2.3 · pp. 52–53

Generalizing DFL across related tasks; DFL with Real-World Multimodal Datasets

• DFL should generalize across related CO instances and support multimodal inputs whose distinct uncertain parameters come from different feature sets.Research could test training on one instance and evaluating on similar instances, and develop methods to coordinate predictions, capture parameter interdependencies, and evaluate on real-world multimodal datasets.Source: §6 · pp. 53, 56

Non-linear objective function

• Most DFL methods do not handle nonlinear objective functions, so techniques for combinatorial optimization with nonlinear objectives and discrete decisions need development and evaluation.Although cvxpylayers differentiates through convex optimization with nonlinear objectives, most techniques reviewed do not address these scenarios.Source: §6 · pp. 53–54

Robust risk-sensitive DFL

• Risk-sensitive DFL remains sparse: future methods should minimize worst-case regret, such as value-at-risk or min-max regret, rather than expected regret alone.Robust optimization and prediction-focused estimate-then-optimize strategies could inform losses that represent uncertainty with a weight-based empirical distribution.Source: §6 · p. 54

Decision-focused learning by zeroth-order gradient; Bilevel Optimization Techniques for DFL

• Zeroth-order gradient estimation and bilevel optimization offer research directions, but high variance and scalability remain obstacles.Score-function gradients are unbiased but can destabilize learning through high variance; a quadratic non-convex reformulation of empirical regret minimization also faces scalability challenges.Source: §6 · p. 54

Scalable DFL

• The quality–scalability trade-off of surrogate solvers and solution caching is unclear, including how cache size affects solution quality and whether surrogates match CO solvers’ regret.Research should identify when pre-trained surrogate solvers approximate traditional CO solvers and how to improve their accuracy and reliability.Source: §6 · pp. 54–55

Theoretical guarantees

• DFL needs stronger regret-minimization guarantees across broader optimization settings, particularly for combinatorial problems with nonlinear constraints and safety-critical applications.Theoretical work should develop analytical tools for establishing regret properties under varied conditions and extend existing frameworks to more CO problems.Source: §6 · p. 55

Uncertainty in the constraints

• DFL for uncertain constraints remains underexplored, especially cache construction and solutions that remain feasible under extreme parameter variation.Future work could extend Neural Combinatorial Optimization (Bello, Pham, Le, Norouzi, & Bengio, 2017) and NCE to predict constraint parameters, jointly optimizing average performance and worst-case constraint violations.Source: §6 · p. 55

Extending DFL to multistage settings

• Research should test DFL in multistage optimization and as an intermediate layer between ML stages, where its effectiveness remains unevaluated.No studies have tested whether DFL improves final objectives in multistage settings; differentiable optimization layers for intermediate tasks also need empirical evaluation.Source: §6 · pp. 55–56

Conclusion

• DFL trains ML models using task losses that capture downstream optimization error, aiming to predict unknown problem parameters for high-quality solutions.The survey frames quality against retrospective solutions obtained with ground-truth parameters.Source: §7 · p. 56
• The survey reviews gradient-based and gradient-free DFL, categorizes gradient-based methods into four classes, and discusses their trade-offs alongside two fundamental challenges.Those challenges are differentiating through combinatorial optimization solutions and the computational cost of solving optimization problems during ML training.Source: §7 · p. 56
• The survey covers real-world Predict-Then-Optimize applications across domains and comparative evaluations of 11 DFL techniques on different problem sets.Source: §7 · p. 57
• The survey identifies open challenges and research directions, and offers datasets and code to encourage practical applications and further methodological research.It argues that addressing the challenges could support more robust and effective DFL methods for complex optimization problems.Source: §7 · p. 57

Appendix A. Results on All Problem Instances

• Figures A1–A7 provide all-instance boxplots for grid shortest path, portfolio optimization, Warcraft shortest path, energy-cost aware scheduling, knapsack, diverse bipartite matching, and subset selection.The figures correspond to the problems in the order listed.Source: Appendix A · p. 57

Appendix B. Learning Curves

• Across the three scheduling instances, learning with Pairwise (diff) ranking loss is stable, whereas Listwise and Pairwise ranking losses do not stabilize.Figure A8 presents the learning curves for the LTR loss functions.Source: Appendix B · p. 57

Appendix C. Details about Hyperparameter Configuration

• Optimal hyperparameter combinations for each methodology and experiment are selected by grid search and provided in the repository for reproducibility.These configurations were used to evaluate all methodologies.Source: Appendix C · p. 57
• Comparative boxplots show relative-regret distributions for synthetic shortest path at ϑ = 0.5 and absolute-regret distributions for synthetic portfolio optimization at ϑ = 1.Source: Figure A1 · p. 58, Figure A2 · p. 59
• Comparative boxplots show relative-regret distributions for the Warcraft shortest path and knapsack problem instances.Source: Figure A3 · p. 60, Figure A5 · p. 62
• Comparative boxplots show relative-regret distributions for energy-cost aware scheduling and diverse bipartite matching; other plots show subset-selection mismatch rates and learning curves for energy scheduling and matching.Source: Figure A4 · p. 61, Figure A6 · p. 63, Figure A7 · p. 64