0
$\begingroup$

I am reading Section 4.1 (An offline algorithm: SmallDB) of The Algorithmic Foundations of Differential Privacy by Dwork and Roth. I am stuck at the proof of Proposition 4.4, which is about the utility guarantee of the small database mechanism (Algorithm 4 in page 70).

Proposition 4.4. Let $\mathcal{Q}$ be any class of linear queries. Let $y$ be the database output by SmallDB($x,\mathcal{Q},\epsilon,\alpha$). Then with probability $1-\beta$: $$ \max_{f\in\mathcal{Q}}|f(x)-f(y)|\le\alpha+\frac{2\left(\frac{\log|\mathcal{X}|\log|\mathcal{Q}|}{\alpha^2}+\log\left(\frac{1}{\beta}\right)\right)}{\epsilon\|x\|_1}. $$ Proof. Applying the utility bounds for the exponential mechanism (Theorem 3.11) with $\Delta u=\frac{1}{\|x\|_1}$ and $\text{OPT}_q(x)\le\alpha$ (which follows from Theorem 4.2), we find: $$ \Pr\left[\max_{f\in\mathcal{Q}}|f(x)-f(y)|\ge\alpha+\frac{2}{\epsilon\|x\|_1}\left(\log|\mathcal{R}|+t\right)\right]\le e^{-t}. $$

Here $\mathcal{R}=\{y\in\mathbb{N}^{|\mathcal{X}|}:\|y\|_1=\log|\mathcal{Q}|/\alpha^2\}$ is the collection of small databases, and $u:\mathbb{N}^{|\mathcal{X}|}\times\mathcal{R}\to\mathbb{R}$ is given by $$ u(x,y)=-\max_{f\in\mathcal{Q}}|f(x)-f(y)|, $$ which measures the similarity between an arbitrary database $x$ and a small database $y\in\mathcal{R}$.

My question: Why is $\Delta u=1/\|x\|_1$? According to page 38, $\Delta u$ is defined by $$ \Delta u=\max_{y\in\mathcal{R}}\max_{\|x-x'\|_1\le 1}|u(x,y)-u(x',y)|, $$ so $\Delta u$ should not depend on the size of any database $x$.

$\endgroup$

1 Answer 1

0
$\begingroup$

I think that Proposition 4.4 states a bound for normalized linear queries, hence counting queries of the form

$$f(x) = \dfrac{1}{||x||_1}\sum_{i=1}^{|\mathcal{X}|}x_i f(\mathcal{X}_i).$$

In this way, by using the neighboring definition of one different user (so the neighboring databases have the same size $||x||_1$ but they differ by one row), the utility function $u(x,y)$ takes the normalization factor in its global sensitivity from the function $f$.

$$\Delta u = \max_{y\in \mathcal{R}}\max_{||x-x'||_1\leq 1}|u(x,y)-u(x',y)| = \max_{y\in \mathcal{R}}\max_{||x-x'||_1\leq 1}\dfrac{1}{||x||_1}|\tilde{u}(x,y)-\tilde{u}(x',y)| =\dfrac{1}{||x||_1},$$

where $\tilde{u}$ is the un-normalized version of $u$, hence a counting queries with sensitivity 1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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