ora-0131

10.3 The categorical OCO declaration

Let \(D\) denote the finite-distribution monad on sets:

\[ D(X) = \left\{ p:X\to \mathbb {R}_{\geq 0} \; \middle |\; p\text{ has finite support and }\sum _{x\in X}p(x)=1 \right\} . \]

A convex set is equivalently a \(D\)-algebra \(\beta _K:D(K)\to K\); the associated PROP presentation encodes the same convex-combination operations [ Haderi et al. , 2024 ] . Ordinary morphisms of convex algebras preserve these operations with equality and are therefore affine. Convex losses require an order-enriched weakening.

Definition 10.1 Categorical OCO declaration

A finite-horizon categorical OCO declaration consists of:

  1. a convex decision algebra \((K,\beta _K)\), together with a declared metric realization when boundedness, closure, or convergence is used;

  2. an ordered convex value algebra \((V,\beta _V,\leq )\);

  3. a registered loss family \(\ell _t:K\to V\) satisfying the order-lax algebra law

    \begin{equation} \ell _t\circ \beta _K \; \leq \; \beta _V\circ D(\ell _t) \qquad \text{pointwise on }D(K); \end{equation}
    10.1

  4. decision rules \(A_t:(\ell _1,\ldots ,\ell _{t-1})\mapsto x_t\in K\);

  5. a comparator declaration, initially the constant decision sections \(u\in K\), against which cumulative performance is evaluated; and

  6. an admissible tangent assignment. In a finite-dimensional convex realization this is the tangent cone

    \[ T_K(x) = \overline{ \{ a(y-x)\mid a\geq 0,\ y\in K\} }. \]

The additive accumulation of the losses is a subsequent evidence operation; it is not the source of convexity in the declaration.

Proposition 10.2 Recovery of Euclidean OCO

Let \(K\subseteq \mathbb {R}^d\) be nonempty, bounded, closed, and convex, let \(\beta _K\) evaluate finite convex combinations, and take \(V=\mathbb {R}\) with its usual order and barycentric operations. Let the registered losses be bounded real-valued maps on \(K\). Then 10.1 holds exactly when each \(\ell _t\) is convex. Consequently, 10.1 recovers the standard OCO protocol

\[ x_t=A_t(\ell _1,\ldots ,\ell _{t-1})\in K, \qquad \ell _t:K\to \mathbb {R}, \]

with static regret against constant sections

\[ R_T = \sum _{t=1}^T\ell _t(x_t) - \inf _{u\in K}\sum _{t=1}^T\ell _t(u). \]
Proof ▼

For a finitely supported probability weight \(p\), 10.1 reads

\[ \ell _t\! \left(\sum _xp(x)x\right) \leq \sum _xp(x)\ell _t(x), \]

which is Jensen convexity. The remaining data are precisely the feasible decision, revealed convex loss, history-dependent learner, and fixed comparator class in the Euclidean OCO protocol [ Hazan , 2023 ] .

Remark 10.3 Two structures, not one

The convex algebra specifies feasible mixtures of decisions. The \(\mathbb {R}\)-linear enrichment used later specifies how revealed quadratic statistics accumulate. Keeping these declarations separate prevents the convexity of \(K\) from being confused with addition of losses.