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
OptimizeRC
1.02
1.03
1.32
1.04
1.12
1.05
1.22
1.10
1.05
1.04
HLY-UQ
1.23
1.08
5.45
3.97
1.43
2.94
8.40
4.31
1.27
6.93
UQ , 0.9
1.64
6.26
5.31
1.01
1.05
1.58
5.67
35.65
3.24
2.08
UQ , 0.95
1.01
2.76
11.15
1.41
1.32
1.06
7.74
67.95
1.22
3.96
UQ , 0.99
2.33
1.01
41.40
5.06
2.06
1.41
11.78
136.66
1.10
13.87
F^(C∗)
0.96
0.99
0.51
0.89
0.86
0.97
0.08
≈ 0.00
0.98
0.65
Table 1: First five rows: mean error ratio (relative to optimal clipping) across 100 trials at ρ\textscclip=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 OptimizeRC ’s performance against UQ ( q={0.9,0.95,0.99} ) and HLY-UQ . Each line is a different method, and each point on the line represents the mean of 100 trials per ρ\textscclip∈{0.01,0.02,…,0.1} . We plot ratios of the mean MSE with respect to the (non-private) MSE-optimal Optimal , so a lower value is better.
Dataset
Steam
Reddit
LastFM
HN
MovieLens
Pantry
Twitch
Foursquare
Jester
Slashdot
∥L∥2∥L−R∥2
0.10
0.04
0.27
0.27
0.13
0.29
0.27
0.18
0.14
0.38
Table 2: Normalized ℓ2 distance between L=E^[(Ri−C∗)Ui∣Ri>C∗] and R=E^[Ri−C∗∣Ri>C∗]E^[Ui∣Ri>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
OptimizeRC
0.14
0.7
0.4
0.1
0.06
0.05
1
0.2
0.07
0.13
UQ , 0.9
0.01
0.03
0.02
0.007
0.006
0.02
0.02
0.008
0.01
0.007
UQ , 0.95
0.01
0.03
0.02
0.007
0.006
0.02
0.02
0.009
0.01
0.007
UQ , 0.99
0.02
0.03
0.02
0.009
0.006
0.02
0.02
0.01
0.01
0.009
HLY-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 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 OptimizeRC outputs 1. This aggressively clipped bound nonetheless beats the 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 Optimal on NFL because the low d increases the noise variance.
Figure 5: An analogue of Figure 3 , but for light-tailed datasets.
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.
Yizhao Fan, Wenjian Luo, Jiaojiao Zhang
Harbin Institute of Technology, Shenzhen · Great Bay University
A key technical difficulty in differential privacy is selecting a privacy budget that satisfies privacy requirements while maximizing utility. A natural and well-studied workaround is to use personalized privacy budgets, which may differ across agents. In this paper, we show that personalized budgets come with major limitations and that for mean estimation, the dominant factor is not full personalization, but rather choosing the right effective privacy budget. This can be achieved through a simple thresholding operator that we describe. Compared with this thresholding baseline, the gains obtained by fully personalized mechanisms are limited. In particular, we precisely quantify the constant-factor improvement in settings with mixed private and public datasets and in private datasets with two levels of privacy requirements. We also establish upper bounds and identify regimes of maximal gain for arbitrary privacy requirements.
Edwige Cyffers, Juba Ziani
CNRS, LAMSADE, Dauphine-PSL · Georgia Institute of Technology.
Data privacy is important in the AI era, and differential privacy (DP) is one of the golden solutions. However, DP is typically applicable only if data have a bounded underlying distribution. We address this limitation by leveraging second-moment information from a small amount of public data. We propose Public-moment-guided Truncation (PMT), which transforms private data using the public second-moment matrix and applies a principled truncation whose radius depends only on non-private quantities: data dimension and sample size. This transformation yields a well-conditioned second-moment matrix, enabling its inversion with a significantly strengthened ability to resist the DP noise. Furthermore, we demonstrate the applicability of PMT by using penalized and generalized linear regressions. Specifically, we design new loss functions and algorithms, ensuring that solutions in the transformed space can be mapped back to the original domain. We have established improvements in the models' DP estimation through theoretical error bounds, robustness guarantees, and convergence results, attributing the gains to the conditioning effect of PMT. Experiments on synthetic and real datasets confirm that PMT substantially improves the accuracy and stability of DP models.
Zilong Cao, Xuan Bi, Hai Zhang
School of Mathematics, Northwest University · Department of Information and Decision Sciences, Minnesota Carlson, University of Minnesota