0
$\begingroup$

Please explain me why global sensitivity of a mean or variance queries will be

(b-a)/n

and

(b-a)^2/n

where b is the upper bound of the data and a is the lower bound?

$\endgroup$
0
$\begingroup$

The global sensitivity is defined as $\max_{M,M'\text{ neighboring databases}}|f(M)-f(M')|$, where $f$ is your function, and "neighboring databases" typically mean "differing in at most one element". Given the formulas you give, I assume that your in use case, "neighboring" means "$M$ and $M'$ both have $n$ elements, and $n-1$ elements in common".

When $f$ is the average, assuming that all elements are between $a$ and $b$, the maximum is reached when the only differing element between $M$ and $M'$ is $a$ in one of the databases and $b$ in the other. In that case, you can easily verify that $|f(M)-f(F')|=\frac{b-a}{n}$, and similarly for when $f$ is the variance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.