Answering Private Linear Queries Adaptively using the Common Mechanism

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 M₁. But, if the data are relatively sparse, the analyst may choose to examine noisy one-way marginals, produced by a mechanismM₂, instead. Since the choice of whether to use M₁ orM₂ is data-dependent, a typical differentially private workflow is to first split the privacy loss budget ρ into two parts: ρ₁ and ρ₂, then use the first part ρ₁ to determine which mechanism to use, and the remainder ρ₂ 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 M₁ and M₂ can be performed without wasting any privacy loss budget. For linear queries, we propose a method for decomposing M₁ and M₂ into three parts: (1) a mechanism M_∗ that captures their shared information, (2) a mechanism M′₁ that captures information that is specific to M₁, (3) a mechanism M^′₂ that captures information that is specific to M₂. Running M_∗ andM^′₁ together is completely equivalent to running M₁ (both in terms of query answer accuracy and total privacy cost ρ). Similarly, running M_∗ and M^′₂ together is completely equivalent to running M₂. Since M_∗ will be used no matter what, the analyst can use its output to decide whether to subsequently run M^′₁ (thus recreating the analysis supported by M₁) or M^′₂ (recreating the analysis supported by M₂), without wasting privacy loss budget.