PaperlayerView exact revision on arXiv

Source-linked AI summary

Contraction of $E_\gamma$-Divergence and Its Applications to Privacy

Shahab Asoodeh, Mario Diaz, Flavio P. Calmon

arXiv:2012.11035v2cs.ITcs.CRcs.LGmath.ITstat.ML

TL;DR

The paper studies how to characterize divergence contraction through channels for privacy analysis. It extends Dobrushin’s result to Eγ-divergence and applies the characterization to LDP risk and iterative-algorithm privacy, including an effective-sample-size reduction in estimation.

Abstract

from arXiv · show

We investigate the contraction coefficients derived from strong data processing inequalities for the $E_\gamma$-divergence. By generalizing the celebrated Dobrushin's coefficient from total variation distance to $E_\gamma$-divergence, we derive a closed-form expression for the contraction of $E_\gamma$-divergence. This result has fundamental consequences in two privacy settings. First, it implies that local differential privacy can be equivalently expressed in terms of the contraction of $E_\gamma$-divergence. This equivalent formula can be used to precisely quantify the impact of local privacy in (Bayesian and minimax) estimation and hypothesis testing problems in terms of the reduction of effective sample size. Second, it leads to a new information-theoretic technique for analyzing privacy guarantees of online algorithms. In this technique, we view such algorithms as a composition of amplitude-constrained Gaussian channels and then relate their contraction coefficients under $E_\gamma$-divergence to the overall differential privacy guarantees. As an example, we apply our technique to derive the differential privacy parameters of gradient descent. Moreover, we also show that this framework can be tailored to batch learning algorithms that can be implemented with one pass over the training dataset.

I. INTRODUCTION

The paper characterizes divergence through Markov chains and extends Dobrushin’s contraction result to Eγ-divergence. It uses this characterization to express local privacy through contraction and analyze privacy in estimation and iterative algorithms.

A. Main Contributions

  • Theorem 2 gives a two-point characterization of Eγ contraction, extending Dobrushin’s total-variation result for γ ≥ 1; for γ < 1, ηγ(K) = η1/γ(K).The paper also derives strong data processing inequalities for amplitude-constrained Gaussian channels.Source: §I · p. 2, A. Main Contributions · p. 3
  • The contraction result also yields a provably tighter upper bound on output f-divergence than the cited earlier bound.The paper numerically compares the bounds for χ2-divergence.Source: A. Main Contributions · p. 3
  • An (ε, δ)-LDP mechanism is equivalently characterized by ηe^ε(K) ≤ δ.This equivalence provides an output-divergence bound for general f-divergences under LDP.Source: A. Main Contributions · p. 4
  • For one-dimensional minimax and Bayesian estimation under (ε, δ)-LDP, the effective sample size becomes n(1 − (1 − δ)e^-ε).The minimax analysis applies for any ε ≥ 0 and δ ∈ [0, 1].Source: A. Main Contributions · p. 4
  • The paper analyzes iterative algorithms by modeling each update as a Gaussian channel followed by projection, then translating Eγ-divergence bounds into central DP guarantees.The framework is applied to one-pass stochastic gradient descent and online gradient descent.Source: A. Main Contributions · p. 4

B. Additional Related Work

The section situates Eγ contraction among prior SDPI and privacy work, then presents its two-point characterization and the assumptions under which the framework applies to online and batch learning. It also outlines the paper’s organization and notation.

B. Additional Related Work

  • Prior work links SDPI to statistical and information-theoretic problems; this paper uses Eγ-SDPI to study minimax risk under approximate LDP, where δ > 0.Earlier minimax bounds were meaningful only at small ε, while later order-optimal bounds covered the general privacy regime using KL-SDPI.Source: B. Additional Related Work · pp. 4–5
  • The online-learning framework assumes each update depends only on the current cost and state, and that only the final output is disclosed; this excludes FTL variants except Regularized FTL.The Markovity condition is met by several named online algorithms, including online gradient descent and online mirror descent.Source: B. Additional Related Work · p. 5
  • The privacy analysis extends to batch algorithms represented as one-pass online processes, provided each data point is used exactly once.SGD with subsampling without replacement is given as an example.Source: B. Additional Related Work · pp. 5–6

C. Paper Organization

  • The paper proceeds from contraction coefficients and Gaussian-channel contraction to LDP applications in estimation and testing, then privacy analysis of noisy iterative algorithms.The listed algorithm applications include projected noisy SGD and online gradient descent.Source: C. Paper Organization · p. 6

D. Notation

  • The notation uses uppercase letters for random variables, calligraphic letters for their alphabets, and μK for the output distribution induced by channel K under input distribution μ.For sets D ⊂ R^d, dia(D) denotes their diameter.Source: D. Notation · p. 6

