Heavy-Tailed Privacy: The Symmetric alpha-Stable Privacy Mechanism

Christopher C. Zawacki; Eyad H. Abed

REVIEW 4 major objections 5 minor 12 references

Heavy-Tailed Privacy: The Symmetric alpha-Stable Privacy Mechanism

T0 review · 4 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that adding symmetric alpha-stable noise to bounded query answers yields pure ε-differential privacy while keeping the Gaussian mechanism's closure under convolution.

desk verdict Correct core result with real but fixable rigor gaps; worth a serious referee. read the letter →

arxiv 2504.18411 v1 pith:SN2WG3EO submitted 2025-04-25 cs.CR cs.DS

Christopher C. Zawacki , Eyad H. Abed This is my paper · ORCID

classification cs.CRcs.DS MSC 60E0768P27

keywords differentialprivacypuresymmetricalpha-stabledistributionheavy-tailednoisestabledistributionsconvolutionclosurefederatedlearningmeanabsoluteerror

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces the Symmetric alpha-Stable (SaS) privacy mechanism, which perturbs query answers with noise drawn from a symmetric stable distribution with tail parameter α in [1,2). Its central claim is that this mechanism satisfies pure ε-differential privacy, not merely the approximate (ε,δ) guarantee that the Gaussian mechanism provides, while remaining closed under convolution like the Gaussian. If correct, the result gives distributed and federated settings a noise distribution that can be added locally by many clients and still aggregate into the same family with a pure privacy guarantee. The paper also shows that the privacy budget scales inversely with the noise scale and that the mean absolute error can be made nearly equal to the Gaussian's by taking α close to 2.

What carries the argument

The load-bearing object is the symmetric $\alpha$-stable density p_SaS(x;α,γ,μ) defined through its characteristic function φ(t)=exp(-|γt|^α - i t μ) and the integral inversion formula; the mechanism adds independent SaS noise to each query coordinate. The proof machinery consists of two asymptotic expansions of this density due to Bergström: one at infinity showing p(x) ~ -(1/π) Γ(α+1) sin(απ/2) $x^{{-(α+1)}}$, which makes the shifted-density ratio tend to 1 and kills the privacy loss at large |x|, and one near zero used to show that the privacy loss scales as O(Δ1/γ). Bell-shape monotonicity is used to show that the worst case occurs at the extremes of the query range, and the closed Cauchy form (α=1) supplies explicit asymptotic formulas.

What would settle it

For α=1.5, γ=1 and sensitivity Δ=1, evaluate the density ratio p_SaS(x−1;α,γ)/p_SaS(x;α,γ) by high-precision numerical inversion of the characteristic function at |x|=$10^{3}$, $10^{4}$ and $10^{5}$; if the log-ratio does not tend to 0 as |x| grows, the tail argument behind Theorem 16 is wrong, and if the supremum over a nested grid grows without bound, the claimed finite ε does not hold.

Watch

Extended reading notes

Core claim

The paper's central discovery is Theorem 16: for a bounded query f, for any neighboring datasets D1 and D2, and for any stability parameter α∈[1,2), the SaS mechanism satisfies p1(x) ≤ e^ε p2(x) for all outputs x, i.e. pure differential privacy. The argument splits the privacy loss into compact and tail regions; on compact sets, the density is strictly positive and bounded, and in the tail, a series expansion shows the density decays as |x|^{-(α+1)} with a location-independent leading term, so the log-ratio of the two shifted densities tends to 0 as |x|→∞. The paper further claims the level of privacy is governed by the ratio of query sensitivity to noise scale, ε = O(Δ1/γ), and that for α near 2 the mean absolute error is almost identical to the Gaussian's, leading to the conclusion that the SaS mechanism can replace the Gaussian without sacrificing the convolution property or the purity of the guarantee.

Load-bearing premise

The proof rests on the assumption that at very large outputs the two shifted stable densities look identical in their tails, so their ratio approaches 1; that asymptotic scale-independence is asserted in Lemma 15 rather than fully proved, and if it failed the privacy loss could become unbounded and pure DP would collapse.

Editorial extensions

If this is right

