What are global sensitivity and local sensitivity in differential privacy?

Question

I am learning differential privacy now, and there is no one surrounding I can ask questions about differential privacy. I am confused about the definitions of the global sensitivity and local sensitivity.

The two definitions are from the book 《Differential Privacy and Applications》written by Tianqing Zhu, Gang Li, Wanlei Zhou, Philip S. Yu.

My understanding is:

The neighbor database only has one different record to the original database.

For the definition of global sensitivity, if $f=\sum x_i$, $x_i\in \{0,1\}$, the global sensitivity is the max value of $\sum |f(D)-f(D')|, D'\in D^n-D$, and there is only one different record between neighbor databases, so it equals to the max value among $|f(D)-f(D')|$, is obvious 1.

I am not if my understanding is right.

And how to understand local sensitivity?

Answer 1

I have read the reference to the definition in Zhu's book. The paper is 《Smooth Sensitivity and Sampling in Private Data Analysis》, which gives more distinct definitons of global sensitivity and local sensitivity[1].

Obviously, $GS_f=max_{x}LS_f(x)$

[1] K. Nissim, S. Raskhodnikova, and A. Smith, “Smooth sensitivity and sampling in private data analysis,” Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC 07, 2007.

Answer 2

Global Sensitivity (GS) depends only on the function f. When trying to figure out the GS of function f, we examine all possible pairs of neighboring datasets in the domain of the function f.

Local Sensitivity (LS) depends on both the function f and the data set at hand D (known as an instance). When trying to figure out the LS of (f, D), we only examine a subset of all possible pairs of neighboring datasets, holding one of the dataset constant at D.