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

Approximate differential privacy can be an inelegant abstraction for mathematical analysis, especially composition. The paper reformulates concentrated differential privacy using Rényi divergence and reports lower bounds, including a separation between zCDP and approximate differential privacy for accurate histograms.

  • Problem

    Approximate differential privacy can be an inelegant abstraction for mathematical analysis, particularly for composition.

    Source: §1 · p. 3

  • Method

    The paper defines zCDP using Rényi divergence between neighboring-input output distributions to capture subgaussian privacy loss, and introduces approximate zCDP.

    Source: §1 · p. 4, §8 · p. 30

  • Results

    For accurate histograms over a domain of size k, zCDP requires n = Θ(√log k), while approximate differential privacy permits n independent of k [BNS13].

    Source: §1.2.5 · p. 8

  • Takeaways & Limitations

    The lower bounds show that stability-based techniques, including propose-test-release, are not compatible with zCDP.

    Source: §1.2.5 · p. 8

    The paper leaves open whether CDP has a complete mechanism and a simple characterization of its sample complexity.

    Source: §1.4 · p. 10

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 · 1.1 Our Reformulation: Zero-Concentrated Differential Privacy · 1.2 Results

This section develops a Rényi-divergence formulation of concentrated privacy and defines approximate zCDP to connect it with approximate differential privacy. It describes the formulation’s properties and consequences, including stability-based techniques and composition analysis involving approximate differential privacy.

1.1 Our Reformulation: Zero-Concentrated Differential Privacy

  • zCDP bounds neighboring-input Rényi divergence, capturing subgaussian privacy loss; (µ, τ)-mCDP implies (µ−τ^2/2, τ^2/2)-zCDP, but the converse does not hold.The stated conversion is tight for the Gaussian mechanism.Source: §1 · p. 4, §1.1 · p. 5, §1.1.1 · p. 6

1.2.1 Relationship between zCDP and Differential Privacy

  • ρ-zCDP implies (ρ + 2√(ρ log(1/δ)), δ)-differential privacy for any δ > 0, with a partial converse up to parameter loss.The paper also places zCDP between pure and approximate differential privacy.Source: §1.2.1 · p. 6

1.2.2 Gaussian Mechanism

  • A Gaussian mechanism releasing a sensitivity-∆ query with noise variance σ^2 satisfies (∆^2/2σ^2)-zCDP, and the defining inequalities are exactly tight for it.Tightness holds for every α.Source: §1.2.2 · p. 7

1.2.3 Basic Properties of zCDP

  • zCDP composes additively and is preserved under postprocessing, whereas mCDP is not closed under postprocessing.Combining mechanisms with guarantees ρ and ρ′ yields (ρ + ρ′)-zCDP.Source: §1.2.3 · p. 7

1.2.4 Group Privacy

  • A ρ-zCDP mechanism guarantees k^2ρ-zCDP for groups of up to k changed entries, a bound that is exactly tight and achieved by the Gaussian mechanism.The guarantee applies over a wider parameter range than the cited earlier result.Source: §1.2.4 · p. 7

1.2.5 Lower Bounds

  • For independent dataset entries, zCDP bounds I(X; M(X)) by ρn; accurate histograms over a domain of size k require n = Θ(√log k) under zCDP, unlike approximate DP.Under approximate differential privacy, the histogram sample size can be independent of k.Source: §1.2.5 · p. 8
  • A zCDP statistical-query mechanism can be converted to pure differential privacy with quadratic sample-size blowup, including n′ = 5n^2 in the theorem’s ε = α, ρ = α^2 setting.For one-way marginals, the Gaussian mechanism has zCDP sample complexity Θ(√k), while the pure-DP Laplace mechanism requires Θ(k).Source: §1.2.5 · pp. 8–9

1.2.6 Approximate zCDP

  • Approximate zCDP relaxes zCDP by permitting a small probability δ of catastrophic failure.The supplied passage introduces this relaxation but does not provide the full defining condition.Source: §1.2.6 · p. 9
  • For neighboring inputs, approximate zCDP bounds Rényi divergence in both directions after conditioning on events that each occur with probability at least 1 − δ.The bounds are D_α ≤ ξ + ρ·α for all α > 1; δ-approximate ρ-zCDP is defined as δ-approximate (0, ρ)-zCDP.Source: §1.2.6 · p. 9
  • Setting δ = 0 recovers the original zCDP definition, and Proposition 1.13 connects (ε, δ)-differential privacy to δ-approximate zCDP.The supplied passage does not specify the parameters of the resulting zCDP guarantee.Source: §1.2.6 · p. 9
  • Approximate zCDP retains most desirable zCDP properties while enabling stability-based techniques, bypassing the stated lower bounds, and analyzing compositions with approximate differential privacy.The passage points to Section 8 for composition analysis.Source: §1.2.6 · p. 9