In settings that aggregate many local noise additions, the SaS mechanism keeps the Gaussian's advantage: a sum of independent SaS noises is again SaS, so the aggregate mechanism remains in the same family and can still claim the same pure-DP structure.
Choosing α=1.999 gives almost the same expected absolute error as Gaussian noise (about 0.04% larger) while providing a pure privacy guarantee instead of an approximate one.
The privacy budget scales as ~Δ1/γ for large noise scale, matching Laplace; for small scale and α=1 it grows only as O(log(1/γ)), so over-noising is less punishing than for the Laplace mechanism in that regime.
Real-valued queries that currently force a δ term under Gaussian noise can instead be answered with a strict ε bound using SaS noise, at the cost of heavier tails and occasional large perturbations.
The inverse relation between ε and γ carries over: improving privacy (smaller ε) necessarily increases the expected distortion of query answers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The convolution-closure argument suggests a local-DP pipeline: each client adds SaS noise locally, the server averages, and the aggregate noise remains SaS; the paper does not carry out the full composition or shuffling privacy accounting, so the exact ε for the aggregated mechanism is an open computation.
The proof's tail mechanism is generic: any symmetric noise whose shifted densities have matching power-law tails should admit a similar pure-DP argument, which would generalize the mechanism beyond the stable family if such densities remain closed enough for aggregation.
The m-factor bound in the proof is crude for vector queries; numerical optimization of the multidimensional privacy loss could reveal that practical ε budgets are smaller than the paper's worst-case bound, a testable refinement.
As α→2 the SaS privacy loss approaches the unbounded linear loss of the Gaussian, so the practical choice of α is a continuous knob trading purity of the guarantee against tail risk; the paper leaves the optimal choice to application-specific tuning.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The core theorem is true and the paper fills a small but real gap: SaS noise with alpha in [1,2) gives pure epsilon-DP while staying closed under convolution, which neither Laplace nor Gaussian can do alone. The tail-ratio argument in Theorem 16 is the right one and the Cauchy closed form is a nice check. That said, the main theorem is not new — it appeared in the authors' CISS 2024 paper. What this version adds is the closed-form epsilon for alpha=1, the asymptotic O(Delta/gamma) analysis, and the error comparison. Those are useful extensions.

The soft spots are real but mostly cosmetic. Lemma 15's proof as printed has a wrong change of variables: Eq. (27) drops the 1/gamma Jacobian and fails to rescale mu, so the displayed identity is false. The lemma's conclusion is correct and follows directly from the scaling property p(x;gamma,mu)=gamma^{-1} p_1((x-mu)/gamma), so this is a typo-adjacent rigor gap, not a fatal flaw. Lemma 14 is stated for alpha in (1,2] but is cited in Theorem 16 to cover alpha=1; the alpha=1 case is handled later in Theorem 25 via the Cauchy density, so the proof just needs to point there earlier. Theorem 19's geometric argument is informal and not a proof, though it is plausible and consistent with the numerics. Theorem 24 only shows pointwise scaling; the paper honestly acknowledges it cannot get the max without more information. The later claim that epsilon scales like Delta/gamma is only proven for alpha=1 and suggested by numerics for other alpha; that should be labeled as a conjecture.

The least fair part is the conclusion that "there is little reason to use the Gaussian mechanism." That overreaches. Gaussian approximate DP composes better, and for many applications delta is tiny. SaS also has infinite variance, which raises its own utility questions. The paper's own Table 1 shows that for alpha close to 2 the error is nearly identical, so the practical gain is marginal. The right claim is that SaS is a legitimate alternative for settings where pure DP and convolution closure both matter.

Citation pattern looks honest. The self-citation is the predecessor paper, not a hidden dependency. Benchmarks to Nolan and Bergstrom are appropriate.

Verdict: deserving of peer review. The main theorem is correct, the extensions are useful, and the gaps are fixable with a careful revision. A serious referee should engage.

Referee Report

4 major / 5 minor

Summary. The paper introduces the Symmetric alpha-Stable (SaS) mechanism for differential privacy, with stability parameter alpha in [1,2), and claims that it satisfies pure epsilon-DP because the ratio of two shifted SaS densities tends to 1 as |x| tends to infinity. It further claims that the privacy budget scales linearly with the query's ell_1 sensitivity and inversely with the noise scale, provides explicit formulas for alpha = 1, and compares the mean absolute deviation of the mechanism with those of the Laplace and Gaussian mechanisms. The manuscript is an extension of a CISS conference paper and positions the SaS mechanism as combining the convolution closure of the Gaussian family with a pure, rather than approximate, DP guarantee.

Significance. If the central theorem is correct, the paper makes a useful conceptual contribution: stable noise with alpha < 2 is arguably the first commonly used noise family that is simultaneously closed under convolution and satisfies pure differential privacy, which matters for distributed and federated settings. The derivation is self-contained and parameter-free; it relies on classical external results (Nolan 2020, Bergstrom 1952) rather than on fitted constants, and the explicit alpha = 1 bounds together with the expected-distortion comparisons are concrete and reproducible. However, the paper's second contribution, the epsilon proportional to Delta_1/gamma scaling law, is only proved pointwise for general alpha and in closed form for alpha = 1; this is a substantive gap between what is claimed and what is established.

