The Exponential Mechanism
What you'll learn: How differential privacy handles non-numeric queries by probabilistically selecting answers weighted by their utility and privacy cost.
Beyond Numeric Noise
So far, differential privacy mechanisms like Laplace and Gaussian add noise to numeric outputs—perfect for counts, sums, or averages. But what if your query returns something non-numeric, like "Which city has the highest crime rate?" or "What's the most common diagnosis?" You can't just add noise to "Boston" or "diabetes."
The Core Idea
The Exponential Mechanism solves this by turning selection into a privacy-preserving lottery. Instead of deterministically picking the "best" answer (which leaks information about individuals), it assigns each candidate answer a probability proportional to:
exp(ε × utility(answer) / (2 × sensitivity))
Where:
- Utility measures how "good" each answer is (e.g., accuracy, relevance)
- Sensitivity captures how much one person's data can change the utility scores
- ε is your privacy budget
Better answers get exponentially higher probabilities, but worse answers still have a chance. This randomness provides plausible deniability: observers can't be certain whether the true best answer was chosen or a nearby alternative.
Example Analogy
Imagine voting for "favorite ice cream flavor" in a dataset. Vanilla scores 100 points, chocolate 95, strawberry 80. Instead of always announcing "vanilla wins," the mechanism might pick vanilla 70% of the time, chocolate 25%, and strawberry 5%—masking whether any single person's vote mattered.
When to Use It
Any time you need to privately select from discrete options: top-k queries, recommendation systems, or releasing categorical statistics.
Key Takeaway:
The Exponential Mechanism achieves differential privacy for non-numeric outputs by exponentially weighting candidates based on utility, making better answers more likely while preserving plausible deniability.