Lemma D.1 — Hoeffding's lemma
ProvedMohriFoML.OnlineToBatch.hoeffding_lemmaconcentration-inequalitiesprobability
Let be a real random variable on a probability space with and , where . Then for every ,
Hoeffding's lemma bounds the moment generating function of a bounded centred variable by that of a Gaussian with variance . Combined with the Chernoff bounding technique (D.1) it yields Hoeffding's inequality (Theorem D.2), which Section 8.4 applies to a fixed near-optimal hypothesis in the proof of (8.28).
Formalization Note is a measurable function on the probability space and the bounds hold at every point; and are then integrable, so both expectations are genuine.
Differences from the source: none.
Preamble
import Mathlib
Formal statement
namespace MohriFoML.OnlineToBatch
open MeasureTheory
/-- **Lemma D.1: Hoeffding's lemma.**
Mohri, Rostamizadeh & Talwalkar, Foundations of Machine Learning, 2nd ed., MIT Press 2018,
Appendix D, §D.1, p. 437 (PDF p. 454), Lemma D.1, inequality (D.2).
Let `X` be a random variable with `E[X] = 0` and `a ≤ X ≤ b` with `b > a`. Then for any `t > 0`,
`E[e^{tX}] ≤ e^{t²(b−a)²/8}`.
**Formalization Note.** `X` is a measurable real function on a probability space `(Ω, μ)`, and
`a ≤ X ≤ b` holds at every point; together these make `X` and `e^{tX}` integrable, so both
expectations (written as Bochner integrals) are the genuine ones. -/
theorem hoeffding_lemma {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]
(X : Ω → ℝ) (a b : ℝ) (hX : Measurable X)
(hmean : ∫ ω, X ω ∂μ = 0) (hab : a < b) (hXab : ∀ ω, a ≤ X ω ∧ X ω ≤ b) :
∀ t : ℝ, 0 < t →
∫ ω, Real.exp (t * X ω) ∂μ ≤ Real.exp (t ^ 2 * (b - a) ^ 2 / 8) := by sorry
end MohriFoML.OnlineToBatch
Source
Mohri, Rostamizadeh & Talwalkar, Foundations of Machine Learning, 2nd ed., MIT Press 2018, p. 437 (PDF p. 454), Appendix D §D.1, Lemma D.1 (Hoeffding's lemma), (D.2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.