ora-0105

8.2 The PACC declaration

Fix a target categorical world \(\mathcal C_\star \) in a hypothesis category \(\mathbf H\), and a doctrine \(\mathcal Q\) of admissible probes. A probe \(q\in \mathcal Q\) has an answer object \(q(\mathcal C)\) for every hypothesis on which it is defined. Examples include:

  • [leftmargin=*]

  • the domain, codomain, identity, or composite of named arrows;

  • whether proposed generators factor an observed composite and whether a declared relation is respected by the model;

  • whether a displayed diagram commutes or a specified horn has a filler;

  • the category or space of cones realizing a universal property;

  • a representable, predictive, causal, decision, or tangent-sensitive response admitted by the doctrine.

Each probe carries a bounded discrepancy

\[ d_q:q(\mathcal C_\star )\times q(\mathcal C)\longrightarrow [0,1]. \]

The notation suppresses the comparison span needed when the answers do not literally inhabit the same set. We require \(d_q\) to vanish on the declared answer equivalences and to be invariant under equivalent re-presentations of the target and hypothesis. Literal equality of chosen terminal objects, for example, is the wrong test; equivalence of their cone categories is the relevant one.

Definition 8.1 Categorical probe risk

For a distribution \(P\) on \(\mathcal Q\), the risk of a hypothesis \(\mathcal C\) relative to \(\mathcal C_\star \) is

\begin{equation} \mathsf{Err}_{P,\mathcal Q}(\mathcal C,\mathcal C_\star ) =\mathbb E_{q\sim P} \bigl[d_q\bigl(q(\mathcal C_\star ),q(\mathcal C)\bigr)\bigr]. \end{equation}
8.3

Two hypotheses are \(\mathcal Q\)-equivalent when every admissible probe assigns equivalent answers to them.

Definition 8.2 PACC declaration and learner

A PACC declaration is a tuple

\[ \mathbb A_{\mathrm{PACC}} =(\mathbf H,\mathcal Q,P,d,\epsilon ,\delta ), \qquad 0{\lt}\epsilon ,\delta {\lt}1, \]

together with a presentation protocol that produces a typed transcript \(S=((q_i,q_i(\mathcal C_\star )))_{i=1}^m\). A UOCL algorithm \(A\) is \((\epsilon ,\delta )\)-PACC after \(m\) probes when

\begin{equation} \Pr _{S\sim P^m} \left\{ \mathsf{Err}_{P,\mathcal Q} \bigl(A(S),\mathcal C_\star \bigr)\leq \epsilon \right\} \geq 1-\delta . \end{equation}
8.4

It PACC-learns a family of declarations when a sample bound \(m(\epsilon ,\delta )\) makes this statement hold uniformly over their targets and admitted probe distributions.

The i.i.d. protocol is the closest analogue of classical PAC and supplies the baseline theory below. It is not the full online theory. Active probes, dependent categorical fragments, and world-changing interventions require conditional or martingale variants of the guarantee.