Theorem 3.4 — the generic private learner agnostically learns any finite class from examples
ProvedPrivLearn.Generic.theorem_3_4There is an absolute constant with the following property. Let be a finite set of examples, a finite nonempty class of hypotheses , and let and . Then the exponential mechanism over satisfies:
- Privacy. For every database size , is -differentially private.
- Utility. For every probability distribution on and every with
if consists of examples drawn i.i.d. from , then
where and the probability is over and the coins of the mechanism.
This is the quantitative ("More precisely") form of Theorem 3.4: every finite concept class is privately agnostically learnable with sample size logarithmic in its cardinality. The qualitative first sentence of the theorem (classes of cardinality at most are privately agnostically learnable) follows, since then is polynomial in .
Formalization Note. The paper writes the sample size as ; we state it with one absolute constant , chosen before the domain, the class, the distribution and all parameters. The constant written at the end of the paper's proof does not make the final inequality close, so no numeric constant is stated. Logarithms are natural. The example domain is a finite type with the discrete σ-algebra (the paper's has representations of size at most ), quantified over Type so that the existential is well-formed. The learner's output law is a measure on X → Bool; the failure probability is the integral over of the mechanism's probability of the event .
import Mathlib import Definitions.Def_PrivLearn_Generic_Privacy import Definitions.Def_PrivLearn_Generic_ExpMech open MeasureTheory
namespace PrivLearn.Generic
/-- Theorem 3.4 (p. 11, generic private learner), in its quantitative form. There is an absolute
constant `C > 0` such that for every finite example domain `X`, every finite nonempty class
`H = C_d` of hypotheses `X → {0,1}` and all `ε > 0`, `α, β ∈ (0, 1/2)`, the exponential
mechanism `A^ε_q` (a) is `ε`-differentially private, and (b) for every distribution `P` on
`X × {0,1}` and every
`n ≥ C (ln|H| + ln(1/β)) max{1/(εα), 1/α²}`, run on `n` i.i.d. examples from `P` it outputs a
hypothesis with `err(h) > OPT + α` with probability at most `β`. -/
theorem theorem_3_4 :
∃ C : ℝ, 0 < C ∧
∀ (X : Type) [Fintype X] [MeasurableSpace X] [DiscreteMeasurableSpace X]
(H : Finset (X → Bool)) (hH : H.Nonempty) (ε α β : ℝ),
0 < ε → 0 < α → α < 1 / 2 → 0 < β → β < 1 / 2 →
(∀ n : ℕ, IsDP (fun z : Fin n → X × Bool => expMech H ε z) ε) ∧
∀ (P : Measure (X × Bool)) [IsProbabilityMeasure P] (n : ℕ),
C * (Real.log H.card + Real.log (1 / β)) * max (1 / (ε * α)) (1 / α ^ 2) ≤ n →
∫⁻ z, expMech H ε z {h | OPT P H hH + α < err P h} ∂(Measure.pi fun _ : Fin n => P)
≤ ENNReal.ofReal β := by sorry
end PrivLearn.Generic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.