Research map / Learning theory and algorithms / Sample complexity
On Differentially Private Subspace Estimation in a Distribution-Free Setting
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 measures of dataset "easiness" for differentially private subspace estimation based on multiplicative singular-value gaps, with matching-style upper and lower sample-complexity bounds independent of dimension in some regimes.
Problem
Differentially private subspace estimation (top-k subspace of unit-norm data) suffers polynomial dependence on the ambient dimension in worst case; it is unclear how to quantify when a dataset is "easy" enough to avoid this dependence.
Approach
Defines weak and strong subspace estimators whose utility guarantees depend on multiplicative singular-value gaps in the input dataset (sqrt of tail energy over sigma_k, or sigma_{k+1}/sigma_k), realized via sample-and-aggregate over random subsets with FriendlyCore aggregation, and proves lower bounds via fingerprinting codes with padding-and-permuting.
Key results
- Weak estimator upper bound n = Õ(k + min{k^2 sqrt(d), kd}/λ) and strong estimator upper bound n = Õ(k + k^3 d/λ^2), both (ε,δ)-DP.
- Matching-style lower bounds Ω̃(sqrt(kd)/λ) for weak and Ω̃(k sqrt(d)/λ) for strong estimators under (1, 1/(50nk))-DP.
- For 0.001-useful rank-k projections, dimension-independent sample size requires strong gap σ_{k+1}/σ_k ∝ 1/sqrt(d) for small k.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the weak multiplicative singular-value gap to quantify dataset easiness | Private weak subspace estimation · Weak subspace estimation | sample complexity n: $\tilde{O}_{\varepsilon,\delta}\paren{k + \frac{k^2 \sqrt{d}}{\lambda}}$ | Helped |
| Use the strong multiplicative singular-value gap to quantify dataset easiness | Private strong subspace estimation · Strong subspace estimation | sample complexity n: $\widetilde{O}_{\varepsilon,\delta}\paren{k + \frac{k^3 d}{\lambda^2}}$ | Helped |
| Use multiplicative singular-value gaps in the input dataset rather than an additive-gap measure | Private subspace estimation · High-dimensional regimes | sample complexity dependence on dimension | Helped |
| Use the weak-gap condition instead of the strong-gap condition | Private subspace estimation · Subspace estimation | sample complexity n: $\tilde{O}_{\varepsilon,\delta}\paren{k + \frac{k^2 \sqrt{d}}{\lambda}}$; $\widetilde{O}_{\varepsilon,\delta}\paren{k + | Mixed |
Limitations
- Gap of about k^1.5 between weak upper and lower bounds remains open.
- Strong estimator upper bound only holds for gamma restricted to roughly k^{-2/3} d^{-1/3} and does not match lower bound.
- Requires data to be very close to a k-dimensional structure to be effective, which may not hold for typical deep learning gradients.
Experimental setup
Metrics: projection usefulness (Frobenius) mean estimation error
Baselines: additive-gap subspace recovery (Dwork et al.) Gaussian noise on covariance (noisy PCA)
Builds on: FriendlyCore sample-and-aggregate fingerprinting codes lower bound framework Dwork et al. private subspace recovery (additive gap)
Closest papers by meaning
- Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.87)
- Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation (ICML 2024 · similarity 0.87)
- Dimension-free Private Mean Estimation for Anisotropic Distributions (NeurIPS 2024 · similarity 0.87)
- An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise (NeurIPS 2025 · similarity 0.86)
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.86)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 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.