acceptodds
Under review as a conference paper at ICLR 2027

The Law of the Perturbed Optimizer

13 views

Abstract

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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
perturb-and-MAP, Gumbel-max trick, Gibbs distribution, importance sampling

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_qoMiOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper is addressing probabilistic combinatorial optimisation, in which we need to assign the values of one variable (e.g. measurements) to the values of another (e.g. sensors) with a probability. Each assignment is assumed to have a score, and so we want to find the probability of each assignment, p(x)∝escorep(x) \propto e^{score} (a Gibbs distribution). The issue is that if we want to find p(x)p(x), we have to marginalise over all combinations with that assignment of xx, and the number of possible assignments scale as n!n!, so this quickly becomes intractable. As a result, despite the optimal allocation being reasonably easy to find (i.e. select the assignments with the highest score), determining p(x)p(x) is difficult.

Perturb & MAP's solution is to take the optimal set of scores (easy to find), add random noise and find the resulting best assignments. This process is repeated thousands of times, each output of which is treated as a sample. However, after sampling, the assignments no longer follow a Gibbs distribution. This paper derives the assignments' distribution after sampling, and shows how to correct them to be Gibbs distributed.

Critical strengths

I've been thinking carefully about this, but have struggled to identify concrete strengths supporting acceptance. The technical aspects of the work are rigorous, but until my concerns about motivation are resolved, I'm not convinced they're significant enough to warrant acceptance.

Critical weaknesses

There are 2 key issues I would need to see resolved to change my score:

1. Clarity

This paper is exceptionally difficult to read - it is littered with technical jargon that's very difficult to interpret and has little intuitive explanation. There is far far too much assumed knowledge of probabilistic combinatorial optimisation, Perturb-and-MAP and Gumbel-max. These things should be explained much more carefully. Accordingly, it takes a lot of additional reading to understand the problem being solved, and as far as I could tell no motivated is provided at all. The introduction needs to make it substantially clearer what probabilistic combinatorial optimisation is, why it's important, common areas where you might see these problems, how Perturb-and-MAP solves them, limitations of Perturb-and-MAP, and where this paper's contribution lies.

2. Motivation

The paper leaps into technical jargon from the first sentence of the abstract without motivating the problem at all. I could not understand why probabilistic combinatorial optimisation is important, common approaches to solving it, why perturb-and-map is the norm and what its limitations are. As a result, it's very difficult to interpret the technical significance of the work. More than this, it appears to me to solve a problem that is reasonably inconsequential. More detail on this is provided in the text below.

Questions for authors

I thank the authors for the work they've put into the paper, and while I appreciate my review scores are low, I have tried to offer the most honest and thorough assessment of their work of which I am capable. Aside from clarity, my key issue with this work was its motivation, which has left me with a couple of clarifying questions:

1. When is probabilistic combinatorial optimisation important?

What are real-world scenarios where probabilistic combinatorial optimisation is important? The example mentioned in Section 6 is multi-target tracking, which is extraordinarily broad. In computer vision, where the sensor is a camera, this optimisation isn't difficult at all - being able to maintain tracks between successive images is largely solved and reasonably inconsequential. As a result, I don't understand why this is a problem worth pursuing, and moreover, if it's straightforward to find the optimal allocation - when is it important to know the allocation uncertainty?

2. Why can't we just use Perturb-and-MAP?

My understanding is that modern approaches to combinatorial optimisation allocate a score to each assignment, say that the true distribution must follow a Gibbs distribution (p(x)∝escorep(x) \propto e^{score}), and use Perturb-and-MAP to estimate assignment probabilities. This work is then showing that the result after Perturb-and-MAP does not follow a Gibbs distribution, and therefore proves the corrections required to estimate a Gibbs distribution. However I don't understand why we need these to follow a Gibbs distribution. I can understand that the perturb-and-MAP sampling technique might lead to a slightly incorrect distribution, but surely in the real world all score metrics will always be imperfect and noisy, so why can we be so confident that the true probabilities are proportional to escoree^{score}? Surely instead, this is just an imperfect model we use to make a good allocation decision, and if so then why does the error introduced by perturb-and-MAP need correcting - why can't we just use the results from perturb-and-MAP? This question is the reason for my "Soundness" score of 2, as it is not clearly explained in the paper.

3 comments
AuthorsOpenReview ↗

Response to Reviewer qoMi (1/3)

Thank you for your honest and careful review, and for stating precisely what would have to change. We agree that the submitted version had shortcomings in the clarity of its writing and presentation, and that it did not motivate its problem clearly. We have substantially rewritten the abstract and the introduction and added a pen-and-paper example to the main text. The theorems are unchanged in content apart from one added case, and new and substantively changed text is marked in red in the revised paper.

Clarity. The revised introduction follows the order that you propose: the problem, where it arises and why it matters, how perturb-and-MAP addresses it and where it falls short, and what the paper contributes. It explains the Gibbs distribution, perturb-and-MAP and the Gumbel-max trick where they first appear, and the new Section 2.3 works out a small pen-and-paper example with two rows and two columns, that is, two tracks and two measurements. The paragraphs below give the motivation along the lines of the revised introduction.

Motivation. Many models need probabilities over whole structures, such as a subset of kk out of nn items, a ranking, a spanning tree or a matching of two sets, which we call an assignment. A structure with score ss, the sum of the scores of its elements, has probability proportional to ese^{s}. This is the Gibbs distribution, and the problem of the paper is to sample from it and to compute probabilities under it. In machine learning the structure is a hidden part of a model, such as a latent subset, permutation or matching (Niepert et al., 2021; Mena et al., 2018; Linderman et al., 2018), and training on observed structures uses these probabilities, which make up the gradient of the log-likelihood (Berthet et al., 2020). In survey sampling, kk units are drawn from a population with unequal probabilities, for example firms in proportion to their size. A classical design for this, the rejective sampling of Hájek (1964), is the Gibbs distribution on the subsets of size kk.

