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

Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın · 2026

Read Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees by Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29331.txt.

Description

Kocabay and two colleagues ask how much data symbolic regression needs to discover a true formula. Symbolic regression searches expressions built from operators like sine and exponential, and the space of possible formulas grows combinatorially with depth, which makes discovery look hopeless. Their paper revisits that worry through PAC learning, the theory of learning from samples with guaranteed error bounds.

For compositional function trees built from a finite set of smooth operators, they prove the key quantity does not blow up with the number of distinct structures. It is controlled instead by tree depth and by the operators' Lipschitz constants, measures of how much each operator can stretch its input. The matching risk bound grows with depth in a precise way. A companion codebase trains such operator trees on synthetic physics-like targets, and the observed generalisation gap tracks the predicted complexity term.

Catalog record

CREATORŞuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.29331

Browse the full library · About the Tower of Babel