Research map / Learning theory and algorithms / Sample complexity
Profile Reconstruction from Private Sketches
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.
Reconstructs a profile (fraction of items appearing exactly t times) from a discrete-Laplace-privatized histogram by inverting the noise via a circulant linear system, giving an O(d + n log n) algorithm with error O(1/sqrt(d)) and a matching updatable-sketch lower bound.
Problem
Estimating the profile (frequency-of-frequencies) of a multiset under differential privacy, in a distributed, updatable, space-constrained sketch setting.
Approach
Publish a discrete-Laplace-noised histogram, then invert the expected noise transform, which is a circulant matrix, using FFT-based solves; a fast rounding procedure enforces that the result is a valid profile (entries in [0,1], summing to 1). The LP of prior work is reduced to a near-linear-time l_p regression.
Key results
- Algorithm runs in O(d + n log n) time, versus polynomial time for the prior LP approach.
- Error bounds in l1, l2 and l_infinity norms all scale as O(1/sqrt(d)) under epsilon-DP.
- An information-theoretic lower bound shows the Omega(1/sqrt(d)) dependence is asymptotically optimal for updatable epsilon-DP sketches with high-probability error.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Invert the expected profile transform induced by discrete Laplace noise instead of using the empirical noisy profile | Private profile reconstruction · Private profile reconstruction | ℓp error: Ω(1) error for the empirical noisy profile in the example; the proposed method gives the stated ℓ1, ℓ2, and ℓ∞ error bou | Helped |
| Use circulant-matrix inversion via FFT | Private profile reconstruction · Private profile reconstruction | running time: from polynomial time to O(d + n log n) | Helped |
| Round the estimated profile to satisfy support, coordinate-range, and sum-to-one constraints | Private profile reconstruction · Private profile reconstruction | ℓ1 error: err1' ≤ err1 | No clear effect |
| Round the estimated profile to satisfy support, coordinate-range, and sum-to-one constraints | Private profile reconstruction · Private profile reconstruction | ℓ∞ error: err∞' ≤ 2 · err∞ | Hurt |
Surprising findings
- Naive empirical profiles from the noisy histogram can incur Omega(1) error, e.g. when every item appears once the fraction at count 1 falls to about epsilon.
Limitations
- Lower bound does not directly bound expected error and requires a sensitivity assumption.
- l_infinity dependence on epsilon is 1/epsilon^1.5 rather than the 1/epsilon lower bound for single counters.
- Sampling error from the domain sample is treated separately and not analyzed in the main bounds.
Experimental setup
Metrics: l1 error l2 error l_infinity error running time
Baselines: Dwork et al. LP-based profile estimation naive empirical profile from noisy histogram
Builds on: Dwork et al. (ITCS 2010) LP-based noise reversal discrete Laplace (geometric) mechanism pan-private t-incidence estimation
Closest papers by meaning
- Privately Learning Smooth Distributions on the Hypercube by Projections (ICML 2024 · similarity 0.84)
- Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.84)
- On Differentially Private Subspace Estimation in a Distribution-Free Setting (NeurIPS 2024 · similarity 0.83)
- Dimension-free Private Mean Estimation for Anisotropic Distributions (NeurIPS 2024 · similarity 0.83)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.83)
- Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust (NeurIPS 2024 · similarity 0.83)
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.