# Efficient and Private Marginal Reconstruction with Local Non-Negativity

arXiv: https://arxiv.org/abs/2410.01091 · HTML: https://mlsanity.com/paper/2410.01091/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 1 Oct 2024.

## Builds on (most cited first, 18 of 18)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Winning the NIST Contest: A scalable and general approach to differentially private synthetic data](https://mlsanity.com/paper/2108.04978/) (2021)
- [AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data](https://mlsanity.com/paper/2201.12677/) (2022)
- [Graphical-model based estimation and inference for differential privacy](https://mlsanity.com/paper/1901.09136/) (2019)
- [Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods](https://mlsanity.com/paper/2106.07153/) (2021)
- [Fair Decision Making using Privacy-Protected Data](https://mlsanity.com/paper/1905.12744/) (2019)
- [Differentially Private Query Release Through Adaptive Projection](https://mlsanity.com/paper/2103.06641/) (2021)
- [Geographic Spines in the 2020 Census Disclosure Avoidance System](https://mlsanity.com/paper/2203.16654/) (2022)
- [Differentially Private Synthetic Data: Applied Evaluations and Enhancements](https://mlsanity.com/paper/2011.05537/) (2020)
- [Private Synthetic Data for Multitask Learning and Marginal Queries](https://mlsanity.com/paper/2209.07400/) (2022)
- [Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/1808.03537/) (2018)
- [HDMM: Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/2106.12118/) (2021)
- [Principled Evaluation of Differentially Private Algorithms using DPBench](https://mlsanity.com/paper/1512.04817/) (2015)
- [Optimizing Fitness-For-Use of Differentially Private Linear Queries](https://mlsanity.com/paper/2012.00135/) (2020)
- [ResidualPlanner+: a scalable matrix mechanism for marginals and beyond](https://mlsanity.com/paper/2305.08175/) (2023)
- [Fast Kronecker Matrix-Matrix Multiplication on GPUs](https://mlsanity.com/paper/2401.10187/) (2024)

## Built on by (most cited first, 1 of 1)

- [Accurate and Scalable Matrix Mechanisms via Divide and Conquer](https://mlsanity.com/paper/2604.00868/) (2026)

## Abstract (arXiv)

Differential privacy is the dominant standard for formal and quantifiable privacy and has been used in major deployments that impact millions of people. Many differentially private algorithms for query release and synthetic data contain steps that reconstruct answers to queries from answers to other queries that have been measured privately. Reconstruction is an important subproblem for such mechanisms to economize the privacy budget, minimize error on reconstructed answers, and allow for scalability to high-dimensional datasets. In this paper, we introduce a principled and efficient postprocessing method ReM (Residuals-to-Marginals) for reconstructing answers to marginal queries. Our method builds on recent work on efficient mechanisms for marginal query release, based on making measurements using a residual query basis that admits efficient pseudoinversion, which is an important primitive used in reconstruction. An extension GReM-LNN (Gaussian Residuals-to-Marginals with Local Non-negativity) reconstructs marginals under Gaussian noise satisfying consistency and non-negativity, which often reduces error on reconstructed answers. We demonstrate the utility of ReM and GReM-LNN by applying them to improve existing private query answering mechanisms.