Tracking is a third case. A tracker that follows several nearby targets receives a set of position measurements at every scan and does not know which measurement belongs to which target. It can find the best assignment of measurements to targets, but if it commits to this assignment and part of it is wrong, it updates a track with the measurement of another target. It needs the probability that a given measurement belongs to a given target, by which to weight the measurements. Question 1 below develops this example.

In all these cases the best structure is easy to find, by sorting, by a greedy algorithm or by the Hungarian algorithm. Probabilities are harder, because the probability of an element is a sum over all structures that contain it. With nn tracks and nn measurements the normalizing sum runs over n!n! assignments and is #P-hard to compute.

Perturb-and-MAP turns the easy problem into a sampler. It adds random noise to the score of every element and returns the best structure for the perturbed scores, so one sample takes one run of the optimization algorithm. For a single choice among several options with independent standard Gumbel noise this is the Gumbel-max trick, whose samples follow the Gibbs distribution exactly. Independent Gumbel noise on every whole structure would also be exact, but there can be exponentially many structures. Perturb-and-MAP puts the noise on the elements, so that the fast algorithm still applies, and its samples then follow a different distribution in general. Since its introduction for random fields in computer vision (Papandreou and Yuille, 2011), the method has been applied to subsets, permutations, assignments and other structures (Tarlow et al., 2012; Kool et al., 2019; Mena et al., 2018; Paulus et al., 2020; Berthet et al., 2020; Niepert et al., 2021). The distribution that its samples follow has been regarded as intractable (Papandreou and Yuille, 2011; Mena et al., 2018), so the difference from the Gibbs distribution was hard to quantify.

The paper quantifies this difference and shows how to correct for it. We prove that, apart from the simplest cases, no choice of noise makes the samples follow the Gibbs distribution for all scores. For assignments under independent Gumbel noise we give the distribution that the samples follow as an explicit formula. From this formula we obtain weights that turn the samples into estimates that converge to the probabilities under the Gibbs distribution. For the tracking task the weights give a new estimator of the pairing probabilities. On scenes with 30 closely spaced targets its mean error on the ambiguous pairings is 0.005. Belief propagation, an enumeration of the likeliest assignments and a Markov chain, the methods that trackers use, have about 5 to 18 times this error, the last two even with budgets one to three orders of magnitude larger than ours (Section 6).

AuthorsOpenReview ↗

Response to Reviewer qoMi (2/3)

Question 1. When the uncertainty of the allocation matters. It matters when the best allocation is likely to be wrong in part and a wrong pairing has consequences, and tracking shows both. A sonar that follows several nearby targets keeps a track for each of them, an estimate of its motion. Every scan returns a set of measurements, which may include false alarms, called clutter, and the sonar cannot tell which measurement came from which target. An assignment pairs each track with a different measurement or marks it as missed. The sensor model gives every assignment a score that combines how well the measurements fit the tracks with how likely the misses and false alarms are, and given the scan an assignment with score ss has posterior probability proportional to ese^{s}.

The best assignment is easy to find, but that does not make it likely to be correct. On our simulated random scenes, with 20 targets that are close together compared with the uncertainty of their predicted positions, all detected and without clutter, a measurement that the best assignment gives to a track belongs to that track with posterior probability 0.18 on average (Appendix F.3). In expectation, about 16 of its 20 pairings are therefore wrong. A tracker that commits to this assignment updates those tracks with the measurements of other targets, which pulls them toward the wrong targets. Probabilistic data association was introduced for this reason. Instead of committing to one assignment, it updates every track with every measurement, weighted by the probability that the measurement belongs to that track (Bar-Shalom and Tse, 1975), and Fortmann et al. (1983) used it to track multiple targets by sonar. Current trackers approximate the same probabilities by belief propagation (Williams and Lau, 2014). The probabilities of the pairings, which express the uncertainty of the allocation, are thus what such a tracker needs at every scan.

How hard the association is depends on the sensor. A radar or a sonar returns positions, and when targets are close together compared with the measurement noise, one measurement can fit several tracks. A camera also records what an object looks like, so the same object can be recognized in the next frame, and this often settles the association, as you note. When the objects look alike, trackers have to rely more on position and motion, as with a radar. Two recent benchmarks show this case. In DanceTrack the people look alike and move in diverse ways, and state-of-the-art trackers perform markedly worse on it than on earlier benchmarks (Sun et al., CVPR 2022). On the sports benchmark SportsMOT the authors identify association as the key challenge (Cui et al., ICCV 2023). A camera can thus leave several plausible assignments as well, and when the probability is spread over them, even the best one is unlikely to be correct.

AuthorsOpenReview ↗

Response to Reviewer qoMi (3/3)

Question 2. Can we just use perturb-and-MAP? If only the best allocation were needed, the Hungarian algorithm would give it and no sampling would be required. Perturb-and-MAP is used when probabilities are needed, and the frequencies of its samples converge to the probabilities of its own distribution. What follows depends on what one takes as the model, and your question raises both possibilities.

