Algorithmic Stability and Online Learning

Intuition Beginner

The earlier units measured a family of rules by how rich it is, then argued that a rich family can fool you by fitting noise. This unit offers two different lenses on the same worry, neither of which counts the family at all. The first asks a question about the learning procedure itself: if you remove one training example, does the rule it produces change much? A procedure that barely flinches when you drop one example cannot have leaned hard on any single point, so it cannot have memorised the noise in your sample. That insensitivity is called stability, and it turns out that a stable procedure automatically generalises.

Why is stability the right thing to ask about? Because overfitting is, at heart, sensitivity to individual examples. A rule that fits the noise must change a lot when the noisy point is removed. So a procedure built to resist such change — for instance by adding a penalty that discourages extreme rules — is a procedure that cannot overfit. This explains why penalised methods like ridge regression and support vector machines work well even when the family of candidate rules is enormous.

The second lens drops the assumption that data come from a fixed distribution at all. Picture a game played day by day. Each day you predict tomorrow's weather, then nature reveals the truth, possibly chosen by an adversary to trip you up. You cannot hope to be right every time. Instead you measure regret: how much worse you did than the single best fixed forecaster, looking back. A good online method keeps its average regret shrinking to zero, so over time it does almost as well as the best fixed rule, even against an adversary. Remarkably, a method that wins this adversarial game can be turned into one that generalises in the ordinary fixed-distribution setting.

Visual Beginner

Two pictures. On the left, stability: a learning recipe takes in a class roster and outputs a rule; remove one student and rerun, and a stable recipe gives almost the same rule, while an unstable one lurches. On the right, the online game: each round you guess, then the answer arrives, and you tally how far behind the best fixed expert you have fallen.

   STABILITY                              ONLINE / REGRET
   full sample S  --> recipe --> rule h   round 1: guess, see answer, tally
   drop one point --> recipe --> rule h'  round 2: guess, see answer, tally
                                          ...
   stable:   h and h' nearly identical    regret = your total loss
   unstable: h and h' very different              minus best fixed expert's
   "barely notices a missing point"       "how much you regret not copying
   = cannot have memorised it             the best single expert all along"

Lens	What it measures	Good behaviour means
stability	change in output when one example is dropped	small change, so no overfitting
regret (online)	gap to the best fixed rule in hindsight	average gap shrinks to zero
capacity (earlier units)	richness of the family	small relative to sample size

These two pictures, plus the capacity lens of the earlier units, are three independent ways to certify that a learner will do well on data it has not seen.

Worked example Beginner

We watch a tiny online game with three weather experts and a learner that follows the weighted-majority rule. Each day an expert says rain or shine; the learner blends their votes by weight and predicts the heavier side. After the truth is revealed, every expert who was wrong has its weight halved.

Step 1. Start all weights equal: $(1,1,1)$, total weight $3$.

Step 2. Day one. Experts say (rain, rain, shine). Weighted vote for rain is $1+1=2$, for shine is $1$. The learner predicts rain. Truth is shine, so experts one and two were wrong. Halve their weights: $(0.5,0.5,1)$.

Step 3. Day two. Experts say (shine, rain, shine). Weighted vote for shine is $0.5+1=1.5$, for rain is $0.5$. The learner predicts shine. Truth is shine, everyone correct who said shine; experts one and three keep their weight, expert two is wrong and is halved: $(0.5,0.25,1)$.

Step 4. Count. The learner made one mistake in two days. Expert three, the best fixed expert so far, made zero. The running gap is one mistake, but notice expert three's weight has grown relative to the others, so the learner is steadily concentrating on the best expert.

What this tells us: by demoting wrong experts, the learner's weight piles onto whoever is doing best, so its long-run mistake count stays close to that of the best single expert. The gap, divided by the number of days, shrinks toward zero — that is the no-regret promise.

Check your understanding Beginner

Formal definition Intermediate+

The setting is the learning framework of 45.07.05: a domain $\mathcal{Z}$ (typically $\mathcal{X}\times \mathcal{Y}$), an unknown distribution $\mathcal{D}$, a sample $S=(z_1,\dots ,z_n)\sim {\mathcal{D}}^n$, a loss $\ell$ with values in $[0,M]$, and the risk $R(h)={\mathbb{E}}_{z\sim \mathcal{D}}\ell (h,z)$ with empirical counterpart ${\hat{R}}_S(h)=\frac{1}{n}{\sum }_i\ell (h,z_i)$. A learning algorithm is a map $A$ sending a sample $S$ to a hypothesis $A_S$. Write $S^{\setminus i}$ for $S$ with the $i$-th example deleted and $S^i$ for $S$ with the $i$-th example replaced by an independent $z_i^{\prime }\sim \mathcal{D}$.