major comments (4)

[Section 4, Lemma 15, Eq. (27)] The displayed substitution in Eq. (27) is incorrect. The correct scaling identity is p(x; alpha, gamma, mu) = gamma^{-1} p((x - mu)/gamma; alpha, 1, 0), so the integral is missing the Jacobian factor 1/gamma and the location parameter must be rescaled to mu/gamma rather than left as mu. The conclusion of the lemma is true, but the printed proof does not establish it; please replace Eq. (27) with the correct identity and re-derive Eqs. (28)-(29) from it.
[Section 4, proof of Theorem 16] Theorem 16 is stated for alpha in [1,2), but the asymptotic argument invokes Lemma 14, which is stated only for alpha in (1,2]. The case alpha = 1 is therefore not covered by the proof as written. Since the alpha = 1 density has the closed Cauchy form, either prove the tail-ratio limit directly for alpha = 1 or cite the computation in Theorem 25 and make explicit that it supplies the missing boundary case.
[Section 5.1, Theorem 19 and its use] The proof of Theorem 19 is an informal geometric argument about shifting bell-shaped curves, and the statement that the distance between the two curves necessarily increases under the shift is asserted rather than derived from Lemma 18. Because Corollary 20, Theorem 21, and the normalized form in Eq. (51) all rely on the maximizer being at the range boundary, this issue is load-bearing. Please provide a rigorous argument (for example, via monotonicity of the likelihood ratio on each side of the modes) or state precisely which additional hypothesis is needed.
[Section 5.1, Theorem 24 and Eq. (41)] Theorem 24 establishes the pointwise bound |L(x)|(gamma) = O(Delta_1/gamma) for each fixed observation x as gamma tends to infinity. It does not prove that max_x |L(x)|(gamma) = O(Delta_1/gamma), which is the quantity identified with epsilon in Eq. (11). The sentence immediately after Theorem 24 acknowledges this limitation, but Eq. (41) and the surrounding text nonetheless assert the scaling law for the mechanism's privacy budget. Please either provide a uniform-in-x argument or explicitly restate the scaling law as a conjecture supported by Figure 8.

minor comments (5)

[Abstract] There is a grammatical error: 'we present and analyze of the Symmetric alpha-Stable mechanism' should read 'we present and analyze the Symmetric alpha-Stable mechanism'.
[Section 5.1, proof of Theorem 24] The proof refers to 'Lemma 19', which does not exist; the reference should be to Theorem 19.
[Section 4, Eq. (27)] The notation x-hat is used before it is defined; please define x-hat = (x - mu)/gamma or an equivalent rescaling.
[Section 2.1, Definition 5] The convention that a mechanism whose supports differ is assigned epsilon = infinity is nonstandard and can conflict with the usual formulation of pure DP on a common support; please clarify this convention.
[Section 5, Figure 8] The numerical claim that the maximum privacy loss falls off at the same rate as the Laplace mechanism is presented without confidence intervals or a fitted slope; adding the fitted asymptotic slope or an error measure would make the claim more transparent.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the pure-DP proof is anchored in external stable-distribution expansions; the single self-citation is a non-load-bearing predecessor.

full rationale

Walking the derivation chain: the SaS mechanism is defined in Definition 12 from the stable family, and Theorem 16 proves pure DP by combining Lemma 13 (support on R, cited from Nolan), a Gamma-integral boundedness argument on compact sets, and the tail asymptotics of Lemma 14 (cited from Bergström) together with Lemma 15 to remove scale dependence. These are external mathematical inputs, not fitted quantities. No parameter is estimated from data: α and γ are design choices, and the theorem is parameter-uniform. The scaling results in Section 5 (Theorems 19, 21, 24, 25) are obtained by change of variables, by an external bell-shape theorem, by Bergström's small-argument expansion, and by the closed-form Cauchy density; none of these reduce to the paper's own conclusions by construction. The error analysis in Section 6 uses strict stability from the characteristic function and Nolan's external mean-absolute-deviation formula, which is independent support. The only self-citation, Zawacki and Abed (2024), appears in the introduction as a predecessor ('extends the initial results') and is not used as a proof ingredient. There is no fitted input renamed as a prediction and no self-citation chain carrying the central claim. Two rigor gaps should be flagged but they are not circularity: Lemma 15's displayed Eq. (27) omits the 1/γ Jacobian and does not rescale μ, so the printed identity p(x;α,γ,μ)=p(x_hat;α,1,μ) is false as written; the lemma's conclusion is nevertheless correct after the proper substitution, so Theorem 16's tail argument is repairable. Also, Theorem 16 claims α∈[1,2) but invokes Lemma 14, which is stated only for α∈(1,2]; the α=1 endpoint should be handled by the Cauchy computation in Theorem 25. These are proof-coverage issues, not circular reductions. Consequently the appropriate circularity score is 1.0: a minor non-load-bearing self-citation with an otherwise self-contained derivation.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The analysis relies entirely on established properties of stable distributions and standard DP definitions. No free parameters are fitted to data: alpha and gamma are design choices of the mechanism. No new entities are introduced; the SaS mechanism is a method, not a new physical or mathematical object.

