New generalization bound theory for GP-based symbolic regression reveals why practices like depth limits work

A new theoretical analysis from Nomura, Hamano, and Ono provides the first rigorous generalization bound for symbolic regression (SR) using genetic programming (GP). Accepted at PPSN2026, the work addresses a long-standing gap: while GP-based SR empirically discovers interpretable mathematical expressions from data, its theoretical generalization properties were poorly understood. The authors model SR expressions as tree structures and derive a bound that separates the generalization gap into two interpretable components.

The structure-selection term captures the combinatorial complexity of choosing which tree topology to use, while the constant-fitting term measures the sensitivity of numerical constants to data perturbations. Strikingly, the analysis shows how common GP design choices directly reduce these terms: depth limits and parsimony pressure shrink the hypothesis class of possible trees, while numerically stable operators and interval arithmetic control constant sensitivity. This gives practitioners a principled explanation for why these heuristics work, potentially guiding smarter algorithm design for interpretable AI.