PaperlayerView exact revision on arXiv

Source-linked AI summary

Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds

Mark Bun, Thomas Steinke

arXiv:1605.02065v1cs.CRcs.DScs.ITcs.LG

TL;DR

The paper addresses the difficulty of analyzing composition under approximate differential privacy by reformulating concentrated differential privacy through Rényi divergence. It introduces zCDP, derives sharper analyses and lower bounds, and extends the framework to approximate zCDP. The paper also identifies scope boundaries, including the need for further study of concentrated differential privacy mechanisms and sample complexity.

  • Problem

    Approximate differential privacy has unwieldy composition bounds that can be computationally hard to optimize and non-tight even for simple Gaussian mechanisms.

  • Method

    The paper defines zero-concentrated differential privacy using Rényi divergence between outputs on neighboring inputs and extends it with approximate zCDP.

  • Results

    The reformulation permits sharper analyses of basic computations, including a tight Gaussian-mechanism analysis, while supporting lower bounds and composition with approximate differential privacy.

  • Takeaways & Limitations

    zCDP supplies a unified privacy-analysis framework with strong composition and lower-bound tools, while approximate zCDP accommodates stability-based techniques.

  • Takeaways & Limitations

    The paper leaves open whether concentrated differential privacy has a complete mechanism and a simple sample-complexity characterization; its lower bounds apply to specified mechanism paradigms.

Abstract

from arXiv · show

"Concentrated differential privacy" was recently introduced by Dwork and Rothblum as a relaxation of differential privacy, which permits sharper analyses of many privacy-preserving computations. We present an alternative formulation of the concept of concentrated differential privacy in terms of the Renyi divergence between the distributions obtained by running an algorithm on neighboring inputs. With this reformulation in hand, we prove sharper quantitative results, establish lower bounds, and raise a few new questions. We also unify this approach with approximate differential privacy by giving an appropriate definition of "approximate concentrated differential privacy."

1 Introduction

The paper reformulates concentrated differential privacy using Rényi divergence, yielding zCDP with strong composition, postprocessing, Gaussian-mechanism, and lower-bound results. It also relates zCDP to differential privacy and introduces an approximate variant that retains key properties while accommodating stability-based techniques.

  • Motivation: Approximate differential privacy has unwieldy and sometimes non-tight composition bounds, motivating a sharper abstraction for privacy-preserving computation.Computing the tightest guarantee for arbitrary heterogeneous mechanisms is #P-hard, and advanced composition is not tight even for independent Gaussian noise.
  • Reformulation: Rényi divergence provides the basis for zero-concentrated differential privacy (zCDP), an alternative formulation of concentrated differential privacy distinct from mean-concentrated differential privacy (mCDP).The formulation captures the requirement that the privacy loss random variable is subgaussian.
  • Relationship to differential privacy: For every δ > 0, ρ-zCDP implies (ρ + 2√(ρ log(1/δ)), δ)-differential privacy, with a partial converse up to parameter loss.The paper positions zCDP between pure and approximate differential privacy; pure differential privacy also implies zCDP with transformed parameters.
  • Gaussian mechanism: The Gaussian mechanism satisfies (∆^2/2σ^2)-zCDP, and the defining zCDP inequalities are exactly tight for it across all Rényi orders.This tightness indicates that the definition is particularly well matched to Gaussian noise.
  • Basic properties: zCDP composes additively and is invariant under postprocessing, preserving key modular properties of differential privacy.Mechanisms satisfying ρ-zCDP and ρ′-zCDP compose to (ρ + ρ′)-zCDP, while postprocessing preserves ρ-zCDP.
  • Lower bounds: zCDP yields exact quadratic group-privacy scaling and information-based lower bounds, including n = Θ(√log k) for accurate histograms over domain size k.These bounds separate zCDP from approximate differential privacy, where the histogram sample size can be independent of k, and imply a quadratic sample-complexity conversion to pure differential privacy for statistical queries.
  • Approximate zCDP: Approximate zCDP unifies zCDP with approximate differential privacy while retaining most desirable zCDP properties and allowing stability-based techniques to bypass the stated lower bounds.The paper also identifies a one-parameter ρ-zCDP formulation as sufficient for most purposes.

