Work in machine learning and statistics commonly focuses on building models that capture the vast majority of data, possibly ignoring a segment of the population as outliers. However, there does not often exist a good model on the whole dataset, so we seek to find a small subset where there exists a useful model. We are interested in finding a linear rule capable of achieving more accurate predictions for just a segment of the population. We give an efficient algorithm with theoretical analysis for the conditional linear regression task, which is the joint task of identifying a significant segment of the population, described by a k-DNF, along with its linear regression fit.

In this case, we would be interested used in biological and social sciences to predict events and to in identifying a segment of the population for which describe possible relationships between variables. When addressing a linear rule is highly predictive of the price of certain cars, the task of prediction, machine learning and statistics whereas this linear rule may not provide a good prediction commonly focus on capturing the vast majority of data, overall in the larger population. Let us imagine that for this occasionally ignoring a segment of the population as "outliers" data set, and for a target fraction of the population, we found or "noise," which could be helpful to better understand a simple rule that describes the subpopulation, along with the data. Previous work by Juba (2016) gave an algorithm its linear fit.