MATH - Seminar on Statistics and Data Science - Searching for Interactions in Linear Time
We tackle the problem of variable selection with a focus on discovering interactions between variables. With p variables, there are O(p^k) possible interactions of order k making exhaustive search infeasible. We show that it is nonetheless possible to identify the variables involved in interactions (of any order) with only linear computation cost, O(p), and in a nonparametric fashion. Our algorithm is based on minimizing a non-convex objective, carefully designed to have a favorable landscape. We provide finite sample guarantees on both false positives (we show all stationary points of the objective exclude noise variables) and false negatives (we characterize the sample sizes needed for gradient descent to converge to a "good’’ stationary point).
Feng Ruan is a postdoc in the Department of EECS at Berkeley, advised by Prof. Michael Jordan.He obtained his PhD from the Department of Statistics at Stanford University, where he is advised by Prof. John Duchi. He is broadly interested in developing theory and algorithms for high dimensional statistics, for stochastic convex and non-convex optimization, and for inference under resource constraints.