Regularized Methods¶
A pure linear optimization layer is not differentiable: the optimal solution \(\mathbf{w}^*(\hat{\mathbf{c}}) = \arg\min_{\mathbf{w} \in \mathcal{S}} \hat{\mathbf{c}}^\top \mathbf{w}\) is piecewise constant in \(\hat{\mathbf{c}}\). It jumps between vertices of \(\mathcal{S}\), and its derivative is zero almost everywhere. Regularized methods fix this by adding a strongly convex regularizer \(\Omega\) to the linear objective, yielding a regularized solution
which is unique, lies inside \(\mathrm{conv}(\mathcal{S})\), and varies continuously with \(\hat{\mathbf{c}}\). This deterministic smoothing is dual to the stochastic smoothing of the perturbed methods: both replace the piecewise-constant solution map with a continuous surrogate, the former via a convex regularizer and the latter via Monte Carlo averaging over a noise distribution [1].
PyEPO implements the L2 special case \(\Omega(\mathbf{w}) = \tfrac{\lambda}{2} \|\mathbf{w}\|_2^2\) and solves the regularized program with batched Frank-Wolfe iteration. Frank-Wolfe accesses \(\mathrm{conv}(\mathcal{S})\) through the original LP/ILP solver for \(\mathcal{S}\), used as a linear minimization oracle. lambd is the L2 strength \(\lambda\). max_iter caps Frank-Wolfe iterations, and tol is the convergence tolerance.
The training loops on this page build on the Common Setup from Training Methods.
L2 Regularized Frank-Wolfe Optimizer (RFWO)¶
RFWO [1] exposes \(\hat{\mathbf{w}}_\lambda(\hat{\mathbf{c}})\) directly as a differentiable layer. Since it returns a regularized solution rather than a loss, the user defines a task loss on the output. A common choice is MSE against \(\mathbf{w}^*(\mathbf{c})\).
- pyepo.func.RFWO
alias of
regularizedFrankWolfeOpt
Training loop:
rfwo = pyepo.func.RFWO(optmodel, lambd=1.0, processes=1)
criterion = nn.MSELoss()
for epoch in range(20):
for x, c, w, z in dataloader:
cp = predmodel(x)
wr = rfwo(cp)
loss = criterion(wr, w)
optimizer.zero_grad()
loss.backward()
optimizer.step()
L2 Regularized Frank-Wolfe with Fenchel-Young Loss (RFYL)¶
RFYL [1] pairs the RFWO layer with the Fenchel-Young loss [2] of the regularizer \(\Omega\), returning a scalar loss that compares the predicted cost \(\hat{\mathbf{c}}\) to the true optimum \(\mathbf{w}^*(\mathbf{c})\).
For any convex regularizer \(\Omega: \mathrm{conv}(\mathcal{S}) \to \mathbb{R}\) with conjugate \(\Omega^*(\boldsymbol{\theta}) = \sup_{\mathbf{w}} \boldsymbol{\theta}^\top \mathbf{w} - \Omega(\mathbf{w})\), the Fenchel-Young loss is
The Fenchel-Young inequality gives three properties used by the training loss:
Non-negative, with equality iff \(\mathbf{w}^*(\mathbf{c}) = \hat{\mathbf{w}}_\Omega(\hat{\mathbf{c}})\).
Convex in \(\hat{\mathbf{c}}\).
By Danskin’s theorem, the gradient is the residual between the regularized prediction and the target,
\[\frac{\partial \mathcal{L}_\Omega^{\mathrm{FY}}(\hat{\mathbf{c}}, \mathbf{w}^*(\mathbf{c}))}{\partial \hat{\mathbf{c}}} = \mathbf{w}^*(\mathbf{c}) - \hat{\mathbf{w}}_\Omega(\hat{\mathbf{c}}),\]without differentiating through the Frank-Wolfe iterate.
PyEPO specializes this to \(\Omega(\mathbf{w}) = \tfrac{\lambda}{2}\|\mathbf{w}\|_2^2\). Substituting the closed form of \(\Omega^*\) and the definition of \(\hat{\mathbf{w}}_\lambda\) collapses the loss to
a “compare regularizers + linear residual” form. The gradient remains \(\mathbf{w}^*(\mathbf{c}) - \hat{\mathbf{w}}_\lambda(\hat{\mathbf{c}})\).
- pyepo.func.RFY
alias of
regularizedFrankWolfeFenchelYoung
Training loop:
rfyl = pyepo.func.RFY(optmodel, lambd=1.0, processes=1)
for epoch in range(20):
for x, c, w, z in dataloader:
cp = predmodel(x)
loss = rfyl(cp, w)
optimizer.zero_grad()
loss.backward()
optimizer.step()
Footnotes