Three Noises for the Argmax
7 min read
Suppose a recommendation system gives two options scores of 5 and 4. Always choosing the higher score leaves the second option no chance to be tried. Adding independent noise to both scores gives it a chance, while still favoring the first. But how much of a chance depends on the distribution of the noise.
With Gumbel noise, the probabilities become a softmax of the scores. Exponential noise and Laplace noise produce different probabilities, even at the same scale. We can understand all three by fixing one candidate’s noise and asking what its rivals must do for it to win.
Fix One Draw, Then Average
Let \(s_1,\ldots,s_n\) be fixed scores and let \(Z_1,\ldots,Z_n\) be independent draws from the same continuous noise distribution. We return the index with the largest perturbed score:
\[ \arg\max_i\{s_i+Z_i\}. \]
Write \(F(t)=\Pr(Z_i\le t)\) for the noise’s cumulative distribution function and \(f(t)\) for its density. If candidate \(i\) draws noise \(t\), it wins precisely when every rival \(j\) draws less than \(t+s_i-s_j\). Independence turns those requirements into a product:
\[\begin{align*} \Pr(i\text{ wins}\mid Z_i=t) &=\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*}\]
Averaging over \(i\)’s own draw gives the common calculation:
\[ \boxed{\Pr(i\text{ wins})= \int_{-\infty}^{\infty}f(t)\prod_{j\ne i}F(t+s_i-s_j)\,dt.} \]
Here \(f(t)\) weights the possible draws for candidate \(i\), and each cumulative-distribution factor is the chance of beating one rival. Ties have probability zero because the noises are independent and continuous.
Only score differences appear. Our scores 5 and 4 therefore behave exactly like 1 and 0. More generally, take two scores \(g\) and 0, where \(g\ge0\) is the gap. The lower-scoring option wins with probability:
\[ \Pr(Z_2-Z_1>g)=\int_{-\infty}^{\infty}f(t)F(t-g)\,dt. \]
The explorer evaluates this integral for each noise family. Increasing the gap makes the lower option less likely to win. For unequal scores, increasing the common noise scale \(b>0\) makes it more likely. All three use the same \(g\) and \(b\), so differences in the probabilities come from the noise distribution.
Doubling both the gap and the noise scale preserves every probability. Indeed, dividing the perturbed scores by \(b\) leaves the winner unchanged:
\[ \arg\max_i\{s_i+Z_i\}=\arg\max_i\{s_i/b+Z_i/b\}. \]
The rescaled noise \(Z_i/b\) has the unit-scale distribution, so the relevant quantity is \(g/b\). Equal scale is not equal variance: Gumbel, exponential, and Laplace noise have different shapes. The three calculations below explain the explorer’s curves.
Gumbel Turns Shifts into Powers
Gumbel noise of scale \(b\) has cumulative distribution function:
\[ F(t)=\exp(-e^{-t/b}). \]
A shift of its input becomes a power of the original value:
\[\begin{align*} F(t+c) &=\exp(-e^{-t/b}e^{-c/b})\\ &=F(t)^{e^{-c/b}}. \end{align*}\]
Consequently, every rival in the winner integral contributes a power of the same number \(F(t)\). Substitute the shifted cumulative distributions, then change variables to \(u=F(t)\). Since \(du=f(t)\,dt\) and \(F\) runs from zero to one:
\[\begin{align*} \Pr(i\text{ wins}) &=\int_{-\infty}^{\infty}f(t) F(t)^{\sum_{j\ne i}e^{(s_j-s_i)/b}}\,dt\\ &=\int_0^1u^{\sum_{j\ne i}e^{(s_j-s_i)/b}}\,du\\ &=\frac{1}{1+\sum_{j\ne i}e^{(s_j-s_i)/b}}\\ &=\frac{e^{s_i/b}}{\sum_j e^{s_j/b}}. \end{align*}\]
The added one in the denominator is the missing \(j=i\) term. Multiplying numerator and denominator by \(e^{s_i/b}\) gives the softmax probabilities, the classical Gumbel choice model studied by Yellott [Yellott, ’77].
For the two scores \(g\) and 0, the lower option therefore wins with probability:
\[ \Pr(2\text{ wins})=\frac{1}{1+e^{g/b}}. \]
Exponential Noise Must Clear a Boundary
Exponential noise is nonnegative, with density and cumulative distribution function:
\[ f(t)=\frac1b e^{-t/b}\mathbf1[t\ge0], \qquad F(t)= \begin{cases} 0,&t<0,\\ 1-e^{-t/b},&t\ge0. \end{cases} \]
For scores \(g\) and 0, the leader’s noisy score is at least \(g\). The lower option’s noise must first clear that boundary. The common integral therefore starts at \(t=g\):
\[\begin{align*} \Pr(2\text{ wins}) &=\int_g^\infty\frac1b e^{-t/b} \left(1-e^{-(t-g)/b}\right)\,dt\\ &=e^{-g/b}-\frac12e^{-g/b}\\ &=\frac12e^{-g/b}. \end{align*}\]
Compared with Gumbel noise at the same scale, the ratio of lower-option probabilities is:
\[ \frac{\tfrac12e^{-g/b}}{1/(1+e^{g/b})} =\frac{1+e^{-g/b}}2. \]
At a tie the rules agree. For a large gap, exponential noise selects the lower score about half as often.
The boundary also explains an equivalence that holds for any number of candidates. Subtract the best score from every score, so the best score is zero, and collect the candidates whose noisy scores reach zero:
\[ S=\{i:s_i+Z_i\ge0\}. \]
Each candidate joins this set independently with probability \(e^{s_i/b}\). At least one best candidate joins with probability one, and the winner must be in \(S\) because every excluded candidate finishes below zero.
Conditional on joining, the amount by which a candidate exceeds zero has an exponential distribution again. For any \(x\ge0\):
\[ \Pr(s_i+Z_i>x\mid Z_i\ge-s_i) =\frac{e^{-(x-s_i)/b}}{e^{s_i/b}} =e^{-x/b}. \]
This is memorylessness: after clearing its own threshold, every included candidate has the same fresh noise distribution. Conditional on \(S\), these excesses remain independent, so their maximum is equally likely to belong to any member of \(S\).
We can produce the same winner without drawing noisy scores: independently mark candidate \(i\) with probability \(e^{s_i/b}\), shuffle the candidates, and return the first marked one. The marked set has the same distribution as \(S\), and a uniform shuffle selects each of its members with equal probability. This is permute-and-flip, introduced by McKenna and Sheldon [MS, NeurIPS ’20]; its equivalence to exponential noisy argmax was proved by Ding and colleagues [DK+, ’21].
Laplace Can Also Lower the Leader
Laplace noise has an exponential tail on each side of zero:
\[ f(t)=\frac{1}{2b}e^{-|t|/b}, \qquad F(t)= \begin{cases} \tfrac12 e^{t/b},&t<0,\\ 1-\tfrac12e^{-t/b},&t\ge0. \end{cases} \]
The lower option can win through a positive noise draw of its own, a negative draw for the leader, or both. There is no longer a hard requirement that its noise clear \(g\). In the same integral \(\int f(t)F(t-g)\,dt\), the formulas change at \(t=0\) and \(t=g\). Splitting at those two points gives:
\[ \Pr(2\text{ wins}) =\left(\frac18+\frac{g}{4b}+\frac38\right)e^{-g/b} =\frac14\left(\frac gb+2\right)e^{-g/b}. \]
Evaluating the three parts of the Laplace integral
For \(t<0\), both cumulative-distribution and density factors use their left-hand branches:
\[ \int_{-\infty}^0\frac{e^{t/b}}{2b}\frac{e^{(t-g)/b}}2\,dt =\frac{e^{-g/b}}{4b}\int_{-\infty}^0 e^{2t/b}\,dt =\frac18e^{-g/b}. \]
For \(0\le t\le g\), the two exponential factors cancel their dependence on \(t\):
\[ \int_0^g\frac{e^{-t/b}}{2b}\frac{e^{(t-g)/b}}2\,dt =\int_0^g\frac{e^{-g/b}}{4b}\,dt =\frac{g}{4b}e^{-g/b}. \]
For \(t\ge g\), both use their right-hand branches:
\[\begin{align*} \int_g^\infty\frac{e^{-t/b}}{2b} \left(1-\frac12e^{-(t-g)/b}\right)\,dt &=\frac12e^{-g/b}-\frac18e^{-g/b}\\ &=\frac38e^{-g/b}. \end{align*}\]
Adding the three regions produces the displayed probability, including when \(g=0\) and the middle region has zero length.
The middle region explains the extra factor of \(g/b\). Throughout this entire interval, a smaller positive draw for the lower option and a negative draw for the leader can share the work of overcoming the gap. Their density factors multiply to the same value, so integrating contributes the interval’s length.
Choosing Privately
Noise is also useful when the scores depend on sensitive data. Suppose changing one person’s record changes each score by at most \(\Delta>0\). For all three noise families, the common scale
\[ b=\frac{2\Delta}{\varepsilon} \]
is sufficient for \(\varepsilon\)-differential privacy when we release only the winning index [DK+, ’21]. Here \(\varepsilon>0\) means that changing one person’s record can change the probability of any winning index by at most a factor \(e^\varepsilon\). Thus the same-scale comparison above is also a comparison at a common sufficient privacy guarantee. It does not assert that the scale is the smallest possible for every score function.
Gumbel gives the exponential mechanism, named for its weights \(e^{\varepsilon s_i/(2\Delta)}\). Exponential noise gives permute-and-flip. McKenna and Sheldon prove that permute-and-flip has no larger expected score loss than the exponential mechanism for any number of candidates [MS, NeurIPS ’20]. The distinction between their noise distributions therefore changes the quality of the selected option, even under the same privacy guarantee.