Sensibilidad a la privacidad diferencial

Question

Quiero verificar mis conocimientos de sensibilidad. Entonces en$\epsilon$-privacidad diferencial, el ruido se suma con el mecanismo de Laplace en función de la sensibilidad y el parámetro de pérdida de privacidad. Laplace tiene en cuenta la sensibilidad global y el ruido se escala en la norma L1, ιn$\epsilon-\delta$privacidad diferencial el ruido se agrega con un mecanismo gaussiano que considera la sensibilidad local y usa la norma L2 como métrica, ¿tengo razón o me perdí algo? Creo que quizás he confundido de alguna manera los conceptos.

Answer 1

El libro de privacidad diferencial es la referencia típica para el área, y es bastante útil aquí. Dado que esta respuesta esencialmente equivale a una cita de ese libro, explicaré cómo encontrar las cosas correctas para citar.

Ctrl + F-ing "Laplace", encontramos el Teorema 3.6, que establece que el mecanismo de Laplace es $(\epsilon,0)$-diferencialmente privado. Este mecanismo agrega iid$\mathsf{Lap}(\Delta f/\epsilon)$ ruido a la salida, donde (como mencionas): $$\Delta f = \max_{\substack{x, y\in\mathbb{N}^{|\mathcal{X}|}\\\lVert x - y\rVert_1 = 1}} \lVert f(x) - f(y)\rVert_1$$ Entonces este es el $\ell_1$ versión de la sensibilidad.

Ctrl + F-ing "Gaussiano", vemos que funciona para la sensibilidad definida a través de: $$\Delta_2 f = \max_{\substack{x, y\in\mathbb{N}^{|\mathcal{X}|}\\\lVert x - y\rVert_1 = 1}} \lVert f(x) - f(y)\rVert_2$$ Esto es un $\ell_2$ noción de sensibilidad (aunque tenga en cuenta que "conjuntos de datos vecinos" $x, y$ todavía están a 1 de cada uno en el $\ell_1$norma, lo que significa que todavía difieren como máximo en una fila). El teorema 3.22 muestra entonces que para ser$(\epsilon, \delta)$ diferencialmente privado, el mecanismo gaussiano agrega ruido iid $\mathcal{N}(0, 2\ln(1.25/\delta) \Delta_2(f)^2/\epsilon^2)$ a la salida de la función.