Exponential Mechanism

The mechanism selects an output r from a discrete set R based on a utility function u(D, r) that scores the quality of output r for dataset D. The probability of selecting any output is exponentially proportional to its utility score, ensuring high-utility outcomes are chosen with high probability. This makes it ideal for tasks like selecting the best candidate from a set (e.g., the optimal hyperparameter, the top-k items from a ranking, or the most frequent label in a federated voting round).

The randomness (and thus the privacy guarantee) is controlled by the global sensitivity Δu of the utility function. Sensitivity is the maximum change in the utility score for any output r when a single individual's data is added or removed from D. The probability distribution is scaled by ε / (2Δu), meaning:

• Lower sensitivity allows for sharper probability distinctions between high and low-utility outputs.
• Higher sensitivity flattens the distribution, providing stronger privacy but potentially lower output quality.
• This sensitivity is global, calculated over all possible datasets and outputs.

When implemented correctly, the exponential mechanism provides pure ε-differential privacy (ε-DP), meaning it does not require the failure probability parameter δ. This is a stronger guarantee than the (ε, δ)-DP offered by mechanisms like the Gaussian mechanism. The guarantee holds for any choice of utility function and output space, making it a foundational building block for complex private algorithms where the output is a 'best choice' rather than a numerical query answer.

In privacy-preserving federated learning, the exponential mechanism is used for discrete decisions at the server or client level. Key use cases include:

• Client Selection: Privately selecting a subset of devices for a training round based on a utility score (e.g., data quality, device readiness).
• Hyperparameter Tuning: Selecting the best-performing model configuration from a discrete set based on private validation metrics aggregated from clients.
• Voting & Consensus: Aggregating discrete labels or decisions from clients (e.g., in federated classification of rare events) while protecting individual votes.

The main challenge is sampling from the complex probability distribution defined over the potentially massive output space R. Efficient implementation strategies include:

• Gumbel Max Trick: Adding independent Gumbel noise to each utility score and selecting the argmax; this is mathematically equivalent to sampling from the exponential mechanism and can be more efficient.
• Domain-Specific Optimizations: For structured spaces like intervals or graphs, specialized sampling algorithms (e.g., via the exponential mechanism for range queries) can be used.
• The computational cost is a key trade-off versus the simpler Laplace or Gaussian mechanisms.

The exponential mechanism is a generalization. The Laplace mechanism can be seen as a special case for real-valued queries where the utility function is the negative absolute error. Its properties contrast with other core tools:

• vs. Laplace/Gaussian: Used for numeric queries; exponential is for non-numeric selection.
• vs. Randomized Response: A specific, simple instance of the local exponential mechanism for binary or categorical data.
• Composition: It composes with other differentially private mechanisms under standard composition theorems, allowing it to be part of larger private workflows where its privacy cost consumes part of the overall privacy budget.

The Laplace Mechanism is the foundational algorithm for achieving pure ε-differential privacy for numeric queries. It works by adding noise drawn from a Laplace distribution to the true query result. The scale of the noise is calibrated to the query's L1 sensitivity (the maximum change a single data point can cause), divided by the privacy parameter ε. It is optimal for queries where utility is measured by absolute error.

• Core Use: Releasing private counts, sums, averages, and histograms.
• Key Property: Provides pure (ε, 0)-DP, meaning no probability of failure.
• Contrast with Exponential Mechanism: The Laplace Mechanism outputs perturbed numbers, while the Exponential Mechanism selects from a discrete set of candidates.

The Gaussian Mechanism is a core algorithm for achieving the relaxed (ε, δ)-differential privacy guarantee. It adds noise drawn from a Gaussian (normal) distribution to the output of a function. The noise variance is proportional to the square of the function's L2 sensitivity and depends on both ε and δ. This mechanism often enables better utility than the Laplace Mechanism for high-dimensional queries like gradients, as Gaussian noise has lighter tails.

• Core Use: Differentially Private Stochastic Gradient Descent (DP-SGD) and high-dimensional vector queries.
• Key Property: Requires the relaxed (ε, δ)-DP guarantee (δ > 0).
• Utility Trade-off: Typically allows for smaller error magnitude than Laplace for the same privacy cost when δ is permissible.

Sensitivity is the maximum possible change in the output of a function when a single individual's data is added or removed from the dataset. It is the foundational concept that determines how much noise must be added to achieve differential privacy.

• L1 Sensitivity (Δ₁): The maximum absolute change, measured by the L1 norm. It directly sets the scale parameter for the Laplace Mechanism.
• L2 Sensitivity (Δ₂): The maximum Euclidean distance change, measured by the L2 norm. It determines the standard deviation of noise for the Gaussian Mechanism.
• Role in Exponential Mechanism: The sensitivity of the utility function determines how the probability distribution over outputs changes, controlling the privacy loss. A lower sensitivity allows for a sharper, higher-utility probability distribution for the same ε.

Randomized Response is a classic survey technique and one of the simplest mechanisms for achieving Local Differential Privacy (LDP). A respondent answers a sensitive binary question (e.g., "Yes/No") by telling the truth with probability p and lying with probability 1-p. The data collector can then correct for this known noise to estimate the true population proportion. It is a building block for more complex LDP protocols.

• Core Use: Collecting aggregate statistics (like heavy hitters or histograms) from users without trusting a central server.
• Key Property: Provides privacy at the data source before data leaves the client's device.
• Contrast with Exponential Mechanism: Both select an output from a set (truth/lie), but Randomized Response uses a fixed, simple probability flip, while the Exponential Mechanism uses a complex utility score to guide selection.

Composition Theorems are the mathematical rules that govern how privacy loss accumulates when multiple differentially private mechanisms are applied to the same dataset, either sequentially (adaptive composition) or in parallel. They are essential for privacy accounting in complex, multi-step algorithms like iterative machine learning.

• Basic Composition: The privacy parameters add up linearly. If you run k mechanisms each satisfying (εᵢ, δᵢ)-DP, the total composition satisfies (Σεᵢ, Σδᵢ)-DP. This bound is often loose.
• Advanced Composition: Provides a tighter, more favorable bound, where the total ε grows roughly with √k for a fixed δ.
• Role in Practice: Allows the design of algorithms like DP-SGD or private federated learning, where gradients are noised in each of thousands of training steps, by tracking the total (ε, δ) budget consumed.

Privacy Amplification by Subsampling is a powerful technique where applying a DP mechanism to a random subset of the data (e.g., a mini-batch) results in a stronger privacy guarantee (a smaller effective ε) than if the mechanism were applied to the full dataset. This is because an individual's data is only involved in the analysis with a known probability (the sampling rate).

• Core Use: The foundation for the strong privacy guarantees of DP-SGD, where each training step operates on a randomly sampled mini-batch.
• Key Insight: An adversary's uncertainty about any individual's participation is increased, amplifying privacy.
• Interaction with Exponential Mechanism: If the Exponential Mechanism's selection is based on a random sample of data, its privacy guarantee can be amplified, allowing for higher utility (a larger ε in the base mechanism) for the same final privacy level.