ora-0170

15.3 Boosting as free convex completion

Boosting is the first test of structural amplification: can a learner turn mechanisms that are only weakly useful in isolation into a composite object with a stronger warrant? The categorical contribution is not the observation that convex combinations exist. It is the separation of three maps that classical notation often compresses: free completion of the hypothesis class, online selection of generators, and feasibility repair of the resulting composite.

Let \(C\) be a context set, \(K\) a convex decision algebra, and \(H\subseteq K^C\) a class of weak hypotheses. The function object \(K^C\) carries convex structure pointwise. If \(i:H\hookrightarrow K^C\) is inclusion, define

\[ \overline i = \beta _{K^C}\circ D(i):D(H)\longrightarrow K^C. \]

Proposition 15.4 Free convex completion of a hypothesis class

The map \(\overline i\) is the unique convex-algebra morphism extending \(i\) from the free convex algebra \(D(H)\). Its image is the finite convex hull of \(H\). Moreover, evaluation at every context \(c\in C\) commutes with completion:

\[ \operatorname {ev}_c\circ \overline i = \beta _K\circ D(\operatorname {ev}_c\circ i). \]

Proof ▼

The free-algebra property of the finite-distribution monad gives the unique algebra morphism from \(D(H)\) extending any set map \(H\to K^C\). Its elements are finite probability-weighted families of hypotheses, so its image is their pointwise finite convex hull. Since the algebra structure on \(K^C\) is pointwise, evaluation preserves every finite convex combination, which proves the commuting equation.

This proposition categorifies the target class used by online boosting, but not yet the weak-to-strong algorithm. Hazan’s online construction [ Hazan , 2023 ] scales weak predictions outside \(K\), extends each loss to the ambient linear space, and projects the final prediction back to \(K\):

\[ \text{weak policies} \longrightarrow \text{ambient mixture} \longrightarrow \text{loss extension} \longrightarrow \text{feasible projection}. \]

The analytic loss-extension operator must not be called a Kan extension by analogy alone. The theoretical task is to determine whether it has an appropriate universal or order-lax extension property, prove that feasibility repair preserves the admitted comparison, and show that the weak-learning warrant composes into a strong guarantee over \(\operatorname {im}(\overline i)\). In UODL, successful boosting should create a reusable composite object, not merely reduce the loss of one ensemble.