arxiv: 2604.17402 · v1 · submitted 2026-04-19 · 💻 cs.LG · cs.NE

Recognition: unknown

On the Generalization Bounds of Symbolic Regression with Genetic Programming

Isao Ono, Masahiro Nomura, Ryoki Hamano

Authors on Pith no claims yet

Pith reviewed 2026-05-10 05:46 UTC · model grok-4.3

classification 💻 cs.LG cs.NE

keywords symbolic regressiongenetic programminggeneralization boundsexpression treesstructure selectionconstant fittinglearning theory

0 comments

The pith

Symbolic regression via genetic programming generalizes according to a bound that separates the complexity of selecting expression tree structures from the complexity of fitting constants within them.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives a generalization bound for symbolic regression performed by genetic programming on expression trees. It splits the gap between training and test error into one term that grows with the number of possible tree shapes and another that grows with how sensitively the predictions change when constants inside a fixed tree are perturbed. This split supplies a direct theoretical account of why common GP controls such as depth limits, size penalties, and stable operators tend to improve performance on unseen data. A reader cares because the bound turns those empirical heuristics into explicit, additive contributions to the overall complexity of the hypothesis class.

Core claim

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.

What carries the argument

A generalization bound on bounded expression trees that decomposes the generalization gap into a structure-selection term measuring combinatorial tree complexity and a constant-fitting term measuring prediction sensitivity to constant changes.

If this is right

Structural restrictions such as depth or size limits shrink the structure-selection term by reducing the number of admissible trees.
Numerically stable operators and interval arithmetic shrink the constant-fitting term by bounding the effect of small constant perturbations on predictions.
Parsimony pressure acts as an explicit penalty on the structure-selection complexity term.
The two-term split supplies a quantitative rationale for why these design choices improve generalization in GP-based symbolic regression.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The decomposition could be used to design GP variants that allocate search effort differently between structure enumeration and constant refinement.
Analogous two-term bounds may exist for other tree-structured symbolic models such as expression-based neural networks.
Direct numerical checks of the bound against measured gaps on standard SR benchmarks would show how loose or tight the theoretical estimates are.

Load-bearing premise

The GP search process can be modeled as selection within a fixed class of bounded-size expression trees to which standard statistical learning complexity measures apply directly.

What would settle it

An experiment in which imposing stricter tree-size or depth limits, or switching to numerically stable operators, fails to reduce the observed generalization gap on held-out data while other factors remain fixed.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The abstract sketches a decomposition of the generalization gap for bounded-tree GP symbolic regression into structure-selection and constant-fitting terms, but supplies no derivation or assumptions so the claim stays uncheckable.

read the letter

The core new piece is the explicit split of the bound into a combinatorial term for picking the expression tree shape and a separate term for tuning the constants inside a fixed shape. The authors then use that split to argue that common GP moves like depth limits, parsimony pressure, and interval arithmetic each tighten one of the two terms. That linkage is the main contribution on offer; it tries to give a learning-theoretic story for practices that have mostly been justified empirically so far.

Referee Report

1 major / 0 minor

Summary. The paper claims to derive a generalization bound for GP-style symbolic regression on expression trees with constraints on tree size, depth, and learnable constants. The bound decomposes the generalization gap into a structure-selection term (combinatorial complexity of choosing an expression-tree structure) and a constant-fitting term (complexity of optimizing numerical constants within a fixed structure), and links this decomposition to practices such as parsimony pressure, depth limits, and numerically stable operators.

Significance. If the derivation holds and the modeling assumptions are appropriate, the result would offer a principled learning-theoretic explanation for several empirical design choices in genetic programming for symbolic regression, connecting them directly to explicit complexity terms in the generalization bound and advancing theoretical understanding in this area.

major comments (1)

[Abstract] Abstract: The central claim is that a generalization bound is derived and decomposed into interpretable structure-selection and constant-fitting terms. However, the manuscript (which consists only of the abstract) supplies no proof sketch, explicit assumptions, derivation steps, hypothesis-class definition, or application of specific complexity measures. This makes it impossible to verify whether the mathematics supports the stated decomposition or whether standard learning-theoretic tools apply to the class of bounded expression trees.

Simulated Author's Rebuttal

1 responses · 1 unresolved