1.3 Related Work

The paper recasts concentrated differential privacy through zCDP, a Rényi-divergence formulation that is generally easier to use than mCDP. It develops tighter bounds and lower bounds, while identifying open questions about CDP’s scope and interpretation.

  • Alternative formulation: zCDP uses Rényi divergence to formulate concentrated differential privacy, while mCDP is the terminology used for Dwork and Rothblum’s definition.Both definitions formalize the same underlying concept, but zCDP directly captures privacy-loss concentration around zero.
  • Alternative formulation: The zCDP formulation generally simplifies analyses compared with mCDP, and some resulting bounds are sharper.The paper also studies lower bounds, which Dwork and Rothblum did not explore.
  • Motivation: CDP is presented as a useful framework for obtaining simpler and tighter bounds in private-computation analysis.The authors hope it will prove useful in both differential-privacy theory and practice.
  • Scope and lower bounds: Lower bounds show that CDP can be substantially more stringent than approximate differential privacy, forming a subclass that excludes some propose-test-release algorithms.The excluded algorithms exploit low local sensitivity.
  • Further work: Open questions include whether CDP has a complete mechanism, how much sample complexity it requires, and how strongly ρ-zCDP improves on its implied (ε, δ)-DP guarantees.The lower bounds apply to algorithms built from several standard mechanisms and techniques with composition and postprocessing.

2 R´enyi Divergence

This section introduces Rényi divergence and records the properties used to analyze zCDP. These tools yield composition and postprocessing rules and characterize the Gaussian mechanism’s zCDP guarantee.

  • Definition: Rényi divergence Dα(P∥Q) is defined for probability distributions P and Q and order α ∈ (1, ∞), with KL divergence treated separately.The definition uses probability mass or density functions, or the Radon-Nikodym derivative.
  • Definition: Rényi divergence can also be expressed through the privacy-loss random variable, with D1(P∥Q) equal to its expected privacy loss.This connects the divergence formulation to privacy-loss analysis.
  • Properties: For product distributions, Rényi divergence equals the sum of the divergences of the marginals.This additive property supports composition analyses.
  • Properties: Rényi divergence is nonnegative, quasi-convex under mixtures, and nonincreasing under postprocessing, including randomized mappings.Non-negativity is equality-only when the two distributions coincide.
  • Composition and postprocessing: Sequential composition of (ξ, ρ)-zCDP and (ξ′, ρ′)-zCDP mechanisms gives (ξ+ξ′, ρ+ρ′)-zCDP, and the result extends inductively to arbitrarily many mechanisms.The second mechanism may depend on the first mechanism’s output.
  • Gaussian mechanism: A Gaussian mechanism releasing N(q(x), σ^2I_d) satisfies ρ-zCDP according to the query’s sensitivity and noise variance.The result follows from the Rényi divergence between equal-variance Gaussian distributions.

3 Relation to Differential Privacy

The paper relates zCDP to pure and approximate differential privacy through exact and approximate conversions. It shows that zCDP corresponds, up to parameter loss, to a family of (ε, δ)-DP guarantees for every δ > 0.

  • Pure DP: Pure ε-differential privacy is exactly equivalent to (ε, 0)-zCDP.The equivalence holds in both directions for mechanisms on neighboring inputs.
  • Pure DP: For distributions with max-divergence at most ε in both directions, the paper bounds Rényi divergence and sharpens the corresponding KL-divergence bound.The KL bound is an important ingredient in advanced-composition analysis.
  • Approximate DP: A partial converse shows that zCDP and differential privacy with guarantees quantified over all δ > 0 are equivalent up to parameter loss.The loss may be potentially substantial.
  • Approximate DP: zCDP implies (ε, δ)-DP for every δ > 0, with ε determined by the zCDP parameters and log(1/δ).The paper also proves a slight strengthening of this conversion.
  • Approximate DP: The conversion from zCDP to approximate DP is derived by applying Rényi-divergence control to the privacy-loss random variable.The analysis bounds the probability that privacy loss exceeds ε.

