Be Greedy, Stay Linear: Universally Robust Feature Engineering

Automated feature engineering (FE) often fails a critical test: strictly improving heavily optimized, state-of-the-art (SOTA) predictors. We show that existing FE methods, while boosting untuned baselines, very often make densely tuned GBDT and Neural Networks (NNs) perform worse. We attribute this to a common design paradigm: modern FE methods rely on complex proxy models under the assumption that sophisticated downstream learners require equally complex selection mechanisms. We show that this is counterproductive from two theoretical standpoints. From a feature selection perspective, we demonstrate that complex selection proxies can significantly inflate a feature's apparent benefit, making the process highly susceptible to spurious correlations. From a performance perspective, we show that complex selection proxies yield significantly higher upper bounds on Universality Regret: a metric capturing the expected performance gap between downstream models trained on selected versus optimal feature sets. Together, these two observations highlight the importance of restricting the selection model complexity. To that end, we introduce LinFE, a greedy symbolic feature construction method that enforces a strictly linear selector, constructing the feature set iteratively using the Gram-Schmidt optimized form of the classical Orthogonal Least Squares (OLS) approach. LinFE essentially represents a modern revival of OLS, fine-tuned with (a) evolutionary elements (for faster search), (b) optimized categorical variable representation using their error residuals, and (c) a patience-based cross-validation stopping criterion that is ubiquitous in neural network training. Via a robust evaluation framework on 20 OpenML benchmarks, we demonstrate that while competing FE methods fail to outperform optimized raw baselines in most cases, LinFE consistently elevates the performance of tuned LightGBM, CatBoost, Random Forests, and NNs. Our results demonstrate that for tabular data regression, restricting selector capacity is not a limitation, but a vital step to ensuring the learning of universally robust features.