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

• URL: http://arxiv.org/abs/2606.29331v1
• Date: Sun, 28 Jun 2026 10:59:01 GMT
• Title: Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees
• Abstract summary: This paper revisits the statistical side through the lens of PAC learning.<n>We focus on compositional function trees built from a finite vocabulary of smooth operators.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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,\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=|\mathcal{H}_{\mathrm{base}}|$ together with Maurer-type vector contraction yields $\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{d}) \leq (Kb\sqrt{2}L)^{d-1}\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})$ with arity bound $b$; corresponding high-probability risk bounds scale as $\mathcal{O}(L^{d}/\sqrt{n})$ when $K,b=O(1)$ and $\mathfrak{R}_n(\mathcal{H}_{\mathrm{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 $(\widehat{L}^{d})/\sqrt{n}$.

Related papers

• Quantitative Sobolev Approximation Bounds for Neural Operators with Empirical Validation on Burgers Equation [0.0]
  We develop a functional-analytic framework for operator learning in Sobolev spaces and connect it to the numerical behavior of Fourier Neural Operators (FNOs) on a prototypical PDE.<n>Across a sweep of model sizes, we obtain test $H1$-errors down to $mathcalO(10-7)$ and relative errors of order $10-3$, with predictions accurately matching both solutions and spatial derivatives.
  arXiv  Detail & Related papers  (2026-05-04T22:15:21Z)
• A Hierarchy of Entanglement Cones via Rank-Constrained $C^*$-Convex Hulls [0.0]
  This paper investigates the geometry of the coneparable ($mathscrPtrivial_+$) and the separable Transpose (PPT) conjecture.
  arXiv  Detail & Related papers  (2025-12-05T09:34:05Z)
• The Space Complexity of Approximating Logistic Loss [11.338399194998933]
  We prove a general $tildeOmega(dcdot mu_mathbfy(mathbfX))$ space lower bound when $epsilon$ is constant.<n>We also refute a prior conjecture that $mu_mathbfy(mathbfX)$ is hard to compute.
  arXiv  Detail & Related papers  (2024-12-03T18:11:37Z)
• A Theory of Interpretable Approximations [61.90216959710842]
  We study the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $mathcalH$. For any given pair of $mathcalH$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $mathcalH$ with arbitrary accuracy. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-
  arXiv  Detail & Related papers  (2024-06-15T06:43:45Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$<n>We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  Ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  arXiv  Detail & Related papers  (2023-02-27T16:34:21Z)
• Randomised Composition and Small-Bias Minimax [0.9252523881586053]
  We prove two results about query complexity $mathrmR(f)$. First, we introduce a "linearised" complexity measure $mathrmLR$ and show that it satisfies an inner-conflict composition theorem: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$ and $g$, and moreover, $mathrmLR$ is the largest possible measure with this property.
  arXiv  Detail & Related papers  (2022-08-26T23:32:19Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.