Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy

• URL: http://arxiv.org/abs/2606.07443v1
• Date: Fri, 05 Jun 2026 16:41:31 GMT
• Title: Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy
• Abstract summary: We study optimal design of $varepsilon$-locally differentially private mechanisms for binary hypothesis testing.<n>Our results make it possible to efficiently compute and characterize the exact optimum across the full privacy range, beyond privacy regimes.
• Score: 1.8549313085249317
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study optimal design of $\varepsilon$-locally differentially private mechanisms for binary hypothesis testing. Each observation is drawn from one of two known distributions $P_0,P_1$ on a finite alphabet of size $k$, privatized by a mechanism $Q$, and then used to infer which distribution generated the data. We measure testing utility using an $f$-divergence, including total variation, KL, and hockey-stick divergences, between the two induced output distributions. Previous work established structural properties of optimal mechanisms, but only yielded exponential-time algorithms. We prove a sharp structure: for every $\varepsilon$ and every $f$-divergence objective, after sorting the alphabet by likelihood ratio, there exists an optimal mechanism that partitions the sorted alphabet into contiguous blocks and applies randomized response to the block label. We call this class Sort-Partition-Randomize (SPR). This characterization yields an exact dynamic program that computes an optimal mechanism in $O(k^3)$ time, and more generally in $O(\ell k^2)$ time with an $\ell$-output budget. Our results make it possible to efficiently compute and characterize the exact optimum across the full privacy range, beyond asymptotic privacy regimes.

Related papers

• Asymptotical Analysis of the $(1+(λ,λ))$ GA Escape Time from Local Optima on Jump Functions [0.5156484100374058]
  The paper develops the approach to the runtime analysis of evolutionary algorithms on the basis of limit theorems from probability theory.<n>The main result of this work is a tightened upper bound on the escape time from the work of Antipov, Doerr and Karavaev (2022). Besides that, the obtained bound applies to a wider range of algorithm parameters.
  arXiv  Detail & Related papers  (2026-07-15T18:37:48Z)
• Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph [45.975805184376036]
  We describe an algorithm that satisfies local differential privacy, performs $tildeO(k3/2)$ non-adaptive queries to individuals.<n>We also introduce a new object we dub the Scheff'e graph, which captures structure of the differences between distributions in $Q$.
  arXiv  Detail & Related papers  (2025-09-19T17:41:15Z)
• 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)
• Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning [2.2083091880368855]
  We study the differentially private top-$k$ selection problem, aiming to identify a sequence of $k$ items with approximately the highest scores from $d$ items. Recent work by Gillenwater et al. (ICML '22) employs a direct sampling approach from the vast collection of $d,Theta(k)$ possible length-$k$ sequences. We present an improved algorithm with time and space complexity $O(d + k2 / epsilon cdot ln d)$, where $epsilon$ denotes the privacy
  arXiv  Detail & Related papers  (2024-11-14T16:06:13Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Efficiently Computing Similarities to Private Datasets [19.99000806126529]
  Many methods in differentially private model training rely on computing the similarity between a query point (such as public or synthetic data) and private data. We study the following fundamental algorithmic problem: Given a similarity function $f$ and a large high-dimensional private dataset $X subset mathbbRd$, output a differentially private (DP) data structure which approximates $sum_x in X f(x,y)$ for any query $y$.
  arXiv  Detail & Related papers  (2024-03-13T19:19:19Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  Differentially private computation often begins with a bound on some $d$-dimensional statistic's sensitivity. For pure differential privacy, the $K$-norm mechanism can improve on this approach using a norm tailored to the statistic's sensitivity space. This paper solves both problems for the simple statistics of sum, count, and vote.
  arXiv  Detail & Related papers  (2023-09-27T17:09:36Z)
• The Normal Distributions Indistinguishability Spectrum and its Application to Privacy-Preserving Machine Learning [7.61316504036937]
  Differential Privacy is the most common method for machine learning (ML) on privacy-sensitive data. In big data analytics, one often uses randomized sketching/aggregation algorithms to make processing high-dimensional data tractable.
  arXiv  Detail & Related papers  (2023-09-03T19:07:31Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
  arXiv  Detail & Related papers  (2020-04-16T19:16:38Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

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.