The Law of the Perturbed Optimizer

Perturb-and-MAP samples a combinatorial structure by adding noise to the scores of its elements and returning the optimal structure, as the Gumbel-max trick does for a single choice. Because optimizing can be easy where normalizing the Gibbs distribution is #P-hard, perturb-and-MAP draws are used in place of draws from that distribution, although the law they follow has been regarded as intractable. We prove that for fixed-size subsets, spanning trees and all other matroid bases, the two laws coincide at every score vector only when the structure splits into separate single choices, even with dependent noise entries. For assignments of three or more rows, no noise achieves this, so we instead show that the law under independent Gumbel noise is an integral of a determinant over the assignment problem's dual variables. This law gives the noise scale at which it agrees with the Gibbs distribution to first order in the scores, n/(n+1) for n×n assignments. Importance weights built from the law turn the draws into consistent estimates of that distribution's marginals, accurate to 0.001 on multi-target tracking scenes where belief propagation and Sinkhorn scaling err by 0.06 to 0.32.