Smooth Sensitivity Revisited: Towards Optimality

Hladík, Richard; Tětek, Jakub

doi:10.4230/LIPIcs.FORC.2025.2

Smooth Sensitivity Revisited: Towards Optimality

Richard Hladík

ETH Zurich, Switzerland Jakub Tětek

INSAIT, Sofia University “St. Kliment Ohridski”, Bulgaria

Abstract

Smooth sensitivity is one of the most commonly used techniques for designing practical differentially private mechanisms. In this approach, one computes the smooth sensitivity of a given query $q$ on the given input $D$ and releases $q(D)$ with noise added proportional to this smooth sensitivity. One question remains: what distribution should we pick the noise from?

In this paper, we give a new class of distributions suitable for the use with smooth sensitivity, which we name the $\operatorname{PolyPlace}$ distribution. This distribution improves upon the state-of-the-art Student’s T distribution in terms of standard deviation by arbitrarily large factors, depending on a “smoothness parameter” $\gamma$ , which one has to set in the smooth sensitivity framework. Moreover, our distribution is defined for a wider range of parameter $\gamma$ , which can lead to significantly better performance.

Furthermore, we prove that the $\operatorname{PolyPlace}$ distribution converges for $\gamma\rightarrow 0$ to the Laplace distribution and so does its variance. This means that the Laplace mechanism is a limit special case of the $\operatorname{PolyPlace}$ mechanism. This implies that our mechanism is in a certain sense optimal for $\gamma\rightarrow 0$ .

Keywords and phrases:

differential privacy, smooth sensitivity

Funding:

Richard Hladík: Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 Research and Innovation Programme (grant agreement No. 949272)

Copyright and License:

2012 ACM Subject Classification:

Security and privacy

\rightarrow

Privacy-preserving protocols

Related Version:

Full Version: https://arxiv.org/abs/2407.05067

Acknowledgements:

We would like to thank Rasmus Pagh and Adam Sealfon for helpful discussions. We would like to thank Rasmus Pagh for hosting Richard at the University of Copenhagen. Jakub worked on this paper while affiliated with BARC, University of Copenhagen. Richard partially worked on this paper while visiting BARC, University of Copenhagen.

Funding:

Partially funded by the Ministry of Education and Science of Bulgaria’s support for INSAIT as part of the Bulgarian National Roadmap for Research Infrastructure. Partially supported by the VILLUM Foundation grants 54451 and 16582.

DOI:

10.4230/LIPIcs.FORC.2025.2

Event:

6th Symposium on Foundations of Responsible Computing (FORC 2025)

Editors:

Mark Bun

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Differential privacy has in recent years become the golden standard for data privacy. Possibly the most common way of achieving differential privacy for numerical queries is the Laplace mechanism, which adds noise from the Laplace distribution scaled with the global sensitivity of the query.¹¹1The global sensitivity is defined as the greatest difference in the query value between some two neighboring datasets. However, global sensitivity has one significant shortcoming: it is not adaptive to the dataset at hand. Namely, the error on every input is the same as that on the most difficult input, which determines the global sensitivity.

One of the most common ways to get practical mechanisms with instance-adaptive performance is to use smooth sensitivity. In contrast with global sensitivity, the smooth sensitivity can adapt to a specific dataset, meaning that easier inputs can have significantly lower errors. The approach works by computing the $\gamma$ -smooth sensitivity (Definition 2) of the given query $q$ on the input $D$ at hand for a smoothness parameter $\gamma$ , and releasing $q(D)$ with added noise scaled with the $\gamma$ -smooth sensitivity, picked from an appropriately chosen distribution. The parameter $\gamma$ here controls a tradeoff between how large the $\gamma$ -smooth sensitivity is on one hand, and how concentrated a distribution we can use for the noise on the other. This leaves one important question unanswered: what distribution should the noise be sampled from?

In this paper, we give a new distribution class suitable for use with smooth sensitivity, which we name the $\operatorname{PolyPlace}$ distribution (Definition 6). The specific distribution from the class that we use depends on the smoothness parameter $\gamma$ and the privacy parameter $\varepsilon$ . Our distribution has two advantages over the state-of-the-art Student’s T distribution: (1) it achieves significantly smaller error, having standard deviation smaller by arbitrarily large factors (depending on $\gamma$ ), as shown in Figure 1, and (2) it is defined for any $\gamma<\varepsilon$ , whereas the previously used distributions all required $\gamma<\varepsilon/2$ . While this may seem as an improvement by a constant factor, it may in fact bring asymptotic decrease of the error as smooth sensitivity can change by an arbitrarily large amount even with a small change in $\gamma$ . Our method also significantly improves upon the Laplace distribution for all but tiny values of $\gamma$ (Laplace distribution moreover provides only approximate DP when used with smooth sensitivity). One of the main strengths of our mechanism is that it is completely general and it provides an improvement in any application relying on smooth sensitivity.

We also prove that for $\gamma\rightarrow 0$ , our $\operatorname{PolyPlace}$ distributions converge in distribution to the Laplace distribution and the variance of $\operatorname{PolyPlace}$ also converges to that of the Laplace distribution. At the same time, with $\gamma\rightarrow 0$ , the $\gamma$ -smooth sensitivity $\SS^{\gamma}$ converges to the global sensitivity. This means that in some sense, our proposed mechanism generalizes the Laplace mechanism, which is a limit special case of our mechanism for $\gamma=0$ . Since the Laplace mechanism is optimal for pure differential privacy [8], this means that our method is also optimal for $\gamma\rightarrow 0$ in the sense that any quantile of $\operatorname{PolyPlace}$ converges to that of the optimal distribution. Our result can be summarized as follows:

Theorem 1 (Informal version of Theorem 8).

Let us have a query $q$ and two parameters $0<\gamma<\varepsilon$ . Let $D$ be a dataset. There exists a class of distributions $\operatorname{PolyPlace}(s,\alpha)$ such that releasing

q(D)+\operatorname{PolyPlace}\left(\frac{\SS_{q}^{\gamma}(D)}{\gamma},\frac{% \varepsilon}{\gamma}\right)

is $\varepsilon$ -DP. Moreover, for $\gamma/\varepsilon\rightarrow 0$ , the variance is up to a factor $(1+o(1))$ the same as scaling the Laplace distribution with the smooth sensitivity. Also, for any value $a>0$ it holds that $\operatorname{PolyPlace}(\frac{a}{\gamma},\frac{\varepsilon}{\gamma})% \xrightarrow{\text{d}}\operatorname{Lap}(a/\varepsilon)$ .

Figure 1: Comparison of the standard deviation of our and the other distributions that can be used with the smooth sensitivity framework. Laplace distribution when used with smooth sensitivity only provides approximate differential privacy; we assume here

\delta=10^{-5}

. The shape parameters for the two other distributions are numerically selected so as to minimize their standard deviations. The standard deviations are calculated in Appendix B. The dashed line represents the standard deviation of the Laplace distribution which, however, needs to be used with the larger global sensitivity and not smooth sensitivity.

Note that this convergence result is meaningful despite the fact that the smooth sensitivity converges to the global sensitivity for $\gamma\rightarrow 0$ : This result implies that for fixed small values of $\gamma$ , the distribution is close to optimal, while the smooth sensitivity will, in general, still be asymptotically smaller than the global sensitivity. This refutes the following argument, that one might naturally make against our result: Namely, that since the smooth sensitivity is, for $\gamma\rightarrow 0$ , equal to the global sensitivity, this result does not show anything that would not already hold for the Laplace mechanism.

Smooth Sensitivity vs. Inverse Sensitivity Mechanism

Recently, an alternative to smooth sensitivity appeared in the form of the inverse sensitivity mechanism [1, 2]. This approach has nice theoretical guarantees, and mechanisms that are optimal up to logarithmic factors have been designed by relying on inverse sensitivity. Admittedly, this reduces the overall impact of our approach. However, we are still convinced that smooth sensitivity has an important place in the repertoire of differential privacy techniques, and that it will continue to be used in practice.

The inverse sensitivity mechanism comes with its own problems. First, inverse sensitivity may be difficult to compute [1, 7], even in cases when smooth sensitivity is easy to compute, such as for counting triangles in a graph. While it is often possible to efficiently approximately implement the inverse sensitivity mechanism [1, 7], this already leads to worsened performance – it remains to be seen whether this approach will be competitive in practice for a wide range of problems.

Moreover, there are practical considerations that often favor the smooth sensitivity approach. First, it is possible to have an efficient generic implementation just based on an oracle that returns the smooth sensitivity. This is clearly not possible for the inverse sensitivity mechanism – the inverse sensitivity mechanism instantiates the exponential mechanism which in general cannot be implemented in time sublinear in the size of the universe. It is also due to this ease of use that there is extensive literature on the uses of smooth sensitivity on the applied side, as we discuss in Section 1.2. We think that even just the existence of this large amount of literature on smooth sensitivity would make improving smooth sensitivity an important undertaking.

Another issue with the inverse sensitivity mechanism is that it may in some cases have worse constants than smooth sensitivity. Specifically, it relies on the exponential mechanism which loses a factor of 2 in some instances. There are other mechanisms that could be used in place of the exponential mechanism, most notably the report-noisy-max mechanism [5], that may have better constants, but even those lose a factor of 2 in the standard deviation in some cases. For example, the Laplace mechanism can be seen as an instantiation of the exponential mechanism or report noisy max, but in doing so, one would lose a factor of 2. Our mechanism for smooth sensitivity does not have this issue (unlike the previously known smooth sensitivity mechanisms that achieved pure differential privacy).

1.1 Technical Overview

The principle that motivated the $\operatorname{PolyPlace}$ distribution is that we wanted to make sure that for $\varepsilon\rightarrow 0$ , the privacy loss will be the same regardless of what value we released (recall that the privacy loss random variable is a function of the value that we release). Indeed, this is precisely the property that the Laplace distribution has in the context of global sensitivity. We formalize this property as a claim about some derivatives involving the density of the $\operatorname{PolyPlace}$ distribution (Lemma 12). Intuitively speaking, these derivatives capture an “infinitesimal privacy loss” as if we had two neighboring datasets whose query values as well as smooth sensitivities differ infinitesimally. In Lemma 9, we essentially integrate this infinitesimal privacy loss in order to express the true privacy loss. Doing so takes bounds on the infinitesimal privacy loss and gives bounds on the actual privacy loss, proving differential privacy.

Intuitively speaking, our improvement comes from two sources. The first is unsurprisingly that our distribution simply has a smaller variance than the Student’s $T$ distribution. The second source of our improvement is more subtle: we do not split the privacy budget the way previous work did. Intuitively speaking, there are two sources of privacy loss when we use smooth sensitivity: from the change in the query value between adjacent inputs (corresponding to shifting of noise) and from the change in the smooth sensitivity between neighboring datasets (corresponding to scaling noise). The standard approach is to split the privacy budget between the privacy loss caused by the shifting and the privacy loss caused by scaling. Surprisingly, if the scaling is not too large, it does not contribute anything to the worst-case privacy loss with the $\operatorname{PolyPlace}$ distribution. This allows us in some sense to use all of the privacy budget to “pay” for the change in query value between neighboring datasets, leading to a more efficient use of the privacy budget.

1.2 Related Work

Smooth sensitivity has been proposed by Nissim, Raskhodnikova, and Smith [12] as an alternative to global sensitivity, rectifying the global sensitivity’s drawback that it is determined by the most difficult input. They have shown how it can be used to privately approximately release the median, minimum, minimum spanning tree, and the number of triangles in a graph. Bun and Steinke [3] later gave new distributions suitable for use with smooth sensitivity. Notably, they propose the use of the Student’s T distribution. They also propose other distributions but those only work with the weaker concentrated differential privacy [6], which we do not focus on in this paper.

Since its inception, smooth sensitivity has been used in many applications. An incomplete list includes: principal component analysis [9], deep learning [13], statistics from genome-wide association studies [17], generating synthetic datasets using Bayesian models [11], generating synthetic graphs [15], random forests [16], or some graph centrality measures [10].

Other frameworks for beyond-worst-case differentially private mechanisms include propose-test-release [4], or privately bounding local sensitivity [14, Section 3.4]. However, these techniques only give approximate differential privacy and they generally speaking tend to need larger datasets to work. Namely, to get non-trivial guarantees, they usually need a dataset of size $\Omega\big{(}\frac{\log\delta^{-1}}{\varepsilon}\big{)}$ .²²2This is the case for propose-test-release as it otherwise always fails. For privately bounding local sensitivity, this is the case assuming the local sensitivity has global sensitivity 1 (it often has bigger sensitivity in which case the situation is even worse). For these reasons as well as for the sake of brevity, we choose not to focus on these techniques.

2 Preliminaries

2.1 Differential Privacy

Let us have a symmetric notion of dataset adjacency $\sim$ . A randomized algorithm $\mathcal{A}$ is said to be $\varepsilon$ -differentially private if, for any two adjacent datasets $D,D^{\prime}$ , and for any measurable set $S$ , the following condition holds:

\Pr[\mathcal{A}(D)\in S]\leq e^{\varepsilon}\cdot\Pr[\mathcal{A}(D^{\prime})% \in S],

where $\varepsilon$ controls the trade-off between privacy and data utility. Smaller values of $\varepsilon$ provide stronger privacy guarantees, but may limit the accuracy of the analysis. One of the most notable ways of achieving differential privacy is using the notion of smooth sensitivity:

Definition 2 (Smooth sensitivity).

Let us have a query $q:\mathcal{D}\rightarrow\mathbb{R}$ . We define the local sensitivity of $q$ at $D\in\mathcal{D}$ as

\operatorname{LS}_{q}(D)=\max\left\{\,|q(D)-q(D^{\prime})|:D^{\prime}\sim D\,% \right\}.

In turn, we define the $\gamma$ -smooth sensitivity of $q$ at $D$ as

\SS_{q}^{\gamma}(D)=\max\left\{\,\operatorname{LS}_{q}(D^{\prime})\cdot e^{-% \gamma d(D,D^{\prime})}:D^{\prime}\in\mathcal{D}\,\right\},

where $d(D,D^{\prime})$ denotes distance induced by $\sim$ .

2.2 Calculus

We now give several statements from calculus. The following is a standard result.

Fact 3.

Let us have $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ . If at a point $\mathbf{x}\in\mathbb{R}^{n}$ , all partial derivatives exist and are continuous, then the function is differentiable at $\mathbf{x}$ .

For the following two statements, we choose to give statements of special cases that suffice for our needs, instead of giving the more general cases. We defer their proofs to Appendix A.

Fact 4.

Let us have a function $f:\mathbb{R}^{2}\rightarrow\mathbb{R}$ . At any $x$ at which $f(x,x)$ is differentiable, it holds

\displaystyle\frac{d}{dx}\,f(x,x)

\displaystyle=\left[\frac{d}{d\lambda}\,f(x+\lambda,x)+\frac{d}{d\lambda}\,f(x% ,x+\lambda)\right]_{\lambda=0}.

Fact 5.

Let us have a real function $f$ . It holds that

\left[\frac{d}{dx}\,f(c\,x)\right]_{x=0}=c\,\left[\frac{d}{dx}\,f(x)\right]_{x% =0}\,.

3 Improved Smooth Sensitivity Mechanism

Definition 6.

We define the $\operatorname{PolyPlace}(s,\alpha)$ distribution with scale $s>0$ and shape $\alpha>1$ by its probability density function

\displaystyle f_{s,\alpha}(x)=\begin{cases}N_{s,\alpha}(\alpha-1)\left(1-\frac% {|x|}{s}\right)^{\alpha-1}&\thinspace\text{if }\frac{|x|}{s}<\alpha^{-1},\\ N_{s,\alpha}(\alpha+1)\left(1-\frac{1}{\alpha^{2}}\right)^{\alpha}\left(1+% \frac{|x|}{s}\right)^{-\alpha-1}&\thinspace\text{otherwise,}\end{cases}

for $N_{s,\alpha}=\frac{\alpha}{2\left(2\left(\frac{\alpha-1}{\alpha}\right)^{% \alpha}+\alpha-1\right)s}$ .

Figure 2: A log-scale plot of selected members of the Laplace and

\operatorname{PolyPlace}

families of distributions. The values of

\alpha

and

s

correspond (for

\SS(D)=1

and

\varepsilon=1

) to

\gamma\approx 0.91,\gamma=2/3

, and

\gamma=0.2

, respectively. Note that the distributions get closer to Laplace, which is explained by the convergence from Theorem 8.

We plot a few example members of this family of distributions in Figure 2, where we also compare it with the Laplace distribution.

We start by claiming that this distribution is correctly defined. We defer the proof to Appendix A.

Lemma 7.

The distribution $\operatorname{PolyPlace}(s,\alpha)$ is correctly defined for $s>0,\alpha>1$ . That is, the density is non-negative and integrates to $1$ .

We now state our main result.

Theorem 8.

Let us have a query $q:\mathcal{D}\rightarrow\mathbb{R}$ . Let us have two parameters $0<\gamma<\varepsilon$ . Then the mechanism

M(D)=q(D)+\operatorname{PolyPlace}\left(\frac{\SS_{q}^{\gamma}(D)}{\gamma},% \frac{\varepsilon}{\gamma}\right)

is $\varepsilon$ -DP. Moreover, for $\gamma/\varepsilon\rightarrow 0$ , it holds that

\operatorname{Var}(M(D))=(1+O(\gamma/\varepsilon))\,\frac{2\SS_{q}^{\gamma}(D)% ^{2}}{\varepsilon^{2}}

and for any value $a>0$ it holds that $\operatorname{PolyPlace}\big{(}\frac{a}{\gamma},\frac{\varepsilon}{\gamma}\big% {)}\xrightarrow{\text{d}}\operatorname{Lap}(a/\varepsilon)$ .

Proof.

We prove the asymptotic expansion of the variance in Corollary 14. We show that the distribution converges to Laplace in Lemma 15.

It remains to prove privacy. Let $p_{M(D)}$ denote the density function of $M(D)$ . We then have

