Research map / Federated learning and privacy / Differential privacy
A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input
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.
Proposes a zCDP recursive algorithm for differentially private second-moment estimation on subsamplable inputs (including distributions with a fraction of outliers), iteratively shrinking tail points and reducing the condition number.
Problem
Differentially private second moment (covariance) estimation for worst-case, ill-conditioned inputs where the range R greatly exceeds the least eigenvalue, including datasets with outliers.
Approach
Assume the dataset is subsamplable (a random subsample preserves the spectrum up to 1±α), then recursively add GUE noise, project down large-eigenvalue directions by a linear shrink Π, and radially shrink tail points, reducing the range by sqrt(3/7) per round until the noise dominates less; this yields a zCDP estimator that works for heavy-tailed and outlier-contaminated distributions with better
Key results
- Baseline subsample-and-aggregate achieves a (1±2α) spectral approximation under (2ε,4e^ε δ)-DP with n = Ω(d·m/(εα)) samples.
- Recursive algorithm is ρ-zCDP and gives (1±γ) approximation of the effective (non-tail) second moment with n = Ω(m·sqrt(d/ρ)(sqrt(T)log(T/ξ)+log(1/ξ)/γ)) samples, T=O(log(R/m)).
- For distributions with η-fraction outliers, tolerates outlier fraction η = O(1/(d log d log(R/λmin))), versus O(γ²/(d log(d/ξ))) for subsample-and-aggregate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use recursive DP second-moment estimation instead of subsample-and-aggregate | Second moment estimation on subsamplable datasets · Subsamplable datasets | spectral approximation factor: 2α -> (1±γ) | Helped |
| Use recursive DP second-moment estimation rather than subsample-and-aggregate | Distributional input with outliers · Distributional input with outliers | sample complexity: \tilde O\left(\frac {d^2\log(d/\beta)}{\epsilon\gamma^3}\right) -> O\left( \frac{d\log(d/\xi)}{\gamma^2} + \frac{d^{3/2} | Helped |
| Allow an outlier fraction η = O(1/(d log(d) log(R/λ_min))) when the outlier second moment is bounded by O(1/η)Σ_D | Recursive DP Second Moment Estimation · Distributional input with outliers | tolerated outlier fraction: η = O(\frac 1 {d \log(d)\log(R/\lambda_{\min})}) | Helped |
Surprising findings
- Outlier fraction tolerated by the proposed method is substantially larger than that of subsample-and-aggregate, at the cost of a dependence on log(R/λmin).
Limitations
- Requires beta = O(alpha/log(R)), which the authors note as an open problem to relax to O(1).
- Requires knowledge of R and lambda_min, estimated via separate private procedures with their own assumptions.
- Analysis relies on sketched proofs in the main text; full details deferred to the appendix.
Experimental setup
Metrics: spectral approximation error (1±γ) sample complexity privacy (zCDP)
Baselines: subsample-and-aggregate baseline (this paper) Brown et al. private covariance estimation
Builds on: Kamath et al. recursive private preconditioning subsample-and-aggregate matrix Bernstein
Closest papers by meaning
- Settling Pure Differentially Private Covariance Estimation (NeurIPS 2026 · similarity 0.89)
- Continual Release Moment Estimation with Differential Privacy (NeurIPS 2025 · similarity 0.87)
- Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy (ICML 2024 · similarity 0.85)
- An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise (NeurIPS 2025 · similarity 0.85)
- Private Continual Counting of Unbounded Streams (NeurIPS 2025 · similarity 0.85)
- Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy (ICLR 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.