Theorem A.14 (p = 1, lower bound) — Khintchine inequality
ProvedModernOnlineLearning.LowerBounds.theorem_A_14_p1khintchine-inequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1probabilityrademacher
Let , let be real numbers, and let be independent random signs, each equally likely to be or . The lower bound in Khintchine's inequality is
This is the sharp case used to estimate a Rademacher sum in the proof of Theorem 5.1.
Formalization Note The signs form the uniform distribution on Boolean vectors, so the expectation is a finite average. The printed theorem also gives an upper bound and sharp constants for all and complex coefficients; this item formalizes only the real-coefficient lower bound.
Preamble
import Mathlib
Formal statement
namespace ModernOnlineLearning.LowerBounds
/-- The lower-bound, real-coefficient `p = 1` case of Theorem A.14,
printed p. 296. Uniform `Bool` vectors are independent Rademacher signs. -/
theorem theorem_A_14_p1 {N : ℕ} (hN : 0 < N) (x : Fin N → ℝ) :
(1 / Real.sqrt 2) * Real.sqrt (∑ i : Fin N, (x i) ^ 2) ≤
((2 : ℝ) ^ N)⁻¹ *
∑ ω : Fin N → Bool,
|∑ i : Fin N, (if ω i then (1 : ℝ) else -1) * x i| := by sorry
end ModernOnlineLearning.LowerBounds
Source
Orabona, arXiv:1912.13213v10, Theorem A.14, p. 296 (p = 1 lower-bound case)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.