Identiﬁcation Ampliﬁcation and Measurement A bridge to Gaussian Differential Privacy Yi Liu

2025-05-08 0 0 692.68KB 21 页 10玖币

侵权投诉

Identiﬁcation, Ampliﬁcation and Measurement: A

bridge to Gaussian Differential Privacy

Yi Liu

Department of Mathematical

and Statistical Sciences

University of Alberta

yliu16@ualberta.ca

Ke Sun

Department of Mathematical

and Statistical Sciences

University of Alberta

ksun6@ualberta.ca

Bei Jiang

Department of Mathematical

and Statistical Sciences

University of Alberta

bei1@ualberta.ca

Linglong Kong

Department of Mathematical

and Statistical Sciences

University of Alberta

lkong@ualberta.ca

Abstract

Gaussian differential privacy (GDP) is a single-parameter family of privacy notions

that provides coherent guarantees to avoid the exposure of sensitive individual

information. Despite the extra interpretability and tighter bounds under composi-

tion GDP provides, many widely used mechanisms (e.g., the Laplace mechanism)

inherently provide GDP guarantees but often fail to take advantage of this new

framework because their privacy guarantees were derived under a different back-

ground. In this paper, we study the asymptotic properties of privacy proﬁles and

develop a simple criterion to identify algorithms with GDP properties. We propose

an efﬁcient method for GDP algorithms to narrow down possible values of an

optimal privacy measurement, µwith an arbitrarily small and quantiﬁable margin

of error. For non GDP algorithms, we provide a post-processing procedure that can

amplify existing privacy guarantees to meet the GDP condition. As applications,

we compare two single-parameter families of privacy notions,



-DP, and

-GDP,

and show that all



-DP algorithms are intrinsically also GDP. Lastly, we show

that the combination of our measurement process and the composition theorem of

GDP is a powerful and convenient tool to handle compositions compared to the

traditional standard and advanced composition theorems.

1 Introduction

Recent years have seen explosive growth in the research and application of data-driven machine

learning. While data fuels advancement in this unprecedented age of “big data”, concern for individual

privacy has deepened with the continued mining, transportation, and exchange of this new resource.

While expressions of privacy concerns can be traced back as early as 1969 [

], the concept of privacy

is often perceived as “vague and difﬁcult to get into a right perspective” [

]. Through its alluring

convenience and promise of societal prosperity, the use of aggregated data has long outstripped the

capabilities of privacy protection measures. Indeed, early privacy protection protocols relied on the

ad hoc enforcement of anonymization and offered little to no protection against the exposure of

individual data, as evidenced by the AOL search log and Netﬂix Challenge dataset controversies

[30, 31, 6].

36th Conference on Neural Information Processing Systems (NeurIPS 2022).

arXiv:2210.09269v1 [cs.CR] 17 Oct 2022

Differential privacy (DP) ﬁrst gained traction as it met the urgent need for rigour and quantiﬁability in

privacy protection [

]. In short, DP bounds the change in the distribution of outputs of a query made

on a dataset under an alteration of one data point. The following deﬁnition formalizes this notion.

Deﬁnition 1.1

[

] A randomized algorithm

, taking a dataset consisting of individuals as its input,

(, δ)

-differentially private if, for any pair of datasets

and

that differ in the record of a single

individual and any event E,

P[A(S)∈E]≤eP[A(S0)∈E] + δ.

When δ= 0,Ais called -differentially private (-DP).

While the notion of

(, δ)

-DP has wide applications [

], there are a few notable drawbacks

to this framework. One is the poor interpretability of

(, δ)

-DP: unlike other concepts in machine

learning, DP should not remain a black box. Privacy guarantees are intended for human interpretation

and so must be understandable by the users it affects and by regulatory entities. A second drawback

(, δ)

-DP’s inferior composition properties and lack of versatility. Here, “composition” refers to

the ability for DP properties to be inherited when DP algorithms are combined and used as building

blocks. As an example, the training of deep learning models involves gradient evaluations and weight

