PaperlayerView exact revision on arXiv

Source-linked AI summary

Renyi Differential Privacy

Ilya Mironov

arXiv:1702.07476v3cs.CR

TL;DR

The paper addresses limitations of (ε, δ)-differential privacy in representing Gaussian mechanisms and composing heterogeneous mechanisms. It proposes Rényi differential privacy, based on Rényi divergence, and shows that it tracks privacy loss through additive RDP curves while offering simpler and stronger bounds than (ε, δ)-DP for sufficiently small probabilities.

  • Problem

    (ε, δ)-differential privacy is an imperfect fit for Gaussian mechanisms and composition, and its δ term can obscure materially different privacy-failure modes.

  • Method

    The paper proposes Rényi differential privacy as a privacy definition based on Rényi divergence for representing privacy-loss tails and composing heterogeneous mechanisms.

  • Results

    RDP curves for composed mechanisms simply add, while analysis via RDP is simpler and especially yields stronger bounds than (ε, δ)-DP for probabilities smaller than δ.

  • Takeaways & Limitations

    RDP restores a privacy-budget interpretation while retaining useful differential-privacy properties and supporting tighter analysis of composite mechanisms.

  • Takeaways & Limitations

    RDP bounds weaken for less likely outcomes, so assessing whether increased risk is tolerable requires estimating the baseline risk first.

Abstract

from arXiv · show

We propose a natural relaxation of differential privacy based on the Renyi divergence. Closely related notions have appeared in several recent papers that analyzed composition of differentially private mechanisms. We argue that the useful analytical tool can be used as a privacy definition, compactly and accurately representing guarantees on the tails of the privacy loss. We demonstrate that the new definition shares many important properties with the standard definition of differential privacy, while additionally allowing tighter analysis of composite heterogeneous mechanisms.

I. INTRODUCTION

The paper identifies limitations of (ε, δ)-differential privacy for Gaussian mechanisms and composition, then proposes Rényi differential privacy as a more accurate and composable relaxation.

  • Motivation: (ε, δ)-differential privacy is an imperfect fit for Gaussian mechanisms and composition, its two most common use cases.The paper highlights limitations in representing Gaussian privacy guarantees and in repeatedly applying advanced composition.
  • Gaussian mechanism: A Gaussian mechanism satisfies a continuum of incomparable (ε(δ), δ)-guarantees, so selecting one point omits information about its behavior.This contrasts with the tighter characterization available for the Laplace mechanism under pure ε-differential privacy.
  • Composition: Advanced composition tightens analyses but repeated application quickly causes a combinatorial explosion of parameters.Pure ε-differential privacy has additive composition, whereas relaxed guarantees introduce multiple ε and δ choices.
  • Proposed definition: Rényi differential privacy is proposed as a natural relaxation suited to privacy guarantees and composition of heterogeneous mechanisms.The paper presents it as an operationally convenient way to track cumulative privacy loss.
  • Background: The standard definitions depend on adjacent inputs, typically differing in one individual’s contribution to the mechanism input.The paper also recalls pure ε-DP, (ε, δ)-DP, and the Laplace mechanism as foundational comparison points.
  • Limitations of (ε, δ)-DP: The (ε, δ)-DP relaxation can obscure whether its δ probability represents gradual degradation or complete exposure of a secret.The paper notes that choosing δ ≪ 1/N or δ = negl(1/N) avoids one worst-case pattern but does not eliminate other leakage.
  • Gaussian mechanism: The Gaussian mechanism remains attractive because Gaussian noise composes under addition, follows ℓ2 sensitivity, and has faster-decaying tails than Laplace noise.These properties motivate seeking a privacy definition better matched to Gaussian mechanisms.

III. R´ENYI DIFFERENTIAL PRIVACY

