# Fast and More Powerful Selective Inference for Sparse High-order Interaction Model

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 36 references that are in the map.
- First posted on arXiv 9 Jun 2021.

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

- [Exact post-selection inference, with application to the lasso](https://mlsanity.com/paper/1311.6238/) (2013)
- [Optimal Inference After Model Selection](https://mlsanity.com/paper/1410.2597/) (2014)
- [Exact Post-Selection Inference for Sequential Regression Procedures](https://mlsanity.com/paper/1401.3889/) (2014)
- [Valid Inference Corrected for Outlier Removal](https://mlsanity.com/paper/1711.10635/) (2017)
- [More Powerful Conditional Selective Inference for Generalized Lasso by Parametric Programming](https://mlsanity.com/paper/2105.04920/) (2021)
- [More powerful post-selection inference, with application to the Lasso](https://mlsanity.com/paper/1801.09037/) (2018)
- [Selective Inference for Group-Sparse Linear Models](https://mlsanity.com/paper/1607.08211/) (2016)
- [Post-Selection Inference for Changepoint Detection Algorithms with Application to Copy Number Variation Data](https://mlsanity.com/paper/1812.03644/) (2018)
- [Selecting the number of principal components: estimation of the true rank of a noisy matrix](https://mlsanity.com/paper/1410.8260/) (2014)
- [A significance test for forward stepwise model selection](https://mlsanity.com/paper/1405.3920/) (2014)
- [Selective Sequential Model Selection](https://mlsanity.com/paper/1512.02565/) (2015)
- [Safe Pattern Pruning: An Efficient Approach for Predictive Pattern Mining](https://mlsanity.com/paper/1602.04548/) (2016)
- [Selective inference in regression models with groups of variables](https://mlsanity.com/paper/1511.01478/) (2015)
- [Integrative Methods for Post-Selection Inference Under Convex Constraints](https://mlsanity.com/paper/1605.08824/) (2016)
- [WHInter: A Working set algorithm for High-dimensional sparse second order Interaction models](https://mlsanity.com/paper/1802.05980/) (2018)

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

- [Valid P-Value for Deep Learning-Driven Salient Region](https://mlsanity.com/paper/2301.02437/) (2023)
- [CAD-DA: Controllable Anomaly Detection after Domain Adaptation by Statistical Inference](https://mlsanity.com/paper/2310.14608/) (2023)
- [Exact Statistical Inference for the Wasserstein Distance by Selective Inference](https://mlsanity.com/paper/2109.14206/) (2021)
- [Statistical Test for Feature Selection Pipelines by Selective Inference](https://mlsanity.com/paper/2406.18902/) (2024)
- [Statistical Test for Auto Feature Engineering by Selective Inference](https://mlsanity.com/paper/2410.19768/) (2024)
- [Quantifying Statistical Significance of Deep Nearest Neighbor Anomaly Detection via Selective Inference](https://mlsanity.com/paper/2502.12978/) (2025)
- [Efficient Model Selection for Predictive Pattern Mining Model by Safe Pattern Pruning](https://mlsanity.com/paper/2306.13561/) (2023)
- [Feature Importance Measurement based on Decision Tree Sampling](https://mlsanity.com/paper/2307.13333/) (2023)
- [Statistical Inference for Feature Selection after Optimal Transport-based Domain Adaptation](https://mlsanity.com/paper/2410.15022/) (2024)
- [Statistical Inference for Autoencoder-based Anomaly Detection after Representation Learning-based Domain Adaptation](https://mlsanity.com/paper/2508.07049/) (2025)
- [A Confidence Machine for Sparse High-Order Interaction Model](https://mlsanity.com/paper/2205.14317/) (2022)
- [Bounded P-values in Parametric Programming-based Selective Inference](https://mlsanity.com/paper/2307.11351/) (2023)
- [Statistical Test for Diffusion-Based Anomaly Localization via Selective Inference](https://mlsanity.com/paper/2402.11789/) (2024)
- [Statistical Inference for the Dynamic Time Warping Distance, with Application to Abnormal Time-Series Detection](https://mlsanity.com/paper/2202.06593/) (2022)
- [Statistical Inference for Clustering-based Anomaly Detection](https://mlsanity.com/paper/2504.18633/) (2025)

## Abstract (arXiv)

Automated high-stake decision-making such as medical diagnosis requires models with high interpretability and reliability. As one of the interpretable and reliable models with good prediction ability, we consider Sparse High-order Interaction Model (SHIM) in this study. However, finding statistically significant high-order interactions is challenging due to the intrinsic high dimensionality of the combinatorial effects. Another problem in data-driven modeling is the effect of "cherry-picking" a.k.a. selection bias. Our main contribution is to extend the recently developed parametric programming approach for selective inference to high-order interaction models. Exhaustive search over the cherry tree (all possible interactions) can be daunting and impractical even for a small-sized problem. We introduced an efficient pruning strategy and demonstrated the computational efficiency and statistical power of the proposed method using both synthetic and real data.