Suppose first that you want the probabilities that your scores specify, as a tracker does. Its sensor model may be imperfect, and it still determines how much weight each measurement gets in the update. Plain perturb-and-MAP estimates the probabilities of its own distribution instead, however many samples are drawn, and we prove how the two differ. With two tracks and two measurements there are two assignments. When one of them scores 1 more than the other, the model gives it probability 0.73 and perturb-and-MAP with standard Gumbel noise gives it 0.66 (Section 2.3). In general, for nn tracks and nn measurements with equal scores, the probabilities of perturb-and-MAP respond to a small change of the scores at n/(n+1)n/(n+1) times the rate of the model (Theorem 3). This factor depends on the number of targets, so one fixed recalibration of the scores does not absorb it. Scaling the noise by it for each nn matches the two rates at equal scores and leaves a difference elsewhere. On scenes with 16 to 30 closely spaced targets, the tight formations of Section 6, the pairing probabilities estimated from 10510^5 perturb-and-MAP samples have a mean error of about 0.03 to 0.08 on the ambiguous pairings even with this scaling, more than ten times the error of our reweighted estimator with as many samples (Table F.3). And by Theorem 1, once there are two or more tracks and three or more measurements, no choice of noise makes the samples follow the Gibbs distribution at every score vector. Our weights, built from the formula of Theorem 2, turn the same samples into estimates that converge to the probabilities of the model.

Suppose instead that one takes the distribution of the perturb-and-MAP samples itself as the model, as your question suggests and as Tarlow et al. (2012) and Berthet et al. (2020) do. No correction is then needed, and the sample frequencies estimate the probabilities that one has chosen. To fit the scores of such a model to data by maximum likelihood, however, one needs the probability that the sampler returns each observed assignment. For assignments under independent Gumbel noise this probability had not been computed before, and Theorem 2 gives the first explicit formula for it.

The distribution of the samples thus gives the weights in the first case and the likelihood in the second. The revised introduction now states where the Gibbs distribution comes from and why the difference from it persists.

We hope that the revised paper and these answers make clear which problem the paper solves and why it matters, and we would be glad to revise any passage that you still find hard to follow. Thank you again for the effort and expertise that you have devoted to our work in this review. Your comments on clarity and motivation have made the paper better.

Reviewer_smrVOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper is about the output law of perturb-and-MAP (P&M) with element-wise noise. Theoretical results comprise multiple theorems, that I'll try to summarize:

  • Theorem 1: about the structures that admit a noise law that is exactly Gibbs,
  • Theorem 2: gives an exact integral formula for the law of Gumbel matching,
  • Theorem 3: first-order temperatures in closed form,
  • Estimator: an importance-sampling estimator of marginals, using Gumbel matching as the proposal distribution and evaluated on data association for tracking.
Critical strengths
  • Theorem 1 rules out every noise law, not only i.i.d. noise.
  • The writing is clear and precise.
  • The experiments have exact ground truth and show that the Gibbs vs. P&M gap matters in practice.
Critical weaknesses

Weaknesses are labelled for future reference in the discussion period.

(W1) The contribution of Theorem 2 is not isolated. There is no ablation about frequency-only vs. law-only vs. hybrid weights in Figure 1(a). I struggle to see an empirical evidence for Theorem 2.

(W2) Wall-clock time. No wall-clock time is reported in the experiment.

(W3) The estimator is ad hoc. In particular, the frequency threshold of 20 feels arbitrary. Also, I think the alignment constant would cancel if law-based weights were used for all sampled assignments.

Questions for authors

Questions are labelled for future reference in the discussion period.

(Q1) Is δ0\delta_0 (Theorem 1) tight?

(Q2) For Theorem 1(b), what happens if n=2n = 2 rows with N≥3N \ge 3 columns?

4 comments
AuthorsOpenReview ↗

Response to Reviewer smrV (1/2)

Thank you for your careful review and for your kind words about the writing and the experiments. In response, we have added an ablation of the weights, running times and a comparison of frequency thresholds, and Theorem 1(b) now answers your question on two rows and three or more columns. We have also further improved the writing and the presentation of the paper. The other theorems are unchanged in content, and new and substantively changed text is marked in red in the revised paper.

(W1) Empirical evidence for Theorem 2. We have added the ablation that you ask for. The same draws of Gumbel matching are weighted in three ways, with frequencies alone, with estimates from the law alone, and with the rule of our estimator, which takes the frequency of an assignment that is drawn at least 20 times and the law-based estimate of every other assignment. The right panel of Figure 1(a) and Table E.2 report the three errors.

The contribution of Theorem 2 is isolated in the experiments on the new tight formations, in which the targets are closer together and the posterior is spread over many hypotheses. At n=28n=28 and 3030 no hypothesis reaches 20 draws, so every weight of our estimator comes from the law. At n=30n=30 the error is 0.082 without weights at the same temperature and 0.060 with weights from frequencies, and our estimator has an error of 0.0052. At n=28n=28 the three errors are 0.067, 0.046 and 0.0064. Using the law of Theorem 2 in place of frequencies thus cuts the error by a factor of about 12 at n=30n=30 and about 7 at n=28n=28. Weights from frequencies do poorly here because frequencies give little information on such scenes. Every assignment drawn once has frequency 1/T1/T whatever its probability, whereas the law gives each assignment an estimate of its own probability. On the random and crossing scenes, frequencies for every assignment give 4.6 to 43.3 times the error of our estimator (Table E.2).

On the formations of the submitted Figure 1(a), at n=8n=8 and 1212 with every target detected, the posterior is instead concentrated on hypotheses that are each drawn many times. Even here weights from the law alone give errors of 0.001 to 0.0074, where belief propagation and Sinkhorn scaling err by 0.05 to 0.34 (Section 6). Our estimator brings the error below 0.0001 by taking the frequencies of these frequent hypotheses, for the reason given under (W3) (Table E.2).

