arXiv:2206.15063v2
Imputation under Differential Privacy
cs.DB
Abstract
The literature on differential privacy almost invariably assumes that the data to be analyzed are fully observed. In most practical applications this is an unrealistic assumption. A popular strategy to address this problem is imputation, in which missing values are replaced by estimated values given the observed data. In this paper we evaluate various approaches to answering queries on an imputed dataset in a differentially private manner, as well as discuss trade-offs as to where along the pipeline privacy is considered. We show that if imputation is done without consideration to privacy, the sensitivity of certain queries can increase linearly with the number of incomplete records. On the other hand, for a general class of imputation strategies, these worst case scenarios can be greatly reduced by ensuring privacy already during the imputation stage. We use a simulated dataset to demonstrate these results across a number of imputation schemes (both private and non-private) and examine their impact on the utility of a private query on the data.
AI-generated audit
Audit summary
Not a correctness certificate. A green “no issues found” result may include yellow suspected typos or minor formal issues that do not affect substantive soundness. It means this audit found no unresolved substantive error under the stated criteria; it does not replace expert scrutiny or formal verification.
Current report
Detailed mathematical audit
01Statements2 reported findingsNo statement issues found
The group-privacy bound, the linear sensitivity amplification example, and the two-stage privacy guarantee are correct under the paper's stated recordwise-imputation assumptions.
Propositions 3.1–3.2No issue found
Non-private imputation can amplify privacy loss and sensitivity linearly
Pages 2–3 · Propositions 3.1 and 3.2 · arXiv:2206.15063v2
Neighboring incomplete datasets can produce completed datasets at Hamming distance at most . Group privacy therefore gives the displayed exponential privacy-loss bound, and telescoping along a record-by-record chain gives sensitivity at most . The order is attainable: with an intercept-only regression trained on a single complete response and missing responses, changing that training response from to changes all completed responses, so the mean changes by .
Full paper, version 2 ↗Theorem 3.3No issue found
Private parameter fitting composes with private analysis
Pages 3–4 · Theorem 3.3 · arXiv:2206.15063v2
For each fixed privately estimated parameter vector , the recordwise imputation kernel maps neighboring original datasets to completed datasets that can be coupled to differ only in the changed record. The subsequent mechanism is therefore -differentially private conditional on the first output. Adaptive sequential composition with the -private fit yields the claimed guarantee.
02Proofs4 reported findingsNo proof issues found
The privacy and sensitivity arguments are complete after three uniquely determined notation and display corrections in Proposition 3.2.
Proposition 3.2Suspected typo
The global-sensitivity display mixes variable names
Page 2 · definition of before Proposition 3.2 · arXiv:2206.15063v2
The outer maximum introduces , while its neighbor condition uses and the objective uses undefined . Use one pair consistently, for example , and write . The surrounding definition and the proof determine this correction uniquely.
Proposition 3.2 proofSuspected minor formal issue
The Hamming chain must be consecutive and may be shorter
Pages 2–3 · proof of the second inequality in Proposition 3.2 · arXiv:2206.15063v2
Replace the sentence saying that every differs from the first dataset by one change with: consecutive datasets differ in one record, and the chain has at most steps. Telescoping over that chain gives exactly the printed bound, so no downstream conclusion changes.
Proposition 3.2 tightness exampleSuspected incorrect as written · an apparently sound repair
The displayed example contains a false final equality
Page 3 · paragraph after the proof of Proposition 3.2 · arXiv:2206.15063v2
The paper computes and then identifies this with , but the stated setup does not make that final equality true. The intended tight example is immediate: train an intercept-only imputation on one observed response, with the other responses missing. Changing the observed response from to changes every completed response, so the mean changes by . Thus the upper bound is genuinely sharp, but the printed display does not prove it without this correction.
Theorem 3.3 proofSuspected minor formal issue
Adaptive composition needs an explicit recordwise coupling assumption
Pages 3–4 · proof of Theorem 3.3 · arXiv:2206.15063v2
Adaptive composition gives the stated result if, conditional on the fitted parameter, unchanged records can be imputed identically and only the changed record can differ. This follows for deterministic recordwise imputation or for independent local randomness. The displayed marginal condition does not by itself specify the joint coupling: correlated imputations can have the same recordwise marginals while changing several completed records. The theorem should make the intended local-kernel or conditional-independence assumption explicit; under that reading, the cited adaptive sequential composition applies exactly as claimed.
03Novelty0 reported findingsNo novelty concerns found
No non-novelty findings.