Definition (uniform stability). The algorithm $A$ is $\beta$-uniformly stable if for every sample $S$ of size $n$, every index $i\in \{1,\dots ,n\}$, and every $z\in \mathcal{Z}$,

$$|\ell (A_S,z)-\ell (A_{S^{\setminus i}},z)|\le \beta .$$

The replacement variant bounds $|\ell (A_S,z)-\ell (A_{S^i},z)|$ and is equivalent up to a factor of $2$. Uniform stability is a property of the algorithm and loss, not of any hypothesis class; it makes no reference to capacity ^{[Bousquet Elisseeff 2002]}.

Definition (regularized loss minimization / Tikhonov regularization). For a convex loss $\ell$ and a reproducing-kernel Hilbert space ${\mathcal{H}}_K$ (the RKHS of 45.07.05), the RLM algorithm returns

$$A_S=\arg \underset{f\in {\mathcal{H}}_K}{\min }\{{\hat{R}}_S(f)+\lambda \Vert f{\Vert }_K^2\}.$$

The penalty $\lambda \Vert f{\Vert }_K^2$ makes the objective $2\lambda$-strongly convex, which is the source of stability. A loss is $\sigma$-admissible if it is convex and $\sigma$-Lipschitz in its prediction argument.

Definition (online learning, mistakes, regret). In the online model the interaction proceeds in rounds $t=1,\dots ,T$: the learner receives $x_t$, outputs a prediction ${\hat{y}}_t$, then observes the true $y_t$ and suffers loss $\ell ({\hat{y}}_t,y_t)$. In the realizable classification case some target $h^{\star }\in \mathcal{H}$ satisfies $y_t=h^{\star }(x_t)$ for all $t$, and the relevant quantity is the total number of mistakes ${\sum }_{t}1[{\hat{y}}_t\ne y_t]$; an algorithm has mistake bound $M$ if it makes at most $M$ mistakes on any realizable stream. In the general (agnostic) case the quantity is the regret against a comparator class $\mathcal{F}$,

$${\mathrm{Reg}}_T=\sum _{t=1}^T\ell ({\hat{y}}_t,y_t)-\underset{f\in \mathcal{F}}{\min }\sum _{t=1}^T\ell (f(x_t),y_t),$$

and the algorithm is no-regret if ${\mathrm{Reg}}_T/T\to 0$ for every (possibly adversarial) stream.

Definition (Littlestone dimension). A mistake tree (shattered tree) for $\mathcal{H}$ on $\mathcal{X}$ is a complete binary tree of depth $d$ whose internal nodes are labelled by instances $x$, such that for every root-to-leaf path — reading the left/right branch taken at each node as the bit $0/1$ — there is an $h\in \mathcal{H}$ consistent with the instance/bit pairs along that path. The Littlestone dimension $\mathrm{Ldim}(\mathcal{H})$ is the depth of the deepest such tree (possibly $\infty$). It is the online/sequential analogue of the VC dimension: VC shatters an unordered set, while $\mathrm{Ldim}$ shatters an adaptively chosen tree, so $\mathrm{Ldim}(\mathcal{H})\ge \mathrm{VCdim}(\mathcal{H})$ always ^{[Littlestone 1988]}.

Counterexamples to common slips Intermediate+

• "Stability is just a restatement of low capacity." It is logically independent: the $1$-nearest-neighbour rule has unbounded capacity (it interpolates any sample) and is not uniformly stable, while regularized convex ERM is stable with $\beta =O(1/(\lambda n))$ regardless of how large the RKHS is. Stability bounds generalization through the algorithm; capacity bounds it through the class.
• "Finite VC dimension implies online learnability." False for the realizable online model. The class of thresholds on $[0,1]$ has VC dimension $1$ but infinite Littlestone dimension — an adversary can binary-search the threshold forever, forcing a mistake every round. Online learnability needs finite $\mathrm{Ldim}$, a strictly stronger condition than finite VC.
• "Regret measures distance to the optimal predictor." It measures distance to the best fixed member of the comparator class in hindsight. Against an adversary the best fixed expert may itself incur large loss; no-regret only promises you match that comparator, not that the loss is small in absolute terms.

Key theorem with proof Intermediate+

The signature result is that uniform stability implies generalization: a stable algorithm's empirical risk is, in expectation and with high probability, close to its true risk, with the high-probability statement coming from the bounded-differences inequality of 45.07.05's concentration prerequisite. The companion fact is that strongly-convex regularized ERM is uniformly stable, so the two together explain the generalization of ridge and SVM directly from the algorithm.

Theorem (stability implies generalization). Let $A$ be $\beta$-uniformly stable with loss bounded by $M$. Then

