ch-duality-approachability

15 Invariance, Amplification, and Approachability

Presentation quotients, convex completion, games, and consistency

The same universal decision mechanism may be presented by cumulative statistics, recursive gradients, proximal resolvents, a different set of generators, or a different clock refinement. Presentation invariance asks when these descriptions may be identified without erasing the assumptions that make the identification valid.

Definition 15.1 Decision presentation

A decision presentation is a tuple \(P=(\mathcal G,\mathcal R,F,\rho ,\Omega )\) consisting of generators, relations, a presented evidence diagram \(F\), a decision readout \(\rho \), and an observer \(\Omega \). Two presentations are equivalent on a registered environment class \(\mathcal U\) when there is a coherent equivalence between their realized diagrams that intertwines readouts and observers for every \(U\in \mathcal U\).

This is stronger than equality of one output sequence. It requires the comparison to remain natural over the environments on which later reuse is claimed. It is weaker than identity of implementations: memory use, conditioning, and numerical error may remain different and must stay in the audit record.

Corollary 15.2 Euclidean mirror descent as linearized FTRL

Let \(x_1=m\), let \(\eta {\gt}0\) be constant, and let \(g_t=\nabla \ell _t(x_t)\). On an unconstrained domain, constant-step Euclidean mirror descent

\[ x_{t+1}=x_t-\eta g_t \]

and initial-centered linearized FTRL

\[ \widehat x_{t+1} = \operatorname *{arg\, min}_x \left\{ \left\langle \sum _{s\le t}g_s,x\right\rangle +\frac{1}{2\eta }\lVert x-m\rVert ^2 \right\} \]

generate the same decision sequence.

Proof ▼

The FTRL first-order condition gives

\[ \widehat x_{t+1}=m-\eta \sum _{s\le t}g_s. \]

The mirror recursion gives the same expression by induction. The paths agree at \(t=1\); hence they reveal the same next gradient at every subsequent round, completing the induction.

Corollary 15.2 motivates a LINCS decision quotient: presentation differences may be removed when an equivalence theorem proves identical decision sections on the registered environment. The hypotheses and the internal derivations remain part of the audit record. This does not identify all computational realizations or extend the result to variable-step, constrained, nonsmooth, or stateful adaptive methods.