Lemma 3 — group privacy with the exact additive term
ProvedPrivPACLower.ICP.lemma_3differential-privacymachine-learningp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be an -DP mechanism on records, with and . If databases differ in exactly records, every measurable output event satisfies
For databases differing in at most records, the same comparison holds with additive term . The case includes identical databases and an empty sum. These comparisons provide the privacy guarantee for repetition and the two-point learner lower bound.
Differences from the source:
- encoding: binary hypotheses, ordered databases and ordinary probabilities → Bool hypotheses, Fin-indexed databases, probability measures and extended nonnegative error probabilities; reason: retains replacement adjacency, improper outputs and the joint sample-and-learner experiment; all applied thresholds are nonnegative
Preamble
import Mathlib import Definitions.Def_PrivateUniformGen_Characterization_Privacy import Definitions.Def_PrivPACLower_ICP_Reductions open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal set_option autoImplicit false
Formal statement
namespace PrivPACLower.ICP
open PrivateUniformGen.Characterization
theorem lemma_3 {Z O : Type*} [MeasurableSpace O] {n : ℕ}
(ε δ : ℝ) (hε : 0 < ε) (hδ : 0 ≤ δ ∧ δ < 1)
(M : Mechanism Z O n) (hM : IsDP M ε δ) :
(∀ (S S' : Fin n → Z) (r : ℕ), hamming S S' = r →
∀ E : Set O, MeasurableSet E →
(M S : Measure O).real E ≤ Real.exp ((r : ℝ)*ε) * (M S' : Measure O).real E +
δ * ∑ s ∈ Finset.range r, Real.exp ((s : ℝ)*ε)) ∧
(∀ (r : ℕ) (S S' : Fin n → Z), hamming S S' ≤ r →
∀ E : Set O, MeasurableSet E →
(M S : Measure O).real E ≤ Real.exp ((r : ℝ)*ε) * (M S' : Measure O).real E +
(r : ℝ) * Real.exp (((r : ℝ)-1)*ε) * δ) := by sorry
end PrivPACLower.ICP
Source
Prathamesh Dharangutte, Amartya Sanyal, STOC 2027 submission #366 (October 2026), p. 11, Lemma 3. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/366.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.