Course contentsShow
← Machine Learning and Deep Learning
Lesson 3345 of 3,53873. Privacy in Machine LearningFree lesson

The Exponential Mechanism

Differential privacy for non-numeric outputs by sampling from exponentially weighted distributions.

The Exponential Mechanism

What You'll Learn

You'll learn how differential privacy can protect non-numeric outputs by sampling from exponentially weighted probability distributions based on utility scores.


Why We Need More Than Laplace or Gaussian Noise

So far, you've seen the Laplace Mechanism and Gaussian Mechanism add calibrated noise to numeric outputs. But what if your algorithm needs to return something non-numeric—like a category, a ranking, or a discrete choice? You can't just "add noise" to "cat" or "Option A."

The Exponential Mechanism solves this by converting your problem into a probability distribution over possible outputs.


How It Works

  1. Define a utility function u(data, output) that scores how "good" each possible output is given your data
  2. Compute the sensitivity Δu: how much one person's data can change the utility score
  3. Sample an output with probability proportional to exp(ε · u(data, output) / (2 · Δu))

Outputs with higher utility are exponentially more likely to be chosen, but lower-utility options still have a chance—this randomness provides privacy.


Intuition: A Weighted Lottery

Imagine choosing the "best city to recommend" from private location data. Instead of always picking the top-scored city (which leaks information), you run a weighted lottery: the best city gets the most tickets, second-best fewer tickets, and so on. The exponential weighting ensures the mechanism is (ε, 0)-differentially private.

The privacy parameter ε controls how much the utility influences the probabilities—smaller ε means flatter distribution (more privacy, less utility).


Key Takeaway:
The Exponential Mechanism enables differentially private selection from discrete, non-numeric outputs by sampling proportionally to exp(ε · utility / (2 · Δu)), balancing privacy with the quality of the chosen result.