The xyz algorithm for fast interaction search in high-dimensional data
OPEN ACCESS
Loading...
Author / Producer
Date
2018
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
When performing regression on a data set with p variables, it is often of interest to go beyond using main linear effects and include interactions as products between individual variables. For small-scale problems, these interactions can be computed explicitly but this leads to a computational complexity of at least O(p2) if done naively. This cost can be prohibitive if p is very large.
We introduce a new randomised algorithm that is able to discover interactions with high probability and under mild conditions has a runtime that is subquadratic in p. We show that strong interactions can be discovered in almost linear time, whilst finding weaker interactions requires O(pα) operations for 1<α<2 depending on their strength. The underlying idea is to transform interaction search into a closest pair problem which can be solved efficiently in subquadratic time. The algorithm is called xyz and is implemented in the language R. We demonstrate its efficiency for application to genome-wide association studies, where more than 1011 interactions can be screened in under 280 seconds with a single-core 1.2 GHz CPU.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
19
Pages / Article No.
37
Publisher
Microtome Publishing
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
interactions; high-dimensional data; regression; computational tradeoffs; close pairs
Organisational unit
03990 - Meinshausen, Nicolai (ehemalig) / Meinshausen, Nicolai (former)