$$\left|{\mathbb{E}}_S\left[R(A_S)-{\hat{R}}_S(A_S)\right]\right|\le \beta ,$$

and for every $\delta \in (0,1)$, with probability at least $1-\delta$ over $S\sim {\mathcal{D}}^n$,

$$R(A_S)\le {\hat{R}}_S(A_S)+\beta +(2n\beta +M)\sqrt{\frac{\log (1/\delta )}{2n}}.$$

Moreover, RLM over an RKHS with a $\sigma$-admissible loss and ${\sup }_{x}K(x,x)\le {\kappa }^2$ is $\beta$-uniformly stable with $\beta \le {\sigma }^2{\kappa }^2/(2\lambda n)$, so its generalization gap is $O({\sigma }^2{\kappa }^2/(\lambda n)+(M/\sqrt{n}))$. ^{[Bousquet Elisseeff 2002]}

Proof. For the expectation bound, introduce a ghost sample $S^{\prime }=(z_1^{\prime },\dots ,z_n^{\prime })\sim {\mathcal{D}}^n$ independent of $S$, and let $S^i$ be $S$ with $z_i$ replaced by $z_i^{\prime }$. Since $z_i^{\prime }$ is a fresh draw, ${\mathbb{E}}_{S}R(A_S)={\mathbb{E}}_{S,S^{\prime }}\frac{1}{n}{\sum }_i\ell (A_S,z_i^{\prime })$ and ${\mathbb{E}}_S{\hat{R}}_S(A_S)={\mathbb{E}}_S\frac{1}{n}{\sum }_i\ell (A_S,z_i)$. Because $(S,z_i^{\prime })$ and $(S^i,z_i)$ have the same joint law under the swap $z_i\leftrightarrow z_i^{\prime }$, renaming gives ${\mathbb{E}}_{S,S^{\prime }}\ell (A_S,z_i^{\prime })={\mathbb{E}}_{S,S^{\prime }}\ell (A_{S^i},z_i)$. Therefore

$${\mathbb{E}}_S\left[R(A_S)-{\hat{R}}_S(A_S)\right]=\frac{1}{n}\sum _{i=1}^n{\mathbb{E}}_{S,S^{\prime }}[\ell (A_{S^i},z_i)-\ell (A_S,z_i)],$$

and each summand is at most $\beta$ in absolute value by uniform stability (the replacement form, with the factor folded into $\beta$). The mean is thus bounded by $\beta$.

For the high-probability bound, view $\Phi (S)=R(A_S)-{\hat{R}}_S(A_S)$ as a function of the $n$ independent coordinates $z_1,\dots ,z_n$ and verify the bounded-differences property. Replacing $z_i$ by $z_i^{\prime }$ changes $A_S$ to $A_{S^i}$; uniform stability bounds the change in $R(A_S)$ by $\beta$ and in each term of ${\hat{R}}_S(A_S)$ by $\beta$, while the directly altered empirical term changes by at most $M/n$. Collecting, $|\Phi (S)-\Phi (S^i)|\le 2\beta +M/n=:c_i$. McDiarmid's inequality (the bounded-differences inequality assumed by 45.07.05) gives, with probability $\ge 1-\delta$,

$$\Phi (S)\le {\mathbb{E}}_S\Phi (S)+\sqrt{\frac{{\sum }_i{c}_i^2}{2}\log \frac{1}{\delta }}={\mathbb{E}}_S\Phi (S)+(2n\beta +M)\sqrt{\frac{\log (1/\delta )}{2n}},$$

using ${\sum }_i{c}_i^2=n(2\beta +M/n{)}^2=(2n\beta +M{)}^2/n$. Bounding ${\mathbb{E}}_S\Phi (S)\le \beta$ by the first part yields the displayed bound.

For RLM stability, let $F_S(f)={\hat{R}}_S(f)+\lambda \Vert f{\Vert }_K^2$, which is $2\lambda$-strongly convex in $f$ over ${\mathcal{H}}_K$. Let $f=A_S$ and $f^{\prime }=A_{S^{\setminus i}}$ be the two minimizers. Strong convexity gives the quadratic lower bound $F_S(f^{\prime })\ge F_S(f)+\lambda \Vert f^{\prime }-f{\Vert }_K^2$ (the gradient at the minimizer vanishes), and symmetrically for $F_{S^{\setminus i}}$. Adding the two inequalities, the regularization terms cancel and only the single differing loss term survives:

$$2\lambda \Vert f-f^{\prime }{\Vert }_K^2\le \frac{1}{n}[\ell (f^{\prime },z_i)-\ell (f,z_i)]\le \frac{\sigma }{n}|f^{\prime }(x_i)-f(x_i)|,$$

