Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§5.2: the conjunction of all significant, non-harmful literals has error at most ε/2 (the analysis behind Theorem 5.2)

Proved
ComputationalLearning.statistics_conjunction_error

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

boolean-conjunctionsstatistical-queriesunion-bound

§5.2 (p. 107). We say that zzz is significant if p0(z)≥ϵ/8np_0(z) \ge \epsilon/8np0​(z)≥ϵ/8n and harmful if p01(z)≥ϵ/8np_{01}(z) \ge \epsilon/8np01​(z)≥ϵ/8n. We now argue that if hhh is the conjunction of all the significant literals that are not harmful, then hhh has error less than ϵ\epsilonϵ with respect to ccc and DDD: Pr⁡[c(a)=0∧h(a)=1]\Pr[c(a) = 0 \wedge h(a) = 1]Pr[c(a)=0∧h(a)=1] is at most the probability that some insignificant literal is 000 in aaa, at most 2n(ϵ/8n)=ϵ/42n(\epsilon/8n) = \epsilon/42n(ϵ/8n)=ϵ/4 by the union bound; Pr⁡[c(a)=1∧h(a)=0]\Pr[c(a) = 1 \wedge h(a) = 0]Pr[c(a)=1∧h(a)=0] is at most the probability that some harmful literal is 000 in aaa with c(a)=1c(a) = 1c(a)=1, at most ϵ/4\epsilon/4ϵ/4; thus error(h)≤ϵ/2\mathrm{error}(h) \le \epsilon/2error(h)≤ϵ/2.

Formally: for every target conjunction TTT over x1,…,xnx_1, \dots, x_nx1​,…,xn​, every distribution DDD on {0,1}n\{0,1\}^n{0,1}n and ϵ>0\epsilon > 0ϵ>0, the conjunction of the significant non-harmful literals has error at most ϵ/2\epsilon/2ϵ/2 with respect to evalConj T\mathrm{evalConj}\,TevalConjT and DDD. This is the exact-probability content of Theorem 5.2 (conjunctions are learnable from statistical queries with tolerance ϵ/8n\epsilon/8nϵ/8n).

Preamble
import Definitions.Def_ComputationalLearning_Noise

open MeasureTheory ProbabilityTheory
Formal statement
namespace ComputationalLearning

/-- **Learning conjunctions from statistics** (§5.2, p. 107; the analysis behind Theorem 5.2). For
a target conjunction `c` over `x₁, …, xₙ`, a distribution `D` and `ε > 0`, if `h` is the
conjunction of all the significant literals (`p₀(z) ≥ ε/8n`) that are not harmful
(`p₀₁(z) < ε/8n`), then `error(h) ≤ ε/4 + ε/4 = ε/2`: a false positive requires an insignificant
literal of `c` to be `0`, a false negative a harmful literal of `h` to be `0` on a positive
example, and the union bound over the `2n` literals gives `ε/4` each. -/
theorem statistics_conjunction_error {n : ℕ} (T : Conjunction (Fin n)) (D : Measure (Cube (Fin n)))
    [IsProbabilityMeasure D] {ε : ℝ} (hε : 0 < ε) :
    errorOf D (evalConj T) (evalConj (statisticsConj D (evalConj T) ε)) ≤ ε / 2 := by sorry

end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §5.2 pp. 106-108, the algorithm for learning conjunctions from statistics and its error analysis
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 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