Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.4 — A∗\mathcal A^*A∗ privately PAC learns PARITY with O(dlog⁡(1/β)/(εα))O(d\log(1/\beta)/(\varepsilon\alpha))O(dlog(1/β)/(εα)) samples

Proved
PrivLearn.Parity.theorem_4_4

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

differential-privacyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1pac-learningparity

There are constants c,c′c, c'c,c′ of the algorithm A∗\mathcal A^*A∗ and a constant C>0C > 0C>0 such that for all d≥1d \ge 1d≥1, 0<ε≤1/20 < \varepsilon \le 1/20<ε≤1/2 and α,β∈(0,1/2)\alpha, \beta \in (0, 1/2)α,β∈(0,1/2):

  1. (Privacy) for every database size nnn, A∗(⋅,ε,α,β)\mathcal A^*(\cdot, \varepsilon, \alpha, \beta)A∗(⋅,ε,α,β) is ε\varepsilonε-differentially private;
  2. (Utility) for every distribution X\mathcal XX on {0,1}d\{0,1\}^d{0,1}d, every target cr∈c_r \incr​∈ PARITY and every
n≥C (d+log⁡2(1/β))log⁡2(1/β)εα,n \ge C\,\frac{(d + \log_2(1/\beta))\log_2(1/\beta)}{\varepsilon\alpha},n≥Cεα(d+log2​(1/β))log2​(1/β)​,

on the database zi=(xi,cr(xi))z_i = (x_i, c_r(x_i))zi​=(xi​,cr​(xi​)) with x1,…,xn∼Xx_1,\dots,x_n \sim \mathcal Xx1​,…,xn​∼X i.i.d., A∗\mathcal A^*A∗ outputs a hypothesis h∗h^*h∗ with err(h∗)≤α\mathrm{err}(h^*) \le \alphaerr(h∗)≤α with probability at least 1−β1 - \beta1−β.

When log⁡2(1/β)≤d\log_2(1/\beta) \le dlog2​(1/β)≤d the bound is O(dlog⁡(1/β)/(εα))O(d\log(1/\beta)/(\varepsilon\alpha))O(dlog(1/β)/(εα)), the paper's. Parity functions are thus privately PAC learnable (Definition 3.1) with a sample complexity that exceeds the non-private O((d+ln⁡(1/β))/α)O((d + \ln(1/\beta))/\alpha)O((d+ln(1/β))/α) by a factor O(ln⁡(1/β)/ε)O(\ln(1/\beta)/\varepsilon)O(ln(1/β)/ε).

Formalization Note "Efficiently" (polynomial running time) is not modelled. Privacy is stated for 0<ε≤1/20 < \varepsilon \le 1/20<ε≤1/2, the range the paper's proof of Lemma 4.2 covers. The printed sample bound is false when log⁡(1/β)≫d\log(1/\beta) \gg dlog(1/β)≫d (the threshold kn′+skn'+skn′+s of step 2 grows like log⁡2(1/β)/(εα)\log^2(1/\beta)/(\varepsilon\alpha)log2(1/β)/(εα)); utility is stated with the corrected bound C(d+log⁡2(1/β))log⁡2(1/β)/(εα)C(d + \log_2(1/\beta))\log_2(1/\beta)/(\varepsilon\alpha)C(d+log2​(1/β))log2​(1/β)/(εα), which reduces to the printed order when log⁡2(1/β)≤d\log_2(1/\beta) \le dlog2​(1/β)≤d. The privacy conjunct does not depend on the sample bound. log⁡\loglog is base 2, and the base of kkk's logarithm is corrected from 3/43/43/4 to 4/34/34/3 (see the definition of A∗\mathcal A^*A∗).

Preamble
import Mathlib
import Definitions.Def_PrivLearn_Generic_Privacy
import Definitions.Def_PrivLearn_Parity_Learner
import Definitions.Def_PrivLearn_Parity_Amplified
Formal statement
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
Source
Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith, What Can We Learn Privately?, arXiv:0803.0924v3, p. 17, Theorem 4.4
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me