Provedunbiased-attentionrandomized-algorithmssoftmaxlower-bound

Sampling lower bound constant: hit probability ≤ 1/2 and output gap ≥ 1/2 give worst-case MSE ≥ 1/32

For all $\htmlData{mx=1}{\eta, \Delta \in \htmlData{mx=0}{\mathbb{R}}}$ , if $\htmlData{mx=0}{\eta} \mathrel{\htmlData{mx=2}{\leq}} \htmlData{mx=1}{\frac{1}{2}}$ and $\htmlData{mx=0}{\frac{1}{2}} \mathrel{\htmlData{mx=3}{\leq}} \htmlData{mx=2}{\left\lvert \htmlData{mx=1}{\Delta} \right\rvert}$ , then

\htmlData{mx=0}{\frac{1}{32}} \mathrel{\htmlData{mx=7}{\leq}} \htmlData{mx=6}{\frac{\htmlData{mx=5}{(\htmlData{mx=2}{1 - \htmlData{mx=1}{\eta}}) \cdot \htmlData{mx=4}{\htmlData{mx=3}{\Delta}^{2}}}}{4}}

What the notation means · or point at any symbol

RReal numbers: The real numbers: every point on the number line. (ℝ)
x ∈ TVariables: η, Δ range over real numbers: the statement must hold for every choice. ((η Δ : ℝ))
≤At most: η is less than or equal to 1/2. (η ≤ 1 / 2)
a/bDivision: 1 divided by 2. In Lean, dividing by 0 gives 0. (1 / 2)
|x|Absolute value: The size of Δ without its sign. (|Δ|)
·Multiplication: 1 − η times Δ^2. ((1 - η) * Δ ^ 2)
-Subtraction: 1 minus η. On ℕ, Lean's subtraction stops at 0: 2 − 5 = 0. (1 - η)
aᵇPower: Δ raised to the power 2. (Δ ^ 2)

theorem ua-sampling-lower-bound-constant (η Δ : ℝ) (hη : η ≤ 1 / 2) (hΔ : 1 / 2 ≤ |Δ|) :
    1 / 32 ≤ (1 - η) * Δ ^ 2 / 4

Final arithmetic of the two-point bound for samplers with s ≤ n/(2m) draws. Part of 'Unbiased randomized attention: cost x variance thresholds', round 9 (true derivative, whole-instance reduction, compositions).

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: 13 lines of Lean

Sampling lower bound constant: hit probability ≤ 1/2 and output gap ≥ 1/2 give worst-case MSE ≥ 1/32

How it was proved

More proved statements