4 Zero- versus Mean-Concentrated Differential Privacy

The paper compares zCDP with mean-concentrated differential privacy, showing parameter conversions in both directions. It treats zCDP as a weaker, more directly centered formulation, while noting losses in round-trip conversion.

  • Parameter conversions: A (µ, τ)-mCDP mechanism satisfies (µ−τ^2/2, τ^2/2)-zCDP.The paper states this conversion as Lemma 4.2.
  • Parameter conversions: A (ξ, ρ)-zCDP mechanism satisfies (ξ + ρ, O(√ξ + 2ρ))-mCDP.This provides a partial converse from zCDP to mCDP.
  • Parameter conversions: Converting mCDP to zCDP and back can cause a large parameter loss, so pure DP is characterizable through zCDP but not through mCDP.The round-trip conversion returns an mCDP guarantee with altered parameters.
  • Conceptual comparison: mCDP bounds privacy loss around its mean, whereas zCDP directly gives a subgaussian bound centered at zero.The distinction reflects tight versus weak concentration of privacy loss.
  • Scope: The stronger mCDP requirement may offer advantages for privacy guarantees or analysis, but the authors suggest zCDP suffices for most applications.This is presented as a qualified comparison rather than a definitive dominance claim.

5 Group Privacy

The paper extends zCDP from individual privacy to groups, obtaining an exactly tight dependence on the quadratic parameter and a near-linear dependence on the mean parameter. These guarantees follow from a triangle-like inequality for Rényi divergence.

  • Definition: zCDP for groups of size k is defined by requiring the Rényi-divergence bound for every pair of databases differing in at most k entries.This extends the usual size-one definition to larger groups.
  • Proof strategy: The group-privacy proof uses a triangle-like inequality for Rényi divergence together with induction on the group size.The induction changes one entry at a time and applies the technical inequality to accumulate the bound.
  • Guarantee: (ξ · O(k log k), ρ · k^2)-zCDP is guaranteed for groups of size k.This is the main group-privacy bound established by Proposition 5.3.
  • Tightness: The ρ · k^2 dependence is optimal, while the ξ dependence can be improved from O(k log k)ξ to kξ when ξ = 0.The Gaussian mechanism witnesses optimality for the quadratic ρ dependence.

6 Lower Bounds

The paper develops information-theoretic lower bounds for zCDP by combining group privacy with mutual information. These bounds yield sample-complexity limits for several tasks and expose a separation from approximate differential privacy.

  • Framework: The lower-bound method constructs input distributions for which accuracy requires revealing substantial information, then contradicts the mutual-information bound imposed by zCDP.Group privacy supplies the privacy-to-information bound used in this argument.
  • Information bounds: For independent inputs, zCDP bounds mutual information through the parameters ξ and ρ, with the basic n-entry bound scaling as ξ · n(1 + log n) + ρ · n^2.The paper also develops stronger bounds for independent entries and grouped independent blocks.
  • Role of group privacy: Strong group privacy makes these lower bounds possible even for groups of size n, whereas approximate differential privacy becomes vacuous for groups of size k = O(log(1/δ)/ε).The contrast explains why the same lower-bound strategy does not apply to approximate DP.
  • Applications: For one-way marginals, Gaussian noise gives accuracy when n ≫ d/ρ, while the lower bound n ≥ Ω(d/ρ) is tight up to constant factors.The lower-bound construction repeats one uniformly random d-bit vector across all database entries.
  • Applications: For the repeated-symbol identification problem, zCDP requires n = Θ(log(T)/ρ) samples for accuracy, establishing a separation from approximate DP.The lower and upper bounds match in the stated dependence on log(T)/ρ.
  • Applications: For randomized response, independent bits achieve expected correlation Θ(nε), while accurate mechanisms reveal Ω(n) information under a ρ-zCDP constraint.The lower bound follows by comparing the information required for accuracy with the independent-input mutual-information bound.

