Module perturbed_optimizer 

Differentiable combinatorial optimization via perturbed optimizers.

Implements the Perturbed Optimizer framework (Berthet et al., 2020) for making any black-box combinatorial solver differentiable through additive Gaussian noise perturbations.

Given a combinatorial optimizer y*(θ) = argmax_y θᵀ y (or argmin), the perturbed optimizer computes:

ŷ(θ) = E[y*(θ + σZ)] where Z ~ N(0, I)

The gradient is estimated as:

∇_θ L ≈ (1/σ) E[L(y*(θ + σZ)) · Z] (REINFORCE)

or via the reparameterized covariance estimator:

∇_θ L ≈ (1/σ) Cov[y*(θ + σZ), Z] · ∇_y L

Also includes SparseMap for structured prediction on the marginal polytope via QP.

References

• Berthet et al. (2020). “Learning with Differentiable Perturbed Optimizers.” NeurIPS.
• Niculae & Blondel (2017). “A regularized framework for sparse and structured neural attention.” NeurIPS.

Structs

PerturbedOptimizer

A differentiable wrapper around any black-box combinatorial optimizer.

PerturbedOptimizerConfig

Configuration for the perturbed optimizer.

SparseMap

A SparseMap layer: structured prediction with sparse marginals.

SparseMapConfig

Configuration for the SparseMap structured prediction layer.