Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising

Introduction

Output perturbation is a cornerstone of mechanism design in differential privacy (DP). Well-known mechanisms in this class are the Laplace and Gaussian mechanisms Dwork et al. (2006); Dwork and Roth (2014). More complex mechanisms are often obtained by composing multiple applications of these basic output perturbation mechanisms. For example, the Laplace mechanism is the basic building block of the sparse vector mechanism Dwork et al. (2009), and the Gaussian mechanism is the building block of private empirical risk minimization algorithms based on stochastic gradient descent Bassily et al. (2014). Analysing the privacy of such complex mechanisms turns out to be a delicate and error-prone task Lyu et al. (2017). In particular, obtaining tight privacy analyses leading to optimal utility is one of the main challenges in the design of advanced DP mechanisms. An alternative to tight a-priori analyses is to equip complex mechanisms with algorithmic noise calibration and accounting methods. These methods use numerical computations to, e.g. calibrate perturbations and compute cumulative privacy losses at run time, without relying on hand-crafted worst-case bounds. For example, recent works have proposed methods to account for the privacy loss under compositions occurring in complex mechanisms Rogers et al. (2016); Abadi et al. (2016).

In this work we revisit the Gaussian mechanism and develop two ideas to improve the utility of output perturbation DP mechanisms based on Gaussian noise. The first improvement is an algorithmic noise calibration strategy that uses numerical evaluations of the Gaussian cumulative density function (CDF) to obtain the optimal variance to achieve DP using Gaussian perturbation. The analysis and the resulting algorithm are provided in Section 3. In order to motivate the need for a numerical approach to calibrate the noise of a DP Gaussian perturbation mechanism, we start with an analysis of the main limitations of the classical Gaussian mechanism in Section 2. A numerical evaluation provided in Section 5.1 showcases the advantages of our optimal calibration procedure.

The second improvement equips the Gaussian perturbation mechanism with a post-processing step which denoises the output using adaptive estimation techniques from the statistics literature. Since DP is preserved by post-processing and the distribution of the perturbation added to the desired outcome is known, this allows a mechanism to achieve the desired privacy guarantee while increasing the accuracy of the released value. The relevant denoising estimators and their utility guarantees are discussed in Section 4. Results presented in this section are not new: they are the product of a century’s worth of research in statistical estimation. Our contribution is to compile relevant results scattered throughout the literature in a single place and showcase their practical impact in synthetic (Section 5.2) and real (Section 5.3) datasets, thus providing useful pointers and guidelines for practitioners.

Limitations of the Classical Gaussian Mechanism

The definition of DP captures the intuition that a computation on private data will not reveal sensitive information about individuals in a dataset if removing or replacing an individual in the dataset has a negligible effect in the output distribution.

For any $\varepsilon,\delta\in(0,1)$, the Gaussian output perturbation mechanism with $\sigma=\Delta\sqrt{2\log(1.25/\delta)}/\varepsilon$ is $(\varepsilon,\delta)$-DP.

A natural question one can ask about this result is whether this value of $\sigma$ provides the minimal amount of noise required to obtain $(\varepsilon,\delta)$-DP with Gaussian perturbations. Another natural question is what happens in the case $\varepsilon\geq 1$. This section addresses both these questions. First we show that the value of $\sigma$ given in Theorem 1 is suboptimal in the high privacy regime $\varepsilon\to 0$. Then we show that this problem is in fact inherent to the usual proof strategy used to analyze the Gaussian mechanism. We conclude the section by showing that for large values of $\varepsilon$ the standard deviation of a Gaussian perturbation that provides $(\varepsilon,\delta$)-DP must scale like $\Omega(1/\sqrt{\varepsilon})$. This implies that the scaling $\Theta(1/\varepsilon)$ provided by the classical Gaussian mechanism in the range $\varepsilon\in(0,1)$ cannot be extended beyond any bounded interval.

To illustrate the sub-optimality of the classical Gaussian mechanism in the regime $\varepsilon\to 0$ we start by showing it is possible to achieve $(0,\delta)$-DP using Gaussian perturbations. This clearly falls outside the capabilities of the classical Gaussian mechanism, since the standard deviation $\sigma=\Theta(1/\varepsilon)$ provided by Theorem 1 grows to infinity as $\varepsilon\to 0$.

