Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees
Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın
cs.LG, stat.ML
Submitted: 2026-06-28
Comments: Accepted to the 2nd Workshop on Compositional Learning: Safety, Interpretability, and Agents at ICML 2026. To be presented in Seoul, South Korea, July 11, 2026
Code: https://github.com/suayptalha/scientific-pac
License: http://creativecommons.org/licenses/by/4.0/
The gist: Scientific discovery via symbolic regression is often viewed as statistically and computationally intractable because the hypothesis space of expressions grows combinatorially with depth.
Terminology
Abstract
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., +, times,, 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= H base together with Maurer-type vector contraction yields R n(H comp d) at most (Kb sqrt 2 L) d-1 R n(H comp 1) with arity bound b; corresponding high-probability risk bounds scale as O(L d/sqrt n) when K,b=O(1) and R n(H comp 1)=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 (d)/sqrt n.
Sources
- User-friendly introduction to PAC-Bayes bounds
- Spectrally-normalized margin bounds for neural networks
- Interpretable Machine Learning for Science with PySR and SymbolicRegression.jl
- Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients
- Contemporary Symbolic Regression Methods and their Relative Performance
- On Rademacher Complexity-based Generalization Bounds for Deep Learning
- Structured Sparsity and Generalization
- AI Feynman: a Physics-Inspired Method for Symbolic Regression
- Exploring Generalization in Deep Learning
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks