We propose a general framework for non-interactive locally differentially private (LDP) learning of structured univariate distributions that can be approximated by piece-wise polynomials. This gives the first sample-efficient LDP learners for several distribution classes, including mixtures of log-concave distributions, such as Gaussian mixture models (GMMs). These learners also provide agnostic guarantees and are computationally efficient. We also prove a lower bound for learning GMMs under LDP, improving on the standard pure-DP packing lower bounds of Bun et al. [BKSW19]. To obtain our general learning framework, we develop an efficient non-interactive LDP algorithm for synthetic data generation over large domains, which may be of independent interest. We then use it together with a deterministic adaptation of the non-private piecewise polynomial learner of Acharya et al. [ADLS17].
Figures & tables
Figure 1: For N=4 , the blue nodes C(3)={I1,0,I2,2} partition the prefix [1,3] , using at most one node per depth.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Iℓ,v={v2L−ℓ+1,…,(v+1)2L−ℓ}
Appendix
Algorithm 3 Canonical dyadic decomposition of a prefix