Local Differential Privacy Is Equivalent to Contraction of $E_\gamma$-Divergence

C. Local Differential Privacy

• LDP constrains how much a randomized mechanism’s output can vary across inputs; the paper considers pure and approximate forms.The introduction describes privacy loss as the output log-likelihood ratio for two different inputs, bounded almost surely for pure LDP and with probability at least 1 −δ for approximate LDP.Source: §I · p. 1

I. INTRODUCTION

• The paper extends an SDPI-based framework to (ε, δ)-LDP and derives minimax and Bayesian risk bounds for all ε ≥0 and δ ≥0.At δ = 0, the bounds can be slightly stronger than [10].Source: §I · p. 1
• A mechanism is (ε, δ)-LDP exactly when its Eγ-divergence contraction coefficient is at most δ for γ = e^ε.This characterizes approximate LDP through contraction under Eγ-divergence.Source: §I · pp. 1–2
• An (ε, δ)-LDP mechanism contracts every f-divergence by at most 1 −e−ε(1 −δ).The guarantee applies to any pair of input distributions.Source: §I · p. 2

A. f-Divergences

• An f-divergence is defined from a convex function f with f(1) = 0; Eγ-divergence is the subfamily generated by fγ(t) = max{t −γ, 0}.The paper also identifies KL, total variation, and χ2 divergence as examples of f-divergences.Source: A. f-Divergences · p. 2

B. Contraction Coefficient

• The contraction coefficient is the smallest η ≤1 bounding the ratio of output to input f-divergence under a Markov kernel.For Eγ-divergence, prior work gives a two-point characterization that extends Dobrushin’s total-variation result.Source: B. Contraction Coefficient · pp. 2–3

III. LDP AS THE CONTRACTION OF Eγ-DIVERGENCE

• A mechanism is (ε, δ)-LDP if and only if its Eγ-contraction coefficient at γ = e^ε is at most δ.The theorem makes precise the view of LDP as contraction of probability measures.Source: §III · p. 3
• Every f-divergence contracts under an (ε, δ)-LDP mechanism by at most ϕ(ε, δ) = 1 −(1 −δ)e−ε.For general kernels, this offers an alternative when KL contraction is difficult to compute in closed form.Source: §III · p. 4
• For n independent applications of an (ε, δ)-LDP mechanism, the f-divergence contraction coefficient is at most ϕn(ε, δ) = 1 −e−nε(1 −δ)n.The section derives this through tensorization rather than first applying privacy composition to the product mechanism.Source: §III · p. 4

IV. PRIVATE MINIMAX RISK

• Private minimax lower bounds reduce estimation to testing separated parameter distributions and then bound testing error using total variation or mutual information.Le Cam’s and Fano’s methods provide these bounds and use the contraction lemmas.Source: §IV · pp. 4–5

A. Locally Private Le Cam’s Method

• (1 −e−ε(1 −δ))n is the effective sample size under (ε, δ)-LDP in the private Le Cam bound.For δ = 0, this strengthens the earlier effective-sample-size bound 4ε2n for sufficiently small ε.Source: A. Locally Private Le Cam’s Method · p. 5
• The framework’s one-dimensional mean-estimation lower bound applies for every ε ≥0 and δ ∈[0, 1], beyond the earlier ε ≤1 result.The example uses squared ℓ2 loss and a moment-constrained distribution family.Source: A. Locally Private Le Cam’s Method · p. 5
• For finite variance, the sample-mean rate worsens from 1/n to 1/ϕ(ε, δ)√n under privacy; for bounded data, the lower bound is (ϕ2(ε, δ)n)−1.The bounded-data case follows as k →∞ in the moment condition.Source: A. Locally Private Le Cam’s Method · p. 5

B. Locally Private Fano’s Method

• Fano’s method uses a larger subset of the parameter family than Le Cam’s pairwise approach to obtain a stronger non-interactive minimax lower bound.The method bounds mutual information after privatization using the contraction result.Source: B. Locally Private Fano’s Method · pp. 5–6
• The high-dimensional mean-estimation lower bound applies for any ε ≥0 and δ ∈(0, 1), though it is slightly weaker than [10, Proposition 3].The example estimates the mean of data in an ℓ2-ball.Source: B. Locally Private Fano’s Method · p. 6

V. PRIVATE BAYESIAN RISK

• The private Bayes-risk bound directly involving Eγ-divergence is stated to be tighter than bound (3).Bayes risk averages loss over a prior on the true parameter, unlike the worst-case minimax risk.Source: §V · pp. 6–7
• In the uniform-prior Bernoulli example with δ = 10−4 and n = 20, Theorem 2’s lower bound has an advantage for small ε over the private version of [44, Theorem 1].Fig. 1 compares the two lower bounds.Source: §V · p. 7, Figure 1 · p. 8
• For the uniform-prior Bernoulli example, bound (17) gives a Bayes-risk lower bound of 0.08, versus 0.03 from (15).The example uses absolute-error loss on parameters in [0, 1].Source: §V · pp. 7–8

• The testing setup distinguishes P0 from P1 using privatized samples and defines β^{ε,δ}_n(α) as the minimum type II error under a type I error constraint.The passage permits sequential interaction in the sample mechanisms, while the trade-off definition specifies non-interactive mechanisms.Source: §VI · p. 8
• A related result by Kairouz et al. [13, Sec. 3] applies only for sufficiently small, unspecified ε and δ = 0.The passage compares the corollary’s setting with the Chernoff–Stein characterization of non-private error decay.Source: §VI · p. 8
• The corollary justifies reducing the effective sample size from n to ϕ(ε, δ)n under an (ε, δ)-LDP requirement.The supplied passage does not give the corollary’s full bound.Source: §VI · p. 8

• The utility objective is to characterize the supremum of I(X; Z) over mechanisms K ∈ Q_{ε,δ}, the maximum information shared by X and its private representation.Source: §VII · p. 9
• Earlier cited bounds include I(X; Z) ≤ 3ε for pure LDP and a result for sufficiently small ε² under Kairouz et al. [13, Corollary 15].The passage attributes the first bound approximately to McGregor et al..Source: §VII · p. 9
• The section provides an upper bound on mutual information under LDP for every ε ≥ 0 and δ ∈ [0, 1].The bound’s formula is not included in the supplied passages.Source: §VII · p. 9

• Theorem 3 is stated for every γ ≥ 1 and Markov kernel, and the appendix identifies its γ = 1 case with Dobrushin’s result.Source: APPENDIX · p. 11
• A mechanism K is (ε, δ)-LDP if and only if its E_{e^ε} contraction coefficient is at most δ.This is stated as the equivalence used to prove Theorem 1.Source: APPENDIX · p. 11
• The Fano argument constructs a separated set of hypercube vectors and distributions indexed by those vectors to obtain a minimax estimation bound.The vectors have pairwise ℓ1 separation at least k/2, and the set has size at least ⌈e^{k/16}⌉.Source: APPENDIX · pp. 14–15
• The Bayesian loss proof bounds the probability of loss within ζ using Markov’s inequality, data processing for Iγ, and the contraction coefficient.For n > 1, it invokes the bound η_{e^ε}(P_{Z^n|X^n}) ≤ ϕ^n(ε, δ).Source: APPENDIX · pp. 15–16
• For n mechanisms, the appendix bounds η_{e^ε}(P_{Z^n|X^n}) by ϕ^n(ε, δ), and derives η_{TV}(K_i) ≤ ϕ(ε, δ) for each (ε, δ)-LDP mechanism.The individual-mechanism step uses η_{e^ε}(K_i) ≤ δ.Source: APPENDIX · pp. 12, 16