Theorem 8.15 — on-line to batch conversion, (8.27) and (8.28)
ProvedMohriFoML.OnlineToBatch.online_to_batch_averaged_hypothesisLet be a set of hypotheses mapping to a convex prediction set (a convex subset of a real vector space), and let be a loss bounded by and convex in its first argument. 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 , let be the generalization error, and let
be the regret (8.25). Then for every , each of the following two inequalities holds with probability at least over :
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 by at most the average regret plus a deviation term of order . Any regret bound 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 and is indexed from ; "with probability at least " is stated as: the (outer) probability of the failure set is at most . The loss is a function on a real vector space whose values outside 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
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
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