safety security
Privacy Counts the Person, Not Each Sample
A degree-six sum-of-squares estimator reaches near-optimal user counts when every participant contributes a batch from one discrete distribution.
Summary
A degree-six sum-of-squares estimator reaches near-optimal user counts when every participant contributes a batch from one discrete distribution.
Sample-level privacy can understate exposure when one person contributes many correlated records. This work studies person-level differential privacy for learning a discrete distribution from n users, each supplying m independent samples. It gives polynomial-time algorithms for both pure and approximate privacy, with the pure-DP user requirement matching the information-theoretic optimum up to logarithmic factors. The construction uses a degree-six sum-of-squares estimator for untrusted batches and a covariance certificate that preserves mean-dependent multinomial variance. A statistical-query lower bound rules out uniformly smaller error under fixed polynomial resources. These are theoretical rate and complexity results under the stated distributional assumptions, not a turnkey privacy guarantee for arbitrary behavioral datasets.
Why it matters
A degree-six sum-of-squares estimator reaches near-optimal user counts when every participant contributes a batch from one discrete distribution.
Limits and context
- These are theoretical rate and complexity results under the stated distributional assumptions, not a turnkey privacy guarantee for arbitrary behavioral datasets.
Key claims
A degree-six sum-of-squares estimator reaches near-optimal user counts when every participant contributes a batch from one discrete distribution.
Qualification: These are theoretical rate and complexity results under the stated distributional assumptions, not a turnkey privacy guarantee for arbitrary behavioral datasets.
Evidence: source-2026-10-25-013
Sources
- arXiv preprint 2610.31612, original v1arXiv · primary research
Corrections
No corrections have been recorded for this story.