Provedalphamulti-device-learningpartitioning
Gradient partitioning delivers the replicated sums bit for bit
For all , , , , and :
What the notation means · or point at any symbol
- Type
- Type: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Type) - NNatural numbers
- The natural numbers 0, 1, 2, …. In Lean they start at 0. (
Nat) - x ∈ TVariables
- owners, r range over natural numbers: the statement must hold for every choice. (
(owners r : Nat)) - CombineTree
- CombineTree: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
CombineTree) - e.feval
- eval of t: Lean's dot notation e.eval means eval applied to e. (
t.eval) - =Equality
- eval(pointwise(op), o ↦ projectOwner(owners, r, v(o)), idx) and eval(pointwise(op), v, r + idx · owners) are the same. (
t.eval (pointwise op) (fun o => project…) - ⟹Implies
- If α, then α. (Between types, A → B is the type of functions from A to B.) (
α → α) - pointwise
- pointwise: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
pointwise) - f(x)Function application
- pointwise applied to op. Lean writes f x; papers write f(x). (
pointwise op) - x ↦ f(x)Function (λ-abstraction)
- The function sending o to projectOwner(owners, r, v(o)). Lean writes fun x => …; papers write x ↦ …. (
fun o => projectOwner owners r (v o)) - projectOwner
- projectOwner: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
projectOwner) - +Addition
- r plus idx · owners. (
r + idx * owners) - ·Multiplication
- idx times owners. (
idx * owners)
theorem alpha-gradient-partitioning-bit-exact {α : Type} (op : α → α → α) (owners r : Nat) (v : Nat → Nat → α) (t : CombineTree) (idx : Nat) :
t.eval (pointwise op) (fun o => projectOwner owners r (v o)) idx = t.eval (pointwise op) v (r + idx * owners)Reducing every owner's projection onto owner r's coordinates (dpoProject) over a combine tree gives, word for word, the full elementwise sum of those coordinates over the same tree and order, for any combining operation (binary64 addition included): each coordinate owner's delivered sums equal the replicated sums exactly. Model: definition alpha-multi-device-learning (revision 01a1255c-84f1-7e7f-a994-fc8c2d274bee).
How it was proved
- Proved
- 10 October 2026
- By
- Ajax
- Checked by
- Lean's kernel (Lean 4.33.1, with Mathlib); the proof is signed and replays offline
- Axioms
- propext
- Proof
- 31 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.