Decision-focused learning

Overview

Many decisions are chosen by a solver from numbers that must first be predicted: travel times, costs, values. The usual pipeline fits the predictor to those numbers with a prediction loss such as MSE, then hands the predictions to the solver. The survey's point is that accurate predictions do not guarantee a good decision. A small error can flip the decision, and a large error may not 2307.13565 §2.2.

Decision-focused learning (DFL) trains the predictor on a task loss instead, most often the regret: the true objective of the decision the solver picks, minus the true optimum 2307.13565 §2.2. Regret needs the true costs at training time.

The obstacle is the solver. For linear and integer programs, the map from predicted costs to the chosen decision is piecewise constant. Its derivative is zero almost everywhere and does not exist at the breakpoints, so plain autodiff through the solver returns zero gradients 2307.13565 §2.3. Every method therefore replaces the missing derivative with a substitute. Choosing the substitute is choosing the method. Solving the problem at every training step is also costly for hard instances 2307.13565 §2.3.

Variants

The survey sorts gradient-based methods into four classes: analytical differentiation, analytical smoothing, random perturbation and surrogate losses 2307.13565 §3.1. Gradient-free methods are reviewed but not benchmarked 2307.13565 §3.2, §5.2. The three families below group those classes by the kind of substitute they use; the grouping is this page's, not the paper's. No method has its own card yet, so each name is given without a link. The card for the survey, which covers all of them, is Mandi et al. survey and benchmark.

Differentiated optimality conditions (exact layers)

These methods keep the solver as a differentiable layer inside the network. They differentiate the solver's optimality conditions or the fixed point of an unrolled solver. They cover convex quadratic programs (OptNet, the cone-program layers of cvxpylayers, and fixed-point differentiation of unrolled solvers). For LPs and ILPs they first add a quadratic term, a log-barrier, or a self-dual embedding to create a smooth problem (QPTL, Intopt/HSD, Mipaal) 2307.13565 tab. 1, §3.1.1, §3.1.2. The smoothing term is removed or tuned at test time, which the card reports for QPTL 2307.13565 §5.2.

Smoothing by perturbation or finite difference

For linear objectives these methods estimate a gradient by probing the solver: a finite difference at nudged costs (DBB), a finite difference with injected noise (I-MLE), or the gradient of a randomly perturbed optimizer (DPO). The perturbed Fenchel-Young loss (FY) is a separate loss that uses the same kind of perturbed solutions. These methods can serve as layers, except FY, which does not 2307.13565 tab. 1, §3.1.3. Each one calls the solver several times per step.

Solver-free surrogate losses

These replace the solver in the backward pass with a surrogate. SPO takes a subgradient of the SPO+ surrogate and needs two solver calls per step 2307.13565 §3.1.4. The solution-cache family (Listwise, Pairwise, Pairwise (diff), MAP) keeps a set of feasible solutions and scores the true optimum against them. The cache starts from the training optima and grows with the solver on a fraction p_{solve} of steps. The benchmark used 5% 2307.13565 §3.1.4, §5.2. NCE, LTR losses and the learned surrogate LODL belong here too but are not in the benchmark. None of these are layers 2307.13565 tab. 1.

When to use which

The survey's benchmark covers 11 methods on 7 problem sets with test regret averaged over 10 seeds. The paper gives qualitative rankings in the text and shows numbers only in box plots 2307.13565 §5.2. The rows below use only those rankings and the cost and structure notes the paper gives.

Two cautions apply to every row. First, no method won on every problem set 2307.13565 §5.2.3. Second, the grid for learning rate and each method's parameters spans several orders of magnitude, and the best value changes with the setting. The paper tuned by grid search on validation regret, so budget for re-tuning when size or solver changes 2307.13565 tab. 3, §5.2.

Implementation sketch

The common core is the same for every method. Only the substitute gradient differs.

# Common loop for decision-focused training  [§2.2] [alg. 2]
# data: (features z, true costs c, optimal decision x_star); lr: learning rate

for epoch in range(epochs):
    for z, c, x_star in data:
        # Predict the cost vector from the features  [§2.2]
        c_hat = model(z)
        # Solve the downstream problem with the predicted costs  [§2.2]
        x_hat = solve(c_hat)
        # Regret of x_hat under the true costs (linear objective)  [§2.2]
        regret = dot(c, x_hat) - dot(c, x_star)
        # Method-specific substitute for dx_hat/dc_hat  [§2.3] [§3.1]
        g = surrogate_gradient(c_hat, c, x_star, regret)
        # Backpropagate g through the model  [alg. 2]
        model.backward(g)

The SPO subgradient needs no differentiation through the solver. It takes two solver calls §3.1.4:

# SPO subgradient with respect to the predicted costs  [§3.1.4]
# solve(c) returns an optimal decision for costs c

def spo_surrogate(c_hat, c):
    # Optimal decision under the true costs  [§3.1.4]
    x_star = solve(c)
    # Decision under the perturbed costs 2 * c_hat - c  [§3.1.4]
    x_pert = solve(2 * c_hat - c)
    # Subgradient with respect to c_hat  [§3.1.4]
    return x_star - x_pert

A cache-based loss needs the solver only when the cache grows §3.1.4. The Listwise form scores the cached solutions with a tempered softmax under the true and predicted costs §3.1.4:

# Listwise loss over a cache of feasible solutions  [§3.1.4]
# cache: (|S|, n) feasible solutions, including the true optimum
# tau: softmax temperature

def listwise_loss(c_hat, c, cache, tau):
    # Cost of every cached solution under true and predicted costs  [§3.1.4]
    costs_true = cache @ c
    costs_hat = cache @ c_hat
    # Tempered-softmax probabilities under each cost vector  [§3.1.4]
    p_true = softmax(-costs_true / tau)
    log_p_hat = log_softmax(-costs_hat / tau)
    # Cross-entropy averaged over the cache  [§3.1.4]
    return -mean(p_true * log_p_hat)

Where the variants differ: only the surrogate_gradient line and whatever the cache is built from. Exact layers return a gradient from the solver's optimality conditions. Perturbation methods average several solver calls on noisy costs. Cache losses call the solver only when the cache grows.

The paper's repository departs from its text in ways that matter when you implement. Its DBB gradient divides the finite difference by the step size, which the paper's equation does not 2307.13565 §3.1.3. It also grows the solution cache once per mini-batch, where the paper describes a draw per instance 2307.13565 §3.1.4. Several hyperparameter values in the repository fall outside the paper's grid 2307.13565 tab. 3. Read the card's Paper vs code section before reproducing a number.

Contradictions

• Warcraft winner at size 30. The text names Listwise as best for sizes 12, 18 and 30, and also names SPO as best for size 30. The figure should settle it; check it before citing a winner 2307.13565 §5.2.1, fig. 7.

No disagreements between papers are known. This page rests on one card, so it cannot report any.

Papers

• Mandi et al. survey and benchmark: survey of gradient-based and gradient-free DFL methods, and a benchmark of 11 methods on 7 problem sets.