Theorem 12.5 — four surrogate losses dominate constrained regret

Let $V\subseteq W$ with $V$ nonempty, closed, and convex. On each of rounds $1,\ldots,T$, let $z_t\in W$, choose any $x_t\in\Pi_V(z_t)$, let $g_t$ be a subgradient of $\ell_t$ at $x_t$ for comparison with points of $V$, and choose $q_t\in\partial d_V(z_t)$. For each of the four surrogate losses $\widetilde\ell_t^{(k)}$ listed in the theorem, and every $u\in V$,

Thus any unconstrained learner's regret bound on one of these surrogate sequences transfers to its projected predictions on $V$.

Formalization Note The four choices are indexed $0,1,2,3$ in Lean, in the book's order. The learner is represented by its arbitrary prediction sequence $z_t$; the inequality is pathwise. The loss subgradient condition is relative to $V$, and $T\ge1$ makes the book's one-based horizon explicit.

Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.