Documentation

LeanMlir.Proofs.Training.SgdDescent.Mlp

Lipschitz constants for the MLP softmax-CE loss — descent through the ReLU kinks #

SgdDescent.Linear discharged sgd_descends' smoothness hypothesis for the Chapter-1 linear net. This file extends the discharge through the Chapter-2 MLP (dense → relu → dense → relu → dense), layer by layer:

The capstones mlp_hidden_sgd_descends / mlp_input_sgd_descends mirror linear_sgd_descends: an η-accurate gradient oracle (the float budgets), the margin(s) at the step radius, the small-step condition, and the two dominance conditions ⇒ one inexact SGD step on that layer's weights, at one example (x, label) with every other parameter fixed, decreases that example's cross-entropy loss by ≥ lr·‖∇L‖₂²/2. Smoothness is proven, not assumed; the oracle accuracy, the margins, the small-step and the two dominance conditions remain hypotheses. mlp_output_float_sgd_descends, mlp_hidden_float_sgd_descends and mlp_input_float_sgd_descends replace the oracle accuracy by the proven accuracy of the FloatModel binary32 gradient. Bias columns are the same argument with the layer input replaced by the constant 1 and are omitted. The joint all-layers step (every parameter moving at once, logits no longer affine in the moving parameters) is not proved here.

theorem Proofs.sign_stable_of_close {zt z c : ℝ} (hc : |zt - z| ≤ c) (hm : c < |z|) :
zt ≠ 0 ∧ (0 < zt ↔ 0 < z)

Margins freeze signs. If a value drifts by at most c and sits at distance more than c from the kink, the drifted value is still off the kink with the same sign — the ReLU mask cannot flip.

theorem Proofs.dense_input_drift {m n : ℕ} (W : Mat m n) (b : Vec n) {wb : ℝ} (hW : ∀ (i : Fin m) (j : Fin n), |W i j| ≤ wb) (u u' : Vec m) (j : Fin n) :
|dense W b u' j - dense W b u j| ≤ wb * ∑ i : Fin m, |u' i - u i|

A dense layer's output moves by at most w·‖Δinput‖₁ per entry — the ℓ1→ℓ∞ operator bound used at every dense crossing of the chain.

theorem Proofs.margin_keeps_offkink_of_drift {P n : ℕ} (Z : Vec P → Vec n) {ρ D : ℝ} (hρ : 0 ≤ ρ) (hZ : ∀ (v e : Vec P) (k : Fin n), |Z (v + e) k - Z v k| ≤ ρ * ∑ idx : Fin P, |e idx|) (v e : Vec P) (he : ∑ idx : Fin P, |e idx| ≤ D) (hm : ∀ (k : Fin n), ρ * D < |Z v k|) (t : ℝ) (ht0 : 0 ≤ t) (ht1 : t ≤ 1) (k : Fin n) :
Z (v + t • e) k ≠ 0 ∧ (0 < Z (v + t • e) k ↔ 0 < Z v k)

A per-entry drift inside the margin keeps a pre-activation off the kink along the whole segment — for any parameter map Z whose entries move by at most ρ·‖e‖₁, the margin ρ·D < |Z v k| at step radius D freezes every sign on [v, v+e].

theorem Proofs.sum_abs_flatten_cols {m n : ℕ} (d : Vec (m * n)) :
∑ j : Fin n, ∑ i : Fin m, |d (finProdFinEquiv (i, j))| = ∑ idx : Fin (m * n), |d idx|

The ℓ1 mass of a flattened weight perturbation, summed column by column, is the total ℓ1 mass — finProdFinEquiv partitions the flat index set into the columns.

theorem Proofs.dense_unflatten_drift_sum {m n : ℕ} (b : Vec n) (x : Vec m) {a : ℝ} (hx : ∀ (i : Fin m), |x i| ≤ a) (v e : Vec (m * n)) :
∑ j : Fin n, |dense (Mat.unflatten (v + e)) b x j - dense (Mat.unflatten v) b x j| ≤ a * ∑ idx : Fin (m * n), |e idx|

Summed over all coordinates, the pre-activation drift is bounded by a·‖e‖₁ total — the column masses tile the flat index set.

theorem Proofs.margin_keeps_offkink {m n : ℕ} (b : Vec n) (x : Vec m) {a D : ℝ} (ha : 0 ≤ a) (hx : ∀ (i : Fin m), |x i| ≤ a) (v e : Vec (m * n)) (he : ∑ idx : Fin (m * n), |e idx| ≤ D) (hmargin : ∀ (j : Fin n), a * D < |dense (Mat.unflatten v) b x j|) (t : ℝ) (ht0 : 0 ≤ t) (ht1 : t ≤ 1) (j : Fin n) :
dense (Mat.unflatten (v + t • e)) b x j ≠ 0 ∧ (0 < dense (Mat.unflatten (v + t • e)) b x j ↔ 0 < dense (Mat.unflatten v) b x j)

The margin keeps the pre-activation off the kink along the whole segment. With the step's ℓ1 mass at most D and inputs bounded by a, the pre-activation drifts by at most a·D — strictly inside the margin — so every point of [v, v + e] is off the kink with the original sign.

theorem Proofs.ce_dense_input_grad {d₂ d₃ : ℕ} (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (label : Fin d₃) (y : Vec d₂) (j : Fin d₂) :
pdiv (fun (z : Vec d₂) (x : Fin 1) => crossEntropy d₃ (dense W₂ b₂ z) label) y j 0 = ∑ k : Fin d₃, W₂ j k * (softmax d₃ (dense W₂ b₂ y) k - oneHot d₃ label k)

Loss input-gradient at the logits' input: ∂(CE ∘ dense W₂)/∂yⱼ = ∑ₖ W₂ⱼₖ·(softmax − onehot)ₖ — the pdiv-level form of the backward chain's dense-back step.

theorem Proofs.ce_head_relu_input_grad {d₂ d₃ : ℕ} (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (label : Fin d₃) (z : Vec d₂) (hz : ∀ (k : Fin d₂), z k ≠ 0) (j : Fin d₂) :
pdiv (fun (y : Vec d₂) (x : Fin 1) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ y)) label) z j 0 = (if z j > 0 then 1 else 0) * ∑ k : Fin d₃, W₂ j k * (softmax d₃ (dense W₂ b₂ (relu d₂ z)) k - oneHot d₃ label k)

Loss input-gradient through one ReLU — at an off-kink point the chain picks up the mask: ∂(CE ∘ dense W₂ ∘ relu)/∂zⱼ = relu'(zⱼ)·∑ₖ W₂ⱼₖ·(softmax − onehot)ₖ. The pdiv-level form of the cotangent mlpCotOut1 delivers (cf. mlpCotOut1_denote).

theorem Proofs.dense_relu_drift {m n : ℕ} (W : Mat m n) (b : Vec n) {wb : ℝ} (hw : 0 ≤ wb) (hW : ∀ (i : Fin m) (j : Fin n), |W i j| ≤ wb) (u u' : Vec m) (j : Fin n) :
|dense W b (relu m u') j - dense W b (relu m u) j| ≤ wb * ∑ i : Fin m, |u' i - u i|

ReLU then a dense layer: an input drift of ℓ1 mass B moves each output entry by at most w·B.

theorem Proofs.MlpSlot.loss_grad_lipschitz {P d₂ d₃ : ℕ} (Z : Vec P → Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (label : Fin d₃) {σ ρ w₂ D : ℝ} (hσ : 0 ≤ σ) (hZ : ∀ (v e : Vec P) (l : Fin d₂), |Z (v + e) l - Z v l| ≤ σ * ∑ idx : Fin P, |e idx|) (hZ1 : ∀ (v e : Vec P), ∑ l : Fin d₂, |Z (v + e) l - Z v l| ≤ ρ * ∑ idx : Fin P, |e idx|) (hw₂ : 0 ≤ w₂) (hW₂ : ∀ (j : Fin d₂) (k : Fin d₃), |W₂ j k| ≤ w₂) (J : Fin d₂ → ℝ) (hJ : ∑ l : Fin d₂, |J l| ≤ ρ) (idx : Fin P) (Q : Vec P → Prop) (hgrad : ∀ (v' : Vec P), Q v' → (∀ (l : Fin d₂), Z v' l ≠ 0) → gradAt (fun (w : Vec P) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (Z w))) label) v' idx = ∑ l : Fin d₂, J l * ((if Z v' l > 0 then 1 else 0) * ∑ k : Fin d₃, W₂ l k * (softmax d₃ (dense W₂ b₂ (relu d₂ (Z v'))) k - oneHot d₃ label k))) (v d : Vec P) (hd : ∑ idx : Fin P, |d idx| ≤ D) (hm : ∀ (l : Fin d₂), σ * D < |Z v l|) (hsmall : 2 * (w₂ * (ρ * D)) < 1) (t : ℝ) (ht : t ∈ Set.Icc 0 1) (hQv : Q v) (hQt : Q (v + t • d)) :
|gradAt (fun (w : Vec P) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (Z w))) label) (v + t • d) idx - gradAt (fun (w : Vec P) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (Z w))) label) v idx| ≤ 2 * ↑d₃ * w₂ ^ 2 * ρ ^ 2 / (1 - 2 * (w₂ * (ρ * D))) * (t * D)