\displaystyle\frac{p_{M(D^{\prime})}(x)}{p_{M(D)}(x)}=\frac{f_{\SS_{q}^{\gamma% }(D^{\prime})/\gamma,\varepsilon/\gamma}(x-q(D^{\prime}))}{f_{\SS_{q}^{\gamma}% (D)/\gamma,\varepsilon/\gamma}(x-q(D))}\leq e^{\varepsilon}\,,

where final inequality holds by Lemma 9. This implies $\varepsilon$ -differential privacy. $\hfill\blacktriangleleft$

Proving Privacy

In this section, we prove Lemma 9, which is the result we used above to prove that our mechanism is differentially private. The technical parts of the proof of the lemma appear in Lemmas 12, 10, and 11. The casual reader may wish to skip the proof of Lemma 9 as well as the other lemmas in this subsection.

Lemma 9.

Let $q:\mathcal{D}\rightarrow\mathbb{R}$ for $\mathcal{D}$ being the set of all possible datasets, be a query function. Let us have two neighboring datasets $D\sim D^{\prime}$ and $x\in\mathbb{R}$ . Then

\frac{f_{\SS_{q}^{\gamma}(D^{\prime})/\gamma,\varepsilon/\gamma}(x-q(D^{\prime% }))}{f_{\SS_{q}^{\gamma}(D)/\gamma,\varepsilon/\gamma}(x-q(D))}\leq e^{% \varepsilon},

where $f$ is defined in Definition 6.

Proof.

Let $x^{\prime}=\frac{x-q(D)}{\SS_{q}^{\gamma}(D)}$ and define $\lambda_{r}$ such that $e^{\lambda_{r}\gamma}=\frac{\SS_{q}^{\gamma}(D^{\prime})}{\SS_{q}^{\gamma}(D)}$ . Let also $\lambda_{s}=\frac{q(D)-q(D^{\prime})}{\SS_{q}^{\gamma}(D)}$ and $y(t)=e^{-\lambda_{r}\gamma t}(x^{\prime}+\lambda_{s}t)$ . Note that for any $s>0,\alpha>1$ and $c>0$ , it holds

\displaystyle f_{s,\alpha}(x)=cf_{cs,\alpha}(cx).

(1)

We now give a bound and we explain the individual steps below.

	$\displaystyle\frac{f_{\SS_{q}^{\gamma}(D^{\prime})/\gamma,\varepsilon/\gamma}(% x-q(D^{\prime}))}{f_{\SS_{q}^{\gamma}(D)/\gamma,\varepsilon/\gamma}(x-q(D))}$
	$\displaystyle=\frac{\SS_{q}^{\gamma}(D)\cdot f_{e^{\lambda_{r}\gamma}/\gamma,% \varepsilon/\gamma}(\frac{x-q(D^{\prime})}{\SS_{q}^{\gamma}(D)})}{\SS_{q}^{% \gamma}(D)\cdot f_{1/\gamma,\varepsilon/\gamma}(\frac{x-q(D)}{\SS_{q}^{\gamma}% (D)})}$		(2)
	$\displaystyle=\frac{f_{e^{\lambda_{r}\gamma}/\gamma,\varepsilon/\gamma}(x^{% \prime}+\lambda_{s})}{f_{1/\gamma,\varepsilon/\gamma}(x^{\prime})}$		(3)
	$\displaystyle=\exp\left(\log f_{e^{\lambda_{r}\gamma}/\gamma,\varepsilon/% \gamma}(x^{\prime}+\lambda_{s})-\log f_{1/\gamma,\varepsilon/\gamma}(x^{\prime% })\right)$
	$\displaystyle=\exp\left(\int_{0}^{1}\Big{(}\frac{d}{dt}\log(f_{e^{\lambda_{r}t% \gamma}/\gamma,\varepsilon/\gamma}(x^{\prime}+\lambda_{s}t))\,\Big{)}dt\right)$		(4)
	$\displaystyle=\exp\left(\int_{0}^{1}\Big{[}\frac{d}{d\lambda}\log(f_{e^{% \lambda_{r}(t+\lambda)\gamma}/\gamma,\varepsilon/\gamma}(x^{\prime}+\lambda_{s% }t))\right.$
	$\displaystyle\qquad\qquad+\left.\frac{d}{d\lambda}\log(f_{e^{\lambda_{r}t% \gamma}/\gamma,\varepsilon/\gamma}(x^{\prime}+\lambda_{s}(t+\lambda)))\,\Big{]% }_{\lambda=0}dt\right)$		(5)
	$\displaystyle=\exp\left(\int_{0}^{1}\Big{[}\frac{d}{d\lambda}\log(f_{e^{% \lambda_{r}\lambda\gamma}/\gamma,\varepsilon/\gamma}(y(t)))\quad+\frac{d}{d% \lambda}\log(f_{1/\gamma,\varepsilon/\gamma}(y(t)+e^{-\lambda_{r}t\gamma}% \lambda_{s}\lambda))\,\Big{]}_{\lambda=0}dt\right)$
	$\displaystyle=\exp\left(\int_{0}^{1}\Big{[}\lambda_{r}\frac{d}{d\lambda}\log(f% _{e^{\lambda\gamma}/\gamma,\varepsilon/\gamma}(y(t)))\right.$
	$\displaystyle\qquad\qquad+\left.e^{-\lambda_{r}t\gamma}\lambda_{s}\frac{d}{d% \lambda}\log(f_{1/\gamma,\varepsilon/\gamma}(y(t)+\lambda))\,\Big{]}_{\lambda=% 0}dt\right)$		(6)
	$\displaystyle\leq\exp\left(\int_{0}^{1}\bigg{[}\lambda_{r}\Big{\|}\frac{d}{d% \lambda}\log(f_{e^{\lambda\gamma}/\gamma,\varepsilon/\gamma}(y(t)))\Big{\|}\right.$
	$\displaystyle\qquad\qquad+\left.e^{-\lambda_{r}t\gamma}\lambda_{s}\Big{\|}\frac% {d}{d\lambda}\log(f_{1/\gamma,\varepsilon/\gamma}(y(t)+\lambda))\,\Big{\|}\bigg% {]}_{\lambda=0}dt\right)$
	$\displaystyle\leq\exp\left(\int_{0}^{1}\bigg{[}\Big{\|}\frac{d}{d\lambda}\log(f% _{e^{\lambda\gamma}/\gamma,\varepsilon/\gamma}(y(t)))\Big{\|}\quad+\Big{\|}\frac% {d}{d\lambda}\log(f_{1/\gamma,\varepsilon/\gamma}(y(t)+\lambda))\,\Big{\|}\bigg% {]}_{\lambda=0}dt\right)$		(7)
	$\displaystyle=\exp\left(\int_{0}^{1}\varepsilon\,dt\right)=e^{\varepsilon}.$		(8)

We now justify the manipulations that may not be clear. Equality (2) holds by Equation 1. Equality (3) holds by the definition of $x^{\prime}$ and $\lambda_{s}$ . The equality (4) holds because of the fundamental theorem of calculus; we use here the fact that by Lemma 11, the function

\ell(y,z)=\log(f_{e^{\lambda_{r}y\gamma}/\gamma,\varepsilon/\gamma}(x^{\prime}% +\lambda_{s}z))

is differentiable except at points where $x^{\prime}+\lambda_{s}z=0$ , at which points it is continuous; furthermore, the function $\phi(t)=\ell(t,t)$ is continuous everywhere and differentiable everywhere except for at most one point where $x^{\prime}+\lambda_{s}t=0$ . The equality (5) holds by (4); we again used that $h$ is differentiable everywhere except for the at most one $t$ satisfying $x^{\prime}+\lambda_{s}t=0$ . The equality (6) holds by viewing each summand as a univariate function in $\lambda$ and applying Equation 5. The bound (7) holds because we argue below that the removed constants are $\lambda_{r},e^{-\lambda_{r}t\gamma}\gamma_{s}\leq 1$ . The equality (8) holds by the Lemma 12 below.

It remains to prove $\lambda_{r},e^{-\lambda_{r}t\gamma}\gamma_{s}\leq 1$ . The definition of smooth sensitivity ensures that $\frac{\SS_{q}^{\gamma}(D^{\prime})}{\SS_{q}^{\gamma}(D)}\leq e^{\gamma}$ , and thus it holds that $\lambda_{r}\leq 1$ . It also holds

q(D)-q(D^{\prime})\leq\min(\SS_{q}^{\gamma}(D),\SS_{q}^{\gamma}(D^{\prime}))

and thus

\lambda_{s}\leq\min\left(1,\;\frac{\SS_{q}^{\gamma}(D)}{\SS_{q}^{\gamma}(D^{% \prime})}\right).

It thus holds $e^{-\lambda_{r}t\gamma}\lambda_{s}\leq 1$ as we needed to prove. $\hfill\blacktriangleleft$

In the following lemma, we explicitly calculate the derivatives of $\log f_{s,\alpha}(x)$ with respect to $s$ and $x$ , which is useful for Lemmas 11 and 12.

Lemma 10.