A Gaussian output perturbation mechanism with $\sigma=\Delta/2\delta$ is $(0,\delta)$-DPProofs for all results given in the paper are presented in Appendix A..

Previous analyses of the Gaussian mechanism are based on a simple sufficient condition for DP in terms of the privacy loss random variable Dwork and Roth (2014). The next section explains why the usual analysis of the Gaussian mechanism cannot yield tight bounds for the regime $\varepsilon\to 0$. This shows that our example is not a corner case, but a fundamental limitation of trying to establish $(\varepsilon,\delta)$-DP through said sufficient condition.

2 Limitations of Privacy Loss Analyses

Given a vector-valued mechanism $M$ let $p_{M(x)}(y)$ denote the density of the random variable $Y=M(x)$. The privacy loss function of $M$ on a pair of neighbouring inputs $x\simeq x^{\prime}$ is defined as

The privacy loss $L_{M,x,x^{\prime}}$ of a Gaussian output perturbation mechanism follows a distribution $\mathcal{N}(\eta,2\eta)$ with $\eta=D^{2}/2\sigma^{2}$, where $D=\|f(x)-f(x^{\prime})\|$.

The privacy analysis of the classical Gaussian mechanism relies on the following sufficient condition: a mechanism $M$ is $(\varepsilon,\delta)$-DP if the privacy loss $L_{M,x,x^{\prime}}$ satisfies

3 Limitations in the Low Privacy Regime

The last question we address in this section is whether the order of magnitude $\sigma=\Theta(1/\varepsilon)$ given by Theorem 1 for $\varepsilon\leq 1$ can be extended to privacy parameters of the form $\varepsilon>1$. We show this is not the case by providing the following lower bound.

Note that as $\varepsilon\to\infty$ the upper bound on $\delta$ in Theorem 4 converges to $1/2$. Thus, as $\varepsilon$ increases the range of $\delta$’s requiring noise of the order $\Omega(1/\sqrt{\varepsilon})$ increases to include all parameters of practical interest. This shows that the rate $\sigma=\Theta(1/\varepsilon)$ provided by the classical Gaussian mechanism cannot be extended beyond the interval $\varepsilon\in(0,1)$. Note this provides an interesting contrast with the Laplace mechanism, which can achieve $\varepsilon$-DP with standard deviation $\Theta(1/\varepsilon)$ in the low privacy regime.

The Analytic Gaussian Mechanism

Using this point of view, we introduce a calibration strategy for Gaussian perturbations that requires solving a simple optimization problem involving $\Phi(t)$. We discuss how to solve this optimization at the end of this section.

The first step in our analysis is to provide a necessary and sufficient condition for differential privacy in terms of privacy loss random variables. This is captured by the following result.

Note that Theorem 5 immediately implies the sufficient condition given in (2) through the inequality

Now we can use Lemma 3 to specialize (3) for a Gaussian output perturbation mechanism. The relevant computations are packaged in the following result, where we express the probabilities in (3) in terms of the Gaussian CDF $\Phi$.

Suppose $M(x)=f(x)+Z$ is a Gaussian output perturbation mechanism with $Z\sim\mathcal{N}(0,\sigma^{2}I)$. For any $x\simeq x^{\prime}$ let $D=\|f(x)-f(x^{\prime})\|$. Then the following hold for any $\varepsilon\geq 0$:

This result specializes the left hand side of (3) in terms of the distance $D=\|f(x)-f(x^{\prime})\|$ between the output means on a pair of neighbouring datasets. To complete the derivation of our analytic Gaussian mechanism we need to ensure that (3) is satisfied for every pair $x\simeq x^{\prime}$. The next lemma shows that this reduces to plugging the global $L_{2}$ sensitivity $\Delta$ in the place of $D$ in (4) and (5).

Now we are ready to state our main result, whose proof follows directly from Theorem 5, Lemma 7, and equations (4) and (5).