We thank the referee for their review. We address the major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: The central claim is that a generalization bound is derived and decomposed into interpretable structure-selection and constant-fitting terms. However, the manuscript (which consists only of the abstract) supplies no proof sketch, explicit assumptions, derivation steps, hypothesis-class definition, or application of specific complexity measures. This makes it impossible to verify whether the mathematics supports the stated decomposition or whether standard learning-theoretic tools apply to the class of bounded expression trees.

Authors: We agree that the provided manuscript consists only of the abstract and therefore supplies no proof sketch, explicit assumptions, derivation steps, hypothesis-class definition, or application of specific complexity measures. As a result, verification of the claimed decomposition and the applicability of standard learning-theoretic tools is not possible from the given text. The abstract is a concise summary of the result and its links to GP practices; it does not contain the technical development. revision: no

standing simulated objections not resolved

The full manuscript beyond the abstract is not available, so the proof sketch, assumptions, derivation steps, hypothesis-class definition, and complexity measure details cannot be supplied.

Circularity Check

0 steps flagged

No circularity in available abstract

full rationale

Only the abstract is provided, which states a derivation of a generalization bound decomposed into combinatorial structure-selection and constant-fitting terms under tree-size constraints. No equations, proof steps, hypothesis-class definitions, or self-citations appear. The claim is presented as a standard learning-theoretic result without any reduction to fitted inputs or self-referential definitions, so the derivation chain cannot be inspected for circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only; no explicit free parameters, axioms, or invented entities are stated. The bound presumably rests on standard statistical learning theory assumptions about hypothesis-class complexity that are not detailed here.

pith-pipeline@v0.9.0 · 5476 in / 1116 out tokens · 72279 ms · 2026-05-10T05:46:38.874621+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

31 extracted references · 2 canonical work pages

[1]

In: International Conference on Machine Learning

Arora, S., Ge, R., Neyshabur, B., Zhang, Y.: Stronger generalization bounds for deep nets via a compression approach. In: International Conference on Machine Learning. pp. 254–263. PMLR (2018)

2018
[2]

Advances in neural information processing systems30(2017)

Bartlett, P.L., Foster, D.J., Telgarsky, M.J.: Spectrally-normalized margin bounds for neural networks. Advances in neural information processing systems30(2017)

2017
[3]

Journal of machine learning research3(Nov), 463–482 (2002)

Bartlett, P.L., Mendelson, S.: Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of machine learning research3(Nov), 463–482 (2002)

2002
[4]

Journal of Machine Learn- ing Research2(Mar), 499–526 (2002)

Bousquet, O., Elisseeff, A.: Stability and Generalization. Journal of Machine Learn- ing Research2(Mar), 499–526 (2002)

2002
[5]

In: Graph theory and computing, pp

de Bruijn, N.G., Knuth, D.E., Rice, S.: The average height of planted plane trees. In: Graph theory and computing, pp. 15–22. Elsevier (1972)

1972
[6]

Proceedings of the national academy of sciences113(15), 3932–3937 (2016)

Brunton, S.L., Proctor, J.L., Kutz, J.N.: Discovering governing equations from data by sparse identification of nonlinear dynamical systems. Proceedings of the national academy of sciences113(15), 3932–3937 (2016)

2016
[7]

IEEE Transactions on Evolutionary Computation23(4), 703–717 (2018) On the Generalization Bounds of Symbolic Regression with GP 15

Chen, Q., Zhang, M., Xue, B.: Structural Risk Minimization-Driven Genetic Pro- gramming for Enhancing Generalization in Symbolic Regression. IEEE Transactions on Evolutionary Computation23(4), 703–717 (2018) On the Generalization Bounds of Symbolic Regression with GP 15

2018
[8]

Journal of Functional Analysis1(3), 290–330 (1967)

Dudley, R.M.: The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Analysis1(3), 290–330 (1967)

1967
[9]

Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data

Dziugaite, G.K., Roy, D.M.: Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data. arXiv preprint arXiv:1703.11008 (2017)

work page Pith review arXiv 2017
[10]

2016, arXiv e-prints, arXiv:1604.00772, doi: 10.48550/arXiv.1604.00772

Hansen, N.: The CMA Evolution Strategy: A Tutorial. arXiv preprint arXiv:1604.00772 (2016)

work page arXiv 2016
[11]

Evolutionary computation9(2), 159–195 (2001)

Hansen, N., Ostermeier, A.: Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary computation9(2), 159–195 (2001)

2001
[12]

In: European Conference on Genetic Programming

