Xjyuk

Could the government trigger by-elections to regain a majority?

Why is differential privacy defined over the exponential function?

Is there a basic list of ways in which a low-level Rogue can get advantage for sneak attack?

Will replacing a fake visa with a different fake visa cause me problems when applying for a legal study permit?

How to create a list of dictionaries from a dictionary with lists of different lengths

Tear out when plate making w/ a router

Is English tonal for some words, like "permit"?

How accurate is the new appraisal system?

How can I protect myself in case of a human attack like the murders of the hikers Jespersen and Ueland in Morocco?

I see your BIDMAS and raise you a BADMIS

Improbable Inequalities

What's the biggest difference between these two photos?

Awesomism and its awesome gods

Why would thermal imaging be used to locate the Chandrayaan-2 lander?

Are scroll bars dead in 2019?

Why was "leaping into the river" a valid trial outcome to prove one's innocence?

Calculate time difference between two dates

Why are some Mac apps not available on AppStore?

Is there any detail about ambulances in Star Wars?

How to split a string by the third .(dot) delimiter

Has any object launched from Earth gone into the Sun?

Are programming languages necessary/useful for operations research practitioner?

Georgian capital letter “Ⴒ” (“tar”) in pdfLaTeX

2.5 year old daughter refuses to take medicine

Why is differential privacy defined over the exponential function?

Estimator for sum of independent and identically distributed (iid) variablesWhat is a probabilistic function and where can I learn more about them?Exponential Concentration Inequality for Higher-order moments of Gaussian Random VariablesDifferential Privacy and Randomized Responses for Counting QueriesUnderstanding proof of Theorem 3.3 in Karp's “Probabilistic Recurrence Relations”Relation between variance and mutual informationJanson-type inequality, limited dependenceHeterogeneous Hoeffding/McDiarmidEmpirical Rademacher averages versus Hoeffdings bound

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

1

$begingroup$

For adjacent database $D,D'$, a randomized algorithm $A$ is $varepsilon$-differential private when the following satisfies

