Lemma B.3 — post-processing of approximate DP
ProvedPrivateAgnosticHalfspace.Gaussian.lemma_B_3differential-privacymachine-learningp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be an -DP mechanism under replacement adjacency, where and . Let be a public randomized measurable post-processing rule from to . Then there is a probability mechanism whose law on input is the kernel mixture
and is also -DP.
This permits fresh randomness after a private release while withholding the original dataset from the post-processing rule.
Differences from the source:
- encoding: any randomized function on the private output → a measurable Markov kernel on that output; reason: expresses the standard measurable probability-law convention; no access to raw data is introduced
Preamble
import Definitions.Def_PrivateAgnosticHalfspace_Gaussian_Regression open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal set_option autoImplicit false
Formal statement
namespace PrivateAgnosticHalfspace.Gaussian
theorem lemma_B_3 {X Y Z : Type*} [MeasurableSpace Y] [MeasurableSpace Z]
(n : ℕ) (ε δ : ℝ) (hε : 0 < ε) (hδ : 0 ≤ δ ∧ δ < 1)
(M : PrivateUniformGen.Characterization.Mechanism X Y n)
(hM : PrivateUniformGen.Characterization.IsDP M ε δ)
(f : Kernel Y Z) [IsMarkovKernel f] :
∃ A : PrivateUniformGen.Characterization.Mechanism X Z n,
(∀ S, (A S : Measure Z) = f ∘ₘ (M S : Measure Y)) ∧
PrivateUniformGen.Characterization.IsDP A ε δ := by sorry
end PrivateAgnosticHalfspace.Gaussian
Source
Giorgio Racca, Amartya Sanyal, Vikrant Singhal, STOC 2027 submission #1006 (October 2026), p. 21, Lemma B.3 and Definition B.2; canonical PDF sha256 f0122a33e29daa624b530bdd0b071998d8e44197b30449b0cb3213289645cec7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.