Research map / Federated learning and privacy / Differential privacy
Privately Counting Partially Ordered Data
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 O(d^2)-time sampler for the K-norm mechanism over the poset ball, enabling pure-DP counting of partially ordered binary data with lower error than the l_infinity baseline.
Problem
Differentially private counting of d-bit data points that satisfy a partial order, where standard l_p sensitivity-based noise is loose and the induced norm ball is hard to sample efficiently.
Approach
Identifies the sensitivity-induced norm ball ("poset ball") with the double order polytope, triangulates it via non-interfering pairs of chains, and reduces uniform sampling to sampling extended bipartitions in O(d^2) time, giving an efficient problem-specific K-norm mechanism.
Key results
- Sampler runs in O(d^2) time, a more than cubic speedup over the best general polytope sampler's O~(d^(2+omega)).
- On random posets, the mechanism's advantage over the l_infinity baseline in squared l2 error grows with d, reaching over 90% reduction at d=40.
- On NHIS posets (d=4 to 15), the mechanism more than halves the error of the l_infinity baseline; up to 4x error reduction on random posets with deeper/richer structure.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the poset K-norm mechanism instead of the ℓ∞ mechanism as poset size grows | Privately counting random posets · Random posets, d=40 | expected squared ℓ2 error reduction: over 90% | Helped |
| Use the poset K-norm mechanism instead of the ℓ∞ mechanism on larger or richer posets | Privately counting random posets · Random posets, d=10 | expected squared ℓ2 error reduction: up to a 4x reduction in error | Helped |
| Use the poset K-norm mechanism instead of the ℓ∞ mechanism | Privately counting NHIS responses · National Health Interview Survey (Hypertension, Cholesterol, and Asthma sections) | mean squared ℓ2 error: more than halves the error | Helped |
| Use the ℓ∞ mechanism instead of the Laplace (ℓ1) mechanism | Private counting · Analytic comparison across dimensions | squared ℓ2 error: approximately 2 (d=2) to 5 (d=50) times worse | Helped |
Surprising findings
- Rejection sampling the poset ball from any l_p ball requires Omega(2^d) samples in expectation, so it is provably exponentially inefficient.
Limitations
- Analysis is for pure DP only; approximate DP with elliptic Gaussian noise does not directly apply because the poset ball is not symmetric around (1,...,1).
- Random poset generator has O(d^4) runtime, restricting experiments to small d.
- Gains depend on poset structure; posets with shallow structure (like NHIS) show constant rather than growing advantage.
Experimental setup
Datasets: National Health Interview Survey synthetic random posets
Benchmarks: National Health Interview Survey
Metrics: expected squared l2 error ratio relative to l_infinity mecha
Baselines: l_infinity mechanism Laplace mechanism rejection sampling from l_p balls
Builds on: K-norm mechanism double order polytope double chain polytope Birkhoff lattice triangulation
Closest papers by meaning
- Private Continual Counting of Unbounded Streams (NeurIPS 2025 · similarity 0.88)
- Differentially Private Set Representations (NeurIPS 2024 · similarity 0.86)
- Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model (ICML 2025 · similarity 0.86)
- Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning (NeurIPS 2024 · similarity 0.85)
- Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.85)
- Continual Counting with Gradual Privacy Expiration (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.