Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy
Open accessThe DOI matches its Crossref record; 20 of the 24 references it cites were found in a registry or an index.
Abstract
We consider the minimax estimation problem of a discrete distribution with support size k under privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A positive number ∈ measures the privacy level of a privatization scheme. For a given ∈, we consider the problem of constructing optimal privatization schemes with ∈-privacy level, i.e., schemes that minimize the expected estimation loss for the worst-case distribution. Two schemes known in the literature provide order optimal performance in the high privacy regime where E is very close to 0, and in the low privacy regime where e∈≈ k, respectively. In this paper, we propose a new family of schemes which substantially improve the performance of the existing schemes in the medium privacy regime when 1 ≪ e∈≪ k. More concretely, we prove that when 3.822metric and by 30% under ℓ1metric over the existing schemes. We also prove a lower bound for the region e∈≪ k, which implies that our schemes are order optimal in this regime.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Recent work has found ways to approximate the geometric median under SecAgg [379] by using a handful of SecAgg calls in a more general aggregation loop.”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [379]
Citations
Cites
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Differential Privacy: A Survey of Results
Dwork, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-79228-4_1 · Cited by 3,542
Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
Warner, S. L. (1965) · Journal of the American Statistical Association · doi:10.1080/01621459.1965.10480775 · Cited by 3,255
Introduction to Nonparametric Estimation
Tsybakov, A. B. (2009) · Springer Series in Statistics · doi:10.1007/b13794 · Cited by 2,486
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response
Erlingsson, Ú., Pihur, V., & Korolova, A. (2014) · Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2660267.2660348 · Cited by 1,838
(1998) · Springer Texts in Statistics · doi:10.1007/b98854 · Cited by 1,719
Local Privacy and Statistical Minimax Rates
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · 2013 IEEE 54th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.53 · Cited by 954
Minimax Optimal Procedures for Locally Private Estimation
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2018) · Journal of the American Statistical Association · doi:10.1080/01621459.2017.1389735 · Cited by 386
Universally Utility-maximizing Privacy Mechanisms
Ghosh, A., Roughgarden, T., & Sundararajan, M. (2012) · SIAM Journal on Computing · doi:10.1137/09076828x · Cited by 253
Theory of Probability and Random Processes
Koralov, L., & Sinai, Y. G. (2007) · Universitext · doi:10.1007/978-3-540-68829-7 · Cited by 241
Research works printed but not linked: 2
- assouad, 1983, Deux remarques sur l’estimation, Comptes Rendus Math Acad Sci Paris, 296, 1021
- royden, 2010, Real Analysis
Cited by
Items 101–163 of 163
Wu, X., Bilal, M., Xu, X., & Song, H. (2023) · Information Sciences · doi:10.1016/j.ins.2023.119111 · Cited by 4
Heterogeneous Ensemble Federated Learning With GAN-Based Privacy Preservation
Chen, M., Liu, H., Chi, H., & Xiong, P. (2024) · IEEE Transactions on Sustainable Computing · doi:10.1109/tsusc.2024.3350040 · Cited by 5
Optimal locally private estimation under $\ell_{p}$ loss for $1\le p\le 2$
Ye, M., & Barg, A. (2019) · Electronic Journal of Statistics · doi:10.1214/19-ejs1625 · Cited by 4
Self-citationA Survey on Randomized Mechanisms for Statistical Learning under Local Differential Privacy
Shen, L., Wu, X., Wu, D., Xu, X., & Qi, L. (2020) · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS) · doi:10.1109/hpcc-smartcity-dss50907.2020.00155 · Cited by 4
Minimax randomized response methods for protecting respondent’s privacy
Chai, J., & Nayak, T. K. (2021) · Communication in Statistics- Theory and Methods · doi:10.1080/03610926.2021.1973503 · Cited by 3
Block Design-Based Local Differential Privacy Mechanisms
Park, H., Nam, S.-H., & Lee, S.-H. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206918 · Cited by 3
Nam, S.-H., Park, H.-Y., & Lee, S.-H. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3448475 · Cited by 4
PrivRM : A Framework for Range Mean Estimation under Local Differential Privacy
Yu, L., Ye, Q., & Du, R. (2025) · Proceedings of the ACM on Management of Data · doi:10.1145/3725414 · Cited by 3
Distribution Privacy Under Function Recoverability
Nageswaran, A., & Narayan, P. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3140317 · Cited by 4
Private Estimation of Symptom Distribution for Infectious Disease Analysis in Edge Computing
Wu, X., Xu, X., Wan, S., & Qi, L. (2021) · IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC) · doi:10.1109/euc53437.2021.00014 · Cited by 3
On the Utility Gain of Iterative Bayesian Update for Locally Differentially Private Mechanisms
Arcolezi, H. H., Cerna, S., & Catuscia Palamidessi, A. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-37586-6_11 · Cited by 3
Nam, S.-H., Park, H.-Y., & Lee, S.-H. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619385 · Cited by 4
Successive Refinement of Privacy
Girgis, A. M., Data, D., Chaudhuri, K., Fragouli, C., & Diggavi, S. N. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.3040403 · Cited by 4
LabelDP Leaks Privacy — A Tightened Correlation-Aware Privacy Model for Labeled Training Data
Xue, Q., Ye, Q., Hu, H., Lou, J., Li, J., Fang, C., & Shi, J. (2025) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2025.3607786 · Cited by 2
Zhao, P., Zhang, Z., Sun, B., Shen, L., Zhang, L., Wang, S., & Liu, Z. (2026) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp63933.2026.00054 · Cited by 2
An Efficient and Privacy-Preserving Outsourced Heavy Hitter Query Scheme with LDP Technique
Zhang, E. Z., Guan, Y., Zhang, S., Lu, R., & Zhang, H. (2023) · IEEE/CIC International Conference on Communications in China (ICCC) · doi:10.1109/iccc57788.2023.10233644 · Cited by 2
Maximum Privacy under Perfect Utility in Sensor Networks
Wang, C. X., Tay, W. P., & Song, Y. (2020) · IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM) · doi:10.1109/sam48682.2020.9104271 · Cited by 3
Differentially Private Parameter Estimation: Optimal Noise Insertion and Data Owner Selection
Cao, X., & Başar, T. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9304375 · Cited by 2
Fisher Information as a Utility Metric for Frequency Estimation under Local Differential Privacy
Lopuhaä-Zwakenberg, M., korić, B., & Li, N.-H. (2022) · WPES@CCS · doi:10.1145/3559613.3563194 · Cited by 3
Ye, Q., Yu, L., Huang, K., Xiao, X., Liu, W., & Hu, H. (2025) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp61157.2025.00215 · Cited by 5
Data Privacy for a ρ-Recoverable Function
Nageswaran, A., & Narayan, P. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437327 · Cited by 4
Research on Selection Method of Privacy Parameter ε
Sun, P. J. (2020) · Security and Communication Networks · doi:10.1155/2020/8845038 · Cited by 2
A Frequency Estimation Algorithm under Local Differential Privacy
Qin, D., & Zhang, Z. (2021) · International Conference on Ubiquitous Information Management and Communication (IMCOM) · doi:10.1109/imcom51814.2021.9377325 · Cited by 2
Compressive Sensing Approaches for Sparse Distribution Estimation Under Local Privacy
Xiong, Z., Sun, J., Mao, X., Wang, J., Shan, Y., & Huang, Z. (2022) · International World Wide Web Conference (WWW) · doi:10.1145/3485447.3512220 · Cited by 3
Practical Differential Privacy for Location Data Aggregation using a Hadamard Matrix
Sangiamchit, P., & Fakcharoenphol, J. (2019) · International Joint Conference on Computer Science and Software Engineering · doi:10.1109/jcsse.2019.8864180 · Cited by 2
Tight lower bound of sparse covariance matrix estimation in the local differential privacy model
Wang, D., & Xu, J. (2020) · Theoretical Computer Science · doi:10.1016/j.tcs.2020.02.027 · Cited by 2
Distribution Privacy Under Function Recoverability
Nageswaran, A., & Narayan, P. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174389 · Cited by 2
Distribution Privacy Under Function $\rho$ -Recoverability
Nageswaran, A., & Narayan, P. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9517744 · Cited by 3
Estimating Sparse Discrete Distributions Under Local Privacy and Communication ConstraintsPreprint
Acharya, J., Kairouz, P., Liu, Y., & Sun, Z. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.00083 · Cited by 2
Privately Learning Mixtures of Axis-Aligned GaussiansPreprint
Aden-Ali, I., Ashtiani, H., & Liaw, C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.02162 · Cited by 2
Statistical Inference in the Differential Privacy ModelPreprint
Zhang, H. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.05000 · Cited by 8
Pan, M. (2025) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf64896.2025.00024 · Cited by 2
Wang, Y. Y., Zhu, Y., Wang, S., Xue, Q., & Wang, J. (2025) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2025.3597536 · Cited by 1
Quantum Advantage in Private Multiple Hypothesis Testing
Nam, S.-H., Park, H., Bae, J., & Lee, S.-H. (2025) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit63088.2025.11195216 · Cited by 3
P2NIA: Privacy-Preserving Non-iterative Auditing
Bourrée, J. G., Lautraite, H., Gambs, S., Trédan, G., Merrer, E. L., & Rottembourg, B. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-06096-9_15 · Cited by 2
Estimating Sparse Distributions Under Joint Communication and Privacy Constraints
Ahn, S., Chen, W., & Özgür, A. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834610 · Cited by 1
Efficient Discrete Distribution Estimation Schemes Under Local Differential Privacy
Dun, W., & Zhu, Y. (2020) · Communications in computer and information science · doi:10.1007/978-981-15-9739-8_38 · Cited by 1
Análise de Dados Privada em Redes Sociais
Mendonça, A. L. C., Brito, F. T., & Machado, J. C. (2024) · doi:10.5753/sbc.14597.4.4 · Cited by 2
Compressive Privatization: Sparse Distribution Estimation under Locally Differentially Privacy.Preprint
Xiong, Z., Huang, Z., Mao, X., Wang, J., & Ying, S. (2020) · arXiv (Cornell University) · Cited by 1
Hiding Identities: Estimation Under Local Differential Privacy
Girgis, A. M., Data, D., & Diggavi, S. N. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174332
Strong Privacy and Utility Guarantee: Over-the-Air Statistical EstimationPreprint
Zhan, W. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.13531
Local Differential Privacy Is Equivalent to Contraction of $E_γ$-DivergencePreprint
Asoodeh, S., Aliakbarpour, M., & Calmon, F. P. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.01258 · Cited by 14
Jornada de Atualização em Informática 2024
Cappelli, C., Alchieri, E. A. P., Campos, J. N., Mendonça, R. D., Fontinele, A., de Carvalho, L. H. S., Oliveira, I. R., Cardoso, Í. W. F., Coelho, R., Freitas, A. E. S., et al. (2024) · doi:10.5753/sbc.14597.4
Consensus and Approximation-based Distribution Statistics in Network Systems
Li, Y., Jiao, Q., Wang, H., & He, J. (2021) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc50511.2021.9483081
Differentially private statistical estimation
Singhal, V. (2021) · Digital Repository Service (Northeastern University) · doi:10.17760/d20413921
Nayak, T. K. (2021) · Contributions to statistics · doi:10.1007/978-3-030-83670-2_15
Optimal Private Discrete Distribution Estimation with One-Bit Communication
Nam, S.-H., Tan, V. Y. F., & Lee, S.-H. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619154
Theoretical lower bounds for one-dimensional locally private estimations with missing data
Ono, H. (2025) · International Journal of Information Security · doi:10.1007/s10207-024-00973-2
Qin, Z., Zhou, J., Tian, M., Zhou, Y., & Lu, L. (2024) · International Conference on Satellite Internet (SAT-NET) · doi:10.1109/sat-net62854.2024.00013
Group fairness under obfuscated sensitive information
Arcolezi, H. H., Makhlouf, K., & Palamidessi, C. (2025) · Journal of Computer Security · doi:10.1177/0926227x251330212 · Cited by 1
A Practical Privacy Protection Procedure for Gathering Categorical Data
Nayak, T. K., & Zhai, X. (2025) · Sankhya B · doi:10.1007/s13571-025-00382-y
On the Extremal Mechanisms for Local Differential Privacy & Binary Maximal Leakage
Cadir, C., & Shkel, Y. Y. (2025) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit63088.2025.11195662
Necessity of Block Designs for Optimal Locally Private Distribution Estimation
Gentle, A. (2025) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw62417.2025.11240420 · Cited by 3
LFS: A Locally Private Framework for Degree Statistic Estimation With Laplace Mechanism
Li, J., Hu, Y., Li, X., Zhou, S., Wang, Y., Li, F., & Niu, B. (2026) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2026.3655155
GBC-UG: An Advanced Location Data Distribution Estimation Mechanism Under Geo-Indistinguishability
Tang, C., Zhu, Y., Chen, R., Yi, C., & Wang, J. (2026) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2026.3666945 · Cited by 1
Personalized frequency estimation via multi-domain utility-optimized local differential privacy
Li, Y., Fu, X., Liu, L., Ding, J., & Peng, W. (2026) · Journal of King Saud University - Computer and Information Sciences · doi:10.1007/s44443-026-00616-7
Private Statistical Survey Avoiding Privacy Composition in the Real World
小野, 元., オノ, ハ., & Ono, H. (2023) · SOKENDAI (Graduate University for Advanced Studies)
Beyond Epsilon: A Principled QIF Framework for Local Differential Privacy
Gonze, R. G., Fernandes, N., Arcolezi, H. H., Catuscia Palamidessi, A., & Bielova, N. (2026) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf68417.2026.00032
Sparse Estimation Under Local Differential Privacy at All Privacy Levels
Zhao, P., Ye, Q., Wang, S., Feng, J., Yue, S., Chen, Z., & Cao, X. (2026) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp63933.2026.00234 · Cited by 2
Quantum Advantage in Locally Differentially Private Hypothesis Testing
Nam, S.-H., Park, H.-Y., Lee, S.-H., & Bae, J. (2026) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2026.3709807 · Cited by 5
Li, Y., Fu, X., Liu, L., Ding, J., & Peng, W. (2026) · Neurocomputing · doi:10.1016/j.neucom.2026.134639
Khodaie, A., Balioglu, B. K., & Gürsoy, M. E. (2026) · Computers & Security · doi:10.1016/j.cose.2026.105166
Metadata
- Authors
- Ye, M., & Barg, A.
- Affiliations
- University of Maryland, College Park (US)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2018-08
- Volume
- 64
- Issue
- 8
- Pages
- 5662-5676
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2792817205
- Cited by
- 158
- References
- 24
- Citations by year
- 2026: 9 · 2025: 15 · 2024: 15 · 2023: 14 · 2022: 15 · 2021: 28 · 2020: 36 · 2019: 22 · 2018: 2
- FWCI
- 12.32
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (CCF1422955, CCF 1422955, CCF 1618603)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed Sensor Networks and Detection Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Internet Traffic Analysis and Secure E-voting
- Keywords
- discrete distribution estimation, minimax estimation, privacy-utility trade-off, lower bounds, order optimality
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.