Strict Optimality of Frequency Estimation Under Local Differential Privacy

• URL: http://arxiv.org/abs/2603.11523v1
• Date: Thu, 12 Mar 2026 04:16:22 GMT
• Title: Strict Optimality of Frequency Estimation Under Local Differential Privacy
• Abstract summary: This paper establishes the strict optimality in precision for frequency estimation under local differential privacy.<n>We prove that a frequency estimator with a symmetric and extremal configuration, and a constant support size equal to an optimized value, is sufficient to achieve maximum precision.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper establishes the strict optimality in precision for frequency estimation under local differential privacy (LDP). We prove that a frequency estimator with a symmetric and extremal configuration, and a constant support size equal to an optimized value, is sufficient to achieve maximum precision. Furthermore, we derive that the communication cost of such an optimal estimator can be as low as $\log_2(\frac{d(d-1)}{2}+1)$, where $d$ denotes the dictionary size, and propose an algorithm to generate this optimal estimator. In addition, we introduce a modified Count-Mean Sketch and demonstrate that it is practically indistinguishable from theoretical optimality with a sufficiently large dictionary size (e.g., $d=100$ for a privacy factor of $ε= 1$). We compare existing methods with our proposed optimal estimator to provide selection guidelines for practical deployment. Finally, the performance of these estimators is evaluated experimentally, showing that the empirical results are consistent with our theoretical derivations.

Related papers

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization [57.179679246370114]
  A potential limitation of existing methods is the bias inherent in most perturbation estimators unless a stepsize is proposed.<n>We propose a novel family of unbiased gradient scaling estimators that eliminate bias while maintaining favorable construction.
  arXiv  Detail & Related papers  (2025-10-22T18:25:43Z)
• Minimax Optimal Kernel Two-Sample Tests with Random Features [6.747832388017275]
  We propose a spectral-regularized two-sample test based on random Fourier feature (RFF) approximation.<n>We show the proposed test to be minimax optimal if the approximation order of RFF is sufficiently large.<n>We develop a practically implementable permutation-based version of the proposed test with a data-adaptive strategy for selecting the regularization parameter.
  arXiv  Detail & Related papers  (2025-02-28T06:12:00Z)
• 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)
• Optimally-Weighted Estimators of the Maximum Mean Discrepancy for Likelihood-Free Inference [12.157511906467146]
  Likelihood-free inference methods typically make use of a distance between simulated and real data. The maximum mean discrepancy (MMD) is commonly estimated at a root-$m$ rate, where $m$ is the number of simulated samples. We propose a novel estimator for the MMD with significantly improved sample complexity.
  arXiv  Detail & Related papers  (2023-01-27T12:13:54Z)
• Best Arm Identification in Stochastic Bandits: Beyond $\eta-$optimality [31.359578768463752]
  This paper investigates a hitherto unaddressed aspect of best arm identification (BAI) in multi-armed bandits in the fixed-confidence setting. Two key metrics for assessing bandit algorithms are computational efficiency and performance optimality. This paper introduces a framework and an algorithm for BAI that achieves optimal performance with a computationally efficient set of decision rules.
  arXiv  Detail & Related papers  (2023-01-10T05:02:49Z)
• On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood [33.051282474765955]
  Our estimator is based on profile-maximum-likelihood (PML) and is sample optimal for estimating various symmetric properties. This result improves upon the previous best accuracy threshold of $epsilon gg n-1/4$ by achievable time.
  arXiv  Detail & Related papers  (2022-10-13T04:52:15Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares [68.8204255655161]
  We consider potentially non- optimized approximation problems. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees.
  arXiv  Detail & Related papers  (2022-04-11T09:37:04Z)
• Entropic estimation of optimal transport maps [15.685006881635209]
  We develop a method for estimating the optimal map between two distributions over $mathbbRd$ with rigorous finite-sample guarantees. We show that our estimator is easy to compute using Sinkhorn's algorithm.
  arXiv  Detail & Related papers  (2021-09-24T14:57:26Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure. Our method achieves significantly higher robustness than existing discrepancy measures.
  arXiv  Detail & Related papers  (2020-06-13T06:09:27Z)
• Projection Robust Wasserstein Distance and Riemannian Optimization [107.93250306339694]
  We show that projection robustly solidstein (PRW) is a robust variant of Wasserstein projection (WPP) This paper provides a first step into the computation of the PRW distance and provides the links between their theory and experiments on and real data.
  arXiv  Detail & Related papers  (2020-06-12T20:40:22Z)

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.