Interaction Screening for Automatically Generated Features

Automated feature engineering systems build new tabular features by combining raw columns (products, ratios, group-wise means), then try to keep the few that actually help prediction. The pool they search is correlated by construction. A product $x_1 x_2$ is correlated with $x_1$, with $x_2$, and with every other product that reuses either parent. We argue this is the same failure that statistical physics identified in learning Ising models (networks of interacting binary variables). When couplings are strong, indirect correlations reach far across the network, swamp the direct ones, and cause simple local tests to pick the wrong variables. More data does not fix this. Current feature-generation tools rank candidates with marginal or residual scores. Those scores are close relatives of the estimators that provably break in that regime, and none of the tools comes with a guarantee on how many samples are needed.

We propose to select generated features with an estimator taken from the strongly coupled Ising literature: the interaction screening objective. Its key property is that its gradient vanishes at the true parameters whatever the correlation structure among the inputs. We then threshold the estimate. The aim is a selection procedure whose sample requirement grows with the logarithm of the candidate-pool size and does not depend on how correlated the candidates are. Two consequences can be tested. First, heuristic selectors should fail at a coupling threshold that no amount of data repairs. Second, because the log of the pool size grows only linearly with composition depth, deeper feature compositions should cost samples roughly linearly in depth. That would turn the open dispute over whether deep compositions help or overfit into a measurable question about the selector rather than the features.

Core Claim

Three bodies of work meet here.

The first supplies the mechanism. Which graphical models are difficult to learn? proves that correlation thresholding, local conditional-independence tests, and $\ell_1$-regularized logistic regression all fail to recover Ising structure past a coupling threshold, even with unlimited samples. The cliff sits at $\theta \approx 0.42$ on random regular graphs of degree 4 and at $\theta \approx 0.7$ on $7\times 7$ grids. The cause is that non-neighbors come to mimic neighbors, which breaks the incoherence condition.

The second supplies the method. Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models and Optimal structure and parameter learning of Ising models introduce an estimator (RISE) that keeps working at low temperature, with $n = \mathcal{O}(e^{\beta d}\ln p)$. Here $\beta$ is the largest coupling and $d$ the largest degree.

The third supplies the regime and the gap. OpenFE scores candidates by boosting on residuals and prunes them with gradient-boosted-tree importance. IIFE filters candidate pairs by three-way interaction information. Both are empirical and offer no recovery guarantee. They also disagree about composition depth: OpenFE finds that first-order features capture almost all gains, while IIFE needs order-10 features on Jungle Chess.

Our move is to treat the target $y\in\{\pm1\}$ as one more variable in a higher-order interaction model. The model is defined over a dictionary $\phi(x)\in[-1,1]^{|C|}$ of generated candidates, built from binarized or bounded base features $x$. We fit

$$\hat\theta = \arg\min_{\theta}\ \frac{1}{n}\sum_{t=1}^{n} \exp\!\big(-y^{(t)}\,\theta^\top \phi(x^{(t)})\big) + \lambda\|\theta\|_1,$$

and keep the candidates whose $|\hat\theta_j|$ exceeds half the smallest true coupling. If $P(y\mid x)\propto \exp(y\,\theta^{*\top}\phi(x))$, then summing over $y$ shows that

$$\mathbb{E}\big[\,y\,\phi_j(x)\,e^{-y\,\theta^{*\top}\phi(x)}\big] = 0 \quad \text{for every candidate } j \text{ and every distribution of } x.$$

So the truth is a stationary point no matter how collinear the dictionary is.

What can still fail is curvature, not bias. If two candidates are near-duplicates once the others are known, the objective is flat between them. Our target theorem is therefore the following. Suppose $\|\theta^*\|_1\le\gamma$, the support has size $k$, the smallest active coefficient is $\eta$, and every candidate keeps conditional variance at least $\kappa$ given the rest. Then thresholded screening recovers the support when