the last step by $\sigma$-admissibility (the loss is $\sigma$-Lipschitz in the prediction). The reproducing property and Cauchy-Schwarz give $|f^{\prime }(x_i)-f(x_i)|=|⟨f^{\prime }-f,K_{x_i}{⟩}_K|\le \Vert f^{\prime }-f{\Vert }_K\sqrt{K(x_i,x_i)}\le \kappa \Vert f^{\prime }-f{\Vert }_K$. Substituting and cancelling one factor of $\Vert f-f^{\prime }{\Vert }_K$ yields $\Vert f-f^{\prime }{\Vert }_K\le \sigma \kappa /(2\lambda n)$. Finally, for any $z$ the loss change is $|\ell (f,z)-\ell (f^{\prime },z)|\le \sigma |f(x)-f^{\prime }(x)|\le \sigma \kappa \Vert f-f^{\prime }{\Vert }_K\le {\sigma }^2{\kappa }^2/(2\lambda n)=\beta$. $\square$

Bridge. This theorem is the foundational reason regularized convex learners generalize even where the uniform-convergence bound of 45.07.05 is loose: it shows the generalization gap is controlled by an algorithmic quantity, $\beta =O(1/(\lambda n))$, with no reference to the capacity of the RKHS, and the bridge is the same bounded-differences inequality that upgraded the in-expectation Rademacher bound to a high-probability one, here applied to $\Phi (S)=R(A_S)-{\hat{R}}_S(A_S)$ instead of to a supremum over the class. This is exactly the substitution that makes the lens shift visible: where Rademacher complexity measured the class, stability measures the map, and putting these together the strong convexity injected by the penalty $\lambda \Vert f{\Vert }_K^2$ is what converts a Lipschitz loss into a $1/(\lambda n)$ stability, so the regularization that 45.07.05 read as shrinking the effective complexity is here read as buying stability. The result builds toward the online theory of the same chapter, where the analogous regret bound appears again as a sequential, distribution-free certificate, and the central insight — that learnability has several independent certificates — is what online-to-batch conversion makes precise. The bridge is that stability and regret are the two algorithm-side lenses complementing the class-side capacity lens, all three bounding the same generalization gap.

Exercises Intermediate+

Advanced results Master

The two lenses divide into four developments: stability as a generalization certificate, the strong-convexity mechanism that produces it, the Littlestone characterization of online learnability, and the regret machinery that unifies the online setting with the batch one through conversion.

Theorem 1 (stability implies generalization; sharp constants). For a $\beta$-uniformly stable algorithm with loss in $[0,M]$, ${\mathbb{E}}_S[R(A_S)-{\hat{R}}_S(A_S)]\le \beta$, and with probability $\ge 1-\delta$, $R(A_S)\le {\hat{R}}_S(A_S)+\beta +(2n\beta +M)\sqrt{\log (1/\delta )/(2n)}$ ^{[Bousquet Elisseeff 2002]}. The high-probability statement is the bounded-differences inequality applied to the gap functional, with bounded-difference constant $2\beta +M/n$; for the bound to be non-vacuous one needs $\beta =o(1/\sqrt{n})$, which the $O(1/(\lambda n))$ stability of regularization comfortably supplies. Hypothesis stability — a weaker $L^1$ form — gives only a variance/Chebyshev bound, so the uniform notion is what buys the exponential concentration.

Theorem 2 (RLM / Tikhonov is uniformly stable). Regularized loss minimization $A_S=\arg {\min }_f{\hat{R}}_S(f)+\lambda \Vert f{\Vert }_K^2$ over an RKHS with $\sigma$-admissible loss and ${\sup }_{x}K(x,x)\le {\kappa }^2$ is $\beta$-uniformly stable with $\beta \le {\sigma }^2{\kappa }^2/(2\lambda n)$ ^{[Bousquet Elisseeff 2002]}. The mechanism is the $2\lambda$-strong convexity of the penalised objective: two minimizers on samples differing in one point cannot be far apart, because the strongly-convex objective grows quadratically away from its minimizer while the two objectives differ by only one $1/n$-weighted loss term. Soft-margin SVM ($\sigma$-admissible hinge loss) and kernel ridge regression are the canonical instances, so stability explains their generalization where a uniform-convergence argument over the unbounded RKHS would be loose — the complement to the norm-based Rademacher bound of 45.07.05, which controls the same learners through the class rather than the algorithm.

