Method for choosing clipping bounds improves private summation of heavy-tailed data
Privately Clipping Heavy-Tailed Data
Cryptography and SecurityMachine Learning
Summary
When adding up many pieces of data while keeping each person’s information private, it’s common to limit how large each piece can be before adding noise. The authors found a way to pick this size limit privately based on the data itself. Their method balances how much data gets clipped versus the extra noise needed for privacy. They tested this on various datasets and it worked better than older approaches.
What this means in practice
- •For privacy engineers: Improve privacy-preserving data aggregation by dynamically selecting clipping thresholds to reduce error in heavy-tailed datasets.
- •For financial data teams: Better handle outliers in private summation of transactional or market data, where some values are unusually large.
Authors
Matthew Joseph, Alex Kulesza
Abstract
Summing vectors is a basic task in differentially private data analysis. Standard private sum algorithms clip vectors to some bound, sum them, and add noise scaled to the bound. The differential privacy literature has developed a deep library of noise addition mechanisms, but it offers few tools for privately choosing a clipping bound based on the data. We introduce a method that privately chooses a clipping bound by optimizing residual coherence, the directional alignment of vectors exceeding the bound, against the variance cost of additional noise. We prove a close relationship between residual coherence and bias for a general class of heavy-tailed data regimes and show empirically that, across several datasets, our method outperforms existing baselines.