$$n \gtrsim \frac{e^{c\gamma}\,k^2}{\kappa\,\eta^2}\,\log\frac{|C|}{\delta}.$$

This has the same form as the RISE bound, with the Ising degree replaced by dictionary sparsity. For all products of up to $r$ of $m$ base features, $\log|C|\approx r\log m$, so the bound predicts a sample cost linear in depth.

The novelty is not interaction screening itself. It is two things together. We identify feature-generation pools as a regime of long-range correlation interference. And we give a selector for them with a sample-complexity guarantee whose only correlation-dependent quantity is the conditional variance $\kappa$, not incoherence.

Research Program

On the theory side, we will prove the bound above for bounded dictionaries. We will follow the restricted-strong-convexity argument of the RISE papers and replace their Ising-specific variance lemma with the assumption $\kappa$. We will then show that $\kappa$ is bounded below when base features are themselves Ising spins with bounded couplings and the dictionary consists of products of spins. This is the case the synthetic benchmark instantiates.

We will also state plainly what the result does not buy. Structure learning of antiferromagnetic Ising models gives an $\Omega(p^{d/2})$ lower bound for statistical algorithms on parity-like structure. Our guarantee is therefore statistical only. Pure high-order interactions remain computationally expensive, because some search must still put them into the dictionary. On Learning Discrete Graphical Models using Group-Sparse Regularization shows that when interactions are hierarchical, lower-order terms reveal higher-order ones. We use that fact for growth, not for selection.

On the algorithm side, enumerating $m^r$ candidates is infeasible beyond small $r$. We therefore grow the dictionary lazily, in the active-set style of Efficient Structure Learning of Markov Networks using L1-Regularization. At each round we propose children of currently active features under the operator set, and add those with the largest screening-objective gradient magnitude. A gradient taken at the reweighted current fit is not a marginal score. Under the identity above, irrelevant candidates' gradients shrink as the fit approaches the truth. We still treat the greedy path as a possible failure point and measure it separately from the convex estimator run on a fully enumerated dictionary. Exact duplicates, such as an operator applied twice to the same input, are merged by hashing before fitting. Continuous targets use the analogous screening loss for bounded responses, and multiclass targets use one-versus-rest.

Baselines

The naive reference is the downstream model on raw features with no generation. All relative-improvement numbers are anchored to it.

The strongest existing tabular competitor is IIFE (IIFE). It reports an average 26.88% improvement over the raw-feature baseline across its 8 public datasets and the top rank in 10 of 24 dataset-model combinations. On a private dataset it reports 6.21% against 1.16% for adjusted OpenFE. IIFE matters most here because it is the existing method most explicitly aimed at synergistic, higher-order interactions. Those are the cases where we claim marginal-style scoring breaks.

OpenFE (OpenFE) is the second heuristic competitor. It reports significant improvements on 40 of 49 OpenML CC18 datasets. We run it with its residual-boosting scoring and two-stage pruning.

Both are re-run by us under the strict inductive cross-validation protocol IIFE advocates. Transformations are fit on training folds only. Every method sees the same operator set, the same depth limit, and the same wall-clock budget per dataset. Each gets the same number of hyperparameter trials, tuned on inner folds. We count our method as beating them only if its mean rank across datasets is better and it wins on a majority of datasets under a paired test across folds. Matching them on average while losing more often does not count.

On synthetic data no AutoFE method has reported results. We found no reported result on Lacuna for OpenFE or IIFE on Ising-generated correlated features. The physics reference points are the Bento–Montanari cliffs ($\theta\approx0.42$ on random regular graphs of degree 4, $\theta\approx0.7$ on $7\times7$ grids). The second reference point is the RISE torus fit $n_{\min}\approx 1.1\times10^5(\ln p-1.9)$, which serves as a scaling check for our estimator when the dictionary is pairwise only.