This result shows that in order to obtain an $(\varepsilon,\delta)$-DP Gaussian output perturbation mechanism for a function $f$ with global $L_{2}$ sensitivity $\Delta$ it is enough to find a noise variance $\sigma^{2}$ satisfying (6). One could now use upper and lower bounds for the tail of the Gaussian CDF to derive an analytic expression for a parameter $\sigma$ satisfying this constraint. However, this again leads to a suboptimal result due to the slack in these tail bounds in the non-asymptotic regime. Instead, we propose to find $\sigma$ using a numerical algorithm by leveraging the fact that the Gaussian CDF can be written as $\Phi(t)=(1+\mathsf{erf}(t/\sqrt{2}))/2$, where $\mathsf{erf}$ is the standard error function. Efficient implementations of this function to very high accuracies are provided by most statistical and numerical software packages. However, this strategy requires some care in order to avoid numerical stability issues around the point where the expression $\Delta/2\sigma-\varepsilon\sigma/\Delta$ in (6) changes sign. Thus, we further massage the left hand side (6) we obtain the implementation of the analytic Gaussian mechanism given in Algorithm 1. The correctness of this implementation is provided by the following result.

Let $f$ be a function with global $L_{2}$ sensitivity $\Delta$. For any $\varepsilon>0$ and $\delta\in(0,1)$, the mechanism described in Algorithm 1 is $(\varepsilon,\delta)$-DP.

Optimal Denoising

Can we improve the performance of analytical Gaussian mechanism even further? The answer is “yes” and “no”. We can’t because Algorithm 1 is already the exact calibration of the Gaussian noise level to the given privacy budget. But if we consider the problem of designing the best differentially private procedure $M(x)$ that approximates $f(x)$, then there could still be room for improvement.

Assumption A.1 translates the problem of optimal denoising into a Bayesian estimation problem, where the underlying parameter $f(x)$ has a prior distribution, and the task is to find an estimator that attains the Bayes risk — the minimum of the average estimation error integrated over a prior $\pi$, defined as

For square loss, the Bayes estimator is simply the posterior mean estimator, as the following theorem shows:

Optimal frequentist denoising.

A complete characterization of this minimax risk (up to a constant) is given by Birgé and Massart (2001, Proposition 5), who show that in the non-trivial regionWhen $\sqrt{\log d}\leq B/\sigma\leq c_{p}d^{1/p}$ for a constant $c_{p}$ that depends only on $p$. of the signal to noise ratio $B/\sigma$, the ball $S=\mathcal{B}(p,B)$ satisfies

for $0<p<2$ and when $p\geq 2$, Donoho et al. (1990) show that

Deriving exact minimax estimators is challenging and most analyses assume certain asymptotic regimes (see the case for $p=2$ by Bickel et al. (1981)). Nonetheless, some techniques have been shown to match $R(\mathcal{B}(p,B))$ up to a small constant factor in the finite sample regime (see, e.g., Donoho et al., 1990; Donoho and Johnstone, 1994). This means that we can often improve the square error from $d\sigma^{2}$ to $R(\mathcal{B}(p,B))$ when we have the additional information that $f(x)$ is in some $L_{p}$ ball. This could be especially helpful in the high-dimensional case for $p<2$. For instance if $p=1$ and $B=\sigma$, then we obtain a risk $\sigma B\sqrt{1+\log(d\sigma/B)}$, which improves exponentially in $d$ over the $d\sigma^{2}$ risk of $\hat{y}$. More practically, if $f(x)$ is a sparse histogram with $s$ non-zero elements, then taking $p\rightarrow 0$ will result in an error bound on the order of $s\sigma^{2}(1+\log(d))$, which is linear in the sparsity $s$ rather than the dimension $d$.

Adaptive estimation.

What if we do not know the prior parameter $w^{2}$, or a right choice of $B$ and $p$? Can we still come up with estimators that take advantage of these structures? It turns out that this is the problem of designing adaptive estimators which sits at the heart of statistical research. An adaptive estimator in our case, is one that does not need to know $w^{2}$ or a pair of $B$ and $p$, yet behave nearly as well as Bayes estimator that knows $w^{2}$ or the minimax estimator that knows $B$ and $p$ for each parameter regime.

We first give an example of an adaptive Bayes estimator that does not require us to specify a prior, yet can perform almost as well as the optimal Bayes estimator for all isotropic Gaussian prior simultaneously.

We now move on to describe a method that is adaptive to $B$ and $p$ in minimax estimation. Quite remarkably, Donoho (1995) shows that choosing $\lambda=\sigma\sqrt{2\log d}$ in the soft-thresholding estimator

yields a nearly optimal estimator for every $L_{p}$ ball.

Let $S=\mathcal{B}(p,B)$ for some $p,B>0$. The soft-thresholding estimator with $\lambda=\sigma\sqrt{2\log d}$ obeys that

The result implies that the soft-thresholding estimator is nearly optimal for all balls up to a multiplicative factor of $4.44\log(d)$.

