Model Recovery in Symbolic Regression: Theory, Conjectures, and Open Questions

With the recent advancements in symbolic regression (SR) enabling search over large function spaces, recovering complex models from data may become attainable. But in what settings can SR algorithms be expected to recover the true data-generating model, or at least the best prediction model? This paper phrases SR as a model selection problem and formalizes the discussion on whether model recovery is possible. For the case of estimating an unknown non-linear conditional expectation function, exhaustive symbolic regression (ESR) is conjectured to select the correct functional form in large samples, given that the true conditional expectation function is in the search space and that a consistent model selection criterion is used. Within the PAC-learning framework, ESR can be phrased as structural risk minimization (SRM) problem, and we indicate that ESR is non-uniformly PAC-learnable under mild assumptions. Finally, we discuss post-selection inference for models selected via SR.