Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8.15 — on-line to batch conversion, (8.27) and (8.28)

Proved
MohriFoML.OnlineToBatch.online_to_batch_averaged_hypothesis

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

generalization-boundsmachine-learningonline-learningonline-to-batch

Let HHH be a set of hypotheses mapping XXX to a convex prediction set Y′Y'Y′ (a convex subset of a real vector space), 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 and convex in its first argument. 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, let 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)] be the generalization error, and let

RT=∑t=1TL(ht(xt),yt)−inf⁡h∈H∑t=1TL(h(xt),yt)R_T = \sum_{t=1}^T L(h_t(x_t), y_t) - \inf_{h \in H} \sum_{t=1}^T L(h(x_t), y_t)RT​=t=1∑T​L(ht​(xt​),yt​)−h∈Hinf​t=1∑T​L(h(xt​),yt​)

be the regret (8.25). Then for every δ>0\delta > 0δ>0, each of the following two inequalities holds with probability at least 1−δ1 - \delta1−δ over SSS:

R(1T∑t=1Tht)≤1T∑t=1TL(ht(xt),yt)+M2log⁡1δT(8.27)R\Big(\frac{1}{T}\sum_{t=1}^T h_t\Big) \le \frac{1}{T} \sum_{t=1}^T L(h_t(x_t), y_t) + M \sqrt{\frac{2 \log \frac{1}{\delta}}{T}} \tag{8.27}R(T1​t=1∑T​ht​)≤T1​t=1∑T​L(ht​(xt​),yt​)+MT2logδ1​​​(8.27) R(1T∑t=1Tht)≤inf⁡h∈HR(h)+RTT+2M2log⁡2δT.(8.28)R\Big(\frac{1}{T}\sum_{t=1}^T h_t\Big) \le \inf_{h \in H} R(h) + \frac{R_T}{T} + 2M \sqrt{\frac{2 \log \frac{2}{\delta}}{T}} . \tag{8.28}R(T1​t=1∑T​ht​)≤h∈Hinf​R(h)+TRT​​+2MT2logδ2​​​.(8.28)

This is the on-line to batch conversion: averaging the hypotheses of any on-line learner yields a batch predictor whose generalization error exceeds the best error in HHH by at most the average regret plus a deviation term of order 1/T1/\sqrt{T}1/T​. Any regret bound RT/T→0R_T / T \to 0RT​/T→0 therefore becomes a generalization guarantee.

Formalization Note The conclusion is the conjunction of two separate probability bounds, one per inequality, as printed (not a bound on the probability of the intersection). The sample has law D⊗TD^{\otimes T}D⊗T and is indexed from 000; "with probability at least 1−δ1 - \delta1−δ" is stated as: the (outer) probability of the failure set is at most δ\deltaδ. The loss is a function on a real vector space E⊇Y′E \supseteq Y'E⊇Y′ whose values outside Y′Y'Y′ never enter.

Differences from the source:

  • reading: Y' an unspecified prediction set, "convex with respect to its first argument" → Y' a convex subset of a real vector space E, a ↦ L(a, y) convex on Y' for every y; reason: the book leaves Y' implicit, but the average (1/T) Σ h_t and the convexity of L in its first argument only make sense in this setting; E is arbitrary, so Y' ⊆ ℝ and weight vectors are covered
  • 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) for h ∈ H, R(h_t) and R((1/T) Σ h_t) are expectations → (x, y) ↦ L(h(x), y) measurable for h ∈ H, (prefix, (x, y)) ↦ L(A(t, prefix)(x), y) jointly measurable, (x, y) ↦ L(avg(x), y) measurable for every sample; reason: these expectations and events are defined only then; no meaningful instance is excluded
  • encoding: min_{h∈H} in R_T (8.25) → infimum over H; reason: equal to the minimum whenever it is attained; H is nonempty and the losses are nonnegative, so the infimum is genuine
  • 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 in (8.27), δ > 2 in (8.28): square root 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
import Definitions.Def_MohriFoML_OnlineToBatch_avgHyp
import Definitions.Def_MohriFoML_OnlineToBatch_regret
Formal statement
namespace MohriFoML.OnlineToBatch

open MeasureTheory

/-- **Theorem 8.15: on-line to batch conversion (both (8.27) and (8.28)).**
Mohri, Rostamizadeh & Talwalkar, Foundations of Machine Learning, 2nd ed., MIT Press 2018,
§8.4, pp. 202–203 (PDF pp. 219–220), Theorem 8.15, inequalities (8.27) and (8.28); standing
setting and regret (8.25) on p. 202 (PDF p. 219).

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

**Formalization Note.** The conclusion is the conjunction of two separate probability bounds,
one per inequality (not a bound on the intersection). The sample `S : Fin T → X × Y` has law
`D^T = Measure.pi (fun _ => D)`; indices are 0-based. "With probability at least `1 − δ`" is
stated as: the (outer) probability of the failure set is at most `δ`. Predictions live in a
convex subset `Y'` of a real vector space `E` (convexity of `Y'` is part of `ConvexOn`), so the
averaged hypothesis is a hypothesis into `Y'`. The book's `min` in `R_T` and `inf` over `H` are
infima over the nonempty set `H`. Measurability of the loss of every `h ∈ H`, of each `h_t`
jointly in the prefix and the new pair, and of the averaged hypothesis makes every `R(·)` a
genuine expectation; without it `R` is undefined. `T > 0`. -/
theorem online_to_batch_averaged_hypothesis {X Y E : Type*} [MeasurableSpace X]
    [MeasurableSpace Y] [AddCommGroup E] [Module ℝ E]
    (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)
    (hL_convex : ∀ y, ConvexOn ℝ Y' (fun a => L a y))
    (H : Set (X → E)) (hH : ∀ h ∈ H, ∀ x, h x ∈ Y')
    (hH_meas : ∀ h ∈ H, Measurable (fun z : X × Y => L (h z.1) z.2))
    (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)
    (hAvg_meas : ∀ S : Fin T → X × Y,
      Measurable (fun z : X × Y => L (avgHyp A S z.1) z.2))
    (δ : ℝ) (hδ : 0 < δ) :
    (Measure.pi fun _ : Fin T => D)
        {S | ¬ (genError D L (avgHyp A S) ≤
            (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 δ ∧
    (Measure.pi fun _ : Fin T => D)
        {S | ¬ (genError D L (avgHyp A S) ≤
            (⨅ h : H, genError D L h) + regret H L A S / T +
              2 * M * Real.sqrt (2 * Real.log (2 / δ) / T))}
      ≤ ENNReal.ofReal δ := by sorry

end MohriFoML.OnlineToBatch
Source
Mohri, Rostamizadeh & Talwalkar, Foundations of Machine Learning, 2nd ed., MIT Press 2018, pp. 202–203 (PDF pp. 219–220), §8.4, Theorem 8.15, (8.27)–(8.28); regret (8.25) and standing setting on p. 202 (PDF p. 219)

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