Theorem 9 — McDiarmid's inequality
ProvedRadGauss.RiskBound.mcdiarmid_inequalityLet be independent random variables taking values in a measurable space , where has law (the laws need not be equal). Let be a measurable function with bounded differences: there are constants such that for every ,
Then for every ,
This concentration inequality is applied twice in the proof of Theorem 8: to the uniform deviation over the centred cost class, and to the empirical mean of the cost of the fixed action .
Formalization Note Independence is the product measure of probability measures on (Measure.pi μ), and the random vector is the identity. The function is assumed measurable, which the paper leaves implicit; bounded differences make it bounded, so is a genuine expectation. If every the printed exponent has a zero denominator; Lean reads as , so the bound becomes , which is true (and is then constant). This is the general, not-necessarily-identically-distributed form as printed; the platform's StabGen.Uniform.mcdiarmid_inequality is its i.i.d. special case and UnderstandingML.mcdiarmid_inequality_pi is a two-sided, uniform- variant.
import Mathlib open MeasureTheory
namespace RadGauss.RiskBound
/-- **Theorem 9 (McDiarmid's inequality)** (p. 467). Let `X_1, …, X_n` be independent random
variables with values in `A` (the coordinates under the product `μ_1 ⊗ ⋯ ⊗ μ_n` of probability
measures, not necessarily equal), and let `f : A^n → ℝ` be measurable with
`|f(x) − f(x_1, …, x_{i−1}, x'_i, x_{i+1}, …, x_n)| ≤ c_i` for every `i`, `x` and `x'_i`. Then for every
`t > 0`, `P{f(X) − E f(X) ≥ t} ≤ exp(−2t² / Σ_i c_i²)`. -/
theorem mcdiarmid_inequality {A : Type*} [MeasurableSpace A] (n : ℕ)
(μ : Fin n → Measure A) [∀ i, IsProbabilityMeasure (μ i)]
(f : (Fin n → A) → ℝ) (hf : Measurable f) (c : Fin n → ℝ)
(hc : ∀ (i : Fin n) (x : Fin n → A) (a : A), |f x - f (Function.update x i a)| ≤ c i)
(t : ℝ) (ht : 0 < t) :
Measure.pi μ {x | t ≤ f x - ∫ y, f y ∂(Measure.pi μ)} ≤
ENNReal.ofReal (Real.exp (-2 * t ^ 2 / ∑ i, c i ^ 2)) := by sorry
end RadGauss.RiskBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.