Additive noise mechanisms

From Justapedia, unleashing the power of collective wisdom
Jump to navigation Jump to search

Adding controlled noise from predetermined distributions is a way of designing differentially private mechanisms. This technique is useful for designing private mechanisms for real-valued functions on sensitive data. Some commonly used distributions for adding noise include Laplace and Gaussian distributions.

Definitions

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{D}} be a collection of all datasets and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:\mathcal{D} \to \R} be a real-valued function. The sensitivity [1] of a function, denoted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta f} , is defined by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta f=\max | f(x)-f(y) |,}

where the maximum is over all pairs of datasets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{D}} differing in at most one element. For functions with higher dimensions, the sensitivity is usually measured under Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_1} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_2} norms.

Throughout this article, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{M}} is used to denote a randomized algorithm that releases a sensitive function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} under the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} - (or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\epsilon,\delta)} -) differential privacy.

Mechanisms for Real-Valued Functions

Laplace Mechanism

Introduced by Dwork et al.,[1] this mechanism adds noise drawn from a Laplace distribution:

Laplace mechanism offering .5-differential privacy for a function with sensitivity 1.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{M}_\mathrm{Lap}(x,f,\epsilon) = f(x) + \mathrm{Lap}\left(\mu = 0, b = \frac{\Delta f}{\epsilon}\right),}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} is the expectation of the Laplace distribution and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} is the scale parameter. Roughly speaking, a small-scale noise should suffice for a weak privacy constraint (corresponding to a large value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} ), while a greater level of noise would provide a greater degree of uncertainty in what was the original input (corresponding to a small value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} ).

To argue that the mechanism satisfies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} -differential privacy, it suffices to show that the output distribution of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{M}_\mathrm{Lap}(x,f,\epsilon)} is close in a multiplicative sense to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{M}_\mathrm{Lap}(y,f,\epsilon)} everywhere.Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \frac{\mathrm{Pr}(\mathcal{M}_\mathrm{Lap}(x,f,\epsilon) = z)}{\mathrm{Pr}(\mathcal{M}_\mathrm{Lap}(y,f,\epsilon) = z)} &= \frac{\mathrm{Pr}(f(x) + \mathrm{Lap}(0,\frac{\Delta f}{\epsilon}) = z)}{\mathrm{Pr}(f(y) + \mathrm{Lap}(0,\frac{\Delta f}{\epsilon}) = z)}\\ &= \frac{\mathrm{Pr}(\mathrm{Lap}(0, \frac{\Delta f}{\epsilon}) = z-f(x))}{\mathrm{Pr}(\mathrm{Lap}(0,\frac{\Delta f}{\epsilon}) = z-f(y))}\\ &= \frac{\frac{1}{2b}\exp\left(- \frac{|z-f(x)|}{b}\right)}{\frac{1}{2b}\exp\left(- \frac{|z-f(y)|}{b}\right)}\\ &= \exp\left(\frac{|z-f(y)|-|z-f(x)|}{b}\right)\\ &\leq \exp\left(\frac{|f(y)-f(x)|}{b}\right)\\ &\leq \exp\left(\frac{\Delta f}{b}\right) = \exp(\epsilon). \end{align} } The first inequality follows from the triangle inequality and the second from the sensitivity bound. A similar argument gives a lower bound of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exp(-\epsilon)} .

A discrete variant of the Laplace mechanism, called the geometric mechanism, is universally utility-maximizing.[2] It means that for any prior (such as auxiliary information or beliefs about data distributions) and any symmetric and monotone univariate loss function, the expected loss of any differentially private mechanism can be matched or improved by running the geometric mechanism followed by a data-independent post-processing transformation. The result also holds for minimax (risk-averse) consumers.[3] No such universal mechanism exists for multi-variate loss functions.[4]

Gaussian Mechanism

Analogous to Laplace mechanism, Gaussian mechanism adds noise drawn from a Gaussian distribution whose variance is calibrated according to the sensitivity and privacy parameters. For any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta\in(0,1)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon\in(0,1)} , the mechanism defined by:

Gaussian mechanism.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{M}_\text{Gauss}(x, f, \epsilon, \delta) = f(x) + \mathcal{N}\left(\mu = 0, \sigma^2 = \frac{2 \ln (1.25/\delta) \cdot (\Delta f)^2}{\epsilon^2}\right) }

provides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\epsilon,\delta)} -differential privacy.

Note that, unlike Laplace mechanism, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{M}_\text{Gauss}} only satisfies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\epsilon, \delta)} -differential privacy with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon<1} . To prove so, it is sufficient to show that, with probability at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1-\delta} , the distribution of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{M}_\text{Gauss}(x, f, \epsilon, \delta)} is close to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{M}_\text{Gauss}(y, f, \epsilon, \delta)} . The proof is a little more involved (see Appendix A in Dwork and Roth[5]).

Mechanisms for High Dimensional Functions

For high dimensional functions of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:\mathcal{D} \to \R^d} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d \geq 2} , the sensitivity of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is measured under Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_1} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_2} norms. The equivalent Gaussian mechanism that satisfies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\epsilon, \delta)} -differential privacy for such function (still under the assumption that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon<1} ) is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{M}_\text{Gauss}(x, f, \epsilon, \delta) = f(x) + \mathcal{N}^d \left(\mu = 0, \sigma^2 = \frac{2 \ln (1.25/\delta) \cdot (\Delta_2 f)^2}{\epsilon^2}\right), }

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta_2 f} represents the sensitivity of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} under Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_2} norm and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{N}^d(0, \sigma^2)} represents a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} -dimensional vector, where each coordinate is a noise sampled according to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{N}(0, \sigma^2)} independent of the other coordinates (see Appendix A in Dwork and Roth[5] for proof).

References

  1. ^ a b Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). "Calibrating Noise to Sensitivity in Private Data Analysis". Theory of Cryptography. Lecture Notes in Computer Science. 3876: 265–284. doi:10.1007/11681878_14. ISBN 978-3-540-32731-8.
  2. ^ Ghosh, Arpita; Roughgarden, Tim; Sundararajan, Mukund (2012). "Universally Utility-maximizing Privacy Mechanisms". SIAM Journal on Computing. 41 (6): 1673–1693. arXiv:0811.2841. doi:10.1137/09076828X.
  3. ^ Gupte, Mangesh; Sundararajan, Mukund (June 2010). "Universally optimal privacy mechanisms for minimax agents". Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS): 135–146. arXiv:1001.2767. doi:10.1145/1807085.1807105. ISBN 9781450300339. S2CID 11553565.
  4. ^ Brenner, Hai; Nissim, Kobbi (January 2014). "Impossibility of Differentially Private Universally Optimal Mechanisms". SIAM Journal on Computing. 43 (5): 1513–1540. arXiv:1008.0256. doi:10.1137/110846671. S2CID 17362150.
  5. ^ a b Dwork, Cynthia; Roth, Aaron (2013). "The Algorithmic Foundations of Differential Privacy" (PDF). Foundations and Trends in Theoretical Computer Science. 9 (3–4): 211–407. doi:10.1561/0400000042. ISSN 1551-305X.
Retrieved from "https://justapedia.org/index.php?title=Additive_noise_mechanisms&oldid=1100495116"