II. CONTRACTION COEFFICIENT OF MARKOV KERNELS UNDER Eγ-DIVERGENCE

  • For γ ≥ 1, Theorem 2 reduces computing a Markov kernel’s Eγ contraction coefficient to maximizing output Eγ-divergence over atomic inputs.This extends the contraction-coefficient result to Eγ-divergence, for which the cited general f-divergence formula does not apply because its defining function is not differentiable.Source: B. Additional Related Work · p. 5, §II · p. 7

A. Contraction Coefficient of the Amplitude-Constrained Additive Gaussian Kernel

The section characterizes Eγ contraction for amplitude-constrained additive Gaussian kernels and applies the general contraction result to upper-bound output f-divergences. The resulting bound improves a classical estimate in the stated comparisons.

A. Contraction Coefficient of the Amplitude-Constrained Additive Gaussian Kernel

  • For a D-constrained additive Gaussian kernel, Proposition 1 gives its Eγ contraction coefficient; without input constraints the coefficient is 1, so constraints are needed for nontrivial contraction.The function θγ used in the characterization is non-decreasing in its argument.Source: A. Contraction Coefficient of the… · pp. 8–9

B. A General Upper Bound for Output f-divergence

III. LDP AS THE CONTRACTION OF Eγ-DIVERGENCE

The section characterizes local differential privacy through Eγ-divergence contraction and applies that equivalence to private estimation and testing. Its minimax analysis expresses the privacy cost as a reduction in effective sample size.

III. LDP AS THE CONTRACTION OF Eγ-DIVERGENCE

  • (ε, δ)-LDP is equivalent to η_e^ε(K) ≤ δ, and every LDP mechanism contracts all f-divergences.This equivalence is used to analyze privacy costs in minimax and Bayesian estimation and binary hypothesis testing.Source: §III · pp. 11–12

1) Non-interactive setting:

  • Non-interactive mechanisms apply K independently to each user's datapoint, yielding the n-fold channel K⊗n.When all users use the same mechanism, the overall mechanism is the n-fold tensor power of K.Source: 1) Non-interactive setting · p. 12

2) Sequentially interactive setting:

  • Sequentially interactive mechanisms allow each user's mechanism to depend on earlier outputs, and the section extends its contraction-based analysis to this setting.The overall mechanism is denoted K_n; the provided text says the non-interactive bound is generalized but does not give its formula.Source: 2) Sequentially interactive setting · p. 12

A. Private Minimax Risk

  • (1 − (1 − δ)e^−ε)n is the effective sample size under (ε, δ)-LDP, strengthening Duchi et al. [20, Corollary 2] for δ = 0 and ε < 0.224.The comparison result is stated for private minimax risk relative to the non-private Le Cam bound.Source: A. Private Minimax Risk · p. 14
  • For one-dimensional mean estimation, the LDP risk scales as (ϕ(ε, δ)√n)^−1 with finite variance and (ϕ²(ε, δ)n)^−1 for bounded data.The finite-variance case corresponds to k = 2; the bounded-data rate is the limiting case k → ∞.Source: A. Private Minimax Risk · p. 14

B. Private Bayesian Risk

The section develops lower bounds for Bayesian estimation under local differential privacy using Eγ-information. It compares the resulting bound with an existing private bound and reports an advantage at small ε in the stated example.

B. Private Bayesian Risk

  • The Bayesian estimation setup places a prior on the parameter and estimates it from privatized observations.The section focuses on the non-interactive setting, and the risk depends on the prior distribution.Source: B. Private Bayesian Risk · pp. 14–15
  • The cited passage identifies Theorem 4 as concerning private Bayesian risk RBayes in the non-interactive setting, but does not state a bound or compare it with Corollary 3.Source: B. Private Bayesian Risk · p. 15
  • For Example 5 with δ = 10^−4 and n = 20, Theorem 4 has a significant advantage over Corollary 3 for small ε.The comparison is between the lower bound from Theorem 4 and the private version of [18, Theorem 1] described in Corollary 3.Source: B. Private Bayesian Risk · p. 16, Figure 1 · p. 16

C. Private Binary Hypothesis Testing

The paper relates private binary testing bounds to effective sample size, then develops an Eγ-contraction framework for online-algorithm privacy. It applies the framework to noisy iterative processes, including a randomly stopped variant.

