Differential Privacy without Sensitivity
Kentaro Minami(The University of Tokyo)

Hiromi Arai

(RIKEN AIP)

Issei Sato

(The University of Tokyo)

Hiroshi Nakagawa(The University of Tokyo)

Overview• Differential Privacy (DP)• A privacy protection measure [Dwork+ 06]• Differentially Private Learning• Statistical learning under differential privacy constraints• Requires some randomization of estimators• Gibbs Posterior• A natural class of distributions of randomized estimators

Contribution• A new proof for (𝜀, 𝛿)-DP (tbd.) of Gibbs posteriors• Applicable for Lipschitz convex losses & log-concave priors
2Differential Privacy [Dwork+ 06]
Adversarial Formulation of Privacy:
1. Algorithm 𝜌 releases an estimator using private data 𝒟Algorithm 𝜌Data 𝐷𝑋) 𝑋*⋯Estimator 𝜃/𝑋+3

Differential Privacy [Dwork+ 06]
Adversarial Formulation of Privacy:
2. Adversary 𝒜 has a reference data 𝒟 1 that differs from 𝒟
in a single individual (say 𝑋) ).
Adversary 𝒜 also knows how Algorithm 𝜌 works.
Algorithm 𝜌

Data 𝐷𝑋) 𝑋*
Adversary⋯Estimator 𝜃/𝑋+Reference Data 𝐷 1𝑋)1 𝑋*⋯𝑋+𝜃/ 14Differential Privacy [Dwork+ 06]
We want to make 𝜃3 and 𝜃3 1 indistinguishable for any
reference data 𝐷 1 .
Idea: Release a sufficiently randomized version of 𝜃3
Data 𝐷𝑋) 𝑋*⋯𝑋+Reference Data 𝐷 1𝑋)1 𝑋*⋯Output distributions are“statistically indistinguishable”

𝑋+
5

Differential Privacy [Dwork+ 06]

Definition:• 𝜀 > 0, 0 ≤ 𝛿 < 1 privacy parameters• Output distribution 𝜌9 satisfies (𝜀, 𝛿)-differential privacy if
1.
2.

For any pair of adjacent datasets (𝐷, 𝐷 1 ), andFor any measurable set 𝐴 ⊂ Θ in the parameter space,6

Differentially Private Learning(Classical) statistical learning:• Minimize the empirical risk 𝐿 𝜃, 𝐷 = ∑C∈9 ℓ(𝜃, 𝑥) or its
expectation
Differentially private learning:• Outputs of DP algorithms are random.
• Minimize the “expected” risk under a DP constraint:

7

Gibbs posterior
In statistics and ML, a typical data-dependent distribution is
the Bayesian posterior.

8

Gibbs posterior
In statistics and ML, a typical data-dependent distribution is
the Bayesian posterior.

Generalization: Introduce a scale parameter 𝛽 > 09Gibbs posterior
We consider a class of posterior distribution with a scale.
Definition:• ℓ: Θ×𝒳 → ℝ• 𝜋(𝜃)

Loss function
Prior distribution on Θ• 𝛽>0

Scale parameterWe define the density of Gibbs posterior 𝐺M,9 as

10

Gibbs posterior
If 𝛽 → 0, the Gibbs posterior becomes flat, and converges
to the prior.

𝛽→011

A Method for (𝜀, 0)-DPFor any function ℒ: Θ×𝒳 + → ℝ, define the sensitivity as

Exponential mechanism [McSherry & Talwar 07]
If Δℒ < ∞, an algorithm that draws 𝜃 from a distribution

satisfies (𝜀, 0)-DP, where 𝛽 > 0 is taken as

12

A Method for (𝜀, 0)-DPThe Gibbs posterior can be seen as the exponential mechanism
if it has a bounded sensitivity.
Question: When is the sensitivity bounded?
Theorem [Wang+ 15]
The Gibbs posterior can satisfy (𝜀, 0)-DP if:(A) the loss function ℓ is bounded for all 𝑥 ∈ 𝒳, or(B) the difference ℓ ⋅, 𝑥 − ℓ(⋅, 𝑥 1 ) is bounded for all 𝑥, 𝑥 1 ∈ 𝒳𝐴𝜃𝐴𝜃

