Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.1: axis-aligned rectangles are PAC learnable by the tightest-fit algorithm with m ≥ (4/ε) ln(4/δ) examples

Proved
ComputationalLearning.rectangles_pac_learnable

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

pac-learningrectanglessample-complexity

Theorem 1.1. The concept class of axis-aligned rectangles over the Euclidean plane R2\mathbb{R}^2R2 is efficiently PAC learnable.

Formally (sample-complexity sense, with the book's algorithm and bound, p. 6): for every target rectangle [a1,b1]×[a2,b2][a_1, b_1] \times [a_2, b_2][a1​,b1​]×[a2​,b2​], every probability measure DDD on R2\mathbb{R}^2R2, ϵ>0\epsilon > 0ϵ>0, 0<δ<10 < \delta < 10<δ<1 and m≥(4/ϵ)ln⁡(4/δ)m \ge (4/\epsilon)\ln(4/\delta)m≥(4/ϵ)ln(4/δ): the tightest-fit rectangle is consistent with every sample labeled by the target; the probability, under the law of mmm independent labeled examples, that the tightest-fit rectangle has error greater than ϵ\epsilonϵ is at most δ\deltaδ; and the class of axis-aligned rectangles is PAC learnable using axis-aligned rectangles. The distribution is arbitrary (the four-strip argument is carried out for measures with atoms by taking the strip of height t∗=sup⁡{t:weight of {y≥t}∩R≥ϵ/4}t^* = \sup\{t : \text{weight of } \{y \ge t\} \cap R \ge \epsilon/4\}t∗=sup{t:weight of {y≥t}∩R≥ϵ/4}).

Preamble
import Definitions.Def_ComputationalLearning_PAC

open MeasureTheory
Formal statement
namespace ComputationalLearning

/-- **Theorem 1.1** (p. 12). The concept class of axis-aligned rectangles over the Euclidean
plane is (efficiently) PAC learnable, by the tightest-fit algorithm: for every target rectangle,
every distribution `D` on the plane and `ε, δ > 0`, the tightest-fit rectangle is consistent with
every sample labeled by the target, and with `m ≥ (4/ε) ln(4/δ)` examples it has error greater
than `ε` with probability at most `δ` (§1.1, p. 6); hence rectangles are PAC learnable using
rectangles in the sample-complexity sense. -/
theorem rectangles_pac_learnable (a b : ℝ × ℝ) (D : Measure (ℝ × ℝ)) [IsProbabilityMeasure D]
    {ε δ : ℝ} (hε : 0 < ε) (hδ : 0 < δ) (hδ1 : δ < 1) (m : ℕ)
    (hm : 4 / ε * Real.log (4 / δ) ≤ m) :
    (∀ S : Fin m → (ℝ × ℝ) × Bool, IsLabeledBy (rectConcept a b) S →
      IsConsistent (tightestFit S) S) ∧
    sampleLaw D (rectConcept a b) m {S | ε < errorOf D (rectConcept a b) (tightestFit S)} ≤
      ENNReal.ofReal δ ∧
    PACLearnable rectangleClass rectangleClass := by sorry

end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §1.1 pp. 3-6 (the tightest-fit algorithm and its analysis) and Theorem 1.1, p. 12
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