Perturbed Methods¶
Perturbed methods estimate gradients by Monte Carlo averaging over random perturbations of the cost vector. They share two design knobs: n_samples (number of Monte Carlo samples) and sigma (perturbation amplitude).
The training loops on this page build on the Common Setup from Training Methods.
Differentiable Perturbed Optimizer (DPO)¶
DPO [1] uses Monte Carlo sampling to estimate solutions by optimizing randomly perturbed costs. Its custom backward pass provides a gradient estimator for end-to-end training. DPO is the additive Gaussian version; DPOMul is the multiplicative version for sign-sensitive oracles [2]. The multiplicative variant assumes predicted costs already have the intended nonzero sign. For nonnegative-cost problems, use a positive-output predictor such as nn.Softplus() with a small epsilon.
DPO replaces the piecewise-constant solution map \(\hat{\mathbf{c}} \mapsto \mathbf{w}^*(\hat{\mathbf{c}})\) with the expectation over a random perturbation,
where \(\boldsymbol{\xi} \sim \mathcal{N}(\mathbf{0}, \mathbf{I})\) and \(K\) is n_samples.
The multiplicative variant DPOMul perturbs each entry of \(\hat{\mathbf{c}}\) as
with \(\odot\) the Hadamard product. The exponential factor preserves the sign of each cost entry, which is required when the solver expects, e.g., nonnegative edge costs.
- pyepo.func.DPO
alias of
perturbedOpt
- pyepo.func.DPOMul
alias of
perturbedOptMul
Training loop (swap predmodel for positive_predmodel when using DPOMul):
dpo = pyepo.func.DPO(optmodel, n_samples=10, sigma=0.5, processes=1)
# if using DPOMul, replace predmodel with positive_predmodel below
# dpo = pyepo.func.DPOMul(optmodel, n_samples=10, sigma=0.5, processes=1)
criterion = nn.MSELoss()
for epoch in range(20):
for x, c, w, z in dataloader:
cp = predmodel(x)
we = dpo(cp)
loss = criterion(we, w)
optimizer.zero_grad()
loss.backward()
optimizer.step()
Perturbed Fenchel-Young Loss (PFYL)¶
PFYL [1] uses the same perturbed expected solution as DPO inside a Fenchel-Young loss and compares it directly with the true optimal solution. It returns a scalar loss. PFY is the additive Gaussian version; PFYMul is the multiplicative sign-preserving variant with the same sign convention as DPOMul.
Let \(F(\hat{\mathbf{c}}) = \mathbb{E}_{\boldsymbol{\xi}}\big[ \min_{\mathbf{w} \in \mathcal{S}} (\hat{\mathbf{c}} + \sigma \boldsymbol{\xi})^\top \mathbf{w} \big]\) be the expected perturbed minimum, and let \(\Omega\) be its Fenchel conjugate. The perturbed Fenchel-Young loss is
The dual term \(\Omega(\mathbf{w}^*(\mathbf{c}))\) does not depend on \(\hat{\mathbf{c}}\), so the gradient collapses to a simple difference of solutions,
The multiplicative variant uses the same sign-preserving perturbation,
- pyepo.func.PFY
alias of
perturbedFenchelYoung
- pyepo.func.PFYMul
alias of
perturbedFenchelYoungMul
Training loop (swap predmodel for positive_predmodel when using PFYMul):
pfy = pyepo.func.PFY(optmodel, n_samples=10, sigma=0.5, processes=1)
# if using PFYMul, replace predmodel with positive_predmodel below
# pfy = pyepo.func.PFYMul(optmodel, n_samples=10, sigma=0.5, processes=1)
for epoch in range(20):
for x, c, w, z in dataloader:
cp = predmodel(x)
loss = pfy(cp, w)
optimizer.zero_grad()
loss.backward()
optimizer.step()
Implicit Maximum Likelihood Estimator (I-MLE)¶
I-MLE [3] uses the perturb-and-MAP framework. It samples noise from a Sum-of-Gamma distribution and interpolates the loss function to approximate finite differences. lambd controls the interpolation step.
I-MLE is framed as imitation learning: bring the model distribution \(p(\mathbf{w} \mid \hat{\mathbf{c}})\) closer to a target distribution \(q(\mathbf{w} \mid \hat{\mathbf{c}})\) by minimizing their KL divergence. An upstream task gradient \(\mathbf{d} = \nabla_{\mathbf{w}} \mathcal{L}(\hat{\mathbf{c}}, \cdot) \big|_{\mathbf{w} = \mathbf{w}^*(\hat{\mathbf{c}})}\) induces a virtual update \(\hat{\mathbf{c}}' = \hat{\mathbf{c}} + \lambda \mathbf{d}\), and the gradient is estimated by a directional finite difference between the smoothed solutions at \(\hat{\mathbf{c}}'\) and \(\hat{\mathbf{c}}\):
where \(\sigma\) smooths the solution map and \(\lambda\) (lambd) is the finite-difference step. The same noise realization \(\boldsymbol{\xi}_\kappa\) is shared across the two perturbed evaluations to reduce variance.
- pyepo.func.IMLE
alias of
implicitMLE
Training loop:
imle = pyepo.func.IMLE(optmodel, n_samples=10, sigma=1.0, lambd=10, processes=1)
criterion = nn.L1Loss()
for epoch in range(20):
for x, c, w, z in dataloader:
cp = predmodel(x)
we = imle(cp)
loss = criterion(we, w)
optimizer.zero_grad()
loss.backward()
optimizer.step()
Adaptive Implicit Maximum Likelihood Estimator (AI-MLE)¶
AI-MLE [4] extends I-MLE with an adaptive interpolation step.
AI-MLE uses the same finite-difference estimator as I-MLE, but replaces the fixed step size \(\lambda\) with an adaptive choice driven by the magnitudes of the predicted cost and the upstream gradient,
where \(\mathbf{d}\) is the upstream task gradient and \(\alpha_t > 0\) is tuned online. When an exponential moving average of the fraction of nonzero gradient entries drops below one, \(\alpha_t\) is increased; otherwise it is decreased. This rescaling keeps the perturbation magnitude commensurate with \(\hat{\mathbf{c}}\) and decouples the step from the absolute scale of \(\mathbf{d}\), removing the need to tune \(\lambda\) by hand.
- pyepo.func.AIMLE
alias of
adaptiveImplicitMLE
Training loop (the adaptive step works with far fewer samples than I-MLE):
aimle = pyepo.func.AIMLE(optmodel, n_samples=2, sigma=1.0, processes=1)
criterion = nn.L1Loss()
for epoch in range(20):
for x, c, w, z in dataloader:
cp = predmodel(x)
we = aimle(cp)
loss = criterion(we, w)
optimizer.zero_grad()
loss.backward()
optimizer.step()
Footnotes