RDP generalizes differential privacy through Rényi divergence, preserving several core privacy properties while representing privacy loss probabilistically and supporting adaptive composition.

  • Definition and motivation: RDP is introduced as a differential-privacy relaxation based on Rényi divergence, with a systematic analysis of its relationship to existing notions.The paper positions this relationship as extending earlier work focused mainly on the Kullback–Leibler endpoint.
  • Definition and motivation: A finite RDP guarantee imposes a support condition: feasible outputs for one input are feasible for all inputs except on a measure-zero set.The event space is taken to be the support of the distribution under this assumption.
  • Definition and motivation: RDP uses orders α greater than 1; Rényi divergence itself also admits orders below 1, including negative orders, which the definition does not use.The paper defines the divergence for α > 1 and identifies its α = 1 limit with Kullback–Leibler divergence.
  • Privacy guarantees: RDP relaxes the bad-outcomes guarantee into a probabilistic statement about changes in the Bayes factor rather than a pointwise bound everywhere.For pure differential privacy, the log posterior-to-prior odds change is bounded by ε everywhere; RDP bounds moments and yields an expectation-based comparison.
  • Privacy guarantees: RDP is preserved under post-processing because Rényi divergence decreases under randomized mappings.Thus applying any randomized mapping to an RDP mechanism retains the same (α, ε) guarantee.
  • Composition and group privacy: Two RDP mechanisms compose adaptively with additive privacy parameters, yielding (α, ε1 + ε2)-RDP even when releases are coordinated or use different dataset versions.This supports a finite privacy budget consumed by each release and a budget curve indexed by α.
  • Composition and group privacy: For a 2c-stable transformation and α ≥ 2c+1, an (α, ε)-RDP mechanism becomes (α/2c, 3cε)-RDP after composition.This is the paper’s RDP analogue of group privacy under c-stable transformations.

IV. RDP AND (ǫ, δ)-DP

RDP connects directly to standard differential privacy: pure ε-DP is the infinite-order case, while finite-order RDP converts to (ε, δ)-DP with an explicit δ-dependent penalty.

  • Pure ε-differential privacy is equivalent to (∞, ε)-RDP, and monotonicity implies (α, ε)-RDP for every finite α.
  • An (α, ε)-RDP guarantee implies (ε + log(1/δ)/(α−1), δ)-differential privacy for any 0 < δ < 1.The conversion is stated as Proposition 3 and provides an explicit tradeoff between order, RDP cost, and δ.

V. ADVANCED COMPOSITION THEOREM

The paper derives advanced-composition guarantees directly from RDP curves, including event-dependent probability bounds and a conventional (ε, δ) corollary in the high-privacy regime.

  • RDP curves of composite mechanisms support non-trivial privacy conclusions analogous to advanced composition theorems, without explicit probability arguments.
  • The resulting guarantee bounds probability gain as a function of the event’s probability, rather than using a fixed bound independent of the event.
  • For n ε-differentially private mechanisms and log(1/δ) ≥ ε^2n, the paper gives a conventional (ε′, δ)-DP advanced-composition bound.
  • The condition log(1/δ) ≥ ε^2n corresponds to the high-privacy regime, where ε′ is bounded relative to log(1/δ).The text notes that for δ below 1%, this covers ε′ < 11.

VI. BASIC MECHANISMS

The paper analyzes RDP for randomized response, Laplace noise, Gaussian noise, and their self-compositions, summarizing results in a table and figures.

  • RDP analysis covers randomized response, Laplace noise addition, Gaussian noise addition, and self-composition of these mechanisms.The results are summarized in Table II and plotted for selected parameters in Figures 1 and 2.

A. Randomized response

The paper defines randomized response for a predicate and states its RDP guarantee via direct application of the RDP definition.

  • Randomized response outputs f(D) with probability p and 1−f(D) with probability 1−p.
  • Proposition 5 states the RDP guarantee satisfied by the randomized response mechanism RRp(f).

B. Laplace noise

The Laplace section assumes a sensitivity-1 real-valued function, defines additive Laplace noise, and derives its RDP guarantee from Rényi divergence between shifted Laplace distributions.

  • The analysis assumes f is real-valued with sensitivity 1, meaning adjacent inputs change f by at most 1.
  • The Laplace mechanism adds noise from a Laplace distribution with mean µ and scale λ.
  • The RDP budget curve is derived by computing Rényi divergence for a Laplace distribution and its offset.
  • Because the mechanism is additive, the divergence depends only on α and the distance between function outputs on adjacent inputs.
  • Corollary 2 gives the RDP guarantee for the Laplace mechanism applied to a sensitivity-1 function.
  • The α→1 limit is 1/λ + exp(−1/λ) −1, approximately .5/λ2.

C. Gaussian noise

The Gaussian section defines additive Gaussian noise, computes the Rényi divergence between shifted Gaussian distributions, and obtains a closed-form RDP guarantee with a simple compositional interpretation.

  • The Gaussian mechanism approximates a real-valued function by adding a normally distributed random variable with mean 0 and standard deviation σ2.
  • The section derives a closed-form expression for the Rényi divergence between a Gaussian distribution and its offset.
  • Corollary 3 states that a sensitivity-1 Gaussian mechanism Gσ f satisfies (α, α/(2σ2))-RDP.
  • The Gaussian mechanism’s RDP budget curve is a straight line, and adaptive composition adds the mechanisms’ budget curves.

