Research map / Federated learning and privacy / Differential privacy
Private Statistical Estimation via Truncation
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 an efficient (epsilon, delta)-DP estimator for unbounded exponential family parameters by truncating data to a bounded survival set, then running DP-SGD on the truncated empirical negative log-likelihood, with specializations to Gaussian mean and covariance estimation.
Problem
Differentially private parameter estimation for exponential families over unbounded data supports (e.g., R^d), where sensitivity of estimators is hard to bound and prior methods were limited to bounded or one-dimensional families.
Approach
Truncate samples to a bounded survival set so sensitivity is controlled, correct the truncation bias by minimizing the truncated negative log-likelihood with DP-SGD over a projection set that ensures strong convexity, and use a uniform convergence result on the empirical NLL (PL condition) to avoid multi-pass issues.
Key results
- Gaussian mean estimation with (epsilon,delta)-DP achieves sample complexity d log(1/(beta delta))/epsilon + d log(1/beta)/alpha^2 + d log(1/(beta delta))/(alpha epsilon), matching known optimal rates up to log factors.
- Exponential family estimator has sample complexity linear in m with 1/alpha^2 and 1/(alpha epsilon) dependence, improving uniform convergence from O(1/alpha^4) to O(1/alpha^2) samples.
- Gaussian covariance estimation achieves d^2 scaling in sample complexity with 1/alpha^2 and 1/(alpha epsilon) terms, matching optimal rates up to log factors, in polynomial time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use truncation-based estimation for unbounded high-dimensional exponential families | DP statistical estimation · Unbounded high-dimensional exponential families | computational efficiency | Helped |
Limitations
- Exponential dependence on the condition parameter lambda (e^{O(1/lambda^2)}) inherited from truncated statistics anti-concentration arguments.
- Requires assumptions (bounded condition number, interiority, log-concavity, polynomial sufficient statistics) and computational oracles (projection, sampling, moment matching).
- Results are theoretical; no experiments are reported.
Experimental setup
Metrics: sample complexity parameter estimation error
Baselines: Kamath et al. 2019 (exponential-time DP Gaussian estimation) Kamath et al. 2019 uniform convergence for exponential families (O(1/alpha^4) sa
Builds on: DP-SGD truncated statistics (Gaussian estimation from truncated samples) private Gaussian covariance estimation (Kamath et al.) recursive Gaussian preconditioning
Closest papers by meaning
- On Inherent Privacy of Posterior Sampling: A Unified R\'enyi-Divergence Framework (NeurIPS 2026 · similarity 0.88)
- Tuning-free Estimation and Inference of Cumulative Distribution Function under Local Differential Privacy (ICML 2024 · similarity 0.87)
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.87)
- Analysis of Differentially Private Synthetic Data: A Measurement Error Approach (AAAI 2024 · similarity 0.87)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.86)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.86)
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.