Subsampled Exponential Mechanism: Differential Privacy in Large Output Spaces.

Area of Science:

• Computer Science
• Data Privacy
• Machine Learning

Background:

• Differential privacy is a leading framework for private data analysis.
• It bounds how much a randomized function's output can change due to single record modifications.
• The exponential mechanism is often used for weighted choices but can be computationally intensive with many outcomes.

Purpose of the Study:

• To address the scalability limitations of the exponential mechanism in differential privacy.
• To introduce a novel approach, the subsampled exponential mechanism, for efficient private data analysis.
• To evaluate the privacy and accuracy guarantees of the subsampled exponential mechanism.

Main Methods:

• Developed the subsampled exponential mechanism, which scores a sample of possible outcomes instead of all of them.
• Proved that the subsampled exponential mechanism preserves differential privacy.
• Established accuracy bounds comparable to the full exponential mechanism.
• Applied the mechanism to a clustering problem for empirical evaluation.

Main Results:

• The subsampled exponential mechanism maintains differential privacy guarantees.
• It achieves accuracy bounds similar to the full exponential mechanism.
• In a clustering application, it outperformed a previously published private algorithm.
• It demonstrated comparable performance to the full exponential mechanism but with significantly improved scalability.

Conclusions:

• The subsampled exponential mechanism is a scalable and effective method for private data analysis.
• It provides a practical alternative to the full exponential mechanism when the outcome space is large.
• This approach enhances the applicability of differential privacy in real-world scenarios with large datasets.