Privately Learning High-Dimensional Distributions

By Gautam Kamath, Jerry Zheng Li, Vikrant Singhal, Jonathan Ullman. 2018

176 citations recorded by the source corpus.

We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian and learning a product distribution over the Boolean hypercube in total variation distance. The sample complexity of our algorithms nearly matches the sample complexity of the optimal non-private learners for these tasks in a wide range of parameters, showing that privacy comes essentially for free for these problems. In particular, in contrast to previous approaches, our algorithm for learning Gaussians does not require strong a priori bounds on the range of the parameters. Our algorithms introduce a novel technical approach to reducing the sensitivity of the estimation procedure that we call recursive private preconditioning.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Learning discrete distributions: user vs item-level privacy (2020, background): “…to various statistical and learning scenarios including learning histograms [Dwork et al., 2006], statistical estimation [Diakonikolas et al., 2015, Kamath et al., 2019, Acharya et al., 2020, Kamath et al., 2020, Acharya et al., 2019a,b], learning machine learning models [Chaudhuri et al., 2011,…”
The Power of the Hybrid Model for Mean Estimation (2018, background): “However, DP mean estimation of distributions under both the TCM and LM has been studied since the models’ introductions [17, 21, 56], and continues to be actively studied to this day [2, 15, 18, 20, 22, 28, 29, 32, 37, 39–42].”
Measuring Forgetting of Memorized Training Examples (2022, methodology): “The analysis in the remainder of this section will use the mean estimation task, a simple task which is frequently used in the theoretical privacy literature to understand the effectiveness of privacy attacks [31, 66, 19] or design differentially private algorithms [6, 40].”
INSPECTRE: Privately Estimating the Unseen (2018, background): “There has also been study on private distribution learning (Diakonikolas et al., 2015; Duchi et al., 2017; Karwa & Vadhan, 2018; Acharya et al., 2018; Kamath et al., 2018), in which we wish to estimate parameters of the distribution, rather than just a particular property of interest.”
Differentially Private Assouad, Fano, and Le Cam (2020, methodology): “6 in Kamath et al. (2019), there exists a constant C1 such that for any pair i 6= j ∈ [h], dTV (pi, pj) ≥ C1α.”
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation (2019, background): “Kamath, Li, Singhal, and Ullman [KLSU19] provide algorithms for learning multivariate Gaussians (extending the work of Karwa and Vadhan).”
Locally Private Gaussian Estimation (2018, background): “Karwa and Vadhan [20] and Kamath et al. [19] consider similar versions of Gaussian estimation under global differential privacy, respectively in the one-dimensional and high-dimensional cases.”
Private Hypothesis Selection (2019, methodology): “…long as Similar to the product distribution case, these are the ﬁrst ˜ O ( d ) and ˜ O ( d 2 ) sample algorithms for learning Gaussians total variation distance under pure diﬀerential privacy, improving upon the concentrated diﬀerential privacy results of Kamath, Li, Singhal, and Ullman [KLSU19].”
Private Mean Estimation of Heavy-Tailed Distributions (2020, background): “ties [BUV14, SU15, DSS+15]. It appears that these qualitative gaps may or may not arise depending on the choice of norm and the assumptions we put on the underlying distribution (see Section 1.1.4 of [KLSU19] and Remark 6.4 of [BKSW19]) for more discussion. We point out that the estimator of Theorem”
CoinPress: Practical Private Mean and Covariance Estimation (2020, unknown): “Later works studied the multivariate setting [24, 9, 25] and estimation under weaker moment assumptions [7, 26], though these investigations are primarily theoretical.”