1.3 Related Work · 1.4 Further Work

The section presents zCDP as an easier-to-use Rényi-divergence formulation of the shared concentrated differential privacy concept, then considers CDP’s implications and open questions. It argues CDP can be more stringent than approximate DP while inviting further study of its uses and limits.

1.3 Related Work

  • The authors characterize zCDP and mCDP as formalizations of the same CDP concept, with zCDP generally easier to use because its Rényi-divergence formulation simplifies analyses.Their work builds on and was heavily inspired by an early Dwork and Rothblum draft [DR16].Source: §1.3 · pp. 9–10
  • Dwork and Rothblum [DR16] prove analogous mCDP properties to this paper’s zCDP results, but some of their bounds are weaker and they do not explore lower bounds.The comparison refers to results discussed in Sections 1.2.1–1.2.4.Source: §1.3 · p. 10
  • Earlier work by Dwork, Rothblum, and Vadhan implicitly uses CDP ideas in proving advanced composition, with analogs of several propositions in this paper.Tardos used Rényi divergence for fingerprinting-code lower bounds, and fingerprinting codes are closely related to differential privacy [Ull13] [BUV14] [SU15b].Source: §1.3 · p. 10

1.4 Further Work

  • The authors argue CDP offers simpler, tighter bounds and hope it proves useful in theory and practice; they suggest re-examining differential-privacy literature through the CDP lens.They also note that some of Dwork and Rothblum’s analogous mCDP bounds are weaker than theirs, and that their work does not explore lower bounds.Source: §1.4 · p. 10, §1.3 · p. 10
  • CDP’s lower bounds show it can be much more stringent than approximate DP, defining a subclass that includes most literature algorithms but excludes notable propose-test-release methods.The authors characterize this subclass as warranting further exploration.Source: §1.4 · p. 10
  • Open questions include whether the CDP subclass has a complete mechanism like the exponential mechanism for pure DP and how to characterize its sample complexity.Stronger, simpler CDP lower bounds may expose limits of algorithmic paradigms; algorithms using Laplace, exponential, Gaussian, sparse vector, composition, and postprocessing are subject to CDP lower bounds.Source: §1.4 · p. 10
  • The authors leave open how much stronger ρ-zCDP is than the implied (ε, δ)-DP guarantees.They refer to Proposition 1.3 for the implied guarantees.Source: §1.4 · p. 10

2 R´enyi Divergence

The section defines Rényi divergence and relates it to privacy loss, then records properties used to establish zCDP composition, postprocessing, and Gaussian-mechanism guarantees.

2 Rényi Divergence

  • Rényi divergence is defined for probability distributions of order α, with the Radon–Nikodym derivative covering the general case; its order-1 form is the expected privacy loss.The section also defines KL divergence, and states that Rényi divergence is infinite when P is not absolutely continuous with respect to Q.Source: §2 · p. 11
  • Rényi divergence is nonnegative, vanishing exactly when the distributions agree, and obeys a composition rule that makes product-distribution divergences additive across marginals.The composition rule decomposes divergence into a marginal term and conditional divergences.Source: §2 · pp. 11–12
  • Rényi divergence is quasi-convex under matched mixtures, KL divergence is convex, and postprocessing cannot increase Rényi divergence, including under randomized mappings.For mixtures P=tP0+(1−t)P1 and Q=tQ0+(1−t)Q1, the divergence is bounded by the larger of the two paired divergences.Source: §2 · p. 12

2.1 Composition and Postprocessing

  • Composing mechanisms satisfying (ξ, ρ)- and (ξ′, ρ′)-zCDP yields a mechanism satisfying (ξ+ξ′, ρ+ρ′)-zCDP.The composition bound applies to adaptive composition and extends inductively to arbitrarily many mechanisms.Source: §2.1 · p. 12

2.2 Gaussian Mechanism

  • The Gaussian-mechanism subsection gives same-variance Gaussian divergence results and states that releasing N(q(x), σ²I_d) satisfies ρ-zCDP.Here q maps inputs to R^d; the guarantee’s parameter expression is not included in the supplied passage.Source: §2.2 · pp. 12–13

3 Relation to Differential Privacy

