Abstract
Taking into account high-order interactions among covariates is valuable in many practical regression problems. This is, however, a computationally challenging task because the number of high-order interaction features to be considered would be extremely large unless the number of covariates is sufficiently small. In this paper, we propose a novel efficient algorithm for LASSO-based sparse learning of such high-order interaction models. Our basic strategy for reducing the number of features is to employ the idea of recently proposed safe feature screening (SFS) rule. An SFS rule has a property that, if a feature satisfies the rule, then the feature is guaranteed to be non-active in the LASSO solution, meaning that it can be safely screened-out prior to the LASSO training process. However, applying such an SFS rule to each of the extremely large number of high-order interaction features would be computationally infeasible. Our key idea for solving this computational issue is to exploit the underlying tree structure among high-order interaction features. Specifically, we introduce a pruning condition called safe feature pruning (SFP) rule which has a property that, if the rule is satisfied in a certain node of the tree, then all the high-order interaction features corresponding to its descendant nodes can be guaranteed to be non-active at the optimal solution. Our algorithm is extremely efficient, making it possible to work with 3rd order interactions of 10,000 original covariates, where the number of possible high-order interaction features is greater than $10^{12}$.
Introduction
In many real-world scenarios, such as genomics or web mining, the relationship between variables is rarely just additive. Variables often interact in complex ways, and capturing these "high-order interactions" (e.g., $x_1 \cdot x_2 \cdot x_3$) is essential for building accurate predictive models. However, researchers face a massive hurdle: the combinatorial explosion of the feature space.
If a dataset contains 10,000 original variables and we wish to consider 3rd-order interactions, the number of potential features exceeds $10^{12}$ (one trillion). Standard optimization tools like the LASSO cannot handle this scale; they cannot store such a massive matrix in memory, nor can they efficiently iterate through a trillion columns to find the few that actually matter. This paper introduces Safe Feature Pruning (SFP), an algorithm designed to navigate this trillion-feature space efficiently.
Methods: The SFP Algorithm
The authors build upon two existing concepts to create a new, scalable approach:
- Safe Feature Screening (SFS): A mathematical rule that uses the dual version of the LASSO problem to identify features guaranteed to have a coefficient of zero at the optimal solution. If a feature is "screened out," it can be safely ignored during training.
- Tree-Structured Features: High-order interactions can be organized into a hierarchical tree. For example, a node for $z_1$ is a parent to $z_1z_2$, which in turn is a parent to $z_1z_2z_3$. This structure is visualized in Figure 1.
- Safe Feature Pruning (SFP): The core innovation is a new pruning condition. If this condition is met at a specific node in the tree, it is mathematically guaranteed that all of its descendants will also be non-active (zero) in the final model. Instead of checking every single one of the trillion features, the algorithm traverses the tree and prunes entire branches at once. This allows the solver to focus only on a tiny fraction of the total feature space.
Theoretical Foundations
Monotonicity and Safety
The SFP rule relies on the fact that if variables are scaled between 0 and 1, the value of an interaction feature can only stay the same or decrease as you add more variables to the interaction ($x_1 \cdot x_2 \le x_1$). This "diminishing" property allows for the creation of upper bounds used for pruning.
Crucially, SFP is not a heuristic. Many researchers use "strong heredity" assumptions, which guess that an interaction only exists if its parent variables are also important. SFP is a "safe" method, meaning it is guaranteed to find the exact same optimal solution as if you had somehow processed all trillion features.
Warm Starts
The algorithm is further optimized using a "warm start" strategy along a regularization path. By testing different levels of sparsity, the solver uses the solution from a simpler model to create tighter bounds for the next, more complex model. This makes the pruning increasingly efficient as the search progresses.
Experimental Results
The researchers evaluated SFP using synthetic data and seven benchmark datasets from the LIBSVM repository (including mnist, rcv1_binary, and news20).
- Massive Speedups: On synthetic data, SFP was up to 80x faster than a version of LASSO without pruning.
- Superiority over Itemset Boosting: SFP was faster than Itemset Boosting (IB) in almost every benchmark. While IB requires a trial-and-error process to confirm optimality, SFP's safety guarantees skip that step entirely.
- Extreme Scalability: The algorithm successfully handled 3rd-order interactions for 10,000 covariates on a standard workstation.
- Pruning Efficiency: In many tests, the "pruning rate" was over 99%, demonstrating that the algorithm successfully ignored the vast majority of the search space.
Conclusion
Safe Feature Pruning provides a robust solution to the curse of dimensionality in high-order interaction models. By leveraging the mathematical properties of the LASSO dual problem and the hierarchical nature of interactions, it enables the training of models with trillions of features. Future work may extend this logic to classification tasks like Logistic Regression and explore broader data domains beyond the $[0, 1]$ range.
Summary updated