Two-sided Hoeffding inequality
Provedhoeffding_two_sidedRole. Reusable two-sided concentration building block toward the bounded-differences / McDiarmid / empirical-process supremum concentration inequalities used in exact matrix completion.
Claim (two-sided Hoeffding inequality). Let be independent real random variables (iIndepFun) on a probability space, each sub-Gaussian with parameter (HasSubgaussianMGF (X i) (c i)). Then their sum satisfies the two-sided deviation bound
Proof. Mathlib's ProbabilityTheory.HasSubgaussianMGF.measure_sum_ge_le_of_iIndepFun gives the one-sided bound . Apply it to (right tail) and to (left tail): the negated family is independent (iIndepFun.comp with the measurable map ) and each is sub-Gaussian with the same parameter (HasSubgaussianMGF.neg), and . Combine via , measureReal_mono, and the union bound measureReal_union_le.
Source. Standard symmetric two-sided form of Hoeffding's inequality for independent sub-Gaussian summands: W. Hoeffding, "Probability inequalities for sums of bounded random variables", JASA 58 (1963) 13-30; S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities, OUP 2013, §2.4 and Theorem 2.8 (sub-Gaussian / two-sided form). Derived here from Mathlib's one-sided measure_sum_ge_le_of_iIndepFun by union-bound symmetrization.
import Mathlib.Probability.Moments.SubGaussian import Mathlib.MeasureTheory.Measure.Real open MeasureTheory ProbabilityTheory Real open scoped NNReal ENNReal
theorem hoeffding_two_sided
{Ω : Type*} {mΩ : MeasurableSpace Ω} {μ : Measure Ω} [IsProbabilityMeasure μ]
{ι : Type*} {X : ι → Ω → ℝ} (h_indep : iIndepFun X μ)
{c : ι → ℝ≥0} {s : Finset ι}
(h_subG : ∀ i ∈ s, HasSubgaussianMGF (X i) (c i) μ) {ε : ℝ} (hε : 0 ≤ ε) :
μ.real {ω | ε ≤ |∑ i ∈ s, X i ω|}
≤ 2 * Real.exp (-ε ^ 2 / (2 * ∑ i ∈ s, c i)) := by sorry