1. Assessment and scope
The reviewed literature connects categorical semantics with PAC learning through composition, invariance, and structural transfer. A quantitative learning theorem also needs observations, probability, loss, complexity, and a learner.
This selective survey covers primary sources checked through 20 October 2026 UTC. Reported results, elementary consequences proved here, and a proposed synthesis are distinguished. It does not claim exhaustive coverage or independent verification of every cited proof.
Three uses of “higher” require separation. A 2-category has morphisms between morphisms. An infinity-category retains coherent higher homotopies. Higher arity PAC learning studies relational observations and structured sampling; its arity does not make it higher category theory. An ordinary Grothendieck topos is not, merely by that name, an infinity-topos of space-valued sheaves.
Recent semantic results include Pugh et al. [1] and Melodia's revision of 9 October 2026 [2]; their statistical reach is discussed below.
2. The statistical statement that semantics must preserve
Let $Z=X\times Y$ be a measurable example space, $H$ a measurable hypothesis space, and $\ell:H\times Z\to[0,1]$ a jointly measurable loss. For a probability law $D$ on $Z$, write
$$ R_D(h)=\mathbb E_{z\sim D}\ell(h,z),\qquad \widehat R_S(h)=\frac1m\sum_{i=1}^m\ell(h,z_i). $$
A possibly randomized learner is a Markov kernel $A_m:Z^m\rightsquigarrow H$. An agnostic PAC guarantee has the quantifier order
$$ \forall\varepsilon,\delta\in(0,1)\ \exists m_0\ \forall D\ \forall m\ge m_0: \Pr_{S\sim D^m,\ h\sim A_m(S)} \left[R_D(h)\le\inf_{g\in H}R_D(g)+\varepsilon\right]\ge1-\delta. $$
Statistical learnability does not assert computability or polynomial runtime. The realizable binary case assumes a target in $H$ with zero risk; agnostic learning does not. For ordinary binary classes, finite VC dimension characterizes distribution-free PAC learnability under the usual measurability conventions [3,4]. This does not extend unchanged to every multiclass, partial, relational, or computational model.
For finite $H$, a directly useful benchmark is
$$ \Pr\!\left[\sup_{h\in H}|R_D(h)-\widehat R_S(h)|>t\right] \le 2|H|e^{-2mt^2}. $$
Indeed, apply Hoeffding to each bounded loss and take a union bound. On the complementary event, an empirical risk minimizer $\widehat h$ satisfies $R_D(\widehat h)\le\min_hR_D(h)+2t$. Thus
$$ m\ge\frac{2}{\varepsilon^2}\log\frac{2|H|}{\delta} $$
is sufficient in this finite agnostic setting. If the binary class is realizable, a consistent learner instead has failure probability at most $|H|e^{-m\varepsilon}$, giving the sufficient bound $m\ge(\log|H|+\log(1/\delta))/\varepsilon$. These are elementary finite-class bounds, not claims of sharp constants for every PAC model.
3. Recent developments and their precise reach
| Work and verified date | Mathematical contribution | Relation to PAC learning | |:--|:--|:--| | Pugh et al. [1], 2025; TMLR publication record dated 10 November 2025 | An error-minimization problem can be represented in a constructed 2-category so that its global minimizers are left Kan extensions. | A representation theorem for optimization; no automatic generalization bound. | | Chernikov and Towsner [5], v2, 15 October 2025 | Higher arity VC dimension, a packing theorem, and proper $\mathrm{PAC}_k$ learnability in the paper's product-measure and fiber-observation model. | A genuine statistical characterization in a specified higher arity model. | | Kattermann and Krapp [4], COLT 2026 | Computable PAC learning related to recursively enumerable representable classes and effective VC dimension. | Shows why semantic existence and finite ordinary VC dimension do not alone produce an executable learner. | | Melodia [2], v4, 9 October 2026 | Kan extensions of representation invariants, discrepancy, persistent-homology stability, and exact finite-sample structural results. | Relates task changes to measurable structural discrepancies; does not identify discrepancy with predictive risk. | | Maeda, Seiller, and Oseki [6], public 2026 manuscript | Structural and lexical identifications induce Kan extensions diagnosing admissibility in COGS. | Studies what a corpus licenses structurally, without training a predictor or establishing a PAC rate. |
Chernikov and Towsner's Corollary 6.6 identifies finite $\mathrm{VC}_k$ dimension, the appropriate packing property, and $\mathrm{PAC}_k$ learnability; Theorem 6.5 obtains a proper learner. Their Definition 4.3 allows restrictions to coordinate fibers through sampled tuples. Replacing that access with an ordinary list of independently labeled tuples changes the learning problem. Coregliano and Malliaris [7] separately develop high arity learning through induced substructures and exchangeable distributions. These models should not be conflated.
Melodia's latest abstract explicitly reports that discrepancy across pretrained models does not track linear-probe accuracy [2]. This is a useful limit: a rigorous structural invariant can detect specified changes while remaining insufficient to predict downstream statistical performance. Maeda et al. similarly separate corpus-level admissibility from model accuracy [6].
4. What the categorical frameworks contribute
4.1 Compositional learners, lenses, and architecture
Fong, Spivak, and Tuyeras organize supervised learning compositionally [8]. Cruttwell and collaborators use parametrized maps, lenses, and reverse derivative categories to describe gradient-based learning and several optimizer families [9]. A parametrized implementation has the form
$$ f:P\times X\longrightarrow Y; $$
the parameter space and its update rules are part of the structure. This exposes how a composite model receives and propagates training information. It does not imply that arbitrary optimizers converge, have equivalent computational behavior, or generalize equally.
Gavranovic and collaborators' ICML 2024 position paper formulates architecture constraints and implementations using monads in a 2-category of parametrized maps [10]. This offers a language for specifying a hypothesis family. A PAC analysis must then study the induced family of measurable predictors or loss functions: an algebraic presentation is not itself a complexity bound.
4.2 Kan extensions and optimization
For $i:C\to D$ and $F:C\to E$, a left Kan extension has a unit $F\Rightarrow(\operatorname{Lan}_iF)i$ and, when it exists, the universal property
$$ \operatorname{Nat}(\operatorname{Lan}_iF,G) \cong\operatorname{Nat}(F,Gi). $$
Pugh et al.'s Theorem 4.1 constructs the surrounding 2-category from the error-minimization problem [1]. The construction uses a selection of existing minimizers. It therefore supplies neither a general algorithm for finding them nor an existence theorem when the infimum is unattained. Its error comparison uses lax 2-functorial structure. This is genuinely 2-categorical, but it is not by itself a full infinity-topos semantics or a proof of uniform convergence.
4.3 Categorical probability and statistical information
Markov categories describe stochastic channels compositionally. Fritz's synthetic treatment includes conditional independence and sufficient statistics [11]. Fritz, Gonda, Perrone, and Rischel prove a categorical Blackwell-Sherman-Stein theorem under their hypotheses, comparing statistical experiments by garbling [12]. Perrone equips categorical probability with quantitative divergence and information-theoretic structure [13].
This is a strong foundation for the stochastic part of PAC semantics: sampling, randomization, postprocessing, and information loss. Nevertheless, bare Markov-category axioms do not contain Hoeffding's inequality, measurable optimization, or finite VC dimension. To obtain a numerical PAC theorem one must supply a suitable probabilistic realization and the relevant concentration and complexity assumptions.
5. PAC-Bayes as a quantitative interface
For independent examples, bounded loss, and a prior $\pi$ on $H$ chosen independently of the sample, a standard PAC-Bayes bound states that, with probability at least $1-\delta$, simultaneously for all posterior laws $\rho$,
$$ \operatorname{kl}\!\left(\mathbb E_{\rho}\widehat R_S \,\middle\|\,\mathbb E_{\rho}R_D\right) \le\frac{\mathrm{KL}(\rho\|\pi)+\log(2\sqrt m/\delta)}{m}. $$
Here $m\ge2$, logarithms are natural, and $\operatorname{kl}(a\|b)=a\log(a/b)+(1-a)\log((1-a)/(1-b))$, with the usual endpoint conventions. See Maurer [14] and Alquier, Theorem 3.2.2 [15]. The posterior can depend on the sample and need not be a Bayesian posterior. A sample-dependent prior needs a separate justification.
A categorical interpretation uses a measurable semantics map $q:H\to\overline H$. If the loss factors through $q$, both empirical and population risks depend only on the pushforward posterior. Data processing gives
$$ \mathrm{KL}(q_*\rho\|q_*\pi)\le\mathrm{KL}(\rho\|\pi). $$
Applying the ordinary PAC-Bayes theorem directly on $\overline H$ can therefore remove a penalty for distinctions invisible to the chosen loss. This is an elementary consequence of loss factorization and data processing; it is not a new higher categorical concentration theorem. The quotient must be measurable. A smaller KL term also does not prove that a representative can be computed or efficiently sampled.
6. A precise higher categorical synthesis
The following construction is a proposed organizing framework, with two elementary consequences proved explicitly. Let $\mathcal H$ be a small infinity-category of structured hypotheses and $W$ a chosen collection of morphisms designated as semantic weak equivalences. Consider its localized core
$$ \mathcal M=\bigl(\mathcal H[W^{-1}]\bigr)^{\simeq}, \qquad H_0=\pi_0(\mathcal M). $$
The core retains objects and invertible higher comparisons; $H_0$ records their equivalence classes. Equip $H_0$ with a sigma-algebra and supply jointly measurable observations $\ell:H_0\times Z\to[0,1]$. A learner is now a measurable kernel $Z^m\rightsquigarrow H_0$, or a kernel into a measurable space of presentations whose loss descends to $H_0$. None of these measurable structures is supplied automatically by localization.
Proposition 1 (transport of a PAC guarantee). Let $q:H\to K$ be a measurable surjection of ordinary hypothesis spaces. Suppose
$$ \ell_H(h,z)=\ell_K(q(h),z) $$
for all $h,z$, and define $A^K_m(S)=q_*A^H_m(S)$. Then the excess-risk random variables of the two learners have the same law. In particular, every agnostic PAC bound for $A^H$ transfers with the same $m,\varepsilon,\delta$.
*Proof.* Loss factorization gives $R^H_D=R^K_Dq$. Surjectivity gives $\inf_HR^H_D=\inf_KR^K_D$. The output law for $A^K$ is exactly the pushforward law, so the probabilities of corresponding excess-risk events agree. $\square$
The converse needs a measurable lift of learner outputs; computable or efficient transport needs corresponding effective lifts. An equivalence of higher categorical presentations that preserves the complete sampling-and-loss experiment can be analyzed this way. An abstract equivalence of categories, without those data, is insufficient.
Proposition 2 (finite observational quotient). Suppose all losses factor through a fixed finite discrete measurable quotient $Q$ of cardinality $N\ge1$. An empirical minimizer over $Q$, with any chosen representatives, satisfies
$$ R_D(\widehat q)\le\min_{q\in Q}R_D(q) +\sqrt{\frac{2\log(2N/\delta)}{m}} $$
with probability at least $1-\delta$.
*Proof.* Apply the finite-class bound of Section 2 to the $N$ quotient losses. A minimizer exists because $Q$ is finite. The same empirical and population values hold for its representative. $\square$
This is a concrete statistical payoff of semantic identification: the bound counts distinct observable loss profiles. It does not count objects, morphisms, or homotopy groups without a theorem relating those quantities to the loss class. The quotient and observations must be fixed independently of the sample for this direct argument.
An invariant scalar loss on a space $\mathcal M$ factors through $\pi_0(\mathcal M)$ because $[0,1]$, viewed here as a set, is 0-truncated. Thus scalar risk alone cannot recover automorphism groups or higher coherence. Learning those structures requires observations sensitive to them and an identification theorem for that richer experiment. Univalence identifies equivalent structures within an appropriate type theory; it does not identify arbitrary statistically similar predictors.
7. Topoi, descent, and contextual learning
Belfiore and Bennequin use topoi, stacks, and homotopical structures to describe neural networks, invariance, and semantic information [16]. Their framework motivates contextual descriptions of learned systems. Its proposed connection between invariance and generalization should be separated from a proved, quantified PAC theorem.
For a genuine infinity-topos $\mathcal E$, Lurie's descent theory [17] supplies a precise way to compare local objects. If $U\to T$ is an effective epimorphism with Cech nerve $U_\bullet$, there is an equivalence
$$ \mathcal E_{/T}\simeq \lim_{[n]\in\Delta}\mathcal E_{/U_n}. $$
Applying $\operatorname{Fun}(K,-)$ transports this equivalence to $K$-shaped diagrams. Additional loss or probability structures must themselves be specified compatibly. Descent requires objects, overlap equivalences, and all coherence data. The existence of some local learner on each patch does not provide those data.
There is a separate elementary statistical gluing argument. Suppose $D=\sum_{i=1}^r w_iD_i$, $w_i\ge0$, $\sum_iw_i=1$, and a *single* learned hypothesis $h$ has local risks $R_i(h)\le b_i$ on events of probability at least $1-\delta_i$, all under the same training experiment. Then
$$ \Pr\left[R_D(h)\le\sum_iw_ib_i\right]\ge1-\sum_i\delta_i. $$
This follows from linearity of expectation and a union bound; independence between the local success events is unnecessary. Distinct local hypotheses first need a valid global construction. If the $b_i$ are local optima plus errors, the weighted local optima can be a stronger benchmark than any globally compatible model can attain. Sheaf descent and statistical confidence budgeting are therefore complementary obligations.
8. What remains open in this synthesis
These reviewed sources leave a general PAC characterization of infinity-categorical hypotheses open. The following questions concern this synthesis:
1. Observable complexity. Relate a specified family of categorical queries to VC dimension, pseudodimension, covering numbers, or another statistical complexity. Raw numbers of higher cells need not control any of these. 2. Quantitative coherence. Bound global predictive error by local error, overlap disagreement, and composition depth under explicit Lipschitz or stability assumptions. Pairwise approximate agreement alone is not homotopy-coherent descent. 3. Effective realization. Turn categorical minimizer existence into computable learners with effective sample bounds. The 2026 computable-PAC results [4] make this distinction mathematically substantive. 4. Structured sampling. Connect categorical relational semantics to a precise exchangeable or fiber-observation model [5,7], proving the required concentration statement rather than treating correlated tuples as independent examples. 5. Identification beyond scalar risk. Determine which experiments can distinguish equivalence classes, automorphisms, and higher coherence, and whether those distinctions matter to the downstream task.
The present mathematical interface is thus explicit: categorical structure specifies the models and comparisons; measurable observations define the statistical experiment; established PAC tools bound its loss class. A new higher categorical PAC theorem must prove a nontrivial connection between those layers.
References
[1] Matthew Pugh, Nick Harris, Corina Cirstea, and Jo Grundy. *Learning Is a Kan Extension*. 2025. Publication record.
[2] Luciano Melodia. *Learning Transfers: Kan Extensions of Topological Invariants of Learned Representations*. 2026, v4, 9 October. Primary record.
[3] Shai Shalev-Shwartz and Shai Ben-David. *Understanding Machine Learning: From Theory to Algorithms*. 2014. Authors' book page.
[4] David Kattermann and Lothar Sebastian Krapp. *Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning*. COLT 2026. Proceedings and paper.
[5] Artem Chernikov and Henry Towsner. *Higher-arity PAC learning, VC dimension and packing lemma*. 2025, v2, 15 October. Primary record.
[6] Akihiro Maeda, Thomas Seiller, and Yohei Oseki. *Compositional Generalization via Structural Identification in a Category-Theoretic Framework*. 2026 manuscript. Author's research page and abstract.
[7] Leonardo N. Coregliano and Maryanthe Malliaris. *High-arity PAC learning via exchangeability*. 2024, v3. Primary preprint.
[8] Brendan Fong, David I. Spivak, and Remy Tuyeras. *Backprop as Functor: A compositional perspective on supervised learning*. 2017; revised 2019. Primary record.
[9] G. S. H. Cruttwell, Bruno Gavranovic, Neil Ghani, Paul Wilson, and Fabio Zanasi. *Categorical Foundations of Gradient-Based Learning*. 2021. Primary preprint.
[10] Bruno Gavranovic, Paul Lessard, Andrew Joseph Dudzik, Tamara von Glehn, Joao Guilherme Madeira Araujo, and Petar Velickovic. *Position: Categorical Deep Learning is an Algebraic Theory of All Architectures*. ICML 2024. Proceedings and paper.
[11] Tobias Fritz. *A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics*. 2020. Primary preprint and publication metadata.
[12] Tobias Fritz, Tomas Gonda, Paolo Perrone, and Eigil Fjeldgren Rischel. *Representable Markov Categories and Comparison of Statistical Experiments in Categorical Probability*. 2023. Primary preprint.
[13] Paolo Perrone. *Markov Categories and Entropy*. 2024. Primary preprint.
[14] Andreas Maurer. *A Note on the PAC Bayesian Theorem*. 2004. Primary preprint.
[15] Pierre Alquier. *User-friendly Introduction to PAC-Bayes Bounds*. 2024; revised 2025. Primary preprint.
[16] Jean-Claude Belfiore and Daniel Bennequin. *Topos and Stacks of Deep Neural Networks*. 2022, v3. Primary preprint.
[17] Jacob Lurie. *Higher Topos Theory*. 2009; maintained manuscript. Author's full text.
[18] Sridhar Mahadevan. *A Categorical Research Program for AI: Shared Glossary*. Author-hosted glossary, accessed 20 October 2026. PACC learning and related terminology.
*Preparation note.* Prepared with AI assistance. Some broad descriptions use primary-source abstracts. The attached full PDF and editable source include expanded bibliographic and access notes. The derivations here are not proof-assistant certified.