# ResidualPlanner+: a scalable matrix mechanism for marginals and beyond

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 72 references that are in the map.
- First posted on arXiv 14 May 2023.

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

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [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)
- [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)
- [New Oracle-Efficient Algorithms for Private Synthetic Data Release](https://mlsanity.com/paper/2007.05453/) (2020)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/1808.03537/) (2018)
- [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019)
- [Dual Query: Practical Private Query Release for High Dimensional Data](https://mlsanity.com/paper/1402.1526/) (2014)
- [Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing](https://mlsanity.com/paper/1602.03090/) (2016)
- [HDMM: Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/2106.12118/) (2021)
- [Differentially Private Release of High-Dimensional Datasets using the Gaussian Copula](https://mlsanity.com/paper/1902.01499/) (2019)
- [Widespread Underestimation of Sensitivity in Differentially Private Libraries and How to Fix It](https://mlsanity.com/paper/2207.10635/) (2022)
- [Precision-based attacks and interval refining: how to break, then fix, differential privacy on finite computers](https://mlsanity.com/paper/2207.13793/) (2022)
- [Optimizing Fitness-For-Use of Differentially Private Linear Queries](https://mlsanity.com/paper/2012.00135/) (2020)
- [Relaxed Marginal Consistency for Differentially Private Query Answering](https://mlsanity.com/paper/2109.06153/) (2021)
- [Convex Optimization for Linear Query Processing under Approximate Differential Privacy](https://mlsanity.com/paper/1602.04302/) (2016)
- [Differentially Private Hierarchical Count-of-Counts Histograms](https://mlsanity.com/paper/1804.00370/) (2018)
- [Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy](https://mlsanity.com/paper/1502.07526/) (2015)
- [A New Class of Private Chi-Square Tests](https://mlsanity.com/paper/1610.07662/) (2016)
- [Private Synthetic Data with Hierarchical Structure](https://mlsanity.com/paper/2206.05942/) (2022)
- [Answering Private Linear Queries Adaptively using the Common Mechanism](https://mlsanity.com/paper/2212.00135/) (2022)

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

- [Efficient and Private Marginal Reconstruction with Local Non-Negativity](https://mlsanity.com/paper/2410.01091/) (2024)
- [Differentially Private Range Queries with Correlated Input Perturbation](https://mlsanity.com/paper/2402.07066/) (2024)

## Abstract (arXiv)

Noisy marginals are a common form of confidentiality protecting data release and are useful for many downstream tasks such as contingency table analysis, construction of Bayesian networks, and even synthetic data generation. Privacy mechanisms that provide unbiased noisy answers to linear queries (such as marginals) are known as matrix mechanisms. We propose ResidualPlanner and ResidualPlanner+, two highly scalable matrix mechanisms. ResidualPlanner is both optimal and scalable for answering marginal queries with Gaussian noise, while ResidualPlanner+ provides support for more general workloads, such as combinations of marginals and range queries or prefix-sum queries. ResidualPlanner can optimize for many loss functions that can be written as a convex function of marginal variances (prior work was restricted to just one predefined objective function). ResidualPlanner can optimize the accuracy of marginals in large scale settings in seconds, even when the previous state of the art (HDMM) runs out of memory. It even runs on datasets with 100 attributes in a couple of minutes. Furthermore, ResidualPlanner can efficiently compute variance/covariance values for each marginal (prior methods quickly run out of memory, even for relatively small datasets). ResidualPlanner+ provides support for more complex workloads that combine marginal and range/prefix-sum queries (e.g., a marginal on race, a range query on age, and a combined race/age tabulation that answers age range queries for each race). It even supports custom user-defined workloads on different attributes. With this added flexibility, ResidualPlanner+ is not necessarily optimal, however it is still extremely scalable and outperforms the prior state-of-the-art (HDMM) on prefix-sum queries both in terms of accuracy and speed.