For $\alpha>1$ and $h:\mathbb{R}_{>0}\times\mathbb{R}\to\mathbb{R}$ defined as $h(s,x)=\log f_{s,\alpha}(x)$ , it holds for any $x\neq 0$ :

	$\displaystyle\left[\frac{d}{d\lambda}h(s,x+\lambda)\right]_{\lambda=0}$	$\displaystyle=\operatorname*{sgn}(x)\cdot\begin{dcases}\frac{\alpha-1}{\|x\|-s}&% \text{if }\frac{\|x\|}{s}<\alpha^{-1},\\ \frac{-\alpha-1}{\|x\|+s}&\text{otherwise},\end{dcases}$
	$\displaystyle\left[\frac{d}{d\lambda}h(e^{\lambda/s}s,x)\right]_{\lambda=0}$	$\displaystyle=\begin{dcases}-\frac{1}{s}+\frac{(\alpha-1)\|x\|}{s(s-\|x\|)}&\text{% if }\frac{\|x\|}{s}<\alpha^{-1},\\ -\frac{1}{s}+\frac{(\alpha+1)\|x\|}{s(s+\|x\|)}&\text{otherwise}.\end{dcases}$

Proof.

The statement follows from direct computation. Full proof is deferred to Appendix A. $\hfill\blacktriangleleft$ We proceed with a technical lemma that justifies the invocation of the fundamental theorem of calculus in the proof of Lemma 9.

Lemma 11.

Let $0<\gamma<\varepsilon$ ; $\lambda_{r},\lambda_{s},x^{\prime}\in\mathbb{R}$ . The function

\ell(y,z)=\log(f_{e^{\lambda_{r}y\gamma}/\gamma,\varepsilon/\gamma}(x^{\prime}% +\lambda_{s}z))

is continuous everywhere. It is differentiable everywhere, except when $x^{\prime}+\lambda_{s}z=0$ .

Proof.

Set $\alpha=\varepsilon/\gamma$ and take $h$ from Lemma 10. Define $y^{\prime}=e^{\lambda_{r}y\gamma}/\gamma$ and $z^{\prime}=x^{\prime}+\lambda_{s}z$ . Then $\ell(y,z)=h(y^{\prime},z^{\prime})$ and we have

	$\displaystyle\frac{d}{dy}\ell(y,z)=\left[\ell(y+\lambda,z)\right]_{\lambda=0}$	$\displaystyle=\left[h(y^{\prime}\cdot e^{\lambda_{r}\lambda\gamma},z^{\prime})% \right]_{\lambda=0},$
	$\displaystyle\frac{d}{dz}\ell(y,z)=\left[\ell(y,z+\lambda)\right]_{\lambda=0}$	$\displaystyle=\left[h(y^{\prime},z^{\prime}+\lambda_{s}\lambda)\right]_{% \lambda=0}.$

Now we can apply Lemma 10 on the right-hand sides, together with the chain rule, to obtain that the partial derivatives on the left exist and are continuous for all $(y,z)$ such that $z^{\prime}=x^{\prime}+\lambda_{s}z\neq 0$ . By Fact 3 and the fact that around every $(y,z)$ , there is a sufficiently small neighborhood where $x^{\prime}+\lambda_{s}z\neq 0$ , we get that $\ell$ is differentiable (and thus continuous) in every $(y,z)$ with $x^{\prime}+\lambda_{s}z\neq 0$ .

It remains to prove that $\ell$ is also continuous for $x^{\prime}+\lambda_{s}z=0$ . It suffices to show that $h(s,x)$ is continuous at $(s,0)$ for all choices of $s>0$ . The first branch $h_{1}$ of $h$ is continuous everywhere, and for any $(s,0)$ , there exists a sufficiently small $\varepsilon$ -neighborhood of $(s,0)$ where $|x|/s<\alpha^{-1}$ , that is, where $h(s,x)=h_{1}(s,x)$ . Therefore, $h$ is continuous at $(s,0)$ . $\hfill\blacktriangleleft$

Lemma 12.

Let $x\in\mathbb{R}\setminus\{0\}$ and let $0<\gamma<\varepsilon$ . It holds

\displaystyle\Bigg{[}\bigg{|}\frac{d}{d\lambda}\log(f_{1/\gamma,\varepsilon/% \gamma}(x+\lambda))\Bigg{|}+\Bigg{|}\frac{d}{d\lambda}\log(f_{e^{\lambda\gamma% }/\gamma,\varepsilon/\gamma}(x)))\bigg{|}\Bigg{]}_{\lambda=0}=\varepsilon.

(9)

Proof sketch.

For the full proof, see Appendix A. The main idea of the proof is to calculate both expressions in the sum using Lemma 10, with $s=1/\gamma$ and $\alpha=\varepsilon/\gamma$ . Then, we distinguish two cases: either $|x|/s<\alpha^{-1}$ , or $|x|/s\geq\alpha^{-1}$ . For both cases separately, and for each absolute value, we can argue that the expression inside this absolute value will always have the same sign, and can be therefore written without the absolute value. This simplifies the analysis, and we can then verify that the left-hand side of Equation 9 always sums up to $\alpha/s$ . Finally, we substitute $s$ and $\alpha$ back to get $\alpha/s=\varepsilon$ . $\hfill\blacktriangleleft$

3.1 Properties of the $\operatorname{PolyPlace}(s,\alpha)$ Distribution

We now give a lemma that among others states the variance of $\operatorname{PolyPlace}$ . To make sure we have not made a mistake in the very technical manipulations, we have checked that we get the same result if we approximate the variance by numerical integration.³³3Specifically, by scaling, we can assume w.l.o.g. that $s=1$ . For this value of $s$ , we have plotted the variance as calculated by numeric integration and the expression above. We checked that they are indeed the same. We defer the proof to Appendix A.

Lemma 13.

$\operatorname{PolyPlace}$ has mean $0$ and variance

\displaystyle\sigma^{2}_{s,\alpha}=2s^{2}\frac{\left(\frac{1}{\alpha}+1\right)% ^{-\alpha}\left(\left(19\alpha^{2}+5\right)\left(1-\frac{1}{\alpha^{2}}\right)% ^{\alpha}+(\alpha-2)(\alpha-1)^{2}\left(\frac{1}{\alpha}+1\right)^{\alpha}% \right)}{\left(2\left(\frac{\alpha-1}{\alpha}\right)^{\alpha}+\alpha-1\right)% \left(\alpha^{4}-5\alpha^{2}+4\right)}.

Corollary 14.

Assume $\gamma<\varepsilon/2$ . It holds

\operatorname{Var}(M(D))=(1+O(\gamma/\varepsilon))\,\frac{2\SS_{q}^{\gamma}(D)% ^{2}}{\varepsilon^{2}}.

Proof.

We substitute into the above lemma with $s=\SS_{q}^{\gamma}(D)/\gamma$ , $\alpha=\varepsilon/\gamma$ , and take the Taylor expansion of order one w.r.t. $\gamma$ around $\gamma=0$ . We skip routine steps in the computation and just state that the second-order Taylor expansion is

\frac{2{\SS_{q}^{\gamma}(D)}^{2}}{\varepsilon^{2}}-\frac{2(3e-17)\gamma{\SS_{q% }^{\gamma}(D)}^{2}}{e\varepsilon^{3}}+O\left(\gamma^{2}\right).

This is exactly as we claim. $\hfill\blacktriangleleft$

Note that the variance of the Laplace distribution scaled to the smooth sensitivity is $\frac{2}{\varepsilon^{2}}$ , meaning that for $\gamma/\varepsilon\rightarrow 0$ , the variance of our mechanism approaches that of the Laplace mechanism scaled to the smooth sensitivity. In fact, the distribution converges to the Laplace distribution for $\gamma\rightarrow 0$ .

Lemma 15.

For $\gamma\rightarrow 0$ and any $a,\varepsilon>0$ , it holds that $f_{a/\gamma,\varepsilon/\gamma}$ converges pointwise to the probability density function (pdf) of $\operatorname{Lap}(a/\varepsilon)$ .

Proof.

Let us denote the pdf of $\operatorname{Lap}(a/\varepsilon)$ by $f_{\operatorname{Lap}(a/\varepsilon)}$ . We prove pointwise convergence, that is, that for any $x\in\mathbb{R}$ , $f_{a/\gamma,\varepsilon/\gamma}(x)\rightarrow f_{\operatorname{Lap}(a/% \varepsilon)}(x)$ . This in turn implies the desired convergence in distribution.⁴⁴4This holds because by Scheffé’s lemma, this means that the TV distance of the two distributions goes to zero, which in turn implies convergence in distribution. Since $f_{\operatorname{Lap}(a/\varepsilon)}$ is bounded, this follows if we prove that for $\gamma/\varepsilon\rightarrow 0$ and any fixed $a>0$ and $x\in\mathbb{R}$ , it holds that $f_{a/\gamma,\varepsilon/\gamma}(x)/f_{\operatorname{Lap}(a/\varepsilon)}(x)\rightarrow 1$ , denoted $f_{a/\gamma,\varepsilon/\gamma}(y)\sim f_{\operatorname{Lap}(a/\varepsilon)}(y)$ . We prove this claim in the rest of this proof.

