Lemma B.1 (group privacy): for inputs differing in at most entries
ProvedPrivBayesTest.lemma_B_1differential-privacyerror-exponentshypothesis-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let and let be an -DP mechanism on with output space : for all differing in exactly one coordinate and every measurable , . Let differ in at most coordinates. Then
- for every measurable ,
- the law of is absolutely continuous with respect to that of , and its density satisfies almost everywhere.
Group privacy is what lets the proof of Lemma 3.2 bound the likelihood ratio of a mechanism's output on two coupled datasets by times the number of entries in which they differ.
Differences from the source:
- generalization: output laws of a randomized mechanism (probability measures) → any family of finite measures A(x) with the DP inequality; reason: the proof (a chain of k neighbour steps) uses only the DP inequality; probability measures are a special case
- encoding: inputs that differ in at most k entries → #{i | xᵢ ≠ x′ᵢ} ≤ k; reason: same condition
- encoding: log dM(X)/dM(X′) ≤ kε → M(X) ≪ M(X′) and dM(X)/dM(X′) ≤ e^{kε} M(X′)-almost everywhere; reason: the density exists only under absolute continuity, which the event bound gives; Radon–Nikodym derivatives are defined almost everywhere
Preamble
import Mathlib import Definitions.Def_PrivLearn_Generic_Privacy open MeasureTheory
Formal statement
namespace PrivBayesTest
/-- **Lemma B.1 (Group Privacy)** of Jacobsen, *Optimal Error Exponents for Private Bayesian Hypothesis Testing*, STOC 2027 submission (manuscript sha256 abff2fdd…124ef), p.27. Let `M` be ε-DP and let `X, X′` be inputs that
differ in at most `k` entries. Then `Pr[M(X) ∈ S] ≤ e^{kε} Pr[M(X′) ∈ S]` for every event `S`, and
the density satisfies `log(dM(X)/dM(X′)) ≤ kε`.
**Formalization Note** The output laws of the mechanism are given by `A : Xⁿ → Measure O`, required
to be finite measures (the paper's are probability measures). ε-DP is the published
`PrivLearn.Generic.IsDP` (replace-one neighbours, Definition 1.1, p.2). "Differ in at most `k`
entries" is `#{i | xᵢ ≠ x′ᵢ} ≤ k`. The density clause is stated as `M(X) ≪ M(X′)` together with
`dM(X)/dM(X′) ≤ e^{kε}` `M(X′)`-almost everywhere (hence also `M(X)`-almost everywhere). -/
theorem lemma_B_1 {D O : Type*} [MeasurableSpace O] {n : ℕ} (A : (Fin n → D) → Measure O)
[∀ z, IsFiniteMeasure (A z)] (ε : ℝ) (hε : 0 < ε) (hA : PrivLearn.Generic.IsDP A ε) (k : ℕ)
(z z' : Fin n → D) (hk : {i : Fin n | z i ≠ z' i}.ncard ≤ k) :
(∀ S : Set O, MeasurableSet S → A z S ≤ ENNReal.ofReal (Real.exp (k * ε)) * A z' S) ∧
A z ≪ A z' ∧
∀ᵐ y ∂(A z'), (A z).rnDeriv (A z') y ≤ ENNReal.ofReal (Real.exp (k * ε)) := by sorry
end PrivBayesTest
Source
Jacobsen, Optimal Error Exponents for Private Bayesian Hypothesis Testing, STOC 2027 submission (manuscript sha256 abff2fdd66827f43…124ef), Lemma B.1, p.27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.