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
Local privacy and statistical minimax rates
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2013.6736718 · Cited by 208
Discrete Distribution Estimation under Local Privacy
Kairouz, P., Bonawitz, K., & Ramage, D. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.07387 · Cited by 197
Extremal mechanisms for local differential privacy
KairouzPeter, OhSewoong, & ViswanathPramod (2016) · Journal of Machine Learning Research · doi:10.5555/2946645.2946662 · Cited by 92
Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.6000 · Cited by 86
On Learning Distributions from their Samples
Kamath, S., Orlitsky, A., Pichapati, D., & Suresh, A. T. (2015) · Conference on Learning Theory · Cited by 67
Mutual Information Optimally Local Private Discrete Distribution Estimation
Wang, S., Huang, L., Wang, P., Nie, Y., Xu, H., Yang, W., Li, X., & Qiao, C. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1607.08025 · Cited by 58
Optimal schemes for discrete distribution estimation under local differential privacy
Ye, M., & Barg, A. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8006630 · Cited by 29
Self-citationLocally differentially-private distribution estimation
Pastore, A., & Gastpar, M. (2016) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2016.7541788 · Cited by 17
Asymptotically optimal private estimation under mean square lossPreprint
Ye, M., & Barg, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1708.00059 · Cited by 12
Self-citationAcharya, J., Sun, Z., & Zhang, H. (2018) · arXiv (Cornell University) · Cited by 10
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
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.