TL;DR
This paper proves that "dimension-free" error rates for differentially private mean estimation are impossible if the data's covariance is unknown. While prior work showed that knowing the data's shape allows for error independent of the ambient dimension $d$, these new lower bounds demonstrate that private estimators must pay a dimension-dependent price to "discover" that structure.
What Problem Does This Paper Address?
Gaussian mean estimation—estimating the average of a population given a set of samples—is a cornerstone of statistics and machine learning. In the context of Differential Privacy (DP), we want to perform this estimation while ensuring that no single individual's data can be identified from the result.
A major challenge in high-dimensional settings (where the dimension $d$ is large) is that the noise required for privacy often scales with $d$, ruining accuracy. However, real-world data is often "anisotropic"—it has structure, living mostly in a low-dimensional subspace or having very different variances across coordinates. Recent research (specifically [DJYZZ24]) showed a remarkable result: if the covariance matrix $\Sigma$ (the "shape" of the data) is known, private mean estimation can be dimension-free. The error depends only on the intrinsic geometry of the data, not the ambient dimension $d$.
The authors of this paper ask a fundamental follow-up: Is this dimension-free magic still possible if we don't know the covariance beforehand?
Methods
The authors establish theoretical lower bounds using a technique called reduction to membership inference. They prove that if a private algorithm were "too good" at mean estimation without knowing the covariance, it would inadvertently leak information about the specific individuals in the dataset.
Key technical components include:
- Reductions to Auxiliary Tasks: They show that an accurate mean estimator can be transformed into an algorithm that solves simpler but related problems:
- Subspace Estimation (General Covariance): Identifying the low-dimensional subspace where the data resides.
- Top-$k$ Selection (Diagonal Covariance): Identifying which coordinates have the largest variances.
- Fingerprinting/Tracing Attacks: They construct sophisticated membership inference attacks (specifically "tracing attacks") for these auxiliary tasks. By showing these tasks are hard to solve privately, they prove by extension that the original mean estimation problem must also be hard.
- Hard Priors: They design specific mathematical distributions (priors) for the mean and covariance that are particularly difficult for private algorithms to handle, such as variances drawn from heavy-tailed inverse chi-squared distributions.
Datasets
As a theoretical work focused on proving fundamental limits (lower bounds), this paper does not use real-world datasets. Instead, it defines and analyzes performance over specific families of synthetic Gaussian distributions:
- Random rank-$k$ orthogonal projectors: Used to model data that exists in a hidden $k$-dimensional subspace.
- Inverse chi-squared diagonal priors: Used to model data where variances are coordinate-aligned but follow a pathological, heavy-tailed distribution.
Key Insights and Ideas
- The "Cost of Ignorance": The primary insight is that in the private setting, not knowing the covariance isn't just a computational hurdle—it's a fundamental statistical barrier. You cannot exploit the "skinny" directions of your data distribution without first spending samples to find them, and doing so privately is expensive.
- Subspace Learning is the Bottleneck: For general covariance, the "obstruction" is subspace estimation. A private algorithm cannot take advantage of low-dimensional structure until it has seen enough samples to essentially learn every direction in the span of the covariance.
- Anisotropy is a Double-Edged Sword: While anisotropy (uneven variance) helps in the non-private or known-covariance settings, it makes private estimation harder when unknown because the algorithm must distinguish high-variance "signal" directions from the noise added for privacy.
Key Results
The paper establishes that the error in the unknown covariance setting is significantly larger than in the known covariance setting. The "blowup" factors are summarized in the following table:
Specifically:
- General Covariance: When the sample size $n$ is small, the error is larger by a factor of $\approx \sqrt{d/n}$.
- Diagonal Covariance: Even with the promise that the covariance is diagonal, the error is larger by a factor of $\approx \sqrt{d}/n^{1.5}$.
- Mahalanobis Error: The authors show that private mean estimation with finite Mahalanobis error (where error is normalized by variance in each direction) is impossible if the number of samples $n$ is less than $d-2$.
The following table compares these new lower bounds with existing upper bounds, showing they are tight up to logarithmic factors:
Limitations and Future Work
- Tightness of Diagonal Bounds: While the bounds for general covariance are quite tight, there is still a small gap in the diagonal case (specifically regarding the $n^{1.5}$ vs $n^2$ terms in the denominator of the error).
- Beyond Gaussians: The current work focuses strictly on Gaussian distributions. Extending these impossibility results to broader classes of distributions (e.g., sub-Gaussian or heavy-tailed) is a natural next step.
- Pure vs. Approximate DP: The results primarily target $(\epsilon, \delta)$-approximate differential privacy. Exploring how these limits change under "pure" $\epsilon$-DP or other privacy definitions could yield further insights.
Summary updated