Take the problem of private releasing a histogram of $n$ items in $d$ bins. Theorem 12 and Equation (7) with $p\leq 1$ imply that the soft-thresholding estimator obeys

Related work.

In all the above references there is some prior knowledge (constraint sets, sparsity or Bayesian prior) that is exploited to improve the utility of DP releases. To the best of our knowledge, we are the first to consider “adaptive estimation” and demonstrate how classical techniques can be helpful even without such prior knowledge. These estimators are not new; they have been known in the statistics literature for decades. Our purpose is to compile facts that are relevant to the practice of DP and initiate a systematic study of how these ideas affect the utility of DP mechanisms, which we complement with the experimental evaluation presented in the next section.

Numerical Experiments

This section provides an experimental evaluation of the improvements in utility provided by optimal calibration and adaptive denoising. First we numerically compare the variance of the analytic Gaussian mechanism and the classical mechanism for a variety of privacy parameters. Then we evaluate the contributions of denoising and analytic calibration against a series of baselines for the task of private mean estimation using synthetic data. We also evaluate several denoising strategies on the task of releasing heat maps based on the New York City taxi dataset under differential privacy. Further experiments are presented in Appendix B, including an evaluation of denoising strategies for the task of private histogram release.

We implemented Algorithm 1 in PythonSee https://github.com/BorjaBalle/analytic-gaussian-mechanism. and ran experiments to compare the variance of the perturbation obtained with the analytic Gaussian mechanism versus the variance required by the classical Gaussian mechanism. In all our experiments the values of $v^{*}$ and $u^{*}$ were solved up to an accuracy of $10^{-12}$ using binary search and the implementation of the $\mathsf{erf}$ function provided by SciPy Jones et al. (2001).

The results are presented in the two leftmost panels in Figure 1. The plots show that as $\varepsilon\to 0$ the optimally calibrated perturbation outperforms the classical mechanism by several orders of magnitude. Furthermore, we see that even for values of $\varepsilon$ close to $1$ our mechanism reduces the variance by a factor of $1.4$ or more, with higher improvements for larger values of $\delta$.

2 Denoising for Mean Estimation

To provide a thorough comparison we explore of the different parameters of the problem on the final utility. The key parameters of the problem are the dimension $d$ and the DP parameters $\varepsilon$ and $\delta$. The dimension affects the utility through the bounds provided in Theorem 11 and Theorem 12. The DP parameters affect the utility through the variance $\sigma^{2}$ of the mechanism, which is also affected by the sample size $n$ via the global sensitivity. Thus, we can characterize the effect of $\sigma^{2}$ by keeping $n$ fixed and changing the DP parameters. In our experiments we consider a fixed sample size $n=500$ and privacy parameter $\delta=10^{-4}$ while trying several values for $\varepsilon$.

The other parameter that affects the utility is the “size” of $f(x)$, controlled either through the variance $w^{2}$ or the norm ball $S$. Since the denoising estimators we use are adaptive to these parameters and do not need to know them in advance, we sample the dataset $x$ repeatedly to obtain a diversity of values for $f(x)$. Each dataset $x$ is sampled as follows: first sample a center $x_{0}\sim\mathcal{N}(0,I)$ and then build $x=(x_{1},\ldots,x_{n})$ with $x_{i}=x_{0}+\xi_{i}$, where each $\xi_{i}$ is i.i.d. with independent coordinates sampled uniformly from the interval $[-1/2,1/2]$. Thus, in each dataset the points $x_{i}$ all lie in an $L_{\infty}$-ball of radius $1$, leading to a global $L_{2}$ sensitivity $\Delta_{2}=\sqrt{d}/n$ and a global $L_{1}$ sensitivity $\Delta_{1}=d/n$. These are used to calibrate the Gaussian and Laplace perturbations, respectively.

The results are presented in two rightmost panels of Figure 1. Each point in every plot is the result of averaging the error over $100$ repetitions with different datasets. The first plot uses $\varepsilon=0.01$ and shows how denoised methods improve the accuracy over all the other methods, sometimes by orders of magnitude. The second plot shows that for this problem the James-Stein estimator provides better accuracy in the high-dimensional setting.

3 New York City Taxi Heat Maps

