Source-linked AI summary
Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization
Bryan Wilder, Bistra Dilkina, Milind Tambe
TL;DR
Conventional pipelines train predictive models for accuracy and then optimize their predictions, even when accuracy is misaligned with decision quality. The paper introduces decision-focused learning, using continuous relaxations and differentiation through optimization for combinatorial problems. Across domains, it often improves decision quality over traditional methods, although differentiability can be limited by non-concavity and local optima.
Problem
Two-stage training minimizes task-agnostic predictive loss without specifically considering how predictions will perform in downstream combinatorial decision making.
Method
The framework jointly trains prediction and optimization by relaxing discrete problems continuously and differentiating the relaxed solution with respect to model predictions.
Results
Decision-focused methods often improve whole-pipeline decision quality over traditional methods, even when their standard predictive accuracy is worse.
Takeaways & Limitations
Standard accuracy measures are not reliable proxies for optimization utility, while training on the true decision objective can improve outcomes across decision problems.
Takeaways & Limitations
Non-concavity can make continuous optimization solutions nondifferentiable because algorithms may switch between non-unique local optima.
Abstract
from arXiv · showhide
Creating impact in real-world settings requires artificial intelligence techniques to span the full pipeline from data, to predictive models, to decisions. These components are typically approached separately: a machine learning model is first trained via a measure of predictive accuracy, and then its predictions are used as input into an optimization algorithm which produces a decision. However, the loss function used to train the model may easily be misaligned with the end goal, which is to make the best decisions possible. Hand-tuning the loss function to align with optimization is a difficult and error-prone process (which is often skipped entirely). We focus on combinatorial optimization problems and introduce a general framework for decision-focused learning, where the machine learning model is directly trained in conjunction with the optimization algorithm to produce high-quality decisions. Technically, our contribution is a means of integrating common classes of discrete optimization problems into deep learning or other predictive models, which are typically trained via gradient descent. The main idea is to use a continuous relaxation of the discrete problem to propagate gradients through the optimization procedure. We instantiate this framework for two broad classes of combinatorial problems: linear programs and submodular maximization. Experimental results across a variety of domains show that decision-focused learning often leads to improved optimization performance compared to traditional methods. We find that standard measures of accuracy are not a reliable proxy for a predictive model's utility in optimization, and our method's ability to specify the true goal as the model's training objective yields substantial dividends across a range of decision problems.
Introduction
The paper introduces decision-focused learning, which integrates prediction and combinatorial optimization so models train for decision quality rather than predictive accuracy alone. It uses continuous relaxations to enable gradient-based training and instantiates the framework for linear programs and submodular maximization.
- Framework: Decision-focused learning trains predictive models jointly with optimization to improve the quality of induced decisions.The framework replaces separate prediction and optimization stages with a single end-to-end system.
- Framework: The method relaxes a discrete problem continuously, differentiates the relaxed optimum with respect to predictions, and rounds the solution at test time.This continuous proxy allows gradient-based training despite discrete decisions.
- Problem classes: The framework is instantiated for linear programs and submodular maximization, including applications such as shortest path, maximum flow, matching, and recommendation.Both classes provide relaxations that can be efficiently differentiated through.
- Empirical findings: Decision-focused methods often improve whole-pipeline decision quality despite worse predictive accuracy under standard measures.The experiments compare decision-focused and traditional methods across multiple domains.
Problem description
The paper studies combinatorial decisions whose objective parameters are unknown and must be inferred from features and historical data. It asks whether training directly for downstream decision performance can outperform the conventional accuracy-focused two-stage approach.
- Problem formulation: The optimization problem maximizes an objective over a discrete feasible set, with unknown parameters that determine the value of each decision.In bipartite matching, for example, the parameters contain rewards for matching node pairs.
- Problem formulation: At test time, a model predicts parameters from observed features, optimization selects a decision, and utility is evaluated using the true parameters.Training instances consist of feature-parameter pairs drawn independently from a joint distribution.
- Learning objective: The learning goal is to choose a model that maximizes expected performance on the underlying optimization task.The model maps observed features to objective parameters.
- Two-stage baseline: The classical two-stage approach minimizes a task-agnostic loss such as mean squared error before using predictions for optimization.Its accuracy objective does not specifically account for downstream decision quality.
- Research question: The central question is whether explicitly training the predictive model for the decision problem can yield better outcomes.This question targets the alignment between model training and optimization performance.
Previous work
Prior work connects machine learning with discrete optimization, but largely treats prediction accuracy and optimization as separate goals. This paper distinguishes its approach by training predictive models directly on combinatorial decision performance and addressing discrete differentiation challenges.
- Machine learning and discrete optimization: Previous research has used discrete optimization to find accuracy-maximizing models or machine learning to accelerate optimization algorithms.The paper characterizes its contribution as a deeper synthesis of the two areas.
- Convex optimization: Task-based convex optimization differentiates through learned-parameter optimization, but it addresses continuous rather than combinatorial problems.The paper uses related differentiation ideas while treating the additional challenges of discrete settings.
- Structured prediction: Structured prediction seeks to predict an element in a discrete set, whereas this work optimizes to find the best decision rather than an externally specified quantity.The distinction concerns the objective of prediction and decision making.
- Submodular methods: A differentiable submodular method predicts user choices by maximizing the likelihood of a fixed set, rather than optimizing for the best set.The paper identifies this difference as a key distinction from its decision-focused setting.
- Differentiation methods: Unrolling gradient-descent iterations can be costly for constrained combinatorial problems, so the paper analytically differentiates through KKT conditions instead.Projection steps needed to enforce feasibility make direct unrolling difficult.
General framework
Decision-focused learning integrates combinatorial optimization into gradient-based training by differentiating through continuous relaxations, while preserving guarantees or tractable backward passes in key problem classes.
- General framework: The framework replaces the nondifferentiable discrete optimizer with a continuous relaxation whose solution can be differentiated with respect to model predictions.At test time, the continuous solution is rounded or the true discrete problem is solved.
- General framework: Gradients combine the objective’s sensitivity to decisions, the optimizer’s sensitivity to predictions, and the predictive model’s parameter derivatives.The middle term is obtained by differentiating KKT conditions and solving the resulting linear system.
- General framework: The framework is instantiated for linear programs and submodular maximization, requiring differentiable relaxations, suitable forward solvers, and efficient backward-pass computations.These classes cover applications including shortest path, maximum flow, matching, social networks, and recommendation systems.
- Linear programming: For linear programs, squared-norm regularization produces a strongly concave quadratic program with a solution differentiable almost everywhere under stated feasibility and rank conditions.The regularized solution’s original linear objective is at least OPT − γD.
- Linear programming: The regularized linear-program surrogate provides an approximation guarantee while enabling straightforward differentiation through primal-dual solutions.At test time, setting γ = 0 produces an integral decision.
- Submodular maximization: For submodular maximization, non-concavity can make optimizer outputs discontinuous under infinitesimal prediction changes, so the forward algorithm must be chosen carefully.The paper identifies local-optimum nonuniqueness as the source of this differentiation difficulty and uses projected stochastic gradient ascent.
Experiments
Across synthetic and real-data domains, decision-focused learning generally produced better optimization decisions than two-stage methods, despite often lower standard predictive accuracy. The experiments show that aligning training with decision quality can matter as much as, or more than, predictive accuracy and model expressiveness.
- Overall results: Decision-focused methods obtained the highest full-pipeline solution quality across domains, tying random forests on synthetic budget allocation.Solution quality is measured by evaluating each decision's objective value using the true parameters.
- Budget allocation: In budget allocation, decision-focused networks achieved at least 37% greater objective value than two-stage neural networks.With the predictive architecture fixed, the comparison isolates the effect of the training method.
- Bipartite matching: In bipartite matching, NN2-Decision made nearly over 70% more matches than the next-best method, while one-layer models performed extremely poorly.The results indicate that this more complex learning problem benefits from a more expressive model class, while alignment remains important.
- Diverse recommendation: In diverse recommendation, NN1-Decision led performance and achieved approximately 2.7 times the objective value of NN1-2Stage.NN2-2Stage trailed NN2-Decision by 23%, while RF-2Stage performed near random.
- Predictive accuracy: Two-stage methods were usually more accurate by standard measures, but no accuracy measure was well-correlated with solution quality.Decision-focused networks had the worst MSE in budget allocation, while two-stage models led some classification metrics despite worse decisions.
- Learned representations: Decision-focused predictions could look dissimilar to ground truth yet still yield the best decisions by emphasizing optimization-relevant structure.In the channel-level analysis, NN1-Decision's predicted out-weights had r2 = 0.94 correlation with ground truth, despite skewed magnitudes.
Proofs
The proofs establish differentiability and structural properties needed for the decision-focused optimization framework, including handling dependent constraints and cardinality-constrained sets.
- Theorem 1: The Hessian is γI and therefore positive definite in the relevant argument.
- Theorem 1: Linearly dependent constraint rows can be removed without changing the feasible region when feasibility forces their right-hand sides to match.The argument applies inductively to eliminate redundant constraints.
- Theorem 2: Theorem 2 begins by selecting a maximum-norm point in the convex hull of the feasible set and applies the reverse triangle inequality.
- Theorem 3: For cardinality-constrained sets, the convex hull is described by −Ix ≤ 0 and 1⊤x ≤ k, with a full-row-rank constraint matrix.Although F is not concave, stationary points satisfy KKT conditions, which can be differentiated using the implicit function theorem.
- Theorem 1: Theorem 1 uses the implicit function theorem to establish derivatives when the relevant right-hand-side matrix is invertible almost everywhere.The derivative satisfies the displayed conditions in a neighborhood of the solution.
Visualizations
The visualizations compare decision-focused and two-stage predictions for diverse recommendation and bipartite matching, including predicted item out-weights.
- Diverse recommendation: Figure 3 arranges diverse-recommendation outputs top-to-bottom as ground truth, NN2-Decision, and NN2-2Stage predictions.The comparison focuses on how the two prediction methods resemble the ground truth.
- Diverse recommendation: Figure 4 compares diverse-recommendation predicted out-weights, with NN2-2Stage on the left and NN2-Decision on the right.
- Bipartite matching: Figure 5 places the bipartite-matching ground-truth adjacency matrix, NN2-Decision prediction, and NN2-2Stage prediction from left to right.The figure enables direct comparison of predicted matching structure against the ground truth.