Optimal locally private estimation under _p loss for 1 p 2

DOI10.1214/19-EJS1625MaRDI QIDQ2326993zbMATH OpenOpenAlexFDO

Authors Min Ye, Alexander Barg

Publication date 11 October 2019

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.07283, https://projecteuclid.org/euclid.ejs/1570586484

zbMATH Keywords

local differential privacyminimax estimation

Mathematics Subject Classification ID

Minimax procedures in statistical decision theory (62C20) Nonparametric estimation (62G05)

Abstract: We consider the minimax estimation problem of a discrete distribution with support size $k$ under locally differential 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 $epsilon$ measures the privacy level of a privatization scheme. In our previous work (IEEE Trans. Inform. Theory, 2018), we proposed a family of new privatization schemes and the corresponding estimator. We also proved that our scheme and estimator are order optimal in the regime $e^{epsilon}llk$ under both $el{l}_2^2$ (mean square) and $el{l}_1$ loss. In this paper, we sharpen this result by showing asymptotic optimality of the proposed scheme under the $el{l}_p^p$ loss for all $1leple2.$ More precisely, we show that for any $pin[1,2]$ and any $k$ and $epsilon,$ the ratio between the worst-case $el{l}_p^p$ estimation loss of our scheme and the optimal value approaches $1$ as the number of samples tends to infinity. The lower bound on the minimax risk of private estimation that we establish as a part of the proof is valid for any loss function $el{l}_p^p,pge1.$

Recommendations

• Minimax Optimal Procedures for Locally Private Estimation
• Geometrizing rates of convergence under local differential privacy constraints
• Local differential privacy: elbow effect in optimal density estimation and adaptation over Besov ellipsoids
• On density estimation at a fixed point under local differential privacy
• Privacy aware learning

Cites work

• Asymptotic methods in statistical decision theory
• Asymptotic Statistics
• Differential Privacy: A Survey of Results
• Distributed private heavy hitters
• Extremal mechanisms for local differential privacy
• scientific article; zbMATH DE number 3733065 (Why is no real title available?)
• scientific article; zbMATH DE number 1220667 (Why is no real title available?)
• scientific article; zbMATH DE number 3441440 (Why is no real title available?)
• Local, private, efficient protocols for succinct histograms
• Minimax Optimal Procedures for Locally Private Estimation
• Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy
• Privacy-preserving statistical estimation with optimal convergence rates
• Randomized response: a survey technique for eliminating evasive answer bias
• Theory of Cryptography
• Universally utility-maximizing privacy mechanisms

Cited in

(8)

• On density estimation at a fixed point under local differential privacy
• Local differential privacy: elbow effect in optimal density estimation and adaptation over Besov ellipsoids
• Geometrizing rates of convergence under local differential privacy constraints
• Minimax Optimal Procedures for Locally Private Estimation
• Comment
• Empirical risk minimization in the non-interactive local model of differential privacy
• scientific article; zbMATH DE number 7415075 (Why is no real title available?)
• The right complexity measure in locally private estimation: it is not the Fisher information

Describes a project that uses

Uses Software

• RAPPOR

This page was built for publication: Optimal locally private estimation under \(\ell_p\) loss for \(1\le p\le 2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2326993)