Documentation

LeanMlir.Proofs.Float.BnFloatBridge

ℝ→Float32 bridge for BatchNorm: the inverse-stddev keystone #

Over FloatBridge's relative-error model (sums, products, exact max), BatchNorm adds one new numerical op: the inverse standard deviation istd = 1/√(σ²+ε). The relative-error model |rnd x − x| ≤ u·|x| does not cover rsqrt (a GPU rsqrt, like exp, has no IEEE spec), so — exactly as the softmax bridge models exp by a supplied fexp with an eexp accuracy hypothesis — we model the float inverse-stddev by a supplied fistd : ℝ → ℝ with a relative accuracy ers.

The keystone is that t ↦ 1/√t is Lipschitz on [ε, ∞) with constant 1/(2ε√ε) (rsqrt_lipschitz, proved by the algebraic identity 1/√a − 1/√b = (b−a)/((√a+√b)·√a·√b) and the ε-floor). Composing the rsqrt accuracy with this Lipschitz bound gives bnIstd_close: the float istd is within ers/√ε + e_var/(2ε√ε) of the certified bnIstd, where e_var is whatever budget the (standard, Higham) variance rounding supplies. This is the BN analog of the exp accuracy handoff. The per-example bnForward rounding budget composes it with the Higham mean/variance budgets (FloatModel.bnMean_close, FloatModel.bnVar_close) and the normalize chain (FloatModel.bnForward_close_of), all in this file.

theorem Proofs.rsqrt_lipschitz {a b ε : ℝ} (hε : 0 < ε) (ha : ε ≤ a) (hb : ε ≤ b) :
|1 / √a - 1 / √b| ≤ |a - b| / (2 * ε * √ε)

t ↦ 1/√t is Lipschitz on [ε, ∞) with constant 1/(2·ε·√ε) = 1/(2ε^{3/2}). Proof: the algebraic identity 1/√a − 1/√b = (b−a)/((√b+√a)·√a·√b), then the ε-floor bounds the denominator below by 2ε√ε. The keystone for pushing a variance-rounding error through the BN inverse-stddev.

theorem Proofs.bnIstd_close_at {n : ℕ} {ε ers evar fvarε V : ℝ} (x : Vec n) (fistd : ℝ → ℝ) (hV0 : 0 < V) (hers : 0 ≤ ers) (hVfv : V ≤ fvarε) (hVbn : V ≤ bnVar n x + ε) (hrs : |fistd fvarε - 1 / √fvarε| ≤ ers * (1 / √fvarε)) (hclose : |fvarε - (bnVar n x + ε)| ≤ evar) :
|fistd fvarε - bnIstd n x ε| ≤ ers / √V + evar / (2 * V * √V)

BN inverse-stddev budget at the OPERATING POINT (a-posteriori). The general form of bnIstd_close (below): the 1/√ Lipschitz floor is a variance lower bound V ≤ σ²+ε (both float and real), not the ε-floor. rsqrt_lipschitz is floor-agnostic, so the bound becomes ers/√V + evar/(2V√V) — and since the measured σ² is O(1) (never near 0), V ≈ σ²+ε ≫ ε makes this ~(σ²/ε)^{3/2} tighter than the ε-floor bnIstd_close (empirically ~10⁷× on the CIFAR-BN probe, scripts/certs/cifar_bn_margin_probe.py). A conditional bound under hVfv, hVbn, hrs, hclose; apart from bnIstd_close (its V = ε case) nothing in the repo applies it.

theorem Proofs.bnIstd_close {n : ℕ} {ε ers evar fvarε : ℝ} (x : Vec n) (fistd : ℝ → ℝ) (hε : 0 < ε) (hers : 0 ≤ ers) (hfv : ε ≤ fvarε) (hrs : |fistd fvarε - 1 / √fvarε| ≤ ers * (1 / √fvarε)) (hclose : |fvarε - (bnVar n x + ε)| ≤ evar) :
|fistd fvarε - bnIstd n x ε| ≤ ers / √ε + evar / (2 * ε * √ε)

