Research map / Learning theory and algorithms / Combinatorial and search optimization
The xyz algorithm for fast interaction search in high-dimensional data
Gian-Andrea Thanei, Nicolai Meinshausen, Rajen D. Shah
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use xyz instead of naive random-pair search on LURIC data | interaction search on LURIC · LURIC SNP (p=687253) | speedup over naive search: about 20 000 times faster empirically (30 000 theoretical) | Improved |
| use xyz instead of epiq and naive search on original LURIC data | interaction search · LURIC SNP original | strongest interaction found at fixed time | Mixed |
| implant artificial strong interaction (gamma 0.8 or 0.9) and compare xyz to competitors | interaction search · LURIC SNP with implanted interaction | interaction strength vs time | Improved |
| use xyz regression instead of two-stage Lasso | regression · Simulated regression, non-hierarchical (setting 2) | normalised l2 prediction error | Improved |
| use xyz instead of brute-force Lasso with all interactions on simulated data | regression · Simulated regression, p 250-1000 | run time at similar error | Improved |
| use xyz instead of glmnet Lasso with all interactions | regression · Riboflavin, Kemmeren, Climate (p=2000) | run time: around 100 times faster for p=2000 | Improved |
| use xyz instead of glmnet Lasso with all interactions | regression · Riboflavin, Kemmeren, Climate (p=2000) | normalised out-of-sample l2 error | No clear effect |
| increase noise variance sigma^2 from 0.1 to 5 | binary interaction model · Binary interaction strength vs noise | interaction strength of pair (1,2): 0.99 -> 0.67 | Hurt |
| increase interaction strength gamma on dimension scaling test | xyz run time · Synthetic, p 1000-30000 | run time | Improved |
Closest papers by meaning
- The Kernel Interaction Trick: Fast Bayesian Discovery of Pairwise Interactions in High Dimensions (ICML 2019 · similarity 0.88)
- WHInter: A Working set algorithm for High-dimensional sparse second order Interaction models (ICML 2018 · similarity 0.88)
- Permutation-Free High-Order Interaction Tests (ICML 2025 · similarity 0.84)
- Proxy-Based Approximation of Shapley and Banzhaf Interactions (NeurIPS 2026 · similarity 0.83)
- Interventional Causal Discovery in a Mixture of DAGs (NeurIPS 2024 · similarity 0.83)
- Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles (AAAI 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
