Mdthbs

How would two worlds first establish an exchange rate between their currencies

How can I fix a framing mistake so I can drywall?

Matrices upper triangular alignment

Gas pipes - why does gas burn "outwards?"

Two different colors in an Illustrator stroke / line

Was Robin Hood's point of view ethically sound?

Procedure for traffic not in sight

SCOTUS - Can Congress overrule Marbury v. Madison by statute?

Writing a love interest for my hero

A medieval fantasy adventurer lights a torch in a 100% pure oxygen room. What happens?

Wrathful Smite, and the term 'Creature'

Job offer without any details but asking me to withdraw other applications - is it normal?

Determining if file in projected or geographic coordinates using ArcGIS Desktop?

Does the word “uzi” need to be capitalized?

Number of aircraft to operate in an airline company

Does the mana ability restriction of Pithing Needle refer to the cost or the effect of an activated ability?

Do Milankovitch Cycles fully explain climate change?

How can "life" insurance prevent the cheapening of death?

How do I politely hint customers to leave my store, without pretending to need leave store myself?

Using the Fruit soaked in vodka

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

What was the first LISP compiler?

Is there a "right" way to interpret a novel? If so, how do we make sure our novel is interpreted correctly?

What is the use of FullForm in Mathematica?

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

$$frac{Pr(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 5 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 11 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

$$frac{Pr(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 5 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 11 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

$$frac{Pr(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 5 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 11 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 5 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 11 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 5 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 11 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 5 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

edited 5 hours ago

Clement C.

2,6551717 silver badges4242 bronze badges

asked 11 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 11 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( frac{Pr[A(D) = a]}{Pr[A(D') = a]}right).
$$
Then, the expectation $mathbb{E}[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 10 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( frac{Pr[A(D) = a]}{Pr[A(D') = a]}right).
$$
Then, the expectation $mathbb{E}[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 10 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( frac{Pr[A(D) = a]}{Pr[A(D') = a]}right).
$$
Then, the expectation $mathbb{E}[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 10 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( frac{Pr[A(D) = a]}{Pr[A(D') = a]}right).
$$
Then, the expectation $mathbb{E}[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 10 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges

$endgroup$

share|cite|improve this answer

answered 10 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges

answered 10 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges

answered 10 hours ago

Sasho NikolovSasho Nikolov

16.7k22 gold badges5555 silver badges9999 bronze badges