Research map / Federated learning and privacy / Differential privacy
Efficient and Private Marginal Reconstruction with Local Non-Negativity
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 ReM, an efficient pseudoinverse-based reconstruction of marginal queries from residual (or marginal) measurements, plus GReM-LNN which adds local non-negativity via convex optimization, improving ResidualPlanner and Scalable MWEM error.
Problem
Reconstructing marginal query answers from noisy privately measured queries (residuals or marginals) in high-dimensional differentially private query answering, where existing methods are exponential or non-convex, and enforcing non-negativity is hard to do efficiently.
Approach
Use the Kronecker and orthogonality structure of residual queries to compute pseudoinverse reconstruction of marginals in time nearly linear in domain size; decompose isotropic Gaussian marginal measurements into independent residual measurements; and enforce non-negativity of reconstructed marginals (local non-negativity) via a convex program over residuals solved with dual ascent.
Key results
- GReM-LNN reduces ResidualPlanner workload error by a factor of 44.0x on average across settings and trials.
- GReM-LNN reduces Scalable MWEM workload error by a factor of 12.3x on average and is 1.1x lower than Trunc+Rescale.
- GReM-LNN has 17.6x lower workload error than Trunc and 3.2x lower than Trunc+Rescale for ResidualPlanner.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply GReM-LNN post-processing to ResidualPlanner | ResidualPlanner · All datasets and privacy budgets in the ResidualPlanner experiment | average ℓ1 workload error: 44.0× | Helped |
| Apply GReM-LNN post-processing instead of Trunc | ResidualPlanner · All datasets and privacy budgets in the ResidualPlanner experiment | average ℓ1 workload error: 17.6× | Helped |
| Apply GReM-LNN post-processing instead of Trunc+Rescale | ResidualPlanner · All datasets and privacy budgets in the ResidualPlanner experiment | average ℓ1 workload error: 3.2× | Mixed |
| Apply GReM-LNN post-processing to Scalable MWEM | Scalable MWEM · 30 rounds, all datasets and privacy budgets | average ℓ1 workload error: 12.3× | Helped |
| Apply GReM-LNN post-processing instead of Trunc+Rescale | Scalable MWEM · 30 rounds, all datasets and privacy budgets | average ℓ1 workload error: 1.1× | Helped |
Limitations
- Does not generate synthetic data, which limits downstream use cases
- Only supports discrete domains; continuous attributes must be discretized
- The 2^|tau| weighting in GReM-LNN loss is a heuristic
Experimental setup
Datasets: Titanic Adult Salary Nist-Taxi
Benchmarks: Titanic Adult Salary Nist-Taxi
Metrics: average l1 workload error on 3-way marginals l2 workload error
Baselines: ResidualPlanner Scalable MWEM Private-PGM Trunc Trunc+Rescale
Builds on: ResidualPlanner MWEM matrix mechanism Private-PGM HDMM
Closest papers by meaning
- Perturb-and-Project: Differentially Private Similarities and Marginals (ICML 2024 · similarity 0.88)
- Privacy-Preserving Data Release Leveraging Optimal Transport and Particle Gradient Descent (ICML 2024 · similarity 0.86)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.85)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · similarity 0.85)
- Open LLMs are Necessary for Current Private Adaptations and Outperform their Closed Alternatives (NeurIPS 2024 · similarity 0.85)
- Private Prediction via Shrinkage (NeurIPS 2026 · 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.