Exponential Mechanism

The mechanism selects an output r from a range R with probability proportional to exp(ε · u(D, r) / (2 · Δu)). This means candidates with higher utility scores are exponentially more likely to be chosen. The utility function u(D, r) maps a dataset D and candidate r to a real-valued score, representing the 'goodness' of r for D. The sensitivity Δu is the maximum change in the utility function when a single record is added or removed, ensuring the probability distribution does not leak individual information.

Unlike the Laplace or Gaussian mechanisms, the Exponential Mechanism is designed for non-numeric, categorical outputs. It is the standard method for privately selecting items from a finite set, such as:

• Choosing the most common medical diagnosis from a patient survey.
• Selecting the best hyperparameter configuration for a model.
• Picking the most popular product category from user purchase histories. It guarantees that the selection process itself does not reveal whether any single individual's data was in the input.

The Exponential Mechanism satisfies ε-differential privacy. For any two neighboring datasets D and D' differing by one record, and for any output r, the ratio of the probabilities of selecting r is bounded by e^ε. This ensures that an adversary observing the selected output cannot confidently infer the presence or absence of any single record. The privacy loss parameter ε directly controls the strength of the guarantee; a smaller ε forces the selection probabilities to be more uniform, increasing privacy but potentially reducing utility.

A common and computationally efficient implementation is the Report Noisy Max algorithm. Instead of sampling from the full exponential distribution, it adds independent noise drawn from a Gumbel distribution (or Laplace noise) to the utility score of each candidate and simply selects the candidate with the highest noisy score. This approach is mathematically equivalent to the Exponential Mechanism and is widely used in practice for tasks like private selection from a large set of candidates.

The accuracy of the mechanism hinges on the sensitivity of the utility function (Δu). This is defined as the maximum absolute difference in utility for any output r across two neighboring datasets: Δu = max_{r} |u(D, r) - u(D', r)| A high-sensitivity utility function requires more randomness (a wider probability distribution) to mask a single record's influence, potentially selecting a sub-optimal candidate. Careful design of the utility function to minimize sensitivity is critical for practical performance.

The Exponential Mechanism composes gracefully with other differentially private mechanisms. When used sequentially, the total privacy cost accumulates according to standard composition theorems. For k independent applications, each with privacy parameter ε, the total privacy loss is at most kε (basic sequential composition). Advanced composition theorems provide tighter bounds, allowing the Exponential Mechanism to be used as a subroutine in complex, multi-stage private data analysis pipelines without exhausting the privacy budget prematurely.