These comparisons test Theorem 2 through the error of the estimates. We also tested its formula directly. For every permutation of two random 3×33\times3 score matrices and one random 4×44\times4 score matrix, we evaluated the integral of the theorem by numerical cubature and compared it with the frequency of that permutation among 2⋅1072\cdot10^7 draws of Gumbel matching. Divided by the standard deviation of a frequency, the differences have a root mean square between 1.01 and 1.12 on the three matrices and are at most 2.23 in absolute value, which is what sampling fluctuation alone would give.

(W2) Wall-clock time. The new Table F.7 reports mean running times over three draws of each scene, for our estimator and for the baselines of Tables F.1, F.2, F.3 and F.6, and Appendix F.8 adds the times of our estimator on the other experiments and the hardware. Our estimator takes between 0.9 and 56 seconds on the scenes of Table F.1 with every target detected, between 14 and 201 seconds with missed detections and clutter, and between 7 and 129 seconds on the tight formations, that is, from a second to a few minutes a scene. Its chains, its annealing runs and its determinant evaluations run in batches on one GPU.

AuthorsOpenReview ↗

Response to Reviewer smrV (2/2)

(W3) The weighting rule and the alignment constant. The weighting rule rests on an identity. An assignment σ\sigma that is drawn mm times and estimated by its frequency m/Tm/T gives each of these draws the weight e⟨θ,Pσ⟩/(m/T)e^{\langle\theta,P_\sigma\rangle}/(m/T), so their weights add up to Te⟨θ,Pσ⟩Te^{\langle\theta,P_\sigma\rangle} whatever mm is. The frequent assignments therefore enter the estimate in the proportions of their Gibbs probabilities, as they would in an enumeration, and this is why our estimator takes their frequencies. An assignment drawn once or a few times has a frequency that gives little information about its probability, and the law-based estimate takes its place. Whether the threshold is 10, 20 or 50 matters little, since with 10 or 50 in place of 20 no error in Table E.2 changes by more than 0.0006. The ablation shows what each part contributes. With frequencies for every assignment the error is 4.6 to 43.3 times that of our estimator on the random and crossing scenes, and with law-based estimates for every assignment it is 24 to 195 times as large on the formations whose posterior is concentrated on frequent assignments. On the formations with missed detections and clutter our estimator is more accurate than either single rule, by a factor of 4.8 to 5.9 against frequencies alone and of 1.5 to 4.2 against the law alone (Section 5 and Table E.2).

The alignment constant does cancel when every weight is law-based. For square assignments the law-based estimates are known up to one constant common to all assignments, and a common factor of the weights cancels from the self-normalized estimate, as Section 5.1 now states. The estimator needs the constant because it combines the two kinds of estimates and has to put them on one scale. With private columns the weights contain further normalizers. Assignments with the same set G\mathcal G of shared columns share one normalizer Ψ(G)\Psi(\mathcal G). These normalizers differ from set to set, so they do not cancel from the relative weights of assignments with different sets. Algorithm 2 therefore estimates the normalizer of every nonempty set that a sampled assignment uses by annealed importance sampling before it fits the alignment constant (Section 5.2).

(Q1) Is δ0\delta_0 tight? It is not tight. The value δ0≈0.0111\delta_0\approx0.0111 comes from an argument with three elements, and an argument with four elements gives a larger bound. For the 2-subsets of four elements it shows that under every noise law the distribution of the output is at total variation distance at least 0.0146 from the Gibbs distribution in the worst case over the scores. Forcing k−2k-2 elements in and n−k−2n-k-2 out extends this bound to the kk-subsets with 2≤k≤n−22\le k\le n-2. For comparison, the best noise law that we have found for the 2-subsets of four elements draws the whole noise vector, with probability one half each, as i.i.d. standard Gumbel noise or as i.i.d. negative Gumbel noise, at a temperature of about 1.10. The largest distance that a numerical search over the scores finds for this noise law is about 0.0217, about one and a half times the bound.

(Q2) Two rows and N≥3N\ge3 columns. With two rows and three or more columns no noise law is exact. Theorem 1(b) now states that for assignments of nn rows to N≥nN\ge n columns an exact noise law exists if and only if n=1n=1 or n=N=2n=N=2. The proof reduces two rows to three rows. Sending the scores of all but three columns to −∞-\infty leaves two rows and three columns. A third row without noise then takes the column that the two rows leave unused, which turns the assignments into the permutations of three elements with the same noise sums. Give the two rows the scores of the first two rows of a three-row problem minus those of its third row, column by column. Every permutation then has the score of its two-row assignment plus one constant, the sum of the scores of the third row, so, with ties broken in the same way, the two problems have the same perturbed optimizer and the same Gibbs distribution. An exact noise law for two rows and three columns would therefore give one for three rows and three columns, which does not exist (Appendix B.5).

We hope that these answers address your points, and we are happy to discuss any of them further. Thank you again for the effort and expertise that you have devoted to our work in this review. The ablation that you asked for and the questions that you raised have made the paper stronger.

Reviewer_smrVOpenReview ↗

Ack of Rebuttal

Thank you for the detailed review. I already have a positive score, and I am waiting for the discussion with the other reviewers to unfold before updating it into my final assesment.

AuthorsOpenReview ↗

Reply to Reviewer smrV

Thank you for your positive assessment. In the last hours before the rebuttal period closes (November 18, AoE), we will carefully go through all reviews and comments. If any new question arises in your discussion with the other reviewers, we are glad to answer it.