Set $s=a/\gamma$ , $\alpha=\varepsilon/\gamma$ . It holds that

	$\displaystyle\bar{f}_{1}$	$\displaystyle\overset{\text{def}}{=}\left(1-\frac{\|x\|}{s}\right)^{\alpha-1}=% \left(1-\frac{\|x\|\gamma}{a}\right)^{\varepsilon/\gamma-1}\sim\left(1-\frac{\|x\|% \gamma}{a}\right)^{\varepsilon/\gamma}$
		$\displaystyle=\left(\left(1-\frac{\|x\|\gamma}{a}\right)^{a/(\gamma\|x\|)}\right)^% {\varepsilon\|x\|/a}\sim e^{-\varepsilon\|x\|/a},$

where the first $\sim$ uses the fact that the base of the exponential converges to $1$ and the second $\sim$ uses the standard limit $(1-z)^{1/z}\rightarrow e^{-1}$ . At the same time, it holds that

	$\displaystyle c\overset{\text{def}}{=}\frac{\alpha}{2\left(2\left(\frac{\alpha% -1}{\alpha}\right)^{\alpha}+\alpha-1\right)s}$	$\displaystyle=\frac{\varepsilon/\gamma}{2\left(2\left(\frac{\varepsilon/\gamma% -1}{\varepsilon/\gamma}\right)^{\varepsilon/\gamma}+\varepsilon/\gamma-1\right% )a/\gamma}$
		$\displaystyle\sim\frac{\varepsilon/\gamma}{2\left(2e^{-1}+\varepsilon/\gamma-1% \right)a/\gamma}$
		$\displaystyle\sim\frac{\varepsilon/\gamma}{2\cdot\varepsilon/\gamma\cdot a/% \gamma}=\frac{\gamma}{2a},$

where the first $\sim$ again uses the limit $(1-z)^{1/z}\rightarrow e^{-1}$ . Overall, we can thus for $\frac{|x|}{s}<\alpha^{-1}$ write

	$\displaystyle f_{a/\gamma,\varepsilon/\gamma}(x)$	$\displaystyle=c\Big{(}\frac{\varepsilon}{\gamma}-1\Big{)}\bar{f}_{1}\sim\frac{% \gamma}{2a}\Big{(}\frac{\varepsilon}{\gamma}-1\Big{)}e^{-\varepsilon\|x\|/a}\sim% \frac{\gamma}{2a}\cdot\frac{\varepsilon}{\gamma}e^{-\varepsilon\|x\|/a}$
		$\displaystyle=\frac{\varepsilon}{2a}e^{-\varepsilon\|x\|/a}=f_{\operatorname{Lap% }(a/\varepsilon)}(x),$

as we wanted to show. The argument for $\frac{|x|}{s}\geq\alpha^{-1}$ is very similar:

	$\displaystyle\bar{f}_{2}$	$\displaystyle\overset{\text{def}}{=}\left(1+\frac{\|x\|}{s}\right)^{-\alpha-1}=% \left(1+\frac{\|x\|\gamma}{a}\right)^{-\varepsilon/\gamma-1}$
		$\displaystyle\sim\left(1+\frac{\|x\|\gamma}{a}\right)^{-\varepsilon/\gamma}\left% (\left(1+\frac{\|x\|\gamma}{a}\right)^{-a/(\gamma\|x\|)}\right)^{\varepsilon\|x\|/a}% \sim e^{-\varepsilon\|x\|/a}$

and

	$\displaystyle f_{a/\gamma,\varepsilon/\gamma}(x)$	$\displaystyle=c\,\left(\frac{\varepsilon}{\gamma}+1\right)\bigg{(}1-\frac{% \gamma^{2}}{\varepsilon^{2}}\bigg{)}^{\varepsilon/\gamma}\bar{f}_{2}$
		$\displaystyle\sim\frac{\gamma}{2a}\left(\frac{\varepsilon}{\gamma}+1\right)% \bigg{(}1-\frac{\gamma^{2}}{\varepsilon^{2}}\bigg{)}^{\varepsilon/\gamma}e^{-% \varepsilon\|x\|/a}$
		$\displaystyle\sim\frac{\gamma}{2a}\frac{\varepsilon}{\gamma}e^{-\varepsilon\|x\|% /a}$
		$\displaystyle=\frac{\varepsilon}{2a}e^{-\varepsilon\|x\|/a}=f_{\operatorname{Lap% }(a/\varepsilon)}(x),$

where the second $\sim$ uses the standard limit $(1-x^{2})^{1/x}\rightarrow 1$ for $x\rightarrow 0$ . $\hfill\blacktriangleleft$

References

[1] Hilal Asi and John C. Duchi. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, volume 33, pages 14106–14117, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/a267f936e54d7c10a2bb70dbe6ad7a89-Abstract.html.
[2] Hilal Asi and John C. Duchi. Near instance-optimality in differential privacy. CoRR, abs/2005.10630, 2020. doi:10.48550/arXiv.2005.10630.
[3] Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, volume 32, pages 181–191, 2019. URL: https://proceedings.neurips.cc/paper/2019/hash/3ef815416f775098fe977004015c6193-Abstract.html.
[4] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 – June 2, 2009, pages 371–380. ACM, 2009. doi:10.1145/1536414.1536466.
[5] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3-4):211–407, 2014. doi:10.1561/0400000042.
[6] Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CoRR, abs/1603.01887, 2016. doi:10.48550/arXiv.1603.01887.
[7] Juanru Fang, Wei Dong, and Ke Yi. Shifted inverse: A general mechanism for monotonic functions under user differential privacy. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pages 1009–1022. ACM, 2022. doi:10.1145/3548606.3560567.
[8] Natasha Fernandes, Annabelle McIver, and Carroll Morgan. The Laplace mechanism has optimal utility for differential privacy over continuous queries. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 – July 2, 2021, pages 1–12. IEEE, IEEE, 2021. doi:10.1109/LICS52264.2021.9470718.
[9] Alon Gonem and Ran Gilad-Bachrach. Smooth sensitivity based approach for differentially private PCA. In Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain, volume 83 of Proceedings of Machine Learning Research, pages 438–450. PMLR, PMLR, 2018. URL: http://proceedings.mlr.press/v83/gonem18a.html.
[10] Jesse Laeuchli, Yunior Ramírez-Cruz, and Rolando Trujillo-Rasua. Analysis of centrality measures under differential privacy models. Applied Mathematics and Computation, 412:126546, 2022. doi:10.1016/j.amc.2021.126546.
[11] Mingzhu Li and Xuebin Ma. Bayesian networks-based data publishing method using smooth sensitivity. In IEEE International Conference on Parallel & Distributed Processing with Applications, Ubiquitous Computing & Communications, Big Data & Cloud Computing, Social Computing & Networking, Sustainable Computing & Communications, ISPA/IUCC/BDCloud/SocialCom/SustainCom 2018, Melbourne, Australia, December 11-13, 2018, pages 795–800. IEEE, IEEE, 2018. doi:10.1109/BDCloud.2018.00119.
[12] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 75–84. ACM, 2007. doi:10.1145/1250790.1250803.
[13] Lichao Sun, Yingbo Zhou, Philip S. Yu, and Caiming Xiong. Differentially private deep learning with smooth sensitivity. CoRR, abs/2003.00505, 2020. doi:10.48550/arXiv.2003.00505.
[14] Salil P. Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pages 347–450. Springer International Publishing, 2017. doi:10.1007/978-3-319-57048-8_7.
[15] Yue Wang and Xintao Wu. Preserving differential privacy in degree-correlation based graph generation. Trans. Data Priv., 6(2):127–145, 2013. URL: http://www.tdp.cat/issues11/abs.a113a12.php.
[16] Bangzhou Xin, Wei Yang, Shaowei Wang, and Liusheng Huang. Differentially private greedy decision forest. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2019, Brighton, United Kingdom, May 12-17, 2019, pages 2672–2676. IEEE, IEEE, 2019. doi:10.1109/ICASSP.2019.8682219.
[17] Akito Yamamoto and Tetsuo Shibuya. Privacy-preserving publication of GWAS statistics using smooth sensitivity. In 20th Annual International Conference on Privacy, Security and Trust, PST 2023, Copenhagen, Denmark, August 21-23, 2023, pages 1–12. IEEE, IEEE, 2023. doi:10.1109/PST58708.2023.10320160.

Appendix A Deferred Proofs

We start by proving the calculus facts from Section 2.2.

Proof of Fact 4.

The statement follows from the chain rule. Its special case states that for $f:\mathbb{R}^{2}\to\mathbb{R}$ and differentiable $g:\mathbb{R}\to\mathbb{R}$ and $h:\mathbb{R}\to\mathbb{R}$ , and all $x\in\mathbb{R}$ such that $y=g(x)$ , $z=h(x)$ and $f$ is differentiable at $(y,z)$ , it holds

	$\displaystyle\frac{d\,f(y,z)}{dx}$	$\displaystyle=\frac{d\,f(y,z)}{dy}\cdot\frac{dy}{dx}+\frac{d\,f(y,z)}{dz}\cdot% \frac{dz}{dx}$
		$\displaystyle=\left[\frac{d\,f(y+\lambda,z)}{d\lambda}\cdot\frac{dy}{dx}+\frac% {d\,f(y,z+\lambda)}{d\lambda}\cdot\frac{dz}{dx}\right]_{\lambda=0},$