Two ablations isolate the key ingredient. The first swaps the screening objective for $\ell_1$-regularized logistic regression, with and without the same thresholding step. The second swaps it for misspecified Lasso with post-thresholding, as analyzed in On Model Selection Consistency of Lasso for High-Dimensional Ising Models. Both keep the dictionary, the active-set growth, and the tuning budget identical. A third ablation replaces gradient-based growth with OpenFE's residual scoring, to separate selection errors from growth errors.

Why not just…?

Why not just run $\ell_1$-logistic regression with post-thresholding on the generated pool?

This is the most serious threat. Logistic loss also has zero expected gradient at a well-specified truth. The AISTATS 2023 paper shows that post-thresholding removes the incoherence requirement for Lasso, though only in the weakly coupled (paramagnetic) phase on tree-like graphs. The Bento–Montanari failure concerns logistic regression without thresholding, and RISE is reported to succeed at low temperature where logistic regression fails. Whether thresholded logistic regression closes that gap is exactly what our first ablation measures, past the cliff on grids and random regular graphs. If it matches screening, we will report that the correlation-robust ingredient is estimate-then-threshold over the dictionary rather than the exponential reweighting. The theory and the depth-scaling prediction would still stand, but the method would be simpler.

Why not just whiten or decorrelate the candidate pool and run Lasso?

The two-stage PCA whitening of Qiong Wu et al. and the design-matrix adaptation of Jonathan A. Kelner et al. were developed for linear Gaussian regression. Rotating the pool also destroys the sparsity of the support in the original candidates, which is what feature engineering needs to return. We include whitening-plus-Lasso as a baseline on the continuous-target datasets. We expect it to be competitive on prediction but poor on recovering the planted support in synthetic tests.

Why not just let gradient-boosted trees find the interactions from raw features?

Trees split greedily on marginal gains. Interactions with no marginal signal, such as parity-like targets, are invisible to them until one split happens by chance. The strongest evidence that explicit high-order candidates matter is IIFE's Jungle Chess result, which required order-10 features. Our synthetic suite includes pure order-3 terms specifically to test this. Raw-feature boosting is also the downstream model in the naive baseline, so any gain it already captures is subtracted out.

Why not just filter with interaction information, as IIFE does?

Interaction information is a three-way marginal quantity. Under strong coupling, distant candidates inherit synergy from the true ones in the same way distant spins inherit correlation, so the filter should admit look-alikes. The synthetic sweep across the coupling threshold tests directly whether its precision collapses independently of $n$.

Proposed Experiments and Decisive Checks

The synthetic benchmark plants base binary features from Ising models on $7\times7$ grids and on random regular graphs of degree 4. Couplings are swept through the published cliffs, and some instances use mixed-sign couplings. Mixed signs are a spin-glass-like case that existing negative results leave untouched. The target is drawn from a sparse logistic model over generated products of orders 1 to 3. We include both hierarchical and pure high-order terms. The metric is exact support recovery probability as a function of $n$, coupling strength, and dictionary depth $r$.

Three outcomes are decisive. First, the premise requires OpenFE-style, IIFE-style, and plain logistic selectors to plateau below full recovery past the cliff as $n$ grows. If they do not, correlation interference is not the bottleneck in feature generation, and the proposal should be abandoned. Second, our estimator's minimal sample size for recovery should grow roughly linearly in $r$ at fixed coupling, consistent with $\log|C|\approx r\log m$. Faster growth would falsify the theory's practical relevance. Third, the ablations should show whether the reweighting, the thresholding, or the growth rule carries the effect.

On real data we use the 49 OpenML CC18 datasets, the IIFE public suite including Jungle Chess, and binarized $16\times16$ MNIST as a naturally long-range-correlated input. Each candidate pool is scored by the minimum conditional variance $\kappa$, estimated on training folds. The final check asks whether the gap between our method and the heuristics widens as $\kappa$ falls and pool correlation rises. Such a trend would connect the synthetic mechanism to tabular practice rather than leaving it as an analogy.