N-output Mechanism: Estimating Statistical Information from Numerical Data under Local Differential Privacy

• URL: http://arxiv.org/abs/2510.11116v1
• Date: Mon, 13 Oct 2025 08:06:59 GMT
• Title: N-output Mechanism: Estimating Statistical Information from Numerical Data under Local Differential Privacy
• Authors: Incheol Baek, Yon Dohn Chung,
• Abstract summary: Local Differential Privacy (LDP) addresses significant privacy concerns in sensitive data collection.<n>Existing LDP mechanisms are optimized for either a very small ($|Omega| in 2, 3$) or infinite output spaces.<n>We propose the textbfN-output mechanism, a generalized framework that maps numerical data to one of $N$ discrete outputs.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Local Differential Privacy (LDP) addresses significant privacy concerns in sensitive data collection. In this work, we focus on numerical data collection under LDP, targeting a significant gap in the literature: existing LDP mechanisms are optimized for either a very small ($|\Omega| \in \{2, 3\}$) or infinite output spaces. However, no generalized method for constructing an optimal mechanism for an arbitrary output size $N$ exists. To fill this gap, we propose the \textbf{N-output mechanism}, a generalized framework that maps numerical data to one of $N$ discrete outputs. We formulate the mechanism's design as an optimization problem to minimize estimation variance for any given $N \geq 2$ and develop both numerical and analytical solutions. This results in a mechanism that is highly accurate and adaptive, as its design is determined by solving an optimization problem for any chosen $N$. Furthermore, we extend our framework and existing mechanisms to the task of distribution estimation. Empirical evaluations show that the N-output mechanism achieves state-of-the-art accuracy for mean, variance, and distribution estimation with small communication costs.

Related papers

• Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy [3.7942266369982955]
  We show that for any dimension, any norm, and any norm-monotone cost function, there exists an $$-DP staircase mechanism that is optimal among all additive mechanisms.<n>This result resolves a conjecture of Geng, Kairouz, Oh, and Viswanath, and provides a geometric explanation for the emergence of staircase mechanisms as extremal solutions in differential privacy.
  arXiv  Detail & Related papers  (2026-01-21T02:35:33Z)
• Privacy Mechanism Design based on Empirical Distributions [36.33156483258328]
  Pointwise maximal leakage (PML) is a per-outcome privacy measure based on threat models from quantitative information flow.<n>We propose a framework for PML privacy assessment and mechanism design with empirical estimates of this data-generating distribution.
  arXiv  Detail & Related papers  (2025-09-26T14:46:59Z)
• Distributionally Robust Optimization with Adversarial Data Contamination [49.89480853499918]
  We focus on optimizing Wasserstein-1 DRO objectives for generalized linear models with convex Lipschitz loss functions.<n>Our primary contribution lies in a novel modeling framework that integrates robustness against training data contamination with robustness against distributional shifts.<n>This work establishes the first rigorous guarantees, supported by efficient computation, for learning under the dual challenges of data contamination and distributional shifts.
  arXiv  Detail & Related papers  (2025-07-14T18:34:10Z)
• 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)
• Optimal Piecewise-based Mechanism for Collecting Bounded Numerical Data under Local Differential Privacy [5.258253745672122]
  Local differential privacy (LDP) has been shown as a framework providing provable individual privacy, even when the third-party platform is untrusted.<n>This paper investigates the optimal design of piecewise-based mechanisms to maximize data utility under LDP.
  arXiv  Detail & Related papers  (2025-05-21T13:01:41Z)
• Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits [8.013444110633223]
  We analytically derive a class of optimal solutions to a linear program (LP) for automated mechanism design.<n>These solutions can be expressed using a set of essential variables whose cardinality is exponentially smaller than the total number of variables in the original formulation.<n>We address this by translating the evaluation of this term into a multi-armed bandit (MAB) problem.
  arXiv  Detail & Related papers  (2024-11-30T03:59:36Z)
• Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy [47.997934291881414]
  Existing mean estimation schemes are usually optimized for $L_infty$ geometry and rely on random rotation or Kashin's representation to adapt to $L$ geometry. We introduce a novel privacy accounting method for the sparsified Gaussian mechanism that incorporates the randomness inherent in sparsification into the DP. Unlike previous approaches, our accounting algorithm directly operates in $L$ geometry, yielding MSEs that fast converge to those of the Gaussian mechanism.
  arXiv  Detail & Related papers  (2024-05-02T03:48:47Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Bounded and Unbiased Composite Differential Privacy [25.427802467876248]
  The objective of differential privacy (DP) is to protect privacy by producing an output distribution that is indistinguishable between two neighboring databases. Existing solutions attempt to address this issue by employing post-processing or truncation techniques. We propose a novel differentially private mechanism which uses a composite probability density function to generate bounded and unbiased outputs.
  arXiv  Detail & Related papers  (2023-11-04T04:43:47Z)
• Online non-parametric likelihood-ratio estimation by Pearson-divergence functional minimization [55.98760097296213]
  We introduce a new framework for online non-parametric LRE (OLRE) for the setting where pairs of iid observations $(x_t sim p, x'_t sim q)$ are observed over time. We provide theoretical guarantees for the performance of the OLRE method along with empirical validation in synthetic experiments.
  arXiv  Detail & Related papers  (2023-11-03T13:20:11Z)
• 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)

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.