Provedunbiased-attentionrandomized-algorithmssoftmaxeasy-side
Product of estimates: (âb̂ − ab)² ≤ 2F²((â − a)² + (b̂ − b)²) when |a|, |b̂| ≤ F
For all , if and , then
What the notation means · or point at any symbol
- RReal numbers
- The real numbers: every point on the number line. (
ℝ) - x ∈ TVariables
- a, b, ahat, bhat, F range over real numbers: the statement must hold for every choice. (
(a b ahat bhat F : ℝ)) - |x|Absolute value
- The size of a without its sign. (
|a|) - ≤At most
- |a| is less than or equal to F. (
|a| ≤ F) - aᵇPower
- ahat · bhat − a · b raised to the power 2. (
(ahat * bhat - a * b) ^ 2) - ·Multiplication
- ahat times bhat. (
ahat * bhat) - -Subtraction
- ahat · bhat minus a · b. On ℕ, Lean's subtraction stops at 0: 2 − 5 = 0. (
ahat * bhat - a * b) - +Addition
- (ahat − a)^2 plus (bhat − b)^2. (
(ahat - a) ^ 2 + (bhat - b) ^ 2)
theorem ua-product-estimate-error (a b ahat bhat F : ℝ) (ha : |a| ≤ F) (hb : |bhat| ≤ F) :
(ahat * bhat - a * b) ^ 2 ≤ 2 * F ^ 2 * ((ahat - a) ^ 2 + (bhat - b) ^ 2)Combined with the SNIS MSE bound for each factor, the covariance (gradient) estimate inherits constant MSE with constant-factor overhead: the easy side of the threshold transfers from attention outputs to query gradients. Part of 'Unbiased randomized attention: cost x variance thresholds', round 6 (gradients).
How it was proved
- Proved
- 4 October 2026
- By
- Ajax, with the agent “Baguette math & proofs (Claude Code, 2026-10-03)”
- Checked by
- Lean's kernel (Lean 4.33.1, with Mathlib); the proof is signed and replays offline
- Axioms
- Classical.choice, Quot.sound, propext
- Proof
- 20 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.