Lemma 5.6 — A_g approximates E[g] within ±τ with probability ≥ 1 − β from n ≥ c·log(1/β)b²/(ε²τ²) samples
ProvedPrivLearn.LocalSim.lemma_5_6There is an absolute constant with the following property. Let be a probability distribution on a domain , let be measurable, and let , with and . If the database has
entries drawn i.i.d. from , then the local algorithm approximates within additive error with probability at least :
One run of thus answers one statistical query; Theorem 5.7 applies it once per query on fresh data.
Formalization Note. "For sufficiently large constant " is stated as before every other quantifier. The paper's is base 2; we use the natural logarithm, which only changes . The probability is over the database and the Laplace noises jointly (product measure). Two hypotheses are added because the printed lemma is false without them. (i) : with and large, is allowed for and the error probability exceeds . (ii) : for large the threshold falls below the samples needed to control the sampling error of (e.g. fair coin, , ); the paper's remark that the sampling bound "is smaller than the lower bound on in the lemma by a factor of " presumes . Every use in the paper satisfies both.
import Mathlib import Definitions.Def_PrivLearn_LocalSim_Privacy import Definitions.Def_PrivLearn_LocalSim_Simulation
namespace PrivLearn.LocalSim
open MeasureTheory
/-- Lemma 5.6 (p. 20): there is an absolute constant `c > 0` such that if the database
`z = (z_1, …, z_n)` has `n ≥ c · ln(1/β) b² / (ε² τ²)` entries drawn i.i.d. from `P`, then for a
measurable query `g : Dom → [−b, b]` the output of `A_g(n, ε, LR_z)` is within `τ` of
`E_{u∼P}[g(u)]` with probability at least `1 − β` (over the database and the Laplace noises).
Stated for `ε ≤ 1` and in the regime `ε τ ≤ 4 b`, without which it is false. -/
theorem lemma_5_6 :
∃ c : ℝ, 0 < c ∧
∀ (Dom : Type) [MeasurableSpace Dom] (P : Measure Dom) [IsProbabilityMeasure P]
(g : Dom → ℝ) (b ε τ β : ℝ) (n : ℕ),
Measurable g → (∀ u, |g u| ≤ b) →
0 < b → 0 < ε → ε ≤ 1 → 0 < τ → ε * τ ≤ 4 * b → 0 < β → β < 1 →
c * Real.log (1 / β) * b ^ 2 / (ε ^ 2 * τ ^ 2) ≤ n →
ENNReal.ofReal (1 - β) ≤
((Measure.pi fun _ : Fin n => P).prod
(Measure.pi fun _ : Fin n => PrivLearn.Generic.laplace (2 * b / ε)))
{p | |avgResp g p.1 p.2 - ∫ x, g x ∂P| ≤ τ} := by sorry
end PrivLearn.LocalSim
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.