skip to primary navigation skip to content
Loading Events

« All Events

  • This event has passed.

BSU Seminar: “The xyz algorithm for fast interaction search in high-dimensional data”

May 30, 2017 @ 2:30 pm - 3:30 pm


By Dr Rajen Shah
Statistical Laboratory, University of Cambridge

Abstract: 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 Gian Thanei and Nicolai Meinshausen (ETH Zurich).


May 30, 2017
2:30 pm - 3:30 pm
Event Category:


MRC Biostatistics Unit


Large Seminar Room, IPH
Institute of Public Health, Forvie Site
Cambridge, CB2 0SR United Kingdom
+ Google Map
View Venue Website