C. Private Binary Hypothesis Testing

  • Under (ε, δ)-LDP, the asymptotic testing bound corresponds to reducing effective sample size from n to ϕ(ε, δ)n.The comparison is with the non-private exponential decay rate given by the Chernoff-Stein lemma.Source: C. Private Binary Hypothesis Testing · p. 17
  • Directly bounding β^n_(ε,δ)(α) through Eγ-divergence is left as future work and may yield a tighter lower bound than Corollary 4.The passage presents this as a potential improvement, not an established result.Source: C. Private Binary Hypothesis Testing · p. 17

A. Online Learning Algorithms

  • The online-learning framework models each noisy iteration as a Markov kernel combining the update rule, additive Gaussian noise, and projection.The chain's final parameter distribution is compared when cost-function sequences differ at one index.Source: A. Online Learning Algorithms · pp. 18–19, Figure 2 · p. 19
  • A bound on the per-step E_e^ε divergence and each kernel's contraction coefficient provides an upper bound for the algorithm's differential privacy parameters.The paper identifies this as the basis for analyzing general iterative processes.Source: A. Online Learning Algorithms · p. 19
  • Theorem 6 gives a differential-privacy guarantee for the randomly stopped Gaussian-noise process, assuming W is closed and convex and the noise is standard Gaussian.The process stops at a time chosen uniformly from [n]; the passage states the theorem but supplies no parameter values here.Source: A. Online Learning Algorithms · p. 20
  • The framework is instantiated for one-pass empirical risk minimization and online gradient descent under a uniform bound on the update-rule outputs.The authors describe this boundedness condition as weaker than regularity conditions typically assumed in differentially private iterative algorithms.Source: A. Online Learning Algorithms · p. 20

B. Empirical Risk Minimization

The section applies the privacy framework to empirical risk minimization through randomly stopped projected noisy SGD (PNSGD), deriving a direct (ε, δ)-DP guarantee and comparing it with guarantees obtained from Rényi differential privacy. The analysis finds tighter privacy parameters in specified learning-rate and noise ranges, with the direct guarantee depending on the learning rate.

B. Empirical Risk Minimization

  • PNSGD performs noisy projected gradient updates and returns an iterate selected by a uniformly random stopping time T from [n].The stated setup uses convex L-Lipschitz losses over a convex set; the comparison theorem additionally assumes β-smooth losses and restricts η.Source: B. Empirical Risk Minimization · pp. 21–22
  • The randomly stopped PNSGD guarantee from Corollary 5 applies for any σ > 0, while the compared theorem is restricted to σ greater than L..Source: B. Empirical Risk Minimization · pp. 21–22
  • The comparison converts the RDP guarantee of to (ε, δ)-DP using existing conversion formulas, including a tighter conversion whose δ cannot be expressed analytically.Source: B. Empirical Risk Minimization · pp. 22–23
  • For randomly-stopped PNSGD, Corollary 5 gives tighter privacy parameters than for η ∈ (0.05, 0.1) for all ε ≥ 2, provided σ ≥ 3.The privacy improvement over is more pronounced for smaller values of ησ.Source: B. Empirical Risk Minimization · p. 23
  • Unlike the comparison based on, Corollary 5’s privacy parameter depends heavily on η, and δ decreases as η increases for fixed ε.Source: B. Empirical Risk Minimization · p. 23

C. Online Gradient Descent Algorithm

The section applies the privacy analysis to online gradient descent (OGD) and examines its privacy–utility trade-off using stochastic regret. Under the stated learning-rate schedule, non-trivial privacy and utility require noise magnitudes to increase, but at a rate slower than √t.

C. Online Gradient Descent Algorithm

  • The analysis combines the privacy guarantee for OGD with a standard online-convex-optimization regret result to characterize the privacy–utility balance.Source: C. Online Gradient Descent Algorithm · pp. 23–24
  • The section evaluates utility using stochastic regret for randomly stopped OGD, assuming independent cost functions sampled from a distribution and uniformly bounded gradients.The regret expectation includes the randomness in stopping time T.Source: C. Online Gradient Descent Algorithm · p. 24
  • With η_t = O(1/√t), a necessary condition for non-trivial privacy and utility is σ_t → ∞ while σ_t√t → 0.Thus the noise sequence must increase more slowly than 1/√t decreases.Source: C. Online Gradient Descent Algorithm · p. 24

APPENDIX

The appendix proves Theorem 2 by bounding the divergence after a channel and establishing the reverse inequality using point-mass inputs. It then uses Theorem 2 and monotonicity of θ_γ to prove Proposition 1.

