Every guarantee in the preceding chapters assumes a fixed distribution and i.i.d. sampling. On-line learning drops both assumptions: an algorithm processes one example at a time, in an adversarial (worst-case) sequence, and is judged by regret against the best fixed comparator in hindsight rather than by generalization error. This chapter develops the theory for this setting — mistake bounds and regret bounds for prediction with expert advice, a margin-based mistake bound for the Perceptron — and then closes a conceptual gap: since on-line algorithms need no distributional assumption, can their guarantees be converted into ordinary distributional (batch) generalization guarantees when the data does happen to be i.i.d.? The on-line-to-batch conversion theorem answers yes, using nothing but an Azuma's-inequality martingale argument on the sequence of hypotheses the algorithm actually produces.
At round t, an on-line algorithm receives x_t, predicts ŷ_t, receives the true label
y_t, and incurs loss L(ŷ_t,y_t); its regret R_T (Eq. 8.1) compares its cumulative loss to
the best fixed action's in hindsight. §8.2 develops this for prediction with expert advice: the
Halving algorithm (realizable case), Weighted Majority and its randomized version RWM
(zero-one loss, Theorem 8.4's L_T ≤ log(N)/(1-β) + (2-β)L_T^min, proved by the chapter's
recurring potential-function technique applied to W_t = ∑_i w_{t,i}), and the Exponential
Weighted Average algorithm (convex losses). §8.3.1 analyzes the Perceptron, a linear
classification algorithm whose margin-based mistake bound (Theorem 8.8, separable case; the
non-separable Theorem 8.11, restated here, in terms of an arbitrary comparator v's hinge
losses) depends only on the normalized margin, not the ambient dimension. §8.4 shows that
averaging the hypotheses h_1,…,h_T an on-line algorithm produces while processing an i.i.d.
sample S yields a hypothesis with controlled true risk: Lemma 8.14 bounds the average of
the per-round risks R(h_t) by the average on-line loss via a martingale argument on
V_t = R(h_t) - L(h_t(x_t),y_t), and Theorem 8.15 upgrades this, via the loss's convexity, to
a bound on the risk of the averaged hypothesis (1/T)∑h_t.
Theorem 8.4 (milestone). Fix β∈[1/2,1). For any T≥1: L_T ≤ log(N)/(1-β) + (2-β)L_T^min; for β=max{1/2,1-√(log(N)/T)}: L_T ≤ L_T^min + 2√(T log N).
Theorem 8.11 (milestone). M ≤ inf_{ρ>0,‖v‖₂≤1}[(r/ρ+√(r²/ρ²+4‖l_ρ‖₁))/2]², where
l_ρ=(l_t)_{t∈I}, l_t=max{0,1-y_t(v·x_t)/ρ}.
Lemma 8.14 (milestone). For any δ>0, with probability at least 1-δ:
(1/T)∑_tR(h_t) ≤ (1/T)∑_tL(h_t(x_t),y_t) + M√(2log(1/δ)/T).
Theorem 8.15 — the mission's goal (first inequality). Under Lemma 8.14's hypotheses, with
L additionally convex in its first argument: for any δ>0, with probability at least
1-δ: R((1/T)∑_th_t) ≤ (1/T)∑_tL(h_t(x_t),y_t) + M√(2log(1/δ)/T).
Theorem 8.15 is the chapter's conceptual capstone: it is the only bridge in the whole book
between the adversarial on-line-learning framework and the distributional PAC/statistical
framework every other chapter develops, and its proof needs nothing beyond Lemma 8.14 plus
convexity — no new machinery, just the right observation about the loss's structure. Theorem
8.4 is the chapter's cleanest instance of its recurring potential-function proof technique
(reused, with variations, for Theorems 8.3, 8.6 and 8.7), and — checked against the platform's
existing OnlineConvexOpt.Introduction.randomized_weighted_majority_mistake_bound (Hazan
series) — a genuinely different result from what is already on the platform: that lemma
bounds a mistake count with a (1+ε) multiplier, this bounds the RWM algorithm's own
weighted-mixture loss with a 1/(1-β) term and a distinct optimal-β substitution,
confirming BRIEF.md's assessment that the two are close but not interchangeable. Theorem
8.11 is the non-realizable generalization of the separable-case Perceptron bound (Theorem 8.8)
that motivates soft-margin algorithms generally, expressed via an arbitrary comparator's hinge
loss rather than assuming perfect separability. No prior art exists for the chapter's other
content: GET /theorems?q=online%20to%20batch returns zero hits, and GET /theorems?q=perceptron returns only an unrelated neural-network topology result.
Theorem 8.4's proof (mirrored by Theorem 8.3's WM analogue) derives matching upper and lower
bounds on the potential W_t, combines them via a logarithm, and substitutes a specific
optimal β found by differentiating the resulting bound — a genuine two-step optimization
argument, not a direct algebraic identity. Theorem 8.11's proof solves a quadratic inequality
in √M after summing the hinge-loss-defining inequalities over the update set I and
invoking the Cauchy-Schwarz step already used in Theorem 8.8's proof; keeping the inf over
both ρ and v in the statement (not fixing them, per BRIEF.md's pitfall note) is what
makes this a genuine bound rather than a bound for one arbitrary choice. Lemma 8.14's proof is
an application of Azuma's inequality (the book's own Theorem D.7) to the martingale difference
sequence V_t = R(h_t) - L(h_t(x_t),y_t), which requires h_t to be measurable with respect
to the history strictly before round t — the on-line algorithm's hypothesis at round t
must not depend on the pair drawn at that same round, per BRIEF.md's pitfall note. Theorem
8.15's step beyond Lemma 8.14 is the passage from the average of T individual risks to the
risk of the averaged hypothesis, licensed by Jensen's inequality under the loss's convexity in
its first argument — dropping convexity breaks exactly this step, not merely weakening a
constant.
GeneralizationError restates chunk 11-regression's Eq. (11.1) convention locally (Y := ℝ,
consistent with that chunk's own harmless simplification), needed here since Theorem 8.15
requires averaging hypotheses into a single real-valued function. OnlineHypothesis A S t is
formalized so that its type signature itself enforces history-adaptedness: the on-line
algorithm A : (n:ℕ) → (Fin n → X × ℝ) → (X → ℝ) is a function of the prefix of the sample
seen so far, and OnlineHypothesis A S t applies it only to S's first t pairs — this is
what licenses Azuma's inequality's martingale-difference argument (the conditional-mean-zero
property of V_t), per BRIEF.md's pitfall note. Revision (2026-09-19), correcting an
earlier claim in this section: history-adaptedness does not by itself guard against
GeneralizationError's Bochner integral silently junking to 0 for a non-measurable
hypothesis (a distinct property — whether h_t, as a function of x, is Measurable — from
whether h_t depends on round t's own draw). Moderation found this a live gap in both Lemma
8.14 and Theorem 8.15's drafted statements; both now carry an explicit hAmeas/hLmeas
hypothesis in addition to the history-adapted type signature.
RWM's w_{t,i}, W_t, p_{t,i}, L_t, L_T, L_{T,i}, L_T^min are modeled as their own
recursively-defined algorithm state (mirroring, but never substituting into, chunk
07-boosting's AdaBoost pattern), matching this chapter's own loss-based (not mistake-count)
quantities, per BRIEF.md's pitfall note distinguishing them from AdaBoost's and RWM-mistake
variants. The Perceptron's w_t, update-index set I, and M = |I| are modeled the same way,
using Eq. (8.23)'s equivalent sign-agreement update rule (the book's own reformulation of
Figure 8.6's sgn-based rule). Theorem 8.11's inf_{ρ>0,‖v‖₂≤1} is a genuine nested restricted
infimum (⨅ ρ ∈ Set.Ioi 0, ⨅ v ∈ Metric.closedBall 0 1, …), not a bound instantiated at fixed
ρ, v, per BRIEF.md's explicit pitfall note. No numerical constant is altered from the
book in any of the four theorems.
Not formalized: Theorems 8.1-8.3 (Halving and WM mistake bounds — the chapter's warm-up
results, superseded in content by the more general RWM/EWA theorems that follow), Theorem 8.5
(a matching lower bound, a distinct impossibility result rather than an algorithm's guarantee),
Theorems 8.6-8.7 (Exponential Weighted Average regret bounds — a third algorithm with its own
potential-function proof, out of scope per BRIEF.md's restriction to §8.2's Halving/WM/RWM),
Theorems 8.8-8.10 (the Perceptron's separable-case bound and its leave-one-out-based expected
generalization bounds, both superseded in generality by Theorem 8.11 for this mission's
purposes), Theorem 8.12 (Perceptron's L²-norm hinge-loss bound, the book's own note that it is
implied by, and looser than, Theorem 8.11's L¹-norm bound), the dual/kernel Perceptron (an
equivalent reformulation, not new generalization content), and Theorem 8.15's second displayed
inequality (a regret-form corollary depending on the regret decomposition of the surrounding
discussion, not drafted per BRIEF.md's own recommendation to commit to the first inequality
as the goal). §8.3.2 (Winnow) and §8.5 (the game-theoretic connection) are out of scope per
BRIEF.md's chapter restriction.
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
Let 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:
No open leaves. Every sub-goal is proved or awaiting decomposition.