The section relates zCDP to traditional differential privacy: pure DP is exactly characterized by zCDP, while approximate DP and zCDP are equivalent up to a loss in parameters. It also gives a max-divergence-based bound on KL divergence and conversions between approximate-DP and zCDP guarantees.

3.1 Pure DP versus zCDP

  • A mechanism satisfies ε-DP if and only if it satisfies (ε, 0)-zCDP.This is an exact characterization of pure differential privacy.Source: §3.1 · p. 14
  • The authors bound KL divergence in terms of max-divergence, sharpening and simplifying a prior bound used in advanced-composition analysis.They describe the improvement as applying up to lower-order terms and identify the bound as an important ingredient in the advanced composition theorem [DRV10].Source: §3.1 · p. 14

3.2 Approximate DP versus zCDP

  • A mechanism satisfying (ξ, ρ)-zCDP satisfies (ε, δ)-DP for every δ > 0, with Lemma 3.6 refining the conversion in Lemma 3.5.The section also gives a sufficient zCDP condition for a target (ε, δ)-DP guarantee, but the supplied passages omit its formula.Source: §3.2 · pp. 15–16
  • Conversely, the section gives a partial converse from (ε, δ)-DP guarantees for all δ > 0 to zCDP, establishing equivalence up to potentially substantial parameter loss.The conclusion qualifies this equivalence by the requirement to quantify over all δ.Source: §3.2 · p. 16

4 Zero- versus Mean-Concentrated Differential Privacy

mCDP centers a subgaussian privacy-loss bound at its mean and separately bounds that mean, while zCDP centers the bound at zero. The two notions convert into one another, but potentially with significant parameter loss.

4 Zero- versus Mean-Concentrated Differential Privacy

  • mCDP [DR16] bounds privacy loss around its mean and separately bounds the mean, whereas zCDP directly gives a subgaussian bound centered at zero.The paper describes zCDP as a relaxation of mCDP: mCDP's tighter concentration about the mean implies weaker concentration about the origin.Source: §4 · p. 17
  • An (µ, τ)-mCDP mechanism is (µ−τ^2/2, τ^2/2)-zCDP; conversely, (ξ, ρ)-zCDP implies (ξ + ρ, O(√ξ + 2ρ))-mCDP.Source: §4 · p. 17
  • Converting between the notions can incur significant parameter loss, and pure DP can be characterized via zCDP but not mCDP.Source: §4 · p. 17
  • Although mCDP's stronger requirement may help with privacy guarantees or analysis, most applications appear to need only what zCDP provides.Source: §4 · p. 17

5 Group Privacy

This section extends zCDP privacy guarantees from individual changes to groups of up to k individuals. It establishes quantitative group bounds and distinguishes the optimal dependence on ρ from a nonoptimal bound on ξ.

5 Group Privacy

  • The group bound is proved inductively, using a triangle-like inequality for Rényi divergence to relate a k-entry change to a (k−1)-entry change and a one-entry change.The usual zCDP definition applies to groups of size 1; the argument extends it to larger groups.Source: §5 · pp. 18–19
  • For inputs differing in at most k entries, (ξ, ρ)-zCDP implies group privacy with parameters (O(k log k)ξ, k²ρ).Proposition 5.3 gives the sharper ξ factor ξ·k times the kth harmonic sum; the Gaussian mechanism shows the k² dependence on ρ is optimal.Source: §5 · p. 19
  • The O(k log k)ξ dependence is not optimal: when ρ = 0, group privacy holds with ξ scaled by k, while k²ρ is optimal.The section states that (ξ, 0)-zCDP implies (kξ, 0)-zCDP for groups of size k.Source: §5 · p. 19

6 Lower Bounds

The section develops zCDP lower bounds by using group privacy to bound how much information a mechanism can reveal about its input. It applies this information-based approach to one-way marginals, histograms, and search problems.

6 Lower Bounds

  • Group privacy bounds mutual information between a zCDP mechanism’s input and output, so distributions requiring accurate mechanisms to reveal substantial information yield accuracy lower bounds.The section also notes that this connection between group privacy and lower bounds reinforces earlier work [HT10] [De12] [SU15a].Source: §6 · p. 20
  • For independent input entries, the section gives stronger mutual-information bounds; for independent blocks of ℓ records, the KL-divergence bound is ξ · ℓ(1 + log ℓ) + ρ · ℓ².The block result applies when n = m · ℓ and the m blocks are independent.Source: §6 · pp. 20–22

