Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 8.14 — average generalization error of on-line hypotheses, (8.26)

Proved
MohriFoML.OnlineToBatch.avg_genError_le_avg_loss

by mikedeng1 · Oct 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

generalization-boundsmachine-learningonline-learning

Let HHH be a set of hypotheses mapping XXX to a prediction set Y′Y'Y′, and let L:Y′×Y→R+L : Y' \times Y \to \mathbb{R}_+L:Y′×Y→R+​ be a loss bounded by M≥0M \ge 0M≥0. Let DDD be a probability distribution on X×YX \times YX×Y and S=((x1,y1),…,(xT,yT))S = ((x_1, y_1), \dots, (x_T, y_T))S=((x1​,y1​),…,(xT​,yT​)), T≥1T \ge 1T≥1, a sample drawn i.i.d. according to DDD. Let h1,…,hT∈Hh_1, \dots, h_T \in Hh1​,…,hT​∈H be the hypotheses generated by an on-line algorithm AAA sequentially processing SSS, and write R(h)=E(x,y)∼D[L(h(x),y)]R(h) = \mathbb{E}_{(x,y)\sim D}[L(h(x), y)]R(h)=E(x,y)∼D​[L(h(x),y)]. Then for every δ>0\delta > 0δ>0, with probability at least 1−δ1 - \delta1−δ over SSS,

1T∑t=1TR(ht)≤1T∑t=1TL(ht(xt),yt)+M2log⁡1δT.\frac{1}{T} \sum_{t=1}^T R(h_t) \le \frac{1}{T} \sum_{t=1}^T L(h_t(x_t), y_t) + M \sqrt{\frac{2 \log \frac{1}{\delta}}{T}} .T1​t=1∑T​R(ht​)≤T1​t=1∑T​L(ht​(xt​),yt​)+MT2logδ1​​​.

The on-line losses L(ht(xt),yt)L(h_t(x_t), y_t)L(ht​(xt​),yt​) are computed on points that hth_tht​ has not seen, so their average is an honest estimate of the average generalization error. This lemma is the first inequality (8.27) of Theorem 8.15 before convexity is used.

Formalization Note The sample has law D⊗TD^{\otimes T}D⊗T on (X×Y)T(X \times Y)^T(X×Y)T and is indexed from 000. "With probability at least 1−δ1 - \delta1−δ" is stated as: the (outer) probability of the set of samples on which the inequality fails is at most δ\deltaδ. The loss is a function on a type E⊇Y′E \supseteq Y'E⊇Y′ whose values outside Y′Y'Y′ never enter.

Differences from the source:

  • encoding: L : Y' × Y → R_+ bounded by M → L : E × Y → ℝ with 0 ≤ L(a, y) ≤ M for a ∈ Y', hypotheses valued in Y' ⊆ E; reason: only the values on Y' enter; same instances
  • encoding: h_t generated by A sequentially processing S → h_{t+1} = A(t, first t pairs of S), A deterministic with values in H; reason: this is the book's description of an on-line algorithm (§8.4)
  • encoding: R(h_t) a random variable → (prefix, (x, y)) ↦ L(A(t, prefix)(x), y) jointly measurable for every t; reason: R(h_t) and the event are defined only then; no meaningful instance is excluded
  • encoding: with probability at least 1 − δ → outer probability of the failure set at most δ; reason: equal to the book's statement whenever the event is measurable, and at least as strong otherwise
  • encoding: sample of size T → T > 0, indices 0-based; reason: 1/T and the sample require T ≥ 1
  • reading: "after processing pair (x_t, y_t), t ∈ [m]" → t ∈ [T]; reason: typo in the setting, the sample has T pairs
  • encoding: δ > 1: √(2 log(1/δ)/T) of a negative number (undefined) → Real.sqrt of a negative number = 0; reason: the claimed failure probability bound δ is then > 1, so the statement holds trivially in both readings; no meaningful instance changes
Preamble
import Mathlib
import Definitions.Def_MohriFoML_OnlineToBatch_genError
import Definitions.Def_MohriFoML_OnlineToBatch_OnlineAlgorithm
import Definitions.Def_MohriFoML_OnlineToBatch_hypSeq
Formal statement
namespace MohriFoML.OnlineToBatch

open MeasureTheory

/-- **Lemma 8.14: average generalization error of the hypotheses of an on-line algorithm.**
Mohri, Rostamizadeh & Talwalkar, Foundations of Machine Learning, 2nd ed., MIT Press 2018,
§8.4, p. 202 (PDF p. 219), Lemma 8.14, inequality (8.26); standing setting of §8.4 on the same
page.

Let `H` be a set of hypotheses `X → Y'`, `L : Y' × Y → ℝ₊` a loss bounded by `M ≥ 0`, `D` a
distribution on `X × Y`, and `S = ((x_1,y_1), …, (x_T,y_T))` drawn i.i.d. from `D`. Let
`h_1, …, h_T ∈ H` be the hypotheses generated by an on-line algorithm `A` sequentially
processing `S`. Then for any `δ > 0`, with probability at least `1 − δ`,
`(1/T) ∑_t R(h_t) ≤ (1/T) ∑_t L(h_t(x_t), y_t) + M √(2 log(1/δ) / T)`.

**Formalization Note.** The sample `S : Fin T → X × Y` has law `D^T = Measure.pi (fun _ => D)`;
indices are 0-based (`hypSeq A S t` is the book's `h_{t+1}`). "With probability at least `1 − δ`"
is stated as: the (outer) probability of the failure set is at most `δ`. The loss is a function
`L : E → Y → ℝ` on a type `E` containing the prediction set `Y'`; only its values on `Y'` enter.
Measurability of `(s, (x, y)) ↦ L (A t s x) y`, jointly in the length-`t` prefix `s` and the new
pair, makes `R(h_t)` a random variable; without it `R` is undefined. `T > 0`. -/
theorem avg_genError_le_avg_loss {X Y E : Type*} [MeasurableSpace X] [MeasurableSpace Y]
    (D : Measure (X × Y)) [IsProbabilityMeasure D]
    (Y' : Set E) (L : E → Y → ℝ) (M : ℝ) (hM : 0 ≤ M)
    (hL : ∀ a ∈ Y', ∀ y, 0 ≤ L a y ∧ L a y ≤ M)
    (H : Set (X → E)) (hH : ∀ h ∈ H, ∀ x, h x ∈ Y')
    (A : OnlineAlgorithm X Y E) (hA : ∀ t s, A t s ∈ H)
    (hA_meas : ∀ t : ℕ,
      Measurable (fun p : (Fin t → X × Y) × (X × Y) => L (A t p.1 p.2.1) p.2.2))
    (T : ℕ) (hT : 0 < T) (δ : ℝ) (hδ : 0 < δ) :
    (Measure.pi fun _ : Fin T => D)
        {S | ¬ ((1 / (T : ℝ)) * ∑ t : Fin T, genError D L (hypSeq A S t) ≤
            (1 / (T : ℝ)) * ∑ t : Fin T, L (hypSeq A S t (S t).1) (S t).2 +
              M * Real.sqrt (2 * Real.log (1 / δ) / T))}
      ≤ ENNReal.ofReal δ := by sorry

end MohriFoML.OnlineToBatch
Source
Mohri, Rostamizadeh & Talwalkar, Foundations of Machine Learning, 2nd ed., MIT Press 2018, p. 202 (PDF p. 219), §8.4, Lemma 8.14, (8.26); standing setting of §8.4 on the same page

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me