Rényi Differential Privacy for Heavy-Tailed SDEs via Fractional Poincaré Inequalities

Benjamin Dupuis, Mert Gürbüzbalaban, Umut Simsekli, Jian Wang, Sinan Yildirim, Lingjiong ZhuarXiv 2025 · DOI · arXiv

Abstract

This paper establishes the first Rényi Differential Privacy (RDP) guarantees for learning algorithms modeled by heavy-tailed Lévy-driven Stochastic Differential Equations (SDEs). By leveraging fractional Poincaré inequalities (FPI), the authors derive privacy bounds that significantly improve upon existing results, particularly regarding their dependence on the model dimension $d$. These findings provide a robust framework for ensuring privacy in modern deep learning settings where noise is often heavy-tailed rather than Gaussian.

What Problem Does This Paper Address?

Differential Privacy (DP) is the standard framework for ensuring that machine learning models do not leak individual training data. Traditionally, DP guarantees rely on the assumption that system noise (e.g., in Stochastic Gradient Descent) is "light-tailed," typically Gaussian. However, recent research indicates that noise in modern deep learning is often heavy-tailed, meaning extreme values are more frequent than a Gaussian distribution predicts.

While heavy-tailed noise can improve generalization, it breaks standard mathematical tools like Logarithmic Sobolev Inequalities used to prove privacy. Previous attempts to address this resulted in weak privacy notions or bounds that "exploded" as the number of parameters (dimension $d$) increased. This paper seeks to provide a dimension-efficient privacy framework for these heavy-tailed settings.

Comparison of existing Differential Privacy guarantees for various algorithms, highlighting the limitations in scaling and assumptions.

Methods

The authors move away from the light-tailed "Gaussian" toolbox and introduce a framework based on Lévy-driven SDEs and fractional calculus. Their key technical contributions include:

  1. Rényi Flow Computations: Deriving how Rényi divergence (a measure of privacy loss) evolves over time for SDEs driven by general Lévy processes.
  2. Fractional Poincaré Inequalities (FPI): Using FPIs to bound "privacy information" flow where standard inequalities fail.
  3. BBM Formula Integration: Utilizing a quantitative version of the Bourgain-Brezis-Mironescu (BBM) formula to bridge fractional and standard derivatives, handling "pure-jump" noise.
  4. Stability Analysis: Proving that these fractional inequalities remain stable after common data operations like convolution or Lipschitz mappings.

Key Insights and Ideas

  • Dimension Independence: In "multifractal" cases (mixed Gaussian and heavy-tailed noise), the authors show that privacy bounds can be completely independent of the dimension $d$, a massive improvement over prior work.
  • The Privacy-Tail Tradeoff: The paper reveals that heavier tails (parameter $\alpha$) are only beneficial for privacy in specific regimes, specifically when the noise scale relative to the dimension is small.
  • Time-Uniformity: By using FPIs, the authors demonstrate that privacy loss does not necessarily grow linearly with training time; under certain conditions, it can stay bounded even for long-running algorithms.

Key Results

The paper provides significantly tighter bounds and more favorable scaling with the number of training samples ($n$) and parameters ($d$) than existing heavy-tailed literature.

Summary of the new Rényi Differential Privacy (RDP) and (0, δ)-DP guarantees established in this work compared to prior state-of-the-art.
  • Multifractal RDP: For SDEs with both Gaussian and $\alpha$-stable noise, they achieved an RDP bound of $\kappa \simeq \mathcal{O}(\beta^2 / n^2)$ under the FPI assumption, independent of dimension $d$.
  • Pure-Jump RDP: In cases with only heavy-tailed noise, they achieved a bound of $\kappa \simeq \mathcal{O}(\beta^2 d^{1-\alpha/2} / n^2)$. While still $d$-dependent, the exponent is much smaller than the previous state-of-the-art ($\mathcal{O}(d^{(1+\alpha)/2})$).

Limitations and Future Work

  • Assumption of FPI: The results rely on the assumption that the model's distribution satisfies a fractional Poincaré inequality. Calculating the exact "Poincaré constant" for complex, non-convex neural networks remains an open problem.
  • Dependence on $\beta^2$: Privacy bounds grow with the square of the Rényi order ($\beta^2$), whereas Gaussian bounds typically grow linearly. This may be an inherent cost of the non-local nature of heavy-tailed noise.
  • Regularity Conditions: The proofs require specific smoothness conditions for probability densities, which may be difficult to verify for complex deep learning architectures.

Future work will focus on improving estimates of fractional Poincaré constants and relaxing regularity conditions to broaden the theory's applicability.

Summary updated

Abstract

Characterizing the differential privacy (DP) of learning algorithms has become a major challenge in recent years. In parallel, many studies suggested investigating the behavior of stochastic gradient descent (SGD) with heavy-tailed noise, both as a model for modern deep learning models and to improve their performance. However, most DP bounds focus on light-tailed noise, where satisfactory guarantees have been obtained but the proposed techniques do not directly extend to the heavy-tailed setting. Recently, the first DP guarantees for heavy-tailed SGD were obtained. These results provide $(0,δ)$-DP guarantees without requiring gradient clipping. Despite casting new light on the link between DP and heavy-tailed algorithms, these results have a strong dependence on the number of parameters and cannot be extended to other DP notions like the well-established Rényi differential privacy (RDP). In this work, we propose to address these limitations by deriving the first RDP guarantees for heavy-tailed SDEs, as well as their discretized counterparts. Our framework is based on new Rényi flow computations and the use of well-established fractional Poincaré inequalities. Under the assumption that such inequalities are satisfied, we obtain DP guarantees that have a much weaker dependence on the dimension compared to prior art.
BibTeX
@misc{dupuis2025renyi,
  author = {Benjamin Dupuis and Mert Gürbüzbalaban and Umut Simsekli and Jian Wang and Sinan Yildirim and Lingjiong Zhu},
  title = {{Rényi Differential Privacy for Heavy-Tailed SDEs via Fractional Poincaré Inequalities}},
  year = {2025},
  eprint = {2511.15634},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.15634},
}
Figure