aiqbench analysis
This research establishes a rigorous learning-theoretic framework for symbolic regression using genetic programming, decomposing generalization error into structural complexity and parameter sensitivity components. By linking practical constraints like tree depth limits to explicit terms in the generalization bound, it offers theoretical justification for common design choices such as parsimony pressure and stability operators. The work advances machine learning theory by bridging empirical success with formal guarantees on hypothesis class growth within evolutionary computing paradigms.
On the Generalization Bounds of Symbolic Regression with Genetic Programming
arXiv:2604.17402v2 Announce Type: replace Abstract: Symbolic regression (SR) with genetic programming (GP) aims to discover interpretable mathematical expressions directly from data. Despite its strong empirical success, the theoretical understanding of why GP-based SR generalizes beyond the training data remains limited. In this work, we provide a learning-theoretic analysis of SR models represented as expression trees. We derive a generalization bound for GP-style SR under constraints on tree size, depth, and learnable constants. Our result decomposes the generalization gap into two interpretable components: a structure-selection term, reflecting the combinatorial complexity of choosing an expression-tree structure, and a constant-fitting term, capturing the complexity of optimizing numerical constants within a fixed structure. This decomposition provides a theoretical perspective on several widely used practices in GP, including parsimony pressure, depth limits, numerically stable operators, and interval arithmetic. In particular, our analysis shows how structural restrictions reduce hypothesis-class growth while stability mechanisms control the sensitivity of predictions to parameter perturbations. By linking these practical design choices to explicit complexity terms in the generalization bound, our work offers a principled explanation for commonly observed empirical behaviors in GP-based SR and contributes towards a more rigorous understanding of its generalization properties.
Abstract:Symbolic regression (SR) with genetic programming (GP) aims to discover interpretable mathematical expressions directly from data. Despite its strong empirical success, the theoretical understanding of why GP-based SR generalizes beyond the training data remains limited. In this work, we provide a learning-theoretic analysis of SR models represented as expression trees. We derive a generalization bound for GP-style SR under constraints on tree size, depth, and learnable constants. Our result decomposes the generalization gap into two interpretable components: a structure-selection term, reflecting the combinatorial complexity of choosing an expression-tree structure, and a constant-fitting term, capturing the complexity of optimizing numerical constants within a fixed structure. This decomposition provides a theoretical perspective on several widely used practices in GP, including parsimony pressure, depth limits, numerically stable operators, and interval arithmetic. In particular, our analysis shows how structural restrictions reduce hypothesis-class growth while stability mechanisms control the sensitivity of predictions to parameter perturbations. By linking these practical design choices to explicit complexity terms in the generalization bound, our work offers a principled explanation for commonly observed empirical behaviors in GP-based SR and contributes towards a more rigorous understanding of its generalization properties.
Machine Learning (cs.LG); Neural and Evolutionary Computing (cs.NE)
arXiv:2604.17402 [cs.LG]
(or arXiv:2604.17402v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2604.17402 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 286 words
Related coverage
Neural Symbollic Regression Using Deep Learning and Sparse Modelling
arXiv · Sep 9, 2026
InsightSR: Refining Symbolic Regression Search Spaces via Parallel Semantic and Structural LLM Guidance
arXiv · Aug 27, 2026
FunctionEvolve: Structure-Guided Symbolic Regression with LLMs
arXiv · Jun 9, 2026
Minimalist Genetic Programming
arXiv · Jun 16, 2026