Reviewer_rAvMOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper analyzes the perturb-and-MAP sampling scheme, providing three main new theorems and an importance sampling estimator of Gibbs marginals for bipartite matchings (assignments). The idea behind perturb-and-MAP is: you add some unary terms sampled from noise (typically, but not necessarily, Gumbel) to the variables of a probabilistic graphical model (PGM) and then compute or estimate the MAP of that perturbed graphical model. That MAP configuration becomes an approximate sample from the model. This approach doesn't sample from the Gibbs distribution, but approximates it.

This paper doesn't consider arbitrary graphical models, where exact MAP inference can be intractable. Instead it focuses on binary PGMs with feasible configurations restricted to be either matroids or bipartite matchings. MAP is tractable for both of these families. Different results are provided for each family:

  • Matroids:

    • Theorem 1 characterizes under which conditions it is possible to sample exactly from some matroids by using the right noise distribution, and how when those conditions are violated, no noise distribution can result in exact sampling.
  • Bipartite matchings (assignments):

    • Theorem 1 says, roughly, that for n≥3n\ge3 rows there's no noise distribution (even dependent) for which the perturb-and-MAP approach produces exact samples from a bipartite matching.

    • Theorem 2, the main contribution, produces a characterization of the probability distribution over square matchings when Gumbel noise and perturb-and-MAP is used to sample assignments that allows it to be approximately computed. This means that for a given assignment xx, which is sampled using perturb-and-MAP (a Gumbel matching), with true distribution Qθ(x)Q_\theta(x), it is possible to approximately evaluate Qθ(x)Q_\theta(x) for each sample.

    • Being able to evaluate the PMF (even if approximately) immediately unlocks importance sampling, which now allows us to weight samples and estimate marginals of the undistorted Gibbs distribution. This is evaluated in multi-target tracking scenarios.

Critical strengths
  • Theorem 2 is, as far as I can tell, a novel theoretical result characterizing the distribution of Gumbel matchings, which allows approximate evaluation of its probability mass function.

  • Theorem 1 rigorously provides precise conditions under which it is possible and impossible to find a noise distribution such that, when added as a collection of unary terms to a matroid or a bipartite matching, results in sampling from the Gibbs distribution. This was heavily suspected and somewhat folklore knowledge, but it hadn't been rigorously proved, as far as I know.

Critical weaknesses

Despite the nice and elegant theoretical results, the usefulness of these ideas to create practical sampling algorithms is not demonstrated.

  1. For general matroids, Theorem 1 is a negative result with limited practical impact for sampling. Fast sampling algorithms already exist. They are not exact in the general case, but they are accurate and fast mixing MCMC using a bases-exchange walk already exists. So sampling in matroids is already well solved, and existing samplers are not limited by the structural needs mentioned in Theorem 1. In fact, for the specific matroid models discussed in the paper, exact sampling is possible without invoking perturb and MAP.

  2. For bipartite matchings is where things get interesting, and a new importance sampling method is developed, based on Theorem 2 to estimate the PMF of a sample. However, here the weakness is the empirical aspect, which doesn't help to decide whether this method is truly a SOTA method for this task or not.

  • On the formation scenes, BP is known to collapse to the most probable hypothesis. Also, that problem is known to have an approximate (but likely very accurate here) solution through hypothesis enumeration (Murty, 1968; Rezatofighi et al., 2016), which is not included as a baseline.
  • Stronger baselines aren't included: ADAPART, MCMC data association.
  • Other, more general problems are not tested.
  • The proposed method is pretty heavy requiring a large number of determinant evaluations for each importance evaluation, and it runs on GPU when BP is run on CPU.
  • No wall-clock, throughput or FLOP figure
  • Overall, to know if this method is competitive, it is necessary to assess performance at matched wall-clock compute for strong baselines (methods that tracking practitioners use), and problem generality. This doesn't happen in the paper.
Questions for authors
  1. Can you report wall-clock for all experiments and runs?
  2. Can you add the baselines I mentioned above to the experimental results?
  3. In the rectangular scenes, can you report the gap between the forward and reverse AIS estimates of log⁡Ψ(G)\log\Psi(\mathcal G)?
  4. About the classification gap, Theorem 1 talks about n≥3n\ge3 rows and N≥nN\ge n and Appendix B.3 talks about 2×22\times 2 being exact: Is 2×N2\times N with N≥3N\ge3 columns exact or not?

Related work that can help to frame Theorem 1 and the estimator (only the first one is cited in the paper, and not to make this point):

  • Gane, Hazan & Jaakkola, Learning with Maximum A-Posteriori Perturbation Models (2014): proves that score-dependent low-dimensional perturbations are exact on tree-shaped MRFs.
  • Hazan, Maji & Jaakkola, On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations (2013) and Kim, Sabharwal & Ermon, Exact Sampling with Integer Linear Programs and Random Perturbations (AAAI 2016): can produce exact Gibbs samples with perturb-and-MAP using sequential mechanisms or integer programming.
  • Balog et al., Lost Relatives of the Gumbel Trick (ICML 2017): studies non-Gumbel noise families for sampling.
  • Cohen Indelman & Hazan, On The Statistical Representation Properties Of The Perturb-Softmax And The Perturb-Argmax Probability Distributions, (2024): analysis of representation properties of perturb-argmax families.
3 comments
AuthorsOpenReview ↗

Response to Reviewer rAvM (1/3)

Thank you for your careful and thorough review, for your positive assessment of Theorems 1 and 2, and for the precise requests on the experiments. In response, we have added the baselines that you name, running times and the annealing gaps. Theorem 1(b) now answers your question on two rows and three or more columns, and the paper discusses the five references that you suggest. We have also rewritten the abstract and the introduction and revised the exposition of the main text to make it easier to follow. The other theorems are unchanged in content, and new and substantively changed text is marked in red in the revised paper.

