Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniform polynomial-time learning with evaluators and generators

Definition
AutoregressiveCompression_Main_Supplement_Learning

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorydistribution-learninginformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let D=(Dn)n∈N\mathcal D=(\mathcal D_n)_{n\in\mathbb N}D=(Dn​)n∈N​ be any size-indexed class of string distributions over a finite alphabet. A learner uses one finite Turing machine, one polynomial running-time bound, and fixed polynomial sample and fair-coin bounds. From unary n,a,bn,a,bn,a,b, where a,b≥2a,b\ge2a,b≥2, samples, and its coins, it outputs an explicitly encoded circuit. On every possible sample block and coin tape of these lengths the output must be a normalized evaluator, or a generator for the target length, respectively. It receives no description or probability table of the target distribution.

Writing ε=1/a\varepsilon=1/aε=1/a and δ=1/b\delta=1/bδ=1/b, one accuracy mode is fixed for the entire learner: either KL divergence in bits is at most ε\varepsilonε with probability at least 1−δ1-\delta1−δ, or total variation distance is at most ε\varepsilonε with that probability. Thus

Pr⁡[KL⁡2(D∥QH)≤ε]≥1−δorPr⁡[Δtv(D,QH)≤ε]≥1−δ.\Pr[\operatorname{KL}_2(D\Vert Q_H)\le\varepsilon]\ge1-\delta\quad\text{or}\quad\Pr[\Delta_{\rm tv}(D,Q_H)\le\varepsilon]\ge1-\delta.Pr[KL2​(D∥QH​)≤ε]≥1−δorPr[Δtv​(D,QH​)≤ε]≥1−δ.

The generic circuit-learning contract is instantiated separately with the two actual circuit encodings and their evaluated masses. It neither assumes nor asserts an interconversion between tasks. Its uniform witnesses precede every size, law, accuracy and confidence parameter. Infinite KL is retained by the published extended-real convention. These predicates extend the existing seven task interfaces without redefining them.

Definition code
import Mathlib
import Definitions.Def_AutoregressiveCompression_Main_Supplement_Representations

noncomputable section

namespace AutoregressiveCompression.Main.Supplement

open scoped Classical

/-! Definition 4.5, printed pp.17–18 / PDF pp.19–20.
One finite machine outputs a circuit description from samples, unary parameters
and its fair coins. All polynomial bounds are fixed before n and the target.
The two modes of accuracy are alternatives for the whole learner, not per target.
-/

/-- Distribution learning with a specified, independently defined hypothesis
representation. `valid` expresses output typing/normalization only; `weights`
is the evaluated law, not a promise of accuracy or a task interconversion. -/
def CircuitLearnable {Sym H : Type} [Fintype Sym] (𝒟 : DistributionClass Sym)
    (encode : H → Bits) (valid : H → ℕ → Prop)
    (weights : H → (N : ℕ) → Word Sym N → ℝ) : Prop :=
  ∃ (L : Program) (time : Polynomial ℕ) (ρ r : MvPolynomial (Fin 3) ℕ)
    (hyp : ℕ → ℕ → ℕ → List (List Sym) → Bits → H),
    (∀ n, ∀ D ∈ 𝒟.members n, ∀ a b : ℕ, 2 ≤ a → 2 ≤ b →
      ∀ (xs : Fin (eval3 ρ n a b) → Word Sym D.length)
        (ω : Fin (eval3 r n a b) → Bool),
      L.OutputsWithin
        (frame [unary n, unary a, unary b, blockBits (blockList xs), coinBits ω])
        (encode (hyp n a b (blockList xs) (coinBits ω))) (time.eval (n + a + b)) ∧
      valid (hyp n a b (blockList xs) (coinBits ω)) D.length) ∧
    ((∀ n, ∀ D ∈ 𝒟.members n, ∀ a b : ℕ, 2 ≤ a → 2 ≤ b →
      1 - 1 / (b : ℝ) ≤ eventProbability
        (samplesAndCoins D.law (eval3 ρ n a b) (eval3 r n a b))
        (fun p => klBitsWeights D.law
          (weights (hyp n a b (blockList p.1) (coinBits p.2)) D.length) ≤
            ((1 / (a : ℝ) : ℝ) : EReal))) ∨
     (∀ n, ∀ D ∈ 𝒟.members n, ∀ a b : ℕ, 2 ≤ a → 2 ≤ b →
      1 - 1 / (b : ℝ) ≤ eventProbability
        (samplesAndCoins D.law (eval3 ρ n a b) (eval3 r n a b))
        (fun p => tvWeights D.law
          (weights (hyp n a b (blockList p.1) (coinBits p.2)) D.length) ≤ 1 / (a : ℝ))))

/-- Definition 4.5(a), using actual rational evaluator circuits. -/
def EvaluatorLearnable {Sym : Type} [Fintype Sym] (𝒟 : DistributionClass Sym) : Prop :=
  CircuitLearnable 𝒟 Circuit.bits (IsEvaluator (Sym := Sym)) evaluatorMass

/-- Definition 4.5(b), using actual finite vector-output circuits with fair seeds.
Only samples of the target are inputs to the learning program. -/
def GeneratorLearnable {Sym : Type} [Fintype Sym] (𝒟 : DistributionClass Sym) : Prop :=
  CircuitLearnable 𝒟 SamplerCode.bits (IsGeneratorAt (Sym := Sym)) SamplerCode.modelMass

end AutoregressiveCompression.Main.Supplement
Source
Shuichi Hirahara, Mikito Nanashima, STOC 2027 submission #793 (October 2026); source.pdf, SHA-256 31e908b0cf51447e89626d9dc6d947c279aec5642ec7b320ceb07ec9b1348341; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/793.pdf, Definition 4.5, printed pp.17–18 / PDF pp.19–20

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