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.
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:
- 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.
- Fractional Poincaré Inequalities (FPI): Using FPIs to bound "privacy information" flow where standard inequalities fail.
- BBM Formula Integration: Utilizing a quantitative version of the Bourgain-Brezis-Mironescu (BBM) formula to bridge fractional and standard derivatives, handling "pure-jump" noise.
- 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.
- 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