Theorem 1 and sampling on matroids. You are right that sampling from these distributions does not need perturb-and-MAP. Exact samplers exist for the kk-subsets and the spanning trees, and the bases-exchange walk mixes fast on general matroids. Perturb-and-MAP is widely used all the same. In machine learning it draws subsets, permutations and other structures as latent variables (Kool et al., 2019; Mena et al., 2018; Niepert et al., 2021), and its draws stand in for draws from the Gibbs distribution. Theorem 1 speaks to this practice. It decides whether a better choice of noise can make the draws exact, a question that, as you write, had not been rigorously settled. For the kk-subsets, Niepert et al. (2021) construct a noise whose sum over every kk-subset is Gumbel and note that they still cannot sample faithfully. Theorem 1 shows that for 2≤k≤n−22\le k\le n-2 no noise can, even with dependent entries, and it bounds the error from below. Under every noise law the distribution of the output is at total variation distance at least δ0\delta_0 from the Gibbs distribution in the worst case over the scores. On matroid bases in general, a noise law that is exact at every score vector exists only when the structure is a product of single choices, each of one element to take or one to leave out.

What can still be chosen is the temperature. For Gumbel top-kk, Theorem 3 gives in closed form the temperature at which the method agrees with the Gibbs distribution to first order near equal scores, (n/k)(Hn−Hn−k)(n/k)(H_n-H_{n-k}). Running at this temperature uses the same optimization, and on random scores it lowers the largest error of a marginal, averaged over the score vectors, by a factor between 1.5 and 20 compared with temperature one (the new Table D.1). Together the two theorems tell a user of perturb-and-MAP on such subsets that no design of the noise makes the draws exact, that the error is at least δ0\delta_0 in the worst case, and which temperature reduces it without further computation.

Related work. The revised paper discusses the five references that you suggest. Theorem 1 concerns one optimization with noise on the elements, under a noise law that does not depend on the scores, and each of the exact samplers that you list obtains exactness by giving up one of these three. Hazan et al. (2013) and Balog et al. (2017) replace the one optimization by a sequence of optimizations with a rejection step. Kim et al. (2016) put Gumbel noise on whole configurations instead of elements, inside an integer program that is solved to completion. Gane et al. (2014) let the perturbations depend on the scores and build them from the conditional distributions of a tree-structured model. Outside the cases in which Theorem 1 gives an exact noise law, exactness therefore requires such a departure. The paragraph on related work at the end of the introduction now states this relation, and Appendix A discusses these works together with the other noise families of Balog et al. (2017) and the result of Cohen Indelman and Hazan (2024) on a single choice among categories.

Two rows and N≥3N\ge3 columns. With two rows and three or more columns no noise law is exact. Theorem 1(b) now states that for assignments of nn rows to N≥nN\ge n columns an exact noise law exists if and only if n=1n=1 or n=N=2n=N=2. The proof reduces two rows to three rows. Sending the scores of all but three columns to −∞-\infty leaves two rows and three columns. A third row without noise then takes the column that the two rows leave unused, which turns the assignments into the permutations of three elements with the same noise sums. Give the two rows the scores of the first two rows of a three-row problem minus those of its third row, column by column. Every permutation then has the score of its two-row assignment plus one constant, the sum of the scores of the third row, so, with ties broken in the same way, the two problems have the same perturbed optimizer and the same Gibbs distribution. An exact noise law for two rows and three columns would therefore give one for three rows and three columns, which does not exist (Appendix B.5).

AuthorsOpenReview ↗

Response to Reviewer rAvM (2/3)

Experiments and baselines. Our estimator is an application of the law, and the experiments show that the law can be computed and what it contributes. On the new tight formations at n=30n=30, for example, 10510^5 draws of Gumbel matching give a mean absolute error of 0.082 without weights and 0.060 with weights from their frequencies, and our estimator, which weights the same draws by the law, has an error of 0.0052. With the baselines that you ask for, the revised Section 6 also shows where our estimator has its advantage, on scenes whose posterior is spread over many hypotheses.

On the formations of the submitted figure, with every target detected, belief propagation does collapse. At every lag below 1/21/2 its beliefs agree with the indicator of the most probable hypothesis to machine precision, by the mechanism of Vontobel (2013) that the paper cites. The enumeration is accurate on these scenes, as you expected, because their posterior is concentrated on hypotheses that Murty's ranking reaches (Appendix F.3). It falls behind where the posterior is spread out. Table F.2 adds the enumeration to all the scenes of Table F.1, and on the random and crossing scenes our estimator is more accurate than the list of 10510^5 hypotheses in every row. At n=15n=15 and 2020 the list errs there by 0.022 to 0.106 and our estimator by at most 0.0045.

The new tight formations are formations with every target detected whose predicted measurements are only 1.2 standard deviations of the likelihood apart. Their posterior is spread so widely that the 10510^5 most probable hypotheses, which have 0.99 of its mass at n=16n=16, have 0.44 at n=30n=30. The error of the enumeration is the mass that its list omits times the mean absolute difference between the marginals on and off the list, and it rises steadily from n=16n=16 to n=30n=30. Our estimator draws independent assignments from Gumbel matching and corrects them with importance weights built from the law. Its only Markov chains sample the column potentials from a log-concave density, so no chain has to move between the modes of the posterior. At budgets of 10510^5 our estimator is more accurate than every other approximate method at n=20n=20, 24, 28 and 30 (left panel of Figure 1(a)). From n=24n=24 on it is also more accurate than the enumeration, sequential importance sampling and the Markov chain at their largest budgets, which are 10, 3000 and 1000 times its own. At n=30n=30 its mean absolute error is 0.0052, and the errors of the three remain 3 to 14 times as large although their budgets are larger by one to more than three orders of magnitude (Table F.3). At these sizes even the larger budgets therefore do not bring the three methods to the accuracy of our estimator.

