Lemma 8.14 — average generalization error of on-line hypotheses, (8.26)
ProvedMohriFoML.OnlineToBatch.avg_genError_le_avg_lossLet be a set of hypotheses mapping to a prediction set , and let be a loss bounded by . Let be a probability distribution on and , , a sample drawn i.i.d. according to . Let be the hypotheses generated by an on-line algorithm sequentially processing , and write . Then for every , with probability at least over ,
The on-line losses are computed on points that 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 on and is indexed from . "With probability at least " is stated as: the (outer) probability of the set of samples on which the inequality fails is at most . The loss is a function on a type whose values outside 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
import Mathlib import Definitions.Def_MohriFoML_OnlineToBatch_genError import Definitions.Def_MohriFoML_OnlineToBatch_OnlineAlgorithm import Definitions.Def_MohriFoML_OnlineToBatch_hypSeq
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