Surrogate Losses

Surrogate losses replace the non-differentiable regret with a differentiable training objective.

The training loops on this page build on the Common Setup from Training Methods.

Smart Predict-then-Optimize+ Loss (SPO+)

SPO+ [1] is a convex surrogate for the SPO loss, also called regret: the decision error of the downstream optimization.

The derivation starts from the observation that for any \(\alpha \geq 0\),

\[\mathrm{regret}(\hat{\mathbf{c}}, \mathbf{c}) \leq \max_{\mathbf{w} \in \mathcal{S}} \big\{ \mathbf{c}^\top \mathbf{w} - \alpha\, \hat{\mathbf{c}}^\top \mathbf{w} \big\} + z^*(\alpha \hat{\mathbf{c}}) - z^*(\mathbf{c}).\]

Set \(\alpha = 2\). Because \(z^*\) is a minimum and \(\mathbf{w}^*(\mathbf{c})\) is feasible, \(z^*(2 \hat{\mathbf{c}}) \leq 2 \hat{\mathbf{c}}^\top \mathbf{w}^*(\mathbf{c})\). This gives the SPO+ loss,

\[\mathcal{L}_{\mathrm{SPO+}}(\hat{\mathbf{c}}, \mathbf{c}) = -z^*(2 \hat{\mathbf{c}} - \mathbf{c}) + 2\, \hat{\mathbf{c}}^\top \mathbf{w}^*(\mathbf{c}) - z^*(\mathbf{c}),\]

which is convex in \(\hat{\mathbf{c}}\) and upper-bounds the regret. By Danskin’s theorem, a subgradient is

\[2 \big( \mathbf{w}^*(\mathbf{c}) - \mathbf{w}^*(2 \hat{\mathbf{c}} - \mathbf{c}) \big) \in \frac{\partial \mathcal{L}_{\mathrm{SPO+}}(\hat{\mathbf{c}}, \mathbf{c})}{\partial \hat{\mathbf{c}}}.\]
class pyepo.func.SPOPlus(optmodel: optModel, processes: int = 1, solve_ratio: float = 1.0, reduction: Reduction = 'mean', dataset: optDataset | None = None)

SPO+ loss: a convex surrogate for the SPO regret of a linear-objective LP.

SPO+ upper-bounds the SPO regret with a convex function of the predicted cost vector and provides an informative subgradient (via Danskin’s theorem) for end-to-end training. It is the strong default for predict-then-optimize when true optimal solutions \(\mathbf{w}^*(\mathbf{c})\) are available as supervision.

The forward pass solves the perturbed problem with cost \(2\hat{\mathbf{c}} - \mathbf{c}\) once per training instance and returns a scalar loss; the backward pass uses the cached solution to form the subgradient \(2(\mathbf{w}^*(\mathbf{c}) - \mathbf{w}^*(2\hat{\mathbf{c}} - \mathbf{c}))\) without any extra solver call.

Reference: Elmachtoub & Grigas (2022) https://doi.org/10.1287/mnsc.2020.3922

forward(pred_cost: Tensor, true_cost: Tensor, true_sol: Tensor, true_obj: Tensor) → Tensor

Forward pass

processes sets the number of solver processes (0 uses all available cores).

Training loop:

spo = pyepo.func.SPOPlus(optmodel, processes=1)

for epoch in range(20):
    for x, c, w, z in dataloader:
        cp = predmodel(x)
        loss = spo(cp, c, w, z)
        optimizer.zero_grad()
        loss.backward()
        optimizer.step()

Perturbation Gradient (PG)

PG [2] is a surrogate loss based on zeroth-order gradient approximation.

By Danskin’s theorem, regret can be written as the directional derivative of \(z^*(\hat{\mathbf{c}})\) along \(\mathbf{c}\) (up to a constant independent of \(\hat{\mathbf{c}}\)). PG approximates this directional derivative with finite differences. Two variants are available, backward (two_sides=False) and central (two_sides=True):

\[\begin{split}\mathcal{L}_{\mathrm{PG}}^{\mathrm{back}}(\hat{\mathbf{c}}, \mathbf{c}) &= \frac{z^*(\hat{\mathbf{c}}) - z^*(\hat{\mathbf{c}} - \sigma \mathbf{c})}{\sigma}, \\ \mathcal{L}_{\mathrm{PG}}^{\mathrm{cent}}(\hat{\mathbf{c}}, \mathbf{c}) &= \frac{z^*(\hat{\mathbf{c}} + \sigma \mathbf{c}) - z^*(\hat{\mathbf{c}} - \sigma \mathbf{c})}{2 \sigma},\end{split}\]

where \(\sigma > 0\) is the finite-difference width (the sigma parameter). The corresponding gradient estimate is

\[\frac{\partial \mathcal{L}_{\mathrm{PG}}^{\mathrm{back}}(\hat{\mathbf{c}}, \mathbf{c})}{\partial \hat{\mathbf{c}}} \approx \frac{\mathbf{w}^*(\hat{\mathbf{c}}) - \mathbf{w}^*(\hat{\mathbf{c}} - \sigma \mathbf{c})}{\sigma}.\]
pyepo.func.PG

alias of perturbationGradient

sigma controls the finite-difference width. two_sides enables central differencing.

Training loop:

pg = pyepo.func.PG(optmodel, sigma=0.1, two_sides=False, processes=1)

for epoch in range(20):
    for x, c, w, z in dataloader:
        cp = predmodel(x)
        loss = pg(cp, c)
        optimizer.zero_grad()
        loss.backward()
        optimizer.step()

Footnotes