Documentation

LeanMlir.Proofs.Foundation.HeadLayers

Shared stem-pool and head CertLayers — batched GAP, the dense classifier, the 3×3/s2 pool #

Every conv net in the suite ends in global average pooling and a dense classifier, and both are globally certified (GAP is linear, dense is affine), so ok := True. Written once here and shared by MobileNetV4, ResNet-34 and ResNet-50. The ResNets' stem is here too, conv-BN-ReLU and the 3×3/s2 pool as one layer (stemReluPoolLayer), certified where every window is smooth or dead (StemPoolSmoothAt).

Both backward graphs tie by rfl. den of .gapBackBatched is definitionally the row-wise GAP VJP, and den of .denseRowBack is rowDenseBackFlat, which is what batchMapHasVJP reduces to. Note: GAP's VJP does not depend on its input, and den .gapBackBatched uses that by evaluating the backward at fun _ => 0. That is sound because GAP is linear, and it is why the tie holds at every x.

noncomputable def Proofs.StableHLO.gapLayer (N : ℕ) {c h w : ℕ} :
CertLayer (N * (c * h * w)) (N * c)

Batched global average pool as a CertLayer. Globally certified — GAP is linear.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    theorem Proofs.StableHLO.gapLayer_fwd_apply (N : ℕ) {c h w : ℕ} (v : Vec (N * (c * h * w))) :

    The GAP layer's forward is the batched global average pool.

    noncomputable def Proofs.StableHLO.denseLayer (N : ℕ) {a nC : ℕ} (W : Mat a nC) (b : Vec nC) :
    CertLayer (N * a) (N * nC)

    Batched dense classifier as a CertLayer. Globally certified — dense is affine.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      theorem Proofs.StableHLO.denseLayer_fwd_apply (N : ℕ) {a nC : ℕ} (W : Mat a nC) (b : Vec nC) (v : Vec (N * a)) :
      (denseLayer N W b).fwd v = batchMap N (dense W b) v

      The classifier layer's forward is the batched dense.

      def Proofs.HasVJPAt.congrOfEventuallyEq {m n : ℕ} {f g : Vec m → Vec n} {x : Vec m} (h : f =ᶠ[nhds x] g) (hf : HasVJPAt f x) :

      Transport a VJP along a local equality. pdiv reads only the germ of the map at the point (it is an fderiv), so a witness for f is one for any g that agrees with f near x, with the same backward. How a map that is not globally a composite of certified pieces still gets a certified VJP: the ReLU-then-pool stem is locally a gather.

      Equations
      Instances For
        theorem Proofs.maxPool3s2Flat_relu_eventuallyEq {c h w : ℕ} (z : Vec (c * (2 * h) * (2 * w))) (hz : ∀ (k : Fin (c * (2 * h) * (2 * w))), z k ≠ 0) (hs : MaxPool3s2SmoothOrDead (Tensor3.unflatten (relu (c * (2 * h) * (2 * w)) z))) :
        (fun (v : Vec (c * (2 * h) * (2 * w))) => maxPool3s2Flat c h w (relu (c * (2 * h) * (2 * w)) v)) =ᶠ[nhds z] fun (v : Vec (c * (2 * h) * (2 * w))) (k : Fin (c * h * w)) => relu (c * (2 * h) * (2 * w)) v (maxPool3s2LocalReindex (Tensor3.unflatten (relu (c * (2 * h) * (2 * w)) z)) k)

        ReLU then the 3×3/s2 pool is locally a gather. Near a pre-activation z with no zero entry, where every window of relu z is smooth or dead (MaxPool3s2SmoothOrDead), the pooled ReLU reads each output from the cell maxPool3s2LocalReindex (relu z) names. A smooth window keeps its strict maximum nearby. A dead window has every pre-activation strictly negative, so nearby its ReLUs are all 0 and any choice of cell reads 0. This is why a window of dead ReLUs, where the pool alone has no derivative, costs the composite nothing.

        def Proofs.StemPoolSmoothAt (N h w : ℕ) {oc : ℕ} (v : Vec (N * (oc * (2 * h) * (2 * w)))) :

        The stem pool's condition, per example: every 3×3 window of the post-ReLU stem activation has its maximum at one position, or is entirely zero (a window of dead ReLUs). A tie is a property of one image's window, so the condition is stated on each row of the batch.

        Real batches have many all-zero windows, and the pool alone has no derivative at any of them; the stem layer is certified as ReLU and pool together (stemReluPoolLayer), where a dead window is locally constant. What is still excluded is a window whose maximum is POSITIVE and attained at two positions. On real ImageNet batches such windows occur in every batch, and they come from two cells reading IDENTICAL input patches (flat image regions); there the stem has no derivative in the image, so an input-gradient statement must exclude them, but the two cells are the same function of the stem's weights, so the loss is still differentiable in the parameters; the loss-gradient statements take the weaker StemPoolTwinAt, which allows them. The probe script scripts/probes/stem_pool_smooth_probe.py counts all three kinds of window.

        Equations
        Instances For
          noncomputable def Proofs.maxPool3s2LocalReindexB (N c h w : ℕ) (y : Vec (N * (c * (2 * h) * (2 * w)))) :
          Fin (N * (c * h * w)) → Fin (N * (c * (2 * h) * (2 * w)))

          The batched argmax gather: output (r, k) reads example r's argmax cell for k.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            theorem Proofs.batchMap_maxPool3s2Flat_relu_eventuallyEq (N : ℕ) {c h w : ℕ} (Z : Vec (N * (c * (2 * h) * (2 * w)))) (hz : ∀ (k : Fin (N * (c * (2 * h) * (2 * w)))), Z k ≠ 0) (hs : StemPoolSmoothAt N h w (relu (N * (c * (2 * h) * (2 * w))) Z)) :
            (fun (v : Vec (N * (c * (2 * h) * (2 * w)))) => StableHLO.batchMap N (maxPool3s2Flat c h w) (relu (N * (c * (2 * h) * (2 * w))) v)) =ᶠ[nhds Z] fun (v : Vec (N * (c * (2 * h) * (2 * w)))) (k : Fin (N * (c * h * w))) => relu (N * (c * (2 * h) * (2 * w))) v (maxPool3s2LocalReindexB N c h w (relu (N * (c * (2 * h) * (2 * w))) Z) k)

            maxPool3s2Flat_relu_eventuallyEq over the batch, one example per row.

            theorem Proofs.maxPool3s2FlatBackB_eq_reindex (N c h w : ℕ) (y v : Vec (N * (c * (2 * h) * (2 * w)))) (dy : Vec (N * (c * h * w))) :

            The render's pool backward is the gather's scatter. maxPool3s2FlatBackB (what den maxPool3s2BackB is) sends each output cotangent to its argmax cell, which is exactly the adjoint of the gather maxPool3s2LocalReindexB, at every input.

            theorem Proofs.batchMap_maxPool3s2Flat_relu_differentiableAt (N : ℕ) {c h w : ℕ} (Z : Vec (N * (c * (2 * h) * (2 * w)))) (hz : ∀ (k : Fin (N * (c * (2 * h) * (2 * w)))), Z k ≠ 0) (hs : StemPoolSmoothAt N h w (relu (N * (c * (2 * h) * (2 * w))) Z)) :
            DifferentiableAt ℝ (fun (v : Vec (N * (c * (2 * h) * (2 * w)))) => StableHLO.batchMap N (maxPool3s2Flat c h w) (relu (N * (c * (2 * h) * (2 * w))) v)) Z

            The batched ReLU-then-pool is differentiable at a smooth-or-dead pre-activation.

            noncomputable def Proofs.batchMapMaxPool3s2FlatReluHasVJPAt (N : ℕ) {c h w : ℕ} (Z : Vec (N * (c * (2 * h) * (2 * w)))) (hz : ∀ (k : Fin (N * (c * (2 * h) * (2 * w)))), Z k ≠ 0) (hs : StemPoolSmoothAt N h w (relu (N * (c * (2 * h) * (2 * w))) Z)) :
            HasVJPAt (fun (v : Vec (N * (c * (2 * h) * (2 * w)))) => StableHLO.batchMap N (maxPool3s2Flat c h w) (relu (N * (c * (2 * h) * (2 * w))) v)) Z

            The batched ReLU-then-pool's VJP at a smooth-or-dead pre-activation: scatter to the argmax cells, then the ReLU mask.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              theorem Proofs.batchMapMaxPool3s2FlatReluHasVJPAt_backward (N : ℕ) {c h w : ℕ} (Z : Vec (N * (c * (2 * h) * (2 * w)))) (hz : ∀ (k : Fin (N * (c * (2 * h) * (2 * w)))), Z k ≠ 0) (hs : StemPoolSmoothAt N h w (relu (N * (c * (2 * h) * (2 * w))) Z)) (dy : Vec (N * (c * h * w))) :
              (batchMapMaxPool3s2FlatReluHasVJPAt N Z hz hs).backward dy = (reluHasVJPAt (N * (c * (2 * h) * (2 * w))) Z hz).backward (maxPool3s2FlatBackB N c h w (relu (N * (c * (2 * h) * (2 * w))) Z) dy)

              Its backward is the render's pool scatter, then the ReLU mask.

              theorem Proofs.pdiv_congr_of_eventuallyEq {m n : ℕ} {f g : Vec m → Vec n} {x : Vec m} (h : f =ᶠ[nhds x] g) (i : Fin m) (j : Fin n) :
              pdiv f x i j = pdiv g x i j

              pdiv reads only the germ. Maps that agree near x have the same partials there.

              def Proofs.StemPoolTwinAt (N h w : ℕ) {oc : ℕ} (T : Fin N → Fin (2 * h) × Fin (2 * w) → Fin (2 * h) × Fin (2 * w) → Prop) (v : Vec (N * (oc * (2 * h) * (2 * w)))) :

              The stem pool's condition along a parameter, per example: every window of the post-ReLU stem activation is dead, or has its maximum strictly above every cell at another position except the positions T r twins with it (MaxPool3s2SmoothUpTo). Weaker than StemPoolSmoothAt (stemPoolTwinAt_of_smoothAt). It is what a parameter gradient needs: twinned cells tie at every parameter value, so the pool's choice between them does not move (stemPoolRelu_param_eventuallyEq_select).

              Equations
              Instances For
                theorem Proofs.stemPoolTwinAt_of_smoothAt (N h w : ℕ) {oc : ℕ} (T : Fin N → Fin (2 * h) × Fin (2 * w) → Fin (2 * h) × Fin (2 * w) → Prop) {v : Vec (N * (oc * (2 * h) * (2 * w)))} (hv : StemPoolSmoothAt N h w v) :
                StemPoolTwinAt N h w T v
                def Proofs.IsMaxPool3s2SelectB (N c h w : ℕ) (y : Vec (N * (c * (2 * h) * (2 * w)))) (σ : Fin (N * (c * h * w)) → Fin (N * (c * (2 * h) * (2 * w)))) :

                A pool selector at y: output (r, co, ho, wo) reads a cell of its own 3×3 window (example r, channel co) that holds the window's maximum. Where a window's maximum is attained once, every selector reads that cell; at a tie each picks one of the tied cells. The argmax gather maxPool3s2LocalReindexB is one selector (maxPool3s2LocalReindexB_isSelect), and so is the render's select_and_scatter with its GE select, which routes each window's cotangent to one maximal cell (the first in window order).

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  theorem Proofs.maxPool3s2LocalReindexB_isSelect (N c h w : ℕ) (y : Vec (N * (c * (2 * h) * (2 * w)))) :

                  The argmax gather is a pool selector.

                  theorem Proofs.stemPoolRelu_param_eventuallyEq_select {k N c h w : ℕ} (Z : Vec k → Vec (N * (c * (2 * h) * (2 * w)))) (θ₀ : Vec k) (hZ : ContinuousAt Z θ₀) (hz : ∀ (i : Fin (N * (c * (2 * h) * (2 * w)))), Z θ₀ i ≠ 0) (T : Fin N → Fin (2 * h) × Fin (2 * w) → Fin (2 * h) × Fin (2 * w) → Prop) (hs : StemPoolTwinAt N h w T (relu (N * (c * (2 * h) * (2 * w))) (Z θ₀))) (htwin : ∀ (θ : Vec k) (r : Fin N) (ci : Fin c) (p q : Fin (2 * h) × Fin (2 * w)), T r p q → Z θ (finProdFinEquiv (r, finProdFinEquiv (finProdFinEquiv (ci, p.1), p.2))) = Z θ (finProdFinEquiv (r, finProdFinEquiv (finProdFinEquiv (ci, q.1), q.2)))) (σ : Fin (N * (c * h * w)) → Fin (N * (c * (2 * h) * (2 * w)))) (hσ : IsMaxPool3s2SelectB N c h w (relu (N * (c * (2 * h) * (2 * w))) (Z θ₀)) σ) :
                  (fun (θ : Vec k) => StableHLO.batchMap N (maxPool3s2Flat c h w) (relu (N * (c * (2 * h) * (2 * w))) (Z θ))) =ᶠ[nhds θ₀] fun (θ : Vec k) (k : Fin (N * (c * h * w))) => relu (N * (c * (2 * h) * (2 * w))) (Z θ) (σ k)

                  Along a parameter, ReLU then the pool is a fixed gather, for ANY pool selector σ at θ₀. Z θ is the pre-ReLU stem activation as the parameter moves; at θ₀ it has no zero entry, every window of its ReLU is smooth up to twins, and twinned cells are equal at EVERY θ. Then near θ₀ the pooled ReLU reads each output from the cell σ names: a dead window stays negative, a strict maximum stays strict, and a twin stays tied with the chosen cell. Which of two tied twins σ picks does not matter, since they are equal near θ₀.

                  theorem Proofs.gatherRelu_differentiableAt {m n : ℕ} (σ : Fin n → Fin m) (Z : Vec m) (hz : ∀ (k : Fin m), Z k ≠ 0) :
                  DifferentiableAt ℝ (fun (v : Vec m) (k : Fin n) => relu m v (σ k)) Z

                  The gather model v ↦ relu v ∘ σ: linear after the ReLU, so differentiable at any point with no zero entry, whatever σ.

                  noncomputable def Proofs.gatherReluHasVJPAt {m n : ℕ} (σ : Fin n → Fin m) (Z : Vec m) (hz : ∀ (k : Fin m), Z k ≠ 0) :
                  HasVJPAt (fun (v : Vec m) (k : Fin n) => relu m v (σ k)) Z

                  The gather model's VJP: scatter along σ, then the ReLU mask.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    theorem Proofs.gatherReluHasVJPAt_stem_backward (N : ℕ) {c h w : ℕ} (Z : Vec (N * (c * (2 * h) * (2 * w)))) (hz : ∀ (k : Fin (N * (c * (2 * h) * (2 * w)))), Z k ≠ 0) (dy : Vec (N * (c * h * w))) :
                    (gatherReluHasVJPAt (maxPool3s2LocalReindexB N c h w (relu (N * (c * (2 * h) * (2 * w))) Z)) Z hz).backward dy = (reluHasVJPAt (N * (c * (2 * h) * (2 * w))) Z hz).backward (maxPool3s2FlatBackB N c h w (relu (N * (c * (2 * h) * (2 * w))) Z) dy)

                    At the stem's argmax gather, the model's VJP is the render's pool scatter, then the ReLU mask.

                    theorem Proofs.stemPool_eventuallyEq (N : ℕ) {ic c h w kH kW : ℕ} (W : Kernel4 c ic kH kW) (b : Vec c) (ε : ℝ) (hε : 0 < ε) (γ β : Vec c) (x : Vec (N * (ic * (2 * (2 * h)) * (2 * (2 * w))))) (hz : ∀ (k : Fin (N * (c * (2 * h) * (2 * w)))), StableHLO.bnBatchLA N c (2 * h) (2 * w) ε γ β (StableHLO.batchMap N (flatConvStride2 W b) x) k ≠ 0) (hs : StemPoolSmoothAt N h w (StableHLO.cbReluStridedB N W b ε γ β x)) :
                    StableHLO.batchMap N (maxPool3s2Flat c h w) ∘ StableHLO.cbReluStridedB N W b ε γ β =ᶠ[nhds x] (fun (y : Vec (N * (c * (2 * h) * (2 * w)))) (k : Fin (N * (c * h * w))) => y (maxPool3s2LocalReindexB N c h w (StableHLO.cbReluStridedB N W b ε γ β x) k)) ∘ StableHLO.cbReluStridedB N W b ε γ β

                    The pooled stem agrees near x with the argmax gather of the stem's post-ReLU output.

                    noncomputable def Proofs.stemReluPoolLayer (N : ℕ) {ic c h w kH kW : ℕ} (W : Kernel4 c ic kH kW) (b : Vec c) (ε : ℝ) (hε : 0 < ε) (γ β : Vec c) :
                    StableHLO.CertLayer (N * (ic * (2 * (2 * h)) * (2 * (2 * w)))) (N * (c * h * w))

                    The ResNet stem, strided conv-BN-ReLU then the 3×3/s2 pool, as ONE certified layer.

                    It is one layer, not cbReluStridedLayer.comp of a pool layer, because the pool alone is not differentiable at a window of dead ReLUs, and real batches have many. Together they are: near the input the pooled stem is the argmax gather of the ReLU output (stemPool_eventuallyEq), so its VJP is the conv-BN-ReLU stage's after the gather's scatter, and that scatter is what the render's maxPool3s2BackB denotes (maxPool3s2FlatBackB_eq_reindex). The forward and the backward graph are the two-layer composite's, so the rendered stem is unchanged; only the certification domain grows.

                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For
                      theorem Proofs.stemReluPoolLayer_vjp_backward (N : ℕ) {ic c h w kH kW : ℕ} (W : Kernel4 c ic kH kW) (b : Vec c) (ε : ℝ) (hε : 0 < ε) (γ β : Vec c) (x : Vec (N * (ic * (2 * (2 * h)) * (2 * (2 * w))))) (hx : (stemReluPoolLayer N W b ε hε γ β).ok x) (dy : Vec (N * (c * h * w))) :
                      ((stemReluPoolLayer N W b ε hε γ β).vjp x hx).backward dy = (StableHLO.cbReluStridedBHasVJPAt N W b ε hε γ β x ⋯).backward (maxPool3s2FlatBackB N c h w (StableHLO.cbReluStridedB N W b ε γ β x) dy)

                      The stem layer's VJP is the conv-BN-ReLU stage's after the render's pool scatter.