In this section, we apply our method to New York City taxi data. The dataset is a collection of time-stamped pick-ups and drop-offs of taxi drivers and we are interested in sharing a density map of such pick-ups and drop-offs in Manhattan at a specific time of a specific day under differential privacy.

This is a problem of significant practical interest. Ever since the NYC Taxi & Limousine Commission released this dataset, there has been multiple independent reports concerning the security and privacy risks this dataset poses for taxi drivers and their passengers (see, e.g., Pandurangan, ; Douriez et al., 2016). The techniques presented in this paper allow us to provably prevent individuals (on both the per-trip level and per-cab level) in the dataset from being identified, while remarkably, permitting the release of rich information about the data with fine-grained spatial and temporal resolution.

Specifically, we apply the analytical Gaussian mechanism to release the number of picks-ups and drop-offs at every traffic junction in Manhattan. There are a total of 3,784 such traffic junctions and they are connected by 7,070 sections of roads. We will treat them as nodes and edges on a graph. In the post-processing phase, we apply graph smoothing techniques to reveal the underlying signal despite the noise due to aGM. Specifically, we compare the JS-estimator and the soft-thresholding estimator we described in Section 4, as well as the same soft-thresholding estimator applied to the coefficients of a graph wavelet transform due to Sharpnack et al. (2013). The basis transformation is important because the data might be sparser in the transformed domain. For reference, we also include the state-of-the-art graph smoothing techniques called graph trend filtering (Wang et al., 2016), which has one additional tuning parameter but has been shown to perform significantly better than wavelet smoothing in practice.

Our experiments provide cab-level differential privacy by assuming that every driver does a maximum of $5$ trips within an hour so that we have a global $L_{2}$-sensitivity of $\Delta=5$. This is a conservative but reasonable estimate and can be enforced by preprocessing the data. Data within each hour is gathered and distributed to each traffic junction using a kernel density estimator; further details are documented in Doraiswamy et al. (2014).

We present some qualitative comparisons in Figure 2, where we visualize the privately released heat map with and without post-processing. Relatively speaking, trend filtering performs better than wavelet smoothing, but both approaches significantly improves the RMSE over the DP release without post-processing. The results in Appendix B provide quantitative results by comparing the mean square error of cGM, aGM as well as the aforementioned denoising techniques for data corresponding to different time intervals.

Conclusion and Discussion

In this paper, we embark on a journey of pushing the utility limit of Gaussian mechanism for $(\varepsilon,\delta)$-differential privacy. We propose a novel method to obtain the optimal calibration of Gaussian perturbations required to attain a given DP guarantee. We also review decades of research in statistical estimation theory and show that combining these techniques with differential privacy one obtains powerful adaptivity that denoises differentially private outputs nearly optimally without additional hyperparameters. On synthetic data and on the New York City Taxi dataset we illustrate a significant gain in estimation error and fine-grained spatial-temporal resolution.

There are a number of theoretical problems of interest for future work. First, on the problem of differentially private estimation. Our post-processing approach effectively restricts our choice of algorithms to the composition of privacy release and post-processing. While we now know that we are optimal in both components, it is unclear whether we lose anything relative to the best differentially private algorithms. Secondly, the analytical calibration proposed in this paper is optimal for achieving $(\varepsilon,\delta)$-DP with Gaussian noise. But when building complex mechanisms we are stuck in the dilemma of choosing between (a) using the aGM with the advanced composition (Kairouz et al., 2015); or, (b) using Rényi DP (Mironov, 2017) or zCDP (Bun and Steinke, 2016) for tighter composition and calculate the $(\varepsilon,\delta)$ from moment bounds. While (a) is tighter in the calculation the privacy parameters of each intermediate value, (b) is tighter in the composition but cannot take advantage of aGM. It would be interesting if we could get the best of both worlds.

Acknowledgments

We thank Doraiswamy et al. (2014) for sharing their preprocessed NYC taxi dataset, the anonymous reviewers for helpful comments that led to improvements of the paper and Stephen E. Fienberg for discussions that inspired the authors to think about optimal post-processing.

References

Appendix A Proofs

In this appendix we present supporting proofs for all the results mentioned in the main text.

An simple way to see that $(0,\delta)$-DP is achievable with Gaussian noise is to recall that $(0,\delta)$-DP is equivalent to a bound of $\delta$ on the total variation (TV) distance between the output distributions of $M(x)$ and $M(x^{\prime})$ for any neighbouring pair $x\simeq x^{\prime}$. If $M(x)$ is an output perturbation mechanism for $f(x)$ with noise $Z\sim\mathcal{N}(0,\sigma^{2}I)$, then using Pinsker’s inequality we have