The Markov chain uses the moves of Oh et al. (2009) together with exchanges of the columns of two rows, which the scenes with every target detected need. On the tight formations it does not mix within its budgets. From n=20n=20 on, a thousand times as many sweeps change its error by less than one percent.

ADAPART draws exact samples, so the sampling error of the tables stands for its error after TT samples, and what limits it is the rate at which it draws them. We ran a Python 3 translation of its authors' sampler. On the tight formations its rate falls from about 400 samples a second at n=16n=16 to about 13 at n=30n=30. With missed detections and clutter, where it runs on a square matrix with added rows of ones, the rate falls quickly as nn grows, and on the random and crossing scenes at n=20n=20 no run completed more than five samples in 300 seconds (Appendix F.4). At that rate the 10510^5 samples of the tables would take more than two months, so exact sampling by ADAPART is not practical on such scenes.

AuthorsOpenReview ↗

Response to Reviewer rAvM (3/3)

More general problems. Our estimator is built for assignments. For assignments of rows to distinct columns no noise law is exact beyond the smallest cases (Theorem 1(b)), and the law of Gumbel matching can be computed, by Theorem 2 for square assignments and by Theorem C.1 for the assignments of data association, in which every track has a private column for a missed detection. The experiments cover three families of scenes, formations, random scenes and crossing scenes, each with every target detected and with missed detections and clutter, and the formations reach n=60n=60 and n=40n=40 in the two regimes. On the 18 rows of Table F.1 the error of our estimator is at most 0.0025 with every target detected and at most 0.0045 with missed detections and clutter, and it is more accurate than Sinkhorn scaling, sequential importance sampling and both unweighted estimators in every row. For the kk-subsets the paper gives the temperature of Theorem 3, which Table D.1 tests. The tree structure behind Theorem 2 is special to bipartite graphs. On the perfect matchings of the complete graph the law is an integral against a density that is #P-hard to evaluate (Proposition C.3).

Computation and running time. Our estimator is heavier than belief propagation and Sinkhorn scaling. Those two are deterministic approximations, and on the tight formations they err by 0.03 to 0.10, where our estimator errs by 0.001 to 0.0064 (Table F.3). With every target detected it evaluates one determinant of order nn for every distinct assignment among its draws and every sample of the column potentials, about 2⋅1082\cdot10^8 determinants of order 16 on a tight formation at n=16n=16. With missed detections and clutter, every nonempty set of shared columns that a sampled assignment uses also takes one annealing run in each direction. The chains advance in parallel, as do the annealing runs, and the determinants are evaluated in batches, so the work parallelizes directly and we run it on a GPU. On the sixteen cores of the CPU alone, independent runs of the same code take between 1.3 and 15.4 times as long on one draw of each scene of Tables F.1 and F.3. The baselines do not call for a GPU. Murty's ranking, a Markov chain and the rejection steps of ADAPART proceed sequentially, and belief propagation, Sinkhorn scaling and sequential importance sampling already finish within two seconds a scene on average on a single CPU core at the budgets of Tables F.1 and F.6 (Appendix F.8).

The new Table F.7 reports mean running times over three draws of each scene, for our estimator and for the baselines on the rows of Tables F.1, F.2, F.3 and F.6. Our estimator takes between 0.9 and 201 seconds on the scenes of Table F.1 and between 7 and 129 seconds on the tight formations, that is, from a second to a few minutes a scene. At the budgets of the tables the baselines take from less than a hundredth of a second to 18 seconds, and at their largest budgets on the tight formations between 70 and 583 seconds. Appendix F.8 adds the times of our estimator on the other experiments, Appendix F.4 gives the sampling rates of ADAPART, and the supplementary code records the time of every run.

Annealing gaps. For every nonempty shared-column set G\mathcal G of a sampled assignment, Algorithm 2 estimates log⁡Ψ(G)\log\Psi(\mathcal G) by annealed importance sampling in both directions and uses the midpoint of the two estimates. Appendix E.2 now reports the gap between them over the 102 runs of Algorithm 2 in Appendix F. On a typical set the two directions agree closely. The median gap of a run, taken over its shared-column sets, has median 0.019 over the runs and is at most 0.072. A gap of 0.019 is a difference of about two percent between the two estimates of Ψ(G)\Psi(\mathcal G). The largest gap of a run has median 0.16 and is at most 3.1.

We hope that the new experiments and these answers address your concerns, and we are happy to discuss any of them further. Thank you again for the effort and expertise that you have devoted to our work in this review. The baselines that you named and the questions that you raised have made the paper stronger.

Reviewer_zxH2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Sampling combinatorial structures (like subsets of a ground set, spanning trees from a graph) from a Gibbs distribution is computationally hard. Instead, an approximate way of doing this in practice is to use the "Perturb-and-MAP" trick, which itself is a generalization of the Gumbel-max trick for categorical variables. Ideally, if we want the sampling distribution from "Perturb-and-MAP" to match exactly with the required Gibbs distribution, we would need to add a corresponding independent Gumbel variable to every structure. But the problem with this approach is that it would require an exponential number of Gumbel variables (for example, there are 2n2^n subsets for any ground set of size nn). Instead, what is apparently popular in practice is to just add an independent Gumbel variable to the score for every element and then optimize to find the structure with the highest cumulative score. This paper explores various settings, covering when these two distributions are equal and also what exactly does Perturb-and-MAP sample when they are not.