assumptions (4)

standard math The symmetric alpha-stable density has support on the entire real line for alpha in [1,2] (Nolan, Lemma 1.1).
Invoked in Lemma 13 to ensure the denominator of the privacy loss never vanishes, a necessary condition for bounded privacy loss.
standard math The Bergstrom finite series expansions characterize the tail and near-zero behavior of SaS densities.
Used in Lemmas 14 and 23 to bound the privacy loss at |x| to infinity and near 0; the tail exponent alpha+1 drives the ratio of shifted densities to 1.
standard math Stable densities are bell-shaped, so their first derivative changes sign exactly once (Kwasnicki 2020).
Used in Lemma 18 to establish monotonicity, which underpins the boundary-maximization argument in Theorem 19.
domain assumption The query is bounded and has finite l1 sensitivity, and the noise is symmetric with alpha restricted to [1,2).
The mechanism is defined only for this parameter range; the proofs of scaling and error rely on finite mean and the tail behavior in this range.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Heavy-Tailed Privacy: The Symmetric alpha-Stable Privacy Mechanism." pith.science (2026). https://pith.science/paper/SN2WG3EO

@misc{pith2026250418411,
  author       = {Pith},
  title        = {Pith review of: Heavy-Tailed Privacy: The Symmetric alpha-Stable Privacy Mechanism},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SN2WG3EO}},
  note         = {Machine review of arXiv:2504.18411}
}

read the original abstract

With the rapid growth of digital platforms, there is increasing apprehension about how personal data is collected, stored, and used by various entities. These concerns arise from the increasing frequency of data breaches, cyber-attacks, and misuse of personal information for targeted advertising and surveillance. To address these matters, Differential Privacy (DP) has emerged as a prominent tool for quantifying a digital system's level of protection. The Gaussian mechanism is commonly used because the Gaussian density is closed under convolution, and is a common method utilized when aggregating datasets. However, the Gaussian mechanism only satisfies an approximate form of Differential Privacy. In this work, we present and analyze of the Symmetric alpha-Stable (SaS) mechanism. We prove that the mechanism achieves pure differential privacy while remaining closed under convolution. Additionally, we study the nuanced relationship between the level of privacy achieved and the parameters of the density. Lastly, we compare the expected error introduced to dataset queries by the Gaussian and SaS mechanisms. From our analysis, we believe the SaS Mechanism is an appealing choice for privacy-focused applications.

Figures

Figures reproduced from arXiv: 2504.18411 by the authors.

