Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints
We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor and the sample complexity under communication constraints up to a logarithmic factor. Our upper bounds under LDP are based on the Hadamard Response, a private coin scheme that requires only one bit of communication per user. Under communication constraints, we propose public coin schemes based on random hashing functions. Our tight lower bounds are based on the recently proposed method of chi squared contractions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Compressive Sensing Approaches for Sparse Distribution Estimation Under Local Privacy
Recent years, local differential privacy (LDP) has been adopted by many web service providers like Google \cite{erlingsson2014rappor}, Apple \cite{apple2017privacy} and Microsoft \cite{bolin2017telemetry} to collect and …
Compressive SensingDimensionality ReductionCollaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints
In modern machine learning, users often have to collaborate to learn the distribution of the data. Communication can be a significant bottleneck. Prior work has studied homogeneous users -- i.e., whose data follow the sa…
Estimating Unknown Population Sizes Using the Hypergeometric Distribution
The multivariate hypergeometric distribution describes sampling without replacement from a discrete population of elements divided into multiple categories. Addressing a gap in the literature, we tackle the challenge of …
Collaborative FilteringSuperMix: Sparse Regularization for Mixtures
This paper investigates the statistical estimation of a discrete mixing measure $\mu$0 involved in a kernel mixture model. Using some recent advances in l1-regularization over the space of measures, we introduce a "data …
Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance
We present \emph{Local Moment Matching (LMM)}, a unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance. We construct an efficiently computable estimator that achie…