Private Selection by Noisy Argmax
12 min read
Picking the best of several candidates by a score built from private data is a standing problem: publish the winner, keep whatever went into each score hidden. The standard tool is the exponential mechanism of McSherry & Talwar [MT, FOCS ’07]: return candidate \(i\) with probability proportional to \(e^{s_i}\), where \(s_i\) is candidate \(i\)’s score. Sampled as written, that needs every weight \(e^{s_i}\) formed, summed, and divided before a single draw.
There is a way to draw from it that never forms that sum. Add independent Gumbel noise to every score and report whichever is largest: the winner is an exact draw from the exponential mechanism, computed as one pass over \(n\) perturbed scores, no normalizer in sight.
I met this argmax twice before noticing it was one algorithm: as the Gumbel-max trick in the language-model watermarking literature, and as the exponential mechanism, thanks to Lucas Rosenblatt, who works on differential privacy. Gumbel is not the only noise that fits the same two lines. Swap it for an exponential and the winner comes from a selector that never does worse than the exponential mechanism. Swap it for a Laplace and the winner comes from the classical report-noisy-max, which gets away with half the noise of either.
Which Candidate Wins
Give each of \(n\) candidates a score \(s_i \in \mathbb{R}\), draw independent noise \(Z_1, \dots, Z_n\) from a distribution with CDF \(F\) and density \(F'\), and return \(\arg\max_j (s_j + Z_j)\). Before picking an \(F\), leave it arbitrary: what is the chance candidate \(i\) wins?
Condition on candidate \(i\)’s own noise, \(Z_i = t\). Then candidate \(i\) wins exactly when every rival lands below it, \(s_j + Z_j < s_i + t\) for all \(j \ne i\). Rearranged, that is \(Z_j < t + s_i - s_j\), which rival \(j\) obeys with probability \(F(t + s_i - s_j)\). The rivals are independent, so we can multiply their chances and average over candidate \(i\)’s own noise:
\[ \Pr\big(\arg\max_j (s_j + Z_j) = i\big) = \int_{-\infty}^{\infty} F'(t) \prod_{j \ne i} F(t + s_i - s_j)\, dt. \]
The scores enter only through the gaps \(s_i - s_j\), and \(F\) is the only other ingredient. So \(F\) alone fixes how the winner is distributed, and three choices are worth working out.
Gumbel Noise Gives the Softmax
That integral has no closed form for a general \(F\). Take the noise to be a standard Gumbel. Its CDF is a double exponential, and its density is that CDF scaled by \(e^{-t}\):
\[ F(t) = e^{-e^{-t}}, \qquad F'(t) = e^{-t}\, F(t). \]
The property we need is that shifting the argument raises the whole CDF to a power, for any real \(c\):
\[ F(t - c) = e^{-e^{-(t - c)}} = e^{-e^{c} e^{-t}} = F(t)^{e^{c}}. \]
Each rival factor is therefore a power of \(F(t)\):
\[ F(t + s_i - s_j) = F(t)^{e^{s_j - s_i}}, \]
so the product over rivals collapses to a single power. The leftover \(F(t)\) sitting inside \(F'(t)\) supplies the missing \(j = i\) term, since \(e^{s_i - s_i} = 1\), and the exponent becomes a sum over all candidates:
\[\begin{align} \Pr\big(\arg\max_j (s_j + Z_j) = i\big) &= \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\Big(-e^{-t} {\textstyle\sum_j} e^{s_j - s_i}\Big)\, dt \\ &= \int_0^{\infty} \exp\Big(-u {\textstyle\sum_j} e^{s_j - s_i}\Big)\, du \\ &= \frac{1}{\sum_j e^{s_j - s_i}} \\ &= \frac{e^{s_i}}{\sum_j e^{s_j}}, \end{align}\]
where the third line rewrites \(F(t)^a = e^{-a e^{-t}}\) for any exponent \(a\), the fourth substitutes \(u = e^{-t}\), the fifth integrates \(\int_0^\infty e^{-au} du = 1/a\), and the last multiplies top and bottom by \(e^{s_i}\). The winner is an exact draw from the softmax of the scores. Nothing in the algorithm ever formed the sum in that denominator: it added \(n\) noise values and took a maximum.
The derivation leaned on exactly one property of \(F\): a shift becomes a power. That property alone pins the noise down. Suppose some \(F\) has it, with the power depending on the shift \(c\) alone. Taking \(-\ln\) of both sides turns that power into a factor, and the assumption is that the factor is the same at every \(t\):
\[ \frac{-\ln F(t - c)}{-\ln F(t)} \quad \text{depends on } c \text{ alone.} \]
The only positive monotone functions that rescale by a constant under every shift are exponentials. So \(-\ln F\) is an exponential, and \(F\) is a Gumbel again, up to a shift and a scale. Yellott [Yellott, JMP ’77] proved the stronger statement, that a Gumbel is the only noise of any kind whose argmax follows a softmax at every score vector. Three candidates are the fewest that force it; with two, other noises match the softmax as well.
A Gumbel still has a free scale, and privacy is what sets it. An argmax is unchanged when every entry is divided by the same positive constant, so multiplying the noise by a constant is the same as dividing every score by it. Let \(\Delta\) bound how much one person’s data can move any single score, and fix a privacy level \(\varepsilon > 0\). Gumbel noise of scale \(2\Delta/\varepsilon\) then draws the winner from the softmax of the scaled scores \(\varepsilon s_i / 2\Delta\): that is the exponential mechanism.
Claim: the exponential mechanism, and so report-noisy-max with Gumbel noise of scale \(2\Delta/\varepsilon\), is \(\varepsilon\)-differentially private: changing one person’s data multiplies the probability of any outcome by at most \(e^{\varepsilon}\).
Proof
Write \(s_i'\) for the scores after one person’s data changes, so that \(|s_i' - s_i| \le \Delta\) for every \(i\), and compare the two chances that candidate \(i\) wins:
\[\begin{align} \frac{\Pr(i \text{ wins, new scores})}{\Pr(i \text{ wins, old scores})} &= \frac{e^{\varepsilon s_i' / 2\Delta}}{e^{\varepsilon s_i / 2\Delta}} \cdot \frac{\sum_j e^{\varepsilon s_j / 2\Delta}}{\sum_j e^{\varepsilon s_j' / 2\Delta}} \\ &\le e^{\varepsilon/2} \cdot e^{\varepsilon/2} \\ &= e^{\varepsilon}. \end{align}\]
The first line writes each probability as its weight over the sum of all weights and regroups. The second bounds both fractions at once: one score moves by at most \(\Delta\), so its weight moves by a factor of at most \(e^{\varepsilon \Delta / 2\Delta} = e^{\varepsilon/2}\), and a sum of weights that each move by at most that factor moves by at most that factor too. The weight and the sum each contribute one \(e^{\varepsilon/2}\), and those two halves are the \(2\) in the noise scale.
Take five candidates with scores \((10, 9, 8, 6, 3)\) and \(\Delta = 1\). At \(\varepsilon = 1\) the mechanism picks them with probabilities about \((0.47, 0.28, 0.17, 0.06, 0.01)\): the frontrunner wins about half the time, and no single record settles it. \(\varepsilon\) is a dial on that spread, not just a scale factor: in the plot, the same five candidates move from equally likely as \(\varepsilon \to 0\) toward the frontrunner winning outright as \(\varepsilon\) grows, with \(\varepsilon = 1\) marked at the point used above.
Exponential Noise Gives Permute-and-Flip
The win-probability integral holds for any noise; only its collapse into a closed form needed Gumbel’s identity. Exponential noise has no such identity. Its CDF only starts at zero:
\[ F(t) = 1 - e^{-t} \quad \text{for } t \ge 0. \]
Its one-sided support truncates every rival factor instead of turning it into a power. Two candidates are enough to see what it gives instead.
Say the two scores are \(s_1 \ge s_2\). Candidate 2 wins when \(Z_2 - Z_1 > s_1 - s_2\), and the difference of two independent \(\mathrm{Exp}(1)\) variables is a standard Laplace:
\[ Z_2 - Z_1 \sim \mathrm{Laplace}(0, 1). \]
Its upper tail beyond any \(t \ge 0\) is \(\tfrac{1}{2} e^{-t}\), so the runner-up’s chance falls off from one half at the same rate as the gap:
\[ \Pr(\text{candidate 2 wins}) = \tfrac{1}{2}\, e^{-(s_1 - s_2)}. \]
The softmax puts \(1 / (1 + e^{s_1 - s_2})\) on that same loser, and dividing one by the other collapses to a single term:
\[\begin{align} \frac{\tfrac{1}{2}\, e^{-(s_1 - s_2)}}{1 / (1 + e^{s_1 - s_2})} &= \frac{1 + e^{s_1 - s_2}}{2\, e^{s_1 - s_2}} \\ &= \frac{1 + e^{-(s_1 - s_2)}}{2}, \end{align}\]
where the first line multiplies by the reciprocal of the softmax probability, and the second divides top and bottom by \(e^{s_1 - s_2}\). That ratio is \(1\) when the scores are tied and drops toward \(\tfrac{1}{2}\) as the gap widens: exponential noise never favors the runner-up more than the softmax does, and in the limit favors it half as much.
That is permute-and-flip, introduced by McKenna & Sheldon [MS, NeurIPS ’20], and the advantage survives past two candidates. Call the regret of a draw the best score minus the selected candidate’s score. They prove that at every score vector, permute-and-flip’s regret exceeds any threshold no more often than the exponential mechanism’s does, so its expected regret is never larger. On the family that holds both mechanisms to their worst case, one candidate on top and the rest tied below it, they work out both expected regrets in closed form.
That floor is exactly the two-candidate computation above, since with two candidates the regret is just the gap times the runner-up’s win chance. Whether any score vector pushes the ratio below it is open.
The source of that factor of two is clearest if we build both mechanisms out of the same coins. Only gaps matter, so shift every score down until the largest is \(0\). Each \(e^{s_i}\) then lands in \((0, 1]\) and can serve as a coin’s probability of heads (in the private version, \(e^{\varepsilon s_i / 2\Delta}\)). The best candidate’s coin always comes up heads, and a candidate one unit of score below it comes up heads a fraction \(e^{-1}\) of the time. Both mechanisms flip these coins and return a candidate that came up heads, and they differ in exactly one place: what happens to a candidate that comes up tails.
The exponential mechanism samples with replacement. Pick a candidate uniformly at random, flip its coin, and on tails put it back and draw again, the same candidate included. A rejected runner-up returns to the pool and gets more chances at its rare heads. Each round returns candidate \(i\) with probability \(e^{s_i}/n\) and terminates with total probability \(\sum_j e^{s_j}/n\). Conditioning on which round ends recovers exactly the softmax.
Permute-and-flip samples without replacement. Shuffle the candidates, walk down the order flipping each coin once, and return the first heads. The best candidate always comes up heads, so the walk always stops. A runner-up that has already been flipped is out for the rest of that draw.
Back at two candidates, half the shuffles put the best one first, and then the runner-up is never flipped at all. Only in the other half does it get its one chance at heads, so it wins \(\tfrac{1}{2} e^{-(s_1 - s_2)}\) of the time, matching the exponential noise above. Ding, Kifer, Saghaian, Steinke, Wang, Xiao & Zhang [DK+, ’21] proved the equivalence holds at every \(n\): the without-replacement sampler is exactly noisy argmax with exponential noise.
Laplace Noise Gives Report-Noisy-Max
Laplace already made an appearance, as the two-candidate gap \(Z_2 - Z_1\) between two exponential draws. Put it in the noise slot directly instead, one Laplace draw per candidate, and neither identity above is available: Laplace has no shift-to-power law like Gumbel’s, and no one-sided memorylessness like the exponential’s. What it has instead is symmetry, and that turns out to be enough.
The mechanism is report-noisy-max: add independent \(\mathrm{Lap}(\Delta/\varepsilon)\) noise to every score and report the argmax, no factor of two in the scale. Gumbel needed that factor because half its privacy budget protects the softmax’s normalizing sum, which a person’s data can shift along with the winner’s own weight. Report-noisy-max never forms that sum. There is nothing behind the argmax but the \(n\) noisy scores themselves, so the whole budget can go toward the one thing a person’s data can actually move: the winner’s own noisy score.
Claim: report-noisy-max with \(\mathrm{Lap}(\Delta/\varepsilon)\) noise is \(\varepsilon\)-differentially private, whenever one person’s data can only raise a score, and raise any single one by at most \(\Delta\).
Proof
Fix candidate \(i\) and two databases where \(D\) has one more person’s data than \(D'\), so their scores satisfy \(s_j \ge s_j'\) and \(s_j \le s_j' + \Delta\) for every \(j\). Fix the noise \(Z_j\) drawn for every rival \(j \ne i\), and given that fixed draw define the threshold candidate \(i\)’s own noise must clear to beat every rival under \(D\):
\[ r^* = \min\{\, r : s_i + r > s_j + Z_j \text{ for every } j \ne i \,\}. \]
Candidate \(i\) wins under \(D\), for this fixed rival draw, exactly when \(Z_i \ge r^*\).
If \(Z_i \ge r^* + \Delta\), candidate \(i\) wins under \(D'\) too, with the same rival draw. By the definition of \(r^*\), \(s_i + r^* > s_j + Z_j\) for every \(j \ne i\); using \(s_i \le s_i' + \Delta\) and \(s_j \ge s_j'\):
\[\begin{align} (s_i' + \Delta) + r^* &\ge s_i + r^* \\ &> s_j + Z_j \\ &\ge s_j' + Z_j, \end{align}\]
so \(s_i' + (r^* + \Delta) > s_j' + Z_j\) for every \(j \ne i\): whenever \(Z_i \ge r^* + \Delta\), candidate \(i\)’s noisy score under \(D'\) already clears every rival’s.
That containment becomes a probability bound through the noise’s tail. \(Z_i \sim \mathrm{Lap}(\Delta/\varepsilon)\) independent of the rivals, and its tail can never fall by more than a factor of \(e^{-\varepsilon}\) when the threshold rises by \(\Delta\):
\[ \Pr(Z_i \ge t + \Delta) \ge e^{-\varepsilon} \Pr(Z_i \ge t) \quad \text{for every } t, \]
with equality once \(t \ge 0\), the same tail rate used for the exponential-noise gap above.
Combine the containment and the tail bound, still conditioned on the fixed rival draw:
\[ \Pr(i \text{ wins} \mid D') \ge \Pr(Z_i \ge r^* + \Delta) \ge e^{-\varepsilon} \Pr(Z_i \ge r^*) = e^{-\varepsilon} \Pr(i \text{ wins} \mid D). \]
Averaging over the rivals’ draw, whose distribution does not depend on the database, removes the conditioning:
\[ \Pr(i \text{ wins} \mid D) \le e^{\varepsilon} \Pr(i \text{ wins} \mid D'). \]
The same argument with \(D\) and \(D'\) exchanged, defining \(r^*\) from \(s_i'\) instead of \(s_i\), bounds the ratio the other way.
This is Dwork & Roth’s proof of report-noisy-max [DR, ’14], carried over from counting queries, where one more person can only raise a count, to general scores with the same monotonicity. Half the noise of Gumbel or exponential noise, for the same \(\varepsilon\): that is Laplace’s advantage, bought by having nothing to protect but the winner itself.
Choosing the Noise
Perturb and maximize is two lines of code, and the noise distribution decides which selector those two lines compute. Gumbel’s shift-to-power identity collapses the win probability into a closed form, so the winner is an exact draw from the softmax, at the price of a factor of two in the noise for the normalizer it has to protect; the same identity is the reparameterization the Gumbel-softmax relaxation uses to backpropagate through a discrete choice. Exponential noise’s memorylessness turns the same two lines into sampling without replacement, so its regret is never larger than the softmax’s and gets up to half as small, a saving worth taking anywhere private selection runs. Laplace has neither identity, but it also has no normalizer, so report-noisy-max spends its whole budget on the winner and gets away with half the noise of either; the same instinct, spend noise only on the one bit you actually need, drives the sparse vector technique, which stretches a fixed privacy budget across many queries by reporting only whether each one clears a threshold.
The general lesson: before building a distribution and drawing from it, check whether some noise’s argmax already lands there, exactly or in expectation, or needs no normalizer to begin with.