Conditional Sparse Linear Regression
This addresses the need for models that capture special cases in data, potentially improving predictions and understanding, but it is incremental as it builds on existing sparse regression and condition identification methods.
The paper tackles the problem of identifying a small population segment with a highly sparse linear regression fit and estimating its coefficients, proposing algorithms for cases where the segment is described by a k-DNF condition and the fit is s-sparse for constant k and s.
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.