Exponential Mechanism

The mechanism's operation is defined by a utility function, u(D, o), which assigns a real-valued score to each possible output o given the input dataset D. This function quantifies the desirability or quality of an output. The mechanism exponentially favors outputs with higher utility scores.

• Key Role: The sensitivity of this utility function, defined as the maximum change in its score when any single individual's data is altered, directly determines the amount of randomness (privacy) injected.
• Example: In selecting the median income from a set of bins, the utility function could score each bin based on how close its value is to the true median of the dataset.

Instead of outputting a deterministic 'best' answer, the mechanism constructs a probability distribution over all possible outputs and samples from it. The probability of selecting an output o is proportional to:

exp(ε * u(D, o) / (2 * Δu))

Where:

• ε (epsilon) is the privacy budget parameter.
• Δu is the sensitivity of the utility function.
• This exponential weighting ensures outputs with higher utility are exponentially more likely to be chosen, but any output with non-zero utility has a non-zero probability, providing plausible deniability.

This is the primary distinction from mechanisms like Laplace or Gaussian noise. The Exponential Mechanism is designed for queries where the output is categorical or discrete, not a simple numeric value.

• Common Use Cases: Selecting the best candidate from a list, choosing a category (e.g., 'most frequent disease'), picking a location, or releasing the winning element in an auction.
• Contrast: Adding Laplace noise to a 'best category' index is meaningless. The Exponential Mechanism provides a principled, private way to make such discrete choices.

The algorithm provides pure ε-differential privacy. The guarantee stems from the use of the utility function's sensitivity (Δu) in the exponent's denominator. The mathematical proof shows that for any two neighboring datasets D and D' (differing by one record), and for any possible output o, the ratio of probabilities is bounded by exp(ε).

This ensures that an adversary observing the output cannot confidently determine whether any specific individual's data was included in the input, as the output distribution is nearly identical in both cases.

The epsilon (ε) parameter explicitly controls the balance between privacy and output quality.

• Low ε (Strong Privacy): The exponent ε / (2Δu) becomes small, making the probability distribution over outputs more uniform. This maximizes privacy but reduces the chance of selecting the truly highest-utility output.
• High ε (Better Utility): The probability mass concentrates more sharply on the outputs with the highest utility scores, increasing accuracy but weakening the privacy guarantee.
• Engineer's Control: This provides a tunable, quantitative knob for system designers to match privacy requirements to application needs.

The Exponential Mechanism is a generalization of the Laplace Mechanism. For a numeric query (like a count or sum), if you define the utility function as the negative absolute error, u(D, r) = -|q(D) - r|, where q(D) is the true query answer and r is a possible numeric output, the Exponential Mechanism's probability distribution becomes equivalent to adding Laplace noise to q(D).

This unified perspective shows that adding calibrated noise is a special case of exponential weighting based on a distance-based utility score.

The foundational mathematical framework that provides the formal privacy guarantee for mechanisms like the Exponential Mechanism. It ensures the output of a computation is statistically indistinguishable whether any single individual's data is included or excluded.

• Core Guarantee: Quantifies privacy loss via the epsilon (ε) parameter.
• Properties: Features post-processing immunity, meaning any analysis on a differentially private output cannot weaken the guarantee.
• Use Case: The essential standard for deploying privacy-preserving machine learning in regulated industries.

A critical pre-processing step that directly determines the amount of randomness (noise) required in differential privacy mechanisms. For a given query or utility function, it calculates the maximum possible change in output when a single record is added or removed from the dataset.

• Global Sensitivity (Δf): The maximum absolute change, over all possible neighboring datasets.
• Role in Exponential Mechanism: The sensitivity of the utility function scales the probability distribution from which the output is sampled, controlling the privacy-utility trade-off.

The canonical algorithm for achieving pure (ε,0)-differential privacy for queries with numeric outputs, such as counts, sums, or averages. It works by adding noise drawn from a Laplace distribution, centered at zero and scaled by the query's sensitivity divided by epsilon.

• Contrast with Exponential Mechanism: The Laplace Mechanism perturbs a single numeric answer. The Exponential Mechanism selects a discrete, non-numeric option (like a candidate or a bin label) from a set.
• Foundation: Often used as a building block within more complex private algorithms.

An algorithm for achieving the relaxed (ε, δ)-differential privacy guarantee. It adds noise drawn from a Gaussian (Normal) distribution, which is often preferable in practice due to its lighter tails compared to the Laplace distribution.

• Trade-off: Allows for a small, bounded probability (δ) of a larger privacy violation, often enabling less noise for the same epsilon value on complex queries.
• Application: Commonly used in private deep learning and iterative algorithms where many compositions occur.

The fundamental tension at the heart of all privacy-preserving data analysis. It describes the inverse relationship between the strength of a privacy guarantee and the accuracy or usefulness of the released output.

• In the Exponential Mechanism: A lower epsilon (stronger privacy) flattens the sampling probability distribution, making a sub-optimal output more likely. A higher epsilon skews the distribution toward higher-utility outputs but weakens privacy.
• Engineering Challenge: The core task of a privacy engineer is to navigate this trade-off to meet application-specific requirements.

Mathematical rules that dictate how privacy loss accumulates when multiple differentially private mechanisms are applied to the same dataset, either sequentially (sequential composition) or in parallel (parallel composition).

• Sequential Composition: The epsilons of sequentially applied mechanisms add up. If you use the Exponential Mechanism (ε₁) and then the Laplace Mechanism (ε₂), the total privacy loss is ε₁ + ε₂.
• Critical for Budgeting: Enables the tracking of a privacy budget across an entire analysis pipeline, ensuring the total cumulative privacy loss does not exceed a pre-defined limit.