BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The xyz algorithm for fast interaction search in high-dimensional 
 data - Rajen Shah (University of Cambridge)
DTSTART:20180118T160000Z
DTEND:20180118T164500Z
UID:TALK97807@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:When performing regression on a dataset with $p$ variables\, i
 t is often of interest to go beyond using main effects and include interac
 tions as products between individual variables. However\, if the number of
  variables $p$ is large\, as is common in genomic datasets\, the computati
 onal cost of searching through $O(p^2)$ interactions can be prohibitive. I
 n this talk I will introduce a new randomised algorithm called xyz that is
  able to discover interactions with high probability and under mild condit
 ions has a runtime that is subquadratic in $p$. The underlying idea is to 
 transform interaction search into a much simpler close pairs of points pro
 blem.  We will see how strong interactions can be discovered in almost lin
 ear time\, whilst finding weaker interactions requires $O(p^u)$ operations
  for $1<u<2$ depending on their strength. An application of xyz to a genom
 e-wide association study shows how more than $10^{11}$ interactions can be
  screened in minutes using a standard laptop.  This is joint work with Gia
 n Thanei and Nicolai Meinshausen (ETH Zurich).
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR