Privately Clipping Heavy-Tailed Data

Matthew Joseph; Alex Kulesza

cs.CROct 26, 2026

Privately Clipping Heavy-Tailed Data

Authors: Matthew Joseph, Alex Kulesza

Organizations: Google Research

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.

Figures & tables

Dataset	Steam	Reddit	LastFM	HN	MovieLens	Pantry	Twitch	Foursquare	Jester	Slashdot
$\mathsf{OptimizeRC}$	1.02	1.03	1.32	1.04	1.12	1.05	1.22	1.10	1.05	1.04
$\mathsf{HLY\text{-}UQ}$	1.23	1.08	5.45	3.97	1.43	2.94	8.40	4.31	1.27	6.93
$\mathsf{UQ}$ , 0.9	1.64	6.26	5.31	1.01	1.05	1.58	5.67	35.65	3.24	2.08
$\mathsf{UQ}$ , 0.95	1.01	2.76	11.15	1.41	1.32	1.06	7.74	67.95	1.22	3.96
$\mathsf{UQ}$ , 0.99	2.33	1.01	41.40	5.06	2.06	1.41	11.78	136.66	1.10	13.87
$\mathbf{\hat{F}(C^{*})}$	0.96	0.99	0.51	0.89	0.86	0.97	0.08	$\approx$ 0.00	0.98	0.65

Table 1: First five rows: mean error ratio (relative to optimal clipping) across 100 trials at

\rho_{\textsc{clip}}=0.05

for each method (lower is better), with the lowest error ratio bolded for each dataset. Bottom row: empirical CDF at the optimal clipping bound

C^{*}

across datasets.

Figure 1: Plots of $\mathsf{OptimizeRC}$ ’s performance against $\mathsf{UQ}$ ( $q=\{0.9,0.95,0.99\}$ ) and $\mathsf{HLY\text{-}UQ}$ . Each line is a different method, and each point on the line represents the mean of 100 trials per $\rho_{\textsc{clip}}\in\{0.01,0.02,\ldots,0.1\}$ . We plot ratios of the mean MSE with respect to the (non-private) MSE-optimal $\mathsf{Optimal}$ , so a lower value is better.

Dataset	Steam	Reddit	LastFM	HN	MovieLens	Pantry	Twitch	Foursquare	Jester	Slashdot
$\frac{\\|\mathbf{L}-\mathbf{R}\\|_{2}}{\\|\mathbf{L}\\|_{2}}$	0.10	0.04	0.27	0.27	0.13	0.29	0.27	0.18	0.14	0.38

Table 2: Normalized

\ell_{2}

distance between

\mathbf{L}=\hat{\mathbb{E}}[(R_{i}-C^{*})U_{i}\mid R_{i}>C^{*}]

and

\mathbf{R}=\hat{\mathbb{E}}[R_{i}-C^{*}\mid R_{i}>C^{*}]\hat{\mathbb{E}}[U_{i}\mid R_{i}>C^{*}]

(LHS and RHS in Assumption 1 ). Values far from 0 correspond to worse assumption violations.

Algorithm	Steam	Reddit	LastFM	HN	MovieLens	Pantry	Twitch	Foursquare	Jester	Slashdot
$\mathsf{OptimizeRC}$	0.14	0.7	0.4	0.1	0.06	0.05	1	0.2	0.07	0.13
$\mathsf{UQ}$ , 0.9	0.01	0.03	0.02	0.007	0.006	0.02	0.02	0.008	0.01	0.007
$\mathsf{UQ}$ , 0.95	0.01	0.03	0.02	0.007	0.006	0.02	0.02	0.009	0.01	0.007
$\mathsf{UQ}$ , 0.99	0.02	0.03	0.02	0.009	0.006	0.02	0.02	0.01	0.01	0.009
$\mathsf{HLY\text{-}UQ}$	0.01	0.03	0.02	0.009	0.006	0.02	0.02	0.006	0.01	0.008

Table 3: Average runtime (in seconds) of bound estimation algorithms.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Plots of residual coherence vs. clipping bounds across all evaluated datasets. The horizontal line is $-T$ in $\mathsf{OptimizeRC}$ . Note that HN, Pantry, and Slashdot have a distinctive “staircase” shape because the small clipping bound range accentuates the underlying integer values. For the Twitch and Foursquare datasets, residual coherence is immediately below the threshold, and $\mathsf{OptimizeRC}$ outputs 1. This aggressively clipped bound nonetheless beats the $\mathsf{UnboundedQuantile}$ methods, which select bounds that are too large (see Figure 3 ).

Figure 3: Plots illustrating the ratio between the estimated clipping bound and the optimal $C^{*}$ . A value $<1$ means the estimated bound is smaller, and a value $>1$ means it is larger.

Figure 4: An analogue of Figure 1 , but for light-tailed datasets. Note that methods occasionally beat $\mathsf{Optimal}$ on NFL because the low $d$ increases the noise variance.

Figure 5: An analogue of Figure 3 , but for light-tailed datasets.

Differential Privacy

Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.

See all 278 papers

Private Decentralized Optimization with Noise Reduction and Bias Correction
Sep 23, 2026Yizhao Fan, Wenjian Luo, Jiaojiao ZhangDifferential Privacy Variance Reduction
Harbin Institute of Technology, Shenzhen · Great Bay University
Limits of Personalizing Differential Privacy Budgets
May 13, 2026Edwige Cyffers, Juba ZianiDifferential Privacy Personalized Differential Privacy
CNRS, LAMSADE, Dauphine-PSL · Georgia Institute of Technology.
Differentially Private Truncation of Unbounded Data via Public Second Moments
Feb 25, 2026Zilong Cao, Xuan Bi, Hai ZhangPrivacy-Preserving ML Differential Privacy
School of Mathematics, Northwest University · Department of Information and Decision Sciences, Minnesota Carlson, University of Minnesota

Sep 23, 2026J/K move · Enter open · S save

Private Decentralized Optimization with Noise Reduction and Bias Correction

Yizhao Fan, Wenjian Luo, Jiaojiao Zhang

Harbin Institute of Technology, Shenzhen · Great Bay University

Differential Privacy Variance Reduction Decentralized Optimization

Open paper AskPDF arXiv

Private decentralized learning is affected by sampling noise, privacy noise, and decentralized bias under heterogeneous data. We propose Private Recursive Decentralized Optimization (PRDO). PRDO uses recursive estimation with same-batch gradient differences to reduce estimation errors caused by sampling and privacy noise, while its Exact Diffusion component corrects decentralized bias arising from data heterogeneity. Our analysis establishes a nonconvex convergence bound without assuming uniformly bounded data heterogeneity across nodes. It further gives a sufficient condition under which recursive gradient differences yield strictly lower query sensitivity than private Exact Diffusion, together with an example that rigorously satisfies this condition. Experiments show improved accuracy over the evaluated baselines.

Abstract

Differential Privacy

Explore similar work

Private Decentralized Optimization with Noise Reduction and Bias Correction

Limits of Personalizing Differential Privacy Budgets

Differentially Private Truncation of Unbounded Data via Public Second Moments