Most methods that look for feature interactions ("gene A and gene B and gene C together change drug response") make the search affordable through one assumption. A three-way interaction is only explored if its pairs and single features already looked useful. The assumption is cheap, and it fails exactly where interactions matter most. In parity-like effects such as genetic epistasis or XOR gates, every lower-order piece has zero correlation with the outcome, so a bottom-up search discards the true interaction before it is ever scored. The methods that avoid the assumption, called safe pruning rules, prove that a whole branch of the search tree cannot contain anything useful. They pay for that proof with restrictions: features must lie in $[0,1]$ so that products only shrink, and the user must tune a regularization strength instead of simply asking for "the $k$ best."
We propose a look-ahead bound that removes both restrictions. Instead of bounding a branch by how its parent scored, we bound the total squared score of every interaction inside the branch. That total can be computed without enumerating the branch, using the dynamic-programming identity behind higher-order factorization machines. The bound is valid for any real-valued, signed features. It does not care whether lower-order pieces carry signal. It plugs into a best-first search whose pruning threshold is the current $k$-th best score. The deliverable is a search that returns the exact top-$k$ interactions up to order $M$ under a gradient score, together with a certificate that nothing pruned could have entered the top $k$. It is aimed at the regime where certificates matter: scientific discovery with modest sample size, thousands of features, and interaction orders of four or five.
Core Claim
Fix a working model with residual vector $r \in \mathbb{R}^n$ over $n$ samples. Score a candidate interaction, a set of features $T$, by its coordinate gradient
$$g_T = \sum_{i=1}^{n} r_i \prod_{j \in T} x_{ij}.$$
This is the quantity used to pick the next feature in greedy forward selection, orthogonal matching pursuit (a greedy method that repeatedly adds the feature most correlated with the current residual), and the coordinate-descent learner of SEQL.
Search proceeds over a canonical enumeration tree in which a node $S$ is extended only by features with index above $\max(S)$. Let $\mathcal{E}_q(S)$ be the extensions of $S$ by exactly $q$ further such features, and set $w_i = r_i \prod_{j\in S} x_{ij}$. The maximum is at most the sum of squares, so
$$\max_{T \in \mathcal{E}_q(S)} g_{T}^2 \;\le\; \sum_{T \in \mathcal{E}_q(S)} g_{T}^2 \;=\; w^\top K^{(q)}_{>\max S}\, w .$$
Here $K^{(q)}_{>j}(i,i') = e_q\big(x_{i,>j} \odot x_{i',>j}\big)$ is the degree-$q$ ANOVA kernel: the $q$-th elementary symmetric polynomial of the elementwise product of two samples, restricted to features after index $j$.
Higher-Order Factorization Machines showed that this kernel is computable in linear time per pair. They used it to fit a dense model over all interactions. We use it differently, as a ceiling score for a sparse, explicit search.
The bound has three properties that matter. First, it never assumes products shrink, so centered or $\pm 1$-coded features are fine. This matters because pure epistasis with zero lower-order marginals is naturally a $\pm1$ phenomenon, where SFP's $[0,1]$ condition does not hold. Second, it measures the contents of the subtree rather than the parent's own score, so a parity interaction raises the bound at its ancestors even though those ancestors score zero. Third, because it sums squared gradients rather than absolute per-sample contributions, noise interactions inside the subtree enter at their typical size. That size scales like $\sqrt{n}$, while a planted signal scales like $n$.
A back-of-envelope calculation gives the regime where pruning works. A signal-free subtree with $N$ members contributes roughly $N n \sigma^2$ to the sum. A node is therefore prunable against threshold $\tau_k = (n c_k)^2$ when $N \lesssim n c_k^2/\sigma^2$, where $c_k$ is the effect size of the $k$-th best interaction. Shallow nodes with huge subtrees will not be pruned. Nodes two or more levels deep often will be, and this is where the cost of order-4 and order-5 search lives.
Research Program
The first component is the bound oracle. Using Newton's identities, $K^{(q)}$ becomes an elementwise polynomial in power-sum Gram matrices $X^{(t)}X^{(t)\top}$ for $t \le q$, so each matrix costs one GPU matrix multiply. Storing a kernel for every suffix start index is too costly. Instead we bin suffixes into blocks and use the kernel of the enclosing block's longer suffix. A larger extension set only increases the sum, so the bound stays valid; it just gets looser. Each node's bound then costs $O(n^2)$ given the cached kernel. This beats enumerating the subtree, which costs $O(nN)$, whenever $N > n$. That condition holds overwhelmingly at depth $M-2$ and above when $M \ge 4$.
We also derive a linear-time but looser first-pass bound, $\sum_i |w_i|\, e_q(|x_{i,>j}|)$. It is the signed-feature analogue of SEQL's per-sample bound, and nodes are screened with it before the quadratic bound is computed.
The second component is the search. Following the ceiling-score queue of Minimal probing, which probes only the database record with the highest possible score until $k$ records are fully evaluated, we keep a priority queue of tree nodes keyed by their bound. We also keep a heap of the $k$ best fully scored interactions. A node is discarded once its bound falls below the current $k$-th best squared gradient. Search stops when the queue's top bound falls below that threshold, and that stopping condition is the certificate.
This replaces the fixed regularization threshold used by Safe Feature Pruning and by the subgradient mining of Feature Selection in Kernel Space. Those methods force a sweep over the regularization parameter $\lambda$ to land on a target count of $k$. CD-LSR argues that such sweeps are unstable, though only for single features.
The third component is seeding. The bound only prunes when the threshold is high, so we raise it early by first scoring candidates proposed by a cheap heredity-based method: adaptive polynomial expansion as in APPLE, or the order-by-order search of PROFIT. Progressive search is thus demoted from decision-maker to proposal generator. Where heredity holds, the threshold rises fast and the certificate is reached quickly. Where it fails, the bound still forces the search into the right subtrees.
The fourth component is model building and inference. The top-$k$ step is iterated inside orthogonal matching pursuit to build a sparse interaction model. Because each step is an exact marginal-screening or OMP selection, its output is the kind of selection event that Selective Inference for Sparse High-Order Interaction Models can attach valid $p$-values to. Whether their pruning during inference carries over to signed features is an open sub-question we will examine rather than assume.
On novelty: SEQL already performs branch-and-bound for the single best coordinate with a best-so-far threshold, and SFP already prunes safely. Extending either to a top-$k$ heap is a small step, and we treat that version as an ablation, not as our contribution. The new ingredient is the subtree-aggregate bound computed through ANOVA kernels. That bound is what allows signed features and parity.
Baselines
The naive reference point is exhaustive GPU enumeration of every interaction up to order $M$, scoring all of them against the residual and taking the top $k$. It is exact by construction. Its cost, roughly $n\binom{d}{M}$ multiply-adds, is the denominator for every speedup we report. It runs on the same hardware as our method. Where it cannot finish, we report it as infeasible and extrapolate its time from measured throughput.
The strongest existing exact competitor is a top-$k$ version of the per-sample safe bound used by SEQL and Safe Feature Pruning. We give it our queue, our dynamic threshold, and our seeding, so that the only difference is the bound. This is the key ablation isolating the aggregate bound. On $[0,1]$ data it can be run in its original form, and on signed data with its absolute-value generalization.
For reference, the reported numbers on Lacuna for SFP are speedups of "up to 80x faster than LASSO without pruning" with a pruning rate "over 99%" on synthetic data. For the Selective Inference paper, pruned inference on $d=10{,}000$ with 5th-order interactions ran in "just a few seconds" versus over a day unpruned on the HIV setting. No reported result was found on Lacuna for top-$k$ interaction recall or for search time to an exact top-$k$ on any benchmark. We will therefore rerun all baselines rather than quote them. Beating this baseline means fewer nodes scored and lower wall-clock time to the same certified top-$k$, and a valid result on signed data where the original SFP bound does not apply.
The strongest heuristic competitors are PROFIT, APPLE, and iterative Random Forests, which harvests co-occurring split paths. They are given the same total compute budget as our method, with hyperparameters tuned on a held-out split using an equal number of trials. They are judged on recall of the true top-$k$ (planted, or certified by our method or brute force) and on downstream held-out error. Beating them means equal or better recall in heredity-friendly settings, and much higher recall in parity settings, at comparable cost.
The final baseline is a dense HOFM trained on the same data. It serves only as a ceiling on predictive accuracy for an all-interactions model. If our sparse OMP model with $k$ explicit interactions comes within a small margin of HOFM's held-out error, the interpretability gain costs little.
Why not just…?
Why not just enumerate everything on a GPU? At order three with $d \approx 1000$ and a few hundred samples, this is a real threat. Roughly $10^8$ candidates times $n$ is seconds of GPU work, and we expect brute force to win there. Our claim is confined to order four and above. At order five with $d=1000$, the roughly $8\times10^{12}$ candidates count cited for this regime makes brute force a multi-day job. The experiments report the crossover order explicitly, and a crossover above order five would sink the proposal.
Why not just use a heredity-based progressive search like PROFIT or APPLE? These methods only expand parents that already score well. The parity argument of Margaritis shows such interactions have zero lower-order signal, so the methods never reach them. Where heredity does hold, they are cheaper than us, which is why we use them as seeds rather than discard them. The planted-parity experiment measures their recall directly. The heredity-friendly experiment tests whether seeding lets our method match their cost.
Why not just add a top-$k$ heap to SEQL or SFP bounds? This is the obvious combination and our main ablation. Its bound sums absolute per-sample contributions, which grow with every noise interaction in the subtree without cancellation. Our squared aggregate lets those noise contributions enter at their typical $\sqrt{n}$ size instead. If the ablation prunes as well as the aggregate bound on real signed data, the aggregate bound is not worth its $O(n^2)$ cost, and we would report the simpler method as the recommendation.
Why not just fit a higher-order factorization machine and read off interactions? HOFM's factors are dense and low-rank, and they do not identify which explicit conjunctions drive predictions. We include it as an accuracy ceiling, not as a selection method.
Proposed Experiments
The first experiment is synthetic. We plant $\pm1$-coded parity interactions of orders three to five among $d \in \{500, 2000\}$ features with $n \in \{250, 1000, 5000\}$. We mix in heredity-respecting interactions and vary effect size. Measurements are recall of the planted top-$k$, nodes scored, and wall-clock time to certificate, compared against all baselines. We also compare the empirical pruning depth against the predicted condition $N \lesssim n c_k^2/\sigma^2$.
The second experiment uses two real datasets. The CCLE MEK-inhibitor response data has $n=259$ and $d=1104$ continuous expression features, which is exactly the signed, small-$n$ regime. RAMPART reported ten top single genes there but no interaction-level numbers. The Stanford HIV drug resistance data from Selective Inference for Sparse High-Order Interaction Models allows a direct check: do we recover, with certificates, the 3rd- and 4th-order mutation interactions that paper flagged? Do we find order-5 interactions their screening could not reach? Held-out regression error of the resulting OMP models is reported against HOFM and iRF.
The third experiment is a scaling check on the LIBSVM sets used by SFP, where features are naturally in $[0,1]$. This gives the per-sample bound its best case, so it is the fair place to see whether the aggregate bound still helps.
The decisive checks are three. On planted parity at order four or higher, our method must reach recall near one while heredity methods stay near zero, and it must finish faster than brute force. On real signed data, the aggregate bound must prune substantially more nodes than the per-sample ablation at matched threshold. Across settings, the measured brute-force crossover order must be at most four. If the bound never prunes nodes two or more levels above the maximum order on CCLE or HIV, the approach does not deliver, and that negative result is itself worth reporting.
References
- Bounded coordinate-descent for biological sequence classification in high dimensional predictor space
- Higher-Order Factorization Machines
- Minimal probing: supporting expensive predicates for top-k queries
- Safe Feature Pruning for Sparse High-Order Interaction Models
- Feature Selection in Kernel Space: A Case Study on Dependency Parsing
- Efficient Top-K Feature Selection Using Coordinate Descent Method
- Scalable Nonlinear Learning with Adaptive Polynomial Expansions
- Progressive Feature Interaction Search for Deep Sparse Network
- Selective Inference for Sparse High-Order Interaction Models
- Iterative random forests to discover predictive and stable high-order interactions
- Toward Provably Correct Feature Selection in Arbitrary Domains
- Top-$k$ Feature Importance Ranking