Theorem 3 (Littlestone dimension characterizes online learnability). In the realizable online model, the optimal mistake bound for $\mathcal{H}$ equals $\mathrm{Ldim}(\mathcal{H})$, attained by the Standard Optimal Algorithm, and no algorithm achieves fewer mistakes against a worst-case stream ^{[Littlestone 1988]}. Thus $\mathcal{H}$ is online learnable in the mistake-bound sense iff $\mathrm{Ldim}(\mathcal{H})<\infty$, the sequential analogue of the VC characterization of 45.07.04; since shattering a tree is at least as demanding as shattering a set, $\mathrm{VCdim}\le \mathrm{Ldim}$, with thresholds on $[0,1]$ (VC dimension $1$, Littlestone dimension $\infty$) the canonical gap. In the agnostic online setting the minimax regret is governed by the sequential Rademacher complexity, the tree-indexed analogue of the empirical Rademacher complexity of 45.07.05.

Theorem 4 (Weighted Majority, Hedge, and online-to-batch). Against $N$ experts with losses in $[0,1]$, the exponentially-weighted Hedge forecaster with $\eta =\sqrt{8\log N/T}$ has regret ${\mathrm{Reg}}_T\le \sqrt{(T/2)\log N}$, and deterministic Weighted Majority makes at most $\frac{\log N}{\log (2/(1+\beta ))}$ mistakes (with multiplicative factor $\beta$) ^{[Cesa-Bianchi Lugosi 2006]}. These are the prediction-with-expert-advice instances of the mirror-descent / exponentiated-gradient regret bound of 44.06.05, the entropic mirror map on the simplex of experts. Online-to-batch conversion (Exercise 8) turns any $O(\sqrt{T})$ regret into an $O(1/\sqrt{T})$ batch excess-risk bound on the averaged hypothesis, so the no-regret guarantee and the stochastic-optimization guarantee are one statement read in two directions, exactly as in 44.06.05.

Synthesis. The foundational reason this chapter has three lenses on generalization is that the same gap $R(h)-{\hat{R}}_S(h)$ admits a class-side certificate (capacity, the Rademacher complexity of 45.07.05), an algorithm-side certificate in the batch setting (uniform stability), and an algorithm-side certificate in the sequential setting (low regret), and each is the natural object for a different question. This is exactly why regularization appears twice: in 45.07.05 the penalty $\lambda \Vert f{\Vert }_K^2$ shrinks the effective norm-ball complexity, while here the same penalty makes the objective $2\lambda$-strongly convex and so buys $O(1/(\lambda n))$ stability — one design choice, two readings, and the central insight is that strong convexity is the common cause of both the complexity control and the stability. The online theory is dual to the batch theory through online-to-batch conversion, which generalises the offline-to-online correspondence of 44.06.05: a no-regret online method, run on i.i.d. data, yields a batch learner, so the Littlestone dimension is to the online setting what the VC dimension of 45.07.04 is to the batch setting, and the Hedge regret bound is the simplex mirror-descent bound of 44.06.05. Putting these together, the bridge across the whole chapter is concentration: the bounded-differences inequality upgrades the in-expectation stability and Rademacher bounds alike to high-probability statements, so capacity, stability, and regret are not competing theories but three faces of the single fact that a learner which cannot be shaken — by a rich-but-controlled class, by deleting one point, or by an adversarial stream — is a learner that generalizes.

Full proof set Master

Proposition 1 (stability implies generalization in expectation). If $A$ is $\beta$-uniformly stable then $|{\mathbb{E}}_S[R(A_S)-{\hat{R}}_S(A_S)]|\le \beta$.

Proof. With a ghost sample $S^{\prime }$ and $S^i$ the replacement of $z_i$ by $z_i^{\prime }$, ${\mathbb{E}}_{S}R(A_S)={\mathbb{E}}_{S,S^{\prime }}\frac{1}{n}{\sum }_i\ell (A_S,z_i^{\prime })$ since each $z_i^{\prime }$ is an independent test point. Relabelling $z_i\leftrightarrow z_i^{\prime }$, which preserves the i.i.d. joint law, gives ${\mathbb{E}}_{S,S^{\prime }}\ell (A_S,z_i^{\prime })={\mathbb{E}}_{S,S^{\prime }}\ell (A_{S^i},z_i)$. Hence ${\mathbb{E}}_S[R(A_S)-{\hat{R}}_S(A_S)]=\frac{1}{n}{\sum }_i{\mathbb{E}}_{S,S^{\prime }}[\ell (A_{S^i},z_i)-\ell (A_S,z_i)]$, and each term has absolute value $\le \beta$ by uniform stability (replacement form). The average is bounded by $\beta$. $\square$

Proposition 2 (high-probability stability bound). Under the hypotheses of Proposition 1 with loss in $[0,M]$, with probability $\ge 1-\delta$, $R(A_S)\le {\hat{R}}_S(A_S)+\beta +(2n\beta +M)\sqrt{\log (1/\delta )/(2n)}$.

