Differentiable optimization

Overview

A solver maps a cost vector to a decision. If a model predicts the costs and the decision is scored by its regret under the true costs, the training signal has to pass through the solver 2307.13565 §2.2. For linear and integer programs that map is piecewise constant. Its derivative is zero almost everywhere and does not exist at the breakpoints, so plain autodiff gives no useful gradient 2307.13565 §2.3.

Each method supplies a substitute for the missing factor in the chain rule, the derivative of the decision with respect to the predicted costs. The substitute is what distinguishes the methods 2307.13565 §2.3 2307.13565 §3.1. In the survey's setting the constraints are known and the costs are predicted from features by a model 2307.13565 §2.1.

Regret is not the only training target. A solver can also sit inside a controller and be trained to reproduce a reference output. LiveNet does this with a QP whose constraints are control barrier functions, trained by regression on the controls of an MPC 2412.04659 §4 2412.04659 §5.1. The chain-rule problem is the same. The loss decides which substitutes apply: the regret surrogates in the survey need the true costs, and a regression loss on a control does not 2307.13565 §3.1.4.

Variants

Differentiating a convex layer

OptNet, CvxpyLayers and Fold-opt return a layer that can sit anywhere in a network. OptNet handles convex QPs by implicit differentiation of the KKT conditions. CvxpyLayers differentiates the self-dual embedding of a convex cone program. Fold-opt differentiates the fixed point of an unrolled solver, and it also covers nonconvex problems 2307.13565 §3.1.1 2307.13565 tab. 1. Card: Decision-focused learning survey and benchmark.

LiveNet uses a convex QP of this kind inside a robot controller. Each robot runs a network that outputs a reference control and two sets of penalties. A QP with an identity quadratic term, a linear term from the reference, and one row per barrier inequality then adjusts the control. Supervised training backpropagates through the QP 2412.04659 §4 2412.04659 §5.1. Card: LiveNet.

Smoothing LPs and ILPs

These methods add a term that makes the LP relaxation differentiable. QPTL adds a quadratic term and differentiates the resulting QP. The quadratic term is dropped at test time 2307.13565 §3.1.2. HSD (Intopt) adds a log-barrier and differentiates the self-dual embedding 2307.13565 §3.1.2. Mipaal turns an ILP into an LP with cutting planes and then applies QPTL 2307.13565 tab. 1. All three work on the relaxation, not on the integer problem itself 2307.13565 §5.2.3. Card: Decision-focused learning survey and benchmark.

Perturbation and finite differences

These methods handle linear objectives. Each one estimates the derivative from solver outputs at perturbed costs.

• Negative identity treats the solver's Jacobian as −I 2307.13565 §3.1.3.
• DBB takes a finite difference at a costs vector nudged against the loss gradient 2307.13565 §3.1.3.
• I-MLE takes a finite difference with added noise 2307.13565 §3.1.3.
• DPO differentiates the perturbed optimiser 2307.13565 §3.1.3.
• Fenchel-Young (FY) uses a perturbed Fenchel-Young loss. It does not produce a layer 2307.13565 tab. 1.

Card: Decision-focused learning survey and benchmark.

Surrogate losses without a backward solve

These methods replace the regret with a surrogate whose gradient needs no solver call in the backward pass. None of them yields a layer 2307.13565 tab. 1.

• SPO uses an SPO+ subgradient, which needs two solver calls per step 2307.13565 §3.1.4.
• NCE, the learning-to-rank losses and LODL use surrogates over a set of feasible solutions or a learned convex local model 2307.13565 §3.1.4.
• Listwise, Pairwise, Pairwise (diff) and MAP work on a cache of feasible solutions. The cache starts from the training optima and grows by solving on a fraction p_solve of steps, 5% in the benchmark 2307.13565 §3.1.4 2307.13565 §5.2.

Gradient-free methods are surveyed but not benchmarked 2307.13565 §3.2 2307.13565 §5.2. Card: Decision-focused learning survey and benchmark.

When to use which

The benchmark covers seven problem sets and eleven methods, with results shown as box plots and only qualitative rankings in the text 2307.13565 §5.2. Treat the rankings as evidence about those problems, not a guide to yours.

Watch for these when you implement a method:

