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/VarB —
planning/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 #
- P3 — sharding commutes with every per-example lift.
batchShard_batchMap,batchShard_batchMapAux,batchShard_map/batchShard_zipWith,batchSlice_batchShard. Every non-BN op in a BN net's chain isbatchMap N(orbatchMapAux N, or pointwise) of a per-example map, so replicar's value at every such node isbatchShard rof the global batch-R·Nvalue whenever its input is. Definitional, all of them. - ⭐⭐ The statistics subgraph (
syncStats: μ all-reduced, then Chan'sσ²_r + (μ_r − μ)²all-reduced, packed) denotes the global[μ ‖ σ²]—den_syncStats_left/_right, the latter bybnVar_row_shard_chan. - ⭐⭐ P1 / P2 / P2γ at the GRAPH, for any
R—den_bnSyncF_allReduce,den_bnSyncBack_allReduce,den_allReduceMeanF_bnSyncGammaGradB. The sync-BN subgraphs a DP render emits, fed by that statistics subgraph, denotebatchShard rofbnBatchTensor4/bnBatchTensor4_grad_inputatN := R·N(forward and input-VJP) and1/RofbnPerChannel_grad_gammaatN := R·N(the γ parameter gradient). These are the BN cases of the chain induction;StableHLO.lean's*_allReduce_R1anchors are theirR := 1instances. - The handed-back statistics are the global batch's own:
den_bnStatsMeanB_allReduce/den_bnStatsVarB_allReduce— what a sync render returns for the host's running-stat EMA isbnBatchMeanB/bnBatchVarBatN := R·N, on every replica. - ⭐⭐ P4 — the parameter collective is the global-batch gradient.
den_allReduceMeanF_convWeightGradB_shard,den_allReduceMeanF_bnBetaGradB_shardand the γ statement above: the all-reduced mean of theRper-replica gradient nodes, each on its shard and at the shard-rblock of the global cotangent, is(1/R)·the batch-R·Ngradient node at the SAME per-example cotangents. Every other*GradBcomposes identically (simp only [den], the shard hypothesis,sum_finProdFinEquiv). The ℝ-level twin isDataParallel.dpSyncGrad_eq_globalBatchGrad, the positive counterpart ofdpMeanGrad_ne_globalBatchGrad.
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.
Example n of shard r is example (r, n) of the global batch.
⭐ 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.
…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.
A pointwise binary map commutes with sharding (addVB, subB, the relu mask selectPosB
against its saved activation, …).
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
⭐⭐ The first collective IS the global mean — bnMean_shard on the channel rows.
⭐⭐ 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.
⭐⭐ 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.
⭐⭐ 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.
⭐⭐ 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 x̂.
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.
…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.
⭐⭐ 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.
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.
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.