Theorem 4.4 — privately PAC learns PARITY with samples
ProvedPrivLearn.Parity.theorem_4_4There are constants of the algorithm and a constant such that for all , and :
- (Privacy) for every database size , is -differentially private;
- (Utility) for every distribution on , every target PARITY and every
on the database with i.i.d., outputs a hypothesis with with probability at least .
When the bound is , the paper's. Parity functions are thus privately PAC learnable (Definition 3.1) with a sample complexity that exceeds the non-private by a factor .
Formalization Note "Efficiently" (polynomial running time) is not modelled. Privacy is stated for , the range the paper's proof of Lemma 4.2 covers. The printed sample bound is false when (the threshold of step 2 grows like ); utility is stated with the corrected bound , which reduces to the printed order when . The privacy conjunct does not depend on the sample bound. is base 2, and the base of 's logarithm is corrected from to (see the definition of ).
import Mathlib import Definitions.Def_PrivLearn_Generic_Privacy import Definitions.Def_PrivLearn_Parity_Learner import Definitions.Def_PrivLearn_Parity_Amplified
namespace PrivLearn.Parity
/-- Theorem 4.4, p. 17. There are constants `c, c′` of algorithm `A*` and a constant `C` such that
for all `d ≥ 1`, `0 < ε ≤ 1/2` and `α, β ∈ (0, 1/2)`:
(privacy) `A*(·, ε, α, β)` is ε-differentially private on databases of every size;
(utility) for every distribution `𝒳` on `{0,1}^d`, every target `c_r ∈ PARITY` and every
`n ≥ C (d + log₂(1/β)) log₂(1/β)/(εα)` (which is `O(d log(1/β)/(εα))` when `log₂(1/β) ≤ d`),
`A*` outputs a hypothesis `h*` with `err(h*) ≤ α` with probability at least `1 − β` over
`x_1, …, x_n ∼ 𝒳` i.i.d. and its coins. -/
theorem theorem_4_4 :
∃ c c' C : ℝ, 0 < c ∧ 0 < c' ∧ 0 < C ∧
∀ d : ℕ, 1 ≤ d → ∀ ε α β : ℝ, 0 < ε → ε ≤ 1 / 2 → 0 < α → α < 1 / 2 → 0 < β → β < 1 / 2 →
(∀ n : ℕ, PrivLearn.Generic.IsDP (fun z : Fin n → Example d => algAstar c c' d ε α β z) ε) ∧
(∀ (𝒳 : PMF (Fin d → ZMod 2)) (r : Fin d → ZMod 2) (n : ℕ),
C * (d + Real.logb 2 (1 / β)) * Real.logb 2 (1 / β) / (ε * α) ≤ n →
ENNReal.ofReal (1 - β) ≤
samplePr 𝒳 r (fun z : Fin n → Example d => algAstar c c' d ε α β z)
{o | ∃ r' : Fin d → ZMod 2, o = AstarOut.hyp r' ∧ err 𝒳 r (some r') ≤ α}) := by sorry
end PrivLearn.Parity
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.