$$fracPr(A(D) in S)Pr(A(D') in S) leq e^varepsilon,$$ where $S$ is any range of A.

Why is the exponential function is used for the upper bounding?

Is that related to Chernoff's inequality? Since most of the textbooks that I have ever seen do not explain why the exponential is used, I have no idea about that.

pr.probability definitions privacy

share|cite|improve this question

edited 3 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 9 hours ago

user9414424user9414424

1122 bronze badges

New contributor

user9414424 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

1

$begingroup$

For adjacent database $D,D'$, a randomized algorithm $A$ is $varepsilon$-differential private when the following satisfies

$$fracPr(A(D) in S)Pr(A(D') in S) leq e^varepsilon,$$ where $S$ is any range of A.

Why is the exponential function is used for the upper bounding?

Is that related to Chernoff's inequality? Since most of the textbooks that I have ever seen do not explain why the exponential is used, I have no idea about that.

pr.probability definitions privacy

share|cite|improve this question

edited 3 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 9 hours ago

user9414424user9414424

1122 bronze badges

New contributor

user9414424 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

$begingroup$

For adjacent database $D,D'$, a randomized algorithm $A$ is $varepsilon$-differential private when the following satisfies

$$fracPr(A(D) in S)Pr(A(D') in S) leq e^varepsilon,$$ where $S$ is any range of A.

Why is the exponential function is used for the upper bounding?

Is that related to Chernoff's inequality? Since most of the textbooks that I have ever seen do not explain why the exponential is used, I have no idea about that.

pr.probability definitions privacy

share|cite|improve this question

edited 3 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 9 hours ago

user9414424user9414424

1122 bronze badges

New contributor

user9414424 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

edited 3 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 9 hours ago

user9414424user9414424

1122 bronze badges

New contributor

user9414424 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

edited 3 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 9 hours ago

user9414424user9414424

1122 bronze badges

New contributor

user9414424 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited 3 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

edited 3 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 9 hours ago

user9414424user9414424

1122 bronze badges

New contributor

user9414424 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 9 hours ago

user9414424user9414424

1122 bronze badges

1 Answer
1

active

oldest

votes

4

$begingroup$

This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties:

• Composition: If $A(cdot)$ is an $varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(cdot, a)$ is an $varepsilon'$-DP algorithm, then the composed algorithm $A' circ A$, defined by $A'circ A(D) = A'(D, A(D))$, is $(varepsilon + varepsilon')$-DP.




• Group Privacy: If $A$ is $varepsilon$-DP, then it satisfies $kvarepsilon$-DP on pairs of data sets that differ in at most $k$ data points.

It may be more natural to define $varepsilon$-DP with $(1+varepsilon)$ in place of $e^varepsilon$, but then the formulas above would be far less nice. There is no real connection with Chernoff bounds here.

Another reason is that this definition makes it more clear how the differential privacy definition is related to divergences between distributions. To see what I mean, let me define the privacy loss of an output $a$ of an algorithm $A$ (with respect to datasets $D$ and $D'$) as
$$
ell_D, D'(a) = logleft( fracPr[A(D) = a]Pr[A(D') = a]right).
$$
Then, the expectation $mathbbE[ell_D, D'(A(D))]$ is simply the KL-divergence between $A(D)$ and $A(D')$. The differential privacy condition asks that this KL-divergence is bounded by $varepsilon$, but in fact it asks much more: that the random variable $ell_D, D'(A(D))$ is bounded by $varepsilon$ everywhere in its support. There are also intermediate definitions which put bounds on moments of $ell_D, D'(A(D))$, and correspond to bounding Renyi divergences between $A(D)$ and $A(D')$.

share|cite|improve this answer

answered 8 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "114"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

user9414424 is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f44507%2fwhy-is-differential-privacy-defined-over-the-exponential-function%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties:

• Composition: If $A(cdot)$ is an $varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(cdot, a)$ is an $varepsilon'$-DP algorithm, then the composed algorithm $A' circ A$, defined by $A'circ A(D) = A'(D, A(D))$, is $(varepsilon + varepsilon')$-DP.




• Group Privacy: If $A$ is $varepsilon$-DP, then it satisfies $kvarepsilon$-DP on pairs of data sets that differ in at most $k$ data points.

It may be more natural to define $varepsilon$-DP with $(1+varepsilon)$ in place of $e^varepsilon$, but then the formulas above would be far less nice. There is no real connection with Chernoff bounds here.

Another reason is that this definition makes it more clear how the differential privacy definition is related to divergences between distributions. To see what I mean, let me define the privacy loss of an output $a$ of an algorithm $A$ (with respect to datasets $D$ and $D'$) as
$$
ell_D, D'(a) = logleft( fracPr[A(D) = a]Pr[A(D') = a]right).
$$
Then, the expectation $mathbbE[ell_D, D'(A(D))]$ is simply the KL-divergence between $A(D)$ and $A(D')$. The differential privacy condition asks that this KL-divergence is bounded by $varepsilon$, but in fact it asks much more: that the random variable $ell_D, D'(A(D))$ is bounded by $varepsilon$ everywhere in its support. There are also intermediate definitions which put bounds on moments of $ell_D, D'(A(D))$, and correspond to bounding Renyi divergences between $A(D)$ and $A(D')$.

share|cite|improve this answer

answered 8 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges

$endgroup$

add a comment | 

4

$begingroup$

This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties:

• Composition: If $A(cdot)$ is an $varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(cdot, a)$ is an $varepsilon'$-DP algorithm, then the composed algorithm $A' circ A$, defined by $A'circ A(D) = A'(D, A(D))$, is $(varepsilon + varepsilon')$-DP.




• Group Privacy: If $A$ is $varepsilon$-DP, then it satisfies $kvarepsilon$-DP on pairs of data sets that differ in at most $k$ data points.

It may be more natural to define $varepsilon$-DP with $(1+varepsilon)$ in place of $e^varepsilon$, but then the formulas above would be far less nice. There is no real connection with Chernoff bounds here.

Another reason is that this definition makes it more clear how the differential privacy definition is related to divergences between distributions. To see what I mean, let me define the privacy loss of an output $a$ of an algorithm $A$ (with respect to datasets $D$ and $D'$) as
$$
ell_D, D'(a) = logleft( fracPr[A(D) = a]Pr[A(D') = a]right).
$$
Then, the expectation $mathbbE[ell_D, D'(A(D))]$ is simply the KL-divergence between $A(D)$ and $A(D')$. The differential privacy condition asks that this KL-divergence is bounded by $varepsilon$, but in fact it asks much more: that the random variable $ell_D, D'(A(D))$ is bounded by $varepsilon$ everywhere in its support. There are also intermediate definitions which put bounds on moments of $ell_D, D'(A(D))$, and correspond to bounding Renyi divergences between $A(D)$ and $A(D')$.

share|cite|improve this answer

answered 8 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges

$endgroup$

add a comment | 

$begingroup$

This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties:

• Composition: If $A(cdot)$ is an $varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(cdot, a)$ is an $varepsilon'$-DP algorithm, then the composed algorithm $A' circ A$, defined by $A'circ A(D) = A'(D, A(D))$, is $(varepsilon + varepsilon')$-DP.




• Group Privacy: If $A$ is $varepsilon$-DP, then it satisfies $kvarepsilon$-DP on pairs of data sets that differ in at most $k$ data points.

It may be more natural to define $varepsilon$-DP with $(1+varepsilon)$ in place of $e^varepsilon$, but then the formulas above would be far less nice. There is no real connection with Chernoff bounds here.

Another reason is that this definition makes it more clear how the differential privacy definition is related to divergences between distributions. To see what I mean, let me define the privacy loss of an output $a$ of an algorithm $A$ (with respect to datasets $D$ and $D'$) as
$$
ell_D, D'(a) = logleft( fracPr[A(D) = a]Pr[A(D') = a]right).
$$
Then, the expectation $mathbbE[ell_D, D'(A(D))]$ is simply the KL-divergence between $A(D)$ and $A(D')$. The differential privacy condition asks that this KL-divergence is bounded by $varepsilon$, but in fact it asks much more: that the random variable $ell_D, D'(A(D))$ is bounded by $varepsilon$ everywhere in its support. There are also intermediate definitions which put bounds on moments of $ell_D, D'(A(D))$, and correspond to bounding Renyi divergences between $A(D)$ and $A(D')$.

share|cite|improve this answer

answered 8 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges

$endgroup$

share|cite|improve this answer

answered 8 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges

answered 8 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges

answered 8 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges