The Laplace Mechanism has optimal utility
for differential privacy over continuous queries

Differential Privacy (DP) concerns databases from which (database-) queries produce statistics: a database of information about people can be queried e.g. to reveal their average height, or how many of them are men. But a risk is that from a general statistic, specific information might be revealed about individuals' data: whether a specific person is a man, or his height, or even both. Differentially-private ``obfuscating'' mechanisms diminish that risk by perturbing their inputs (the raw query results) to produce outputs (the query reported) that are slightly wrong in a probabilistically unpredictable way. That diminishes the personal privacy risk (good) but also diminishes the statistics' utility (bad).

The existing optimality result is that for a mandated differential privacy parameter, some $\varepsilon{>}0$, and under conditions we will explain, the Geometric obfuscating mechanism $G^{\varepsilon}$ (depending on $\varepsilon$) loses the least utility of any $\varepsilon$-Differentially Private oblivious obfuscating mechanism for the same $\varepsilon$, that loss being caused by her having to use the perturbed statistic instead of the real one [1].

A conspicuous feature of $\varepsilon$-DP (that is $\varepsilon$-differential privacy) is that it is achieved without having to know the nature of the individual's privacy that it is protecting: it is simply made ``$\varepsilon$-difficult'' to determine whether any of his data is in the database at all. Similarly the minimisation of an observer's loss (of utility) is achieved by the optimal obfuscation without knowing precisely how the obfuscation affects her: instead, the existence of a ``loss function'' is postulated that monetises her loss (think ``dollars'') based on the raw query (which she does not know) and the obfuscated query (which she does know) — and optimality of $G^{\varepsilon}$ holds wrt. all loss functions (within certain realistic constraints) and all (other) $\varepsilon$-DP mechanisms $M^{\varepsilon}$.

in summary: The existing result states that the $\varepsilon$-DP Geometric obfuscating mechanism $G^{\varepsilon}$ minimises loss of utility to an observer when the query results are discrete, e.g. counting queries in some $(0..N)$, and certain reasonable constraints apply to the monetisation of loss. But the result does not hold when the query results are continuous, e.g. in the unit interval $[0,1]$. We show that optimality is regained by using the $\varepsilon$-DP Laplace mechanism $L^{\varepsilon}$.

Differential privacy begins with a database that is a multiset of rows drawn from some set $R$ [3]; thus the type of a database is $\mathbb{B}\kern-0.29999ptR$ (using ``$\mathbb{B}$'' for ``bag''). A query $q$ is a function from database to a query-result in some set ${\cal X}$, the input of the mechanism, and is thus of type $\mathbb{B}\kern-0.29999ptR{\mathbin{\rightarrow}}{\cal X}$.

A distance function between databases $\mbox{\sc\small d}{:}\,\mathbb{B}\kern-0.29999ptR{\times}\mathbb{B}\kern-0.29999ptR\mathbin{\rightarrow}{\mathbb{R}}$ measures how different two databases are from each other. Often used is the Hamming distance $\mbox{\sc\small d}_{H}$, ¹¹1The Hamming distance is also known as the symmetric distance. which gives (as an integer) how many whole rows would have to be removed or inserted to transform one database into another: given two databases $b_{1},b_{2}{:}\,\mathbb{B}\kern-0.29999ptR$ we define $\mbox{\sc\small d}_{H}(b_{1},b_{2})$ to be the size $\#(b_{1}\mathbin{\bigtriangleup}b_{2})$ of their (multiset-) symmetric difference. Thus in particular two databases that differ only because a row has been removed from one of them have Hamming distance 1, and we say that such databases are adjacent.

We define also a distance function (metric) between –for the moment– discrete distributions ${\mathbb{D}}{\cal Y}$ over a set of observations ${\cal Y}$ the output of the mechanism. Given two distributions $\delta_{1},\delta_{2}$ on ${\cal Y}$, their distance $\,{\textsf{\small d}_{D}}(\delta_{1},\delta_{2})$ (for ``Dwork'') is based on the largest ratio over all $Y{\subseteq}{\cal Y}$ between probabilities assigned to $Y$ by $\delta_{1}$ and $\delta_{2}$ — it is

where $\delta(Y)$ is the probability $\delta$ assigns to the whole subset $Y$ of ${\cal Y}$, and the logarithm is introduced to make the distance satisfy the triangle inequality that metrics require. ²²2This distance is also known as “max divergence”.

Following the presentation of Chatzikokolakis et al. [4], once we have chosen a metric d on databases, we say that a mechanism $M$ achieves $\varepsilon$-Differential Privacy wrt. that d and some query $q$, i.e. is $\varepsilon$-DP for $\mbox{\sc\small d},q$, just when

In the special case when d is the Hamming distance $\mbox{\sc\small d}_{H}$, the above definition becomes

With the above metric-based point of view we can say that an $\varepsilon$-DP mechanism is (simply) a $\varepsilon$-Lipschitz function from databases $\mathbb{B}\kern-0.29999ptR$ with metric d to distributions of observations ${\mathbb{D}}{\cal Y}$ with metric $\,{\textsf{\small d}_{D}}$ [4].

Counting queries on databases are the special case where the codomain ${\cal X}$ of the query (the mechanism input) is the non-negative integers and the query $q$ returns the number of database rows satisfying some criterion, like ``being a man''. The ``average height'' query is not a counting query.

When the database metric is the Hamming distance $\mbox{\sc\small d}_{H}$, a counting query can be characterised more generally as one that is a 1-Lipschitz function wrt. $d_{H}$ and the usual metric (absolute difference) on the integers, i.e. one whose result changes by at most 1 between adjacent databases. Since composition of Lipschitz functions (merely) multiplies their Lipschitz factors, the composition of a counting query and an obfuscating mechanism is $\varepsilon$-DP as a whole if the mechanism on its own (i.e. without the query, acting ``obliviously'' on $x{=}q(b)$) is $\varepsilon$-Lipschitz. That is why for counting queries we can concentrate on the mechanisms alone (whose type is ${\cal X}{\mathbin{\rightarrow}}{\mathbb{D}}{\cal Y}$) rather than including the databases and their type $\mathbb{B}\kern-0.29999ptR$ in our analysis.

Although the database contents are not (generally) known, often the distribution of its query results is known: this is ``prior knowledge'', where e.g. it is known that a database of heights in the Netherlands is likely to contain higher values than a similar database in other countries — and that knowledge is different from the (unknown) fact we are trying to protect, i.e. whether a particular person's height is in that database.

We abstract from prior knowledge of the database by concentrating instead on the prior knowledge $\pi$ of the distribution ${\cal X}$ of raw queries, the inputs $x$ to the mechanism, that is induced as the push-forward of the query-function (an ``open source'' aggregating function) over the known distribution of possible databases themselves. Knowing $\pi$ on the input in ${\cal X}$  the observer can use her knowledge of the mechanism (also open source) to deduce a distribution on the output observations in ${\cal Y}$ that will result from applying it and –further– she can also deduce a posterior distribution on ${\cal X}$ based on any particular $y$ in ${\cal Y}$ that she observes.

It has been shown [1] that when ${\cal X}$ is discrete (and hence the prior $\pi$ on ${\cal X}$ is also), and when the obfuscation is via $G^{\varepsilon}$, and when the observer applies a ``loss function'' $\ell(w,x)$ of her choice to monetise in ${\mathbb{R}}^{\geq}$ the loss of utility to her if the raw query was $x$ but she assumes it was $w$, then any other $\varepsilon$-DP mechanism $M^{\varepsilon}$ acting on ${\cal X}$ can only lose more utility (on average) according to that $\pi$ and $\ell$ than $G^{\varepsilon}$ does. That is, the $\varepsilon$-DP Geometric mechanism is optimal for minimising loss (maximising utility) over all priors $\pi$ and all (``legal'') loss functions $\ell$ under a mandated $\varepsilon$-DP obfuscation. A loss function is said to be legal if it is monotone (increasing) wrt. to the difference between the guess ($w$) and the actual value $x$ of the query. As explained in [1] this means that the loss $\ell(w,x)$ takes the form of a function $m(|w-x|,x)$, which must be monotone (increasing) in its first argument.

If the input metric for $G$ is not the Hamming distance $\mbox{\sc\small d}_{H}$, e.g. when the $G$'s input ${\cal X}$ is continuous, still $G$'s output remains discrete, taking some number of steps, each of fixed length say $\lambda{>}0$, in either direction. That is, any $G$ input $x$ is perturbed to $x{+}i\lambda$ for some integer $i$.

Now because ${\cal X}$ is continuous and dense, we can vary the input $x$ itself, by a tiny amount, to some $x^{\prime}$ so that $\mbox{\sc\small d}(x,x^{\prime})\,{<}\,\lambda$ no matter how small $\lambda$ might be, producing perturbations $x^{\prime}{+}i\lambda$ each of which is distant that same (constant) $\mbox{\sc\small d}(x,x^{\prime})$ from the original $x{+}i\lambda$ and, precisely because $\mbox{\sc\small d}(x,x^{\prime})\,{<}\,\lambda$ , those new perturbations cannot overlap the ones based on the original $x$.

Thus the two distributions produced by $G$ acting on $x$ and on $x^{\prime}$ have supports that do not intersect at all. And therefore the $\,{\textsf{\small d}_{D}}$ distance between the two distributions is infinite, meaning that $G$ cannot be be $\varepsilon$-DP for any (finite) $\varepsilon$. That is, for a database producing truly real query results ${\cal X}$, a standard (discrete) $G$ cannot establish $\varepsilon$-DP for any $\varepsilon$, however large $\varepsilon$ might be.

There are two possible solutions. The first solution, both obvious and practical, is to ``discretise'' the input and to scale appropriately: a person's height of $1.75\textrm{m}$ would become $175\textrm{cm}$ instead. A second solution however is motivated by taking a more theoretical approach. Rather than discretise the type of the query results, we leave it continuous — and seek our optimal mechanism among those that –unlike the Geometric– do not take only discrete steps. It will turn out to be the Laplace distribution.

In the discrete case typically the set ${\cal X}$ of raw queries is $(0..N)$ for some $N{\geq}0$, and the prior knowledge $\pi$ is a (discrete) distribution on that. For our continuous setting we will use ${\cal X}{=}[0,1]$ for raw queries, the unit interval ${\cal U}$, and the discrete distribution $\pi$ will become a proper measure on $[0,1]$ expressed as a probability density function. The $\varepsilon$-DP obfuscating mechanisms, now $K^{\varepsilon}$ for ``kontinuous'', will take a raw query $x$ from a continuous set ${\cal X}$ rather than a discrete one. And the metric on ${\cal X}{=}{\kern 1.00006pt\cal U}$ will be Euclidean.

Our (continuous) optimality result formalised at Thm. 5 is that $\varepsilon$-DP Laplace mechanism $L^{\varepsilon}$ minimises loss over all continuous priors $\pi$ on ${\cal X}{=}{\kern 1.00006pt\cal U}$ and all legal loss functions $\ell$ under a mandated $\varepsilon$-DP obfuscation with respect to the Euclidean metric on the continuous input ${\cal X}{=}[0,1]$.

The theorem requires that all mechanisms satisfy (2) with d the Euclidean distance on continuous inputs. We write $\varepsilon$-DP for such mechanisms. The argument in §II-F above shows therefore that Geometric mechanisms are no longer suitable (for optimality) because on continuous ${\cal X}$ they are no longer $\varepsilon$-DP.

The standard treatment of information flow is via Shannon's (unreliable) channels: they take an input $x$ from say ${\cal X}$ and deliver an output that for a perfect channel will be $x$ again, but for an imperfect channel might be some other $x^{\prime}$ in ${\cal X}$ instead. For example, an imperfect channel transmitting bits might ``flip' input bits so that with probability say $\nicefrac{{1}}{{4}}$ an input 0 becomes an output 1 and vice versa [6]. In the discrete case, and generalising to allow outputs of possibly a different type ${\cal Y}$, such channels are ${\cal X}{\times}{\cal Y}$ matrices $C$ whose row-$x$, column-$y$ element $C_{x,y}$ is the probability that input $x$ will produce output $y$. A perfect channel would be the identity matrix on ${\cal X}{{\times}}{\cal X}$; a completely broken channel on ${\cal X}{{\times}}{\cal Y}$ for any ${\cal Y}$ would have $C_{x,y}=\nicefrac{{1}}{{\#{\cal Y}}}$.

The $x$-th row of a (channel) matrix $C$ is $C_{x,-}$; and the $y$-th column is $C_{-,y}$. Since each row sums to 1 (making $C$ a stochastic matrix), the row $C_{x,-}$ determines a discrete distribution in ${\mathbb{D}}{\cal Y}$; for the ``broken'' channel it would be the uniform distribution, which we write $\odot$.

As a matrix, a channel has type ${\cal X}{{\times}}{\cal Y}\,{\mathbin{\rightarrow}}\,{\mathbb{R}}$ (but with 1-summing rows); isomorphically it also has type ${\cal X}{\mathbin{\rightarrow}}{\mathbb{D}}{\cal Y}$. We'll write ${\cal X}{\mathbin{\rightarrowtriangle}}{\cal Y}$ for both, provided context makes it clear which one we are using.

If a prior distribution $\pi{:}\,{\mathbb{D}}{\cal X}$ on ${\cal X}$ is known, then the channel $C$ can be applied to $\pi$ to create a joint distribution $J$ in ${\mathbb{D}}({\cal X}{\times}{\cal Y})$ on both input and output together, written $\pi\kern 1.00006pt{\triangleright}\kern 1.00006ptC$ and where $J_{x,y}\,{:=}\;\pi_{x}C_{x,y}$. For that $J$, the left-marginal $\sum_{y}J_{x,y}$ gives the prior $\pi$ again (no matter what $C$ might be), i.e. the probability that the input was $x$ — thus $\pi_{x}\,{=}\,J_{x,\Sigma}$ if we use that notation for the marginal. The right marginal $J_{\Sigma,y}$ is the probability that the output is $y$, given both $\pi$ and $C$.

The $y$-posterior distribution on ${\cal X}$, given $\pi,C$ and a particular $y$, is the conditional distribution on ${\cal X}$ if that $y$ was output: it is the $y$-th column divided by the marginal probability of that $y$, that is $J_{-,y}/J_{\Sigma,y}$ (provided the marginal is not zero).

If we fix $\pi$ and $C$, and use the conventional abbreviation $p_{XY}$ for the resulting joint distribution $(\pi\kern 1.00006pt{\triangleright}\kern 1.00006ptC)$, then the usual notations for the above are $p_{X}$ for left marginal $({=}\,\pi)$ and $p_{X}(x)$ for its value $\pi_{x}$ at a particular $x$, with $p_{Y}$ and $p_{Y}(y)$ similarly for the right marginal. Then $p_{X|y}(x)$ is the posterior probability of the original observation's being $x$ when $y$ has been observed. Further, we can write just $p(x)$ and $p(y)$ and $p(x|y)$ when context makes the (missing) subscripts clear.

Our obfuscating mechanisms $M$ and $G^{\varepsilon}$ are channels like $C$ in the discrete case — the result of the query is the channel's input $x$, and the (perturbed) value the observer sees is the channel's output $y$. The loss functions $\ell(w,x)$ will quantify the loss to her of seeing (only) $y$, and then choosing $w$, when what she really wants to know is $x$. Such $\varepsilon$-DP mechanisms have earlier been modelled this way, i.e. as channels by Alvim et al. [7] and Chatzikokolakis et al. [4], who observed that for $\varepsilon$-DP the ratios of their entries must satisfy the $\varepsilon$-DP constraints, because the definition at §II-A(4) reduces to comparing (multiplicatively) adjacent entries in channel columns.

The connection between the observation $y$ and the loss-function parameter $w$ is that the observer does not necessarily have to ``take what she sees'' — there might be good reasons for her making a different choice. For example, in a word-guessing game where the last, obfuscated letter ? in a word SA? is shown on the board, the observer might have to guess what it really is. Even if it looks like a blurry Y (value 4 in Scrabble), she might instead guess X (value 8) because that would earn more points on average if from prior knowledge she knows that X strictly more than half as likely as Y is — i.e. it's worth her taking the risk. Thus rather than mandating that the observer must accept what she thinks the letter is most likely to be, she uses the obfuscated query $y$ to deduce information about the whole posterior distribution of the actual query… and might suggest that she guess some $w{\neq}y$, because the expected loss of doing that is less than (the expected utility is greater than) it would be if she simply accepted the $y$ she saw. That rational strategy is called ``remapping'' [1]. Thus she sees $y$, but $y$ tells her that $w$ is what she should choose as her least-loss inducing guess for $x$. That is, the simplest strategy is ``take what you see''; but it might not be the best one. In general (and now using $M$ again for mechanism), we write $\textsf{\small\$}(\pi,M,\ell)$ for the expected loss to a rational observer, given the $\pi,M$ she knows and the loss function $\ell$ she has chosen: it is

that is the expected value, over all possible observations $y$ and their marginal probabilities, of the least loss she could rationally achieve over all her possible choices $w$ given the knowledge that $y$ will have provided about the posterior distribution $p(X|y)$ of the actual raw input $x$. Note that $M$ and $\pi$ determine (from (§IV-A) the $p(y)$ and $p(x|y)$ that appear in (7). We remark that this formulation for measuring expected loss corresponds precisely to the formulation used by Ghosh et al. in the optimality theorem.

It is important to remember that the expected-loss formula (7) does not use the actual mechanism-output values $y$ in any way directly: instead it takes the only expected value of what they might be. All that matters is their marginal probabilities $p(y)$ and the a-posteriori distributions $p(X|y)$ that they induce. That allows us to abstract from ${\cal Y}$ altogether.

A hyper-distribution expresses that abstraction: it is a distribution of distributions on ${\cal X}$ alone, that is of type ${\mathbb{D}}{\mathbb{D}}{\cal X}$; abbreviate those as ``hyper'' and ``${\mathbb{D}}^{2}{\cal X}$''. Given a joint distribution $J{:}\,{\mathbb{D}}({\cal X}{{\times}}{\cal Y})$, we write $[J]$ for the hyper-distribution whose support is posterior distributions ⁵⁵5In the hyper-distribution literature these are called “inners” [8]. $p(X|y)$ on $X$ and which assigns the corresponding marginal distribution $p(y)$ to each. (Zero-valued marginals are left out.) We now re-express (7) in those terms.

If we write $\ell(w,-)$ for the function on ${\cal X}$ that $\ell$ determines once $w$ is fixed, and write $\,{\cal E}_{\textsc{\tiny dist}}\,{\textsc{\footnotesize rv}}\,$ for expected value of random-variable rv with distribution dist, then $\textsf{\small min}_{w}\,{\cal E}_{p(X|y)}\,{\ell(w,-)}$ is the inner part of (7). Then fix some $\ell$ and define for general distribution $\delta{:}\,{\mathbb{D}}X$ that

(using $Y$ for ``entrop$Y$'') so that $Y_{\ell}$ is itself a real-valued function on distributions $\delta$ (as e.g. Shannon entropy is). With that preparation, the expression (7) becomes the expected value of $Y_{\ell}$ over the hyper produced by abstracting from $J=\pi\kern 1.00006pt{\triangleright}\kern 1.00006ptM$ as above. That is (7) gives equivalently

in which the $M$ and $\pi$ now explicitly appear and where –we recall– the brackets $[-]$ convert the joint distribution $\pi\kern 1.00006pt{\triangleright}\kern 1.00006ptM$ to a hyper. (If $Y_{\ell}$ were in fact Shannon entropy, then (9) would be the conditional Shannon entropy. But $Y_{\ell}$'s are much more general than Shannon entropy alone [2, 9].)

Finally, using hypers we define an abstract channel to be a function from prior to hyper, i.e. of type ${\cal X}{\mathbin{\rightarrow}}{\mathbb{D}}^{2}{\cal X}$, realised from some concrete channel $M{:}\,{\cal X}{\mathbin{\rightarrowtriangle}}{\cal Y}$ as $\pi\,{\mapsto}\,[\pi\kern 1.00006pt{\triangleright}\kern 1.00006ptM]$. It is ``abstract'' because the type ${\cal Y}$ no longer appears: it is unnecessary because if $M(\pi)$ is the application of $M$ as a function applied to prior $\pi$, then from (9) the worst rational expected loss is written simply ${\cal E}_{M(\pi)}\,{Y_{\ell}}$ .

(Recall from §IV-B that this naturally takes into account the ``rational observers'' and the remapping they might perform, as described in [1].)

The hypers ${\mathbb{D}}^{2}{\cal X}$ on ${\cal X}$ have a partial order $(\mathrel{\sqsubseteq})$ ``refinement'' [10] that we will need in the proof of our main result. It admits several equivalent interpretations in this context. Below, we write $\Delta$ etc. for general hypers in ${\mathbb{D}}^{2}{\cal X}$.

We have that $\Delta\,{\mathrel{\sqsubseteq}}\,\Delta^{\prime}$, that hyper $\Delta$ is refined by hyper $\Delta^{\prime}$, under any of these equivalent conditions:

1. (a)

   when ${\cal E}_{\Delta}\,{Y_{\ell}}\leq{\cal E}_{\Delta^{\prime}}\,{Y_{\ell}}$ for all loss functions $\ell$ (i.e. whether legal or not).

2. (b)

   when considered as distributions on posteriors ${\mathbb{D}}{\cal X}$ it is possible to convert $\Delta$ into $\Delta^{\prime}$ via a Wasserstein-style ``earth move'' of probability from one posterior to another [11, 12, 8].

3. (c)

   when generated from joint-distribution matrices $D$ in ${\mathbb{D}}({\cal X}{\times}{\cal Y})$ generating $\Delta$, and $D^{\prime}$ in ${\mathbb{D}}({\cal X}{\times}{\cal Y}^{\prime})$ generating $\Delta^{\prime}$, there is a ``post-processing matrix'' $R$ of type ${\cal Y}{\mathbin{\rightarrowtriangle}}{\cal Y}^{\prime}$ such that as matrices we have $D{\cdot}R=D^{\prime}$ via matrix multiplication.

And we say that one mechanism $M$ is refined by another $M^{\prime}$ just when $[\pi\kern 1.00006pt{\triangleright}\kern 1.00006ptM]\,{\mathrel{\sqsubseteq}}\,[\pi\kern 1.00006pt{\triangleright}\kern 1.00006ptM^{\prime}]$ for all priors $\pi$. When this occurs we also write $M\mathrel{\sqsubseteq}M^{\prime}$. From formulation (a) we will use the fact that the $(\mathrel{\sqsubseteq})$-infimum of the ${}^{T}L^{\varepsilon}_{N}$'s (indexed over a sequence of $T$'s) is just $L^{\varepsilon}$ itself [13] and [15, Lem. 20, Appendix §B].

Formulation (b) is particularly useful. If we find a specific earth move from $\Delta$ to $\Delta^{\prime}$ that defines a refinement we can then use the equivalent (a) to deduce that ${\cal E}_{\Delta}\,{Y_{\ell}}\leq{\cal E}_{\Delta^{\prime}}\,{Y_{\ell}}$. However if we can also compute the cost ⁶⁶6The cost is determined by the amount of “earth” to be moved, and the distance it must be moved. See for example [14]. of the particular earth move we can conclude in addition that the difference $|{\cal E}_{\Delta}\,{Y_{\ell}}-{\cal E}_{\Delta^{\prime}}\,{Y_{\ell}}|$ must be bounded above by an amount we can compute. This follows from the well-known Kantorovich-Rubinstein duality [11] which says that $|{\cal E}_{\Delta}\,{Y_{\ell}}-{\cal E}_{\Delta^{\prime}}\,{Y_{\ell}}|$ is no more than minimal cost incurred by any earth move transforming $\Delta$ to $\Delta^{\prime}$ scaled by the ``Lipschitz constant'' ⁷⁷7The Lipschitz constant of a function is the amount by which the difference in outputs can vary when compared to the difference in inputs. of $Y_{\ell}$. We use these ideas in Lem. 11 and Thm. 13.

Continuous analogues of the $\pi$, $M$ and $\ell$ will be our principal concern here: ultimately we we will use ${\mathbb{M}}[0,1]$ for our measurable spaces ${\cal X}$ and ${\cal Y}$, and will suppose for simplicity that ${\cal X}{=}{\cal Y}{=}[0,1]$. (More generality is achieved by simple scaling).

Measures ${\mathbb{M}}[0,1]$ (that is ${\mathbb{M}}{\cal X}$ and ${\mathbb{M}}{\cal Y}$) will be given as probability density functions, where a pdf say $\mu{:}\,[0,1]{\mathbin{\rightarrow}}{\mathbb{R}}^{\geq}$ determines the probability $\int^{b}_{a}\mu$ assigned to the sample $[a,b]{\subseteq}[0,1]$ using the standard Borel measure on $[0,1]$, and more generally the expected value of some random variable $V$ on $[a,b)$ given by pdf $\mu$ is $\int_{a}^{b-}\mu(x)V(x)\kern 1.00006pt{\rm d}x$ .

Even though $\mu$ is of type pdf, we abuse notation to write for example $\mu[a,b)$ for the probability $\int_{a}^{b-}\kern-7.5pt\mu$ that $\mu$ assigns to that interval, and $\mu_{a}$ for the probability $\mu$ assigns to the point $a$ alone, i.e. some $r$ just when when the actual pdf-value of $\mu(a)$ is the Dirac delta-function scaled by $r$, written $\textrm{\boldmath$\delta$}_{r}$ .

Our mechanisms $M$, up to now discrete, will now become ``kontinuous'', renamed $K$ as a mnemonic. Thus a continuous mechanism $K{:}\,{\cal X}{\mathbin{\rightarrow}}{\mathbb{M}}{\cal Y}$ given input $x$ produces measure $K(x)$ on the observations ${\cal Y}{=}[0,1]$. And given a a whole continuous prior $\pi{:}\,{\mathbb{M}}[0,1]$, that same $K$ therefore determines a joint measure over ${\cal X}{\times}{\cal Y}$. ⁸⁸8See [15, Appendix §A2].By analogy with (8,9) we have

The continuous version of uncertainty (8) is now

and the continuous version of expected loss (9) is now

As for the Geometric mechanism, the Laplace mechanism is based on the Laplace distribution. It is defined as follows:

We can now state our principal contribution. It is to show that the truncated Laplace $\textit{\L}^{\varepsilon}$ is universally optimal, in this continuous setting, in the same way that $G^{\varepsilon}$ was optimal in the discrete setting:

As we foreshadowed in the proof outline in §III, Thm. 5 relies ultimately on the earlier-proven optimality $G^{\varepsilon}$ in the discrete case: we must show how we can approximate continuous $\varepsilon$-DP  mechanisms in discrete form, each one satisfying the conditions under which the earlier result applies, and in §VI we fill in the details. Along the way we show how the Laplace mechanism provides a smooth approximation to the Geometric- with discrete inputs.

Our principal tool for connecting the discrete and continuous settings is the evenly-spaced discrete subset ${\cal U}_{N}=\{0,\nicefrac{{1}}{{N}},\nicefrac{{2}}{{N}}\ldots,\nicefrac{{N-1}}{{N}},1\}$ of the unit interval ${\cal U}{=}[0,1]$ for ever-increasing $N{>}0$.

The separation $\nicefrac{{1}}{{N}}$ is the interval width.

The $N$-approximation of prior $\pi{:}\,{\mathbb{M}}{\kern 1.00006pt\cal U}$ of type ${\mathbb{D}}{\kern 1.00006pt\cal U}_{N}$, i.e. yielding actual probabilities (not densities), and is defined

The discrete $\pi_{N}$ gathers each of the continuous $\pi$-interval's measure onto its left point, with as a special case [1,1] from $\pi$ included onto the point $\nicefrac{{N-1}}{{N}}$ of $\pi_{N}$.

As an example take $N$ to be $2$, and $\pi$ to be the uniform (continuous) distribution over ${\cal U}$, which can be represented by the constant $1$ pdf. Since the interval width is $\nicefrac{{1}}{{2}}$, we see that $\pi_{N}$ assigns probability $\nicefrac{{1}}{{2}}$ to both $0$ and $\nicefrac{{1}}{{2}}$ and zero to all other points in ${\cal U}$.

In the other direction, we can lift discrete $M$ and loss-function $\ell$ on ${\cal U}_{N}$ into the continuous ${\cal X}{=}{\kern 1.00006pt\cal U}$ by replicating their values for the $x$'s not in ${\kern 1.00006pt\cal U}_{N}$  in a way that constructs $N$-step functions: we have

The important property enabled by the above definitions is the correspondence between loss functions' values in their pixelated and original versions, which will allow us to apply the earlier discrete-optimality result, based on Lem. 9 to come. That is, we have

The techniques above give good discrete approximations for continuous-input $\varepsilon$-DP mechanisms $M$ acting on continuous priors simply by considering $M_{N}$'s for increasing $N$'s, using §VI-C. As a convenient abuse of notation, when we start with a continuous-input mechanism $M$ on $[0,1]$ we write $M_{N}$ to mean the $N$-step mechanism that is made by first restricting $M$ to the subset ${\cal U}_{N}$ of $[0,1]$ and then lifting that restriction ``back again'' as in Def. 7, effectively converting it into an $N$-step function. When we do this we find that the posterior loss wrt. $N$-step loss functions can be bounded above and below by using pixelated priors and $N$-stepped mechanisms.

With Lem. 8 and Lem. 9 we can study optimality of $\textit{\L}^{\varepsilon}$ on finite discrete inputs ${\cal U}_{N}$. We will see that, although Geometric mechanisms are still optimal for the (effectively) discrete inputs ${\cal U}_{N}$, the Laplace mechanism provides increasingly good approximate optimality for ${\cal U}_{N}$ as $N$ increases, and is in fact (truly) optimal in the limit.