Segment-Lipschitz gradient for an MLP-slot loss, explicit constant. For a map Z into a ReLU layer's pre-activation whose entries move by at most σ·‖e‖₁ (hZ) and whose ℓ1 drift is at most ρ·‖e‖₁ (hZ1), and whose loss gradient at every off-kink point is a fixed row J (row mass ≤ ρ) contracted with the mask and the W₂ head (hgrad, needed only where Q holds): the margin σ·D freezes the mask along [v, v+d], the row factors out, and the difference collapses to the softmax drift. The hidden layer is the instance σ = ρ = a; the input layer takes Z = the middle pre-activation, σ = w₁·a, ρ = d₂·w₁·a, J = xᵢ·relu₀'s frozen mask·W₁'s row, Q = relu₀'s signs frozen.

theorem Proofs.mlp_hidden_loss_differentiableAt {d₁ d₂ d₃ : ℕ} (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) (label : Fin d₃) (w : Vec (d₁ * d₂)) (hz : ∀ (k : Fin d₂), dense (Mat.unflatten w) b₁ a₀ k ≠ 0) :
DifferentiableAt ℝ (fun (w' : Vec (d₁ * d₂)) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense (Mat.unflatten w') b₁ a₀))) label) w

The loss-of-W₁ map is differentiable wherever the hidden pre-activation is off the kinks.

theorem Proofs.mlp_hidden_loss_gradAt {d₁ d₂ d₃ : ℕ} (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) (label : Fin d₃) (v : Vec (d₁ * d₂)) (hz : ∀ (k : Fin d₂), dense (Mat.unflatten v) b₁ a₀ k ≠ 0) (i : Fin d₁) (j : Fin d₂) :
gradAt (fun (w : Vec (d₁ * d₂)) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense (Mat.unflatten w) b₁ a₀))) label) v (finProdFinEquiv (i, j)) = a₀ i * ((if dense (Mat.unflatten v) b₁ a₀ j > 0 then 1 else 0) * ∑ k : Fin d₃, W₂ j k * (softmax d₃ (dense W₂ b₂ (relu d₂ (dense (Mat.unflatten v) b₁ a₀))) k - oneHot d₃ label k))

Closed form of the hidden-layer loss gradient at any off-kink parameter point: ∂L/∂W₁_{ij} = a₀ᵢ·relu'(z₁ⱼ)·∑ₖ W₂ⱼₖ·(softmax − onehot)ₖ — the suite's conditional fold (mlp_hidden_total_loss_grad) re-expressed through gradAt with both pdiv factors collapsed to their certified closed forms. The hidden-layer peer of linear_loss_gradAt.

theorem Proofs.mlp_hidden_logit_drift {d₁ d₂ d₃ : ℕ} (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) {a w₂ : ℝ} (hx : ∀ (i : Fin d₁), |a₀ i| ≤ a) (hw₂ : 0 ≤ w₂) (hW₂ : ∀ (j : Fin d₂) (k : Fin d₃), |W₂ j k| ≤ w₂) (v e : Vec (d₁ * d₂)) (k : Fin d₃) :
|dense W₂ b₂ (relu d₂ (dense (Mat.unflatten (v + e)) b₁ a₀)) k - dense W₂ b₂ (relu d₂ (dense (Mat.unflatten v) b₁ a₀)) k| ≤ w₂ * (a * ∑ idx : Fin (d₁ * d₂), |e idx|)

The hidden-layer logit drift: a weight perturbation of ℓ1 mass ‖e‖₁ moves every logit by at most w₂·a·‖e‖₁ — through the frozen dense, the 1-Lipschitz ReLU, and the column-tiled ℓ1 mass. No width factor.

theorem Proofs.mlp_hidden_loss_grad_lipschitz {d₁ d₂ d₃ : ℕ} (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) (label : Fin d₃) {a w₂ D : ℝ} (ha : 0 ≤ a) (hx : ∀ (i : Fin d₁), |a₀ i| ≤ a) (hw₂ : 0 ≤ w₂) (hW₂ : ∀ (j : Fin d₂) (k : Fin d₃), |W₂ j k| ≤ w₂) (v d : Vec (d₁ * d₂)) (hd : ∑ idx : Fin (d₁ * d₂), |d idx| ≤ D) (hmargin : ∀ (j : Fin d₂), a * D < |dense (Mat.unflatten v) b₁ a₀ j|) (hsmall : 2 * (w₂ * (a * D)) < 1) (t : ℝ) (ht : t ∈ Set.Icc 0 1) (idx : Fin (d₁ * d₂)) :
|gradAt (fun (w : Vec (d₁ * d₂)) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense (Mat.unflatten w) b₁ a₀))) label) (v + t • d) idx - gradAt (fun (w : Vec (d₁ * d₂)) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense (Mat.unflatten w) b₁ a₀))) label) v idx| ≤ 2 * ↑d₃ * w₂ ^ 2 * a ^ 2 / (1 - 2 * (w₂ * (a * D))) * (t * D)

Segment-Lipschitz gradient for the hidden-layer loss, explicit constant. Under the margin a·D < |z₁ⱼ| (the step cannot flip a ReLU sign — the masks freeze along the whole segment) and the small-step condition 2·w₂·a·D < 1, the gradient entries drift by at most (2·d₃·w₂²·a²/(1−2·w₂·a·D))·(t·D) along [v, v+d] — the exact shape descent_segment consumes. The hidden-layer peer of linear_loss_grad_lipschitz; MlpSlot.loss_grad_lipschitz at σ = ρ = a.

noncomputable def Proofs.mlpHiddenLoss {d₁ d₂ d₃ : ℕ} (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) (label : Fin d₃) :
Vec (d₁ * d₂) → ℝ

The loss as a function of the flattened hidden-layer weights.