6.1 Example Applications of the Lower Bound

  • For one-way marginals, a repeated uniform database construction and Proposition 6.1 yield a zCDP sample-complexity lower bound that is tight up to constant factors.The passage states the matching upper bound uses independent Gaussian noise on the coordinates, but its sample-complexity expression is truncated in the supplied text.Source: §6.1 · p. 23
  • For histograms, the section establishes sample complexity n = Θ(log(T)/ρ) under zCDP and describes this as a strong separation from approximate DP.The lower bound uses a uniformly random value repeated across all records: an accurate output reveals that value, giving information at least Ω(log T).Source: §6.1 · p. 23
  • For randomized response and exponential-mechanism search, independent input bits give I(X; M(X)) ≤ ρ · n, while accuracy permits recovering part of X and implies I(X; M(X)) ≥ Ω(n).The passage identifies randomized response as a special case of the exponential mechanism.Source: §6.1 · p. 24
  • The formal histogram-accuracy argument partitions the input into independent blocks of repeated uniform values and uses the output to identify represented values.It compares the set of values present in the input with values whose estimated counts exceed 5αn.Source: §6.1 · pp. 24–25

7 Obtaining Pure DP Mechanisms from zCDP

The section shows that mechanisms satisfying zCDP can yield pure-DP mechanisms for statistical queries with at most a quadratic sample-complexity blowup. Its proof is nonconstructive, transferring pure-DP lower bounds through packing arguments.

7 Obtaining Pure DP Mechanisms from zCDP

  • When ξ = 0, n′ = O(n^2ρ/(εα)); for constant ρ, ε, and α, this gives a quadratic sample-complexity blowup from zCDP to pure DP.The theorem applies to statistical queries and supports both ∥·∥∞ and ∥·∥1 error bounds.Source: §7 · pp. 25–26
  • The Gaussian-mechanism example shows that the theorem loses a factor of 1/α^2 in α, although its other parameters are tight.Source: §7 · p. 26
  • The proof is nonconstructive: it transfers pure-DP lower bounds through packing arguments, while a net plus the exponential mechanism supplies a pure-DP algorithm.Source: §7 · pp. 26–27
  • For an α-separated, realizable packing and a (ξ, ρ)-zCDP mechanism accurate with failure β, (1 − β) log |T| − log 2 ≤ ξ · n(1 + log n) + ρ · n^2.The bound follows by upper-bounding the mutual information between the packed input and the mechanism’s decoded output.Source: §7 · p. 28

8 Approximate zCDP

Approximate zCDP relaxes zCDP by bounding Rényi divergence on high-probability events, unifying pure zCDP with approximate DP. The section gives composition and conversion results, while noting limits to group-privacy guarantees and deriving an advanced-composition improvement.

8 Approximate zCDP

  • Approximate zCDP bounds Rényi divergence in both directions on high-probability events using parameters δ, ξ, and ρ, unifying pure zCDP with approximate DP.The events each have probability at least 1−δ; setting δ=0 gives zCDP, and δ-approximate (ε,0)-zCDP is equivalent to (ε,δ)-DP.Source: §8 · p. 30
  • Composing δ-approximate (ξ,ρ)-zCDP and δ′-approximate (ξ′,ρ′)-zCDP mechanisms yields (δ+δ′−δδ′)-approximate (ξ+ξ′,ρ+ρ′)-zCDP.The section also proposes m-bounded zCDP, which requires the Rényi-divergence bound only for α<m; its group-privacy guarantees for k≫m are unknown, and it may circumvent group-privacy-based lower bounds.Source: §8 · pp. 30–31

8.1 Approximate DP Implies Approximate zCDP

  • Every (ε,δ)-DP mechanism is δ-approximate (ε,0)-zCDP, using an approximate randomized-response mechanism that simulates neighboring output distributions, [MV16, Lemma 3.2].The section describes approximate randomized response as complete for approximate DP.Source: §8.1 · p. 31

8.2 Approximate zCDP Implies Approximate DP

  • When ρ=0, δ-approximate (ξ,ρ)-zCDP implies (ξ,δ)-DP; more generally, the conversion gives an approximate-DP guarantee for ε≥ξ+ρ.The general bound stated is (ε, δ+(1−δ)δ′)-DP.Source: §8.2 · p. 32

8.3 Application of Approximate zCDP

  • Compared with [DRV10], the composition result saves a modest constant factor in the first term and improves the logarithmic term in most cases when π/2∥ε∥2<1.The analysis may also extend to composing CDP mechanisms with approximate-DP mechanisms, offering a unified composition analysis.Source: §8.3 · pp. 33–34

A Postprocessing and mCDP