Proof. Let $\Phi (S)=R(A_S)-{\hat{R}}_S(A_S)$. Replacing $z_i$ by $z_i^{\prime }$ changes $R(A_S)$ by $\le \beta$ (stability) and changes ${\hat{R}}_S(A_S)$ by $\le \beta +M/n$: each of the $n$ loss terms moves by $\le \beta$ through the change of hypothesis, but the directly replaced term $\ell (A_S,z_i)\mapsto \ell (A_{S^i},z_i^{\prime })$ also moves by $\le M/n$ from the data change, and a careful accounting collapses this to a single $2\beta +M/n$ bounded difference for $\Phi$. McDiarmid's inequality with $c_i=2\beta +M/n$ gives $\mathrm{Pr}[\Phi (S)\ge \mathbb{E}\Phi +t]\le \exp (-2t^2/{\sum }_i{c}_i^2)$ with ${\sum }_i{c}_i^2=(2n\beta +M{)}^2/n$. Setting the right side to $\delta$ and using $\mathbb{E}\Phi \le \beta$ from Proposition 1 yields the bound. $\square$

Proposition 3 (RLM uniform stability). RLM over an RKHS with $\sigma$-admissible loss and ${\sup }_{x}K(x,x)\le {\kappa }^2$ is $\beta$-uniformly stable with $\beta \le {\sigma }^2{\kappa }^2/(2\lambda n)$.

Proof. Let $f=A_S$, $f^{\prime }=A_{S^{\setminus i}}$ minimise the $2\lambda$-strongly-convex objectives $F_S$ and $F_{S^{\setminus i}}$. Strong convexity at a minimizer gives $F_S(f^{\prime })\ge F_S(f)+\lambda \Vert f-f^{\prime }{\Vert }_K^2$ and $F_{S^{\setminus i}}(f)\ge F_{S^{\setminus i}}(f^{\prime })+\lambda \Vert f-f^{\prime }{\Vert }_K^2$. Adding, the penalties and all shared loss terms cancel, leaving $2\lambda \Vert f-f^{\prime }{\Vert }_K^2\le \frac{1}{n}[\ell (f^{\prime },z_i)-\ell (f,z_i)]\le \frac{\sigma }{n}|f^{\prime }(x_i)-f(x_i)|$ by $\sigma$-admissibility. The reproducing property and Cauchy-Schwarz give $|f^{\prime }(x_i)-f(x_i)|=|⟨f^{\prime }-f,K_{x_i}{⟩}_K|\le \kappa \Vert f-f^{\prime }{\Vert }_K$. Substituting and cancelling one factor of $\Vert f-f^{\prime }{\Vert }_K$ gives $\Vert f-f^{\prime }{\Vert }_K\le \sigma \kappa /(2\lambda n)$; then $|\ell (f,z)-\ell (f^{\prime },z)|\le \sigma \kappa \Vert f-f^{\prime }{\Vert }_K\le {\sigma }^2{\kappa }^2/(2\lambda n)$ for every $z$. $\square$

Proposition 4 (Perceptron mistake bound). For data with $\Vert x_t\Vert \le R$ separable with margin $\gamma$ by a unit $u$, the Perceptron makes at most $(R/\gamma {)}^2$ mistakes.

Proof. Indexing by mistakes, $w_0=0$ and $w_k=w_{k-1}+y_t{x}_t$. The projection grows: $⟨u,w_k⟩\ge ⟨u,w_{k-1}⟩+\gamma$, so $⟨u,w_m⟩\ge m\gamma$. The norm grows slowly: $\Vert w_k{\Vert }^2=\Vert w_{k-1}{\Vert }^2+2y_t⟨w_{k-1},x_t⟩+\Vert x_t{\Vert }^2\le \Vert w_{k-1}{\Vert }^2+R^2$ because the mistake condition $y_t⟨w_{k-1},x_t⟩\le 0$ kills the cross term, so $\Vert w_m{\Vert }^2\le m{R}^2$. Cauchy-Schwarz gives $m\gamma \le ⟨u,w_m⟩\le \Vert w_m\Vert \le \sqrt{m}R$, hence $m\le (R/\gamma {)}^2$. $\square$

Proposition 5 (Standard Optimal Algorithm achieves $\mathrm{Ldim}$). In the realizable online model the SOA makes at most $\mathrm{Ldim}(\mathcal{H})$ mistakes, and this is optimal.

Proof. The SOA maintains the version space $V_t$ and predicts the label $b$ with $\mathrm{Ldim}(V_t^{(b)})$ larger, where $V_t^{(b)}=\{h\in V_t:h(x_t)=b\}$. If it errs, the true label is the smaller-dimension one. Both children cannot have $\mathrm{Ldim}\ge \mathrm{Ldim}(V_t)$: joining two shattered trees of depth $\mathrm{Ldim}(V_t)$ under the node $x_t$ would exhibit a shattered tree of depth $\mathrm{Ldim}(V_t)+1$ inside $V_t$, contradicting the definition. So $\mathrm{Ldim}(V_{t+1})\le \mathrm{Ldim}(V_t)-1$ on every mistake; starting from $\mathrm{Ldim}(\mathcal{H})$ and staying nonnegative bounds the mistakes by $\mathrm{Ldim}(\mathcal{H})$. Optimality is the adversary of Exercise 7, which walks a depth-$\mathrm{Ldim}(\mathcal{H})$ shattered tree and answers against the learner, forcing $\mathrm{Ldim}(\mathcal{H})$ mistakes. $\square$

Proposition 6 (Hedge regret bound). Hedge with losses in $[0,1]$ and $\eta =\sqrt{8\log N/T}$ has ${\mathrm{Reg}}_T\le \sqrt{(T/2)\log N}$.

Proof. With ${\Phi }_t=\log {\sum }_i{e}^{-\eta L_{t,i}}$, the per-round increment is ${\Phi }_t-{\Phi }_{t-1}=\log {\mathbb{E}}_{i\sim p_t}{e}^{-\eta {\ell }_{t,i}}\le -\eta {\hat{\ell }}_t+{\eta }^2/8$ by Hoeffding's lemma for $[0,1]$-bounded variables. Telescoping, ${\Phi }_T-\log N\le -\eta {\sum }_t{\hat{\ell }}_t+{\eta }^{2}T/8$, while ${\Phi }_T\ge -\eta {\min }_i{L}_{T,i}$. Rearranging, ${\sum }_t{\hat{\ell }}_t-{\min }_i{L}_{T,i}\le \frac{\log N}{\eta }+\frac{\eta T}{8}$; the optimal $\eta =\sqrt{8\log N/T}$ gives $\sqrt{(T/2)\log N}$. $\square$

Proposition 7 (online-to-batch conversion). An online algorithm with regret $\le B_T$ on i.i.d. data with convex bounded loss yields $\mathbb{E}[R(\bar{h})]\le {\min }_{f}R(f)+B_T/T$ for the averaged hypothesis $\bar{h}=\frac{1}{T}{\sum }_t{h}_t$.

Proof. Since $h_t$ depends only on $z_{<t}$ and $z_t\perp z_{<t}$, $\mathbb{E}[\ell (h_t,z_t)]=\mathbb{E}[R(h_t)]$, and $\mathbb{E}[\ell (f,z_t)]=R(f)$ for fixed $f$. Taking expectations of the regret inequality ${\sum }_t\ell (h_t,z_t)-{\sum }_t\ell (f,z_t)\le B_T$ gives $\frac{1}{T}{\sum }_t\mathbb{E}R(h_t)\le R(f)+B_T/T$. Convexity of $\ell$ in the prediction and Jensen give $R(\bar{h})\le \frac{1}{T}{\sum }_{t}R(h_t)$, so $\mathbb{E}[R(\bar{h})]\le {\min }_{f}R(f)+B_T/T$. $\square$

Connections Master

This unit is the algorithm-side complement of the class-side theory of 45.07.05. Rademacher complexity bounds the generalization gap uniformly over the hypothesis class through the data-dependent complexity of that class; uniform stability bounds the same gap through the sensitivity of the algorithm to a single example, with no capacity term. For regularized convex learners the two meet: the penalty $\lambda \Vert f{\Vert }_K^2$ shrinks the norm-ball complexity in the Rademacher bound and simultaneously makes the objective strongly convex, the source of the $O(1/(\lambda n))$ stability, so the same regularization is read by both lenses.

This unit extends the characterization theme of 45.07.04. There the fundamental theorem identified finite VC dimension as the combinatorial characterization of batch (PAC) learnability via uniform convergence; here the Littlestone dimension plays the exactly parallel role for the online realizable model, characterizing sequential learnability through shattered trees rather than shattered sets. Since $\mathrm{VCdim}\le \mathrm{Ldim}$, online learnability is strictly stronger, and the threshold class is the canonical witness; the agnostic online minimax regret is governed by the tree-indexed sequential Rademacher complexity, the sequential analogue of the empirical Rademacher complexity.

This unit consumes the online convex optimization theory of 44.06.05. The Hedge / multiplicative-weights forecaster is precisely mirror descent with the entropic map on the simplex of experts, so its $\sqrt{T\log N}$ regret is the simplex instance of the OCO regret bound proved there; online-to-batch conversion, also developed there, is what turns the no-regret online guarantee into a batch excess-risk bound, making the stochastic-optimization rate and the regret bound a single statement read in two directions.