where the notation on right-hand side is an equivalent way of writing partial derivatives. In our case, $g=h=\text{id}$ , $x=y=z$ and $\frac{dy}{dx}=\frac{dz}{dx}=1$ , and substituting these facts in the equation above concludes the proof. $\hfill\blacktriangleleft$

Proof of Fact 5.

The statement follows from the chain rule. Its special case states that if $h(x)=f(g(x))$ , $g$ is differentiable everywhere and $f$ is differentiable at $g(x)$ , then $h^{\prime}(x)=f^{\prime}(g(x))\cdot g^{\prime}(x)$ . If we apply the chain rule on $g(x)=cx$ , then $h(x)=f(cx)$ and we get that $\frac{d}{dx}f(cx)=h^{\prime}(x)=f^{\prime}(g(x))\cdot g^{\prime}(x)=f^{\prime}% (cx)\cdot c$ . Evaluated at $x=0$ , this becomes $c\cdot f^{\prime}(0)$ , as needed. $\hfill\blacktriangleleft$

Next, we prove Lemma 7, which states that the $\operatorname{PolyPlace}$ distribution is correctly defined.

Proof of Lemma 7..

By scaling, we may assume without loss of generality that $s=1$ . By symmetry, it then suffices to integrate $f_{1,\alpha}$ from $0$ to $+\infty$ and verify that it integrates to $1/2$ . The first branch in the definition of $f_{1,\alpha}$ integrates to⁵⁵5We do not show the detailed steps of how to compute the antiderivative. However, it should be noted that it is easy to check correctness by differentiating and checking that this results in the respective expressions we were integrating.

I_{1}(\alpha,x)=-\frac{(\alpha-1)(1-x)^{\alpha}}{2\left(2\left(\frac{\alpha-1}% {\alpha}\right)^{\alpha}+\alpha-1\right)},

and the second integrates to

I_{2}(\alpha,x)=-\frac{\left(1-\frac{1}{\alpha^{2}}\right)^{\alpha}(\alpha+1)(% x+1)^{-\alpha}}{2\left(2\left(\frac{\alpha-1}{\alpha}\right)^{\alpha}+\alpha-1% \right)}.

We now write the integral as

\int_{0}^{\infty}f_{1,\alpha}(x)\,dx=I_{1}(\alpha,1/\alpha)-I_{1}(\alpha,0)+% \lim_{x\rightarrow+\infty}I_{2}(\alpha,x)-I_{2}(\alpha,1/\alpha)=1/2,

where in the last step we skipped some elementary manipulations. $\hfill\blacktriangleleft$

Next, we prove Lemma 10, which provides a formula for the derivatives of $h(s,x)=\log f_{s,\alpha}(x)$ .

Proof of Lemma 10.

Define

g(s,x,m)=N_{s,\alpha}(\alpha-m)\left(1-\frac{mx}{s}\right)^{m\alpha-1}.

Then one can verify that

h(s,x)=\begin{cases}\log g(s,|x|,+1)&\text{if }\frac{|x|}{s}<\alpha^{-1},\\ \log g(s,|x|,-1)+\alpha\log\left(1-\frac{1}{\alpha^{2}}\right)&\text{otherwise% },\end{cases}

When taking derivatives, we can ignore the additive $\alpha\log\left(1-\frac{1}{\alpha^{2}}\right)$ in the second branch as $\alpha$ is constant.

We start with analyzing the derivatives of $g$ with respect to $x$ . For $m=\pm 1,x\neq 0$ :

	$\displaystyle\left[\frac{d}{d\lambda}\log(g(s,\|x+\lambda\|,m))\right]_{\lambda=0}$
	$\displaystyle\qquad=\left[\underbrace{\frac{d}{d\lambda}\log\left(N_{s,\alpha}% \cdot(\alpha-m)\right)}_{0}+\frac{d}{d\lambda}(m\alpha-1)\log\left(1-\frac{m\|x% +\lambda\|}{s}\right)\right]_{\lambda=0}$
	$\displaystyle\qquad=\left[(m\alpha-1)\frac{\operatorname{sgn}(x+\lambda)m}{m\|% x+\lambda\|-s}\right]_{\lambda=0}=\operatorname{sgn}(x)\cdot\begin{dcases}% \frac{\alpha-1}{\|x\|-s}&\text{if }m=1,\\ \frac{-\alpha-1}{\|x\|+s}&\text{otherwise}.\end{dcases}$

Now, for $x\neq 0$ , $|x|/s\neq\alpha^{-1}$ , it holds:

\displaystyle\left[\frac{d}{d\lambda}h(s,x+\lambda)\right]_{\lambda=0}

\displaystyle=\operatorname*{sgn}(x)\cdot\begin{dcases}\frac{\alpha-1}{|x|-s}&% \text{if }\frac{|x|}{s}<\alpha^{-1},\\ \frac{-\alpha-1}{|x|+s}&\text{otherwise}.\end{dcases}

(10)

Finally, for $|x|/s=\alpha^{-1}$ , each branch gives us a one-sided derivative at $x=\pm s/\alpha$ , and one can verify that both derivatives are equal and therefore Equation 10 holds for all $x\neq 0$ .

Similarly, for $m=\pm 1,x\neq 0$ :

	$\displaystyle\left[\frac{d}{d\lambda}\log(g(e^{\lambda/s}s,\|x\|,m))\right]_{% \lambda=0}$
	$\displaystyle\qquad=\bigg{[}\frac{d}{d\lambda}\log N_{e^{\lambda/s}s,\alpha}+% \underbrace{\frac{d}{d\lambda}\log(\alpha-m)}_{0}+\frac{d}{d\lambda}(m\alpha-1% )\log\left(1-\frac{m\|x\|}{e^{\lambda/s}s}\right)\bigg{]}_{\lambda=0}$
	$\displaystyle\qquad=\left[\frac{d}{d\lambda}\log e^{-\lambda/s}+\frac{d}{d% \lambda}(m\alpha-1)\log\left(1-\frac{m\|x\|}{e^{\lambda/s}s}\right)\right]_{% \lambda=0}$
	$\displaystyle\qquad=\left[-\frac{1}{s}+\frac{(m\alpha-1)\cdot m\|x\|}{s\left(e^{% \lambda/s}s-m\|x\|\right)}\right]_{\lambda=0}=\begin{dcases}-\frac{1}{s}+\frac{(% \alpha-1)\|x\|}{s(s-\|x\|)}&\text{if }m=1,\\ -\frac{1}{s}+\frac{(\alpha+1)\|x\|}{s(s+\|x\|)}&\text{otherwise}.\end{dcases}$

Thus, for $x\neq 0,|x|/s\neq\alpha^{-1}$ :

\displaystyle\left[\frac{d}{d\lambda}h(e^{\lambda/s}s,x)\right]_{\lambda=0}=% \begin{dcases}-\frac{1}{s}+\frac{(\alpha-1)|x|}{s(s-|x|)}&\text{if }\frac{|x|}% {s}<\alpha^{-1},\\ -\frac{1}{s}+\frac{(\alpha+1)|x|}{s(s+|x|)}&\text{otherwise}.\end{dcases}

(11)

Again, the two branches are equal for $|x|/s=\alpha^{-1}$ and Equation 11 hence holds for all $x\neq 0$ . $\hfill\blacktriangleleft$

Proof of Lemma 12.

In this whole proof, fix $s>0,\alpha>1$ . We will carry through the proof with $s$ and $\alpha$ , and in the very end substitute $s=1/\gamma$ and $\alpha=\varepsilon/\gamma$ .

Per Lemma 10, it holds:

\displaystyle\Bigg{[}\left|\frac{d}{d\lambda}\log(f_{s,\alpha}(x+\lambda))% \right|\Bigg{]}_{\lambda=0}

\displaystyle=\begin{dcases}\left|\frac{\alpha-1}{|x|-s}\right|=\frac{\alpha-1% }{s-|x|}&\text{if }\frac{|x|}{s}<\alpha^{-1},\\ \left|\frac{-\alpha-1}{|x|+s}\right|=\frac{\alpha+1}{s+|x|}&\text{otherwise}.% \end{dcases}

(12)

To justify the removal of the absolute value on the right-hand side, note that $\alpha>1$ and thus $\alpha-1>0$ and $-\alpha-1<0$ . Then consider two cases: if $|x|/s<\alpha^{-1}<1$ , then $|x|-s<0$ and thus $(\alpha-1)/(|x|-s)<0$ , and if $|x|/s\geq\alpha^{-1}>0$ , then $|x|+s>0$ and thus $(-\alpha-1)/(|x|+s)<0$ .

Similarly,

\displaystyle\Bigg{[}\left|\frac{d}{d\lambda}\log(f_{e^{\lambda/s}s,\alpha}(x)% )\right|\Bigg{]}_{\lambda=0}

\displaystyle=\begin{dcases}\left|-\frac{1}{s}+\frac{(\alpha-1)|x|}{s(s-|x|)}% \right|=\frac{1}{s}-\frac{(\alpha-1)|x|}{s(s-|x|)}&\text{if }\frac{|x|}{s}<% \alpha^{-1},\\ \left|-\frac{1}{s}+\frac{(\alpha+1)|x|}{s(s+|x|)}\right|=-\frac{1}{s}+\frac{(% \alpha+1)|x|}{s(s+|x|)}&\text{otherwise}.\end{dcases}

