The xyz algorithm for fast interaction search in high-dimensional data

Jeudi 15 mars 14:00-15:00 - Rajen Shah - University of Cambridge, Department of Pure Mathematics and Mathematical Statistics

Résumé : When performing regression on a dataset with p variables, it is often of interest to go beyond using main effects and include interactions as products between individual variables. However, if the number of variables p is large, as is common in genomic datasets, the computational cost of searching through O(p^2) interactions can be prohibitive. In this talk I will introduce a new randomised algorithm called xyz that is able to discover interactions with high probability and under mild conditions has a runtime that is subquadratic in p. The underlying idea is to transform interaction search into a much simpler closest pair problem. We will see how strong interactions can be discovered in almost linear time, whilst finding weaker interactions requires O(p^u) operations for 1<u<2 depending on their strength. An application of xyz to a genome-wide association study shows how more than 10^11 interactions can be screened in minutes using a standard laptop.
This is joint work with Nicolai Meinshausen and Gian Thanei (ETH Zurich).

The xyz algorithm for fast interaction search in high-dimensional data  Version PDF