The high-probability upgrade throughout relies on the bounded-differences (McDiarmid) inequality, the same concentration tool 45.07.05 used to upgrade its in-expectation Rademacher bound; here it is applied to the gap functional $\Phi (S)=R(A_S)-{\hat{R}}_S(A_S)$, whose bounded-difference constant is $2\beta +M/n$. The stability route and the Rademacher route to a high-probability generalization bound thus share their concentration engine.

The RKHS regularization that makes RLM stable is the kernel-machine framework whose representer theorem and norm geometry 45.07.05 uses for its dimension-free Rademacher bounds; soft-margin SVM and kernel ridge regression are the shared canonical instances, certified by stability here and by norm-based complexity there.

Historical & philosophical context Master

The idea that an algorithm insensitive to individual training points must generalize traces to the leave-one-out and cross-validation heuristics of the 1970s and to the hypothesis stability notion of Devroye and Wagner (1979) for nearest-neighbour and local rules. The modern uniform stability definition, together with the exponential generalization bound obtained by applying the bounded-differences inequality to the leave-one-out gap and the proof that Tikhonov / RKHS regularization with a $\sigma$-admissible loss is ${\sigma }^2{\kappa }^2/(2\lambda n)$-stable, is due to Olivier Bousquet and André Elisseeff in their 2002 Journal of Machine Learning Research paper ^{[Bousquet Elisseeff 2002]}.

The online mistake-bound model and the combinatorial characterization of online learnability were introduced by Nick Littlestone in 1988, who defined the dimension that bears his name as the depth of the deepest realized shattered binary tree, proved that the optimal realizable mistake bound equals it, and gave the Standard Optimal Algorithm and the WINNOW multiplicative-update rule ^{[Littlestone 1988]}. The Perceptron mistake bound for margin-separable data is older, from the convergence analysis of Block (1962) and Novikoff (1962). The prediction-with-expert-advice framework, the Weighted Majority algorithm of Littlestone and Warmuth (1994), and the Hedge / exponentially-weighted-average forecaster with its $\sqrt{T\log N}$ regret were synthesized by Nicolò Cesa-Bianchi and Gábor Lugosi in their 2006 monograph, which also developed online-to-batch conversion ^{[Cesa-Bianchi Lugosi 2006]}. The textbook account assembling uniform stability, the Littlestone dimension, and the weighted-majority regret bound into the form used here is due to Shalev-Shwartz and Ben-David, whose chapters 13 and 21 are the intermediate anchors for this unit.

Bibliography Master

@article{bousquetelisseeff2002,
  author  = {Bousquet, Olivier and Elisseeff, Andr\'e},
  title   = {Stability and generalization},
  journal = {Journal of Machine Learning Research},
  volume  = {2},
  pages   = {499--526},
  year    = {2002}
}

@article{littlestone1988,
  author  = {Littlestone, Nick},
  title   = {Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm},
  journal = {Machine Learning},
  volume  = {2},
  number  = {4},
  pages   = {285--318},
  year    = {1988}
}

@article{littlestonewarmuth1994,
  author  = {Littlestone, Nick and Warmuth, Manfred K.},
  title   = {The weighted majority algorithm},
  journal = {Information and Computation},
  volume  = {108},
  number  = {2},
  pages   = {212--261},
  year    = {1994}
}

@article{freundschapire1997,
  author  = {Freund, Yoav and Schapire, Robert E.},
  title   = {A decision-theoretic generalization of on-line learning and an application to boosting},
  journal = {Journal of Computer and System Sciences},
  volume  = {55},
  number  = {1},
  pages   = {119--139},
  year    = {1997}
}

@book{cesabianchilugosi2006,
  author    = {Cesa-Bianchi, Nicol\`o and Lugosi, G\'abor},
  title     = {Prediction, Learning, and Games},
  publisher = {Cambridge University Press},
  year      = {2006}
}

@book{shalevshwartzbendavid2014s,
  author    = {Shalev-Shwartz, Shai and Ben-David, Shai},
  title     = {Understanding Machine Learning: From Theory to Algorithms},
  publisher = {Cambridge University Press},
  year      = {2014}
}

@article{shalevshwartz2012,
  author  = {Shalev-Shwartz, Shai},
  title   = {Online learning and online convex optimization},
  journal = {Foundations and Trends in Machine Learning},
  volume  = {4},
  number  = {2},
  pages   = {107--194},
  year    = {2012}
}

@article{devroyewagner1979,
  author  = {Devroye, Luc and Wagner, Terry},
  title   = {Distribution-free performance bounds for potential function rules},
  journal = {IEEE Transactions on Information Theory},
  volume  = {25},
  number  = {5},
  pages   = {601--604},
  year    = {1979}
}