7 Obtaining Pure DP Mechanisms from zCDP

The paper shows that zCDP mechanisms for statistical queries can be converted into pure-DP mechanisms, using packing, nets, the exponential mechanism, and an information-based lower bound. The conversion requires at most a quadratic sample-complexity blowup in the stated constant-parameter regime.

  • Main theorem: Any zCDP mechanism for statistical queries can be converted into a pure-DP mechanism with at most a quadratic blowup in sample complexity.The theorem establishes this as a limit on how much more zCDP can achieve than pure DP.
  • Scope: The conversion theorem applies only to families of statistical queries, although it supports both ℓ∞ and ℓ1 error bounds.This is the stated scope limitation of the theorem.
  • Quantitative consequence: For ξ = 0 and constant ρ, ε, and α, the resulting pure-DP sample complexity is n′ = O(n^2).The general expression in the cited passage is n′ = O(n^2ρ/εα).
  • Proof strategy: The proof is nonconstructive: it converts pure-DP lower bounds into zCDP lower bounds rather than directly constructing a pure-DP mechanism from the original zCDP mechanism.Packing lower bounds and the exponential mechanism provide the bridge.
  • Proof strategy: A metric net supplies nearby representatives and a packing supplies well-separated outputs, enabling a finite candidate set for the exponential mechanism.The net and packing properties are stated with separation and coverage at scale 4α in the theorem proof.
  • Proof strategy: The packing argument bounds its size through mutual information: (1/2) log |T| − log 2 ≤ ξ · n(1 + log n) + ρ · n^2.Accuracy lets the output identify a uniformly chosen packed target with high probability.

8 Approximate zCDP

The paper introduces approximate zCDP by allowing Rényi-divergence guarantees to hold on high-probability events. This definition generalizes zCDP and approximate DP, preserves composition and postprocessing, and yields a tightened unified composition analysis.

  • Definition: δ-approximate (ξ, ρ)-zCDP requires Rényi-divergence bounds between conditioned output distributions on events occurring with probability at least 1 − δ.The definition imposes the bound in both directions for all α > 1.
  • Relationship to DP: Approximate zCDP contains ordinary zCDP at δ = 0 and makes δ-approximate (ε, 0)-zCDP equivalent to (ε, δ)-DP.The paper therefore presents it as a unification of both relaxations of pure DP.
  • Properties: Composition and postprocessing add the approximate-zCDP parameters: δ becomes δ + δ′ − δ·δ′, while ξ and ρ become ξ + ξ′ and ρ + ρ′.This is the composition rule for sequentially applying the two mechanisms.
  • Trade-off: Approximate zCDP avoids the strong group-privacy guarantees and corresponding lower bounds established for ordinary zCDP.This loss is part of the motivation for introducing the approximate relaxation.
  • Open direction: The proposed bounded-zCDP variant restricts the Rényi-divergence condition to α ∈ (1, m), but its group-privacy behavior for k ≫ m remains open.The paper leaves this relaxation for future investigation.
  • Relationship to DP: Approximate DP mechanisms can be represented through the approximate randomized-response mechanism, implying that every (ε, δ)-DP mechanism satisfies δ-approximate (ε, 0)-zCDP.This supports the claimed subsumption of approximate DP.
  • Composition: The resulting unified composition analysis saves a constant factor in the first term and improves the logarithmic term when π/2∥ε∥2 < 1.The analysis can combine mechanisms satisfying concentrated and approximate differential privacy.

A Postprocessing and mCDP

