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
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
“While LDP protocols are effective at enforcing privacy and have theoretical justifications [156, 135, 136], a number of results have shown that achieving local differential privacy while preserving utility is challenging particularly, especially in high-dimensional data settings [229, 388, 219, 51, 220, 424, 142, 111].”
BackgroundCollecting and Analyzing Multidimensional Data with Local Differential Privacy
Wang, N., Xiao, X., Yang, Y., Zhao, J., Hui, S. C., Shin, H., Shin, J., & Yu, G. (2019) · 2019 IEEE 35th International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2019.00063 · Cited by 381
Local differential privacy and its applications: A comprehensive survey
Yang, M., Guo, T., Zhu, T., Tjuawinata, I., Zhao, J., & Lam, K.-Y. (2024) · Computer Standards & Interfaces · doi:10.1016/j.csi.2023.103827 · Cited by 229
Locally Private Graph Neural Networks
Sajadmanesh, S., & Gatica-Perez, D. (2021) · Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3460120.3484565 · Cited by 128
Applications of Differential Privacy in Social Network Analysis: A Survey
Jiang, H., Pei, J., Yu, D., Yu, J., Gong, B., & Cheng, X. (2021) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3073062 · Cited by 193
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy. https://app.cochat.ai/papers/10.1109/tit.2018.2809790
- The paper
- Ye, M., & Barg, A. (2018). Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy. IEEE Transactions on Information Theory. https://doi.org/10.1109/tit.2018.2809790
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.