Documentation

LeanMlir.Proofs.Foundation.MLP

MLP VJP Proofs #

Formal VJP correctness for the layers of a 3-layer MLP. All definitions over ℝ, proofs use Mathlib's Finset.sum.

noncomputable def Proofs.dense {m n : ℕ} (W : Mat m n) (b : Vec n) (x : Vec m) :
Vec n

Affine layer x ↦ xW + b in the row-vector convention: W : Mat m n maps Vec m → Vec n, and W i j connects input i to output j.

Equations
Instances For
    theorem Proofs.pdiv_dense {m n : ℕ} (W : Mat m n) (b : Vec n) (x : Vec m) (i : Fin m) (j : Fin n) :
    pdiv (dense W b) x i j = W i j

    Dense Jacobian — ∂(W·x + b)_j/∂x_i = W_{ij}. dense W b is the linear map x ↦ (Σ_i x_i W_{ij})_j plus the constant b, so pdiv_of_affine reads the entry off the basis vector and the Kronecker sum collapses.

    theorem Proofs.pdiv_dense_W {m n : ℕ} (b : Vec n) (x : Vec m) (W : Mat m n) (i : Fin m) (j' j : Fin n) :
    pdiv (fun (v : Vec (m * n)) => dense (Mat.unflatten v) b x) W.flatten (finProdFinEquiv (i, j')) j = if j = j' then x i else 0

    Jacobian of dense wrt W — ∂dense(W, b, x)_j/∂W_{i, j'} = x_i·δ(j, j'). Over the flatten bijection v ↦ dense (unflatten v) b x is linear in v plus the constant b (pdiv_of_affine). Symmetric counterpart to pdiv_dense.

    noncomputable def Proofs.denseHasVJP {m n : ℕ} (W : Mat m n) (b : Vec n) :

    Dense VJP — proved.

    Equations
    Instances For
      noncomputable def Proofs.mnistLinear {m n : ℕ} (W : Mat m n) (b : Vec n) :
      Vec m → Vec n

      The Chapter-1 demo model: a linear classifier is a single dense layer.

      Equations
      Instances For
        theorem Proofs.mnistLinearHasVJP_correct {m n : ℕ} (W : Mat m n) (b : Vec n) (x : Vec m) (dy : Vec n) (i : Fin m) :
        (denseHasVJP W b).backward x dy i = ∑ j : Fin n, pdiv (mnistLinear W b) x i j * dy j

        denseHasVJP's correct field, restated for mnistLinear so it can be cited by name.

        theorem Proofs.dense_differentiable {m n : ℕ} (W : Mat m n) (b : Vec n) :

        Dense is everywhere differentiable. dense W b is affine in x, hence smooth; this is the underlying Differentiable ℝ statement that vjpCompAt needs when composing through dense layers.

        theorem Proofs.denseWeightGrad_correct {m n : ℕ} (W : Mat m n) (b : Vec n) (x : Vec m) (dy : Vec n) (i : Fin m) (j : Fin n) :
        Mat.outer x dy i j = ∑ k : Fin n, pdiv (fun (v : Vec (m * n)) => dense (Mat.unflatten v) b x) W.flatten (finProdFinEquiv (i, j)) k * dy k

        Dense weight gradient is the outer product.

        Mat.outer x dy is the cotangent-contracted Jacobian of dense(W, b, x) with respect to W, at every index.

        (Mat.outer x dy) i j = ∑ k, pdiv (…) (Mat.flatten W) (fPF (i, j)) k · dy k

        theorem Proofs.pdiv_dense_b {m n : ℕ} (W : Mat m n) (b : Vec n) (x : Vec m) (i j : Fin n) :
        pdiv (fun (b' : Vec n) => dense W b' x) b i j = if i = j then 1 else 0

        Dense bias gradient is identity.

        ∂ dense(W, b, x)_j / ∂ b_{j'} = δ(j, j'), so the bias backward is just dy itself: b' ↦ dense W b' x is the identity plus a constant (pdiv_of_affine).

        theorem Proofs.denseBiasGrad_correct {m n : ℕ} (W : Mat m n) (b : Vec n) (x : Vec m) (dy : Vec n) (i : Fin n) :
        dy i = ∑ j : Fin n, pdiv (fun (b' : Vec n) => dense W b' x) b i j * dy j
        noncomputable def Proofs.denseWeightGrad {m n : ℕ} (x : Vec m) (dy : Vec n) :
        Mat m n

        Dense weight backward — named accessor. dW = x ⊗ dy (outer product).

        Equations
        Instances For
          def Proofs.denseBiasGrad {n : ℕ} (dy : Vec n) :
          Vec n

          Dense bias backward — named accessor. db = dy.

          Equations
          Instances For
            noncomputable def Proofs.relu (n : ℕ) (x : Vec n) :
            Vec n

            ReLU, coordinatewise: x i if x i > 0, else 0.

            Equations
            Instances For
              theorem Proofs.relu_apply_eq_max {n : ℕ} (x : Vec n) (i : Fin n) :
              relu n x i = max (x i) 0

              relu is max · 0, coordinatewise.

              theorem Proofs.relu_nonneg (n : ℕ) (v : Vec n) (k : Fin n) :
              0 ≤ relu n v k

              ReLU output is always nonnegative.

              theorem Proofs.relu_entry_lipschitz (n : ℕ) (u v : Vec n) (k : Fin n) :
              |relu n u k - relu n v k| ≤ |u k - v k|

              ReLU is entrywise 1-Lipschitz — what lets a drift (or a rounding error) pass through a kinked layer unamplified.

              theorem Proofs.pdiv_of_hasFDerivAt_mask {n : ℕ} (f : Vec n → Vec n) (x : Vec n) (p : Fin n → Prop) [DecidablePred p] (hf : HasFDerivAt f (ContinuousLinearMap.pi fun (k : Fin n) => if p k then ContinuousLinearMap.proj k else 0) x) (i j : Fin n) :
              pdiv f x i j = if i = j then if p i then 1 else 0 else 0

              The Jacobian of a diagonal 0/1 mask. If f has, at x, the derivative that keeps coordinate k when p k and zeroes it otherwise, its pdiv is the diagonal indicator of p. relu and relu6 at a smooth point are both this.

              noncomputable def Proofs.reluLinearPart (n : ℕ) (x : Vec n) :

              ReLU's local linear part at a smooth point — the diagonal indicator CLM. At each coordinate k, projects to y k if x k > 0, otherwise zero. Two smooth points with the same sign pattern share this same CLM.

              Equations
              Instances For
                @[simp]
                theorem Proofs.reluLinearPart_apply (n : ℕ) (x y : Vec n) (k : Fin n) :
                (reluLinearPart n x) y k = if x k > 0 then y k else 0
                theorem Proofs.relu_hasFDerivAt (n : ℕ) (x : Vec n) (h_smooth : ∀ (k : Fin n), x k ≠ 0) :

                ReLU is differentiable at smooth points. Near x every coordinate keeps its sign (finitely many strict inequalities persist, Filter.eventually_all), so relu n agrees with reluLinearPart n x on a neighbourhood. EventuallyEq promotes the CLM's HasFDerivAt to ReLU's.

                theorem Proofs.relu_differentiableAt_of_smooth (n : ℕ) (x : Vec n) (h_smooth : ∀ (k : Fin n), x k ≠ 0) :

                ReLU is DifferentiableAt at smooth points. Corollary of relu_hasFDerivAt; lets vjpCompAt chain through ReLU.

                theorem Proofs.pdiv_relu (n : ℕ) (x : Vec n) (h_smooth : ∀ (k : Fin n), x k ≠ 0) (i j : Fin n) :
                pdiv (relu n) x i j = if i = j then if x i > 0 then 1 else 0 else 0

                ReLU partial derivative — proved via relu_hasFDerivAt and direct evaluation at basisVec i.

                noncomputable def Proofs.reluHasVJP (n : ℕ) :

                ReLU bundled VJP — canonical (junk-at-kink) witness.

                HasVJP.correct is satisfied by the canonical pdiv-derived backward: at smooth points it is the diagonal indicator (per pdiv_relu); at points where some coordinate is zero, pdiv (relu n) x agrees with fderiv's junk default of 0, so the canonical backward is 0 there too — the witness is HasVJP.canonical, whose correct holds by rfl.

                The codegen (MlirCodegen.lean) emits the standard subgradient formula if x > 0 then dy else 0 instead, which agrees with the canonical witness at smooth points and differs at the kinks (the convention relu'(0) := 0 used by every ML framework). The smooth-point agreement is formal: see relu_codegen_matches_canonical below. The Lean-vs-codegen gap at the kinks is the codegen trust boundary — see LeanMlir/Proofs/README.md.

                Equations
                Instances For
                  theorem Proofs.relu_codegen_matches_canonical (n : ℕ) (x : Vec n) (h_smooth : ∀ (k : Fin n), x k ≠ 0) (dy : Vec n) (i : Fin n) :
                  (reluHasVJP n).backward x dy i = if x i > 0 then dy i else 0

                  Bridge: reluHasVJP's canonical backward matches the codegen formula at smooth points.

                  At any point where no coordinate of x is zero, the canonical pdiv-derived backward ∑ j, pdiv (relu n) x i j * dy j collapses to the framework subgradient if x i > 0 then dy i else 0 that MlirCodegen.lean actually emits. Closes the smooth-point half of the codegen trust boundary — what's left is just the kink convention.

                  noncomputable def Proofs.reluHasVJPAt (n : ℕ) (x : Vec n) (h_smooth : ∀ (k : Fin n), x k ≠ 0) :

                  ReLU pointwise VJP — no canonical-witness escape.

                  Constructs HasVJPAt (relu n) x at a smooth point. The backward is the codegen-shape if x i > 0 then dy i else 0 directly; the correct field is a real proof via pdiv_relu (the smooth-point Jacobian) + sum-collapse, not rfl.

                  Equations
                  Instances For
                    noncomputable def Proofs.softmax (c : ℕ) (z : Vec c) :
                    Vec c

                    Softmax over c classes: exp (z j) / Σ_k exp (z k).

                    Equations
                    Instances For
                      noncomputable def Proofs.oneHot (c : ℕ) (label : Fin c) :
                      Vec c

                      The one-hot vector of label over c classes.

                      Equations
                      Instances For
                        noncomputable def Proofs.crossEntropy (c : ℕ) (logits : Vec c) (label : Fin c) :

                        Cross-entropy at a hard label: −log (softmax logits)_label.

                        Equations
                        Instances For
                          theorem Proofs.softmax_apply (c : ℕ) (z : Vec c) (j : Fin c) :
                          softmax c z j = Real.exp (z j) / ∑ k : Fin c, Real.exp (z k)
                          theorem Proofs.softmax_pos {c : ℕ} (z : Vec c) (j : Fin c) :
                          0 < softmax c z j
                          theorem Proofs.softmax_nonneg {c : ℕ} (z : Vec c) (j : Fin c) :
                          0 ≤ softmax c z j
                          theorem Proofs.softmax_le_one {c : ℕ} (z : Vec c) (j : Fin c) :
                          softmax c z j ≤ 1
                          theorem Proofs.sum_softmax {c : ℕ} [NeZero c] (z : Vec c) :
                          ∑ j : Fin c, softmax c z j = 1

                          The softmax entries sum to one (over a nonempty class set).

                          theorem Proofs.oneHot_apply (c : ℕ) (label j : Fin c) :
                          oneHot c label j = if j = label then 1 else 0
                          theorem Proofs.crossEntropy_def (c : ℕ) (logits : Vec c) (label : Fin c) :
                          crossEntropy c logits label = -Real.log (softmax c logits label)
                          noncomputable def Proofs.mlpForward {d₀ d₁ d₂ d₃ : ℕ} (W₀ : Mat d₀ d₁) (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) :
                          Vec d₀ → Vec d₃

                          The three-layer MLP forward: dense → relu → dense → relu → dense.

                          Equations
                          Instances For
                            noncomputable def Proofs.mlpHasVJP {d₀ d₁ d₂ d₃ : ℕ} (W₀ : Mat d₀ d₁) (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) :
                            HasVJP (mlpForward W₀ b₀ W₁ b₁ W₂ b₂)

                            MLP composition VJP — canonical witness.

                            The MLP forward composes dense W b (everywhere Differentiable) with relu (non-Differentiable at the kinks). vjpComp would require Differentiable ℝ (relu n), which doesn't hold globally, so the chain-rule route is blocked. The canonical pdiv-derived backward inhabits HasVJP.correct directly via rfl — the codegen substitutes the subgradient formula at the kinks (see LeanMlir/Proofs/README.md for the trust-boundary discussion).

                            Equations
                            Instances For
                              noncomputable def Proofs.mlpHasVJPAt {d₀ d₁ d₂ d₃ : ℕ} (W₀ : Mat d₀ d₁) (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (x : Vec d₀) (h_smooth_0 : ∀ (k : Fin d₁), dense W₀ b₀ x k ≠ 0) (h_smooth_1 : ∀ (k : Fin d₂), dense W₁ b₁ (relu d₁ (dense W₀ b₀ x)) k ≠ 0) :
                              HasVJPAt (mlpForward W₀ b₀ W₁ b₁ W₂ b₂) x

                              MLP pointwise VJP — no canonical-witness escape.

                              Constructs HasVJPAt (mlpForward …) x by chaining vjpCompAt through dense → relu_at → dense → relu_at → dense. Requires the intermediate pre-activations dense W₀ b₀ x and dense W₁ b₁ z₀ to avoid zero (no coordinate ties the ReLU kink) — exactly the "smooth input" condition. Unlike the canonical mlpHasVJP, the backward here is built by the chain rule.

                              Equations
                              • One or more equations did not get rendered due to their size.
                              Instances For

                                Public correctness theorems for the canonical-witness defs #

                                Each HasVJP def above bundles a backward function with a .correct field; these _correct theorems expose that field as a top-level proposition so consumers (downstream code, tests/comparator/, doc-gen4) can refer to the contract directly without reaching into record internals.

                                theorem Proofs.reluHasVJP_correct (n : ℕ) (x dy : Vec n) (i : Fin n) :
                                (reluHasVJP n).backward x dy i = ∑ j : Fin n, pdiv (relu n) x i j * dy j

                                Public correctness theorem for reluHasVJP: the canonical witness's backward equals the pdiv-contracted Jacobian by definition.

                                theorem Proofs.mlpHasVJP_correct {d₀ d₁ d₂ d₃ : ℕ} (W₀ : Mat d₀ d₁) (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (x : Vec d₀) (dy : Vec d₃) (i : Fin d₀) :
                                (mlpHasVJP W₀ b₀ W₁ b₁ W₂ b₂).backward x dy i = ∑ j : Fin d₃, pdiv (mlpForward W₀ b₀ W₁ b₁ W₂ b₂) x i j * dy j

                                Public correctness theorem for mlpHasVJP: same pattern as reluHasVJP_correct, lifted to the three-layer MLP forward.

                                theorem Proofs.reluHasVJPAt_correct (n : ℕ) (x : Vec n) (h_smooth : ∀ (k : Fin n), x k ≠ 0) (dy : Vec n) (i : Fin n) :
                                (reluHasVJPAt n x h_smooth).backward dy i = ∑ j : Fin n, pdiv (relu n) x i j * dy j

                                Public correctness theorem for reluHasVJPAt — the pointwise (smooth-input) variant. Unlike reluHasVJP_correct, this wrapper's underlying .correct field is a real proof (pdiv_relu + sum-collapse), not rfl; the wrapper exposes it as a top-level proposition for tests/comparator/ re-verification.

                                theorem Proofs.mlpHasVJPAt_correct {d₀ d₁ d₂ d₃ : ℕ} (W₀ : Mat d₀ d₁) (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (x : Vec d₀) (h_smooth_0 : ∀ (k : Fin d₁), dense W₀ b₀ x k ≠ 0) (h_smooth_1 : ∀ (k : Fin d₂), dense W₁ b₁ (relu d₁ (dense W₀ b₀ x)) k ≠ 0) (dy : Vec d₃) (i : Fin d₀) :
                                (mlpHasVJPAt W₀ b₀ W₁ b₁ W₂ b₂ x h_smooth_0 h_smooth_1).backward dy i = ∑ j : Fin d₃, pdiv (mlpForward W₀ b₀ W₁ b₁ W₂ b₂) x i j * dy j

                                Public correctness theorem for mlpHasVJPAt — the pointwise variant composed via vjpCompAt through dense → relu_at → dense → relu_at → dense. The underlying .correct field chains real chain-rule proofs (no rfl escape at the ReLU kinks).

                                noncomputable def Proofs.relu6 (n : ℕ) (x : Vec n) :
                                Vec n

                                ReLU6, coordinatewise: min (max (x i) 0) 6 (MobileNetV2's activation).

                                Equations
                                Instances For
                                  noncomputable def Proofs.relu6LinearPart (n : ℕ) (x : Vec n) :

                                  ReLU6's local linear part at a smooth point: projects to y k when 0 < x k < 6, otherwise zero.

                                  Equations
                                  Instances For
                                    @[simp]
                                    theorem Proofs.relu6LinearPart_apply (n : ℕ) (x y : Vec n) (k : Fin n) :
                                    (relu6LinearPart n x) y k = if 0 < x k ∧ x k < 6 then y k else 0
                                    theorem Proofs.relu6_hasFDerivAt (n : ℕ) (x : Vec n) (h_smooth : ∀ (k : Fin n), x k ≠ 0 ∧ x k ≠ 6) :
                                    theorem Proofs.relu6_differentiableAt_of_smooth (n : ℕ) (x : Vec n) (h_smooth : ∀ (k : Fin n), x k ≠ 0 ∧ x k ≠ 6) :
                                    theorem Proofs.pdiv_relu6 (n : ℕ) (x : Vec n) (h_smooth : ∀ (k : Fin n), x k ≠ 0 ∧ x k ≠ 6) (i j : Fin n) :
                                    pdiv (relu6 n) x i j = if i = j then if 0 < x i ∧ x i < 6 then 1 else 0 else 0
                                    noncomputable def Proofs.relu6HasVJPAt (n : ℕ) (x : Vec n) (h_smooth : ∀ (k : Fin n), x k ≠ 0 ∧ x k ≠ 6) :
                                    Equations
                                    Instances For
                                      theorem Proofs.relu6_id_window (n : ℕ) (y : Vec n) (hy : ∀ (k : Fin n), 0 < y k ∧ y k < 6) :
                                      relu6 n y = y

                                      ReLU6 is the identity inside its window. Wherever every coordinate is strictly inside (0,6), min (max · 0) 6 does nothing — the step every structural witness takes to collapse a relu6 stage to its BatchNorm. Stated at the top level rather than inside a witness namespace: it is a fact about the op, and BatchSeal's consumers outlive any one witness.

                                      ReLU6 is continuous — min (max · 0) 6 coordinatewise. The peer of relu_continuous (below), for the ray argument of a relu6 net's seal.

                                      relu is continuous everywhere — it is max · 0; only its derivative has a kink.

                                      theorem Proofs.relu_id_of_pos {n : ℕ} {v : Vec n} (hv : ∀ (i : Fin n), 0 < v i) :
                                      relu n v = v

                                      ReLU is the identity on a strictly-positive vector. Discharges the ReLU-as-identity steps that fold the composition into a plain conv stack at a smooth (everywhere-positive) point.