Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Statements 1 and 3 of Theorem 5.3 — uniform polynomial-time learners for PnP_nPn​ with n2 polylog/(ερ2)+O(log⁡(1/δ)/ε)n^2\,\mathrm{polylog}/(\varepsilon\rho^2)+O(\log(1/\delta)/\varepsilon)n2polylog/(ερ2)+O(log(1/δ)/ε) samples

Definition
ReplParity_Supplement_PnRateLearners

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

finite-bit-modellearning-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1pac-learningreplicability

For a flag every∈{false,true}\mathrm{every}\in\{\mathrm{false},\mathrm{true}\}every∈{false,true}, PnRateLearners(every)\mathrm{PnRateLearners}(\mathrm{every})PnRateLearners(every) is the proposition that there are a constant CCC, an exponent kkk, a sample size m(n,ε,δ,ρ)m(n,\varepsilon,\delta,\rho)m(n,ε,δ,ρ), a seed length R(n,ε,δ,ρ)R(n,\varepsilon,\delta,\rho)R(n,ε,δ,ρ) and one algorithm AAA such that:

  1. AAA runs in polynomial time in the finite-bit model (a Turing machine on the base mission's fixed binary encoding);
  2. RRR is bounded by a polynomial in n+mn+mn+m and the encoding lengths of ε,δ,ρ\varepsilon,\delta,\rhoε,δ,ρ;
  3. for every n≥1n\ge1n≥1 and all rationals 0<ε,δ,ρ<1/20<\varepsilon,\delta,\rho<1/20<ε,δ,ρ<1/2, the learner AAA for PnP_nPn​ with mmm samples and a uniform RRR-bit seed outputs ⊥\bot⊥ or an nnn-bit truth table, uses
m≤Cn2ερ2(1+log⁡n+log⁡(1/ε)+log⁡(1/ρ))k+Clog⁡(1/δ)εm\le \frac{Cn^2}{\varepsilon\rho^2}\big(1+\log n+\log(1/\varepsilon)+\log(1/\rho)\big)^k+\frac{C\log(1/\delta)}{\varepsilon}m≤ερ2Cn2​(1+logn+log(1/ε)+log(1/ρ))k+εClog(1/δ)​

samples, is realizably (ε,δ)(\varepsilon,\delta)(ε,δ)-PAC for PnP_nPn​, and is ρ\rhoρ-replicable on realizable distributions (if every=false\mathrm{every}=\mathrm{false}every=false: statement 1) or on every labeled distribution on [n]×{0,1}[n]\times\{0,1\}[n]×{0,1} (if every=true\mathrm{every}=\mathrm{true}every=true: statement 3).

These are the two learning sides of the characterization in Theorem 5.3.

Formalization Note One machine serves all n,ε,δ,ρn,\varepsilon,\delta,\rhon,ε,δ,ρ, and C,k,m,R,AC,k,m,R,AC,k,m,R,A are chosen before them, as in the base goal. A factor polylog(n,1/ε,1/ρ)\mathrm{polylog}(n,1/\varepsilon,1/\rho)polylog(n,1/ε,1/ρ) bounded by a fixed polynomial in the logarithms is written (1+log⁡n+log⁡(1/ε)+log⁡(1/ρ))k(1+\log n+\log(1/\varepsilon)+\log(1/\rho))^k(1+logn+log(1/ε)+log(1/ρ))k; these logarithms are nonnegative here, so every such polynomial is at most a constant times this power.

Definition code
import Mathlib
import Definitions.Def_ReplParity_IsReplicable
import Definitions.Def_ReplParity_IsRealizablyPAC
import Definitions.Def_ReplParity_runLearner
import Definitions.Def_ReplParity_Supplement_IsReplicableOnRealizable
import Definitions.Def_ReplParity_Supplement_pnLearner

set_option autoImplicit false

namespace ReplParity

namespace Supplement

/-- **Statements 1 and 3 of Theorem 5.3: uniform polynomial-time learners for `P_n` at the rate
`n² polylog/(ερ²) + O(log(1/δ)/ε)`.** Shen, Zhong, *Replicable Parity Learning: Cubic Sample
Complexity and a Geometric Characterization*, STOC 2027 submission (manuscript sha256 40424491…),
Theorem 5.3, p.26 (PDF p.28):
"1. For every n ≥ 1 and all rational 0 < ε, δ, ρ < 1/2, there is a uniform polynomial-time
finite-bit learner for P_n with m ≤ Cn²/(ερ²) polylog(n, 1/ε, 1/ρ) + C log(1/δ)/ε samples, which is
realizably (ε, δ)-PAC and ρ-replicable on realizable distributions. …
3. The learners of statement 1 exist with ρ-replicability on every labeled distribution."

`PnRateLearners every` asserts: there are a constant `C`, an exponent `k`, a sample size
`m(n, ε, δ, ρ)`, a seed length `R(n, ε, δ, ρ)` and one total function `A` such that
1. `A` is computed in polynomial time by a Mathlib `TM2` machine on the base mission's fixed binary
   encodings `encIn`, `encOut`;
2. `R ≤ c (n + m + |ε| + |δ| + |ρ|)^{k′} + c` (encoding lengths `|·| = ratSize`);
3. for every `n ≥ 1` and rationals `0 < ε, δ, ρ < 1/2`:
   * `m ≤ C n²/(ερ²) · (1 + log n + log(1/ε) + log(1/ρ))^k + C log(1/δ)/ε`;
   * every output is `⊥` or an `n`-bit truth table;
   * the learner `pnLearner A n ε δ ρ` is realizably `(ε, δ)`-PAC for `P_n` (all functions
     `Fin n → ZMod 2`);
   * if `every = false` it is ρ-replicable on the distributions realizable by `P_n`
     (statement 1); if `every = true` it is ρ-replicable on every labeled distribution on
     `Fin n × ZMod 2` (statement 3).

**Formalization Note.** "Uniform" is one machine for all `n, ε, δ, ρ` (they are part of its
input), and `C, k, m, R, A` are chosen before `n, ε, δ, ρ`, as in the base goal
`ReplParity.theorem_3_6`. A factor `polylog(n, 1/ε, 1/ρ)` bounded by a fixed polynomial in
`log n, log(1/ε), log(1/ρ)` (§2, p.10) is written `(1 + log n + log(1/ε) + log(1/ρ))^k`: these logs
are nonnegative in the parameter range, so every such polynomial is at most a constant times this
power, and the constant goes into `C`. -/
def PnRateLearners (every : Bool) : Prop :=
  ∃ C : ℝ, ∃ k : ℕ, ∃ m R : ℕ → ℚ → ℚ → ℚ → ℕ, ∃ A : LInput → Option (List Bool),
    Nonempty (Turing.TM2ComputableInPolyTime encIn encOut A) ∧
    (∃ k' c : ℕ, ∀ (n : ℕ) (ε δ ρ : ℚ),
      R n ε δ ρ ≤ c * (n + m n ε δ ρ + ratSize ε + ratSize δ + ratSize ρ) ^ k' + c) ∧
    ∀ n : ℕ, 1 ≤ n → ∀ ε δ ρ : ℚ, 0 < ε → ε < 1 / 2 → 0 < δ → δ < 1 / 2 → 0 < ρ → ρ < 1 / 2 →
      ((m n ε δ ρ : ℝ) ≤
          C * (n : ℝ) ^ 2 / ((ε : ℝ) * (ρ : ℝ) ^ 2) *
              (1 + Real.log n + Real.log (1 / (ε : ℝ)) + Real.log (1 / (ρ : ℝ))) ^ k +
            C * Real.log (1 / (δ : ℝ)) / ε) ∧
      (∀ (S : Fin (m n ε δ ρ) → Fin n × ZMod 2) (r : Fin (R n ε δ ρ) → Bool),
        runLearner A n ε δ ρ (fun i => toExample (S i)) r = none ∨
          ∃ l : List Bool, runLearner A n ε δ ρ (fun i => toExample (S i)) r = some l ∧
            l.length = n) ∧
      IsRealizablyPAC (Set.univ : Set (Fin n → ZMod 2))
        (fun (S : Fin (m n ε δ ρ) → Fin n × ZMod 2) (r : Fin (R n ε δ ρ) → Bool) =>
          pnLearner A n ε δ ρ S r) (ε : ℝ) (δ : ℝ) ∧
      (if every then
        IsReplicable
          (fun (S : Fin (m n ε δ ρ) → Fin n × ZMod 2) (r : Fin (R n ε δ ρ) → Bool) =>
            pnLearner A n ε δ ρ S r) (ρ : ℝ)
      else
        IsReplicableOnRealizable (Set.univ : Set (Fin n → ZMod 2))
          (fun (S : Fin (m n ε δ ρ) → Fin n × ZMod 2) (r : Fin (R n ε δ ρ) → Bool) =>
            pnLearner A n ε δ ρ S r) (ρ : ℝ))

end Supplement

end ReplParity
Source
Shen, Zhong, Replicable Parity Learning: Cubic Sample Complexity and a Geometric Characterization, STOC 2027 submission (manuscript sha256 40424491d00eef39c790dd41b7557e0ffdf9de2d14d95ddcd611aeacb0f77a50), Theorem 5.3 statements 1 and 3, p.26 (PDF p.28); finite-bit model §2.2, p.11 (PDF p.13); polylog convention §2, p.10 (PDF p.12)

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