Source-linked AI summary
Privately Learning High-Dimensional Distributions
Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan Ullman
TL;DR
High-dimensional distribution learning can expose sensitive individual information, motivating private algorithms for estimating multivariate Gaussians and Boolean product distributions. This paper uses recursive private preconditioning and shows that privacy can come nearly for free, with sample complexity comparable to optimal non-private learning in many parameter regimes.
Problem
High-dimensional distribution estimates can reveal sensitive individual information, while empirical covariance estimation has infinite sensitivity without prior parameter bounds.
Source: §1 · p. 3, §1.2.1 · p. 7Method
The paper develops computationally efficient private learners for multivariate Gaussians and Boolean product distributions using recursive private preconditioning to reduce estimation sensitivity.
Source: §1 · pp. 3–4Results
The algorithms have sample complexity comparable to optimal non-private learners in a wide range of parameters, with Gaussian learning requiring only weak a priori bounds.
Source: §1 · pp. 3–4Takeaways & Limitations
The results show that privacy can come nearly for free when learning these important high-dimensional distribution classes.
Source: §1 · p. 4Proving lower bounds for covariance estimation under concentrated or approximate differential privacy remains an open question.
Source: §6 · p. 32
Abstract
from arXiv · showhide
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.
1 Introduction
High-dimensional distribution parameters can reveal sensitive individual information, while straightforward private estimation may require strong parameter-range bounds. This work develops efficient private learners for Gaussians and Boolean product distributions whose sample complexity nearly matches non-private optimal rates.
Motivation
- High-dimensional released statistics can reveal individual-specific information, making privacy-preserving distribution learning crucial.The paper cites attacks showing that statistical releases can reveal individuals’ presence and associated medical conditions.Source: §1 · p. 3
Challenges
- Straightforward noise addition can require strong a priori parameter bounds and incur costly dependence on the parameter range.For a Gaussian mean in (−R, R), naive private estimation adds variance O(R^2/n^2), requiring Ω(R^2) samples before data variance dominates.Source: §1 · p. 3
- Existing low-dimensional techniques do not extend well to high dimensions, either increasing sample complexity substantially or requiring exponential running time.Methods such as smooth sensitivity, subsample-and-aggregate, and propose-test-release address related problems in lower-dimensional settings.Source: §1 · p. 3
Contributions
- The work gives an efficient private learner for multivariate Gaussians with unknown mean and covariance whose sample complexity matches the optimal non-private rate up to lower-order terms in many regimes.The Gaussian learner operates in total variation distance and needs only weak a priori bounds on the mean and covariance.Source: §1 · p. 3
- The work also privately learns Boolean product distributions efficiently, adding variance-proportional coordinate noise without knowing variances a priori and achieving similar sample complexity in many regimes.Both results use private recursive preconditioning to reduce estimation sensitivity, making privacy nearly free for these distribution families.Source: §1 · p. 4
1.1 Our Results
The paper gives private, computationally efficient learners for high-dimensional Gaussians and product distributions, with sample complexity nearly matching non-private methods in broad parameter regimes. It also proves lower bounds and explains why these guarantees avoid standard high-dimensional privacy barriers.
1.1.1 Privately Learning Gaussians
- For Gaussians, a polynomial-time zCDP algorithm privately estimates unknown mean and covariance in total variation distance, with privacy nearly free except when 1/ε, κ, or R are large.The guarantees assume ||μ||_2 ≤ R and I ⪯ Σ ⪯ κI, and hold with high probability.Source: §1.1.1 · p. 4
- The Gaussian method uses recursive private preconditioning to learn A with I ⪯ AΣA ⪯ 1000I, making the distribution nearly spherical before applying univariate techniques.This addresses the main difficulty of extending private Gaussian estimation when the covariance is almost completely unknown.Source: §1.1.1 · pp. 4–5
1.1.2 Privately Learning Product Distributions
- For product distributions over {0,1}^d, a zCDP learner achieves total variation error α while avoiding the ˜Θ(d/(αε)) blowup of independently perturbing coordinates.The algorithm uses a recursive preconditioning technique distinct from Gaussian covariance estimation, demonstrating the approach’s versatility.Source: §1.1.2 · p. 5
1.1.3 Lower Bounds
- The lower bounds show that many sample complexities are optimal up to polylogarithmic factors, while Gaussian covariance lower bounds remain weaker because they apply only to ε-differential privacy.The dependence on R is optimal up to logarithmic factors, and the stronger dependence on κ is necessary for dimensions d ≥ 2.Source: §1.1.3 · pp. 5–6
1.1.4 Comparison to Lower Bounds for High-Dimensional DP
- The results do not contradict costly high-dimensional DP lower bounds because they use stronger metrics and exploit Gaussian and product-distribution structure rather than arbitrary-distribution guarantees.For Gaussians the relevant metric is Mahalanobis distance, while product-distribution guarantees are closely related to χ2-divergence; analogous guarantees can require more samples for arbitrary distributions.Source: §1.1.4 · pp. 6–7
1.2 Techniques
The techniques for both Gaussian and Boolean product-distribution learning recursively reduce the natural estimator’s sensitivity rather than relying on a single worst-case noise calibration. For Gaussians, private preconditioning drives the covariance condition number toward a constant; for product distributions, iterative coordinate partitioning reduces bias and enables tighter clamping.
1.2.1 Privately Learning Gaussians
- The Gaussian mechanism’s global-sensitivity approach can require Ω(κd^2) samples, because unbounded samples force clamping whose sensitivity scales linearly with the covariance bound κ.Without such prior bounds, empirical covariance has infinite sensitivity; truncation nevertheless preserves privacy for arbitrary datasets.Source: §1.2.1 · pp. 7–8
- Recursive private preconditioning transforms Gaussian samples so the covariance is well-conditioned, allowing the Gaussian mechanism to learn the transformed distribution with ˜O(d^2) samples.The preconditioner is found recursively: each iteration reduces the covariance condition number, and O(log κ) iterations suffice to reach a constant condition number.Source: §1.2.1 · p. 8
- The recursive Gaussian procedure uses noisy covariance eigendirections to identify reliably large-variance directions and clamp more aggressively in low-variance directions, reducing maximum variance more than minimum variance.This yields a preconditioner A with I ⪯ AΣA ⪯ 7/10κI, which can be iterated toward constant conditioning.Source: §1.2.1 · p. 8
1.2.2 Privately Learning Product Distributions
- For Boolean product distributions, recursive sensitivity reduction addresses the Gaussian mechanism’s failure when coordinate means are near 1/d, where its noise is too large for the target total-variation accuracy.When means are roughly balanced, O(d) samples suffice, while highly biased coordinates can be clamped to reduce sensitivity to O(log d/n).Source: §1.2.2 · p. 9
- The product-distribution algorithm privately partitions coordinates by estimated bias, locks in sufficiently balanced estimates, and recursively restricts and reclamps the remaining coordinates, requiring O(log d) rounds with only polylogarithmic overhead.At each round, coordinates with estimated mean at least 1/4 are retained, while the remaining coordinates have a reduced bias bound and can be estimated with less noise.Source: §1.2.2 · p. 9
1.3 Additional Related Work
This section situates the paper among private learning, covariance estimation, robust estimation, testing, and privacy-attack research. It emphasizes the paper’s advantages over prior methods in parameter assumptions and dimensional dependence, while distinguishing privacy from robustness and tracing limitations.
Differentially Private Learning and Statistics
- Prior private-learning work covers low-dimensional statistics, arbitrary distributions in Kolmogorov distance, and structured one-dimensional distributions in total variation.Smith estimates asymptotically normal statistics efficiently, but does not apply to covariance estimation or sparse product distributions and learns high-dimensional distributions coordinate by coordinate.Source: §1.3 · p. 10
- Cai, Wang, and Zhang [CWZ19] study private subgaussian mean and covariance estimation under strong parameter bounds, with a lower bound quantitatively larger by log1/2(1/δ) but applying to a broader non-product class.Their reduction from does not preserve Gaussian or product-distribution structure, making the lower bound incomparable to Theorems 6.1 and 6.5.Source: §1.3 · p. 10
Covariance Estimation
- Unlike covariance-estimation methods requiring bounded data norms and polynomial dependence on those bounds, this paper’s algorithms have mild or no norm dependence.Source: §1.3 · p. 10
Robust Statistical Estimation on High-Dimensional Data
- Differential privacy and robust estimation both limit outlier influence, but privacy makes no data assumptions and tolerates O(1/ε) corruptions, whereas robustness assumes a nice distribution and tolerates Ω(n).Source: §1.3 · p. 10
Differentially Private Testing
- Private testing work addresses goodness-of-fit, closeness, independence, support size, and entropy, but arbitrary-distribution testing has sample complexity exponential in dimension.The cited works include [WLK15],,, and local-privacy studies.Source: §1.3 · p. 10
Privacy Attacks and Lower Bounds
- Tracing attacks can target product distributions and Gaussians, but require datasets too small to learn the distribution in total variation and therefore do not contradict these results.Related attacks concern PCA, ERM, and variable selection, while other attacks yield computational hardness results.Source: §1.3 · p. 11
2 Preliminaries
This section defines the differential privacy variants and establishes their post-processing and composition properties. It also introduces the Gaussian mechanism and explains how parameter accuracy yields total-variation guarantees for product and Gaussian distributions.
Privacy definitions
- Differential privacy requires neighboring datasets to induce close output distributions, with standard (ε, δ)-DP and ρ-zCDP as variants.Qualitatively, DP with δ = 0 is stronger than zCDP, which is stronger than DP with δ > 0.Source: §2 · p. 11
Privacy properties
- Both DP variants are closed under post-processing, and adaptive compositions remain private under standard, advanced, and zCDP composition rules.The parameters add linearly for standard DP and zCDP, while ε grows roughly with the square root of the number of steps for bounded-ε composition with a small δ increase.Source: §2 · pp. 11–12
The Gaussian Mechanism
- The Gaussian mechanism provides differential privacy by adding noise calibrated to a function’s ℓ2-sensitivity, with Gaussian tail bounds supporting its accuracy analysis.The section defines ℓ2-sensitivity and states the Gaussian mechanism lemma, then invokes standard tails for Z ∼ N(0, σ^2).Source: §2 · p. 12
Parameter Estimation to Distribution Estimation
- The algorithms obtain total-variation guarantees by estimating distribution parameters, using chi-squared accuracy for product distributions and covariance-relative norms for Gaussian parameters.For Gaussians, if mean and covariance errors are each at most α in the specified Σ-relative norms, total variation is O(α) for sufficiently small α.Source: §2 · p. 13
3 Private Covariance Estimation for Gaussians
The section develops a private covariance estimator for Gaussians by recursively preconditioning the covariance to constant condition number, then applying a noisy covariance estimator. The resulting algorithm is ρ-zCDP and achieves normalized Frobenius error O(α) with probability 1−O(β).
3 Private Covariance Estimation for Gaussians
- The section targets private estimation of an unknown Gaussian covariance under I ⪯Σ ⪯κI using the normalized error norm ∥A∥_Σ=∥Σ^−1/2AΣ^−1/2∥_F.The estimator must privately output an approximation bΣ to Σ.Source: §3 · p. 13
3.1 Useful Concentration Inequalities
- The analysis uses random-matrix concentration, Hanson-Wright quadratic-form bounds, and Gaussian tail bounds for independent samples.These facts control spectral and quadratic-form deviations arising in the noisy covariance and preconditioning analyses.Source: §3.1 · pp. 13–14
3.2 Deterministic Regularity Conditions
- Gaussian samples satisfy deterministic regularity conditions with probability 1−O(β), and these conditions yield algebraic consequences used to analyze covariance estimates after preconditioning.The regularity framework assumes I ⪯Σ ⪯κI and standardizes samples as Y_i=Σ^−1/2X_i.Source: §3.2 · p. 14
3.3 A Simple Algorithm for Well Conditioned Gaussians
- NaivePCE truncates large-norm samples, computes empirical covariance, adds Gaussian-matrix noise, and projects onto the PSD cone, but its error has polynomial dependence on κ.For constant κ, it privately estimates covariance with little overhead compared with non-private estimation.Source: §3.3 · pp. 14–15, §3.4 · p. 16
3.4.1 Reducing the Condition Number by a Constant
- WeakPPC privately constructs a preconditioner that improves the condition number of AΣA by a constant factor, enabling recursive reduction from the initial condition number.The procedure uses a weak NaivePCE estimate and satisfies ρ-zCDP with probability 1−O(β).Source: §3.4.1 · pp. 16–17
3.4.2 Recursive Preconditioning
- Recursive preconditioning outputs A satisfying I ⪯AΣA ⪯1000I with probability 1−O(β), while preserving ρ-zCDP.The construction applies the condition-number reduction primitive for O(log κ) rounds.Source: §3.4.2 · p. 19
3.5 Putting It All Together
- The complete PGCE algorithm privately preconditions samples and then applies NaivePCE, achieving ∥Σ − bΣ∥_Σ ≤O(α) with probability 1−O(β) under I ⪯Σ ⪯κI.It satisfies ρ-zCDP and combines the preconditioner with constant-condition-number covariance estimation.Source: §3.5 · p. 20
4 Private Mean Estimation for Gaussians
This section develops differentially private Gaussian mean estimation under Mahalanobis error, first coordinate-wise for well-conditioned covariances and then for general covariances using private preconditioning. The general algorithm achieves privacy and accuracy guarantees without introducing κ dependence into the stated error guarantee.
4 Private Mean Estimation for Gaussians
- The target is estimating an unknown mean with ||µ||2 ≤ R when I ⪯ Σ ⪯ κI, while coordinate-wise estimation requires a reasonably tight upper bound κ on the variance.If Σ is known, whitening removes κ dependence; private preconditioning approximates this reduction when Σ is unknown.Source: §4 · pp. 20–21, §4.1 · p. 21, §4.2 · p. 22
4.1 Mean Estimation for Well-Conditioned Gaussians
- For multivariate Gaussian samples with ∥µ∥2 ≤ R and I ⪯ Σ ⪯ κI, NaivePME is ρ-zCDP and estimates µ with Mahalanobis error at most α with probability at least 1−β.Source: §4.1 · p. 21
4.2 An Algorithm for General Gaussians
- Private preconditioning reduces general Gaussian mean estimation to the well-conditioned case, yielding a 2ρ-zCDP estimate with Mahalanobis error at most α and success probability at least 1−2β.The preconditioner produces A with I ⪯ AΣA ⪯ 1000I, after which NaivePME estimates Aµ and transforms the result back.Source: §4.2 · pp. 22–23
5 Privately Learning Product Distributions
This section presents and analyzes PPDE, a private estimator for product distributions on {0,1}^d, using recursive partitioning and a final estimation round. It establishes an O(α) total variation error guarantee with high probability, including a version without the coordinate-wise mean bound at constant-factor sample cost.
5 Privately Learning Product Distributions
- The algorithm assumes each marginal mean is at most 1/2, an assumption that can be removed while increasing sample complexity by only a constant factor.Source: §5 · p. 23
5.1 A Private Product-Distribution Estimator
- The estimator privately releases truncated means with ℓ2-sensitivity B/m, using disjoint sample blocks so privacy does not require composition.Privacy follows from the Gaussian mechanism and the bounded sensitivity of the truncated mean.Source: §5.1 · pp. 23–24
5.2 Accuracy Analysis for PPDE
- PPDE outputs a product distribution Q with dTV(P, Q) ≤ O(α) with probability at least 1 − O(β) under the sample-size condition of Theorem 5.2.The theorem applies to every product distribution over {0,1}^d and hides polylogarithmic factors in d and the accuracy and confidence parameters.Source: §5.2 · pp. 24–25
5.2.1 Analysis of the Partitioning Rounds
- During partitioning, coordinates fixed by a round have small χ2-divergence error, whereas coordinates carried forward have small true means.These two properties hold simultaneously in every partitioning round with probability at least 1 − O(β).Source: §5.2.1 · p. 26
5.2.2 Analysis of the Final Round
- In the final round, the restricted product distribution on the remaining coordinates is learned within O(α) total variation distance with probability at least 1 − O(β).The final-round analysis assumes the remaining marginals are bounded by u_r and that u_r|S_r| ≤ 1.Source: §5.2.2 · p. 29
- Combining Claims 5.20 and 5.21 with Lemma 5.4 completes the final-round analysis.Source: §5.2.2 · p. 31
5.2.3 Putting it Together
- With probability at least 1−O(β), coordinates not set during partitioning satisfy p[j] ≤ u_r in the final round.Source: §5.2.3 · p. 31
- With probability at least 1−O(β), the final-round coordinates SF satisfy dTV(P[SF], Q[SF]) ≤ O(α).Source: §5.2.3 · p. 31
- A union bound and Lemma 5.4 yield dTV(P, Q) = O(α) with probability at least 1−O(β).Source: §5.2.3 · p. 31
6 Lower Bounds for Private Distribution Estimation
This section establishes privacy lower bounds for distribution estimation, covering product distributions and Gaussian mean and covariance estimation. It develops techniques for known and unknown covariance, including a reduction from total-variation estimation to inverse-covariance estimation.
6 Lower Bounds for Private Distribution Estimation
- The lower bounds nearly match the upper bounds: mean estimation is shown under weaker (ε, δ)-DP, while Gaussian covariance estimation uses ε-DP against an ε^2-zCDP upper bound.Proving covariance lower bounds under concentrated or approximate differential privacy remains an open question.Source: §6 · p. 32
6.1 Privately Learning Product Distributions
- The product-distribution learner has optimal sample complexity up to polylogarithmic factors, even for somewhat balanced marginals and under (ε, δ)-DP.The proof reduces total-variation estimation to ℓ2 mean estimation and uses a fingerprinting-based lower bound.Source: §6.1 · pp. 32, 35
6.2 Privately Learning Gaussian Distributions with Known Covariance
- For Gaussians with known covariance, any (ε, δ)-DP learner estimating total variation to accuracy α requires a sample lower bound depending on dimension, privacy, accuracy, covariance scale, and mean range.The argument reduces total-variation estimation to ℓ2 mean estimation and adapts the product-distribution proof to unbounded Gaussian data.Source: §6.2 · pp. 37–38
- For known covariance, the analysis handles the unbounded Gaussian support by privately estimating the statistic only on [0,T] and separately bounding the tail on (T,∞).The statistic is split into positive and negative parts, with Gaussian-tail bounds controlling the non-private region.Source: §6.2 · pp. 40–41
6.3 Privately Learning Gaussian Distributions with Unknown Covariance
- For unknown covariance, the lower-bound proof targets inverse-covariance estimation because failing in Frobenius norm implies failure in total variation by Theorem 6.10 of [DMR18].The argument adapts the covariance lower-bound construction to inverse covariances and uses a construction with Frobenius diameter Θ(α), avoiding an O(log d) loss.Source: §6.3 · p. 42
- n ≥ Ω(d^2/(αε)) samples are required to privately estimate an unknown-covariance Gaussian to total-variation accuracy α under the stated constant-α condition.The proof combines a constant lower bound on one probability with an exp(O(αεn) − Ω(d^2)) upper bound, forcing the stated sample complexity.Source: §6.3 · pp. 42, 45