Equations
Instances For
    theorem Proofs.mlp_hidden_sgd_descends {d₁ d₂ d₃ : ℕ} (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) (label : Fin d₃) (gh : Vec (d₁ * d₂)) {lr η a w₂ : ℝ} (ha : 0 ≤ a) (hx : ∀ (i : Fin d₁), |a₀ i| ≤ a) (hw₂ : 0 ≤ w₂) (hW₂ : ∀ (j : Fin d₂) (k : Fin d₃), |W₂ j k| ≤ w₂) (hlr : 0 ≤ lr) (hη : 0 ≤ η) (hgh : ∀ (idx : Fin (d₁ * d₂)), |gh idx - gradAt (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten idx| ≤ η) (hmargin : ∀ (j : Fin d₂), a * stepRadius (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten lr η < |dense W₁ b₁ a₀ j|) (hsmall : 2 * (w₂ * (a * stepRadius (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten lr η)) < 1) (h1 : lr * η * ∑ idx : Fin (d₁ * d₂), |gradAt (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten idx| ≤ (lr * ∑ idx : Fin (d₁ * d₂), gradAt (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten idx ^ 2) / 4) (h2 : 2 * ↑d₃ * w₂ ^ 2 * a ^ 2 / (1 - 2 * (w₂ * (a * stepRadius (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten lr η))) * stepRadius (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten lr η ^ 2 ≤ (lr * ∑ idx : Fin (d₁ * d₂), gradAt (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten idx ^ 2) / 4) :
    mlpHiddenLoss b₁ W₂ b₂ a₀ label (W₁.flatten - lr • gh) ≤ mlpHiddenLoss b₁ W₂ b₂ a₀ label W₁.flatten - (lr * ∑ idx : Fin (d₁ * d₂), gradAt (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten idx ^ 2) / 2

    One inexact SGD step on the MLP's hidden weights decreases one example's cross-entropy loss (example (a₀, label), W₁ moving, every other parameter fixed). sgd_descends' smoothness hypotheses are discharged for the loss-of-W₁ map: differentiability along the segment and the segment-Lipschitz constant C = 2·d₃·w₂²·a²/(1−2·w₂·a·D) at step radius D = lr·(‖∇L‖₁ + d₁d₂·η) both come from the margin hypothesis — the step radius is small enough that no hidden ReLU can change sign. Remaining hypotheses: the oracle accuracy η (the float budgets), the margins, the small-step condition, and the two dominance conditions. Conclusion: the loss drops by ≥ lr·‖∇L‖₂²/2. The hidden-layer peer of linear_sgd_descends.

    theorem Proofs.ce_head2_input_grad {d₁ d₂ d₃ : ℕ} (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (label : Fin d₃) (z : Vec d₁) (hz0 : ∀ (k : Fin d₁), z k ≠ 0) (hz1 : ∀ (k : Fin d₂), dense W₁ b₁ (relu d₁ z) k ≠ 0) (j : Fin d₁) :
    pdiv (fun (y : Vec d₁) (x : Fin 1) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ y)))) label) z j 0 = (if z j > 0 then 1 else 0) * ∑ l : Fin d₂, W₁ j l * ((if dense W₁ b₁ (relu d₁ z) l > 0 then 1 else 0) * ∑ k : Fin d₃, W₂ l k * (softmax d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ z)))) k - oneHot d₃ label k))

    Loss input-gradient through the relu→dense→relu chain — the two-mask closed form relu'(z₀ⱼ)·∑ₗ W₁ⱼₗ·relu'(z₁ₗ)·∑ₖ W₂ₗₖ·(softmax − onehot)ₖ at a point with both pre-activations off the kinks. The pdiv-level form of the deepest cotangent mlpCotOut0 delivers (cf. mlpCotOut0_denote).

    theorem Proofs.mlp_input_loss_differentiableAt {d₀ d₁ d₂ d₃ : ℕ} (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (x : Vec d₀) (label : Fin d₃) (w : Vec (d₀ * d₁)) (hz0 : ∀ (k : Fin d₁), dense (Mat.unflatten w) b₀ x k ≠ 0) (hz1 : ∀ (k : Fin d₂), dense W₁ b₁ (relu d₁ (dense (Mat.unflatten w) b₀ x)) k ≠ 0) :
    DifferentiableAt ℝ (fun (w' : Vec (d₀ * d₁)) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense (Mat.unflatten w') b₀ x))))) label) w

    The loss-of-W₀ map is differentiable wherever both pre-activations are off the kinks.

    theorem Proofs.mlp_input_loss_gradAt {d₀ d₁ d₂ d₃ : ℕ} (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (x : Vec d₀) (label : Fin d₃) (v : Vec (d₀ * d₁)) (hz0 : ∀ (k : Fin d₁), dense (Mat.unflatten v) b₀ x k ≠ 0) (hz1 : ∀ (k : Fin d₂), dense W₁ b₁ (relu d₁ (dense (Mat.unflatten v) b₀ x)) k ≠ 0) (i : Fin d₀) (j : Fin d₁) :
    gradAt (fun (w : Vec (d₀ * d₁)) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense (Mat.unflatten w) b₀ x))))) label) v (finProdFinEquiv (i, j)) = x i * ((if dense (Mat.unflatten v) b₀ x j > 0 then 1 else 0) * ∑ l : Fin d₂, W₁ j l * ((if dense W₁ b₁ (relu d₁ (dense (Mat.unflatten v) b₀ x)) l > 0 then 1 else 0) * ∑ k : Fin d₃, W₂ l k * (softmax d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense (Mat.unflatten v) b₀ x))))) k - oneHot d₃ label k)))

    Closed form of the input-layer loss gradient at any two-margin point: ∂L/∂W₀_{ij} = xᵢ·relu'(z₀ⱼ)·∑ₗ W₁ⱼₗ·relu'(z₁ₗ)·∑ₖ W₂ₗₖ· (softmax − onehot)ₖ — the deepest fold (mlp_input_total_loss_grad) with both pdiv factors collapsed. The input-layer peer of linear_loss_gradAt.

    theorem Proofs.margin_keeps_offkink_mid {d₀ d₁ d₂ : ℕ} (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (x : Vec d₀) {a w₁ D : ℝ} (ha : 0 ≤ a) (hx : ∀ (i : Fin d₀), |x i| ≤ a) (hw₁ : 0 ≤ w₁) (hW₁ : ∀ (j : Fin d₁) (l : Fin d₂), |W₁ j l| ≤ w₁) (v e : Vec (d₀ * d₁)) (he : ∑ idx : Fin (d₀ * d₁), |e idx| ≤ D) (hmargin1 : ∀ (l : Fin d₂), w₁ * (a * D) < |dense W₁ b₁ (relu d₁ (dense (Mat.unflatten v) b₀ x)) l|) (t : ℝ) (ht0 : 0 ≤ t) (ht1 : t ≤ 1) (l : Fin d₂) :
    dense W₁ b₁ (relu d₁ (dense (Mat.unflatten (v + t • e)) b₀ x)) l ≠ 0 ∧ (0 < dense W₁ b₁ (relu d₁ (dense (Mat.unflatten (v + t • e)) b₀ x)) l ↔ 0 < dense W₁ b₁ (relu d₁ (dense (Mat.unflatten v) b₀ x)) l)

    The layer-1 margin keeps the middle pre-activation off the kink along the segment: the perturbation arrives through one dense + ReLU, so the drift is at most w₁·a·D — the layer-1 analogue of margin_keeps_offkink.

    theorem Proofs.mlp_input_loss_grad_lipschitz {d₀ d₁ d₂ d₃ : ℕ} (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (x : Vec d₀) (label : Fin d₃) {a w₁ w₂ D : ℝ} (ha : 0 ≤ a) (hx : ∀ (i : Fin d₀), |x i| ≤ a) (hw₁ : 0 ≤ w₁) (hW₁ : ∀ (j : Fin d₁) (l : Fin d₂), |W₁ j l| ≤ w₁) (hw₂ : 0 ≤ w₂) (hW₂ : ∀ (l : Fin d₂) (k : Fin d₃), |W₂ l k| ≤ w₂) (v d : Vec (d₀ * d₁)) (hd : ∑ idx : Fin (d₀ * d₁), |d idx| ≤ D) (hmargin0 : ∀ (j : Fin d₁), a * D < |dense (Mat.unflatten v) b₀ x j|) (hmargin1 : ∀ (l : Fin d₂), w₁ * (a * D) < |dense W₁ b₁ (relu d₁ (dense (Mat.unflatten v) b₀ x)) l|) (hsmall : 2 * (w₂ * (↑d₂ * (w₁ * (a * D)))) < 1) (t : ℝ) (ht : t ∈ Set.Icc 0 1) (idx : Fin (d₀ * d₁)) :
    |gradAt (fun (w : Vec (d₀ * d₁)) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense (Mat.unflatten w) b₀ x))))) label) (v + t • d) idx - gradAt (fun (w : Vec (d₀ * d₁)) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense (Mat.unflatten w) b₀ x))))) label) v idx| ≤ 2 * ↑d₃ * ↑d₂ ^ 2 * w₁ ^ 2 * w₂ ^ 2 * a ^ 2 / (1 - 2 * (w₂ * (↑d₂ * (w₁ * (a * D))))) * (t * D)

    Segment-Lipschitz gradient for the input-layer loss, explicit constant. Under both margins (neither ReLU layer's sign pattern can change along the step) and the small-step condition, the gradient entries drift by at most (2·d₃·d₂²·w₁²·w₂²·a²/(1−2·w₂·d₂·w₁·a·D))·(t·D). The input-layer peer of mlp_hidden_loss_grad_lipschitz; the extra d₂·w₁ is the middle layer's ℓ1→ℓ1 operator factor. MlpSlot.loss_grad_lipschitz at the middle pre-activation, σ = w₁·a, ρ = d₂·w₁·a.

    noncomputable def Proofs.mlpInputLoss {d₀ d₁ d₂ d₃ : ℕ} (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (x : Vec d₀) (label : Fin d₃) :
    Vec (d₀ * d₁) → ℝ

    The loss as a function of the flattened input-layer weights.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      theorem Proofs.mlp_input_sgd_descends {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₀) (label : Fin d₃) (gh : Vec (d₀ * d₁)) {lr η a w₁ w₂ : ℝ} (ha : 0 ≤ a) (hx : ∀ (i : Fin d₀), |x i| ≤ a) (hw₁ : 0 ≤ w₁) (hW₁ : ∀ (j : Fin d₁) (l : Fin d₂), |W₁ j l| ≤ w₁) (hw₂ : 0 ≤ w₂) (hW₂ : ∀ (l : Fin d₂) (k : Fin d₃), |W₂ l k| ≤ w₂) (hlr : 0 ≤ lr) (hη : 0 ≤ η) (hgh : ∀ (idx : Fin (d₀ * d₁)), |gh idx - gradAt (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten idx| ≤ η) (hmargin0 : ∀ (j : Fin d₁), a * stepRadius (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten lr η < |dense W₀ b₀ x j|) (hmargin1 : ∀ (l : Fin d₂), w₁ * (a * stepRadius (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten lr η) < |dense W₁ b₁ (relu d₁ (dense W₀ b₀ x)) l|) (hsmall : 2 * (w₂ * (↑d₂ * (w₁ * (a * stepRadius (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten lr η)))) < 1) (h1 : lr * η * ∑ idx : Fin (d₀ * d₁), |gradAt (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten idx| ≤ (lr * ∑ idx : Fin (d₀ * d₁), gradAt (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten idx ^ 2) / 4) (h2 : 2 * ↑d₃ * ↑d₂ ^ 2 * w₁ ^ 2 * w₂ ^ 2 * a ^ 2 / (1 - 2 * (w₂ * (↑d₂ * (w₁ * (a * stepRadius (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten lr η))))) * stepRadius (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten lr η ^ 2 ≤ (lr * ∑ idx : Fin (d₀ * d₁), gradAt (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten idx ^ 2) / 4) :
      mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label (W₀.flatten - lr • gh) ≤ mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label W₀.flatten - (lr * ∑ idx : Fin (d₀ * d₁), gradAt (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten idx ^ 2) / 2

      One inexact SGD step on the MLP's input weights decreases one example's cross-entropy loss (example (x, label), W₀ moving, every other parameter fixed). The deepest descent capstone: both ReLU layers' margins at the step radius D = lr·(‖∇L‖₁ + d₀d₁·η) freeze the masks, the segment-Lipschitz constant C = 2·d₃·d₂²·w₁²·w₂²·a²/(1−2·w₂·d₂·w₁·a·D) is proven, and the loss drops by ≥ lr·‖∇L‖₂²/2. The oracle accuracy, the margins, the small-step and the two dominance conditions remain hypotheses. The input-layer peer of linear_sgd_descends; with this each MLP weight layer has a single-layer, single-example descent statement.

      noncomputable def Proofs.mlpOutputLoss {d₀ d₁ d₂ d₃ : ℕ} (W₀ : Mat d₀ d₁) (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (b₂ : Vec d₃) (x : Vec d₀) (label : Fin d₃) :
      Vec (d₂ * d₃) → ℝ

      The loss as a function of the flattened output-layer weights.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        theorem Proofs.mlp_output_float_sgd_descends {d₀ d₁ d₂ d₃ : ℕ} (M : FloatModel) (W₀ : Mat d₀ d₁) (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (x : Vec d₀) (label : Fin d₃) (fexp : ℝ → ℝ) {lr a eexp δ : ℝ} (ha : 0 ≤ a) (hx : ∀ (i : Fin d₂), |relu d₂ (dense W₁ b₁ (relu d₁ (dense W₀ b₀ x))) i| ≤ a) (hlr : 0 ≤ lr) (heexp0 : 0 ≤ eexp) (heexp1 : eexp ≤ 1) (hδ0 : 0 ≤ δ) (hfexp : ∀ (t : ℝ), |fexp t - Real.exp t| ≤ eexp * Real.exp t) (hρ1 : FloatModel.smRho M.u eexp d₃ < 1) (hδ : ∀ (k' : Fin d₃), |M.dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense W₀ b₀ x)))) k' - dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense W₀ b₀ x)))) k'| ≤ δ) (hsmall : 2 * (a * stepRadius (mlpOutputLoss W₀ b₀ W₁ b₁ b₂ x label) W₂.flatten lr (FloatModel.mulErr M.u a 1 0 (FloatModel.cotErr M.u eexp δ d₃))) < 1) (h1 : lr * FloatModel.mulErr M.u a 1 0 (FloatModel.cotErr M.u eexp δ d₃) * ∑ idx : Fin (d₂ * d₃), |gradAt (mlpOutputLoss W₀ b₀ W₁ b₁ b₂ x label) W₂.flatten idx| ≤ (lr * ∑ idx : Fin (d₂ * d₃), gradAt (mlpOutputLoss W₀ b₀ W₁ b₁ b₂ x label) W₂.flatten idx ^ 2) / 4) (h2 : 2 * a ^ 2 / (1 - 2 * (a * stepRadius (mlpOutputLoss W₀ b₀ W₁ b₁ b₂ x label) W₂.flatten lr (FloatModel.mulErr M.u a 1 0 (FloatModel.cotErr M.u eexp δ d₃)))) * stepRadius (mlpOutputLoss W₀ b₀ W₁ b₁ b₂ x label) W₂.flatten lr (FloatModel.mulErr M.u a 1 0 (FloatModel.cotErr M.u eexp δ d₃)) ^ 2 ≤ (lr * ∑ idx : Fin (d₂ * d₃), gradAt (mlpOutputLoss W₀ b₀ W₁ b₁ b₂ x label) W₂.flatten idx ^ 2) / 4) :
        crossEntropy d₃ (dense (Mat.unflatten (W₂.flatten - lr • M.linearFloatGrad W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense W₀ b₀ x)))) fexp label)) b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense W₀ b₀ x))))) label ≤ mlpOutputLoss W₀ b₀ W₁ b₁ b₂ x label W₂.flatten - (lr * ∑ idx : Fin (d₂ * d₃), gradAt (mlpOutputLoss W₀ b₀ W₁ b₁ b₂ x label) W₂.flatten idx ^ 2) / 2

        One SGD step with the FloatModel binary32 output-layer gradient decreases one example's cross-entropy loss; the gradient's accuracy is proven, not assumed. The output-layer rung of the η-composition. Since the top dense layer sits directly below the softmax-CE loss with no ReLU between, the loss-of-W₂ map is the linear net's loss at the hidden activation a₁ = relu(dense W₁ b₁ (relu(dense W₀ b₀ x))) — so this is linear_float_sgd_descends instantiated there, with the same scope (one example, W₂ moving, update in ℝ). The gradient is the FloatModel binary32 output-layer gradient M.linearFloatGrad W₂ b₂ a₁ and its accuracy η = mulErr u a 1 0 (cotErr …) is proven (by linear_grad_close, inside the linear theorem), not assumed. No margin needed — the output layer never crosses a kink.

        The hidden and input rungs are mlp_hidden_float_sgd_descends and mlp_input_float_sgd_descends.

        theorem Proofs.mlp_w1_grad_close {d₁ d₂ d₃ : ℕ} (M : FloatModel) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) (label : Fin d₃) (fexp : ℝ → ℝ) {a w₁ β₁ w₂ β₂ eexp : ℝ} (ha : 0 ≤ a) (hw₁ : 0 ≤ w₁) (hβ₁ : 0 ≤ β₁) (hw₂ : 0 ≤ w₂) (hβ₂ : 0 ≤ β₂) (heexp0 : 0 ≤ eexp) (heexp1 : eexp ≤ 1) (hfexp : ∀ (t : ℝ), |fexp t - Real.exp t| ≤ eexp * Real.exp t) (hρ1 : FloatModel.smRho M.u eexp d₃ < 1) (hx : ∀ (i : Fin d₁), |a₀ i| ≤ a) (hW₁ : ∀ (i : Fin d₁) (j : Fin d₂), |W₁ i j| ≤ w₁) (hb₁ : ∀ (j : Fin d₂), |b₁ j| ≤ β₁) (hW₂ : ∀ (i : Fin d₂) (j : Fin d₃), |W₂ i j| ≤ w₂) (hb₂ : ∀ (j : Fin d₃), |b₂ j| ≤ β₂) (hmargin : ∀ (j' : Fin d₂), FloatModel.layerBudget M.u d₁ w₁ β₁ a 0 < |dense W₁ b₁ a₀ j'|) (i : Fin d₁) (j : Fin d₂) :
        |M.mul (a₀ i) (FloatModel.reluMask (M.dense W₁ b₁ a₀) (M.dense (fun (j' : Fin d₃) (i' : Fin d₂) => W₂ i' j') (fun (x : Fin d₂) => 0) (M.softmaxCECotF fexp (M.dense W₂ b₂ (relu d₂ (M.dense W₁ b₁ a₀))) label)) j) - a₀ i * FloatModel.reluMask (dense W₁ b₁ a₀) (dense (fun (j' : Fin d₃) (i' : Fin d₂) => W₂ i' j') (fun (x : Fin d₂) => 0) fun (k : Fin d₃) => softmax d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ a₀))) k - oneHot d₃ label k) j| ≤ FloatModel.mulErr M.u a (FloatModel.layerAct d₃ w₂ 0 1) 0 (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ a) (FloatModel.layerBudget M.u d₁ w₁ β₁ a 0)) d₃))

        The binary32 hidden-layer (W₁) gradient is within an explicit budget of the certified one, per entry — the float-backward grad-close that the hidden η-composition needs. With the layer-1 input activation a₀ frozen exact (the descent moves only W₁), the FloatModel transcription computes the W₁ gradient as fl(a₀ᵢ · c̃₁ⱼ) where the float layer-1 cotangent c̃₁ = mask(z̃₁, W₂ᵀ·c̃₂) reads the float pre-activation z̃₁ = M.dense W₁ b₁ a₀ and the float softmax−onehot head c̃₂ at the float logits. This is within mulErr M.u a … 0 (layerBudget … (cotErr …)) of the certified a₀ᵢ · mask(z₁, W₂ᵀ·(softmax−onehot))ⱼ (= mlp_hidden_loss_gradAt), built from three reusable closes: the head (softmax_ce_cot_close, accuracy cotErr), the masked W₂ᵀ contraction (cot_step_close, under the quantitative margin E₁ < |z₁ⱼ| — forward rounding must not flip the layer-1 ReLU), and the final input multiply (mul_close, with the exact a₀ operand, ea = 0, exactly as the linear grad-close).

        noncomputable def Proofs.FloatModel.mlpHiddenFloatGrad (M : FloatModel) {d₁ d₂ d₃ : ℕ} (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) (fexp : ℝ → ℝ) (label : Fin d₃) :
        Vec (d₁ * d₂)

        The binary32 hidden-layer (W₁) gradient of the MLP loss — the FloatModel transcription of the per-example gradient (with the layer-1 input activation a₀ frozen exact): fl(a₀ᵢ · c̃₁ⱼ) where the float layer-1 cotangent c̃₁ = mask(z̃₁, W₂ᵀ·c̃₂) reads the float pre-activation z̃₁ = M.dense W₁ b₁ a₀ and the float softmax−onehot head c̃₂ at the float logits. Flattened to the Vec (d₁*d₂) parameter layout that gradAt/mlp_hidden_sgd_descends use. The hidden-layer peer of linearFloatGrad.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          @[simp]
          theorem Proofs.mlpHiddenFloatGrad_apply (M : FloatModel) {d₁ d₂ d₃ : ℕ} (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) (fexp : ℝ → ℝ) (label : Fin d₃) (i : Fin d₁) (j : Fin d₂) :
          M.mlpHiddenFloatGrad W₁ b₁ W₂ b₂ a₀ fexp label (finProdFinEquiv (i, j)) = M.mul (a₀ i) (FloatModel.reluMask (M.dense W₁ b₁ a₀) (M.dense (fun (j' : Fin d₃) (i' : Fin d₂) => W₂ i' j') (fun (x : Fin d₂) => 0) (M.softmaxCECotF fexp (M.dense W₂ b₂ (relu d₂ (M.dense W₁ b₁ a₀))) label)) j)
          theorem Proofs.mlp_hidden_loss_gradAt_reluMask {d₁ d₂ d₃ : ℕ} (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) (label : Fin d₃) (hz : ∀ (k : Fin d₂), dense W₁ b₁ a₀ k ≠ 0) (i : Fin d₁) (j : Fin d₂) :
          gradAt (fun (w : Vec (d₁ * d₂)) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense (Mat.unflatten w) b₁ a₀))) label) W₁.flatten (finProdFinEquiv (i, j)) = a₀ i * FloatModel.reluMask (dense W₁ b₁ a₀) (dense (fun (j' : Fin d₃) (i' : Fin d₂) => W₂ i' j') (fun (x : Fin d₂) => 0) fun (k : Fin d₃) => softmax d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ a₀))) k - oneHot d₃ label k) j

          The certified hidden-layer loss gradient, in the reluMask form that mlp_w1_grad_close bounds against. At an off-kink parameter point (hz), mlp_hidden_loss_gradAt's closed form a₀ᵢ·relu'(z₁ⱼ)·∑ₖ W₂ⱼₖ·(softmax−onehot)ₖ equals the masked-W₂ᵀ- contraction form a₀ᵢ · reluMask(z₁, dense (fun j' i' => W₂ i' j') 0 (softmax−onehot))ⱼ. The bridge that lets the float grad-close (stated with reluMask) discharge mlp_hidden_sgd_descends' abstract η (stated with gradAt).

          theorem Proofs.mlp_hidden_float_sgd_descends {d₁ d₂ d₃ : ℕ} (M : FloatModel) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (a₀ : Vec d₁) (label : Fin d₃) (fexp : ℝ → ℝ) {lr a w₁ β₁ w₂ β₂ eexp : ℝ} (ha : 0 ≤ a) (hw₁ : 0 ≤ w₁) (hβ₁ : 0 ≤ β₁) (hw₂ : 0 ≤ w₂) (hβ₂ : 0 ≤ β₂) (hlr : 0 ≤ lr) (heexp0 : 0 ≤ eexp) (heexp1 : eexp ≤ 1) (hfexp : ∀ (t : ℝ), |fexp t - Real.exp t| ≤ eexp * Real.exp t) (hρ1 : FloatModel.smRho M.u eexp d₃ < 1) (hx : ∀ (i : Fin d₁), |a₀ i| ≤ a) (hW₁ : ∀ (i : Fin d₁) (j : Fin d₂), |W₁ i j| ≤ w₁) (hb₁ : ∀ (j : Fin d₂), |b₁ j| ≤ β₁) (hW₂ : ∀ (i : Fin d₂) (j : Fin d₃), |W₂ i j| ≤ w₂) (hb₂ : ∀ (j : Fin d₃), |b₂ j| ≤ β₂) (hmargin_round : ∀ (j' : Fin d₂), FloatModel.layerBudget M.u d₁ w₁ β₁ a 0 < |dense W₁ b₁ a₀ j'|) (hmargin_step : ∀ (j : Fin d₂), a * stepRadius (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten lr (FloatModel.mulErr M.u a (FloatModel.layerAct d₃ w₂ 0 1) 0 (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ a) (FloatModel.layerBudget M.u d₁ w₁ β₁ a 0)) d₃))) < |dense W₁ b₁ a₀ j|) (hsmall : 2 * (w₂ * (a * stepRadius (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten lr (FloatModel.mulErr M.u a (FloatModel.layerAct d₃ w₂ 0 1) 0 (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ a) (FloatModel.layerBudget M.u d₁ w₁ β₁ a 0)) d₃))))) < 1) (h1 : lr * FloatModel.mulErr M.u a (FloatModel.layerAct d₃ w₂ 0 1) 0 (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ a) (FloatModel.layerBudget M.u d₁ w₁ β₁ a 0)) d₃)) * ∑ idx : Fin (d₁ * d₂), |gradAt (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten idx| ≤ (lr * ∑ idx : Fin (d₁ * d₂), gradAt (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten idx ^ 2) / 4) (h2 : 2 * ↑d₃ * w₂ ^ 2 * a ^ 2 / (1 - 2 * (w₂ * (a * (lr * (∑ idx : Fin (d₁ * d₂), |gradAt (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten idx| + ↑(d₁ * d₂) * FloatModel.mulErr M.u a (FloatModel.layerAct d₃ w₂ 0 1) 0 (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ a) (FloatModel.layerBudget M.u d₁ w₁ β₁ a 0)) d₃))))))) * stepRadius (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten lr (FloatModel.mulErr M.u a (FloatModel.layerAct d₃ w₂ 0 1) 0 (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ a) (FloatModel.layerBudget M.u d₁ w₁ β₁ a 0)) d₃))) ^ 2 ≤ (lr * ∑ idx : Fin (d₁ * d₂), gradAt (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten idx ^ 2) / 4) :
          mlpHiddenLoss b₁ W₂ b₂ a₀ label (W₁.flatten - lr • M.mlpHiddenFloatGrad W₁ b₁ W₂ b₂ a₀ fexp label) ≤ mlpHiddenLoss b₁ W₂ b₂ a₀ label W₁.flatten - (lr * ∑ idx : Fin (d₁ * d₂), gradAt (mlpHiddenLoss b₁ W₂ b₂ a₀ label) W₁.flatten idx ^ 2) / 2

          One SGD step with the FloatModel binary32 hidden-layer gradient decreases one example's cross-entropy loss; the gradient's accuracy is proven, not assumed. The hidden-layer rung of the η-composition. The gradient is the FloatModel binary32 W₁ gradient M.mlpHiddenFloatGrad W₁ b₁ W₂ b₂ a₀ fexp label, and its accuracy η = mulErr u a (layerAct …) 0 (layerBudget … (cotErr …)) is proven by mlp_w1_grad_close (via the reluMask↔gradAt bridge mlp_hidden_loss_gradAt_reluMask), not assumed.

          Two margins are carried as hypotheses: the rounding margin hmargin_round (layerBudget < |z₁|, forward rounding must not flip the layer-1 ReLU — the grad-close precondition) and the step margin hmargin_step (a·D < |z₁|, the parameter step must not flip it along the segment — the smoothness precondition). They are the same shape ("nothing flips the layer-1 ReLU") and are not collapsed into one here. This is the hidden-layer peer of linear_float_sgd_descends / mlp_output_float_sgd_descends.

          Scope: one example (a₀, label), the layer's weights only (other parameters fixed), and the update taken in ℝ — only the gradient is float-modelled.

          theorem Proofs.reluMask_dense_transpose_eq {p n : ℕ} (z : Vec p) (W : Mat p n) (c : Vec n) (l : Fin p) :
          (if z l > 0 then 1 else 0) * ∑ k : Fin n, W l k * c k = FloatModel.reluMask z (dense (fun (j : Fin n) (i' : Fin p) => W i' j) (fun (x : Fin p) => 0) c) l

          A masked Wᵀ contraction in if-then-else form equals the reluMask form. (relu'(zₗ))·∑ₖ Wₗₖ·cₖ = reluMask z (Wᵀ·c) l — the per-step identity behind the gradAt↔reluMask bridges (mlp_hidden_/ mlp_input_loss_gradAt_reluMask): one ReLU-sign case split + mul_comm (the transpose dense (fun j i' => W i' j) 0 c reads ∑ₖ cₖ·Wₗₖ).

          noncomputable def Proofs.FloatModel.mlpInputFloatGrad (M : FloatModel) {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₀) (fexp : ℝ → ℝ) (label : Fin d₃) :
          Vec (d₀ * d₁)

          The binary32 input-layer (W₀) gradient of the MLP loss — the FloatModel transcription of the per-example gradient (x the exact input): fl(xᵢ · c̃₀ⱼ) where the float layer-0 cotangent c̃₀ = mask(z̃₀, W₁ᵀ·c̃₁) reads the float layer-1 cotangent c̃₁ = mask(z̃₁, W₂ᵀ·c̃₂) and the float softmax−onehot head c̃₂, all at the float pre-activations. Flattened to the Vec (d₀*d₁) parameter layout. The two-mask peer of mlpHiddenFloatGrad.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            @[simp]
            theorem Proofs.mlpInputFloatGrad_apply (M : FloatModel) {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₀) (fexp : ℝ → ℝ) (label : Fin d₃) (i : Fin d₀) (j : Fin d₁) :
            M.mlpInputFloatGrad W₀ b₀ W₁ b₁ W₂ b₂ x fexp label (finProdFinEquiv (i, j)) = M.mul (x i) (FloatModel.reluMask (M.dense W₀ b₀ x) (M.dense (fun (j' : Fin d₂) (i' : Fin d₁) => W₁ i' j') (fun (x : Fin d₁) => 0) (FloatModel.reluMask (M.dense W₁ b₁ (relu d₁ (M.dense W₀ b₀ x))) (M.dense (fun (j' : Fin d₃) (i' : Fin d₂) => W₂ i' j') (fun (x : Fin d₂) => 0) (M.softmaxCECotF fexp (M.dense W₂ b₂ (relu d₂ (M.dense W₁ b₁ (relu d₁ (M.dense W₀ b₀ x))))) label)))) j)
            theorem Proofs.mlp_input_loss_gradAt_reluMask {d₀ d₁ d₂ d₃ : ℕ} (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (W₀ : Mat d₀ d₁) (x : Vec d₀) (label : Fin d₃) (hz0 : ∀ (k : Fin d₁), dense W₀ b₀ x k ≠ 0) (hz1 : ∀ (k : Fin d₂), dense W₁ b₁ (relu d₁ (dense W₀ b₀ x)) k ≠ 0) (i : Fin d₀) (j : Fin d₁) :
            gradAt (fun (w : Vec (d₀ * d₁)) => crossEntropy d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense (Mat.unflatten w) b₀ x))))) label) W₀.flatten (finProdFinEquiv (i, j)) = x i * FloatModel.reluMask (dense W₀ b₀ x) (dense (fun (j' : Fin d₂) (i' : Fin d₁) => W₁ i' j') (fun (x : Fin d₁) => 0) (FloatModel.reluMask (dense W₁ b₁ (relu d₁ (dense W₀ b₀ x))) (dense (fun (j' : Fin d₃) (i' : Fin d₂) => W₂ i' j') (fun (x : Fin d₂) => 0) fun (k : Fin d₃) => softmax d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense W₀ b₀ x))))) k - oneHot d₃ label k))) j

            The certified input-layer loss gradient, in the nested reluMask form that mlp_w0_grad_close bounds against. At an off-kink point (both hz0, hz1), mlp_input_loss_gradAt's two-mask if-then-else closed form equals xᵢ · reluMask(z₀, W₁ᵀ·reluMask(z₁, W₂ᵀ·(softmax−onehot)))ⱼ. Two applications of reluMask_dense_transpose_eq (inner W₂ᵀ then outer W₁ᵀ), fired by simp_rw.

            theorem Proofs.mlp_w0_grad_close {d₀ d₁ d₂ d₃ : ℕ} (M : FloatModel) (W₀ : Mat d₀ d₁) (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (x : Vec d₀) (label : Fin d₃) (fexp : ℝ → ℝ) {a w₀ β₀ w₁ β₁ w₂ β₂ eexp : ℝ} (ha : 0 ≤ a) (hw₀ : 0 ≤ w₀) (hβ₀ : 0 ≤ β₀) (hw₁ : 0 ≤ w₁) (hβ₁ : 0 ≤ β₁) (hw₂ : 0 ≤ w₂) (hβ₂ : 0 ≤ β₂) (heexp0 : 0 ≤ eexp) (heexp1 : eexp ≤ 1) (hfexp : ∀ (t : ℝ), |fexp t - Real.exp t| ≤ eexp * Real.exp t) (hρ1 : FloatModel.smRho M.u eexp d₃ < 1) (hx : ∀ (i : Fin d₀), |x i| ≤ a) (hW₀ : ∀ (i : Fin d₀) (j : Fin d₁), |W₀ i j| ≤ w₀) (hb₀ : ∀ (j : Fin d₁), |b₀ j| ≤ β₀) (hW₁ : ∀ (i : Fin d₁) (j : Fin d₂), |W₁ i j| ≤ w₁) (hb₁ : ∀ (j : Fin d₂), |b₁ j| ≤ β₁) (hW₂ : ∀ (i : Fin d₂) (j : Fin d₃), |W₂ i j| ≤ w₂) (hb₂ : ∀ (j : Fin d₃), |b₂ j| ≤ β₂) (hmargin0 : ∀ (j' : Fin d₁), FloatModel.layerBudget M.u d₀ w₀ β₀ a 0 < |dense W₀ b₀ x j'|) (hmargin1 : ∀ (l' : Fin d₂), FloatModel.layerBudget M.u d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a) (FloatModel.layerBudget M.u d₀ w₀ β₀ a 0) < |dense W₁ b₁ (relu d₁ (dense W₀ b₀ x)) l'|) (i : Fin d₀) (j : Fin d₁) :
            |M.mul (x i) (FloatModel.reluMask (M.dense W₀ b₀ x) (M.dense (fun (j' : Fin d₂) (i' : Fin d₁) => W₁ i' j') (fun (x : Fin d₁) => 0) (FloatModel.reluMask (M.dense W₁ b₁ (relu d₁ (M.dense W₀ b₀ x))) (M.dense (fun (j' : Fin d₃) (i' : Fin d₂) => W₂ i' j') (fun (x : Fin d₂) => 0) (M.softmaxCECotF fexp (M.dense W₂ b₂ (relu d₂ (M.dense W₁ b₁ (relu d₁ (M.dense W₀ b₀ x))))) label)))) j) - x i * FloatModel.reluMask (dense W₀ b₀ x) (dense (fun (j' : Fin d₂) (i' : Fin d₁) => W₁ i' j') (fun (x : Fin d₁) => 0) (FloatModel.reluMask (dense W₁ b₁ (relu d₁ (dense W₀ b₀ x))) (dense (fun (j' : Fin d₃) (i' : Fin d₂) => W₂ i' j') (fun (x : Fin d₂) => 0) fun (k : Fin d₃) => softmax d₃ (dense W₂ b₂ (relu d₂ (dense W₁ b₁ (relu d₁ (dense W₀ b₀ x))))) k - oneHot d₃ label k))) j| ≤ FloatModel.mulErr M.u a (FloatModel.layerAct d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1)) 0 (FloatModel.layerBudget M.u d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1) (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a)) (FloatModel.layerBudget M.u d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a) (FloatModel.layerBudget M.u d₀ w₀ β₀ a 0))) d₃)))

            The binary32 input-layer (W₀) gradient is within an explicit budget of the certified one, per entry — the float-backward grad-close for the deepest rung. With x exact, the FloatModel transcription computes the W₀ gradient fl(xᵢ·c̃₀ⱼ), c̃₀ = mask(z̃₀, W₁ᵀ·mask(z̃₁, W₂ᵀ·c̃₂)) from the float softmax−onehot head c̃₂ back through two ReLU masks. This is within mulErr … 0 (layerBudget … (layerBudget … (cotErr …))) of the certified xᵢ·mask(z₀, W₁ᵀ·mask(z₁, W₂ᵀ·(softmax−onehot)))ⱼ (= mlp_input_loss_gradAt, via mlp_input_loss_gradAt_reluMask). Built like mlp_w1_grad_close with one more cot_step_close: head (softmax_ce_cot_close), masked W₂ᵀ contraction (cot_step_close, under the layer-1 margin E₁ < |z₁|), masked W₁ᵀ contraction (cot_step_close, under the layer-0 margin E₀ < |z₀|), final exact-x multiply (mul_close, ea = 0).

            theorem Proofs.mlp_input_float_sgd_descends {d₀ d₁ d₂ d₃ : ℕ} (M : FloatModel) (W₀ : Mat d₀ d₁) (b₀ : Vec d₁) (W₁ : Mat d₁ d₂) (b₁ : Vec d₂) (W₂ : Mat d₂ d₃) (b₂ : Vec d₃) (x : Vec d₀) (label : Fin d₃) (fexp : ℝ → ℝ) {lr a w₀ β₀ w₁ β₁ w₂ β₂ eexp : ℝ} (ha : 0 ≤ a) (hw₀ : 0 ≤ w₀) (hβ₀ : 0 ≤ β₀) (hw₁ : 0 ≤ w₁) (hβ₁ : 0 ≤ β₁) (hw₂ : 0 ≤ w₂) (hβ₂ : 0 ≤ β₂) (hlr : 0 ≤ lr) (heexp0 : 0 ≤ eexp) (heexp1 : eexp ≤ 1) (hfexp : ∀ (t : ℝ), |fexp t - Real.exp t| ≤ eexp * Real.exp t) (hρ1 : FloatModel.smRho M.u eexp d₃ < 1) (hx : ∀ (i : Fin d₀), |x i| ≤ a) (hW₀ : ∀ (i : Fin d₀) (j : Fin d₁), |W₀ i j| ≤ w₀) (hb₀ : ∀ (j : Fin d₁), |b₀ j| ≤ β₀) (hW₁ : ∀ (i : Fin d₁) (j : Fin d₂), |W₁ i j| ≤ w₁) (hb₁ : ∀ (j : Fin d₂), |b₁ j| ≤ β₁) (hW₂ : ∀ (i : Fin d₂) (j : Fin d₃), |W₂ i j| ≤ w₂) (hb₂ : ∀ (j : Fin d₃), |b₂ j| ≤ β₂) (hmargin0_round : ∀ (j' : Fin d₁), FloatModel.layerBudget M.u d₀ w₀ β₀ a 0 < |dense W₀ b₀ x j'|) (hmargin1_round : ∀ (l' : Fin d₂), FloatModel.layerBudget M.u d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a) (FloatModel.layerBudget M.u d₀ w₀ β₀ a 0) < |dense W₁ b₁ (relu d₁ (dense W₀ b₀ x)) l'|) (hmargin0_step : ∀ (j : Fin d₁), a * stepRadius (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten lr (FloatModel.mulErr M.u a (FloatModel.layerAct d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1)) 0 (FloatModel.layerBudget M.u d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1) (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a)) (FloatModel.layerBudget M.u d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a) (FloatModel.layerBudget M.u d₀ w₀ β₀ a 0))) d₃)))) < |dense W₀ b₀ x j|) (hmargin1_step : ∀ (l : Fin d₂), w₁ * (a * stepRadius (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten lr (FloatModel.mulErr M.u a (FloatModel.layerAct d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1)) 0 (FloatModel.layerBudget M.u d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1) (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a)) (FloatModel.layerBudget M.u d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a) (FloatModel.layerBudget M.u d₀ w₀ β₀ a 0))) d₃))))) < |dense W₁ b₁ (relu d₁ (dense W₀ b₀ x)) l|) (hsmall : 2 * (w₂ * (↑d₂ * (w₁ * (a * stepRadius (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten lr (FloatModel.mulErr M.u a (FloatModel.layerAct d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1)) 0 (FloatModel.layerBudget M.u d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1) (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a)) (FloatModel.layerBudget M.u d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a) (FloatModel.layerBudget M.u d₀ w₀ β₀ a 0))) d₃)))))))) < 1) (h1 : lr * FloatModel.mulErr M.u a (FloatModel.layerAct d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1)) 0 (FloatModel.layerBudget M.u d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1) (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a)) (FloatModel.layerBudget M.u d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a) (FloatModel.layerBudget M.u d₀ w₀ β₀ a 0))) d₃))) * ∑ idx : Fin (d₀ * d₁), |gradAt (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten idx| ≤ (lr * ∑ idx : Fin (d₀ * d₁), gradAt (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten idx ^ 2) / 4) (h2 : 2 * ↑d₃ * ↑d₂ ^ 2 * w₁ ^ 2 * w₂ ^ 2 * a ^ 2 / (1 - 2 * (w₂ * (↑d₂ * (w₁ * (a * stepRadius (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten lr (FloatModel.mulErr M.u a (FloatModel.layerAct d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1)) 0 (FloatModel.layerBudget M.u d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1) (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a)) (FloatModel.layerBudget M.u d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a) (FloatModel.layerBudget M.u d₀ w₀ β₀ a 0))) d₃))))))))) * stepRadius (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten lr (FloatModel.mulErr M.u a (FloatModel.layerAct d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1)) 0 (FloatModel.layerBudget M.u d₂ w₁ 0 (FloatModel.layerAct d₃ w₂ 0 1) (FloatModel.layerBudget M.u d₃ w₂ 0 1 (FloatModel.cotErr M.u eexp (FloatModel.layerBudget M.u d₂ w₂ β₂ (FloatModel.layerAct d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a)) (FloatModel.layerBudget M.u d₁ w₁ β₁ (FloatModel.layerAct d₀ w₀ β₀ a) (FloatModel.layerBudget M.u d₀ w₀ β₀ a 0))) d₃)))) ^ 2 ≤ (lr * ∑ idx : Fin (d₀ * d₁), gradAt (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten idx ^ 2) / 4) :
            mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label (W₀.flatten - lr • M.mlpInputFloatGrad W₀ b₀ W₁ b₁ W₂ b₂ x fexp label) ≤ mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label W₀.flatten - (lr * ∑ idx : Fin (d₀ * d₁), gradAt (mlpInputLoss b₀ W₁ b₁ W₂ b₂ x label) W₀.flatten idx ^ 2) / 2

            One SGD step with the FloatModel binary32 input-layer gradient decreases one example's cross-entropy loss; the gradient's accuracy is proven, not assumed. The input-layer rung of the η-composition, one mask deeper than the hidden rung. The gradient is the FloatModel binary32 W₀ gradient M.mlpInputFloatGrad …, and its accuracy is proven by mlp_w0_grad_close (via the nested reluMask↔gradAt bridge mlp_input_loss_gradAt_reluMask), not assumed.

            Four margins are carried as hypotheses: the two rounding margins hmargin0_round/hmargin1_round (forward rounding must not flip either ReLU — the grad-close preconditions) and the two step margins hmargin0_step/hmargin1_step (the parameter step must not flip either along the segment — the smoothness preconditions). With this each of the three MLP weight layers has a float-gradient descent statement.

            Scope: one example (x, label), the layer's weights only (other parameters fixed), and the update taken in ℝ — only the gradient is float-modelled.