The appendix constructs a Gaussian-mechanism counterexample showing that mCDP is not preserved under postprocessing, despite the original mechanism satisfying the stated guarantee.

  • Counterexample construction: The Gaussian mechanism M on a single bit satisfies (2/σ^2, 2/σ)-mCDP and (2/σ^2)-zCDP.M(x) samples from N(x, σ^2).
  • Counterexample construction: Postprocessing M with threshold function T produces M′ mapping outputs to {−1, 0, 1}.T outputs 1 above t, −1 below −t, and 0 between those thresholds.
  • Failure of postprocessing: The required mCDP tail bound would be ≤e^{2λ^2/σ^2} for all λ > 0, but the appendix shows this fails for σ ≥ 1 and t ≥ 6σ^3 + 1.The failure can also be checked numerically for specific parameter settings.

B Miscellaneous Proofs and Lemmata

These lemmas develop technical tools relating privacy loss, Rényi divergence, concentrated privacy, and approximate differential privacy, including a conversion from zCDP to CDP.

  • Technical inequalities: The appendix uses hyperbolic-function inequalities and an involved proof strategy to establish the needed technical bounds.It notes that one technical lemma may be verified numerically by inspecting a plot, while the actual proof is more involved.
  • Privacy-loss bounds: A technical lemma bounds events of large privacy loss using Rényi-divergence bounds D_α(P∥Q) ≤ ξ + ρ·α.The proof decomposes an event according to whether privacy loss is at most ε and then bounds the large-loss tail using Markov’s inequality.
  • Privacy-loss bounds: The resulting conversion sets ε = ξ̂ + λ and δ = e^{−λ^2/ρ̂}.This connects concentrated privacy parameters to approximate differential privacy parameters.
  • zCDP to CDP: If M satisfies (ξ, ρ)-zCDP, then M satisfies (ξ + ρ, O(√ξ + 2ρ))-CDP.The proof uses the privacy-loss random variable and bounds its mean through Rényi-divergence quantities.

B.1 Proof of Lemma 2.2

This section establishes auxiliary properties of Rényi divergence, including non-negativity, quasi-convexity under mixtures, and postprocessing behavior.

  • Rényi-divergence properties: Rényi divergence is nonnegative because x^α is strictly convex for α > 1.Applying Jensen’s inequality to the likelihood ratio yields the non-negativity result.
  • Rényi-divergence properties: Although Rényi divergence is not convex for α > 1, it satisfies a quasi-convexity property for convex combinations of distributions.The proof studies the second derivative of e^{(α−1)D_α(P_t∥Q_t)}.
  • Postprocessing: Postprocessing is analyzed by grouping inputs according to the output of the mapping and applying Jensen’s inequality conditionally.The argument uses the convexity of x^α over the preimages of each output.

C Privacy versus Sampling

This section connects private query answering with distributional sampling: accurate private answers can yield nearby sample-based query answers under zCDP guarantees.

  • Privacy versus sampling: The technical lemma shows that a private mechanism accurately answering queries with a given sample complexity can support approximation on an unknown distribution with the same sample complexity.This establishes the section’s privacy-versus-sampling connection.
  • Divergence to expectation: Pinsker’s inequality and its Rényi-divergence generalization convert divergence bounds into expectation bounds for bounded functions.The results apply to functions f: Ω → R and, in particular, to postprocessed outputs of zCDP mechanisms.
  • Reduction construction: The construction W outputs a mechanism answer together with a vector used to evaluate query expectations under a distribution D.The proof defines a normalized inner-product function f(z, a, s) to connect query values with the mechanism output.
  • Reduction construction: Replacing one database element by an independent draw from D is controlled through divergence bounds, postprocessing, convexity, and Pinsker’s inequality.These steps compare the resulting expectations across neighboring databases and distributional samples.
  • Sampling guarantee: There exists a sample ˆx drawn from D^n whose query vector satisfies ∥q(ˆx) − q(D)∥ ≤ 2α + 2(ξ + ρ).The proof obtains this conclusion by applying the preceding proposition to the uniform distribution over elements of a database.
Loading 1605.02065v1…