Source-linked AI summary
Privately Clipping Heavy-Tailed Data
Matthew Joseph, Alex Kulesza
TL;DR
Private vector sums require a clipping bound, but the literature offers little guidance for choosing one from data, and bound selection is a challenge to deploying DP. OptimizeRC privately tests residual coherence across candidate bounds; experiments report lower MSE than comparable baselines.
Problem
The literature offers little guidance for privately choosing a data-dependent clipping bound, although selecting one is a significant challenge to deploying DP.
Source: §1 · p. 1Method
OptimizeRC applies AboveThreshold to candidate clipping bounds, using residual coherence as a proxy for the bias derivative when selecting a bound.
Source: §1 · p. 2, §3.1 · p. 4Results
Across experiments, OptimizeRC yields lower MSE than comparable baselines in the literature.
Source: §5 · p. 12Takeaways & Limitations
The experiments provide evidence that good private sum clipping bounds can be selected without operator input using fixed, untuned algorithmic choices.
Source: §5 · p. 12The authors have not applied OptimizeRC to gradient clipping in DP-SGD.
Source: §5 · p. 12
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction frames clipping-bound selection as a difficult private-sum problem when vector norms span widely different scales. It proposes using residual coherence to choose a bound privately and situates this approach among quantile- and mean-based alternatives.
1 Introduction
- For heavy-tailed data, norm quantiles can lie on vastly different scales, and light-tailed heuristics offer no general reason to prefer one clipping bound.A high quantile may work when large vectors align and poorly when they do not.Source: §1 · p. 1
- OptimizeRC privately checks residual coherence along candidate clipping bounds with AboveThreshold to choose an ℓ2 bound for a private vector sum.Residual coherence has bounded sensitivity, making it amenable to AboveThreshold.Source: §1 · p. 2
- Residual coherence is large when many vectors above the bound are well aligned, helping indicate when the clipped tail signal may be outweighed by added noise.Larger clipping bounds reduce bias but increase noise.Source: §1 · pp. 1–2
1.1 Related Work
- Prior work gives an optimal norm quantile for scalar sums, while vector quantile methods shift tuning to a fixed quantile that varies across heavy-tailed datasets [12].Other mean-estimation approaches may assume light-tailed data or require careful parameter choices; DP-SGD clipping methods also introduce tuning or privacy-budget costs.Source: §1.1 · pp. 2–3
2 Preliminaries
The preliminaries use swap neighboring databases and concentrated differential privacy to state the privacy setup. They also describe Gaussian noise for the final sum and AboveThreshold for privately checking a sequence of queries.
2 Preliminaries
- Neighboring databases differ by replacing at most one data point; the paper uses swap privacy and notes the method can be modified for add-remove privacy.The authors choose concentrated differential privacy partly for composition neatness.Source: §2 · p. 3
- Under ρ-CDP, Rényi divergence between outputs on neighboring databases is bounded by ρα for every α > 1.The paper says its approach extends to pure and approximate DP, with less neat composition.Source: §2 · p. 3
- The final private sum is tuned for spherical ρ-CDP Gaussian noise, with the derivation extending to noise whose covariance trace has a closed-form expression.The Gaussian mechanism adds noise calibrated to the statistic’s ℓ2 sensitivity.Source: §2 · p. 3
- AboveThreshold checks low-sensitivity queries against a threshold with added noise, returns at the first crossing, and is 4ρ-CDP.Its privacy cost scales with the number of positive responses.Source: §2 · p. 3
3 Optimizing Residual Coherence
OptimizeRC chooses a clipping bound by using residual coherence as a proxy for the bias derivative and balancing it against the variance cost of noise. Under Assumption 1, expected residual coherence at the MSE-optimal bound is near the algorithm’s threshold.
3.1 Algorithm Description
- OptimizeRC uses residual coherence, a proxy for the bias derivative, to search for a bound balancing C · RC(C)^2 against the variance derivative.The bias derivative depends on private magnitude depths with unbounded sensitivity, while residual coherence has bounded sensitivity.Source: §3.1 · p. 4
- OptimizeRC is ρclip-CDP for nonnegative vectors and 4ρclip-CDP for general vectors.Source: §3.1 · p. 4
3.2 Implementing OptimizeRC
- The pre-computation obtains all needed residual-coherence values in O(nd + Bd) time and space.The implementation can gain further savings from sparse matrices and parallelism.Source: §3.2 · p. 5
3.3 Residual Coherence and the Optimal Clipping Bound
- Under Assumption 1, expected residual coherence at the MSE-optimal bound is near T = 2d/ρsum.The assumption requires a tail vector’s excess magnitude to be uncorrelated with its direction; it formalizes the idea that outliers vary in different ways.Source: §3.3 · p. 5
- Assumption 1 is sufficient but may not be necessary, and most evaluated datasets only approximately satisfy it.No dataset was chosen to satisfy the assumption.Source: §3.3 · p. 7
4 Experiments
Experiments compare OptimizeRC with quantile-based baselines on real-world datasets, evaluating error, the utility assumption, and runtime.
4.1 Baselines
4.2 Datasets
- Ten real-world datasets span mostly internet contexts; eight contain nonnegative data and two also contain negative data, while user-dependent histogram key selection is treated as outside scope.The evaluation treats dataset column headers as public information and omits private key selection.Source: §4.2 · pp. 8–9
- On four additional light-tailed datasets, OptimizeRC matched the best baseline error.The authors report that tailoring OptimizeRC to heavy-tailed data did not lead to poor light-tailed performance.Source: §4.2 · p. 9
4.3.1 Error
- At ρclip = 0.055, OptimizeRC is best on 6/10 datasets, second-best on 4/10, and at most 1.32× suboptimal; every baseline is at least 2× suboptimal on half or more.Figure 1 plots mean MSE ratios against non-private Optimal; lower is better.Source: §4.3.1 · p. 9, Figure 1 · p. 10
- Residual coherence typically crosses its threshold near C*, while HLY-UQ overestimates C* and never beats OptimizeRC across 100 heavy-tailed dataset–ρclip pairs.Residual coherence is also monotonically decreasing in C on these datasets.Source: §4.3.1 · pp. 9, 11
4.3.2 Testing Assumption 1
- Assumption 1 is only approximately satisfied on most datasets, suggesting Theorem 1 is conservative and weaker properties may govern practical performance.Table 2 reports normalized ℓ2 distances between the assumption’s two sides; larger distances indicate worse violations.Source: §4.3.2 · p. 11, Table 2 · p. 11
4.3.3 Time
- OptimizeRC runs in ≤1 s even on hundreds of thousands of vectors, though it is typically about an order of magnitude slower than UQ and HLY-UQ.The authors regard this mild absolute-runtime increase as acceptable given the error improvements.Source: §4.3.3 · pp. 11–12, Table 3 · p. 12
5 Discussion
OptimizeRC incorporates dataset geometry to select clipping bounds with lower MSE than comparable baselines; experiments suggest good bounds can be chosen without operator input.
5 Discussion
- OptimizeRC achieves lower MSE than comparable baselines using the same untuned algorithmic choices across experiments.The authors present this as empirical evidence that good sum clipping bounds can be privately chosen without operator input.Source: §5 · p. 12
- Theorem 1 gives sufficient, not necessary, conditions for residual coherence to meet the threshold at C*, and does not establish that the output is near-optimal.Source: §5 · p. 12
- The paper offers evidence that residual coherence is a plausible low-sensitivity proxy for the bias derivative, while identifying better regime characterization or alternatives as open work.Source: §5 · p. 12
- OptimizeRC was not evaluated for DP-SGD because improving it does not cleanly reduce to minimizing gradient-sum MSE.The paper notes that clipping can improve SGD convergence stability and that appropriate clipping is not well understood even without privacy.Source: §5 · p. 12
6 AI Use Disclosure
The authors used Gemini for experiment code and minor proof assistance, while stating that prose was human-written and the AI-assisted work was human-checked.
6 AI Use Disclosure
- Gemini assisted with experiment code and minor Theorem 1 proof mathematics; the authors say all prose and checks of the code and math were human-produced.The authors take responsibility for the work's correctness.Source: §6 · p. 12
A Omitted Methods
The omitted alternatives choose bounds intended to leave most points unclipped, which the authors associate with the difficulties of large fixed-quantile bounds; none beat the three methods discussed in the text.
A Omitted Methods
- ApproxBounds, CoinPress, and CDPHDME each deliberately choose a clipping bound large enough to leave most points unclipped, inheriting fixed-large-quantile problems.Source: A Omitted Methods · p. 16
- ApproxBounds builds a private norm histogram and uses its largest bin above a threshold as the clipping bound, but is empirically dominated by UnboundedQuantile.The passage attributes this in part to the histogram being a less accurate private quantile primitive.Source: A Omitted Methods · p. 16
- CoinPress calibrates clipping to Gaussian tail bounds intended to contain all points, a strategy with no obvious heavy-tailed analogue that effectively uses the maximum norm.The cited experiments generally show HLY-UQ outperforming CoinPress outside well-specified Gaussian data [23].Source: A Omitted Methods · p. 16
- CDPHDME requires an input interval containing the true mean, a kth-moment bound, and n ≫ d for accuracy; its truncated radius also accommodates nearly all points.The authors report that only 4/10 primary datasets have n ≥ 2d, and say the required parameters are not generally clear.Source: A Omitted Methods · p. 16
- The omitted methods never beat the three methods discussed in the text, though user-specified parameters in CoinPress and CDPHDME make untuned comparisons difficult to standardize.Source: A Omitted Methods · p. 16
B Additional Heavy-Tail Plots
The additional plots show residual coherence against clipping bounds and estimated-bound ratios against the optimal C*.
B Additional Heavy-Tail Plots
- Figure 2 plots residual coherence against clipping bounds and marks the OptimizeRC threshold −T; Twitch and Foursquare sit just below it, yielding bound 1.HN, Pantry, and Slashdot show staircase patterns because the small bound range accentuates underlying integer values.Source: Figure 2 · p. 18
- Figure 3 plots estimated clipping bound divided by optimal C*; ratios below 1 indicate underestimation and ratios above 1 indicate overestimation.Source: Figure 3 · p. 19
C Light-Tailed Experiments
On four light-tailed datasets, OptimizeRC’s utility is similar to its heavy-tail performance, while UnboundedQuantile 0.99 and HLY-UQ often perform similarly well. The section also reports occasional cases on NFL where methods beat Optimal because its low dimension increases noise variance.
- The light-tailed experiments cover ANSUR, ATUS, NFL, and Powerlifting, with dataset dimensions ranging from 5 to 132.Source: C Light-Tailed Experiments · p. 20
- On NFL, methods occasionally beat Optimal because the dataset’s low dimension increases noise variance.Source: Figure 4 · p. 20
- OptimizeRC’s utility is similar to the heavy-tail setting, while UnboundedQuantile 0.99 and HLY-UQ often perform similarly well.Source: C Light-Tailed Experiments · p. 20
- Figure 5 presents clipping-bound plots for the light-tailed experiments, as an analogue of Figure 3.Source: Figure 5 · p. 21