Thus, we see that a Gaussian perturbation with standard deviation $\sigma=\Delta/2\delta$ is enough to achieve $(0,\delta)$-DP. ∎

Note that the proof of Theorem 9 shows that a Gaussian perturbation with $\sigma=\Delta/\sqrt{2\varepsilon}$ yields a $(\varepsilon,\delta_{0}(\varepsilon))$-DP mechanism, where $\delta_{0}(\varepsilon)=\Phi(0)-e^{\varepsilon}\Phi(-\sqrt{2\varepsilon})$. Thus, it is not possible to attain $(\varepsilon,\delta)$-DP with $\delta<\delta_{0}(\varepsilon)$ without increasing the variance of the perturbation.

The result follows by showing that the upper bound for $\delta$ proposed in Theorem 4 is a lower bound for $\delta_{0}(\varepsilon)$. Since $\Phi(0)=1/2$, all we need to show is $e^{\varepsilon}\Phi(-\sqrt{2\varepsilon})<\frac{e^{-3\varepsilon}}{\sqrt{4\pi\varepsilon}}$.

Recall that the density of the Gaussian output perturbation mechanism $M(x)=f(x)+Z$ with $Z\sim\mathcal{N}(0,\sigma^{2}I)$ is given by $p_{M(x)}(y)=\exp(-\|y-f(x)\|^{2}/2\sigma^{2})/\sqrt{2\pi\sigma^{2}}$. Plugging this expression into the definition of the privacy loss function and performing a quick computation we get

To compute the privacy loss random variable $L_{M,x,x^{\prime}}$ we need to plug $Y=f(x)+Z$ with $Z\sim\mathcal{N}(0,\sigma^{2}I)$ in the above inner product. By observing that $\langle Z,f(x)-f(x^{\prime})\rangle\sim\mathcal{N}(0,\sigma^{2}\|f(x)-f(x^{\prime})\|^{2})$ we obtain the distribution of the privacy loss random variable is given by

Therefore, the privacy loss of the Gaussian mechanism has the form $\mathcal{N}(\eta,2\eta)$ for $\eta=D^{2}/2\sigma^{2}$. ∎

A.2 Proofs from Section 3

Because (9) has to hold for any event $E$ and the upper bound above holds for any event, we conclude that $M$ is $(\varepsilon,\delta)$-DP if and only if

holds for any $x\simeq x^{\prime}$. To complete the proof we need to show that (10) is equivalent to (3). Expanding the definition of $L_{M,x,x^{\prime}}$ we get:

A similar argument with $L_{M,x^{\prime},x}$ also shows:

Putting the last two equations together we obtain see that the left hand side of (3) equals the left hand side of (10). ∎

Note that Lemma 3 shows that the privacy loss random variables $L_{M,x,x^{\prime}}$ and $L_{M,x^{\prime}x}$ both follow the same distribution $\mathcal{N}(\eta,2\eta)$ with $\eta=D^{2}/2\sigma^{2}$. This allows us to write the left hand side of (4) in terms of the Gaussian CDF $\Phi$ as follows:

We prove the result by using Leibniz’s rule for differentiation under the integral sign to show that the function of interest has non-negative derivatives. First note that from the derivation of (4) we have

where $a(\eta)=\sqrt{\eta/2}-\varepsilon/\sqrt{2\eta}$. Now we can use Leibniz’s rule to write

Therefore, we see that the derivative of $h$ satisfies:

where we used that $a(\eta)^{2}+2\varepsilon=b(\eta)^{2}$. ∎

Recall that the derivations in Section 3 establish that in order to calibrate a Gaussian perturbation to achieve $(\varepsilon,\delta)$-DP all that is required is find the smallest $\sigma$ such that

To establish the correctness of the analytic Gaussian mechanism we begin by observing that the argument in the first term of (11) changes sign at $\sigma=\Delta/\sqrt{2\varepsilon}$, while the argument for the second terms is always negative. Thus, we substitute $\sigma=\alpha\Delta/\sqrt{2\varepsilon}$ in the expression above and obtain:

To solve the optimization $\inf\{\alpha>0:B_{\varepsilon}(\alpha)\leq\delta\}$ using numerical evaluations of $\Phi$ it is convenient to consider the cases $\alpha\geq 1$ and $\alpha<1$ separately. In the case $\alpha\geq 1$ we define $u=(\alpha-1/\alpha)^{2}/2$ and substitute the corresponding $\alpha$ in $B_{\varepsilon}$ to obtain

Similarly, by taking $v=(1/\alpha-\alpha)^{2}/2$ in the case $\alpha<1$ we obtain

Note that, as expected, these definitions satisfy $\lim_{v\to\infty}B_{\varepsilon}^{+}(v)=1$ and $\lim_{u\to\infty}B_{\varepsilon}^{-}(u)=0$, since the limits correspond to $\lim_{\alpha\to 0}B(\alpha)=1$ and $\lim_{\alpha\to\infty}B(\alpha)=0$, respectively. Furthermore, we have

which corresponds to the privacy guarantee $(\varepsilon,\delta_{0}(\varepsilon))$-DP obtained by taking $\sigma=\Delta/\sqrt{2\varepsilon}$; i.e. $\alpha=1$.

These observations motivate the mechanism described in Algorithm 1. In particular, for $\delta\geq\delta_{0}(\varepsilon)$ we can achieve $(\varepsilon,\delta)$-DP with $\alpha<1$, and the smallest $\alpha<1$ such that $B_{\varepsilon}(\alpha)\leq\delta$ corresponds to the largest $v\geq 0$ such that $B_{\varepsilon}^{+}(v)\leq\delta$. Similarly, for $\delta<\delta_{0}(\varepsilon)$ we require $\alpha\geq 1$, and the smallest $\alpha\geq 1$ such that $B_{\varepsilon}(\alpha)\leq\delta$ corresponds to the smallest $u\geq 0$ such that $B_{\varepsilon}^{-}(u)\leq\delta$. ∎

A.3 Proofs from Section 4

The proofs in this section are well-known and not part of the contribution of the current paper. We include these proofs because they are short and revealing and we hope to be self-contained as much as possible.

Take the gradient with respect to $\theta$ on both sides and apply Fubini’s theorem

Note that $\frac{\|\hat{y}\|^{2}}{w^{2}+\sigma^{2}}$ follows a $\chi^{2}$ distribution with degree of freedom $d$. The likelihood function

The gradient w.r.t. $w^{2}$ of the log-likelihood, we get

Appendix B Additional Experiments

Here we present additional experimental results. Figure 3 provides more plots for the setups explored in Sections 5.1 and 5.2. The next two sections present further experiments on a sparse histogram denoising task and on the New York City taxi dataset.

For this task, each dataset is sampled from a multinomial distribution with parameters sampled from a symmetric Dirichlet with $\alpha=1/d$. The parameters are resampled for each individual experiment. The choice of $\alpha$ guarantees that the resulting histograms are highly sparse Telgarsky . Our setup follows the same structure as the one for the experiments from previous section. The results are presented in Figure 4. We observe that in this problem the Laplace mechanism is better than the classical Gaussian mechanism, and in the setting $\varepsilon=1$ it is even better than the analytic Gaussian mechanism, with and without denoising. However, as we decrease $\varepsilon$ the utility of the analytic Gaussian mechanism becomes better than that of the Laplace mechanism, and denoising provides a significant advantage over mechanisms without denoising. Finally, we note that due to the sparsity of the underlying datapoint, denoising via soft thresholding provides better utility in this case than denoising via shrinking.

B.2 New York City Taxi Heat Maps

Here we present a second qualitative experiment with the New York City taxi dataset. The difference with the previous experiment is that we use data for a different time of the same day, leading to a different structure in the activities around the city; see Figure 2. This illustrates that the selected denoising methods are adaptive to the structure of the underlying data.

Furthermore, Figure 6 presents quantitative results where we compare the mean square error (MSE) of cGM, aGM as well as the aforementioned denoising techniques. As we can see, on the real datasets, aGM always improves over cGM by a constant factor and denoising techniques are able to leverage bias-variance trade-off and improve the recovery in MSE further. The benefits of denoising range from orders of magnitude (in the case when $\varepsilon$ is tiny) to a small constant factor (when $\varepsilon$ is moderate). In the low-privacy regime (e.g., $\varepsilon>5$), soft-thresholding performs a little worse than not using it at all. This is the expected cost of adaptivity and it does appear in its error bound.