Strict Optimality of Frequency and Distribution Estimation Under Local Differential Privacy

Mingen Pan · 2026

Read Strict Optimality of Frequency and Distribution Estimation Under Local Differential Privacy by Mingen Pan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-11523.txt.

Introduction

Pan proves strict optimality for frequency and distribution estimation under local differential privacy. The winning design is linear, symmetric, and extremal, with support size set to an optimized value. It hits the L2 lower bound for both tasks, and the L1 bound in the limit. Its communication cost can drop to a short log-sized bit count. Pan also gives an algorithm to build the estimator, plus selection guidance for practice. A modified Count-Mean Sketch, he shows, sits practically at the optimal level too.

Catalog record

CREATORMingen Pan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91821
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.11523

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Strict Optimality of Frequency and Distribution Estimation Under Local Differential Privacy Mingen Pan Abstract Abstract This paper establishes the strict optimality in precision for frequency and distribution estimation under local differential privacy (LDP). We prove that a linear estimator with a symmetric and extremal configuration, and a constant support size equal to an optimized value, is sufficient to achieve the theoretical lower bound of the \mathcal{L}_{2} loss for both frequency and distribution estimation. The theoretical \mathcal{L}_{1} lower bound is also achieved asymptotically. 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) bits, 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 parameter of \epsilon=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. 1 Introduction The frequency of a dataset and the distribution of a population represent the most fundamental statistics. They serve as the essential building blocks for deriving a wide array of statistical properties, ranging from basic mean and variance to more complex higher-order moments. While computing frequencies or distributions is straightforward when an analyst has unrestricted access to a dataset, typically involving a simple iteration using a hash map, the task becomes significantly more complex when raw individual values are inaccessible. This is often the case when robust data privacy protections are implemented to mask sensitive information. This paper focuses on a privacy-preserving technique known as Local Differential Privacy (LDP) [ 13 ] , the localized counterpart to Differential Privacy (DP) [ 9 ] , which has become the de facto standard for data privacy. Before reporting an aggregate statistic from a dataset, DP injects sufficient noise into the result to ensure that an adversary cannot determine whether a specific data point was included in the original set. However, DP traditionally requires centralized data processing, meaning it collects and stores raw data from clients before adding noise to the final aggregation. This architecture leaves data vulnerable to server breaches and eavesdropping during the transmission of raw values. LDP was proposed to mitigate these risks by perturbing data locally on the client side before it is sent to the server. Consequently, even if intercepted, an adversary cannot effectively infer the original value from the perturbed output. The degree of this perturbation is quantified by a privacy parameter, \epsilon , representing the maximum amount of knowledge an adversary can gain from the perturbed result [ 15 ] . Since frequency and distribution are such fundamental statistical properties, numerous LDP algorithms have been developed to estimate them effectively. These algorithms are discussed in detail in Section 1.1 . Among them, the Subset Selection mechanism proposed by [ 19 , 22 ] achieved state-of-the-art precision regarding \mathcal{L}_{1} and \mathcal{L}_{2} losses. These metrics, formally defined in Section 2.2 , measure the overall precision across all estimated frequencies or distributions. Notably, since the introduction of Subset Selection, no subsequent LDP estimator has surpassed its leading precision in these metrics. While the leading precision has remained unsurpassed for years, it remains unknown whether these algorithms are strictly optimal. The Subset Selection paper [ 22 ] established a lower bound for LDP distribution estimation, proving that their algorithm is order-optimal when e^{\epsilon}\ll d . However, a significant gap remains in the constant term; specifically, the derived lower bound can be as low as \frac{1}{512} of the achieved precision. A follow-up study [ 23 ] suggested that Subset Selection achieves asymptotic strict optimality for distribution estimation, but this does not apply to finite datasets or frequency estimation (see Section 1.1 ). It remains unclear whether an algorithm exists to bridge this gap, or if current approaches are already strictly optimal. This paper directly addresses these questions by establishing a strict lower bound for LDP frequency and distribution estimation precision in terms of \mathcal{L}_{1} and \mathcal{L}_{2} losses: Proposition 1 . Let d , \epsilon , n , and \hat{f} denote the dictionary size (the number of all possible inputs), privacy parameter, dataset size, and frequency estimator, respectively. The minimum \mathcal{L}_{2} loss is given by \min_{\hat{f}}\mathcal{L}_{2}(\hat{f})=\begin{cases}\displaystyle\frac{(d-1)[4de^{\epsilon}-(e^{\epsilon}+1)^{2}]}{nd(e^{\epsilon}-1)^{2}}&\text{if }d\geq e^{\epsilon}+1,\\[15.0pt] \displaystyle\frac{(d-1)(d+2e^{\epsilon}-2)}{n(e^{\epsilon}-1)^{2}}&\text{otherwise.}\end{cases} Meanwhile, \min_{\hat{f}}\mathcal{L}_{1}(\hat{f})\approx\sqrt{\frac{2}{\pi}\min_{\hat{f}}\mathcal{L}_{2}(\hat{f})}. Full details are presented in Theorem 3.8 and Corollary 3.3 . Distribution estimation has a similar result: \min_{\hat{\theta}}\mathcal{L}_{2}(\hat{\theta},n)=\min_{\hat{f}}\mathcal{L}_{2}(\hat{f},n)+\frac{1-1/d}{n} , and \min_{\hat{\theta}}\mathcal{L}_{1}(\hat{\theta},n)\approx\sqrt{\frac{2}{\pi}\min_{\hat{\theta}}\mathcal{L}_{2}(\hat{\theta},n)} , where \hat{\theta} denotes a distribution estimator. To establish these tight lower bounds, this paper first demonstrates that an estimator constructed from a uniformly random permutation (URP), when paired with an optimized reconstruction matrix, achieves the theoretical \mathcal{L}_{2} loss lower bound derived from the Fisher information for any given perturbation matrix. The theoretical \mathcal{L}_{1} lower bound is also achieved asymptotically. We then prove that these losses are further minimized when the perturbation matrix maintains a constant support size across all responses. Under these conditions, we express \mathcal{L}_{1} and \mathcal{L}_{2} as functions of the support size while holding other parameters constant. Finally, we determine the optimal support size to derive the strict lower bounds for both loss functions. The complete proof is provided in Section 3 . Furthermore, we derive that the communication cost, defined as the number of bits required to transfer a response from a client, for an optimal estimator is upper bounded by \log_{2}(\frac{d(d-1)}{2}+1) bits, where d denotes the dictionary size. We then develop an optimal estimator, Weighted Subset Selection, which achieves this reduced communication cost despite having high precomputation requirements. Subsequently, we evaluate the optimality of existing algorithms and find that Subset Selection [ 22 ] already achieves strict optimality in terms of precision, while its communication cost is linear in d . We also demonstrate that the Count-Mean Sketch (CMS), with minor modifications, can approach strict optimality provided the dictionary size is sufficiently large, such as when d=100 for \epsilon=1 . Notably, this modified version, which we refer to as Optimized CMS, requires a significantly lower communication cost of O(\log_{2}(d)) bits, making it much more efficient than Subset Selection. Consequently, we provide practical guidance for their deployment; the rule of thumb is to employ Optimized CMS when the dictionary size is sufficiently large and to use either Weighted Subset Selection or the original Subset Selection otherwise. Finally, we conduct two experiments in Section 6 to compare the performance of the optimal algorithms discussed in Section 5 with the theoretical strict lower bounds of \mathcal{L}_{1} and \mathcal{L}_{2} . Both experiments demonstrate that all three optimal algorithms align perfectly with the strict lower bounds. 1.1 Previous Work Numerous LDP algorithms have been developed for frequency and distribution estimation. Randomized Response [ 21 , 12 ] , predating the formal LDP definition, was initially designed for the frequency estimation of sensitive data. RAPPOR [ 10 ] later achieved estimation precision for individual values independent of the dictionary size d , although its communication cost remains linear in d . Subsequently, methods such as Hadamard Encoding [ 4 ] , private Count-Mean Sketch [ 8 ] , Local Hashing and asymmetric RAPPOR [ 20

Read the complete text