Keijzer, M.: Improving Symbolic Regression with Interval Arithmetic and Linear Scaling. In: European Conference on Genetic Programming. pp. 70–82. Springer (2003)

2003
[13]

Genetic Programming and Evolvable Machines5(3), 259–269 (2004)

Keijzer, M.: Scaled Symbolic Regression. Genetic Programming and Evolvable Machines5(3), 259–269 (2004)

2004
[14]

Genetic Programming and Evolvable Machines21(3), 471–501 (2020)

Kommenda, M., Burlacu, B., Kronberger, G., Affenzeller, M.: Parameter identifica- tion for symbolic regression using nonlinear least squares. Genetic Programming and Evolvable Machines21(3), 471–501 (2020)

2020
[15]

Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection, vol. 1. MIT Press (1992)

1992
[16]

Chapman and Hall/CRC (2024)

Kronberger, G., Burlacu, B., Kommenda, M., Winkler, S.M., Affenzeller, M.: Sym- bolic Regression. Chapman and Hall/CRC (2024)

2024
[17]

In: Pro- ceedings of the 6th International Conference on Genetic Algorithms

Langdon, W.B.: Evolving Data Structures with Genetic Programming. In: Pro- ceedings of the 6th International Conference on Genetic Algorithms. pp. 295–302 (1995)

1995
[18]

In: Soft Computing in Engineering Design and Manufacturing, pp

Langdon, W.B., Poli, R.: Fitness Causes Bloat. In: Soft Computing in Engineering Design and Manufacturing, pp. 13–22. Springer (1997)

1997
[19]

Quarterly of applied mathematics2(2), 164–168 (1944)

Levenberg, K.: A method for the solution of certain non-linear problems in least squares. Quarterly of applied mathematics2(2), 164–168 (1944)

1944
[20]

In: Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation

Luke, S., Panait, L.: Lexicographic Parsimony Pressure. In: Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation. pp. 829–836 (2002)

2002
[21]

Journal of the society for Industrial and Applied Mathematics11(2), 431–441 (1963)

Marquardt, D.W.: An Algorithm for Least-Squares Estimation of Nonlinear Param- eters. Journal of the society for Industrial and Applied Mathematics11(2), 431–441 (1963)

1963
[22]

MIT press (2018)

Mohri, M., Rostamizadeh, A., Talwalkar, A.: Foundations of Machine Learning. MIT press (2018)

2018
[23]

In: Conference on Learning Theory

Neyshabur, B., Tomioka, R., Srebro, N.: Norm-Based Capacity Control in Neural Networks. In: Conference on Learning Theory. pp. 1376–1401. PMLR (2015)

2015
[24]

Poli, R., Langdon, W.B., McPhee, N.F., Koza, J.R.: A Field Guide to Genetic Programming. Lulu. com (2008)

2008
[25]

In: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Poli, R., McPhee, N.F.: Parsimony Pressure Made Easy. In: Proceedings of the 10th annual conference on Genetic and evolutionary computation. pp. 1267–1274 (2008)

2008
[26]

Genetic Programming and Evolvable Machines3(3), 283–309 (2002)

Soule, T., Heckendorn, R.B.: An Analysis of the Causes of Code Growth in Genetic Programming. Genetic Programming and Evolvable Machines3(3), 283–309 (2002)

2002
[27]

In: Proceedings of the 5th International Conference on Genetic Algorithms

Tackett, W.A.: Genetic Programming for Feature Discovery and Image Discrimina- tion. In: Proceedings of the 5th International Conference on Genetic Algorithms. pp. 303–311 (1993)

1993
[28]

Science advances6(16), eaay2631 (2020)

Udrescu, S.M., Tegmark, M.: AI Feynman: A Physics-Inspired Method for Symbolic Regression. Science advances6(16), eaay2631 (2020)

2020
[29]

Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science, vol. 47. Cambridge university press (2018) 16 Nomura et al

2018
[30]

MRS communications9(3), 793–805 (2019)

Wang, Y., Wagner, N., Rondinelli, J.M.: Symbolic Regression in Materials Science. MRS communications9(3), 793–805 (2019)

2019
[31]

Evolutionary Computation3(1), 17–38 (1995)

Zhang, B.T., Mühlenbein, H.: Balancing Accuracy and Parsimony in Genetic Programming. Evolutionary Computation3(1), 17–38 (1995)

1995