Documentation

LeanMlir.Proofs.Foundation.DataParallelSync

Data parallelism, piece 3: synchronised BatchNorm — the DP step IS the global-batch step #

DataParallel.lean (piece 1) proved that a data-parallel step on a batch-BN net is a step on the mean of R per-replica losses and provably NOT the batch-R·N step (dpMeanGrad_ne_globalBatchGrad); DataParallelNode.lean (piece 2) put the collective in the AST. This is the third piece: with the sync-BN kit (StableHLO.bnBatchVarAtB, bnPackB, bnSyncF, bnSyncDyStatsB, bnSyncBack, bnSyncGammaGradB, bnStatsMeanB/VarBplanning/global_bn_verified.md §2b) 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 (§3.2 onward of the plan): 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 piece 2. ⚠ The lowerer's all_reduce is trusted as every other op's lowering is.

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 aVec 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 sVec aVec 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 RStableHLO.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 RStableHLO.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 meanbnMean_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 RStableHLO.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 the one-round E[x²] exchange could not have, and the reason it was replaced.

    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) (hM : R * N * (h * w) 0) (gN bN es t t' : String) (ds ds' : List ) (ε : ) (γ β : Vec oc) (x : Fin RStableHLO.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) (hM : R * N * (h * w) 0) (gN xN es t t' t'' : String) (ds ds' ds'' : List ) (ε : ) (γ : Vec oc) (x : Fin RStableHLO.SHlo (N * (oc * (h * w)))) (xv : Fin RVec (N * (oc * (h * w)))) (dy : Fin RStableHLO.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)) (bnBatchTensor4_grad_input (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 bnBatchTensor4_grad_input — 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) (hM : R * N * (h * w) 0) (xN es t t' t'' : String) (ds ds' ds'' : List ) (ε : ) (x : Fin RStableHLO.SHlo (N * (oc * (h * w)))) (xv : Fin RVec (N * (oc * (h * w)))) (dy : Fin RStableHLO.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 * bnPerChannel_grad_gamma 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 bnPerChannel_grad_gamma 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 .

    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 RStableHLO.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 ownbnStatsMeanB 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 RStableHLO.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. ⛔ No per-replica variance is ever averaged on its own: the between-shard spread (μ_r − μ)² rides along, which is what Chan's formula is.

    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 RStableHLO.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 (piece 2) 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) composes by the same three lines.

    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 RStableHLO.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.

    theorem Proofs.HasVJP.backward_smul {m n : } {f : Vec mVec n} (hf : HasVJP f) (x : Vec m) (a : ) (dy : Vec n) :
    (hf.backward x fun (j : Fin n) => a * dy j) = fun (i : Fin m) => a * hf.backward x dy i

    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.