A. Proof of Theorem 2

  • For γ > 1, the proof uses the Hahn–Jordan decomposition of μ − γν to bound the output divergence after applying a channel.It establishes the reverse inequality by choosing distinct point-mass inputs, whose channel outputs are the corresponding conditional distributions.Source: A. Proof of Theorem 2 · pp. 29–31
  • For γ ∈ (0, 1), the proof relates E_γ(μ∥ν) to E_1/γ(ν∥μ), then applies the divergence definitions to complete the equality argument.Source: A. Proof of Theorem 2 · p. 31

B. Proof of Proposition 1

C. Proof of Lemma 4

The appendix proves Lemma 4 using Pinsker’s inequality and the KL-divergence chain rule. It proves Corollary 2 by constructing a pair of distributions and applying Le Cam’s bound to their mechanism outputs.

C. Proof of Lemma 4

  • The proof of Lemma 4 uses Pinsker’s inequality and the KL-divergence chain rule to bound the distance between the output distributions.Source: C. Proof of Lemma 4 · p. 32

D. Proof of Corollary 2

  • The proof of Corollary 2 constructs two distributions in the specified class, composes the LDP mechanisms, and applies Le Cam’s bound using total variation bounded by Hellinger distance.Source: D. Proof of Corollary 2 · p. 32

E. Proof of Lemma 5

These proof passages connect privacy contraction bounds to estimation and testing results, then apply contraction arguments to an iterative process with constrained additive Gaussian kernels. Several displayed derivations are omitted, so the supplied text supports the proof steps and conclusions only at a high level.

E. Proof of Lemma 5

  • The proof invokes Theorem 3 for each conditional kernel K_i in Q_{ε,δ}, after using Pinsker’s inequality and KL-divergence tensorization.The passage identifies these as steps in the proof of Lemma 5.Source: E. Proof of Lemma 5 · p. 33

F. Proof of Theorem 4

  • For estimation, the proof bounds the probability of a low-loss event using E_γ divergence and the contraction coefficient of the privacy mechanism.It uses data processing for I_γ, then applies η_{e^ε}(P_{Z^n|X^n}) ≤ ϕ_n(ε,δ) when n > 1.Source: F. Proof of Theorem 4 · pp. 33–34

G. Proof of Corollary 4

  • The hypothesis-testing proof applies the Chernoff–Stein lemma to the non-private trade-off and then invokes (53) and (19) for an (ε,δ)-LDP product mechanism.The supplied passages do not state the resulting trade-off expression.Source: G. Proof of Corollary 4 · p. 34

H. Proof of Theorem 5

  • Theorem 5’s proof analyzes an iterative process whose steps use Ψ_{f_t}(W)-constrained additive Gaussian kernels, combining Jensen’s inequality, data processing, and Lemma 3.The proof says that substituting its intermediate bounds into (55) yields the claimed result.Source: H. Proof of Theorem 5 · p. 35

I. Proof of Theorem 6

Theorem 6’s proof bounds divergence for neighboring collections of cost functions by averaging over the differing index and using contraction. Its corollary applies that theorem to PNSGD to obtain a differential privacy guarantee.

I. Proof of Theorem 6

  • For neighboring cost-function collections differing at index i, the proof averages over a uniform index T and bounds each summand using inequality (31).Convexity of E_γ divergence and Jensen’s inequality are used in the averaging argument.Source: §I · pp. 35–36
  • Theorem 6 derives (33) and (34), using the monotonicity of θ_γ to obtain the latter bound.The proof connects the intermediate bound to Definition 4.Source: §I · p. 36

J. Proof of Corollary 5

  • Applying Theorem 6 to PNSGD yields an (ε,δ)-differential privacy guarantee for ε ≥ 0.The supplied passage does not give the corresponding δ expression.Source: J. Proof of Corollary 5 · p. 36

K. Missing proof of Section IV-B

The missing proof for Section IV-B establishes a Lipschitz property of the gradient update under convexity and smoothness assumptions. The proposition proof uses convexity and independence to analyze the iterative update.

K. Missing proof of Section IV-B

  • For convex, β-smooth f, the proof establishes that G(w) = w − η∇f(w) is 1-Lipschitz when η ≤ 2 β.It invokes Lemma 3.11 in in the argument.Source: K. Missing proof of Section IV-B · p. 37
  • The proof of (36) uses that x(w) is 1-Lipschitz for all x ∈ X and modifies the earlier Corollary 5 argument.The passage says this modified bound is combined with (61) to obtain (36).Source: K. Missing proof of Section IV-B · p. 37

L. Proof of Proposition 2

  • For Proposition 2, the proof uses convexity of the expected cost and independence of f_t and Z_t from W_t to analyze the update-rule inner product.It also defines 1/η_0 = 0 and uses η_t = diam(W)/t.Source: L. Proof of Proposition 2 · pp. 38–39

Related papers

Loading 2012.11035v2…