13

Unbounded Loss Differences• For (𝜀, 0)-DP, the loss functions need to be bounded.
• However, many loss functions in statistical learning theory
is unbounded.
Example: The logistic regression loss
has unbounded sensitivity.
ℓ(𝜃, 𝑧, +1 )+∞ℓ(𝜃, 𝑧, −1 )𝑀𝜃14Unbounded Loss Differences• For (𝜀, 0)-DP, the loss functions need to be bounded.
• However, many loss functions in statistical learning theory
is unbounded.
Example: The logistic regression
loss
Our Goal:

Prove DP of the Gibbs posterior
has unboundedsensitivity.
whenthe loss is unbounded!
ℓ(𝜃, 𝑧, +1 )+∞ℓ(𝜃, 𝑧, −1 )𝑀𝜃15Key Idea: From Bounded to Lipschitz• In the example of logistic loss, the first derivative isbounded• The Lipschitz constant 𝐿 is not influenced by
the size of parameter space

16

Main TheoremTheorem
1. For all 𝑥 ∈ 𝒳, ℓ(⋅, 𝑥) is 𝐿-Lipschitz and convex
2. − log 𝜋(⋅) is 𝑚Z -strongly convex
3. Θ = ℝ]
The Gibbs posterior 𝐺M,9 satisfies (𝜀, 𝛿)-DP if

The upper bound does not require boundedness of ℓ!
17

Lipschitz & Convex Losses
1. Classification• Logistic regression• Hinge loss (SVM)

2. Regression• Quantile regression• Huber loss for robust regression

3. Parametric statistics• Negative log-likelihood of binomial / multinomial
distributions w.r.t. the natural parametrization of the
exponential family
18

Utility Analysis

A DP guarantee for Gibbs posteriors implies a trade-off
between privacy and learning efficiency.
Examples:
1. Statistical efficiency
2. PAC-Bayesian bound19

Statistical Efficiency• In parametric statistics, ℓ 𝜃, 𝑥 = − log 𝑝(𝑥 ∣ 𝜃)
• The Gibbs posterior is 𝛽`) times less efficient than theBayesian posterior.
Proposition (Misspecified Bernstein—von Mises)
Under some regularity conditions, 𝐺M,9 converges to anormal distribution with covariance matrix 𝑛𝛽 `) 𝐼c`)
:d20

PAC-Bayesian Bounds• The Gibbs posterior has a fundamental role in PAC-Bayes
theory [McAllester 98] [Catoni 07] [Alquier 15]• Tightness of the empirical bound is controlled by 𝛽`) .
Proposition (PAC-Bayesian bound) [Alquier 15]
Under some regularity conditions, 𝐺M,9 satisfies the following
risk boundwith probability at least 1 − 2𝜂.
21Approximation of Posteriors
In practice, sampling from the Gibbs posterior can be acomputationally hard problem.
Langevin Monte Carlo (LMC)
A variant of MCMC like a “noisy gradient descent”.
GDLMC

22

Privacy-Preserving Approximate Posterior (PPAP)If 𝐺M,9 satisfies (𝜀, 𝛿)-DP, we can also prove (𝜀, 𝛿 1 )-DP of
approximate Gibbs posterior by LMC.
Proposition:• Assume that ℓ and 𝜋 satisfy the assumption in Main
Theorem. We also assume that ℓ(⋅, 𝑥) is 𝑀-smooth forevery 𝑥 ∈ 𝒳• After 𝑂+ *h+ *log
hiterations, the output of the LMC

satisfies (𝜀, 𝛿 + 𝑒 j + 1 𝛾)-DP.
23

Conclusion• A new proof of (𝜀, 𝛿)-DP for Gibbs posteriors• Removed the boundedness assumption• Lipschitz convex losses & (strongly) log-concave priors• Properties• Easily connected to statistical efficiency / PAC-Bayesian bounds• Finite-time DP guarantee of Langevin Monte-CarloThank you!

24