Source-linked AI summary
Privately Learning High-Dimensional Distributions
Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan Ullman
TL;DR
The paper addresses private learning of high-dimensional Gaussians and Boolean product distributions, where released statistics can expose individual information and existing methods face range or dimensionality costs. It develops computationally efficient learners using recursive private preconditioning, achieving sample complexity comparable to optimal non-private algorithms in broad parameter regimes. For Gaussians, the approach requires only weak a priori bounds on the mean and covariance.
Problem
High-dimensional distribution statistics can reveal individual-specific information, while existing private methods may require strong parameter bounds or incur costly dimensionality dependence.
Method
The paper uses private recursive preconditioning to reduce estimation sensitivity while privately learning multivariate Gaussians and Boolean product distributions in total variation distance.
Results
Privacy comes nearly for free: sample complexity is comparable to that of optimal non-private learners for both distribution classes in broad parameter regimes.
Takeaways & Limitations
The algorithms provide computationally efficient private learning for these high-dimensional distributions without the strong a priori parameter bounds required by previous Gaussian approaches.
Takeaways & Limitations
Lower bounds for covariance estimation under concentrated or approximate differential privacy remain an open question.
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 learning raises privacy risks because released statistics can reveal individual information, while existing private methods often impose burdensome parameter-range or dimensionality costs. This work gives efficient private learners for Gaussians and Boolean product distributions whose sample complexity is comparable to optimal non-private learning in broad parameter regimes.
- High-dimensional released statistics can reveal substantial individual-specific information even when only distribution parameters are published.
- Straightforward private estimation requires strong a priori parameter bounds, while low-dimensional techniques do not extend well to high-dimensional problems.High-dimensional extensions can incur costly dimension dependence or exponential running time.
- Across both distribution classes, the results show that privacy can be obtained nearly for free through private recursive preconditioning.
- The paper privately learns multivariate Gaussians with unknown mean and covariance in total variation distance using only weak a priori bounds.In a wide range of parameters, its sample complexity matches the optimal non-private algorithm up to lower-order terms.
- The paper gives a computationally efficient private learner for Boolean-hypercube product distributions in total variation distance without knowing coordinate variances in advance.Noise added to each coordinate is proportional to its variance, and sample complexity is similar to the optimal non-private algorithm in many parameter regimes.
1.1 Our Results
The paper develops efficient private algorithms for learning multivariate Gaussians and Boolean product distributions in total variation distance, with sample complexity close to optimal non-private learning in broad parameter regimes. Its central technique is recursive private preconditioning, which reduces sensitivity while avoiding strong parameter-range assumptions in Gaussian learning.
- Privately Learning Gaussians: The Gaussian result preserves the mild range dependence and near-non-private sample complexity previously achieved for univariate Gaussians, despite the unknown covariance setting.A naive extension with unknown covariance would preserve neither feature.
- Privately Learning Gaussians: The Gaussian algorithm privately estimates an unknown mean and covariance in total variation distance using only weak a priori bounds, matching optimal non-private sample complexity up to lower-order terms in a wide parameter range.It is polynomial time and achieves the guarantee with high probability.
- Privately Learning Gaussians: The algorithm first learns a matrix A satisfying I ⪯ AΣA ⪯ 1000I, transforming the Gaussian to a nearly spherical distribution for subsequent private estimation.This recursive private preconditioning step approximates the inverse covariance and enables applying univariate Gaussian estimation methods.
- Privately Learning Product Distributions: The product-distribution algorithm avoids the standard ˜Θ(d/(αε)) sample complexity from independently perturbing coordinates and instead uses recursive preconditioning.It adds coordinate noise proportional to variance without requiring the variances to be known beforehand.
- Lower Bounds: The paper proves lower bounds showing that its sample complexities are optimal up to polylogarithmic factors for many considered problems, including private product-distribution mean estimation.It also gives qualitatively similar lower bounds for private Gaussian mean estimation.
- Comparison to Lower Bounds for High-Dimensional DP: The privacy cost disappears for stronger, structure-aware guarantees such as ℓ2 or total-variation-related metrics, but the corresponding range-independent guarantee relies on Gaussian or product-distribution structure.For arbitrary distributions, the Gaussian Σ-norm guarantee cannot generally avoid dependence on the covariance range, while product-distribution mean learning can require ˜O(d) samples instead of Ω(d3/2).
1.2 Techniques
The paper develops recursive private preconditioning to reduce sensitivity when privately estimating multivariate Gaussians and Boolean product distributions. The approach progressively exploits distributional structure so private accuracy approaches non-private accuracy with manageable computation.
- Privately Learning Gaussians: For Gaussian covariance estimation, the empirical covariance has infinite sensitivity because one arbitrary sample can change it without bound.Clamping under prior covariance bounds gives finite sensitivity, but introduces dependence on the covariance range.
- Privately Learning Gaussians: The Gaussian mechanism’s privacy error can depend linearly on the covariance condition parameter, requiring at least Ω(κd^2) samples in the basic approach.This dependence remains tight when Σ = I under the stated analysis.
- Privately Learning Gaussians: Recursive private preconditioning privately finds A such that I ⪯ AΣA ⪯ O(1)I, enabling accurate estimation after transforming the data.The procedure begins with a rough estimate satisfying I ⪯ AΣA ⪯ 7/10κ I and iterates O(log κ) times until the condition number is constant.
- Privately Learning Gaussians: The method uses large-variance directions, which remain informative despite noise, to make multiplicative progress toward a well-conditioned covariance estimate.Low-variance directions may be overwhelmed by noise, but directions observed with sufficiently large variance must also be large in the true covariance.
- Privately Learning Product Distributions: For Boolean product distributions, recursive partitioning groups coordinates by bias and repeatedly re-estimates the remaining coordinates with reduced noise.Coordinates with sufficiently large estimated means are fixed, while the remaining coordinates have a smaller bias range; O(log d) rounds add only polylogarithmic factors.
- Privately Learning Product Distributions: The product-distribution procedure reduces the natural estimator’s sensitivity by clamping samples and achieves the relevant noise scale with n = ˜O(d) samples.The approach addresses the failure of adding coordinatewise Gaussian noise when all means are roughly 1/d.
1.3 Additional Related Work
The paper relates its contributions to private learning, covariance estimation, robust estimation, testing, and privacy attacks. It emphasizes differences in assumptions, distance measures, dimensional dependence, and corruption models.
- Differentially Private Learning and Statistics: Prior private-learning work achieved strong results for low-dimensional statistics and arbitrary distributions, but used weaker distance measures or did not directly cover the high-dimensional settings studied here.The cited results include univariate Gaussian mean estimation and distribution learning in Kolmogorov distance.
- Covariance Estimation: Earlier covariance-estimation algorithms require bounded data norms and have sample complexity polynomially dependent on that bound, whereas these algorithms have mild or no norm dependence.This contrast is stated specifically for the covariance-estimation literature.
- Robust Statistical Estimation on High-Dimensional Data: Differentially private and robust estimation both limit outlier influence, but privacy makes no data assumptions and tolerates O(1/ε) corruptions, while robust estimation assumes a nice distribution and tolerates Ω(n) corruptions.The paper describes the two guarantees as technically incomparable.
- Differentially Private Testing: Private testing research addresses goodness-of-fit, closeness, independence, support size, and entropy, rather than the parameter-learning problems targeted here.The related algorithms are described as essentially optimal for several testing or property-estimation tasks.
- Privacy Attacks and Lower Bounds: Privacy attacks can infer sensitive information from noisy high-dimensional statistics, but the cited attacks require datasets too small to learn the underlying distribution in total variation distance.The attacks apply to product distributions and Gaussians as well as other learning problems.
2 Preliminaries
The preliminaries define differential privacy and concentrated differential privacy, their composition and post-processing properties, the Gaussian mechanism, and the link between parameter estimation and total variation learning.
- Differential Privacy: Differential privacy compares algorithm outputs on neighboring datasets that differ in at most one entry.The standard definition requires output distributions to remain close for every neighboring pair.
- Privacy Definitions: The paper also uses zero-concentrated differential privacy, whose parameters differ in scale from (ε, δ)-DP.Both privacy variants are closed under post-processing.
- Composition: Adaptive composition combines privacy guarantees across algorithms whose later computations may depend on earlier outputs.The paper states linear composition for (ε, δ)-DP and zCDP, while approximate DP can compose sublinearly with increased δ.
- Parameter Estimation to Distribution Estimation: The learning algorithms estimate distribution parameters and then use parameter-to-distribution guarantees to obtain total variation accuracy.For Gaussians, suitable mean and covariance errors imply dTV(N(µ,Σ), N(µ̂,Σ̂)) ≤ O(α).
3 Private Covariance Estimation for Gaussians
The covariance estimator first adds private noise to a truncated empirical covariance, then uses recursive private preconditioning to reduce the condition number before final estimation. The resulting procedure is differentially private and achieves covariance error guarantees under weak conditioning assumptions.
- Baseline covariance estimation: NaivePCE privately perturbs a truncated empirical covariance and projects the result onto the positive semidefinite cone.The approach has nearly optimal dependence on most parameters but initially incurs polynomial dependence on the covariance condition number.
- Baseline covariance estimation: When the covariance condition number is constant, NaivePCE estimates covariance with little overhead compared to non-private estimation.
- Recursive preconditioning: WeakPPC privately constructs a preconditioner that improves the condition number of AΣA by a constant factor.It uses a weak covariance estimate and an eigenspace-based transformation.
- Recursive preconditioning: PPC recursively applies WeakPPC to produce A satisfying I ⪯ AΣA ⪯ 1000I with probability 1 − O(β).
- Final estimator: PGCE combines private preconditioning with covariance estimation to output bΣ satisfying ∥Σ − bΣ∥Σ ≤ O(α) with probability 1 − O(β).The combined algorithm satisfies ρ-zCDP under I ⪯ Σ ⪯ κI.
4 Private Mean Estimation for Gaussians
The paper estimates Gaussian means privately by combining coordinate-wise univariate mean estimation with a private covariance preconditioner. This removes the large-condition-number dependence from the final mean-estimation reduction while retaining explicit accuracy and privacy guarantees.
- Problem setting: The mean-estimation task assumes unknown μ and Σ with ∥μ∥2 ≤ R and I ⪯ Σ ⪯ κI, targeting Mahalanobis error at most α.
- Baseline estimator: Coordinate-wise NaivePME provides a private baseline for bounded-condition-number Gaussians by applying univariate Gaussian mean estimation to each coordinate.
- Baseline estimator: The univariate guarantee requires only an upper bound κ on the variance, but useful accuracy depends on that bound being reasonably tight.
- Preconditioned estimation: Private preconditioning approximates Σ^-1/2, transforming samples so their covariance lies between I and 1000I before mean estimation.
- Final guarantee: PME is 2ρ-zCDP and returns bμ with ∥μ − bμ∥Σ ≤ α with probability at least 1 − 2β.Its sample complexity includes the cost of private preconditioning and the subsequent well-conditioned mean estimator.
5 Privately Learning Product Distributions
The product-distribution learner estimates Boolean marginals through disjoint, truncated blocks whose noise is scaled to coordinate variance. Its partitioning rounds separate accurately estimated coordinates from coordinates with small means, yielding a private total-variation guarantee.
- Problem and algorithm: PPDE learns an unknown product distribution over {0,1}^d and outputs Q with dTV(P,Q) ≤ α.
- Privacy mechanism: Truncated means reduce ℓ2-sensitivity from infinite for the untruncated mean to B/m for a block of m samples.
- Privacy mechanism: Each partitioning round uses a disjoint sample block, so each sample affects only one round and privacy does not require composition across rounds.
- Guarantee: With probability at least 1 − O(β), PPDE outputs Q satisfying dTV(P,Q) ≤ O(α), with polylogarithmic factors hidden in the sample complexity notation.
- Partitioning analysis: Coordinates leaving a partitioning round have small χ2-divergence error, while coordinates continuing to the next round have small true means.
6 Lower Bounds for Private Distribution Estimation
The section establishes lower bounds for private estimation of product and Gaussian distributions, showing that the algorithms’ sample complexities are nearly optimal up to polylogarithmic factors. It uses reductions from parameter estimation to statistical distance and identifies an open question for stronger covariance-estimation lower bounds.
- Overview: Private lower bounds for product and Gaussian distribution estimation nearly match the corresponding upper bounds up to polylogarithmic factors.For mean estimation, the lower bounds apply even under weaker (ε, δ)-differential privacy, while the upper bounds use stronger privacy notions.
- Gaussian distributions: For Gaussian covariance estimation, the lower bound is proved under ε-differential privacy, which is stronger than the concentrated privacy guarantee used for the corresponding upper bound.The section leaves lower bounds for covariance estimation under concentrated or approximate differential privacy as an open question.
- Product distributions: The product-distribution lower bound remains optimal up to polylogarithmic factors even for somewhat balanced marginals.The proof proceeds by lower-bounding the samples needed for mean estimation and showing that total-variation estimation implies mean estimation in ℓ2 distance.
- Product distributions: The product-distribution argument converts a total-variation learner into an ℓ2-accurate mean estimator, contradicting the mean-estimation lower bound when the sample size is too small.The reduction boosts success probability by repeating the algorithm and uses boundedness of the domain to control the resulting expected accuracy.
- Gaussian distributions: For Gaussian mean estimation with known covariance, the lower bound applies to mechanisms achieving total-variation accuracy under approximate differential privacy.The theorem is stated for means in a bounded range and shows that private estimation requires a dimension- and accuracy-dependent sample size.