Privately Clipping Heavy-Tailed Data

Matthew Joseph, Alex Kulesza

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.