BN inverse-stddev rounding budget (the keystone). Model the GPU inverse-stddev by a supplied fistd with relative accuracy ers (|fistd t − 1/√t| ≤ ers·(1/√t)), evaluated at the rounded fvarε ≥ ε (the float σ²+ε, within evar of the real σ²+ε). Then the float istd is within ers/√ε + evar/(2ε√ε) of the certified bnIstd. The first term is the rsqrt accuracy lifted to the ε-floor; the second is the variance rounding pushed through rsqrt_lipschitz. The BN analog of the softmax exp-accuracy handoff; bnIstd_close_at at the floor V = ε.

noncomputable def Proofs.FloatModel.bnForwardF {n : ℕ} (M : FloatModel) (γ β fμ fistdv : ℝ) (x : Vec n) :
Vec n

The float BN forward (per-example, supplied mean fμ and inverse-stddev fistdv): yᵢ = fl(γ ⊙ fl(fl(xᵢ ⊖ fμ) ⊙ fistdv) ⊕ β) — every +/−/· rounded; γ/β are the stored (exact) parameters.

Equations
Instances For
    noncomputable def Proofs.bnNormBudget (u D S G Bbnd emean eistd : ℝ) :

    The closed-form budget of the BN normalize chain: a sub rounding, two muls (mulErr), and the final add rounding, threading the upstream mean error emean and inverse-stddev error eistd.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      theorem Proofs.FloatModel.bnForward_close_of {n : ℕ} (M : FloatModel) {ε γ β fμ fistdv emean eistd D S G Bbnd : ℝ} (x : Vec n) (i : Fin n) (hmean : |fμ - bnMean n x| ≤ emean) (histd : |fistdv - bnIstd n x ε| ≤ eistd) (hD : |x i - bnMean n x| ≤ D) (hSabs : |bnIstd n x ε| ≤ S) (hγ : |γ| ≤ G) (hβ : |β| ≤ Bbnd) :
      |M.bnForwardF γ β fμ fistdv x i - bnForward n ε γ β x i| ≤ bnNormBudget M.u D S G Bbnd emean eistd

      BN forward closeness, normalize chain. Given the mean within emean and the inverse-stddev within eistd of the certified values (the latter from bnIstd_close), plus magnitude bounds (|xᵢ−μ| ≤ D, |istd| ≤ S, |γ| ≤ G, |β| ≤ Bbnd), the rounded BN forward output is within bnNormBudget of the real bnForward per coordinate. The output half of the per-example BN bridge; compose with bnIstd_close (istd) and the mean/var Higham budgets.

      theorem Proofs.FloatModel.bnMean_close_of {n : ℕ} (M : FloatModel) {fsum : Vec n → ℝ} {γn A : ℝ} (x : Vec n) (hn : 0 < n) (hγn0 : 0 ≤ γn) (hsc : |fsum x - ∑ i : Fin n, x i| ≤ γn * ∑ i : Fin n, |x i|) (hA : ∀ (i : Fin n), |x i| ≤ A) :
      |M.div (fsum x) ↑n - bnMean n x| ≤ M.u * ((γn + 1) * A) + γn * A

      The mean reduction's budget, parameterised by the REDUCTION'S OWN SPEC. bnMean_close below is this at fsum := M.sum, the concrete LEFT FOLD — and a GPU does not reduce left to right, so a number stated through that instance is about a program we do not ship. This form takes any fsum whose forward error meets a fan-in γn (hypothesis hsc). Classically every summation order satisfies such a bound: sequential summation is the worst of them at γ = (1+u)^{n+1} − 1, and a tree's is (1+u)^{⌈log₂n⌉+1} − 1. That the shipped kernel's reduction meets hsc is the hypothesis, not proved here; given it, the proof is bnMean_close's with one hypothesis substituted.

      Note: Only the SUM is parameterised. The division by the exact width is M.div, one rounding, and there is nothing to model about it.

      theorem Proofs.FloatModel.bnMean_close {n : ℕ} (M : FloatModel) (x : Vec n) {A : ℝ} (hn : 0 < n) (hA : ∀ (i : Fin n), |x i| ≤ A) :
      |M.div (M.sum x) ↑n - bnMean n x| ≤ M.u * ((1 + M.u) ^ (n + 1) * A) + ((1 + M.u) ^ (n + 1) - 1) * A

      BN mean rounding budget. The float mean fl((Σx)/n) (rounded sum, then a rounded division by the exact n) is within u·(1+u)^{n+1}·A + ((1+u)^{n+1}−1)·A of the real bnMean, under |xᵢ| ≤ A. Standard: sum_close's fan-in γ plus one division rounding. Note: Stated at the concrete left fold M.sum; bnMean_close_of above is the form that covers the kernels we ship.

      noncomputable def Proofs.bnVarBudget (u D emean : ℝ) (n : ℕ) :

      Closed-form budget of the float variance vs bnVar. esq is the per-term centered-square error (mulErr at the centered bound D and centered error es1 = u(D+emean)+emean); γₙ is the reduction fan-in.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        theorem Proofs.FloatModel.bnVar_close {n : ℕ} (M : FloatModel) (x : Vec n) {fμ emean D : ℝ} (hn : 0 < n) (hmean : |fμ - bnMean n x| ≤ emean) (hD : ∀ (i : Fin n), |x i - bnMean n x| ≤ D) :
        |M.div (M.sum fun (i : Fin n) => M.mul (M.sub (x i) fμ) (M.sub (x i) fμ)) ↑n - bnVar n x| ≤ bnVarBudget M.u D emean n

        BN variance rounding budget. The float variance (rounded centered squares, rounded sum, rounded /n) is within bnVarBudget of the real bnVar, given the mean within emean and the centered bound |xᵢ−μ| ≤ D. The coupled Higham reduction: each centered term inherits emean (via mul_close), then a fan-in γ sum and a division rounding — the variance peer of bnMean_close.

        theorem Proofs.FloatModel.bnForward_close {n : ℕ} (M : FloatModel) {ε γ β evar D S G Bbnd ers fvarε A : ℝ} (x : Vec n) (i : Fin n) (fistd : ℝ → ℝ) (hn : 0 < n) (hε : 0 < ε) (hers : 0 ≤ ers) (hfv : ε ≤ fvarε) (hrs : |fistd fvarε - 1 / √fvarε| ≤ ers * (1 / √fvarε)) (hvar : |fvarε - (bnVar n x + ε)| ≤ evar) (hA : ∀ (j : Fin n), |x j| ≤ A) (hD : |x i - bnMean n x| ≤ D) (hSabs : |bnIstd n x ε| ≤ S) (hγ : |γ| ≤ G) (hβ : |β| ≤ Bbnd) :
        |M.bnForwardF γ β (M.div (M.sum x) ↑n) (fistd fvarε) x i - bnForward n ε γ β x i| ≤ bnNormBudget M.u D S G Bbnd (M.u * ((1 + M.u) ^ (n + 1) * A) + ((1 + M.u) ^ (n + 1) - 1) * A) (ers / √ε + evar / (2 * ε * √ε))

        Per-example BN forward closeness (assembled). The float BN forward at the rounded mean fl((Σx)/n) and the GPU inverse-stddev fistd fvarε is within bnNormBudget of the certified bnForward, with the mean error discharged by bnMean_close, the inverse-stddev error by the bnIstd_close keystone (the rsqrt accuracy + rsqrt_lipschitz), and the normalize chain by bnForward_close_of. fvarε's closeness to σ²+ε (hvar) is taken as a hypothesis; FloatModel.bnVar_close supplies a variance budget in the rounded-sum form.