Proof of Theorem 3, pp. 21–22 — E|N¹ − N⁰| = Σₖ C(n,k)qᵏ(1−q)ⁿ⁻ᵏ E|2Bin(k,½) − k| ≤ √(nq)
ProvedFastCLO.LowerBound.binomial_boundbinomiallower-boundsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and . Suppose each of independent draws lands in a given cell with probability , and each draw in the cell is labelled or with probability each. With the numbers of draws in the cell with label and ,
Explicitly, the statement is
The page takes (Theorem 3); the proof of Theorem 7 uses the same bound with . Combined with the Jensen step it bounds the Bayes risk of every coordinate from below by .
Formalization Note The expectation is written as the page's explicit mixture over (the number of draws in the cell) and (the number of those labelled ).
Preamble
import Mathlib
Formal statement
namespace FastCLO.LowerBound
/-- The binomial bound (Hu, Kallus, Mao, arXiv:2011.03030v3, proof of Theorem 3, pp. 21–22): if each
of `n` draws lands in a cell with probability `q`, and each draw in the cell is labelled `1` or `0`
with probability `1/2`, then the expected absolute difference of the label counts satisfies
`E|N¹ − N⁰| = Σ_k C(n,k) q^k (1−q)^{n−k} E|2 Bin(k, 1/2) − k| ≤ √(nq)`.
Formalization Note: the expectation is written as the page's explicit mixture, with `k` the number of
draws in the cell and `j` the number of those labelled `1`. The page has `q = 1/η` (Theorem 3); the
proof of Theorem 7 uses `q = ζ^α/(η − 1)` (p. 29). -/
theorem binomial_bound (n : ℕ) (q : ℝ) (hq0 : 0 ≤ q) (hq1 : q ≤ 1) :
∑ k ∈ Finset.range (n + 1), (n.choose k : ℝ) * q ^ k * (1 - q) ^ (n - k) *
(∑ j ∈ Finset.range (k + 1), (k.choose j : ℝ) / 2 ^ k * |2 * (j : ℝ) - k|) ≤
Real.sqrt (n * q) := by sorry
end FastCLO.LowerBound
Source
Hu, Kallus, Mao, Fast Rates for Contextual Linear Optimization, arXiv:2011.03030v3, proof of Theorem 3 (A.2), pp. 21–22, the display after "Thus, letting Bin(k, 1/2) …"; used with q = ζ^α/(η−1) in the proof of Theorem 7, p. 29
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.