Privately Clipping Heavy-Tailed Data

Summing vectors is a basic task in differentially private data analysis. Standard algorithms clip vectors to some bound, sum them, and add noise scaled to the bound. While the differential privacy literature has developed a deep library of such noise addition mechanisms, it offers few tools for privately choosing the clipping bound directly from 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.