Privacy by Postprocessing the Discrete Laplace Mechanism Quentin Hillebrand, Jacob Imola, Rasmus Pagh, Sia Sejer Abstract We show that an “old dog,” the classical discrete Laplace (aka. geometric) mechanism, can “perform new tricks”: 1. It can be post-processed to yield a simple, unbiased estimator of any subexponential function f f of the original data, giving a simple, discrete, multivariate version of the recent unbiasing result for the Laplace mechanism by Calmon et al. (FORC ’25). 2. It can be post-processed to output the same distribution as the Laplace mechanism or the Staircase mechanism with identical privacy parameters. Thus, the discrete Laplace mechanism is a versatile mechanism that should be preferred over the Laplace and Staircase mechanisms whenever the data is discrete (or can be made discrete while controlling ℓ 1 \ell_{1} -sensitivity). We show bounds on the variance of our estimator, compared to the mean square error of the biased estimator that simply evaluates the f f on the output of the mechanism. Though our unbiased estimator has exponential running time for worst-case functions, we show that it can often be computed in linear or polynomial time for some common functions exhibiting structure. We showcase the properties of our methods empirically with several use cases including profile and entropy estimation, as well as distributed/federated data analysis applications in which unbiasedness is key to accuracy. 1 Introduction Differential privacy has a powerful post-processing property: For any differentially private mechanism \mathcal{M} and any function f , we can release f(\mathcal{M}(x)) while preserving the privacy guarantees of \mathcal{M} . As a consequence, we can release all values f_{i}(\mathcal{M}(x)) for any family of functions (f_{i})_{i\in I} with no loss of privacy. In this paper, we consider additive noise mechanisms where \mathbb{E}\left[\mathcal{M}(x)\right]=x . For non-linear functions f , the expected function value \mathbb{E}\left[f(\mathcal{M}(x))\right] , assuming it exists, is in general different from f(x) . Such bias can be a problem in some applications, which led 9 and later 1 to study methods for debiasing via post-processing of the Laplace mechanism. First, 9 showed how to construct unbiased estimators for multivariate polynomials. Later, 1 gave estimators in the univariate setting for a wide class of twice differentiable functions f . Debiasing in Post-Processing. In this paper, we propose a new post-processing method for the discrete Laplace mechanism \mathcal{M}_{\text{DLap}}:\mathbb{Z}^{n}\rightarrow\mathbb{Z}^{n} , first proposed and studied by 8 . For convenience we will use the notation \tilde{x}=\mathcal{M}_{\text{DLap}}(x) , that is, \tilde{x}_{i}=x_{i}+\eta_{i} where \eta_{i} is sampled i.i.d. from the discrete Laplace distribution with parameter p=e^{-\varepsilon} . This mechanism is a canonical way of releasing histograms, and more generally integer-valued data with sensitivity 1, with an \varepsilon -differential privacy guarantee. Given \tilde{x} , our post-processing method returns an unbiased estimator of f(x) for any univariate or multivariate function f where \mathbb{E}\left[f(\tilde{x})\right] exists and is finite. A sufficient condition for this is that f is subexponential (or exponential with low enough rate). Our method thus supports a class of functions f much wider than that of 1 , 9 , both of which can only handle functions that are twice differentiable. Previously, unbiased postprocessing of the discrete Laplace distribution had only been described in the special case of univariate threshold functions, by 7 . We show that our post-processing method is unique in the sense that it is the only deterministic method that constructs unbiased estimates in the discrete setting. From this, it follows that it has the smallest variance of all unbiased estimators. Though our estimator takes exponential time to compute for worst-case functions, we show that for functions which exhibit structure (e.g. decomposable functions such as entropy and order statistics), it is often possible to design linear or polynomial time algorithms for computing the unbiased estimation. Transformations to other Additive Noise Mechanisms. We show how to post-process \tilde{x} so that the resulting distribution is identical to that of the classical (real-valued) Laplace mechanism [ 3 ] or the Staircase mechanism [ 5 , 6 ] on input x with the same privacy parameter \varepsilon . This means the Discrete Laplace Mechanism is a versatile mechanism that should be preferred over the Laplace and Staircase Mechanisms whenever the data is discrete or can be made discrete while still controlling the \ell_{1} -sensitivity. Everything that can be done with these mechanisms can also be based on the Discrete Laplace Mechanism, and the latter may lead to better utility, especially for medium to large values of \varepsilon . Applications to Federated/ Distributed Settings. Unbiased estimators are particularly useful in settings where the statistic of interest can be obtained by summing or averaging many individual contributions. For example, suppose that each of k parties (e.g. hospitals) holds a distribution given by a histogram, that each histogram has been released with the Discrete Laplace mechanism, and we wish to compute the entropy of the joint distribution over all parties. Assuming independence, the joint entropy is the sum of the entropy of each distribution, a non-linear function of the histogram. Summing an unbiased estimator for the entropy of each distribution we get an estimator for the total entropy whose error scales with O(\sqrt{k}) . In contrast, summing biased estimators will result in error proportional to k , which will be worse for sufficiently large k . As another example, suppose we wish to gather statistics across histograms, for example the minimum, maximum, mean and variance of each column in the histograms. We can avoid bias in these estimates by using our estimator on the “transposed” histograms formed by combining information on each column across histograms. 1.1 Overview of Our Contributions. In Section 2 , we first show ( Theorem 1 ) that in the univariate case ( n=1 ) a linear combination of f(\tilde{x}-1) , f(\tilde{x}) , and f(\tilde{x}+1) is an unbiased estimator of f(x) for any function f and input x where \mathbb{E}\left[f(\tilde{x})\right] exists. This estimator can be interpreted as the discrete second derivative of f evaluated in \tilde{x} , analogous to the approach by 1 for univariate functions. We then show ( Theorem 2 ) that our method extends naturally to the multivariate case x\in\mathbb{Z}^{n} where the estimator is a linear combination of the function values f(\tilde{x}+\xi) for \xi\in\{-1,0,+1\}^{n} . Section 3 investigates properties of our unbiased estimator. We first show ( Theorem 4 ) that it is unique among deterministic estimators and has minimum variance among all unbiased estimators. In particular, for a black-box function f , any deterministic estimator requires 3^{n} function evaluations. Then we consider the mean square error (MSE) and show ( Theorem 5 ) that it is at most a factor O(1+1/\varepsilon^{4})^{n} worse than the MSE of the naive estimator f(\tilde{x}) . This bound is tight: Proposition 6 shows that there are functions for which our estimator exhibits this rate of exponential variance growth, but for other functions we instead see that the unbiased estimator is exponentially better . Section 4 shows that it is possible to post-process the Discrete Laplace Mechanism to be identical to either the classical Laplace Mechanism ( Theorem 10 ) or to the Staircase mechanism ( Theorem 17 ) while preserving the same privacy level \varepsilon . The insight is that it is possible to choose random variables X_{\varepsilon} and Y_{\gamma,\varepsilon} (independently of x ), such that \tilde{x}+X_{\varepsilon} and \tilde{x}+Y_{\gamma,\varepsilon} have the same distribution as the classical Laplace mechanism and the Staircase Mechanism with privacy parameter \varepsilon , respectively. Section 5 studies functions and classes of functions for which our estimator can be computed much faster than by direct summation of its 3^{n} terms. The key idea is to group terms with the same contribution, and compute how many terms are in each group. This allows us to compute order statistics (such as the minimum, median, and maximum), inference for decision trees, as well as entropy and KL divergence in polynomial time. In Section 6 we present four case studies showcasing settings in which our estimator has an advantage over alternatives. We consider polynomials, for a use case in graph counting, for which we emphasize the advantage of the discrete Laplace mechanism over the classical Laplace mechanism for high values of \varepsilon . For empirical entropy, where we see a significantly improved mean square error for low- and medium values of \varepsilon for sparse histograms. For estimating partition functions, a setting in which the naive estimator has considerable bias, we also see improved behavior near the convergence radius. Finally, we give the first practical demonstration of profile estimation by post-processing. Societal Impact of Unbiasedness. So far, we have considered unbiasedness from the technical perspective of statistical bias. From a societal perspective, one can ask how unbiased estimation relates to algorithmic bias and fairness. There are many distinct and incompatible notions of algorithmic fairness (e.g. 11 ). A potential benefit of pointwise unbiased estimators is that they avoid directional statistical bias so that no group of points is systematically underestimated or overestimated in expectation. However, an unbiased estimator might have a high variance and over- or underestimate the function value most of the time, reducing its fairness in practice. For example, the estimator may overestimate the target value with high probability while remaining unbiased, because it occasionally produces underestimates that compensate in expectation. Another concern is that the estimator’s variance may differ substantially across groups of input points. This raises the question of whether one can design unbiased estimators with uniform or controlled variance for all points, and what trade-offs such constraints would impose. To sum up, one should be careful not to conflate unbiasedness and fairness. 1.2 Related Work Debiasing Functions of the Laplace Mechanism. 9 showed how to debias functions of the classical Laplace mechanism (an additive noise mechanism that yields privacy guarantees also for non-integer data) when f is a multivariate polynomial. 1 considered a much more general class of functions in the univariate case ( n=1 ). They showed that there is an essentially unique way of computing such unbiased estimators: for a suitable constant c_{\varepsilon} and any twice-differentiable, so-called tempered function f , the estimator \hat{f}(\mathcal{M}(x))=f(\mathcal{M}(x))-c_{\varepsilon}f^{\prime\prime}(\mathcal{M}(x)) satisfies \mathbb{E}\left[\hat{f}(\mathcal{M}(x))\right]=f(x) . The result is derived via a deconvolution perspective in the Fourier domain and yields closed-form unbiased estimators for broad classes of nonlinear functions. It is not immediately clear from their results how to extend the result to the multivariate setting. For our estimator these strong assumptions on f are not necessary, so it is applicable to a wider class of functions for which the naive estimator has a well-defined, finite expectation. Mechanisms based on Postprocessing the Discrete Laplace Mechanism. 7 considered a related distributed setting in which a cryptographic primitive, a shuffler 2 , 4 , is used to collect and noise histogram data. Similar to our results they consider Discrete Laplace noise, and in the univariate case they show how to debias a threshold indicator function applied to the output of the Discrete Laplace mechanism. This result is used as a stepping stone to estimate any symmetric function of the histogram. For comparison we provide a method that can be used without shuffling and supports a wider class of functions that are not necessarily symmetric. 17 studied profile estimation which boils down to estimating for various k a sum of indicator function values f(x) where f(x)=1 if x=k and f(x)=0 otherwise. They present a way of “inverting” the noise added by the Discrete Laplace mechanism and show that it is asymptotically near-optimal. Our estimator gives a much simpler solution to this problem. Privately Estimating Black-Box Statistics. Related to supporting privacy on a broad class of functions, 14 designed a so-called down-local algorithm for estimating a function f with exponentially many evaluations of f on noisy data. Despite the superficial similarity, their setting is rather different from ours. Their method provides accurate estimations for well-behaved (finite-domain or c -Lipschitz) functions on the dataset and its subset. For monotone functions, the bias is always downwards, and for more general functions with finite range, they provided a guaranteed interval. 16 presents a method for interpolating between computational efficiency and statistical accuracy when estimating a black box function f . Formally, they interpolate between high statistical accuracy and an exponential number of evaluations, and low statistical accuracy, where the number of evaluations depends only on the privacy parameters and the domain size. 1.3 Definitions Definition 1 (Differential Privacy (DP) [ 3 ] ) . For \varepsilon>0 an algorithm \mathcal{M} with domain \mathcal{D} and range \mathcal{S} satisfies \varepsilon -differential privacy ( \varepsilon -DP) if, for every S\subset\mathcal{S} and any D^{(1)},D^{(2)}\in\mathcal{D} that differ by only one element, we have \Pr\left[\mathcal{M}\left(D^{(1)}\right)\in S\right]\leq{e^{\varepsilon}\cdot\Pr\left[\mathcal{M}\left(D^{(2)}\right)\in S\right]}\kern 5.0pt. In this paper we consider datasets that have been transformed to integer-valued vectors in \mathbb{Z}^{n} . A canonical example of such a dataset is a histogram of counts of elements in a discrete domain of size n . We consider two datasets x,x^{\prime} to be neighboring if \|x-x^{\prime}\|_{1}\leq 1 , i.e., at most one count can be changed by 1 . For discrete-valued data, the canonical DP mechanism is based on adding noise drawn from the discrete Laplace distribution : Definition 2 (Discrete Laplace distribution) . For p\in(0,1) , \textnormal{{DLap}}(p) denotes the discrete Laplace distribution whose probability mass at i\in\mathbb{Z} is \frac{1-p}{1+p}\cdot p^{|i|} . We consider the setting where x has been published as a noisy histogram \tilde{x}=x+\textnormal{{DLap}}(p)^{n} by adding independent noise drawn from \textnormal{{DLap}}(p) to each coordinate. This is an example of the Discrete Laplace Mechanism, and it is known that if p=e^{-\varepsilon} , it satisfies \varepsilon -DP [ 8 ] . We are interested in estimating a function f(x) of the sensitive dataset, where f:\mathbb{Z}^{n}\rightarrow\mathbb{R} , while only having access to \tilde{x} . To do so, we will use an estimator g(\tilde{x}) . We measure the accuracy of an estimator using the mean square error. Definition 3 (Mean Square Error) . The mean square error (MSE) of an estimator g on input x is \text{MSE}_{g}(x)=\mathbb{E}\left[(g(\tilde{x})-f(x))^{2}\right] . If the expected value does not exist the MSE is undefined . Note that this definition includes the dataset x as a parameter, rather than considering a maximum over all x . This pointwise definition will be useful when computing our error bounds later. 2 Debiasing the Discrete Laplace Mechanism We now study how to design an unbiased estimator g that, given access to the dataset x published with Discrete Laplace Noise, has expected value f(x) for a given function f . Univariate Case. We first consider a single dimension n=1 . The basic idea is to “invert” the equation \mathbb{E}\left[g(\tilde{x})\right]=f(x) , which is generally possible because, when expanded out, expectation is a linear operator. In general, such an estimator would not have a closed form, but the Discrete Laplace Distribution has tails with a simple exponential shape, which enables cancellation. This makes it possible to debias f(\tilde{x}) by considering only f(\tilde{x}+1) , f(\tilde{x}) , and f(\tilde{x}-1) . We show: Theorem 1 . For f:\mathbb{Z}\to\mathbb{R} , p\in(0,1) , x\in\mathbb{Z} , and y\in\mathbb{Z} define: g(y)=f(y)-\tfrac{p}{(1-p)^{2}}\left(f(y+1)-2f(y)+f(y-1)\right). (1) Given \tilde{x}=x+\textnormal{{DLap}}(p) if \mathbb{E}\left[|f(\tilde{x})|\right] exists and is finite then g(\tilde{x}) is an unbiased estimator of f(x) , i.e., \mathbb{E}\left[g(\tilde{x})\right]=f(x) . The proof of Theorem 1 is a straightforward computation of the expected value of g(\tilde{x}) and is omitted to Appendix A . The condition that \mathbb{E}\left[f(\tilde{x})\right] exists and is finite is satisfied for every function whose growth rate is subexponential or, more generally, dominated by a certain exponential function depending on p , see Lemma 18 for details. Comment. The value f(y+1)-2f(y)+f(y-1) is equal to (f(y+1)-f(y))-(f(y)-f(y-1)) and can be interpreted as a discrete second derivative. This makes our estimator analogous to the unbiased estimator for real-valued functions f(\tilde{x})-c_{\varepsilon}f^{\prime\prime}(\tilde{x}) derived in 1 . The special case where f is a threshold function, i.e., where for some value k , f(x)=1 if x\geq k and f(x)=0 for x1 , and for \gamma>0 we have 00\} . Let g be from Theorem 2 . If p=e^{-\varepsilon} with \varepsilon\leq 1 , then for every x with \sum_{i}x_{i}=0 , \operatorname{Var}\left(g(\tilde{x})\right)=\exp(\Omega(n)) . The proof of Proposition 8 can be found in Appendix B.4 . The idea is to show that for an all-zeros input the variance is lower bounded by the event that zero-sum noise is added by the Discrete Laplace mechanism, which happens with probability \Omega(1/\sqrt{n}) , in which case the estimator has value \exp(\Omega(n)) . 4 Postprocessing Discrete Laplace Noise into Laplace or Staircase Noise We show that discrete Laplace noise can be converted, by input-independent postprocessing, into either continuous Laplace noise or staircase noise at the same privacy level. The constructions are local to each unit interval and work by adding an independent random variable supported on [-1,1] . It suffices to consider the univariate setting, since the multivariate setting just repeats the same method to each coordinate. Fix \varepsilon>0 and write p=e^{-\varepsilon} . Let \eta\sim\textnormal{{DLap}}(p) , so that \tilde{x}=x+\eta is the discrete Laplace mechanism at privacy level \varepsilon for unit sensitivity. Since all transformations below are postprocessings of \eta , they preserve \varepsilon -DP automatically. Both our results use the following lemma. Lemma 9 . Let q be a probability distribution with support contained in [-1,1] , symmetric around zero, and let Y\sim q be independent of \eta . For z\in\mathbb{R} , write |z|=n+u with n\in\mathbb{Z}_{\geq 0} and u\in[0,1) . Then \eta+Y has density function f_{\eta+Y}(z)=\tfrac{1-p}{1+p}\,p^{n}\bigl(q(u)+p\,q(u-1)\bigr)\kern 5.0pt. Proof. First suppose z\geq 0 . Since q is supported on [-1,1] , only the atoms n and n+1 can contribute to z=n+u . Thus f_{\eta+Y}(n+u)=\Pr[\eta=n]\,q(u)+\Pr[\eta=n+1]\,q(u-1)=\tfrac{1-p}{1+p}\,p^{n}\bigl(q(u)+p\,q(u-1)\bigr)\kern 5.0pt. Here we use that q(u-1)=q(1-u) since q is symmetric around zero. For z<0 , by symmetry the same formula with -z=n+u determines the density. ∎ Now we show a method for post-processing from the discrete Laplace mechanism to the continuous Laplace mechanism while preserving the same privacy level \varepsilon=\ln(1/p) . Theorem 10 . Let Y be independent of \eta with density q_{\mathrm{Lap}}(y)=\begin{cases}\tfrac{\ln(1/p)}{2(1-p)^{2}}\Bigl(p^{|y|}-p^{2-|y|}\Bigr)&\text{for }|y|\leq 1\\ 0&\text{otherwise}\end{cases}\kern 5.0pt. Then \eta+Y has the Laplace density f(z)=\frac{\ln(1/p)}{2}p^{|z|}. Proof. It is easy to verify that q_{\mathrm{Lap}} is a density function, is symmetric around zero, and has support [-1,1] . Fix z and write |z|=n+u with n\geq 0 and u\in[0,1) . We have q_{\mathrm{Lap}}(u)+p\,q_{\mathrm{Lap}}(1-u)=\tfrac{\ln(1/p)}{2(1-p)^{2}}\Bigl((p^{u}-p^{2-u})+p(p^{1-u}-p^{1+u})\Bigr)=\tfrac{(1+p)\ln(1/p)}{2(1-p)}\,p^{u}\kern 5.0pt. By Lemma 9 and using q_{\mathrm{Lap}}(u-1)=q_{\mathrm{Lap}}(1-u) : f_{\eta+Y}(z)=\tfrac{1-p}{1+p}p^{n}\bigl(q_{\mathrm{Lap}}(u)+p\,q_{\mathrm{Lap}}(u-1)\bigr)=\tfrac{1-p}{1+p}p^{n}\cdot\tfrac{(1+p)\ln(1/p)}{2(1-p)}\,p^{u}=\tfrac{\ln(1/p)}{2}p^{|z|}\kern 5.0pt.\qed Figure 2 illustrates the transformation. We defer the method and the accompanying proofs for post-processing to the Staircase mechanism to Appendix C.2 . Discussion. We have shown in this section that both the continuous Laplace mechanism and the Staircase mechanism can be simulated by post-processing a draw from the discrete Laplace mechanism. Consequently, any unbiased estimator for either of these mechanisms induces an unbiased estimator based on discrete Laplace output. For example, if g is an unbiased estimator for the continuous Laplace mechanism and Y is independent post-processing noise from Theorem 10 , then y\mapsto g(y+Y) , evaluated on discrete Laplace output, has the same distribution as g evaluated on continuous Laplace output. The same argument applies to the Staircase mechanism. By Theorem 4 , the discrete Laplace unbiased estimator has minimum variance among all unbiased estimators, including randomized ones. Hence, no unbiased estimator based on the continuous Laplace or Staircase mechanism can have smaller variance than the corresponding unbiased estimator based directly on the discrete Laplace mechanism. This fact, along with the possibility to transform the output into a continuous Laplace or Staircase distribution if necessary, means that the discrete Laplace mechanism should be preferred over the Laplace and Staircase mechanisms whenever possible. 5 Unbiased Estimators for Specific Multivariate Functions The computational bottleneck of Theorem 2 is due to the exponential size of the set B_{y}=\{y+\xi:\xi\in\{-1,0,1\}^{n}\} on which f needs to be evaluated. Fortunately, many common functions of interest exhibit structure which makes it tractable to compute g(y) . In this section, we give polynomial time algorithms for unbiasing the min, max, general order statistics, a decision tree evaluation, the entropy function, and multivariate polynomials. These functions all satisfy the condition of Theorem 2 because they exhibit polynomial growth (formalized in Lemma 18 ). These results are unified by a general technique which can give efficient unbiased estimators for any function f that is locally decomposable as a sum of polynomially many “easy” functions on the domain B_{y} , for any y\in\mathbb{Z}^{n} . Easy functions refer to a basis class of functions where it is possible to evaluate ( 2 ) efficiently. Due to space constraints, we provide the details of this in Appendix D . Remarks on Running Time and Error. We measure running time in the real-RAM arithmetic model; specifically, we assume that the input y is given as a sequence of n integers, we can evaluate f at any point in constant time (producing a real number), and we can do real-valued arithmetic in constant time in addition to the standard operations of a Turing machine. In preliminary experiments, we observed that the unbiased estimators in this section can have high error that is possibly much higher than that of the naive estimator (consistent with the gap in Theorem 5 ). Thus, the results in this section are primarily of theoretical interest, and further work is necessary to demonstrate their practical performance. Order Statistics For an integer 1\leq i\leq n , the i th order statistic of an input x_{1},\ldots,x_{n} is the i th element in the sorted input. This encapsulates the minimum, median, and maximum. The unbiased estimators for order statistics have the following running times: Theorem 11 . (Informal statement of Theorems 20 , 21 ). The estimator ( 2 ) for min and max can be computed in O(n) time. For the i th order statistic (e.g., median) it can be computed in O(n^{2}) time. Decision Tree Evaluation A decision tree evaluation function can be described by a tree T . Each internal node of the tree is labeled with a predicate of the form x_{i}\leq c with c a real-valued constant. Internal nodes have two children corresponding to YES and NO. Finally, the leaves are labeled with real-valued constants. The function is evaluated at x_{1},\ldots,x_{n} by following the valid path from root to leaf, and then outputting the value at the leaf. We show: Theorem 12 . (Informal statement of Theorem 19 ) The unbiased estimator of a decision tree evaluation function with s internal nodes can be computed in O(ns) time. Entropy and KL Divergence If x_{1},\ldots,x_{n} is interpreted as a vector of counts over a domain of size n , then it is natural to consider the entropy of the empirical probability distribution p_{1},\ldots,p_{n} where p_{i}=\frac{x_{i}}{\sum_{j}x_{j}} . The entropy takes the form H(x_{1},\ldots,x_{n})=\sum_{i=1}^{n}h(\frac{x_{i}}{\sum_{j}x_{j}}) , where h(z)=-z\log_{2}(z) . The estimator for the entropy has the following runtime: Theorem 13 . (Informal statement of Theorem 23 ) The unbiased estimator for the entropy can be computed in O(n^{2}) time. In Section D.5 , we extend these results to KL divergence and obtain an unbiased estimator with O(n^{3}) running time. Multivariate Polynomials A multivariate monomial of the form x_{1}^{a_{1}}\ldots x_{n}^{a_{n}} does not fit easily into the local decomposition framework. Nonetheless, it is possible to compute the unbiased estimator efficiently because the variables in the monomial interact through a product, and this allows one to factor ( 2 ) directly. Specifically, products of functions can be unbiased as the product of the unbiased estimators as follows: Theorem 14 . Suppose f(y_{1},\ldots,y_{n})=f_{1}(Y_{1})f_{2}(Y_{2}) for two functions f_{1}:\mathbb{Z}^{n_{1}}\rightarrow\mathbb{R} and f_{2}:\mathbb{Z}^{n_{2}}\rightarrow\mathbb{R} , where Y_{1}\sqcup Y_{2} is a partition of the variables y_{1},\ldots,y_{n} . Let g_{1}(Y_{1}),g_{2}(Y_{2}) be the unbiased estimators given in Theorem 2 . Then the unbiased estimator g(y_{1},\ldots,y_{n}) for f is equal to g_{1}(Y_{1})g_{2}(Y_{2}) . Thus, a multivariate monomial can be unbiased by multiplying the unbiased estimators for x_{i}^{a_{i}} separately (which are given in Theorem 1 ). A general multivariate polynomial can be unbiased by adding the estimators for each monomial. 6 Empirical Results Here we briefly discuss our empirical validation 1 1 1 The code used for those experiments is available in the following repository: https://github.com/Gericko/Postprocessing-Discrete-Laplace , for which further details can be found in Appendix E . Section E.1 considers polynomials, for a use case in graph counting ( k -star counting), where we emphasize the advantage of the discrete Laplace mechanism over the classical Laplace mechanism for high values of \varepsilon . The k -stars experiments suggest that both the use of the discrete Laplace mechanism and the debiasing matter. Section E.2 concerns empirical entropy, where we see a significantly improved root mean square error for low- and medium values of \varepsilon . The entropy experiment, whose results are shown in Figure 1(a) , highlights that when the naive estimator consists of a sum of biased terms, debiasing yields a significant improvement when applied to a sparse bag-of-words dataset. Other functions, such as partition functions, also fall into the category of functions written as a sum over disjoint variables. We consider empirical results on estimating partition functions in Section E.3 , for a setting in which the naive estimator has considerable bias. Finally, Section E.4 provides the first practical demonstration of post-processing-based profile estimation. One of the results is shown in Figure 1(b) . These results show that debiasing can help prevent the smoothing effect of the noise addition. Overall, debiasing is most compelling when bias would otherwise accumulate. Our empirical results show that even in non-distributed settings, there are functions for which our unbiased estimator leads to lower error than the naive plug-in estimator. In particular, they confirm the theoretical contributions and the applicability of the proposed method. (a) Root mean square error of the entropy estimation on the bag of words of NIPS articles. Quantiles are shown over about 30,000 runs for each \varepsilon (20 repetitions over 1491 histograms). (b) Profile estimation on ExAC histogram. Quantiles are shown for \varepsilon=1 and for over 200 noise realizations for each value of k . Figure 1 : Examples where our estimator compares favorably to the naive estimator on real datasets. 7 Discussion and Limitations Our proposed method is general and imposes minimal assumptions on the properties of f . Compared with previous work, this generality allows unbiased estimators to be constructed for a much wider class of functions. One cost of this generality is computational: in general computing our estimator requires exponential time. For many natural functions we show, however, that the estimator can be computed in polynomial time. A natural open problem of characterizing the classes of functions that admit polynomial-time unbiased estimation algorithms. A second limitation of our estimator is that it sometimes has substantially higher variance than the naive estimator. This is the case for some of the functions we have studied, such as order statistics. However, as we have seen in our theoretical and empirical results there are other cases of interest where the mean square error of our estimator is small or even significantly better than that of the naive estimator. Characterizing the functions and inputs for which such an improvement occurs is another interesting avenue for future work. Finally, unbiased estimators sometimes have worse error than estimators with a small, controlled bias — it would be interesting to understand if such biased estimators can lead to better estimation of sums in distributed/federated settings. Appendix A Omitted Proofs for Section 2 A.1 Proof of Theorem 1 Proof. Let f:\mathbb{Z}\to\mathbb{R} , p\in(0,1) , x\in\mathbb{Z} , \tilde{x}=x+\textnormal{{DLap}}(p) , and g as defined in Equation 1 . \displaystyle\mathbb{E}\left[g(\tilde{x})\right]= \displaystyle\sum\limits_{i=-\infty}^{+\infty}\Pr\left[\tilde{x}-x=i\right]g(x+i) \displaystyle= \displaystyle\frac{1-p}{1+p}\sum\limits_{i=-\infty}^{+\infty}p^{|i|}g(x+i) \displaystyle= \displaystyle\frac{1-p}{1+p}\sum\limits_{i=-\infty}^{+\infty}p^{|i|}\left(f(x+i)-\frac{p}{(1-p)^{2}}(f(x+i+1)-2f(x+i)+f(x+i-1))\right) \displaystyle= \displaystyle\frac{(1-p)^{2}+2p}{(1+p)(1-p)}\sum\limits_{i=-\infty}^{+\infty}p^{|i|}f(x+i)-\frac{p}{(1+p)(1-p)}\left[\sum\limits_{i=-\infty}^{-1}p^{-i}f(x+i+1)\right. \displaystyle\left.+\sum\limits_{i=0}^{+\infty}p^{i}f(x+i+1)+\sum\limits_{i=-\infty}^{0}p^{-i}f(x+i-1)+\sum\limits_{i=1}^{+\infty}p^{i}f(x+i-1)\right] \displaystyle= \displaystyle\frac{1+p^{2}}{(1+p)(1-p)}\sum\limits_{i=-\infty}^{+\infty}p^{|i|}f(x+i)-\frac{p}{(1+p)(1-p)} \displaystyle\left[\sum\limits_{i=-\infty}^{0}p^{-i+1}f(x+i)+\sum\limits_{i=1}^{+\infty}p^{i-1}f(x+i)+\sum\limits_{i=-\infty}^{-1}p^{-i-1}f(x+i)+\sum\limits_{i=0}^{+\infty}p^{i+1}f(x+i)\right] \displaystyle= \displaystyle\frac{1+p^{2}}{(1+p)(1-p)}\sum\limits_{i=-\infty}^{+\infty}p^{|i|}f(x+i)-\frac{p}{(1+p)(1-p)} \displaystyle\left[p\sum\limits_{i=-\infty}^{+\infty}p^{|i|}f(x+i)+pf(x)+\frac{1}{p}\sum\limits_{i=-\infty}^{+\infty}p^{|i|}f(x+i)-\frac{1}{p}f(x)\right] \displaystyle= \displaystyle f(x)\qed A.2 Proof of Theorem 2 Proof. Let f:\mathbb{Z}^{n}\to\mathbb{R} , p\in(0,1) , (x_{1},\ldots,x_{n})\in\mathbb{Z}^{n} , for all i\in[n] , \tilde{x}_{i}=x_{i}+\textnormal{{DLap}}(p) , and g as defined in Equation 2 . \displaystyle\mathbb{E}_{\tilde{x}_{1},\ldots,\tilde{x}_{n}}\left[g(\tilde{x}_{1},\ldots,\tilde{x}_{n}))\right] \displaystyle=\mathbb{E}_{\tilde{x}_{1},\ldots,\tilde{x}_{n}}\left[\sum\limits_{(\xi_{1},\ldots,\xi_{n})\in\{-1,0,1\}^{n}}f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n}+\xi_{n})\prod\limits_{j=1}^{n}\alpha_{\xi_{j}}\right] \displaystyle=\mathbb{E}_{\tilde{x}_{1},\ldots,\tilde{x}_{n-1}}\left[\mathbb{E}_{\tilde{x}_{n}}\left[\sum\limits_{(\xi_{1},\ldots,\xi_{n})\in\{-1,0,1\}^{n}}f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n}+\xi_{n})\prod\limits_{j=1}^{n}\alpha_{\xi_{j}}\right]\right] \displaystyle=\mathbb{E}_{\tilde{x}_{1},\ldots,\tilde{x}_{n-1}}\left[\sum\limits_{(\xi_{1},\ldots,\xi_{n-1})\in\{-1,0,1\}^{n-1}}\prod\limits_{j=1}^{n-1}\alpha_{\xi_{j}}\cdot\mathbb{E}_{\tilde{x}_{n}}\left[-\frac{p}{(1-p)^{2}}f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n-1}+\xi_{n-1},\tilde{x}_{n}-1)\right.\right. \displaystyle\left.\left.+\left(1+\frac{2p}{(1-p)^{2}}\right)f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n-1}+\xi_{n-1},\tilde{x}_{n})-\frac{p}{(1-p)^{2}}f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n-1}+\xi_{n-1},\tilde{x}_{n}+1)\right]\right] \displaystyle=\mathbb{E}_{\tilde{x}_{1},\ldots,\tilde{x}_{n-1}}\left[\sum\limits_{(\xi_{1},\ldots,\xi_{n-1})\in\{-1,0,1\}^{n-1}}f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n-1}+\xi_{n-1},x_{n})\prod\limits_{j=1}^{n-1}\alpha_{\xi_{j}}\right] \displaystyle=f(x_{1},\ldots,x_{n}) The second equality is derived using the independence of the random variables \tilde{x}_{i} . For the fourth equality, we apply Theorem 1 to the functions g(x)=f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n-1}+\xi_{n-1},x) for each assignment of (\xi_{1},\ldots,\xi_{n-1}) . Finally the last equality is obtained by induction on n by considering this time the function g(x_{1},\ldots,x_{n-1})=f(x_{1},\ldots,x_{n-1},x_{n}) . ∎ Appendix B Omitted Proofs for Section 3 B.1 Proof of Theorem 4 For y\in\mathbb{Z}^{n} we will prove that if g is an unbiased estimator of the function y\mapsto 0 , then for all y\in\mathbb{Z}^{n},g(y)=0 . From there, we can easily prove the theorem by noticing that if g_{1} and g_{2} are unbiased estimators of the same function f , then g_{1}-g_{2} is an unbiased estimator of the constant function y\mapsto 0 . Let p\in(0,1) , x\in\mathbb{Z}^{n} , \tilde{x}=x+\textnormal{{DLap}}(p) , and h be a deterministic unbiased estimator for y\mapsto 0 . By the definition of the unbiased estimator, we have \mathbb{E}\left[h(\tilde{x})\right]=\left(\tfrac{1-p}{1+p}\right)^{n}\sum_{i\in\mathbb{Z}^{n}}p^{\|i-x\|_{1}}h(i)=0. To obtain a cancellation in the sum, we will use the following equality. p^{|z-1|}+p^{|z+1|}-\tfrac{p^{2}+1}{p}p^{|z|}=\begin{cases}p-\frac{1}{p},&z=0\\[5.16663pt] 0,&\text{otherwise}\end{cases} For any fixed x\in\mathbb{Z}^{n} , by applying the unbiased estimator to \tilde{x}-e_{1} , \tilde{x}+e_{1} , and \tilde{x} , we have that the following linear combination is also equal to 0: \displaystyle\mathbb{E}\left[h(\tilde{x}-e_{1})\right]+\mathbb{E}\left[h(\tilde{x}+e_{1})\right]-\tfrac{p^{2}+1}{p}\mathbb{E}\left[h(\tilde{x})\right] \displaystyle=\left(\tfrac{1-p}{1+p}\right)^{n}\sum_{(i_{2},\ldots,i_{n})\in\mathbb{Z}^{n-1}}p^{\sum_{j=2}^{n}|i_{j}-x_{j}|}\sum_{i_{1}=-\infty}^{+\infty}\left[p^{|i_{1}-x_{1}-1|}+p^{|i_{1}-x_{1}+1|}-\tfrac{p^{2}+1}{p}p^{|i_{1}-x_{1}|}\right]h(i) \displaystyle=\left(\tfrac{1-p}{1+p}\right)^{n}\left(p-\tfrac{1}{p}\right)\sum_{(i_{2},\ldots,i_{n})\in\mathbb{Z}^{n-1}}p^{\sum_{j=2}^{n}|i_{j}-x_{j}|}h(x_{1},i_{2},\ldots,i_{n}) \displaystyle=\tfrac{1-p}{1+p}\left(p-\tfrac{1}{p}\right)\mathbb{E}\left[h(x_{1},\tilde{x}_{2},\ldots,\tilde{x}_{n})\right] This shows that the zero expectation is preserved when replacing the random variable \tilde{x}_{1} by x_{1} . By performing the same cancellation for each coordinate j , we obtain h(x)=0 . This is true for every x\in\mathbb{Z}^{n} and concludes the proof of the uniqueness of the deterministic estimator. Concerning the optimality, let U be auxiliary randomness and \delta(\tilde{x},U) an unbiased estimator of f(x) . Using Theorem 3 , we have that \bar{\delta}(\tilde{x}) is a deterministic unbiased estimator of f(x) with smaller variance than \delta(\tilde{x},U) . However, by the uniqueness of the deterministic unbiased estimator, \bar{\delta} is g . ∎ B.2 Proof of Theorem 5 For simplicity, we first consider the n=1 case: First, we state and prove the following lemma: Lemma 15 . For f:\mathbb{Z}\to X , p\in(0,1) , x\in\mathbb{Z} , \tilde{x}=x+\textnormal{{DLap}}(p) , and \xi\in\{-1,+1\} , \mathbb{E}\left[(f(\tilde{x}+\xi)-f(x))^{2}\right]\leq\frac{1}{p}\cdot\text{MSE}_{f}(x). Proof. \displaystyle\mathbb{E}\left[(f(\tilde{x}+\xi)-f(x))^{2}\right] \displaystyle=\frac{1-p}{1+p}\sum\limits_{i=-\infty}^{+\infty}p^{|i|}(f(x+i+\xi)-f(x))^{2} \displaystyle=\frac{1-p}{1+p}\sum\limits_{j=-\infty}^{+\infty}p^{|j-\xi|}(f(x+j)-f(x))^{2} \displaystyle\leq\frac{1-p}{1+p}\sum\limits_{j=-\infty}^{+\infty}\frac{p^{|j|}}{p}(f(x+j)-f(x))^{2} \displaystyle=\frac{1}{p}\cdot\text{MSE}_{f}(x)\qed Then, we prove the theorem for n=1 by applying the lemma above: Proof. \displaystyle\text{MSE}_{g}(x) \displaystyle=\mathbb{E}\left[\left(f(\tilde{x})-\frac{p}{(1-p)^{2}}(f(\tilde{x}+1)-2f(\tilde{x})+f(\tilde{x}-1))-f(x)\right)^{2}\right] \displaystyle=\frac{1}{(1-p)^{4}}\mathbb{E}\left[\left(\left(1+p^{2}\right)\left(f(\tilde{x})-f(x)\right)-p\left(f(\tilde{x}+1)-f(x)\right)-p\left(f(\tilde{x}-1)-f(x)\right)\right)^{2}\right] \displaystyle\leq\frac{3}{(1-p)^{4}}\mathbb{E}\left[\left(1+p^{2}\right)^{2}\left(f(\tilde{x})-f(x)\right)^{2}+p^{2}\left(f(\tilde{x}+1)-f(x)\right)^{2}+p^{2}\left(f(\tilde{x}-1)-f(x)\right)^{2}\right] \displaystyle\leq\frac{3}{(1-p)^{4}}\left(\left(1+p^{2}\right)^{2}\text{MSE}_{f}(x)+p\cdot\text{MSE}_{f}(x)+p\cdot\text{MSE}_{f}(x)\right) \displaystyle=3\frac{\left(1+p^{2}\right)^{2}+2p}{(1-p)^{4}}\cdot\text{MSE}_{f}(x).\qed Now we consider the general case. Before proving the main theorem, we state and prove the following lemma (similar to the n=1 case): Lemma 16 . For f:\mathbb{Z}^{n}\to X , p\in(0,1) , (x_{1},\ldots,x_{n})\in\mathbb{Z}^{n} , and for all i\in[n] , \tilde{x}_{i}=x_{i}+\textnormal{{DLap}}(p) , and (\xi_{1},\ldots,\xi_{n})\in\{-1,0,1\}^{n} , \mathbb{E}\left[(f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n}+\xi_{n})-f(x_{1},\ldots,x_{n}))^{2}\right]\leq\frac{1}{p^{\sum_{j=1}^{n}|\xi_{j}|}}\cdot\text{MSE}_{f}(x_{1},\ldots,x_{n}). Proof. \displaystyle\mathbb{E}\left[(f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n}+\xi_{n})-f(x_{1},\ldots,x_{n}))^{2}\right] \displaystyle=\left(\frac{1-p}{1+p}\right)^{n}\sum\limits_{(i_{1},\ldots,i_{n})\in\mathbb{Z}^{n}}p^{\sum_{j=1}^{n}|i_{j}|}(f(x_{1}+\xi_{1}+i_{1},\ldots,x_{n}+\xi_{n}+i_{n})-f(x_{1},\ldots,x_{n}))^{2} \displaystyle=\left(\frac{1-p}{1+p}\right)^{n}\sum\limits_{(i_{1},\ldots,i_{n})\in\mathbb{Z}^{n}}p^{\sum_{j=1}^{n}|i_{j}-\xi_{j}|}(f(x_{1}+i_{1},\ldots,x_{n}+i_{n})-f(x_{1},\ldots,x_{n}))^{2} \displaystyle\leq\left(\frac{1-p}{1+p}\right)^{n}\sum\limits_{(i_{1},\ldots,i_{n})\in\mathbb{Z}^{n}}p^{\sum_{j=1}^{n}|i_{j}|-|\xi_{j}|}(f(x_{1}+i_{1},\ldots,x_{n}+i_{n})-f(x_{1},\ldots,x_{n}))^{2} \displaystyle=\frac{1}{p^{\sum_{j=1}^{n}|\xi_{j}|}}\cdot\mathbb{E}\left[(f(\tilde{x}_{1},\ldots,\tilde{x}_{n})-f(x_{1},\ldots,x_{n}))^{2}\right].\qed Then, we prove Theorem 5 by applying the lemma above: Proof. \displaystyle\text{MSE}_{g}(x_{1},\ldots,x_{n}) \displaystyle=\ \displaystyle\mathbb{E}\left[\left(\sum\limits_{(\xi_{1},\ldots,\xi_{n})\in\{-1,0,1\}^{n}}f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n}+\xi_{n})\prod\limits_{j=1}^{n}\alpha_{\xi_{j}}-f(x_{1},\ldots,x_{n})\right)^{2}\right] \displaystyle\leq\ \displaystyle 3^{n}\sum\limits_{(\xi_{1},\ldots,\xi_{n})\in\{-1,0,1\}^{n}}\mathbb{E}\left[(f(\tilde{x}_{1}+\xi_{1},\ldots,\tilde{x}_{n}+\xi_{n})-f(x_{1},\ldots,x_{n}))^{2}\right]\prod\limits_{j=1}^{n}\alpha_{\xi_{j}}^{2} \displaystyle\leq\ \displaystyle 3^{n}\sum\limits_{(\xi_{1},\ldots,\xi_{n})\in\{-1,0,1\}^{n}}\text{MSE}_{f}(x_{1},\ldots,x_{n})\prod\limits_{j=1}^{n}\frac{\alpha_{\xi_{j}}^{2}}{p^{|\xi_{j}|}} \displaystyle=\ \displaystyle\left(3\frac{\left(1+p^{2}\right)^{2}+2p}{(1-p)^{4}}\right)^{n}\text{MSE}_{f}(x_{1},\ldots,x_{n}).\qed B.3 Proof of Proposition 6 Proof. Let p\in(0,1) , \gamma\in(-1/p,-p)\cup(p,1/p) , x\in\mathbb{Z}^{n} , and \tilde{x}=x+\textnormal{{DLap}}(p) . In one dimension, \displaystyle\mathbb{E}\left[|\gamma^{\tilde{x}}|\right] \displaystyle=\tfrac{1-p}{1+p}\sum_{i=-\infty}^{+\infty}p^{|i|}|\gamma|^{x+i}=\tfrac{1-p}{1+p}|\gamma|^{x}\left(\sum_{i=1}^{+\infty}\left(\frac{p}{|\gamma|}\right)^{i}+\sum_{i=0}^{+\infty}(p|\gamma|)^{i}\right). As |\gamma|\in(p,1/p) , both p/|\gamma|<1 and p|\gamma|<1 . Thus the expected value is finite. This carries to the multidimensional case as the noise added to each component are independent and thus \mathbb{E}\left[|f_{\gamma}(\tilde{x})|\right]=\prod_{i=1}^{n}\mathbb{E}\left[|\gamma^{\tilde{x}_{i}}|\right]. We use the same independence property to get the unbiased estimator. It is useful to express this using the operator form of the estimator. Let \Delta_{i}f(y)=f(y+e_{i})-2f(y)+f(y-e_{i}) denote the discrete second derivative in coordinate i , and write T_{i}=I-c\Delta_{i} , c=\frac{p}{(1-p)^{2}} . Then Theorem 2 can be written compactly as g=\prod_{i=1}^{n}T_{i}f, where the operators commute because they act on different coordinates. As \Delta_{i}(f_{\gamma}(y))=\frac{(1-\gamma)^{2}}{\gamma}f_{\gamma}(y) , this gives g_{\gamma}(y)=A(\gamma)^{n}f_{\gamma}(y) . Last, whenever the variance of f_{\gamma}(\tilde{x}) exists, it follows immediately that the variance of g_{\gamma}(\tilde{x}) exists as well and that \operatorname{Var}\left(g_{\gamma}(\tilde{x})\right)=A(\gamma)^{2n}\operatorname{Var}\left(f_{\gamma}(\tilde{x})\right) . The existence of that variance is given by the previous claim on expected value by noticing that \operatorname{Var}\left(f_{\gamma}(\tilde{x})\right) converges exactly when \mathbb{E}\left[f_{\gamma^{2}}(\tilde{x})\right] converges. ∎ B.4 Proof of Proposition 8 Proof. Write \alpha_{0}=1+2c , \alpha_{+1}=\alpha_{-1}=-c , where c=p/(1-p)^{2} . For y with \sum_{i}y_{i}=0 , g(y)=\sum_{\xi:\,\sum_{i}\xi_{i}>0}\prod_{i}\alpha_{\xi_{i}}. Let \beta_{k}=\sum_{\xi:\,\sum_{i}\xi_{i}=k}\prod_{i}\alpha_{\xi_{i}} . Then \beta_{k}=\beta_{-k} and \sum_{k}\beta_{k}=1 , so g(y)=\sum_{k>0}\beta_{k}=\tfrac{1-\beta_{0}}{2} . Since all terms in the sum defining \beta_{0} are non-negative we can lower bound \beta_{0} using vectors \xi with n/2 entries +1 and n/2 entries -1 : \beta_{0}\geq\binom{n}{n/2}c^{n}\geq\tfrac{(2c)^{n}}{n+1}. For \varepsilon\leq 1 we have p\geq e^{-1} and thus c=p/(1-p)^{2}>0.92 . Consider the event E that \sum_{i}\xi_{i}=0 . By standard concentration bounds, \Pr[E]=\Theta(n^{-1/2}) . Conditioned on E , we have \sum_{i}\tilde{x}_{i}=0 , so |g(\tilde{x})|=\tfrac{|1-\beta_{0}|}{2}\geq\Omega\bigl((2c)^{n}/n\bigr). Since \mathbb{E}\left[g(\tilde{x})\right]=0 , \operatorname{Var}\left(g(\tilde{x})\right)\geq\Pr[E]\cdot\Omega\bigl((2c)^{2n}/n^{2}\bigr)=\Omega\bigl((2c)^{2n}/n^{5/2}\bigr), which is exponential since 2c>1 . ∎ Appendix C Details on Transformations to Other Mechanisms C.1 Illustration of the Conversion to the Laplace Mechanism Figure 2 : Illustration of Theorem 10 for \varepsilon=2 (so p=e^{-2} ). Each red curve is one translated component \Pr[\eta=k]\,q_{\rm Lap}(z-k) corresponding to an atom of the discrete Laplace distribution \eta\sim\mathrm{DLap}(e^{-\varepsilon}) . Summing all components yields exactly the continuous Laplace density \frac{\varepsilon}{2}e^{-\varepsilon|z|} shown in black. C.2 Conversion to the Staircase Mechanism We next treat the Staircase noise distribution 5 , 6 in the standard form used in the differential privacy literature. Like for the Laplace mechanisms we use the parameter p=e^{-\varepsilon} and further introduce a shape parameter \gamma\in[0,1/2] . Define the symmetric density f_{\gamma} by f_{\gamma}(x)=\begin{cases}a_{\gamma}\,p^{k}&\text{ for }|x|\in[k,k+\gamma),\,k\in\mathbb{Z}_{\geq 0}\\ a_{\gamma}\,p^{k+1}&\text{ for }|x|\in[k+\gamma,k+1),\,k\in\mathbb{Z}_{\geq 0}\end{cases} where a_{\gamma}=\frac{1-p}{2(\gamma+p(1-\gamma))} . Additive noise using this density function is the staircase mechanism with shape parameter \gamma , satisfying \varepsilon -differential privacy 5 , 6 . Theorem 17 . Fix \gamma\in[0,1/2] . Let \eta be sampled from the discrete Laplace distribution with parameter p , and let Y_{\gamma} be independent of \eta with density q_{\gamma}(y)=\begin{cases}\tfrac{1+p}{2(\gamma+p(1-\gamma))}&\text{for }|y|<\gamma\\ \tfrac{p}{2(\gamma+p(1-\gamma))}&\text{for }\gamma\leq|y|\leq 1-\gamma\\ 0&\text{otherwise }\end{cases}\kern 5.0pt. Then \eta+Y_{\gamma} has density f_{\gamma} . Proof. The function q_{\gamma} is symmetric and nonnegative. Its total mass (the integral over all reals) is 2\gamma\cdot\tfrac{1+p}{2(\gamma+p(1-\gamma))}+2(1-2\gamma)\cdot\tfrac{p}{2(\gamma+p(1-\gamma))}=1, so it is indeed a density. For any z we write |z|=n+u with n\geq 0 and u\in[0,1) , and apply Lemma 9 . If u<\gamma , then q_{\gamma}(u)=\frac{1+p}{2(\gamma+p(1-\gamma))} and q_{\gamma}(u-1)=0 , because |u-1|>1-\gamma . Therefore f_{X+Y_{\gamma}}(z)=\tfrac{1-p}{1+p}p^{n}\cdot\tfrac{1+p}{2(\gamma+p(1-\gamma))}=a_{\gamma}p^{n}. If \gamma\leq u<1-\gamma , then q_{\gamma}(u)=q_{\gamma}(u-1)=\frac{p}{2(\gamma+p(1-\gamma))} , and hence f_{X+Y_{\gamma}}(z)=\tfrac{1-p}{1+p}p^{n}\cdot\tfrac{p(1+p)}{2(\gamma+p(1-\gamma))}=a_{\gamma}p^{n+1}. If 1-\gamma\leq u , then q_{\gamma}(u)=0 and q_{\gamma}(u-1)=\frac{1+p}{2(\gamma+p(1-\gamma))} , so again f_{X+Y_{\gamma}}(z)=\tfrac{1-p}{1+p}p^{n}\cdot p\tfrac{1+p}{2(\gamma+p(1-\gamma))}=a_{\gamma}p^{n+1}. This matches exactly the definition of f_{\gamma} . ∎ The transformation is illustrated in Figure 3 . Figure 3 : Illustration of Theorem 17 for \varepsilon=1 and \gamma=\tfrac{1}{4} (so p=e^{-1} ). Each red dashed curve is one translated component \Pr[\eta=k]\,q_{\gamma}(z-k) corresponding to an atom of the discrete Laplace distribution \eta\sim\mathrm{DLap}(e^{-\varepsilon}) . Summing all components yields exactly the Staircase density shown in black. Appendix D Omitted Details from Section 5 In Section D.1 , we describe the general framework for obtaining faster unbiased formula. In the remaining sections, we use this framework to obtain faster estimators for various functions. The functions in this section satisfy the condition of Theorem 2 , and thus have unbiased estimators, because they all exhibit subexponential growth which ensures their expectation exists and is finite. We formalize this in the following lemma. Lemma 18 . For p\in(0,1) , suppose |f(y)|\leq r(\|y\|_{1}) , where r(k):\mathbb{R}\rightarrow\mathbb{R} is an increasing function such that \lim_{k\rightarrow\infty}r(k)p^{k/4}=0 . For a given x\in\mathbb{Z}^{d} , let \tilde{x}=x+\textnormal{{DLap}}(p)^{d} . Then, \mathbb{E}\left[f(\tilde{x})\right] exists and is finite. Proof. We will show that the expectation converges to a finite value. To do so, observe the expectation can be written as a limit of the following partial sums: \displaystyle\mathbb{E}\left[f(\tilde{x})\right] \displaystyle=\sum_{z\in\mathbb{Z}^{d}}f(x+z)\left(\frac{1-p}{1+p}\right)^{d}p^{\|z\|_{1}} \displaystyle=\lim_{k\rightarrow\infty}\sum_{z:\|z\|_{1}\leq k}f(x+z)\left(\frac{1-p}{1+p}\right)^{d}p^{\|z\|_{1}}. Define the partial sum P(k)=\sum_{z:\|z\|_{1}\leq k}f(x+z)p^{\|z\|_{1}} . We will show that for any \alpha>0 , there exists k_{0} such that for all k_{1},k_{2}\geq k_{0} such that k_{1}