D. Privacy of basic mechanisms under composition

The paper interprets RDP bounds through changes in event probabilities and compares RDP-based analyses with standard composition bounds for self-composed randomized response and Laplace mechanisms.

  • RDP bounds relate probabilities of the same outcome under mechanism runs on adjacent inputs, with the bound depending on the event’s initial probability.
  • For most parameters, the more involved RDP analysis produces tighter bounds on probability increases.
  • Figure 2 compares four analyses across self-compositions of randomized response and Laplace mechanisms for initial event probabilities 10−6, 10−3, and 10−1.
  • The naïve nε composition bound is very pessimistic except for a handful of parameters.
  • The RDP-specific analysis is tighter than generic bounds using only the mechanism’s differential privacy parameter for both mechanisms.
  • The paper’s Proposition 4 advanced-composition bound is consistently outperformed by the standard (ε, δ) composition theorem with optimally chosen δ.

VII. DISCUSSION

R´enyi differential privacy preserves key privacy properties while offering direct tail guarantees, simpler analysis than (ǫ, δ)-DP, and additive composition for heterogeneous mechanisms.

  • Probabilistic privacy guarantee: R´enyi differential privacy prevents a total privacy breach, retaining residual uncertainty even with very weak parameters.This assurance is quantified through bounds on posterior-odds increases.
  • Probabilistic privacy guarantee: For an (α, ǫ)-RDP mechanism, posterior odds increase by more than β with probability below e^ǫ/β^(1/(α−1)); for α = 2, this decays as O(1/β).The bound applies for α > 1 and arbitrary priors.
  • Baseline-dependent guarantees: RDP bounds become weaker for rarer outcomes, requiring baseline-risk estimates to determine whether increased risk is tolerable.For a (10.0, .1)-RDP mechanism, a baseline event probability of 10−6 can change to [.195 · 10−6, 4.36 · 10−6].
  • Baseline-dependent guarantees: Compared with (ǫ, δ)-DP, RDP analysis is simpler and yields stronger bounds especially when event probabilities are smaller than δ.Optimizing the implicit ǫ-δ tradeoff in (ǫ, δ)-DP can be non-trivial, particularly in closed form.
  • Keeping track of accumulated privacy loss: RDP curves for composed mechanisms add directly without changing their α values, preserving a privacy-budget abstraction for heterogeneous compositions.This composition rule also retains sublinear privacy loss as the number of queries grows.
  • Keeping track of accumulated privacy loss: In a mixed iterative mechanism, bounds using an optimal α and 13 restricted α values are nearly identical across up to 100 iterations.The mechanism combines randomized response, Laplace, and Gaussian noise, with baseline risks .1, .001, and 10−6.

VIII. CONCLUSIONS AND OPEN QUESTIONS

The paper presents RDP as a natural generalization of pure differential privacy with simple Gaussian analysis and composition that preserves aggregate privacy information. It also identifies unresolved questions about tightness and probability-preservation bounds.

  • RDP is a natural generalization of pure differential privacy.
  • RDP shares, with adaptations, many properties that make differential privacy useful and versatile.
  • RDP analysis of Gaussian noise is particularly simple.
  • A composition theorem based solely on RDP enables analysis of composite mechanisms without considering their components.
  • Sampling an RDP curve at a few consistently chosen points can estimate aggregate privacy loss across multiple mechanisms.
  • Formal bounds on the tightness of RDP guarantees from selected α values remain an open direction, and probability preservation is not tight as Dα(P∥Q) →0.

APPENDIX

The appendix recalls and reproves core properties of Rényi divergence used in the paper, including non-negativity, monotonicity, probability preservation, and a weak triangle inequality. It emphasizes choosing divergence orders carefully because bounds can vary nonmonotonically with α.

  • The appendix reintroduces non-negativity, monotonicity, probability preservation, and a weak triangle inequality for Rényi divergence.
  • The appendix includes Jensen-inequality and continuity arguments for non-negativity and monotonicity, and records probability preservation as Proposition 10.
  • Hölder’s inequality supplies the proof strategy for the weak triangle inequality and related results.
  • As α approaches 1, Rényi divergence shrinks while the exponent tends to zero, so bounds may depend nonmonotonically on α.
  • Rényi divergence is generally neither symmetric nor subject to the triangle inequality, but a weaker inequality relates different divergence orders.
  • The weak triangle inequality yields several special cases by fixing or taking limits of the auxiliary parameters p and q.
Loading 1702.07476v3…