On the Generalization Bounds of Symbolic Regression with Genetic Programming

Symbolic regression (SR) is a method aimed at discovering analytical expressions that describe relationships between input variables and target outputs directly from data. Unlike conventional regression methods, which assume a predefined model class and then optimize parameters within that class, SR simultaneously searches for both the functional form of the predictor and its numerical coefficients. Because the output of SR is an explicit mathematical expression, the resulting models are often interpretable and can sometimes reveal underlying mechanisms in the data. Genetic programming (GP) is one of the most widely used approaches to SR. In GP-based SR, candidate models are typically represented as expression trees whose internal nodes correspond to operators and whose leaves correspond to variables or constants. Evolutionary search is then used to explore the space of symbolic structures through operations such as mutation, crossover, and selection. Additionally, the numerical constants within a given structure are often refined using dedicated continuous optimization techniques, such as nonlinear least squares. This hybrid nature—combining discrete structure search with continuous parameter optimization—makes GP particularly attractive for SR, as it enables open-ended exploration of functional forms without requiring prior commitment to a specific model class.

Despite the significant empirical success of GP in symbolic regression, the theoretical understanding of its generalization capabilities remains limited. Specifically, why a model found by GP should generalize beyond the training data is a question that has not been fully explained in learning-theoretic terms. This question concerns how well a model that fits the training data will perform on unseen data, typically formalized through the notion of a generalization gap, the difference between training error and expected prediction error. In practice, GP-based SR is known to be sensitive to design choices such as tree-size limits, maximum depth, constant optimization strategies, and the use of protected or numerically stable operators, many of which are motivated by the need to control overfitting.

The core innovation of this paper lies in deriving an explicit generalization bound for GP-style symbolic regression models for the first time and decomposing the generalization gap into structure selection and constant fitting. This decomposition provides a theoretical lens for understanding how common mechanisms in GP influence generalization. Specifically, structural restrictions improve generalization performance by reducing hypothesis-class growth, while stability mechanisms such as protected operators and interval arithmetic control the sensitivity of predictions to parameter perturbations. By linking these practical design choices to explicit complexity terms in the generalization bound, the study offers a theoretical explanation for commonly observed empirical behaviors in GP-based symbolic regression.

The methodology of this paper includes the following key steps:

• �� Deriving the generalization bound for GP-style symbolic regression: Under constraints on tree size, depth, and learnable constants, derive an explicit bound for the generalization gap.
• �� Decomposition of the generalization gap: Decompose the generalization gap into a structure-selection term and a constant-fitting term, reflecting the combinatorial complexity of choosing an expression-tree structure and the complexity of optimizing numerical constants within a fixed structure, respectively.
• �� Linking theoretical analysis to practice: By linking practical design choices to explicit complexity terms in the generalization bound, provide a theoretical explanation for commonly observed empirical behaviors in GP-based symbolic regression.
• �� Experimental validation: Validate the theoretical analysis through experiments, demonstrating the impact of structural restrictions and stability mechanisms on generalization performance.

The experimental design includes comparisons using multiple datasets and baseline methods to evaluate the generalization performance of the proposed method. Key parameters include tree size and depth limits, constant optimization strategies, etc. The experiments also include ablation studies to verify the impact of different design choices on generalization performance. By comparing the performance of different models on test datasets, the validity of the theoretical analysis is verified.

Results analysis shows that limiting the depth and size of trees significantly lowers the combinatorial complexity of the model, thereby reducing the risk of overfitting. Additionally, stability mechanisms such as protected operators and interval arithmetic are reflected in better test performance, validating the theoretical analysis. Experiments also demonstrate that common GP practices, such as parsimony pressure and depth limits, are directly related to theoretical complexity terms, providing a theoretical explanation for empirically observed behaviors.

The applications of this research include scientific discovery and interpretable modeling, where symbolic regression can provide compact analytical expressions that offer insights in addition to predictive accuracy. Through theoretical analysis, the study lays the foundation for developing more rigorous methods for controlling model complexity, with broad academic and industrial impact.

Although the study provides a theoretical framework for symbolic regression, the worst-case complexity measures used may be conservative in practice and fail to fully capture the effective complexity of observed data. Additionally, the generalization bounds are data-independent, which may affect their quantitative tightness. Future work needs to develop data-dependent bounds to better capture the effective complexity of symbolic regression models on observed data.