Talk: Brendan Juba: Conditional Sparse Linear Regression

Wednesday, August 24, 2016 - 4:00pm to 5:00pm
Brendan Juba
Washington University in St. Louis

We consider the problem of jointly identifying a significant (but perhaps small) segment of a population in which there is a highly sparse linear regression fit, together with the coefficients for the linear fit. This is intended to serve as a principled alternative to the practice of clustering the data under a variety of methods to see if any yield clusters that can be modeled well. We give algorithms for such problems when this unknown segment of the population ("cluster") is described by a k-DNF condition and the regression fit is s-sparse for constant k and s. We note evidence that k-DNFs are essentially the most expressive natural representation for which this problem is tractable.

Based on joint work with Ben Moseley (WUSTL).