Privacy by Postprocessing the Discrete Laplace Mechanism

• URL: http://arxiv.org/abs/2605.06502v1
• Date: Thu, 07 May 2026 16:19:08 GMT
• Title: Privacy by Postprocessing the Discrete Laplace Mechanism
• Abstract summary: We show that an "old dog", the classical discrete Laplace (aka.geometric) mechanism, can "perform new tricks"<n>It can be post-processed to yield a simple, unbiased estimator of any subexponential function $f$ of the original data.
• Score: 11.768495184175054
• License: http://creativecommons.org/licenses/by/4.0/
• 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$ 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 $\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$ 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.

Related papers

• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  We investigate the Generalized Gaussian mechanism, which samples the additive noise term $x$ with probability proportional to $e-frac| x |sigmabeta $ for some $beta geq 1$.<n>We show that privacy accounting for the GG Mechanism and its variants is independent, which substantially improves computational costs of privacy accounting.
  arXiv  Detail & Related papers  (2025-06-14T15:49:25Z)
• Debiasing Functions of Private Statistics in Postprocessing [6.22153888560487]
  We derive an unbiased estimator for private means when the size $n$ of the dataset is not publicly known.<n>We also apply our estimators to develop unbiased transformation mechanisms for per-record differential privacy.
  arXiv  Detail & Related papers  (2025-02-18T22:16:37Z)
• Streaming Private Continual Counting via Binning [11.72102598708538]
  We present a simple approach to approximating factorization mechanisms in low space via $textitbinning$.<n>We show empirically that even with very low space usage we are able to closely match, and sometimes surpass, the performance of optimal factorization mechanisms.
  arXiv  Detail & Related papers  (2024-12-10T01:21:56Z)
• Truncated Laplace and Gaussian mechanisms of RDP [28.227024132603123]
  The Laplace mechanism and the Gaussian mechanism are primary mechanisms in differential privacy. Due to the infinite-range random variables they generate, the Laplace and Gaussian mechanisms may return values that are semantically impossible, such as negative numbers.
  arXiv  Detail & Related papers  (2023-09-22T06:37:45Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Robust computation of optimal transport by $\beta$-potential regularization [79.24513412588745]
  Optimal transport (OT) has become a widely used tool in the machine learning field to measure the discrepancy between probability distributions. We propose regularizing OT with the beta-potential term associated with the so-called $beta$-divergence. We experimentally demonstrate that the transport matrix computed with our algorithm helps estimate a probability distribution robustly even in the presence of outliers.
  arXiv  Detail & Related papers  (2022-12-26T18:37:28Z)
• Statistical Properties of the log-cosh Loss Function Used in Machine Learning [0.0]
  We present the distribution function from which the log-cosh loss arises. We also examine the use of the log-cosh function for quantile regression.
  arXiv  Detail & Related papers  (2022-08-09T07:03:58Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Strongly universally consistent nonparametric regression and classification with privatised data [2.879036956042183]
  We revisit the classical problem of nonparametric regression, but impose local differential privacy constraints. We design a novel estimator of the regression function, which can be viewed as a privatised version of the well-studied partitioning regression estimator.
  arXiv  Detail & Related papers  (2020-10-31T09:00:43Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.