# Answering Private Linear Queries Adaptively using the Common Mechanism

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 79 references that are in the map.
- First posted on arXiv 30 Nov 2022.

## Builds on (most cited first, 30 of 32)

- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [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)
- [Private Selection from Private Candidates](https://mlsanity.com/paper/1811.07971/) (2018)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (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)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017)
- [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)
- [Understanding the Sparse Vector Technique for Differential Privacy](https://mlsanity.com/paper/1603.01699/) (2016)
- [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019)
- [Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained ERM](https://mlsanity.com/paper/1705.10829/) (2017)
- [Towards Practical Differential Privacy for SQL Queries](https://mlsanity.com/paper/1706.09479/) (2017)
- [Bayesian and Frequentist Semantics for Common Variations of Differential Privacy: Applications to the 2020 Census](https://mlsanity.com/paper/2209.03310/) (2022)
- [The Large Margin Mechanism for Differentially Private Maximization](https://mlsanity.com/paper/1409.2177/) (2014)
- [Gradual Release of Sensitive Data under Differential Privacy](https://mlsanity.com/paper/1504.00429/) (2015)
- [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)
- [Convex Optimization for Linear Query Processing under Approximate Differential Privacy](https://mlsanity.com/paper/1602.04302/) (2016)
- [Free Gap Estimates from the Exponential Mechanism, Sparse Vector, Noisy Max and Related Algorithms](https://mlsanity.com/paper/2012.01592/) (2020)
- [Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy](https://mlsanity.com/paper/1502.07526/) (2015)
- [Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms](https://mlsanity.com/paper/1904.12773/) (2019)

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

- [ResidualPlanner+: a scalable matrix mechanism for marginals and beyond](https://mlsanity.com/paper/2305.08175/) (2023)
- [Accurate and Scalable Matrix Mechanisms via Divide and Conquer](https://mlsanity.com/paper/2604.00868/) (2026)

## Abstract (arXiv)

When analyzing confidential data through a privacy filter, a data scientist often needs to decide which queries will best support their intended analysis. For example, an analyst may wish to study noisy two-way marginals in a dataset produced by a mechanism M1. But, if the data are relatively sparse, the analyst may choose to examine noisy one-way marginals, produced by a mechanism M2 instead. Since the choice of whether to use M1 or M2 is data-dependent, a typical differentially private workflow is to first split the privacy loss budget rho into two parts: rho1 and rho2, then use the first part rho1 to determine which mechanism to use, and the remainder rho2 to obtain noisy answers from the chosen mechanism. In a sense, the first step seems wasteful because it takes away part of the privacy loss budget that could have been used to make the query answers more accurate. In this paper, we consider the question of whether the choice between M1 and M2 can be performed without wasting any privacy loss budget. For linear queries, we propose a method for decomposing M1 and M2 into three parts: (1) a mechanism M* that captures their shared information, (2) a mechanism M1' that captures information that is specific to M1, (3) a mechanism M2' that captures information that is specific to M2. Running M* and M1' together is completely equivalent to running M1 (both in terms of query answer accuracy and total privacy cost rho). Similarly, running M* and M2' together is completely equivalent to running M2. Since M* will be used no matter what, the analyst can use its output to decide whether to subsequently run M1'(thus recreating the analysis supported by M1) or M2'(recreating the analysis supported by M2), without wasting privacy loss budget.