Conditional Sparse l_p-norm Regression With Optimal Probability

We consider the following conditional linear regression problem: the task is to identify both (Formula present) condition c and (ii) a linear rule f such that the probability of c is (approximately) at least some given bound µ, and f minimizes the l_ploss of predicting the target 2 in the distribution of examples conditioned on c. Thus, the task is to identify a portion of the distribution on which a linear rule can provide a good fit. Algorithms for this task are useful in cases where simple, learnable rules only accurately model portions of the distribution. The prior state-of-the-art for such algorithms could only guarantee to find a condition of probability (Formula present) when a con-dition of probability u exists, and achieved an (Formula present)-approximation to the target loss, where n is the number of Boolean attributes. Here, we give efficient algorithms for solv-ing this task with a condition c that nearly matches the probability of the ideal condition, while also improving the approximation to the target loss. We also give an algorithm for finding a k-DNF reference class for prediction at a given query point, that obtains a sparse regression fit that has loss within (Formula present) of op-timal among all sparse regression parameters and sufficiently large k-DNF reference classes containing the query point.