Conditional Sparse Linear Regression
  Machine learning and statistics typically focus on building models that
capture the vast majority of the data, possibly ignoring a small subset of data
as "noise" or "outliers." By contrast, here 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. We contend that such tasks are of interest both because the
models themselves may be able to achieve better predictions in such special
cases, but also because they may aid our understanding of the data. We give
algorithms for such problems under the sup norm, when this unknown segment of
the population is described by a k-DNF condition and the regression fit is
s-sparse for constant k and s. For the variants of this problem when the
regression fit is not so sparse or using expected error, we also give a
preliminary algorithm and highlight the question as a challenge for future
work.