To again justify the removal of absolute values, we distinguish two cases. If $|x|/s<\alpha^{-1}$ , then

	$\displaystyle\frac{s}{\|x\|}>\alpha$	$\displaystyle\implies\frac{s-\|x\|}{\|x\|}>\alpha-1\implies\frac{s-\|x\|}{(\alpha-1)% \|x\|}>1$
		$\displaystyle\implies\frac{(\alpha-1)\|x\|}{s-\|x\|}<1\implies\frac{(\alpha-1)\|x\|}% {s(s-\|x\|)}<\frac{1}{s},$

and thus, $\frac{1}{s}-\frac{(\alpha-1)|x|}{s(s-|x|)}>0$ . If $|x|/s\geq\alpha^{-1}$ , then, similarly,

	$\displaystyle\frac{s}{\|x\|}\leq\alpha$	$\displaystyle\implies\frac{s+\|x\|}{\|x\|}\leq\alpha+1\implies\frac{s+\|x\|}{(\alpha% +1)\|x\|}\leq 1$
		$\displaystyle\implies\frac{(\alpha+1)\|x\|}{s+\|x\|}\geq 1\implies\frac{(\alpha+1)% \|x\|}{s(s+\|x\|)}\geq\frac{1}{s},$

and thus, $\frac{1}{s}-\frac{(\alpha+1)|x|}{s(s+|x|)}\leq 0$ .

Now we can combine both results to conclude that

	$\displaystyle\Bigg{[}\left\|\frac{d}{d\lambda}\log(f_{s,\alpha}(x+\lambda))% \right\|+\left\|\frac{d}{d\lambda}\log(f_{e^{\lambda/s}s,\alpha}(x))\right\|\Bigg% {]}_{\lambda=0}$
	$\displaystyle=\left.\begin{dcases}\frac{\alpha-1}{s-\|x\|}+\frac{1}{s}-\frac{(% \alpha-1)\|x\|}{s(s-\|x\|)}=\frac{(s-\|x\|)(1+\alpha-1)}{s(s-\|x\|)}&\text{if }\frac{\|% x\|}{s}<\alpha^{-1},\\ \frac{\alpha+1}{s+\|x\|}-\frac{1}{s}+\frac{(\alpha+1)\|x\|}{s(s+\|x\|)}=\frac{(s+\|x\|% )(\alpha+1-1)}{s(s+\|x\|)}&\text{otherwise};\end{dcases}\right\}=\frac{\alpha}{s}.$

To conclude the proof, set $s=1/\gamma$ , $\alpha=\varepsilon/\gamma$ and observe that $s>0$ and $\alpha>1$ as needed. Thus, all previous claims hold, and we have

\Bigg{[}\left|\frac{d}{d\lambda}\log(f_{1/\gamma,\varepsilon/\gamma}(x+\lambda% ))\right|+\left|\frac{d}{d\lambda}\log(f_{e^{\lambda\gamma}/\gamma,\varepsilon% /\gamma}(x))\right|\Bigg{]}_{\lambda=0}=\frac{\varepsilon/\gamma}{1/\gamma}=% \varepsilon.\

$\hfill\blacktriangleleft$

Now we prove Lemma 13, which states that the $\operatorname{PolyPlace}$ distribution has mean 0 and calculates its variance.

Proof of Lemma 13..

Assuming the expectation is defined, it has to be $0$ as the distribution is symmetric around this point. We now focus on the variance; by proving that the variance is finite, we also get that the expectation is defined and therefore $0$ . Similarly to proof of Lemma 7, we first separately give the indefinite integrals of the two branches, this time of $x^{2}f_{1,\alpha}(x)$ :

I_{1}^{\sigma^{2}}=-\frac{(\alpha-1)(1-x)^{\alpha}\left(\alpha(\alpha+1)x^{2}+% 2\alpha x+2\right)}{2(\alpha+1)(\alpha+2)\left(2\left(\frac{\alpha-1}{\alpha}% \right)^{\alpha}+\alpha-1\right)}

I_{2}^{\sigma^{2}}=\frac{\left(1-\frac{1}{\alpha^{2}}\right)^{\alpha}(\alpha+1% )(x+1)^{-\alpha}\left(-\left((\alpha-1)\alpha x^{2}\right)-2\alpha x-2\right)}% {2(\alpha-2)(\alpha-1)\left(2\left(\frac{\alpha-1}{\alpha}\right)^{\alpha}+% \alpha-1\right)}.

We may now use this to write the integral as

	$\displaystyle\sigma_{1,\alpha}^{2}$	$\displaystyle=2\int_{0}^{+\infty}x^{2}f_{1,\alpha}(x)\,dx=I_{1}^{\sigma^{2}}% \Big{(}\alpha,\frac{1}{\alpha}\Big{)}-I_{1}^{\sigma^{2}}(\alpha,0)+\lim_{{x\to% +\infty}}I_{2}^{\sigma^{2}}(\alpha,x)-I_{2}^{\sigma^{2}}\Big{(}\alpha,\frac{1}% {\alpha}\Big{)}$
		$\displaystyle=\frac{\left(\frac{1}{\alpha}+1\right)^{-\alpha}\left(\left(19% \alpha^{2}+5\right)\left(1-\frac{1}{\alpha^{2}}\right)^{\alpha}+(\alpha-2)(% \alpha-1)^{2}\left(\frac{1}{\alpha}+1\right)^{\alpha}\right)}{\left(2\left(% \frac{\alpha-1}{\alpha}\right)^{\alpha}+\alpha-1\right)\left(\alpha^{4}-5% \alpha^{2}+4\right)}\,.\$

$\hfill\blacktriangleleft$

Appendix B Other Mechanisms for Smooth Sensitivity

In this section, we calculate the variances of the generalized Cauchy distribution of [12], the Student’s T distribution [3], and the Laplace distribution, when used with the smooth sensitivity framework. We use these variances in Figure 1 in order to compare our distribution with these two distributions.

Claim 16.

When scaled according to Nissim, Raskhodnikova, and Smith [12], the generalized Cauchy distribution has, for $c>3$ and $0<\gamma<\varepsilon/(c+1)$ , a standard deviation

\frac{c+1}{(\varepsilon-\gamma(c+1))\sqrt{2\cos\left(\frac{2\pi}{c}\right)+1}}\,.

For other values of $c>0,\gamma>0$ , the standard deviation is infinite.

Proof.

The generalized Cauchy distribution is defined in Nissim, Raskhodnikova, and Smith [12] as having density $\propto\frac{1}{1+|y|^{\alpha}}$ . Using a Computer Algebra System (such as Mathematica), it is easy to verify that the density is in fact equal to

\frac{c}{2\pi\csc\left(\frac{\pi}{c}\right)\left(|y|^{c}+1\right)}.

Writing the variance as an integral and again using a CAS to evaluate it, one gets that the variance is

\frac{1}{2\cos\left(\frac{2\pi}{c}\right)+1}

for $c>3$ and infinite otherwise. For two neighboring datasets $D\sim D^{\prime}$ , let us have $\lambda_{r}$ such that $SS_{q}^{\gamma}(D)=e^{\lambda_{r}}SS_{q}^{\gamma}(D^{\prime})$ and let $\lambda_{s}=\frac{q(D^{\prime})-q(D)}{SS_{q}^{\gamma}(D)}$ . It is shown in Nissim, Raskhodnikova, and Smith [12] that the privacy loss is at most $(|\lambda_{r}|+|\lambda_{s}|)(c+1)$ . If we substitute the bound $|\lambda_{r}|\leq\gamma$ , the remaining privacy budget is $\varepsilon-\gamma(c+1)$ , meaning that we need to scale the distribution with $\frac{c+1}{\varepsilon-\gamma(c+1)}$ in order to ensure the bound on privacy loss is at most $\varepsilon$ , assuming $\gamma<\varepsilon/(c+1)$ . This results in a standard deviation of

\frac{c+1}{(\varepsilon-\gamma(c+1))\sqrt{2\cos\left(\frac{2\pi}{c}\right)+1}}.\

$\hfill\vartriangleleft$

Claim 17.

When scaled according to Bun and Steinke [3], the Student’s T distribution has, for $d>2$ and $0<\gamma<\varepsilon/(d+1)$ , a standard deviation

\sqrt{\frac{d}{d-2}}\cdot\frac{d+1}{2\sqrt{d}(\varepsilon-\gamma(d+1))}

For other values of $d>0,\gamma>0$ , the standard deviation is infinite.

Proof.

The variance of the T distribution with $d$ degrees of freedom is $\frac{d}{d-2}$ . At the same time, for $\lambda_{r}$ , $\lambda_{s}$ defined as in the proof above, the privacy loss is at most

|\lambda_{r}|\cdot(d+1)+|\lambda_{s}|\cdot\frac{d+1}{2\sqrt{d}}.

We have $|\lambda_{r}|\leq\gamma$ . The remaining budget for privacy loss caused by the distribution shift is $\varepsilon-\gamma\,(d+1)$ , meaning that we need

