Lemma 7.7 (Azuma cgf) — log E[e^{2εθX} | X] ≼ 2θ²A² when X² ≼ A²
ProvedMatrixTail.Azuma.lemma7_7Let be a fixed self-adjoint complex matrix, let be a Rademacher random variable and let . For every self-adjoint matrix with ,
In the paper the lemma is stated for a random self-adjoint matrix with and a Rademacher independent of : . Because is independent of , the conditional expectation given is the function evaluated at , so the statement above, for every admissible value , is the paper's lemma. It is the conditional bound on the matrix cumulant generating function of a symmetrized difference used at each step of the proof of the matrix Azuma inequality.
Formalization Note Exponential and logarithm are defined by the continuous functional calculus; is positive definite, so its logarithm is the paper's. The expectation is entrywise and is the semidefinite order.
import Mathlib import Definitions.Def_MatrixTail_Azuma_Model open MeasureTheory ProbabilityTheory open scoped MatrixOrder ComplexOrder ENNReal
namespace MatrixTail.Azuma
/-- **Lemma 7.7 (Azuma cgf).** Tropp, *User-Friendly Tail Bounds for Sums of Random Matrices*,
arXiv:1004.4389v7, p. 29: "Suppose that `X` is a random s.a. matrix and `A` is a fixed s.a. matrix that satisfy
`X² ≼ A²`. Let `ε` be a Rademacher random variable independent from `X`. Then
`log E[e^{2εθX} | X] ≼ 2θ²A²` for `θ ∈ ℝ`."
**Formalization Note.**
* Complex Hermitian `d × d` matrices; `exp`, `log` are `cfc Real.exp`, `cfc Real.log` (`mexp`, `mlog`); `E` is
the entrywise expectation (`mean`); `≼` is the Loewner order under `MatrixOrder`.
* **The conditioning is resolved by independence.** Since `ε` is independent of `X`, the conditional
expectation `E[e^{2εθX} | X]` is the function `x ↦ E e^{2εθx}` evaluated at `X`. The statement is therefore
posed for every fixed Hermitian `x` with `x² ≼ A²` (the values `X` takes almost surely): for each such `x`,
`log E e^{2εθx} ≼ 2θ²A²`. Applied at `x = X(ω)` this is the paper's almost-sure inequality. The content
(`E e^{2εθx} = cosh(2θx) ≼ e^{2θ²x²}` and the operator monotonicity of `log` together with `x² ≼ A²`) is
intact. `E e^{2εθx}` is positive definite, where `log` is the paper's (2.7).
* No integrability hypothesis: `ε = ±1` almost surely, so `e^{2εθx}` is bounded. `P` is a probability
measure. -/
theorem lemma7_7 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
{d : ℕ} (x A : Matrix (Fin d) (Fin d) ℂ) (hx : x.IsHermitian) (hA : A.IsHermitian)
(hxA : x ^ 2 ≤ A ^ 2) (ε : Ω → ℝ) (hε : IsRademacher P ε) (θ : ℝ) :
mlog (mean P (fun ω => mexp ((2 * ε ω * θ) • x))) ≤ (2 * θ ^ 2) • A ^ 2 := by sorry
end MatrixTail.Azuma
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.