Theorem 6.17 — the matrix Bernstein bound (for )
DisprovedHighDimStat.RandomMatrices.matrix_bernstein_bound_v2Theorem 6.17 (Bernstein bound for random matrices). Let be a sequence of independent, zero-mean, symmetric random matrices that satisfy the Bernstein condition (Definition 6.10) with parameter . Then for all , the operator norm satisfies the tail bound
where .
This is the chapter's central matrix concentration tool, generalizing the scalar Bernstein bound (Chapter 2) to the operator norm of a sum of random matrices; it is the basis of Theorem 6.23's proof.
Formalization Note. The retired version (matrix_bernstein_bound) stated the bound for
all , as printed. At the left side is while
the right side is , which is whenever the total
variance vanishes (all a.s., e.g. in dimension ), so the printed inequality reads
there (accepted disproof). This is a degenerate failure of the printed source; the
corrected statement restricts to , which loses nothing (for and nonzero
total variance the bound is the trivial , and for zero total variance
the left side is for every ). The factor is kept exactly
(not replaced by the ambient dimension ); independence is Mathlib's iIndepFun with the
local MeasurableSpace instance on matrices; zero mean, symmetry and the moment condition are
packaged in BernsteinConditionMatrix.
import Mathlib import Definitions.Def_HighDimStat_RandomMatrices_BernsteinConditionMatrix import Definitions.Def_HighDimStat_RandomMatrices_matrixVariance import Definitions.Def_HighDimStat_RandomMatrices_opNorm open MeasureTheory ProbabilityTheory
namespace HighDimStat.RandomMatrices
noncomputable instance instMeasurableSpaceMatrixV2 {d : ℕ} :
MeasurableSpace (Matrix (Fin d) (Fin d) ℝ) := by
unfold Matrix; infer_instance
/-- **Theorem 6.17** (Bernstein bound for random matrices), Wainwright, *High-Dimensional
Statistics* (2019), p. 176, Eq. (6.42). Let `{Qᵢ}` be independent, zero-mean, symmetric random
matrices satisfying the Bernstein condition with parameter `b > 0`. Then for all `δ > 0`, the
operator norm satisfies
`P[(1/n)|||∑Qᵢ|||₂ ≥ δ] ≤ 2 rank(∑var(Qᵢ)) exp(-nδ²/(2(σ²+bδ)))`, where
`σ² := (1/n)|||∑var(Qᵢ)|||₂`.
Correction to the printed source: the bound is stated here for `δ > 0` rather than the printed
`δ ≥ 0`. At `δ = 0` the left side is `P[‖·‖ ≥ 0] = 1`, while the right side is
`2·rank(∑var(Qᵢ))`, which vanishes whenever the total variance is zero (all `Qᵢ = 0` a.s., in
particular in dimension `d = 0`); the printed inequality `1 ≤ 0` is false there, and the
`δ = 0` case carries no content otherwise (the bound reads `1 ≤ 2·rank ≥ 2`). For `δ > 0` the
statement is exactly the printed one. -/
theorem matrix_bernstein_bound_v2 {n d : ℕ} {Ω : Type*} [MeasurableSpace Ω] {Prob : Measure Ω}
[IsProbabilityMeasure Prob] (Q : Fin n → Ω → Matrix (Fin d) (Fin d) ℝ) (b : ℝ) (hb : 0 < b)
(hIndep : iIndepFun Q Prob)
(hBernstein : ∀ i, BernsteinConditionMatrix (Q i) Prob b)
(δ : ℝ) (hδ : 0 < δ) :
Prob.real {ω | δ ≤ opNorm (∑ i, Q i ω) / (n : ℝ)} ≤
2 * (Matrix.rank (∑ i, matrixVariance (Q i) Prob) : ℝ) *
Real.exp (-((n : ℝ) * δ ^ 2) /
(2 * ((1 / (n : ℝ)) * opNorm (∑ i, matrixVariance (Q i) Prob) + b * δ))) := by sorry
end HighDimStat.RandomMatrices