**Figure 2.** Pure-Differential Privacy limits the amount of information an adversary can gain from the outcome [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** The family of Symmetric alpha-Stable densities consists of bell shaped densities with varying tail [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Figures from the paper (7 more)

**Figure 4.** Figure 4: The real part of the integrand of (22) for [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]

**Figure 5.** Figure 5: Consider two bell curves, shown here as p1 in blue and p2 in orange, with location parameters µ1 > µ2 respectively. Given a point x ∗ > µ1, denote by d the distance between the curves at x ∗ : d := p1(x ∗ ) − p2(x ∗ ). Shifting the distribution p1 to the right by some …

**Figure 6.** Figure 6: Denote by L(x; α, γ = 1) the privacy loss of the SaS mechanism with unit scale over observations x. Without loss of generality, let D1 and D2 be neighboring datasets such that the privacy loss of the Gaussian mechanism is linear: L(x; 2, 1) = x shown in black. As the s…

**Figure 7.** Figure 7: Denote by L(x; α = 1.5, γ) the privacy loss of the SaS mechanism with stability parameter α = 1.5 over observations x. Without loss of generality, let D1 and D2 be neighboring datasets such that the privacy loss is symmetric about the origin. As the scale γ of the dens…

**Figure 8.** Figure 8: The maximum privacy loss of the Laplace mechanism is inversely related to the scale of the [PITH_FULL_IMAGE:figures/full_fig_p023_8.png]

**Figure 9.** Figure 9: The privacy loss ε for the SaS mechanism, with α = 1 and ∆1 = 1, over a range of scale values γ described by (73) and shown here in orange. For small γ, the privacy loss is approximated by Eq. (95) in green, and, for large γ, the privacy loss is approximated by Eq. (91…

**Figure 10.** Figure 10: The Gamma function Γ(x) achieves a minimum value in the right hand plane at x ≈ 1.462. When α is bounded between [1, 2), the Gamma component of the injected error takes input values in [0, 0.5). The Gamma function is monotonically decreasing in this interval from ∞ to…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 8 canonical work pages

[1]

Abadi, A

M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC con- ference on computer and communications security , pages 308–318,

work page 2016
[9]

org/abs/1602.05629

URL http://arxiv. org/abs/1602.05629. F. McSherry and K. Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07) , pages 94–103. IEEE,

arXiv
[2006]

Springer, 2006a

Proceedings 25, pages 486–503. Springer, 2006a. C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Confer- ence, TCC 2006, New York, NY, USA, March 4-7,

work page 2006
[2011]

47 CFR § 8.1(a) 2011,

work page 2011
[2014]

Dwork, K

C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology-EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic 29 Zawacki and Abed Techniques, St. Petersburg, Russia, May 28-June 1,

work page 2006
[2015]

2021 annual data breach report, Apr

Id-Theft-Center. 2021 annual data breach report, Apr

work page 2021
[2016]

H. Asi, D. Liu, and K. Tian. Private stochastic convex optimization with heavy tails: Near-optimality from simple reductions. arXiv preprint arXiv:2406.02789 ,

arXiv
[2020]

Zawacki and Eyad H

Christopher C. Zawacki and Eyad H. Abed. The symmetric alpha-stable privacy mechanism. In 2024 58th Annual Conference on Information Sciences and Systems (CISS), pages 1–6,

work page 2024

Show all 12 references

[2021]

URL https://www.singular.net/blog/ limit-ad-tracking-privacy-checkup-in-2020/ . M. Kwa´ snicki. A new class of bell-shaped functions. Transactions of the American Mathe- matical Society, 373(4):2255–2280,

2020
[2022]

idtheftcenter.org/publication/2021-annual-data-breach-report-2/

URL https://www. idtheftcenter.org/publication/2021-annual-data-breach-report-2/ . K. Ito, Y. Kawano, and K. Kashima. Privacy protection with heavy-tailed noise for linear dynamical systems. Automatica, 131:109732,

2021
[2023]

30 The Symmetric alpha-Stable Privacy Mechanism U

Published electronically at http://oeis.org. 30 The Symmetric alpha-Stable Privacy Mechanism U. S ¸im¸ sekli, M. G¨ urb¨ uzbalaban, S. Yıldırım, and L. Zhu. Differential privacy of noisy (s) gd under heavy-tailed perturbations. arXiv preprint arXiv:2403.02051 ,

arXiv
[2024]

doi: 10.1109/CISS59072.2024.10480198. 31

2024

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

Abadi, A

M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC con- ference on computer and communications security , pages 308–318,

work page 2016

[2] [9]

org/abs/1602.05629

URL http://arxiv. org/abs/1602.05629. F. McSherry and K. Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07) , pages 94–103. IEEE,

arXiv

[3] [2006]

Springer, 2006a

Proceedings 25, pages 486–503. Springer, 2006a. C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Confer- ence, TCC 2006, New York, NY, USA, March 4-7,

work page 2006

[4] [2011]

47 CFR § 8.1(a) 2011,

work page 2011

[5] [2014]

Dwork, K

C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology-EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic 29 Zawacki and Abed Techniques, St. Petersburg, Russia, May 28-June 1,

work page 2006

[6] [2015]

2021 annual data breach report, Apr

Id-Theft-Center. 2021 annual data breach report, Apr

work page 2021

[7] [2016]

H. Asi, D. Liu, and K. Tian. Private stochastic convex optimization with heavy tails: Near-optimality from simple reductions. arXiv preprint arXiv:2406.02789 ,

arXiv

[8] [2020]

Zawacki and Eyad H

Christopher C. Zawacki and Eyad H. Abed. The symmetric alpha-stable privacy mechanism. In 2024 58th Annual Conference on Information Sciences and Systems (CISS), pages 1–6,

work page 2024