Observation 2.4 — a counting query has global sensitivity at most 1/n
ProvedPrivateRelease.NetMechanism.observation_2_4counting-queriesdifferential-privacyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sensitivity
Let be a data universe (any set), , and a predicate. The counting query on inputs changes by at most when one entry of is replaced:
This bound on the sensitivity of counting queries is what turns the general utility bound of the Net mechanism (Property 3.4) into its counting-query form (Corollary 3.5).
Formalization Note Neighbouring inputs differ in exactly one entry (PrivLearn.Generic.Neighbors). The input is read as the multiset of its entries. The global sensitivity is a real supremum over neighbouring pairs; the differences lie in , so it is a genuine supremum for any .
Preamble
import Mathlib import Definitions.Def_PrivateRelease_NetMechanism_Queries
Formal statement
namespace PrivateRelease.NetMechanism
/-- Observation 2.4 (p. 6): for any predicate `φ : X → {0,1}`, the counting query
`Q_φ : Xⁿ → [0, 1]` has global sensitivity `GS_{Q_φ} ≤ 1/n` (replace-one neighbours). -/
theorem observation_2_4 {X : Type} (φ : X → Bool) (n : ℕ) (hn : 1 ≤ n) :
GS (fun z : Fin n → X => countQ φ (inputDB z)) ≤ 1 / (n : ℝ) := by sorry
end PrivateRelease.NetMechanism
Source
Blum, Ligett, Roth, A Learning Theory Approach to Non-Interactive Database Privacy, arXiv:1109.2229v1 (2011), p. 6, Observation 2.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.