# The SKIM-FA Kernel: High-Dimensional Variable Selection and Nonlinear Interaction Discovery in Linear Time

arXiv: https://arxiv.org/abs/2106.12408 · HTML: https://mlsanity.com/paper/2106.12408/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 73 references that are in the map.
- First posted on arXiv 23 Jun 2021.

## Builds on (most cited first, 7 of 7)

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Structure Discovery in Nonparametric Regression through Compositional Kernel Search](https://mlsanity.com/paper/1302.4922/) (2013)
- [Sparsity information and regularization in the horseshoe and other shrinkage priors](https://mlsanity.com/paper/1707.01694/) (2017)
- [Safe Pattern Pruning: An Efficient Approach for Predictive Pattern Mining](https://mlsanity.com/paper/1602.04548/) (2016)
- [The Kernel Interaction Trick: Fast Bayesian Discovery of Pairwise Interactions in High Dimensions](https://mlsanity.com/paper/1905.06501/) (2019)
- [Convex Modeling of Interactions with Strong Heredity](https://mlsanity.com/paper/1410.3517/) (2014)
- [Bayesian Factor Analysis for Inference on Interactions](https://mlsanity.com/paper/1904.11603/) (2019)

## Built on by (most cited first, 3 of 3)

- [Common Functional Decompositions Can Mis-attribute Differences in Outcomes Between Populations](https://mlsanity.com/paper/2504.16864/) (2025)
- [CUBE: Contrastive Understanding by Balanced Experiments](https://mlsanity.com/paper/2509.10825/) (2025)
- [A Weighted Kernel Method for Approximation that Adapts to Learned Multivariable Structure](https://mlsanity.com/paper/2609.16606/) (2026)

## Abstract (arXiv)

Many scientific problems require identifying a small set of covariates that are associated with a target response and estimating their effects. Often, these effects are nonlinear and include interactions, so linear and additive methods can lead to poor estimation and variable selection. Unfortunately, methods that simultaneously express sparsity, nonlinearity, and interactions are computationally intractable -- with runtime at least quadratic in the number of covariates, and often worse. In the present work, we solve this computational bottleneck. We show that suitable interaction models have a kernel representation, namely there exists a "kernel trick" to perform variable selection and estimation in O(# covariates) time. Our resulting fit corresponds to a sparse orthogonal decomposition of the regression function in a Hilbert space (i.e., a functional ANOVA decomposition), where interaction effects represent all variation that cannot be explained by lower-order effects. On a variety of synthetic and real data sets, our approach outperforms existing methods used for large, high-dimensional data sets while remaining competitive (or being orders of magnitude faster) in runtime.