updates: each of these steps can be treated as a building block. It is natural to expect that a DP learning

algorithm can be built using differentially-private versions of these components. However, the DP

composition properties cannot generally be well characterized within the framework of

(, δ)

-DP,

leading to very loose composition theorems.

To overcome the drawbacks of

(, δ)

-DP, numerous variants have been developed, including the

hypothesis-testing-based

-DP [

], the moments-accountant-based Rényi DP [

], as well as

concentrated DP and its variants [

]. Despite their very different perspectives, all of these DP

variants can be fully characterized by an inﬁnite union of

(, δ)

-DP guarantees. In particular, there is

a two-way embedding between

-DP and the inﬁnite union of

(, δ)

-DP guarantees: any guarantee

provided by an inﬁnite union of

(, δ)

-DP can be fully characterized by

-DP and vice visa [

Consequently, f-DP has the versatility to treat all of the above notions as special cases.

In addition to its versatility,

-DP is more interpretable than other DP paradigms because it considers

privacy protection from an attacker’s perspective. Under

-DP, an attacker is challenged with the

hypothesis-testing problem

H0:the underlying dataset is Sversus H1:the underlying dataset is S0

and given output of an algorithm

, where

and

are neighbouring datasets. The harder this

testing problem is, the less privacy leakage

has. To see this, consider the dilemma that the attacker

is facing. The attacker must reject either

based on the given output of

: this means the

attacker must select a subset

Range(A)

and reject

if the sampled output is in

(or must

otherwise reject

). The attacker is more likely to incorrectly reject

(in a type I error) when

R0is large. Conversely, if R0is small, the attacker is more likely to incorrectly reject H1(in a type

II error). We say that an algorithm

-DP if, for any

α∈[0,1]

, no attacker can simultaneously

bound the probability of type I error below αand bound the probability of type II error below f(α).

Such fis called a trade-off function and controls the strength of the privacy protection.

The versatility afforded by

can be unwieldy in practice. Although

-DP is capable of handling

composition and can embed other notions of differential privacy, it is not convenient for repre-

senting safety levels as a curve amenable to human interpretation. Gaussian differential privacy

(GDP), as a parametric family of

-DP guarantees, provides a balance between interpretability and

versatility. GDP guarantees are parameterized by a single value

and use the trade-off function

f(α)=ΦΦ−1(1 −α)−µ

, where

is the cumulative distribution function of the standard normal

distribution. With this choice of

, the hypothesis-testing problem faced by the attacker is as hard

as distinguishing between

N(0,1)

and

N(µ, 1)

on the basis of a single observation. Aside from

its visual interpretation, GDP also has unique composition theorems: the composition of a

µ1

- and

µ2

-GDP algorithm is, as expected,

pµ2

1+µ2

-GDP. This property can be easily generalized to

-fold

composition. GDP also has a special central limit theorem implying that all hypothesis-testing-based

deﬁnitions of privacy converge to GDP in terms of a limit in the number of compositions. Readers

are referred to [13] for more information.

1.1 Outline

The goal of this paper is to provide a bridge between GDP and algorithms developed under other DP

frameworks. We start by presenting an often-overlooked partial order on

(, δ)

-DP conditions induced

by logical implication. Ignoring this partial order will lead to problematic asymptotic analysis.

We then break down GDP into two parts: a head condition and a tail condition. We show that the

latter, through a single limit of a mechanism’s privacy proﬁle, is sufﬁcient to distinguish between

GDP and non-GDP algorithms. For GDP algorithms, this criterion also provides a lower bound for the

privacy protection parameter

and can help researchers widen the set of available GDP algorithms.

This criterion furthermore gives an interesting characterization of GDP without an explicit reference

to the Gaussian distribution.

The next logical step is to measure the exact privacy performance. Interestingly, while the binary

“GDP or not” question can be answered solely by the tail, the actual performance of a DP algorithm

is determined by the head. We deﬁne and apply the Gaussian Differential Privacy Transformation

(GDPT) to narrow the set of potential optimal values of

with an arbitrarily small and quantiﬁable

margin of error. We further provide procedure to adapt an algorithm to GDP or improve the privacy

parameter when results from the GDP identiﬁcation and measurement procedures are undesirable.

Lastly, we demonstrate additional applications of our newly developed tools. We ﬁrst make a

comparison between DP and GDP and show that any



-DP algorithm is automatically GDP. We then

show that the combination of our measurement process and the GDP composition theorem is a more

powerful and convenient tool for handling compositions relative to traditional composition theorems.

2 Privacy proﬁles and an exact partial order on (, δ)-DP conditions

The beneﬁts of DP come with a price. As outlined in the deﬁnition of DP, any DP algorithm must be

randomized. This randomization is usually achieved by perturbing the intermediate step or the ﬁnal

output via the injection of random noise. Because of the noise, a DP algorithm cannot faithfully output

the truth like its non DP counterpart. To provide a higher level of privacy protection, a stronger utility

compromise should be made. This leads to the paramount problem of the “privacy–utility trade-off”.

Under the

(, δ)

-DP framework, this trade-off is often characterized in a form of

σ=f(, δ)

: to

achieve

(, δ)

-DP, the utility parameter (usually the scale of noise) needs to be chosen as

f(, δ)

Therefore, an algorithm can be

(, δ)

-DP for multiple pairs of



and

: the union of all such pairs

provides a complete image of the algorithm under the

(, δ)

-DP framework. In particular, an

(, δ)

-DP

mechanism

is also

(0, δ0)

-DP for any

0≥

and any

δ0≥δ

. The inﬁnite union of

(, δ)

pairs

can thus be represented as the smallest

associated with each



. This intuition is formulated as a

privacy proﬁle in [5]. The privacy proﬁle corresponding to a collection of (, δ)-DP guarantees Ωis

deﬁned as the curve in

[0,∞)×[0,1]

separating the space of privacy parameters into two regions,

one of which contains exactly the pairs in

Ω

. The privacy proﬁle provides as much information as

Ω

itself. Many privacy guarantees and privacy notions, including

(, δ)

-DP, Rényi DP,

-DP, GDP, and

concentrated DP, can be embedded into a family of privacy proﬁle curves and fully characterized [

A privacy proﬁle can be provided or derived by an algorithm’s designer or users.

Before proceeding with detailed discussions, we ﬁrst give three examples of DP algorithms that are

used throughout the paper. The ﬁrst example we consider is the Laplace mechanism, a classical DP

mechanism whose prototype is discussed in the paper that originally deﬁned the concept of differential

privacy [

]. The level of privacy that the Laplace mechanism can provide is determined by the

scale

of the added Laplacian noise. Given a global sensitivity

∆

, the value of

needs to be chosen

f(, 0) = ∆/

in order to provide an

(, 0)

-DP guarantee. Despite its long history, the Laplace

mechanism has remained in use and study in recent years [

]. Our second example is

a family of algorithms in which a noise parameter has the form

σ=A−1plog(B/δ)

. Examples

include: the goodness of ﬁt algorithm [

], noisy stochastic gradient descent and its variants [

]

and the one-shot spectral method and the one-shot Laplace algorithm [

]. Our third example comes

from the ﬁeld of federated learning: given

users and the number of messages

, the invisibility

cloak encoder algorithm (ICEA) from [

] is

(, δ)

-DP if

m > 10 log(n/(δ))

[

]. See also [

]

for other analysis of ICEA.

For ﬁgures and numerical demonstrations in this paper, we use

b= 2/∆

for the Laplace mechanism;

A= 2

B= 1

, and

σ= 2

for the second example, which we refer to as SGD; and

m= 20

and

n= 4

for the ICEA. We omit the internal details of these methods and focus on their privacy

guarantees: other than for the classical Laplace mechanism, whose privacy proﬁle is known [

privacy guarantees are given in the form of a privacy–utility trade-off equation

σ=g(, δ)

. Given

, it is tempting to derive the privacy proﬁle by inverting

(i.e., as

δA() = min{δ|σ=g(, δ)}

)

because an

(0, δ0)

-DP algorithm is trivially

(, δ)

-DP for any

≥0

and

δ≥δ0

. However, in

most cases, a privacy proﬁle naively derived in this way is not tight and will lead to a problematic

asymptotic analysis, especially near the origin, because of a frequently overlooked partial order

between (, δ)-DP conditions below.

Theorem 2.1

Assume that

0≥0

and

0≤δ0<1

. The

(0, δ0)

-DP condition implies

(, δ)

-DP if

and only if δ≥δ0+ (1 −δ0)(e0−e)+/(1 + e0).

Theorem 2.1 states the exact partial order of logical implication on

(, δ)

-DP conditions. Though not

being explicitly discussed in this form in previous literature on DP, this partial order can be implicitly

derived from other results (e.g. proposition 2.11 of [

]). Taking this partial order into account, the

privacy proﬁle derived from the naive inversion of the trade-off function can be reﬁned into

δA() = min δ|σ=g(0, δ0)and δ≥δ0+(1 −δ0)(e0−e)+

1 + e0.

Intuitively, the reﬁned privacy proﬁle not only considers

(, δ)

-DP provided directly by the trade-off

function but also takes all pairs

(, δ)

inferred by corollary 2.1. See ﬁgure 1 for comparsion before

and after this reﬁnement.

3 The identiﬁcation of GDP algorithms

We next show the connection between GDP and the privacy proﬁle: brieﬂy, Gaussian differential

privacy can be characterized as an inﬁnite union of (, δ)-DP conditions.

Theorem 3.1

([Corollary 2.13 [

]) A mechanism is

-GDP if and only if it is

(, δµ())

-DP for all

≥0, where

δµ() = Φ −

µ+µ

2−eΦ−

µ−µ

2.(1)

This result follows from properties of

-DP. Prior to this general form, a expression for a special case

appeared in [

]. From the deﬁnition of the privacy proﬁle, it follows immediately that an algorithm

with the privacy proﬁle

δA

-GDP if and only if

δµ()≥δA()

for all non-negative



. However,

this observation does not automatically lead to a meaningful way to identify GDP algorithms.

Before proceeding with an analysis of privacy proﬁles, we give a few visual examples in Figure 1.

The left side of1 illustrates the privacy proﬁles of our examples. That of the Laplace mechanism is

derived in [

] as Theorem 3: given a noise parameter

and a global sensitivity

∆

, the privacy proﬁle

of the Laplace mechanism is

δ() = max(1 −exp{ε/2−∆/(2b)},0)

. For the second and the third

examples, we compare the naive privacy proﬁles obtained by inverting the trade-off function with

the reﬁned privacy proﬁles. The reﬁned and naive privacy proﬁles take on notably different values

around

= 0

. The inverted trade-off functions suggest that

(0, δ)

cannot be achieved by any choice

of parameter σ. However, this is clearly not true, considering Theorem 2.1.

As shown in right side of Figure 1, the Laplace mechanism’s privacy proﬁle is below the 2-GDP and

4-GDP curves but crosses the 1-GDP curve, indicating that the Laplace mechanism in this case is

2-GDP and 4-GDP but not 1-GDP. The ICEA curve intersects all of the displayed GDP curves, so the

algorithm is not

-GDP for

µ∈ {1,2,4}

. It is hard to tell whether or not the SGD curve crosses the

1-GDP curve and we cannot say if it will cross the 2-GDP or even the 4-GDP curve at a large value of



. These examples illustrate that we cannot draw conclusions simply by looking at a graph. A privacy

proﬁle is deﬁned on

[0,∞)

, so it is hard to tell if an inequality is maintained as



increases. Previous

failures of ad hoc attempts at privacy have taught that privacy must be protected via tractable and

objective means [30, 31, 6].

Performing this check via numerical evaluation yields similar problems: we cannot consider all values



on an inﬁnite interval (or even a ﬁnite one, for that matter). Turning to closed forms for privacy

proﬁles and

δµ

is also difﬁcult: even if a given privacy proﬁle is easy to handle,

δµ

presents some

technical hurdles. The proﬁle

δµ

and

are transcendental with different asymptotic behaviors for

Figure 1: Left: Examples of privacy proﬁles obtained by inverting the trade-off function (naive) and

by Theorem 2.1 (reﬁned). Right: Comparison of 1-GDP and 2-GDP privacy proﬁles against those for

our three examples.

different values of

and



. This is clear from the Figure 1: near

= 0

δµ

is concave for

µ= 4

but

convex for

µ= 1

. As a further complication, both the ﬁrst and second terms in the deﬁnition of

δµ

converge to

→ ∞

, but the difference between them vanishes. Subtracting good approximations

of two nearby numbers may cause a phenomenon called catastrophic cancellation and lead to very

bad approximations [

]. Due to the risk of catastrophic cancellation, a good approximation of

does not guarantee a good approximation of the GDP privacy proﬁle. These problems make it

difﬁcult to tightly bound δµby a function with a simple form.

To address the problem of differing asymptotic behaviours, we deﬁne the following two notions.

Deﬁnition 3.1

(Head condition) An algorithm

with the privacy proﬁle

δA

(h, µ)

-head GDP if

and only if δA()≤δµ()when ≤h.

Deﬁnition 3.2

(Tail condition) An algorithm

with the privacy proﬁle

δA

(t, µ)

-tail GDP if and

only if δA()≤δµ()when >t.

The head condition checks the

-GDP condition for



near zero and the tail condition checks the

-GDP condition for



far away from zero. As such, the combination of

(, µ)

-head GDP and

(, µ)

-tail GDP is equivalent to

-GDP. For now, we put the exact value of

aside and consider only

the qualitative question of how to identify a GDP algorithm by its privacy proﬁle. The following

theorem answers this question.

Theorem 3.2 An algorithm Ais GDP if and only if Ais (, µ)-tail GDP for any ﬁnite and µ.

Interestingly, only the tail condition ﬁgures into the identiﬁcation problem. The reason for this

stems from theorem 2.1. Any nontrivial

(, δ)

-DP algorithm must be

(0, δ)

-DP for some

δ < 1

and

therefore must satisfy a head condition for some sufﬁciently large

. The only problem left is the

tail. However, it is not possible to check whether

δ()< δµ()

for all values of



. To circumvent this

issue, we present a key lemma that underlies much of the theoretical analysis in this section and may

continue to be useful in future developments.

Lemma 3.1 Deﬁne ˜

δµ() = µe−a2/2

√2πa2, where a=−

µ+µ

2. It follows that lim

→+∞

δµ()

δµ()= 1.

Using the key lemma above, a condition for identifying GDP algorithms is simple to formulate:

Theorem 3.3

Let

µt=qlim

→+∞

2

−2 log δA()

. An algorithm

with the privacy proﬁle

δA()

µ-GDP if and only if µt<∞and µis no smaller than µt.

Theorems 3.2 and 3.3 give a useful criterion characterizing GDP and deepen our understanding of

GDP. Putting the exact value of

aside, a GDP algorithm must provide an inﬁnite union of

(, δ)

-DP

conditions, where δmust be O(e−2)as → ∞. Refer to Appendices B.3 for proofs of Theorems.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Identication,AmplicationandMeasurement:AbridgetoGaussianDifferentialPrivacyYiLiuDepartmentofMathematicalandStatisticalSciencesUniversityofAlbertayliu16@ualberta.caKeSunDepartmentofMathematicalandStatisticalSciencesUniversityofAlbertaksun6@ualberta.caBeiJiangDepartmentofMathematicalandStatisticalSc...

展开>> 收起<<

Identiﬁcation Ampliﬁcation and Measurement A bridge to Gaussian Differential Privacy Yi Liu.pdf

共21页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Identiﬁcation Ampliﬁcation and Measurement A bridge to Gaussian Differential Privacy Yi Liu

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: