Three Noises for the Argmax
10 min read
Suppose we want to choose a high-scoring candidate while leaving some chance of choosing another. We can add independent noise to every score and take the largest result. The choice of noise determines how often a lower-scoring candidate wins, so changing the noise changes the selection rule.
Gumbel, exponential, and Laplace noise give three different rules, but we can understand all three with the same calculation. Fix one candidate’s noise, find the chance that it beats every rival, and average over the value we fixed. The differences come from how each noise distribution responds to the gaps between scores.
Write the \(n\) candidate scores as \(s_1,\ldots,s_n\) and their independent continuous noise draws as \(Z_1,\ldots,Z_n\). The selected candidate is:
\[ \arg\max_i\{s_i+Z_i\}. \]
The Common Calculation
How do we compute the chance that candidate \(i\) wins, for any noise at all? Let \(F\) be the cumulative distribution function and \(f\) the density of the noise. Fix candidate \(i\) and condition on its noise taking the value \(t\). It wins when every rival’s noisy score falls below \(s_i+t\):
\[\begin{align} \Pr(i\text{ wins}\mid Z_i=t) &=\Pr(s_j+Z_j<s_i+t\text{ for every }j\ne i) \\ &=\Pr(Z_j<t+s_i-s_j\text{ for every }j\ne i) \\ &=\prod_{j\ne i}F(t+s_i-s_j). \end{align}\]
The first line states the event that candidate \(i\) beats every rival. The second isolates each rival’s noise, and the third uses independence. Now average over candidate \(i\)’s own noise:
\[ \Pr(i\text{ wins}) = \int_{-\infty}^{\infty} f(t)\prod_{j\ne i}F(t+s_i-s_j)\,dt. \]
The density \(f(t)\) weights candidate \(i\)’s possible perturbations, and each factor in the product is the chance of clearing one rival. The scores enter only through pairwise gaps.
If the noise has scale \(b>0\), we can use unit-scale noise and divide every score by \(b\):
\[ \arg\max_i\{s_i+bZ_i\} = \arg\max_i\{s_i/b+Z_i\}. \]
Thus the meaningful quantity is a score gap divided by the noise scale. We will work at unit scale first and restore \(b\) when comparing the three distributions. The noise enters the integral only through \(F\) and \(f\), so each of the next three sections substitutes one distribution and simplifies the product: Gumbel collapses it to a softmax, exponential noise to permute-and-flip, and Laplace to neither.
The diagram compares the three noise distributions inside this common calculation:
Gumbel: Shifts Become Powers
What does the integral become when the noise is Gumbel? A standard Gumbel variable has cumulative distribution function and density:
\[ F(t)=e^{-e^{-t}}, \qquad f(t)=e^{-t}F(t). \]
In the plot, increasing the scale lowers the peak and stretches the longer right tail while the mode stays at zero.
Claim: with standard Gumbel noise, the winner follows the softmax distribution of the scores:
\[ \Pr(i\text{ wins}) = \frac{e^{s_i}}{\sum_j e^{s_j}}. \]
Proof
The relevant property of the Gumbel cumulative distribution function is that a shift of the input becomes a power. For any real number \(c\):
\[\begin{align} F(t+c) &=e^{-e^{-(t+c)}} \\ &=e^{-e^{-c}e^{-t}} \\ &=F(t)^{e^{-c}}. \end{align}\]
The first line substitutes the Gumbel formula, the second separates the shift from \(t\), and the third recognizes the original cumulative distribution function. For rival \(j\), set \(c=s_i-s_j\):
\[ F(t+s_i-s_j) = F(t)^{e^{s_j-s_i}}. \]
Every rival therefore contributes a power of the same number \(F(t)\). Substitute this identity into the common winner formula:
\[\begin{align} \Pr(i\text{ wins}) &=\int_{-\infty}^{\infty} e^{-t}F(t) \prod_{j\ne i}F(t)^{e^{s_j-s_i}}\,dt \\ &=\int_{-\infty}^{\infty} e^{-t}F(t)^{\sum_j e^{s_j-s_i}}\,dt \\ &=\int_{-\infty}^{\infty} e^{-t}\exp\!\left(-e^{-t}\sum_j e^{s_j-s_i}\right)\,dt \\ &=\int_0^\infty \exp\!\left(-u\sum_j e^{s_j-s_i}\right)\,du \\ &=\frac{1}{\sum_j e^{s_j-s_i}} \\ &=\frac{e^{s_i}}{\sum_j e^{s_j}}. \end{align}\]
The first line inserts the Gumbel density and the shifted cumulative distribution functions. The second combines their powers, including the factor \(F(t)\) as the missing \(j=i\) term. The third expands \(F(t)\), the fourth substitutes \(u=e^{-t}\), and the fifth integrates an exponential density. The last line multiplies numerator and denominator by \(e^{s_i}\).
At noise scale \(b\), the same calculation replaces every score by \(s_i/b\). Large \(b\) flattens the softmax, while small \(b\) concentrates it on the highest score.
There is another way to see the same identity. If \(Z_i\) is standard Gumbel, then \(e^{-Z_i}\) is a standard exponential variable, and maximizing \(s_i+Z_i\) is equivalent to minimizing \(e^{-Z_i}/e^{s_i}\). These are exponential clocks with rates \(e^{s_i}\), so clock \(i\) rings first with probability \(e^{s_i}/\sum_j e^{s_j}\).
Yellott [Yellott, JMP ’77] proved that this behavior characterizes Gumbel noise. With at least three candidates, an independent additive-noise model follows the softmax for every score vector only when the noise is Gumbel, up to location and scale.
Exponential: A Boundary and Memorylessness
What happens when the noise can only push a score up, never down? A standard exponential variable is nonnegative. Its cumulative distribution function and density are:
\[ F(t)= \begin{cases} 0,&t<0,\\ 1-e^{-t},&t\geq0, \end{cases} \qquad f(t)=e^{-t}\mathbf{1}[t\geq0]. \]
In the plot, the support boundary remains fixed at zero as the scale stretches the right tail.
The zero in the first branch changes the common integral. Candidate \(i\) has no chance to win unless its own noise reaches at least the gap between its score and the best score. Consequently, its winner probability is:
\[ \Pr(i\text{ wins}) = \int_{\max_j s_j-s_i}^{\infty} e^{-t}\prod_{j\ne i} \left(1-e^{-(t+s_i-s_j)}\right)\,dt. \]
The lower limit is the first value of \(t\) for which every cumulative distribution factor is nonzero. Unlike the Gumbel case, shifts do not turn the factors into powers of one shared function, so the product does not reduce to a softmax.
With two candidates we can evaluate the result directly. Suppose candidate 1 leads candidate 2 by \(g\geq0\). Candidate 2 wins when \(Z_2-Z_1>g\), so:
\[\begin{align} \Pr(\text{candidate 2 wins}) &=\int_0^\infty \Pr(Z_2>g+t)e^{-t}\,dt \\ &=\int_0^\infty e^{-(g+t)}e^{-t}\,dt \\ &=\frac12e^{-g}. \end{align}\]
The first line conditions on \(Z_1=t\), the second uses the exponential tail, and the third evaluates the integral. At the same unit scale, Gumbel noise gives the lower-scoring candidate probability \(1/(1+e^g)\). Their ratio is:
\[ \frac{\tfrac12e^{-g}}{1/(1+e^g)} = \frac{1+e^{-g}}{2}. \]
It equals one when the scores tie and approaches one half as the gap grows. This comparison concerns the probability of selecting the lower score in the two-candidate case.
Exponential noise also has the memoryless property. Conditional on exceeding a threshold, the amount by which it exceeds that threshold is a fresh exponential variable. That property identifies its noisy argmax with permute-and-flip, introduced by McKenna & Sheldon [MS, NeurIPS ’20].
Claim: Exponential noisy argmax with scale \(b\) has the same output distribution as permute-and-flip with coin probabilities \(e^{s_i/b}\) after shifting the best score to zero.
Proof
Subtract the best score from every score, so that \(\max_i s_i=0\). This shift does not change the argmax.
Let \(Z_i\) be the exponential noise of scale \(b\) added to candidate \(i\). Collect the candidates whose noisy scores cross zero:
\[ S=\{i:s_i+Z_i\geq0\}. \]
Candidate \(i\) enters \(S\) independently with probability:
\[\begin{align} \Pr(i\in S) &=\Pr(Z_i\geq-s_i) \\ &=e^{s_i/b}. \end{align}\]
The best candidate enters with probability one, so \(S\) is never empty. Conditional on \(i\in S\), memorylessness says that the excess \(s_i+Z_i\) is a fresh exponential variable of scale \(b\). The excesses are independent and identically distributed across \(S\), so their maximum is uniform over the candidates in \(S\).
Permute-and-flip independently marks candidate \(i\) with probability \(e^{s_i/b}\), visits the candidates in a uniform random order, and returns the first marked candidate. It creates the same random set \(S\). Conditional on \(S\), the first marked candidate in a uniform permutation is also uniform over \(S\). The two selectors agree conditional on every possible \(S\), so their output distributions agree.
Ding, Kifer, Saghaian, Steinke, Wang, Xiao & Zhang [DK+, ’21] proved this equivalence for any number of candidates.
The two-candidate calculation extends to a stronger comparison. If a selector returns candidate \(i\), define its regret as the score lost relative to the maximum:
\[ R=\max_j s_j-s_i. \]
McKenna & Sheldon’s Theorem 2 states that, at the same scale and for every threshold \(t\geq0\):
\[ \Pr(R^{\mathrm{exp}}\geq t) \leq \Pr(R^{\mathrm{Gum}}\geq t). \]
Here the superscripts denote exponential and Gumbel noise. This is the precise sense in which exponential noise does no worse: it is no more likely to lose at least \(t\) score units, for any \(t\). Integrating the tail probabilities also gives no larger expected regret.
Laplace: Two Exponential Tails
Does Laplace noise, which is exponential on each side of zero, behave like the exponential case? A standard Laplace variable is symmetric, with density:
\[ f(t)=\frac12e^{-|t|}. \]
In the plot, increasing the scale lowers the central peak and stretches both tails by the same amount.
Its right tail resembles the exponential distribution, but it can also be negative. This removes the exponential distribution’s hard boundary and its memoryless threshold construction. It also lacks Gumbel’s shift-to-power identity, so the common winner integral has no comparable collapse.
Again take two candidates separated by a gap \(g\geq0\). The lower score wins when the difference of two independent Laplace variables exceeds \(g\). For \(t\geq0\), the density of that difference is the convolution:
\[\begin{align} f_{Z_2-Z_1}(t) &=\frac14\int_{-\infty}^{\infty} e^{-|z|-|z+t|}\,dz \\ &=\frac14\left( \int_{-\infty}^{-t}e^{2z+t}\,dz +\int_{-t}^{0}e^{-t}\,dz +\int_0^\infty e^{-2z-t}\,dz \right) \\ &=\frac14\left( \frac12e^{-t}+te^{-t}+\frac12e^{-t} \right) \\ &=\frac14(t+1)e^{-t}. \end{align}\]
The second line splits the real line where the two absolute values change sign. The three pieces correspond to both noises being on the left, on opposite sides, and both being on the right. Integrating this density above the score gap gives the lower candidate’s chance of winning:
\[\begin{align} \Pr(\text{candidate 2 wins}) &=\int_g^\infty\frac14(t+1)e^{-t}\,dt \\ &=\frac14(g+2)e^{-g}. \end{align}\]
The extra factor \(g+2\) comes from Laplace’s two-sided support. An exponential variable can clear the score gap only by giving the lower candidate a large positive draw. With Laplace noise, a large positive draw for the lower candidate and a negative draw for the leader can share that work.
Restoring a common scale \(b\), the exact two-candidate probabilities are:
| Noise | Probability that the candidate lower by \(g\) wins |
|---|---|
| Gumbel | \(1/(1+e^{g/b})\) |
| Exponential | \(\tfrac12e^{-g/b}\) |
| Laplace | \(\tfrac14(g/b+2)e^{-g/b}\) |
The plot shows these three formulas over the same normalized score gap. Equal scale does not make the winner distributions interchangeable.
A Short Privacy Connection
What does any of this have to do with differential privacy? These probability identities also give three mechanisms for differentially private selection. Let one person’s data change each score by at most \(\Delta\), and let \(\varepsilon>0\) be the privacy budget.
Gumbel noise of scale \(2\Delta/\varepsilon\) gives the exponential mechanism of McSherry & Talwar [MT, FOCS ’07], because the softmax weights become \(e^{\varepsilon s_i/(2\Delta)}\). Exponential noise at the same scale gives permute-and-flip. Both selectors are \(\varepsilon\)-differentially private for arbitrary sensitivity-\(\Delta\) scores.
Laplace noise of scale \(2\Delta/\varepsilon\) gives the usual report-noisy-max guarantee for arbitrary scores. For monotone scores such as counts, adding one record moves every score in \([0,\Delta]\) rather than in \([-\Delta,\Delta]\). Dwork & Roth’s Claim 3.9 [DR, ’14] then reduces the sufficient Laplace scale to \(\Delta/\varepsilon\).
“Half the noise” means half the scale parameter, and only under the monotonicity assumption. The distributions have different shapes, so the statement does not imply half the variance or half the expected regret.
What Each Distribution Contributes
What carries over to a noise distribution that is not on this page? The winner-probability integral gives a direct way to analyze any additive-noise selector: condition on one perturbation, multiply one cumulative distribution factor per rival, and integrate. Special noise distributions become useful when a feature of their cumulative distribution simplifies that expression.
For Gumbel, shifts become powers and produce the softmax. For exponential noise, the support boundary and memorylessness produce permute-and-flip. For Laplace, two exponential tails produce the factor \((g/b+2)\) even with only two candidates.
When two noisy-argmax methods are compared, the comparison needs two labels: the common noise scale and the statistic of the selected score. Without both, phrases such as “less noise” or “better selection” do not specify a mathematical claim.