• Plain autodiff through a solver gives zero gradients for LPs and ILPs. The surrogate you choose is the method you run 2307.13565 §2.3.
• Ties at zero predicted cost make every feasible solution optimal. The benchmark assumes a fixed tie-breaking rule, so check your solver's behaviour before comparing numbers 2307.13565 §5.2.
• Relative regret is undefined when the true optimum has zero objective. The portfolio benchmark switches to absolute regret for that reason 2307.13565 §5.2.1.
• The grid spans several orders of magnitude for learning rate, damping and μ, and the best value changes by setting. Re-tune when problem size or solver changes 2307.13565 tab. 3.
• Runtime figures include system overhead. Only the ratios between methods are meaningful 2307.13565 §5.2.2.
• A QP layer can fail to solve, and the paper does not say what the network should output then. The authors' code returns a fallback instead, which the LiveNet card records as breaking its guarantee 2412.04659 §4 2412.04659 §6.
• Match the sign of the QP's linear term to the weights you load. LiveNet's paper writes the QP as a maximisation, while its code minimises with the opposite sign on the reference. Shipped weights expect the code's sign 2412.04659 §4. See the LiveNet card's Paper vs code section.
• Derive the second Lie derivative of the collision barrier yourself. The paper and code use cos(θ_i + θ_j). A derivation from the drift term gives a minus sign, and the paper does not settle the question 2412.04659 §4.1.

Implementation sketch

The loop is the same for every method. Only the substitute gradient changes. The SPO and DBB substitutes are short enough to state in full.

# Shared training loop for decision-focused learning  [arxiv:2307.13565 alg. 2]
# data: (features z, true costs c, optimal decision x_star)
# method_gradient: one of the substitutes below

def train(model, data, lr, epochs):
    # Repeat over the training set  [arxiv:2307.13565 alg. 2]
    for epoch in range(epochs):
        for z, c, x_star in data:
            # Predict the costs from the features  [arxiv:2307.13565 §2.2]
            c_hat = model(z)
            # Solve with the predicted costs  [arxiv:2307.13565 §2.1]
            x_hat = solve(c_hat)
            # Replace dx_hat/dc_hat, which is zero almost everywhere  [§2.3]
            g = method_gradient(c_hat, c, x_hat, x_star)
            # Backpropagate through the predictor  [arxiv:2307.13565 alg. 2]
            model.backward(g)
            model.step(lr)

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

def spo_gradient(c_hat, c):
    # Optimal decision under the true costs  [arxiv:2307.13565 §3.1.4]
    x_star = solve(c)
    # Decision under the perturbed costs 2 * c_hat - c  [arxiv:2307.13565 §3.1.4]
    x_perturbed = solve(2 * c_hat - c)
    # Subgradient of the SPO+ surrogate  [arxiv:2307.13565 §3.1.4]
    return x_star - x_perturbed

# Blackbox differentiation (DBB) as written in the paper  [arxiv:2307.13565 §3.1.3]
# dL_dx: gradient of the task loss at x_hat; delta: step size

def dbb_gradient(c_hat, dL_dx, delta):
    # Decision with the costs nudged against the loss gradient  [§3.1.3]
    x_nudged = solve(c_hat + delta * dL_dx)
    # Decision with the unchanged predicted costs  [arxiv:2307.13565 §3.1.3]
    x_hat = solve(c_hat)
    # The paper has no division by delta; the authors' code divides by it
    return x_nudged - x_hat

Contradictions

• Best method on Warcraft. The text names Listwise as best at sizes 12, 18 and 30, and also names SPO as best at size 30. Check the figure before citing a winner 2307.13565 §5.2.1 2307.13565 fig. 7.
• Paper and repository. The authors' repository differs from the paper in several places. It divides the DBB gradient by the step size 2307.13565 §3.1.3. It sums the pairwise losses over one representative per distinct true cost, not over every cached rival 2307.13565 §3.1.4. It draws the cache-growth coin once per mini-batch, not once per instance 2307.13565 §3.1.4. The card for this paper lists these differences in detail: Decision-focused learning survey and benchmark.
• Paper and repository, LiveNet. The LiveNet repository differs from its paper in fifteen listed places. Among them are the QP objective sign, the direction of the liveness critical points and the batch size 2412.04659 §4 2412.04659 §5.1. The card lists them: LiveNet.

Papers

• Decision-focused learning survey and benchmark: survey of gradient-based and gradient-free methods for training a predictor on decision regret, with a benchmark of eleven methods on seven problem sets 2307.13565 §5.2.
• LiveNet: Robust, Minimally Invasive Multi-Robot Control for Safe and Live Navigation in Constrained Environments: a neural controller whose QP layer adds collision and liveness barrier rows, trained by imitating an MPC; simulation results for two robots 2412.04659 §5.2.