A Gaussian mechanism satisfies the stated mCDP guarantee, but a threshold postprocessing can violate that same guarantee. The appendix uses this counterexample to show that mCDP, unlike zCDP, is not closed under postprocessing.

A Postprocessing and mCDP

  • The starting Gaussian mechanism M is (2/σ^2, 2/σ)-mCDP and also (2/σ^2)-zCDP.Source: A Postprocessing and mCDP · p. 37
  • The counterexample postprocesses M by mapping outputs above t to 1, below −t to −1, and outputs between them to 0.The resulting mechanism is M′(x) = T(M(x)).Source: A Postprocessing and mCDP · p. 37
  • For σ ≥1 and t ≥6σ^3 + 1, M is (2/σ^2, 2/σ)-mCDP but its postprocessed version M′ is not, showing mCDP is not closed under postprocessing.Source: A Postprocessing and mCDP · p. 37

B Miscellaneous Proofs and Lemmata

The appendix collects technical lemmas supporting the paper’s privacy guarantees. It relates Renyi-divergence and approximate-DP assumptions to privacy-loss bounds and records a zCDP-to-CDP conversion.

Lemma B.2

  • Under Dα(P∥Q) ≤ ξ + ρ · α for all α > 1, Lemma B.2 bounds measurable-event probabilities when ε ≥ ξ + ρ.Its proof defines the privacy-loss random variable and uses tail bounds to obtain the event bound.Source: B Miscellaneous Proofs and Lemmata · pp. 41–43

Lemma B.3

  • For neighboring inputs under approximate DP, Lemma B.3 bounds the privacy-loss tail and substitutes ε = ˆξ + λ and δ = e^−λ²/ˆρ.It defines privacy loss for the two neighboring output distributions and applies the approximate-DP condition.Source: B Miscellaneous Proofs and Lemmata · p. 44

Lemma B.5

B.1 Proof of Lemma 2.2

The section proves properties of Rényi divergence used in Lemma 2.2, including non-negativity, quasi-convexity, postprocessing, and monotonicity. Its arguments use convexity and Jensen’s inequality, alongside a second-derivative proof for mixtures.

Proof of Non-Negativity

  • Convexity of h(t) = t^α for α > 1 establishes non-negativity, with the other side of the inequality following symmetrically.The proof notes that h′′(t) = α(α − 1)t^(α−2) > 0 for t > 0.Source: §B.1 · p. 47

Proof of Quasi-Convexity

  • Rényi divergence is shown to be quasi-convex under simultaneous convex mixtures of P and Q, using Lemma B.6’s second-derivative argument.The proof sets f(t) = e^((α−1)Dα(Pt∥Qt)) and aims to show f′′(t) ≥ 0 on [0, 1].Source: §B.1 · pp. 47–48

Proof of Postprocessing

  • The postprocessing proof uses convexity of h(x) = x^α and Jensen’s inequality on the conditional distribution given f(x) = y.It defines Qy by conditioning x ∼ Q on f(x) = y.Source: §B.1 · p. 48

Proof of Monotonicity

  • For 1 < α ≤ α′ < ∞, the monotonicity proof applies h(x) = x^α and concludes with the stated result.The supplied passage ends with “which gives the result” but does not include the intervening derivation.Source: §B.1 · p. 49

C Privacy versus Sampling

The appendix connects private query mechanisms’ sample complexity to approximation on an unknown distribution. It develops this transfer using Rényi-divergence generalizations of Pinsker’s inequality for zCDP mechanisms.

C Privacy versus Sampling

  • The appendix relates its result to private-sample-complexity lower bounds using VC dimension [DR14, Theorem 4.8] and [BNSV15, Theorem 5.5].Source: C Privacy versus Sampling · p. 49
  • The Rényi-divergence generalization of Pinsker’s inequality yields a bound for bounded functions of outputs from neighboring inputs of a (ξ, ρ)-zCDP mechanism.The passages state the inequality and its zCDP application, but omit their formulas.Source: C Privacy versus Sampling · p. 49
  • The proof constructs W from the mechanism output and a vector-valued statistic, then uses Pinsker’s inequality to compare outputs after replacing one sample with a fresh draw.This argument is similar to [BNS+16a, Lemma 3.1].Source: C Privacy versus Sampling · pp. 50–51
  • 2α + 2(ξ + ρ) bounds ∥q(ˆx) − q(D)∥ for some ˆx∼D^n, completing the private-mechanism-to-distribution approximation argument.The proof takes D to be uniform over the elements of x.Source: C Privacy versus Sampling · pp. 49, 52

Related papers

Loading 1605.02065v1…