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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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.
