Definition 2.5 — uniform efficient robust IAT generator with surface bound
DefinitionReplParity_Supplement_IsUniformIATGeneratorfinite-bit-modelp2o-gran-per-chapterp2o-plan-paperp2o-v1replicabilitytilings
A uniform efficient robust IAT generator with surface bound is a pair of finite-bit algorithms, a generator and its query program , such that:
- receives and rationals together with uniform random bits and runs in time polynomial in , , and the encoding lengths of ; on a query , runs in time polynomial in the same quantities and the encoding length of (so the returned label also has polynomial length); both use polynomially many random bits;
- in every output of with , is bounded by a polynomial in , , ;
- for every and rationals , with probability at least over its random bits, outputs that, run by , is a robust description (Definition 2.4) of some -IAT of .
One generator serves every , and its randomness is its own, independent of any learning data. Statement 2 of Theorem 5.3 asks for such a generator with .
Formalization Note Polynomial time is that of Mathlib's Turing machines (TM2ComputableInPolyTime) on the fixed encodings of genEncoding; is supplied in unary so that time polynomial in the input length is time polynomial in , , . The encoding lengths of enter as §2.2 requires.
Definition code
import Mathlib
import Definitions.Def_ReplParity_Supplement_IAT
import Definitions.Def_ReplParity_Supplement_genEncoding
import Definitions.Def_ReplParity_Supplement_IsRobustDescription
set_option autoImplicit false
namespace ReplParity
namespace Supplement
/-- **Definition 2.5 (Uniform efficient generator).** Shen, Zhong, *Replicable Parity Learning:
Cubic Sample Complexity and a Geometric Characterization*, STOC 2027 submission (manuscript sha256
40424491…), Definition 2.5, p.12 (PDF p.14): "A uniform efficient robust IAT generator with surface
bound A(N, γ, ζ) is a finite-bit algorithm that receives N and rationals 0 < γ, ζ < 1/2, runs in time
polynomial in N, 1/γ, and log(1/ζ), and with probability at least 1 − ζ outputs a robust description
of a (γ, A(N, γ, ζ))-IAT. In the description, log(1/η∗) is polynomial in N, 1/γ, and log(1/ζ), and
on a query q the running time and the length of the returned label are polynomial in these
quantities and in the encoding length of q. Its randomness is independent of any learning data."
`IsUniformIATGenerator G gbits Q qbits Abd` says that the generator `G` (using `gbits N γ ζ` random
bits) and its query program `Q` (using `qbits N γ ζ (qSize q)` random bits on the query `q`) form a
uniform efficient robust IAT generator with surface bound `Abd`:
1. `G` and `Q` are computed in polynomial time by Mathlib `TM2` machines on the fixed encodings
`encGenIn`/`encGenOut` and `encQIn`/`encQOut`; the unary header makes this polynomial in
`N, 1/γ, log(1/ζ)`, the encoding lengths of `γ, ζ` (and of `q`), and the random bits;
2. on the valid parameter range, both numbers of random bits are polynomial in the same quantities;
3. on that range, `log(1/η∗) ≤ c · padSize(N, γ, ζ)^k + c` for every prescribed-length
random string whose output has `η∗ > 0`;
4. for every `N ≥ 1` and rationals `0 < γ, ζ < 1/2`, with probability at least `1 − ζ` over its
random bits, `G`'s output `(d, η∗)` is a robust description (via `Q`) of some
`(γ, Abd N γ ζ)`-IAT of `ℝ^N`.
**Formalization Note.** One generator and one query program serve every `N, γ, ζ`. Mathlib's
`TM2ComputableInPolyTime` measures time in the input length, so `N + ⌈1/γ⌉ + ⌈log₂(1/ζ)⌉` is supplied
in unary (`encHeader`); the encoding lengths of `γ, ζ` enter as §2.2 requires ("polynomial in … the
encoding lengths of its parameters"). The label length is at most the input length plus the running
time of `Q`, so it is polynomial too. The generator's randomness is its own bits, independent of
any learning data. -/
def IsUniformIATGenerator (G : GenInput → GenOutput) (gbits : ℕ → ℚ → ℚ → ℕ)
(Q : QInput → Option (List ℚ)) (qbits : ℕ → ℚ → ℚ → ℕ → ℕ) (Abd : ℕ → ℚ → ℚ → ℝ) : Prop :=
Nonempty (Turing.TM2ComputableInPolyTime encGenIn encGenOut G) ∧
Nonempty (Turing.TM2ComputableInPolyTime encQIn encQOut Q) ∧
(∃ k c : ℕ, ∀ (N : ℕ), 1 ≤ N → ∀ (γ ζ : ℚ),
0 < γ → γ < 1 / 2 → 0 < ζ → ζ < 1 / 2 →
gbits N γ ζ ≤ c * (padSize N γ ζ + ratSize γ + ratSize ζ) ^ k + c) ∧
(∃ k c : ℕ, ∀ (N : ℕ), 1 ≤ N → ∀ (γ ζ : ℚ),
0 < γ → γ < 1 / 2 → 0 < ζ → ζ < 1 / 2 → ∀ s : ℕ,
qbits N γ ζ s ≤ c * (padSize N γ ζ + ratSize γ + ratSize ζ + s) ^ k + c) ∧
(∃ k c : ℕ, ∀ (N : ℕ), 1 ≤ N → ∀ (γ ζ : ℚ),
0 < γ → γ < 1 / 2 → 0 < ζ → ζ < 1 / 2 →
∀ r : Fin (gbits N γ ζ) → Bool, 0 < (G (N, γ, ζ, List.ofFn r)).2 →
Real.log (1 / ((G (N, γ, ζ, List.ofFn r)).2 : ℝ)) ≤
c * (padSize N γ ζ : ℝ) ^ k + c) ∧
∀ N : ℕ, 1 ≤ N → ∀ γ ζ : ℚ, 0 < γ → γ < 1 / 2 → 0 < ζ → ζ < 1 / 2 →
1 - (ζ : ℝ) ≤ bitProb (gbits N γ ζ) (fun r =>
∃ (L : Set (EuclideanSpace ℝ (Fin N)))
(T : EuclideanSpace ℝ (Fin N) → Set (EuclideanSpace ℝ (Fin N))),
IsIAT N γ (Abd N γ ζ) L T ∧
IsRobustDescription Q qbits N γ ζ (G (N, γ, ζ, List.ofFn r)).1
(G (N, γ, ζ, List.ofFn r)).2 L T)
end Supplement
end ReplParity
Source
Shen, Zhong, Replicable Parity Learning: Cubic Sample Complexity and a Geometric Characterization, STOC 2027 submission (manuscript sha256 40424491d00eef39c790dd41b7557e0ffdf9de2d14d95ddcd611aeacb0f77a50), Definition 2.5, p.12 (PDF p.14); finite-bit model §2.2, p.11 (PDF p.13)