|\lambda_{s}|\leq\nu=\frac{2\sqrt{d}(\varepsilon-\gamma(d+1))}{d+1}

assuming $\gamma<\varepsilon/(d+1)$ . To achieve $\varepsilon$ -differential privacy, for a fixed value of $\gamma$ , we have to scale the distribution with $\nu^{-1}$ . This results in a standard deviation of

\sqrt{\frac{d}{d-2}}\cdot\frac{d+1}{2\sqrt{d}(\varepsilon-\gamma(d+1))}.

$\hfill\vartriangleleft$

Claim 18.

When scaled according to Nissim, Raskhodnikova, and Smith [12], the Laplace distribution has, for $0<\gamma<\varepsilon/\log\delta^{-1}$ , a standard deviation

\frac{\sqrt{2}}{\varepsilon-\gamma\log 2\delta^{-1}}.

Proof.

The proof is essentially the same as the proofs above. It is shown by [12] that the privacy loss is at most $|\lambda_{r}|\log 2\delta^{-1}+|\lambda_{s}|$ . This means we have to scale the noise to be inversely proportional to $\varepsilon-\gamma\log 2\delta^{-1}$ . This leads to the claimed standard deviation. $\hfill\vartriangleleft$

[bib.bib1] [1] Hilal Asi and John C. Duchi. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, volume 33, pages 14106–14117, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/a267f936e54d7c10a2bb70dbe6ad7a89-Abstract.html.

[bib.bib2] [2] Hilal Asi and John C. Duchi. Near instance-optimality in differential privacy. CoRR, abs/2005.10630, 2020. doi:10.48550/arXiv.2005.10630.

[bib.bib3] [3] Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, volume 32, pages 181–191, 2019. URL: https://proceedings.neurips.cc/paper/2019/hash/3ef815416f775098fe977004015c6193-Abstract.html.

[bib.bib4] [4] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 – June 2, 2009, pages 371–380. ACM, 2009. doi:10.1145/1536414.1536466.

[bib.bib5] [5] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3-4):211–407, 2014. doi:10.1561/0400000042.

[bib.bib6] [6] Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CoRR, abs/1603.01887, 2016. doi:10.48550/arXiv.1603.01887.

[bib.bib7] [7] Juanru Fang, Wei Dong, and Ke Yi. Shifted inverse: A general mechanism for monotonic functions under user differential privacy. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pages 1009–1022. ACM, 2022. doi:10.1145/3548606.3560567.

[bib.bib8] [8] Natasha Fernandes, Annabelle McIver, and Carroll Morgan. The Laplace mechanism has optimal utility for differential privacy over continuous queries. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 – July 2, 2021, pages 1–12. IEEE, IEEE, 2021. doi:10.1109/LICS52264.2021.9470718.

[bib.bib9] [9] Alon Gonem and Ran Gilad-Bachrach. Smooth sensitivity based approach for differentially private PCA. In Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain, volume 83 of Proceedings of Machine Learning Research, pages 438–450. PMLR, PMLR, 2018. URL: http://proceedings.mlr.press/v83/gonem18a.html.

[bib.bib10] [10] Jesse Laeuchli, Yunior Ramírez-Cruz, and Rolando Trujillo-Rasua. Analysis of centrality measures under differential privacy models. Applied Mathematics and Computation, 412:126546, 2022. doi:10.1016/j.amc.2021.126546.

[bib.bib11] [11] Mingzhu Li and Xuebin Ma. Bayesian networks-based data publishing method using smooth sensitivity. In IEEE International Conference on Parallel & Distributed Processing with Applications, Ubiquitous Computing & Communications, Big Data & Cloud Computing, Social Computing & Networking, Sustainable Computing & Communications, ISPA/IUCC/BDCloud/SocialCom/SustainCom 2018, Melbourne, Australia, December 11-13, 2018, pages 795–800. IEEE, IEEE, 2018. doi:10.1109/BDCloud.2018.00119.

[bib.bib12] [12] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 75–84. ACM, 2007. doi:10.1145/1250790.1250803.

[bib.bib13] [13] Lichao Sun, Yingbo Zhou, Philip S. Yu, and Caiming Xiong. Differentially private deep learning with smooth sensitivity. CoRR, abs/2003.00505, 2020. doi:10.48550/arXiv.2003.00505.

[bib.bib14] [14] Salil P. Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pages 347–450. Springer International Publishing, 2017. doi:10.1007/978-3-319-57048-8_7.

[bib.bib15] [15] Yue Wang and Xintao Wu. Preserving differential privacy in degree-correlation based graph generation. Trans. Data Priv., 6(2):127–145, 2013. URL: http://www.tdp.cat/issues11/abs.a113a12.php.

[bib.bib16] [16] Bangzhou Xin, Wei Yang, Shaowei Wang, and Liusheng Huang. Differentially private greedy decision forest. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2019, Brighton, United Kingdom, May 12-17, 2019, pages 2672–2676. IEEE, IEEE, 2019. doi:10.1109/ICASSP.2019.8682219.

[bib.bib17] [17] Akito Yamamoto and Tetsuo Shibuya. Privacy-preserving publication of GWAS statistics using smooth sensitivity. In 20th Annual International Conference on Privacy, Security and Trust, PST 2023, Copenhagen, Denmark, August 21-23, 2023, pages 1–12. IEEE, IEEE, 2023. doi:10.1109/PST58708.2023.10320160.

	$\displaystyle f_{a/\gamma,\varepsilon/\gamma}(x)$	$\displaystyle=c\,\left(\frac{\varepsilon}{\gamma}+1\right)\bigg{(}1-\frac{% \gamma^{2}}{\varepsilon^{2}}\bigg{)}^{\varepsilon/\gamma}\bar{f}_{2}$
		$\displaystyle\sim\frac{\gamma}{2a}\left(\frac{\varepsilon}{\gamma}+1\right)% \bigg{(}1-\frac{\gamma^{2}}{\varepsilon^{2}}\bigg{)}^{\varepsilon/\gamma}e^{-% \varepsilon\|x\|/a}$
		$\displaystyle\sim\frac{\gamma}{2a}\frac{\varepsilon}{\gamma}e^{-\varepsilon\|x\|% /a}$
		$\displaystyle=\frac{\varepsilon}{2a}e^{-\varepsilon\|x\|/a}=f_{\operatorname{Lap% }(a/\varepsilon)}(x),$

	$\displaystyle\left[\frac{d}{d\lambda}\log(g(e^{\lambda/s}s,\|x\|,m))\right]_{% \lambda=0}$
	$\displaystyle\qquad=\bigg{[}\frac{d}{d\lambda}\log N_{e^{\lambda/s}s,\alpha}+% \underbrace{\frac{d}{d\lambda}\log(\alpha-m)}_{0}+\frac{d}{d\lambda}(m\alpha-1% )\log\left(1-\frac{m\|x\|}{e^{\lambda/s}s}\right)\bigg{]}_{\lambda=0}$
	$\displaystyle\qquad=\left[\frac{d}{d\lambda}\log e^{-\lambda/s}+\frac{d}{d% \lambda}(m\alpha-1)\log\left(1-\frac{m\|x\|}{e^{\lambda/s}s}\right)\right]_{% \lambda=0}$
	$\displaystyle\qquad=\left[-\frac{1}{s}+\frac{(m\alpha-1)\cdot m\|x\|}{s\left(e^{% \lambda/s}s-m\|x\|\right)}\right]_{\lambda=0}=\begin{dcases}-\frac{1}{s}+\frac{(% \alpha-1)\|x\|}{s(s-\|x\|)}&\text{if }m=1,\\ -\frac{1}{s}+\frac{(\alpha+1)\|x\|}{s(s+\|x\|)}&\text{otherwise}.\end{dcases}$

Smooth Sensitivity Revisited: Towards Optimality

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1 (Informal version of Theorem 8).

Smooth Sensitivity vs. Inverse Sensitivity Mechanism

1.1 Technical Overview

1.2 Related Work

2 Preliminaries

2.1 Differential Privacy

Definition 2 (Smooth sensitivity).

2.2 Calculus

Fact 3.

Fact 4.

Fact 5.

3 Improved Smooth Sensitivity Mechanism

Definition 6.

Lemma 7.

Theorem 8.

Proof.

Proving Privacy

Lemma 9.

Proof.

Lemma 10.

Proof.

Lemma 11.

Proof.

Lemma 12.

Proof sketch.

3.1 Properties of the 𝐏𝐨𝐥𝐲𝐏𝐥𝐚𝐜𝐞⁡(𝒔,𝜶) Distribution

Lemma 13.

Corollary 14.

Proof.

Lemma 15.

Proof.

References

Appendix A Deferred Proofs

Proof of Fact 4.

Proof of Fact 5.

Proof of Lemma 7..

Proof of Lemma 10.

Proof of Lemma 12.

Proof of Lemma 13..

Appendix B Other Mechanisms for Smooth Sensitivity

Claim 16.

Proof.

Claim 17.

Proof.

Claim 18.

Proof.

3.1 Properties of the $\operatorname{PolyPlace}(s,\alpha)$ Distribution