# Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees

arXiv: https://arxiv.org/abs/2606.29331 · HTML: https://mlsanity.com/paper/2606.29331/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 28 Jun 2026.

## Builds on (most cited first, 10 of 10)

- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Discovering Symbolic Models from Deep Learning with Inductive Biases](https://mlsanity.com/paper/2006.11287/) (2020)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Contemporary Symbolic Regression Methods and their Relative Performance](https://mlsanity.com/paper/2107.14351/) (2021)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [Interpretable Scientific Discovery with Symbolic Regression: A Review](https://mlsanity.com/paper/2211.10873/) (2022)
- [A chain rule for the expected suprema of Gaussian processes](https://mlsanity.com/paper/1411.2635/) (2014)
- [Local Rademacher Complexity Bounds based on Covering Numbers](https://mlsanity.com/paper/1510.01463/) (2015)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)

## Abstract (arXiv)

Scientific discovery via symbolic regression is often viewed as statistically and computationally intractable because the hypothesis space of expressions grows combinatorially with depth. This paper revisits the statistical side through the lens of PAC learning, focusing on compositional function trees built from a finite vocabulary of smooth operators (e.g., +,×,sin,exp and affine maps). We prove that the relevant generalization quantity, Rademacher complexity, hence the excess risk, does not necessarily blow up exponentially with the number of distinct symbolic structures, but is controlled by (i) the depth d and (ii) the Lipschitz constants of the base operators along the composed computation graph. Concretely, under mild Lipschitz conditions on operators and bounded affine leaves, a finite-union bound over a vocabulary of size K=|Hbase| together with Maurer-type vector contraction yields mathfrakRn(Hcompd) ≤ (Kb√2L)d-1mathfrakRn(Hcomp1) with arity bound b; corresponding high-probability risk bounds scale as O(Ld/√n) when K,b=O(1) and mathfrakRn(Hcomp1)=O(n-1/2). We complement the theory with a modular codebase that trains differentiable operator trees (not MLPs) on synthetic "physics-like" targets of controlled depth and shows that the empirical generalization gap correlates positively with the predicted complexity term (widehatLd)/√n.