Critical strengths

Covers a wide variety of settings. Thorough paper.

Critical weaknesses

None

Questions for authors

The paper felt pretty dense to read. The related works section is pretty exhaustive in the main paper but perhaps some of it could be moved to the appendix and the extra space could be used to improve readability by making the overall paper gentler for non-experts.

1 comment
AuthorsOpenReview ↗

Response to Reviewer zxH2

Thank you for your careful review and for your suggestion on how to make the paper easier to read. We have followed it. The discussion of related work has moved to Appendix A, and the introduction now closes with a short paragraph on related work. With the space gained, we have substantially rewritten the abstract and the introduction to make the paper easier to follow, and we have added a pen-and-paper example to the main text. Apart from one new case of Theorem 1(b), the theorems are unchanged in content, and new and substantively changed text is marked in red in the revised paper.

A gentler introduction. The introduction now starts from a need shared by many problems in tracking and in machine learning. These problems require sampling from a probability distribution over combinatorial structures, such as subsets, spanning trees or assignments, or computing its marginals. A sonar that follows several nearby targets through clutter, for example, cannot tell which measurement came from which target. The most likely pairing of targets and measurements is easy to compute, but a tracker that commits to it may update a track with the wrong measurement, so probabilistic data association weights every measurement by the probability that it belongs to the track. Such probabilities are those of a Gibbs distribution, and they are hard to compute although the best structure is easy to find. Perturb-and-MAP samples by optimizing instead, but its samples do not follow the Gibbs distribution in general. This difference raises the three questions of the paper, and the introduction states them together with their answers. Along the way it explains the Gumbel-max trick, and it defines terms such as the law of the perturbed optimizer and an exact noise law where it first uses them.

A pen-and-paper example. The new Section 2.3 works out the assignment problem with two rows and two columns. There are only two assignments, so everything depends on one number, the difference of their scores. When one assignment has a score larger by one, the Gibbs distribution gives it probability 0.73, and perturb-and-MAP with standard Gumbel noise returns it with probability 0.66. The same example shows what a temperature corrects. Scaling the noise by 2/32/3, the temperature that Theorem 3 gives for two rows and two columns, makes the two distributions agree to first order near equal scores. A different noise, standard Gumbel noise on the first row alone, removes the difference altogether, whereas with a third column no noise does (Theorem 1).

We hope that the paper is now easier to read, for non-experts in particular, and we would be glad to revise any passage that still feels dense or unclear. Thank you again for the effort and expertise that you have devoted to our work in this review. Your suggestion has made it a better paper.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Revision

We thank the reviewers for their careful reading and their questions. We have uploaded a revised paper, with new and substantively changed text marked in red, together with the code for the algorithms and the experiments as supplementary material. At the request of several reviewers, we have rewritten the abstract and the introduction to make the paper easier to follow, and we have added the baselines, the ablation and the running times that were asked for. Apart from one new case of Theorem 1(b), the theorems are unchanged in content.

Presentation (Reviewers qoMi, zxH2 and rAvM). The abstract and the introduction now start from the need for probabilities over combinatorial structures. The introduction explains what the Gibbs distribution over such structures is, says where it arises in machine learning and in survey sampling, and illustrates the need with the tracking of several targets through clutter. It then explains why these probabilities are hard to compute although the best structure is easy to find. Next it describes how perturb-and-MAP samples by optimizing and notes that its samples do not follow the Gibbs distribution in general. After this it states the three questions of the paper and their answers, and it explains its central terms where it first uses them. The new Section 2.3 works out the assignment problem with two rows and two columns by hand. It shows how far the samples of perturb-and-MAP are from the Gibbs distribution in this case and how a temperature removes the difference to first order. Following the suggestion of Reviewer zxH2, the discussion of related work has moved to Appendix A, and the introduction closes with a short paragraph on related work.

Classification (Reviewers rAvM and smrV). A noise law is exact if perturb-and-MAP with this noise samples the Gibbs distribution at every score vector. At the request of Reviewers rAvM and smrV, Appendix B.5 now proves that no noise law is exact for assignments with two rows and three or more columns. With this case added, Theorem 1(b) states that for assignments of nn rows to N≥nN\ge n columns an exact noise law exists if and only if n=1n=1 or n=N=2n=N=2.

Experiments (Reviewers rAvM and smrV). Section 6 and Appendix F report a new set of experiments. We have added three baselines, the enumeration of the most probable hypotheses by Murty's ranking, a Markov chain over the hypotheses and the exact sampler ADAPART. We have also added tight formations with up to 30 targets, in which the targets are closer together and the posterior is spread over many hypotheses. From 24 targets on, our reweighted estimator gives more accurate marginals on these scenes than the enumeration, sequential importance sampling and the Markov chain, even at their largest budgets. Figure 1(a) and Table E.2 compare the estimator with two variants that weight the same samples by their frequencies alone and by their law alone, and Table E.2 also varies the frequency threshold. Appendix F.4 gives the sampling rates of ADAPART, Table F.7 the running times of the estimator and of the other baselines, and Appendix E.2 the gap between the forward and the reverse annealing estimates. The new Table D.1 compares the errors of the marginals of Gumbel top-kk at temperature one and at the first-order temperature of Theorem 3.

Related work (Reviewer rAvM). The paper now discusses the five references that Reviewer rAvM suggested. The paragraph on related work in the introduction states how Theorem 1 relates to the exact samplers that are built on perturbations, and Appendix A discusses all five references with the rest of the related work.

The remaining changes keep the rest of the paper consistent with these revisions or adjust wording to improve clarity.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.