sec-pacc-evolvability
8.8 PACC evolvability
PAC learning permits a learner to inspect a labeled sample and replace its current hypothesis by any hypothesis its algorithm can construct. Valiant’s theory of evolvability imposes a different discipline [ Valiant , 2009 ] . A representation changes only through a bounded neighborhood of mutations, and selection sees empirical aggregate performance rather than the identities of the examples responsible for that performance. Learning is therefore a path of locally selected variations, not a sequence of globally recomputed empirical-risk minimizers.
The categorical abstraction must constrain both the states and the steps of that path. Let \(\mathbf R\) be a category of admissible representations inside the PACC hypothesis class \(\mathbf H\). Its objects are categorical world models, and a morphism, span, or declared higher cell records an admissible mutation together with the comparison data needed to audit what it preserves. For each representation \(\mathcal C\) and accuracy scale \(\epsilon \), a finite neighborhood \(\mathsf N_\epsilon (\mathcal C)\) contains the candidate mutations that may be tested in one generation. Define aggregate performance by
A categorical mutator may estimate this quantity on fresh sampled probes for the current representation and its neighbors. It receives those empirical scores, up to a declared tolerance, but not an example-indexed prescription of how to alter the hypothesis.
A family of PACC declarations is PACC evolvable relative to a representation category \(\mathbf R\) when there are polynomially bounded neighborhood, sampling, tolerance, and selection rules such that, for every admitted target \(\mathcal C_\star \), every initial representation \(\mathcal C_0\), and every \(0{\lt}\epsilon ,\delta {\lt}1\), the induced sequence
uses at each step only aggregate empirical categorical performance to select \(\mathcal C_{t+1}\in \mathsf N_\epsilon (\mathcal C_t)\), remains inside the declared hypothesis doctrine, and satisfies
after a number of generations and probes polynomial in the declared size parameters, \(1/\epsilon \), and \(\log (1/\delta )\). The neighborhood and selection rules must respect the answer equivalences used by the PACC risk; equivalent re-presentations may not acquire different fitness merely from their syntax.
Ordinary evolvability is recovered when the objects of \(\mathbf R\) are an ordinary representation class, its admissible morphisms encode the mutation graph, the probes are discrete input points, and performance is agreement with an ideal function. PACC evolvability adds three obligations. Mutations must remain well typed and categorically valid. Their scores must be invariant under the declared equivalences. Finally, the mutation arrows expose which settled objects, composites, universal witnesses, or higher coherences survive a statistically favored change. Thus two neighbors can have indistinguishable predictive fitness while differing sharply in their capacity for persistent reuse.
Within a fixed fiber of the ORACLE hypothesis fibration, this is a model of evolutionary assimilation: local variants compete under one doctrine. Accommodation is more demanding. A mutation that changes doctrine crosses fibers, so its old and new performance values are comparable only after probes and answers have been transported along declared cartesian, cocartesian, or profunctorial structure. Without that comparison, a doctrine shift is not a beneficial mutation; it is a change of measurement scale. PACC evolvability therefore turns a biological restriction into an ORACLE design question: which local, compositional variations permit statistically reliable progress without granting the learner direct access to the individual experiences that selected them?