Documentation

LeanMlir.Proofs.Foundation.DataParallel.Sync

Data parallelism with synchronised BatchNorm — the DP step IS the global-batch step #

DataParallel.Basic proves that a data-parallel step on a per-replica-BN net is a step on the mean of R per-replica losses and not the batch-R·N step (dpMeanGrad_ne_globalBatchGrad); DataParallel.Node puts the collective in the AST. With the sync-BN ops (StableHLO.bnBatchVarAtB, bnPackB, bnSyncF, bnSyncDyStatsB, bnSyncBack, bnSyncGammaGradB, bnStatsMeanB/VarB) the negative result reverses, and this file is what a per-net DP twin walks its chain with.

What is proved #

The 1/R, and where it goes #

A DP render divides its loss cotangent by the PER-REPLICA batch (divConstB N); the single-device batch-R·N step it is compared to divides by R·N. So at a common per-example cotangent the replica mean is 1/R of the global sum, and the two divisors differ by exactly that R. A per-net twin closes it with ONE linearity step — the whole-net backward is a HasVJP.backward, and HasVJP.backward_smul says scaling the cotangent scales the gradient — instead of threading a factor through every op of the chain.

What is NOT claimed #

Nothing here is a whole-net statement. The chain induction is per net: this file supplies the BN case and the commutation lemmas the non-BN cases reduce to, and each net's DP twin walks its own chain with them. That the R graphs' host inputs ARE the replica shards of one batch — hx / hxv / hdy below — remains the driver's, exactly as in DataParallel.Node. The lowerer's all_reduce is trusted as every other op's lowering is.

noncomputable def Proofs.bnchwChan (N oc h w : ℕ) (t : Fin (N * (oc * (h * w)))) :
Fin oc

The channel a [N,C,H,W] flat index belongs to.

