Be Greedy, Stay Linear: Universally Robust Feature Engineering

Automated feature engineering (FE) for tabular data often assumes that complex downstream models require equally complex selection proxies. We expose this as a fundamental fallacy: the Selector Overfitting Paradox. As dimensionality scales, high-capacity proxies overfit to the expanding combinatorial noise, generating bloated representations that actively degrade densely tuned, state-of-the-art predictors. To resolve this, we introduce LinFE, a greedy symbolic feature-construction method that enforces a strict linear bottleneck. By utilizing an Ordinary Least Squares (OLS) readout, feature generation transitions from an approximate heuristic into an exact geometric matching pursuit, where the optimal candidate is strictly the one maximizing its orthogonal projection onto the current residual. We further unify the search space by statically mapping categorical variables to continuous residual-mean terminals. Across a comprehensive OpenML benchmark, competing FE methods inject variance and fail to outperform optimized raw baselines. In stark contrast, LinFE extracts sparse, structural representations that consistently improve densely tuned LightGBM, CatBoost, and Neural Networks. Our results demonstrate a counterintuitive truth governing high-dimensional learning dynamics: restricting selection capacity liberates representation power, immunizing the search against the curse of dimensionality and distilling only universally robust features.