Corollary 13.11: a convex-smooth-bounded problem (β, B) with ℓ(0, z) ≤ 1 is learned by RLM with λ = ε/(3B²) once m ≥ 150βB²/ε²: E_S[L_D(A(S))] ≤ min_{w∈H} L_D(w) + ε

Corollary 13.11. Let $(H, Z, \ell)$ be a convex-smooth-bounded learning problem with parameters $\beta, B$. Assume in addition that $\ell(0, z) \le 1$ for all $z \in Z$. For any $\epsilon \in (0,1)$ let $m \ge \frac{150\beta B^2}{\epsilon^2}$ and set $\lambda = \epsilon/(3B^2)$. Then for every distribution $D$, $\mathbb{E}_S[L_D(A(S))] \le \min_{w \in H} L_D(w) + \epsilon$.

The book derives this from Corollary 13.10, whose stability constant $48\beta/(\lambda m)$ would need $m \ge 216\beta B^2/\epsilon^2$ in this chain. The printed $150$ is nonetheless correct, because the derivation of Corollary 13.7 is loose: with $a = \sqrt{\ell(A(S), z_i)}$, $b = \sqrt{\ell(A(S^{(i)}), z')}$ and $\lambda \ge 2\beta/m$ one has $\|A(S^{(i)}) - A(S)\| \le 2\sqrt{2\beta}(a+b)/(\lambda m)$, hence $\ell(A(S^{(i)}), z_i) - \ell(A(S), z_i) \le \frac{\beta}{\lambda m}(6a^2 + 8ab + 2b^2) \le \frac{10\beta}{\lambda m}(a^2 + b^2)$, a stability rate of $20\beta/(\lambda m)$ in place of $48\beta/(\lambda m)$. Then $\mathbb{E}[L_D(A(S))] \le \min(1, L_D(w) + \lambda\|w\|^2)(1 + 60\beta B^2/(\epsilon m)) \le L_D(w) + \epsilon/3 + 60\beta B^2/(\epsilon m)$, which is at most $L_D(w) + \epsilon$ once $m \ge 90\beta B^2/\epsilon^2$. Measurability: jointly measurable loss and measurable algorithm, with a nonnegative loss bounded at the origin so that all expectations exist (for the RLM rule the minimizer is unique, so measurability of the algorithm is automatic).