Equations
Instances For
    theorem Proofs.bnSyncTensor4_apply (N oc h w : ℕ) (ε : ℝ) (γ β μ m2 : Vec oc) (x : Vec (N * (oc * (h * w)))) (t : Fin (N * (oc * (h * w)))) :
    bnSyncTensor4 N oc h w ε γ β μ m2 x t = γ (bnchwChan N oc h w t) * ((x t - μ (bnchwChan N oc h w t)) * (1 / √(m2 (bnchwChan N oc h w t) - μ (bnchwChan N oc h w t) * μ (bnchwChan N oc h w t) + ε))) + β (bnchwChan N oc h w t)

    The sync forward is POINTWISE once its statistics are fixed.

    Cell t becomes γ_c·(x_t − μ_c)·(m2_c − μ_c² + ε)^(−1/2) + β_c with c its own channel — no other cell is read. Cells mix ONLY when the statistics are computed, and under sync-BN that computation has been hoisted out into the collective.

    This is what makes the shard argument (bnSyncTensor4_batchShard) pure index bookkeeping: a pointwise map commutes with any reindexing that preserves the channel, and sharding the batch does.

    noncomputable def Proofs.batchShard (R N a : ℕ) (X : Vec (R * N * a)) (r : Fin R) :
    Vec (N * a)

    Shard r's block of a global batch laid out row-major [R·N, a]: example (r, n) of the global batch is example n of shard r. The contiguous cut the DP shim makes.

    Equations
    Instances For
      theorem Proofs.bnchwChan_batchShard (R N oc h w : ℕ) (r : Fin R) (idx : Fin (N * (oc * (h * w)))) :

      Sharding the batch does not move a cell's CHANNEL. The one fact P1 needs about the layout: the batch axis is outside the channel axis in [N,C,H,W], so cutting the batch leaves every cell in the channel it was already in.

      noncomputable def Proofs.bnShardEquiv (R N hw : ℕ) :
      Fin R × Fin (N * hw) ≃ Fin (R * N * hw)

      The shard of a channel's ROW. Channel c of a global [R·N,C,H,W] batch is a (R·N)·h·w-wide row; this is the equiv exhibiting it as R blocks of N·h·w, one per replica — (r, (n,s)) ↦ ((r,n), s). The row-level counterpart of batchShard.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        theorem Proofs.bnchwFwd_row_batchShard (R N oc h w : ℕ) (X : Vec (R * N * (oc * (h * w)))) (c : Fin oc) (r : Fin R) (k : Fin (N * (h * w))) :
        Mat.unflatten (bnchwFwd (R * N) oc h w X) c ((bnShardEquiv R N (h * w)) (r, k)) = Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r)) c k

        The global channel row, restricted to replica r's block, IS that replica's own channel row. The layout fact that connects a batch shard to the [C, N·H·W] world bnPerChannelFlat reduces in — i.e. the one step the bnchwFwd relabel was hiding.

        theorem Proofs.bnSyncTensor4_batchShard (R N oc h w : ℕ) (ε : ℝ) (γ β μ m2 : Vec oc) (X : Vec (R * N * (oc * (h * w)))) (r : Fin R) :
        batchShard R N (oc * (h * w)) (bnSyncTensor4 (R * N) oc h w ε γ β μ m2 X) r = bnSyncTensor4 N oc h w ε γ β μ m2 (batchShard R N (oc * (h * w)) X r)

        P1a — the sync forward COMMUTES WITH SHARDING, for any statistics at all.

        shard_r ∘ (sync BN at μ, m2) = (sync BN at μ, m2) ∘ shard_r. No hypothesis on μ/m2: once the statistics are fixed the map is pointwise (bnSyncTensor4_apply) and sharding preserves each cell's channel (bnchwChan_batchShard), so there is nothing to prove about BatchNorm here — only about indices.

        This is the half of P1 that carries no mathematics, and separating it is what leaves the real content in one place: whether the handed-in statistics ARE the global ones, which is bnMean_shard/bnMeanSq_shard, i.e. exactly what allReduceMeanF computes.

        theorem Proofs.bnMean_row_shard (R N oc h w : ℕ) (hR : R ≠ 0) (hm : N * (h * w) ≠ 0) (X : Vec (R * N * (oc * (h * w)))) (c : Fin oc) :
        bnMean (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c) = 1 / ↑R * ∑ r : Fin R, bnMean (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r)) c)

        P1b — the GLOBAL per-channel mean is the mean of the replicas' per-channel means. bnMean_shard transported along the row shard. This is precisely what syncStats's first collective — allReduceMeanF over the replicas' bnBatchMeanB — computes.

        theorem Proofs.bnMeanSq_row_shard (R N oc h w : ℕ) (hR : R ≠ 0) (hm : N * (h * w) ≠ 0) (X : Vec (R * N * (oc * (h * w)))) (c : Fin oc) :
        bnMeanSq (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c) = 1 / ↑R * ∑ r : Fin R, bnMeanSq (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r)) c)

        …and so is the global per-channel SECOND MOMENT. Note: There is no such statement for the variance alone — the mean of the shards' variances is not the variance of the union — which is why the exchange carries Chan's corrected variance (bnVar_row_shard_chan) rather than a plain σ²_r.

        theorem Proofs.bnVar_row_shard_chan (R N oc h w : ℕ) (hR : R ≠ 0) (hm : N * (h * w) ≠ 0) (X : Vec (R * N * (oc * (h * w)))) (c : Fin oc) :
        bnVar (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c) = 1 / ↑R * ∑ r : Fin R, (bnVar (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r)) c) + (bnMean (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r)) c) - bnMean (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c)) * (bnMean (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r)) c) - bnMean (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c)))

        Chan's parallel variance on the channel rows: the global channel variance is the replica mean of each replica's own two-pass variance plus its mean's squared offset from the global mean. This is what the second collective of a sync-BN forward carries (StableHLO.bnBatchVarAtB), and it is why no consumer ever forms E[x²] − μ².

        theorem Proofs.bnMean_pair_row_shard (R N oc h w : ℕ) (hR : R ≠ 0) (hm : N * (h * w) ≠ 0) (X DY : Vec (R * N * (oc * (h * w)))) (c : Fin oc) (f : ℝ → ℝ → ℝ) :
        (bnMean (R * N * (h * w)) fun (k : Fin (R * N * (h * w))) => f (Mat.unflatten (bnchwFwd (R * N) oc h w X) c k) (Mat.unflatten (bnchwFwd (R * N) oc h w DY) c k)) = 1 / ↑R * ∑ r : Fin R, bnMean (N * (h * w)) fun (k : Fin (N * (h * w))) => f (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r)) c k) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) DY r)) c k)

        P2b's workhorse: a mean over the global batch of ANY pointwise function of two rows is the mean of the replicas' means of the same. Both dy-reductions the sync backward needs have this shape — mdy reads only dy, mdyx reads x and dy together — so one lemma covers both, and bnMean_row_shard is its one-row special case.

        theorem Proofs.mulR_nhw_ne_zero {R N h w : ℕ} (hR : 0 < R) (hm : N * (h * w) ≠ 0) :
        R * N * (h * w) ≠ 0

        The global batch-spatial count is nonzero when a replica's is: (R·N)·(h·w) = R·(N·(h·w)).

        theorem Proofs.bnSyncTensor4_shard_eq_global (R N oc h w : ℕ) (hR : R ≠ 0) (hm : N * (h * w) ≠ 0) (ε : ℝ) (γ β : Vec oc) (X : Vec (R * N * (oc * (h * w)))) (r : Fin R) :
        bnSyncTensor4 N oc h w ε γ β (fun (c : Fin oc) => 1 / ↑R * ∑ r' : Fin R, bnMean (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r')) c)) (fun (c : Fin oc) => 1 / ↑R * ∑ r' : Fin R, bnMeanSq (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r')) c)) (batchShard R N (oc * (h * w)) X r) = batchShard R N (oc * (h * w)) (bnBatchTensor4 (R * N) oc h w ε γ β X) r

        P1 — SYNC-BN ON REPLICA r IS THE SHARD-r BLOCK OF THE GLOBAL-BATCH BN.

        Handed the GLOBAL statistics — (1/R)·Σ_r of each replica's own bnMean and bnMeanSq, which is what syncStats denotes once its σ² is read back as m2 = σ² + μ² — replica r's sync forward on its own shard equals batchShard r of bnBatchTensor4 run on the whole R·N batch.

        The spec does not move: the right-hand side is the EXISTING bnBatchTensor4, at N := R·N. Nothing new is being specified; the render is being shown to hit a target the tier already names.

        It is P1a (pointwise, so sharding commutes — no mathematics) composed with P1b (the statistics really are the all-reduced ones — all the mathematics) through bnSyncTensor4_at_own_stats.

        theorem Proofs.bnSyncPerChannelGradGamma_row_shard (R N oc h w : ℕ) (ε : ℝ) (μ m2 : Vec oc) (X DY : Vec (R * N * (oc * (h * w)))) (c : Fin oc) :
        bnSyncPerChannelGradGamma oc (R * N * (h * w)) ε μ m2 (bnchwFwd (R * N) oc h w X) (bnchwFwd (R * N) oc h w DY) c = ∑ r : Fin R, bnSyncPerChannelGradGamma oc (N * (h * w)) ε μ m2 (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r)) (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) DY r)) c

        A channel's γ gradient over the global batch is the SUM of the replicas' γ gradients at the same handed-in statistics — a sum, not a mean, because this is a parameter gradient: the parameter collective's 1/R is what turns it into the global-batch mean. The row split bnchwFwd_row_batchShard, under Σ instead of bnMean.

        theorem Proofs.bnPerChannelGradBeta_row_shard (R N oc h w : ℕ) (DY : Vec (R * N * (oc * (h * w)))) (c : Fin oc) :
        bnPerChannelGradBeta oc (R * N * (h * w)) (bnchwFwd (R * N) oc h w DY) c = ∑ r : Fin R, bnPerChannelGradBeta oc (N * (h * w)) (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) DY r)) c

        …and so is the β gradient, which reads no statistic at all: Σ dy over the global channel row is the sum of the shards' Σ dy.

        theorem Proofs.bnSyncPerChannelGradInput_apply (oc m : ℕ) (ε : ℝ) (γ μ m2 mdy mdyx : Vec oc) (x dy : Vec (oc * m)) (idx : Fin (oc * m)) :
        bnSyncPerChannelGradInput oc m ε γ μ m2 mdy mdyx x dy idx = 1 / √(m2 (finProdFinEquiv.symm idx).1 - μ (finProdFinEquiv.symm idx).1 * μ (finProdFinEquiv.symm idx).1 + ε) * (γ (finProdFinEquiv.symm idx).1 * dy idx - mdy (finProdFinEquiv.symm idx).1 - (x idx - μ (finProdFinEquiv.symm idx).1) * (1 / √(m2 (finProdFinEquiv.symm idx).1 - μ (finProdFinEquiv.symm idx).1 * μ (finProdFinEquiv.symm idx).1 + ε)) * mdyx (finProdFinEquiv.symm idx).1)

        The sync backward is POINTWISE too, with the channel read off the index — it reads only x idx and dy idx. Both its reductions were hoisted into the collective.

        theorem Proofs.bnSyncTensor4GradInput_apply (N oc h w : ℕ) (ε : ℝ) (γ μ m2 mdy mdyx : Vec oc) (x dy : Vec (N * (oc * (h * w)))) (t : Fin (N * (oc * (h * w)))) :
        bnSyncTensor4GradInput N oc h w ε γ μ m2 mdy mdyx x dy t = 1 / √(m2 (bnchwChan N oc h w t) - μ (bnchwChan N oc h w t) * μ (bnchwChan N oc h w t) + ε) * (γ (bnchwChan N oc h w t) * dy t - mdy (bnchwChan N oc h w t) - (x t - μ (bnchwChan N oc h w t)) * (1 / √(m2 (bnchwChan N oc h w t) - μ (bnchwChan N oc h w t) * μ (bnchwChan N oc h w t) + ε)) * mdyx (bnchwChan N oc h w t))

        The [N,C,H,W] lift: cell t of the sync backward depends only on x t, dy t and its own channel's four statistics.

        theorem Proofs.bnSyncTensor4GradInput_batchShard (R N oc h w : ℕ) (ε : ℝ) (γ μ m2 mdy mdyx : Vec oc) (X DY : Vec (R * N * (oc * (h * w)))) (r : Fin R) :
        batchShard R N (oc * (h * w)) (bnSyncTensor4GradInput (R * N) oc h w ε γ μ m2 mdy mdyx X DY) r = bnSyncTensor4GradInput N oc h w ε γ μ m2 mdy mdyx (batchShard R N (oc * (h * w)) X r) (batchShard R N (oc * (h * w)) DY r)

        P2a — the sync backward COMMUTES WITH SHARDING, for any statistics at all. The backward twin of bnSyncTensor4_batchShard, and equally free of mathematics: pointwise plus channel-preserving reindex.

        theorem Proofs.bnSyncTensor4GradInput_at_own_stats' (N oc h w : ℕ) (hm : N * (h * w) ≠ 0) (ε : ℝ) (γ : Vec oc) (x dy : Vec (N * (oc * (h * w)))) :
        bnSyncTensor4GradInput N oc h w ε γ (fun (c : Fin oc) => bnMean (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w x) c)) (fun (c : Fin oc) => bnMeanSq (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w x) c)) (fun (c : Fin oc) => bnMean (N * (h * w)) fun (k : Fin (N * (h * w))) => γ c * Mat.unflatten (bnchwFwd N oc h w dy) c k) (fun (c : Fin oc) => bnMean (N * (h * w)) fun (k : Fin (N * (h * w))) => bnSyncXhat (N * (h * w)) ε (bnMean (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w x) c)) (bnMeanSq (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w x) c)) (Mat.unflatten (bnchwFwd N oc h w x) c) k * (γ c * Mat.unflatten (bnchwFwd N oc h w dy) c k)) x dy = bnBatchTensor4GradInput N oc h w ε γ x dy

        The R = 1 backward anchor restated with bnSyncXhat in the mdyx reduction — the form the sync GRAPH produces, since bnSyncDyStatsB builds x̂ from the statistics handed to it rather than from x directly.

        theorem Proofs.bnSyncTensor4GradInput_shard_eq_global (R N oc h w : ℕ) (hR : R ≠ 0) (hm : N * (h * w) ≠ 0) (ε : ℝ) (γ : Vec oc) (X DY : Vec (R * N * (oc * (h * w)))) (r : Fin R) (μg m2g mdyg mdyxg : Vec oc) (hμ : μg = fun (c : Fin oc) => 1 / ↑R * ∑ r' : Fin R, bnMean (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r')) c)) (hm2 : m2g = fun (c : Fin oc) => 1 / ↑R * ∑ r' : Fin R, bnMeanSq (N * (h * w)) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r')) c)) (hmdy : mdyg = fun (c : Fin oc) => 1 / ↑R * ∑ r' : Fin R, bnMean (N * (h * w)) fun (k : Fin (N * (h * w))) => γ c * Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) DY r')) c k) (hmdyx : mdyxg = fun (c : Fin oc) => 1 / ↑R * ∑ r' : Fin R, bnMean (N * (h * w)) fun (k : Fin (N * (h * w))) => bnSyncXhat (N * (h * w)) ε (μg c) (m2g c) (Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) X r')) c) k * (γ c * Mat.unflatten (bnchwFwd N oc h w (batchShard R N (oc * (h * w)) DY r')) c k)) :
        bnSyncTensor4GradInput N oc h w ε γ μg m2g mdyg mdyxg (batchShard R N (oc * (h * w)) X r) (batchShard R N (oc * (h * w)) DY r) = batchShard R N (oc * (h * w)) (bnBatchTensor4GradInput (R * N) oc h w ε γ X DY) r

        P2 — THE SYNC BACKWARD ON REPLICA r IS THE SHARD-r BLOCK OF THE GLOBAL-BATCH INPUT-VJP.

        Handed the four all-reduced statistics — each literally (1/R)·Σ_r' of a per-replica quantity, which is what syncStats, then allReduceMeanF of bnSyncDyStatsB, denotes — replica r's sync backward equals batchShard r of bnBatchTensor4GradInput run on the whole R·N batch.

        Including the cross-shard terms. mdyx averages x̂·dx̂ with x̂ built from the GLOBAL μ, m2 — not from the shard's own statistics — which is exactly why bnSyncDyStatsB consumes the already-reduced vector instead of recomputing one. That is what makes each replica's output the true shard-r block of the global gradient, and hence the all-reduced PARAMETER gradient exact rather than approximate.

        The spec does not move: the right-hand side is the existing bnBatchTensor4GradInput at N := R·N.

        theorem Proofs.batchSlice_batchShard {R N a : ℕ} (X : Vec (R * N * a)) (r : Fin R) (n : Fin N) :

        Example n of shard r is example (r, n) of the global batch.

        theorem Proofs.batchShard_batchMap {R N a b : ℕ} (f : Vec a → Vec b) (X : Vec (R * N * a)) (r : Fin R) :
        batchShard R N b (StableHLO.batchMap (R * N) f X) r = StableHLO.batchMap N f (batchShard R N a X r)

        batchMap commutes with sharding — the block analogue of batchSlice_batchMap. A per-example lift applied to the global batch, restricted to replica r, is the same lift applied to replica r's shard: so every conv, relu, pool, GAP and dense node in a DP render denotes batchShard r of its batch-R·N value as soon as its input does.

        theorem Proofs.batchShard_batchMapAux {R N s a b : ℕ} (f : Vec s → Vec a → Vec b) (aux : Vec (R * N * s)) (X : Vec (R * N * a)) (r : Fin R) :
        batchShard R N b (StableHLO.batchMapAux (R * N) f aux X) r = StableHLO.batchMapAux N f (batchShard R N s aux r) (batchShard R N a X r)

        …and so does batchMapAux, the shape of every batched backward that recomputes from a saved per-example activation: example n is handed ITS slice of aux, which sharding respects.

        theorem Proofs.batchShard_map {R N a : ℕ} (φ : ℝ → ℝ) (X : Vec (R * N * a)) (r : Fin R) :
        batchShard R N a (fun (i : Fin (R * N * a)) => φ (X i)) r = fun (i : Fin (N * a)) => φ (batchShard R N a X r i)

        A pointwise map commutes with sharding (scaleB, shiftB, divConstB, …).

        theorem Proofs.batchShard_zipWith {R N a : ℕ} (φ : ℝ → ℝ → ℝ) (X Y : Vec (R * N * a)) (r : Fin R) :
        batchShard R N a (fun (i : Fin (R * N * a)) => φ (X i) (Y i)) r = fun (i : Fin (N * a)) => φ (batchShard R N a X r i) (batchShard R N a Y r i)

        A pointwise binary map commutes with sharding (addVB, subB, the relu mask selectPosB against its saved activation, …).

        theorem Proofs.dpMean_const_mul {R : ℕ} (hR : ↑R ≠ 0) (K : ℝ) :
        1 / ↑R * ∑ _r : Fin R, K = K

        The replica mean of a replica-independent value is that value. bnSyncDyStatsB passes the already-global [μ ‖ m2] through the second collective, and this is why that costs nothing.

        def Proofs.syncStats {N oc h w : ℕ} (R : ℕ) (hR : 0 < R) (t t' : String) (ds ds' : List ℕ) (x : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) :

        The sync-BN statistics subgraph a render emits: the replicas' means all-reduced, then their Chan-corrected variances at that mean all-reduced, packed as [μ ‖ σ²]. The same expression on every replica — the collective is what makes it replica-independent.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          theorem Proofs.den_syncStats_left {N oc h w : ℕ} (R : ℕ) (hR : 0 < R) (hm : N * (h * w) ≠ 0) (t t' : String) (ds ds' : List ℕ) (x : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) (X : Vec (R * N * (oc * (h * w)))) (hx : ∀ (r : Fin R), StableHLO.den (x r) = batchShard R N (oc * (h * w)) X r) (c : Fin oc) :
          StableHLO.den (syncStats R hR t t' ds ds' x) (Fin.castAdd oc c) = bnMean (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c)

          The first collective IS the global mean — bnMean_shard on the channel rows.

          theorem Proofs.den_syncStats_right {N oc h w : ℕ} (R : ℕ) (hR : 0 < R) (hm : N * (h * w) ≠ 0) (t t' : String) (ds ds' : List ℕ) (x : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) (X : Vec (R * N * (oc * (h * w)))) (hx : ∀ (r : Fin R), StableHLO.den (x r) = batchShard R N (oc * (h * w)) X r) (c : Fin oc) :
          StableHLO.den (syncStats R hR t t' ds ds' x) (Fin.natAdd oc c) = bnVar (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c)

          The second collective IS the global variance — Chan's parallel variance (bnVar_row_shard_chan): each replica's two-pass σ²_r plus (μ_r − μ)², averaged. This is the lemma a one-round E[x²] exchange does not have.

          theorem Proofs.global_var_add_sq {N oc h w : ℕ} (R : ℕ) (hM : R * N * (h * w) ≠ 0) (X : Vec (R * N * (oc * (h * w)))) (c : Fin oc) :
          bnVar (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c) + bnMean (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c) * bnMean (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c) = bnMeanSq (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c)

          σ² + μ² at the global statistics is the global second moment — how a consumer's den, stated at (μ, m2), reads the packed [μ ‖ σ²].

          theorem Proofs.den_bnSyncF_allReduce {N oc h w : ℕ} (R : ℕ) (hR : 0 < R) (hm : N * (h * w) ≠ 0) (gN bN es t t' : String) (ds ds' : List ℕ) (ε : ℝ) (γ β : Vec oc) (x : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) (X : Vec (R * N * (oc * (h * w)))) (hx : ∀ (r : Fin R), StableHLO.den (x r) = batchShard R N (oc * (h * w)) X r) (r : Fin R) :
          StableHLO.den (StableHLO.SHlo.bnSyncF gN bN es ε γ β (x r) (syncStats R hR t t' ds ds' x)) = batchShard R N (oc * (h * w)) (bnBatchTensor4 (R * N) oc h w ε γ β X) r

          P1 on the graph, any R. Replica r's bnSyncF, fed by the two-round statistics subgraph over the R replicas' inputs, denotes batchShard r of the batch-R·N bnBatchTensor4 — given that each replica's operand denotes its shard (hx, the chain's induction hypothesis). den_bnSyncF_allReduce_R1 is this at R := 1.

          theorem Proofs.den_bnSyncBack_allReduce {N oc h w : ℕ} (R : ℕ) (hR : 0 < R) (hm : N * (h * w) ≠ 0) (gN xN es t t' t'' : String) (ds ds' ds'' : List ℕ) (ε : ℝ) (γ : Vec oc) (x : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) (xv : Fin R → Vec (N * (oc * (h * w)))) (dy : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) (X DY : Vec (R * N * (oc * (h * w)))) (hx : ∀ (r : Fin R), StableHLO.den (x r) = batchShard R N (oc * (h * w)) X r) (hxv : ∀ (r : Fin R), xv r = batchShard R N (oc * (h * w)) X r) (hdy : ∀ (r : Fin R), StableHLO.den (dy r) = batchShard R N (oc * (h * w)) DY r) (r : Fin R) :
          StableHLO.den (StableHLO.SHlo.bnSyncBack gN xN es ε γ (xv r) (dy r) (StableHLO.SHlo.allReduceMeanF R hR t'' ds'' fun (r' : Fin R) => StableHLO.SHlo.bnSyncDyStatsB gN xN es ε γ (xv r') (dy r') (syncStats R hR t t' ds ds' x))) = batchShard R N (oc * (h * w)) (bnBatchTensor4GradInput (R * N) oc h w ε γ X DY) r

          P2 on the graph, any R. Replica r's bnSyncBack, fed by the collective over the replicas' bnSyncDyStatsB (each reading the packed forward statistics), denotes batchShard r of the batch-R·N bnBatchTensor4GradInput — given that each replica's saved activation and its incoming cotangent are its shards of the global ones (hx / hxv, hdy). den_bnSyncBack_allReduce_R1 is this at R := 1.

          theorem Proofs.den_allReduceMeanF_bnSyncGammaGradB {N oc h w : ℕ} (R : ℕ) (hR : 0 < R) (hm : N * (h * w) ≠ 0) (xN es t t' t'' : String) (ds ds' ds'' : List ℕ) (ε : ℝ) (x : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) (xv : Fin R → Vec (N * (oc * (h * w)))) (dy : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) (X DY : Vec (R * N * (oc * (h * w)))) (hx : ∀ (r : Fin R), StableHLO.den (x r) = batchShard R N (oc * (h * w)) X r) (hxv : ∀ (r : Fin R), xv r = batchShard R N (oc * (h * w)) X r) (hdy : ∀ (r : Fin R), StableHLO.den (dy r) = batchShard R N (oc * (h * w)) DY r) (c : Fin oc) :
          StableHLO.den (StableHLO.SHlo.allReduceMeanF R hR t'' ds'' fun (r : Fin R) => StableHLO.SHlo.bnSyncGammaGradB xN es ε (xv r) (dy r) (syncStats R hR t t' ds ds' x)) c = 1 / ↑R * bnPerChannelGradGamma oc (R * N * (h * w)) ε (bnchwFwd (R * N) oc h w X) (bnchwFwd (R * N) oc h w DY) c

          P2γ on the graph, any R, already all-reduced. The parameter collective over the replicas' bnSyncGammaGradB — each at its shard, its shard's cotangent and the packed global statistics — is 1/R of bnPerChannelGradGamma at N := R·N: the committed γ gradient at the global batch. The BN γ node is the one parameter gradient sync-BN changes, because it is the one that reads x̂.

          theorem Proofs.den_bnStatsMeanB_allReduce {N oc h w : ℕ} (R : ℕ) (hR : 0 < R) (hm : N * (h * w) ≠ 0) (t t' : String) (ds ds' : List ℕ) (x : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) (X : Vec (R * N * (oc * (h * w)))) (hx : ∀ (r : Fin R), StableHLO.den (x r) = batchShard R N (oc * (h * w)) X r) :
          StableHLO.den (syncStats R hR t t' ds ds' x).bnStatsMeanB = fun (c : Fin oc) => bnMean (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c)

          The handed-back running MEAN under sync-BN is the global batch's own — bnStatsMeanB on the packed statistics denotes what bnBatchMeanB at N := R·N denotes, so the host EMAs the global statistic on every replica.

          theorem Proofs.den_bnStatsVarB_allReduce {N oc h w : ℕ} (R : ℕ) (hR : 0 < R) (hm : N * (h * w) ≠ 0) (t t' : String) (ds ds' : List ℕ) (x : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) (X : Vec (R * N * (oc * (h * w)))) (hx : ∀ (r : Fin R), StableHLO.den (x r) = batchShard R N (oc * (h * w)) X r) :
          StableHLO.den (syncStats R hR t t' ds ds' x).bnStatsVarB = fun (c : Fin oc) => bnVar (R * N * (h * w)) (Mat.unflatten (bnchwFwd (R * N) oc h w X) c)

          …and so is the handed-back VARIANCE — the global batch's bnVar, what bnBatchVarB at N := R·N denotes. Note: No per-replica variance is ever averaged on its own: the between-shard spread (μ_r − μ)² rides along, which is what Chan's formula is.

          Closes a P4 collective once den has been unfolded on both sides: splits the global batch sum Σ_{m : R·N} into Σ_r Σ_n and reads each replica's shard back as a slice of the global tensor. rw, not simp, for the slices: in the conv kinds the x slice sits inside a VJP whose TYPE depends on it, and simp has no congruence through a dependent argument.

          Equations
          Instances For
            theorem Proofs.den_allReduceMeanF_convWeightGradB_shard {N ic oc h w kH kW : ℕ} (R : ℕ) (hR : 0 < R) (t xN cotN : String) (ds : List ℕ) (b : Vec oc) (W : Kernel4 oc ic kH kW) (X : Vec (R * N * (ic * h * w))) (DY : Vec (R * N * (oc * h * w))) (dy : Fin R → StableHLO.SHlo (N * (oc * h * w))) (hdy : ∀ (r : Fin R), StableHLO.den (dy r) = batchShard R N (oc * h * w) DY r) (idx : Fin (oc * ic * kH * kW)) :
            StableHLO.den (StableHLO.SHlo.allReduceMeanF R hR t ds fun (r : Fin R) => StableHLO.SHlo.convWeightGradB xN b (batchShard R N (ic * h * w) X r) W (dy r)) idx = 1 / ↑R * StableHLO.den (StableHLO.SHlo.convWeightGradB xN b X W (StableHLO.SHlo.operand cotN DY)) idx

            P4 for the Σ_n-shaped gradients, at the conv weight. The collective over the replicas' convWeightGradB, each on its shard at the shard-r block of the global cotangent, is 1/R of the batch-R·N node at that cotangent. den_allReduceMeanF_convWeightGradB (DataParallel.Node) is the same collective with NO relation between the replicas' inputs; this is what it becomes once P1–P3 relate them. Every other Σ_n gradient (denseWeightGradB, denseBiasGradB, the strided / depthwise / bias kinds) closes by the same shard_sum.

            theorem Proofs.den_allReduceMeanF_bnBetaGradB_shard {N oc h w : ℕ} (R : ℕ) (hR : 0 < R) (t cotN : String) (ds : List ℕ) (DY : Vec (R * N * (oc * (h * w)))) (dy : Fin R → StableHLO.SHlo (N * (oc * (h * w)))) (hdy : ∀ (r : Fin R), StableHLO.den (dy r) = batchShard R N (oc * (h * w)) DY r) (c : Fin oc) :

            P4 at the BN β gradient: Σ dy over each shard's channel row, averaged, is 1/R of the global row's Σ dy. β reads no statistic, so this is the row split alone.

            @[reducible, inline]
            abbrev Proofs.IsHomog {a b : ℕ} (f : Vec a → Vec b) :

            f scales with its argument: f (s • v) = s • f v, spelled pointwise. The statement of every cotangent-chain _smul lemma; an abbrev, so rw [h] and h s v see the equation.

            Equations
            Instances For
              theorem Proofs.IsHomog.comp {a b c : ℕ} {g : Vec b → Vec c} {f : Vec a → Vec b} (hg : IsHomog g) (hf : IsHomog f) :
              IsHomog (g ∘ f)
              theorem Proofs.HasVJP.backward_smul {m n : ℕ} {f : Vec m → Vec n} (hf : HasVJP f) (x : Vec m) :

              A VJP backward is linear in its cotangent — read off HasVJP.correct. This is the one step that reconciles a DP render's divConstB N with the batch-R·N step's divConstB (R·N): the per-replica cotangent is R · the shard of the global one, so every per-replica gradient is R · its shard contribution, and the collective's 1/R cancels it.