Research map / Learning theory and algorithms / Sample complexity
Dimension-free Private Mean Estimation for Anisotropic Distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives dimension-free (eps,delta)-DP mean estimators for anisotropic subgaussian distributions, matching a near-optimal lower bound for known covariance, and a d^{1/4} bound for unknown covariance.
Problem
Differentially private mean estimation in high dimensions suffers a curse of dimensionality (sample size growing as sqrt(d)) even when the data covariance is anisotropic and effectively low-dimensional.
Approach
Replace the coordinate-wise coarse mean pre-processing with FriendlyCore-style filtering on pairwise distances measured by M^{-1/4}, using M = Sigma so that outliers are removed with only ~1/eps samples, then add anisotropic Gaussian noise proportional to Sigma^{1/2}; for unknown covariance, privately learn the top ~eps^2 n^2 variances and handle the rest with spherical noise.
Key results
- Known covariance: (eps,delta)-DP estimator achieves error alpha with n = Õ(tr(Σ)/α² + tr(Σ^{1/2})√log(1/δ)/(αε) + log(1/δ)/ε), dimension-free for effectively low-rank signals.
- Lower bound: any (eps,delta)-DP estimator for Gaussian mean with known covariance needs n = Ω(tr(Σ^{1/2})/(αε log²d)), matching the upper bound's privacy term up to logs.
- Unknown covariance: sample complexity improves dependence on dimension from d^{1/2} to d^{1/4}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use covariance-aware re-scaled filtering and noise instead of dimension-dependent private mean estimation | Known-covariance private mean estimation · Anisotropic subgaussian distributions | sample complexity: n\gtrsim\tr(\Sigma)/\alpha^2+ \tr(\Sigma^{1/2})/(\alpha\eps) | Helped |
| Use covariance-aware re-scaled filtering and noise rather than the folklore estimator | Known-covariance private mean estimation · Anisotropic distributions | sample complexity: n \gtrsim \frac{\tr(\Sigma)}{\alpha^2} + \frac{\sqrt{d}}{\eps} + \frac{\sqrt{d\tr(\Sigma)}}{\alpha\eps} -> n\gtrsim\tr(\ | Helped |
| Use the proposed known-covariance estimator instead of the Aumüller et al. estimator | Known-covariance private mean estimation · Anisotropic distributions | sample complexity: n \gtrsim \frac{\tr(\Sigma)}{\alpha^2} + \frac{\sqrt{d}}{\eps} + \frac{\tr(\Sigma^{1/2})}{\alpha\eps} -> n\gtrsim\tr(\Si | Helped |
| Estimate unknown covariance by identifying large variances and treating the remaining coordinates separately | Unknown-covariance private mean estimation · Gaussian distributions | sample complexity dimension dependence: from d^{1/2} to d^{1/4} | Helped |
| Assume covariance is unknown rather than known | Private mean estimation · Anisotropic Gaussian distributions | sample complexity: n=\tilde{O}\left( \frac{\tr(\Sigma)}{\alpha^2} + \frac{\sum_{i=1}^d \Sigma_{ii}^{1/2}\sqrt{\log(1/\delta)}}{\alpha\eps} | Hurt |
| Exploit exponential decay of diagonal variances and learn only the top k=\log(d) variances | Unknown-covariance private mean estimation · Exponentially decaying diagonal covariance | sample complexity: n=\tilde{O} \left(\frac{\tr(\Sigma)}{\alpha^2} + \frac{\tr(\Sigma^{1/2})\sqrt{\log(1/\delta)} }{\alpha\eps} + \frac{\log | Helped |
| Replace approximate differential privacy with pure differential privacy | Private Gaussian mean estimation · Anisotropic Gaussian distributions | sample complexity dimension dependence: n\geq \frac{d\log(R/2\alpha)}{\eps} | Hurt |
Surprising findings
- Pure eps-DP necessarily requires n on the order of d, so improvements are only possible under (eps,delta)-DP.
Limitations
- Unknown-covariance bound still has d^{1/4} dependence; optimal rate left open.
- Upper bounds mainly stated for Gaussian or subgaussian data with known covariance proxy.
- Pure DP lower bound shows dimension dependence; results depend on (eps,delta) relaxation.
Experimental setup
Metrics: sample complexity estimation error in Euclidean norm
Baselines: folklore coordinate-wise clipping estimator Aumüller et al. estimator Mahalanobis-norm optimal estimators Brown et al. covariance-aware estimator
Builds on: FriendlyCore Aumüller et al. diagonal-covariance DP mean estimation Brown et al. covariance-aware private mean estimation fingerprinting lower bound (Kamath et al.)
Closest papers by meaning
- Covariance-Aware Private Mean Estimation Without Private Covariance Estimation (NeurIPS 2021 · similarity 0.91)
- An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise (NeurIPS 2025 · similarity 0.87)
- On Differentially Private Subspace Estimation in a Distribution-Free Setting (NeurIPS 2024 · similarity 0.87)
- Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.86)
- On Differentially Private U Statistics (NeurIPS 2024 · similarity 0.86)
- Privately Learning Smooth Distributions on the Hypercube by Projections (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.