Abstract
We consider the following conditional linear regression problem: the task is to identify both (i) a $k$-DNF condition $c$ and (ii) a linear rule $f$ such that the probability of $c$ is (approximately) at least $\mu$, and the $L_p$ loss of $f$ on the subpopulation satisfying $c$ is minimized.
Introduction
In many real-world datasets, a single global model fails because the population is highly heterogeneous. However, there might be a specific segment of the population—say, patients over 65 on a specific medication—where a simple linear model works perfectly. The challenge is identifying both the interpretable rule defining the segment (modeled as a $k$-DNF, an OR of ANDs) and the sparse linear regression weights simultaneously.
Previous algorithms for this "conditional sparse $\ell_p$-norm regression" problem suffered from a significant drawback: if an optimal subpopulation of size $\mu$ existed, they could only guarantee finding a much smaller subpopulation of size $\Omega(\mu/n^k)$ (where $n$ is the number of Boolean features). They also yielded a loose $O(n^k)$ approximation of the target loss. This research aims to close that gap, finding a subpopulation that is practically the same size as the optimal one, with much tighter error bounds.
Methodology
The proposed approach utilizes sparsifiers for linear systems (using techniques like Lewis weights). While sparsifiers are typically used to speed up algorithms by reducing data points while preserving problem geometry, here they are used to reduce the system size enough to feasibly exhaustively enumerate all possible candidate regression coefficients.
Once a list of candidate linear predictors is generated, each is evaluated by scoring data points based on their prediction loss. These scores are then processed by a Weighted Conditional Distribution Search algorithm. This subroutine searches for a $k$-DNF condition that captures a large enough fraction of the data while keeping the weighted loss low. This pipeline is also adapted for reference class regression, where the goal is to find the best subpopulation that specifically includes a given query point to make a tailored prediction for that instance.
Key Results
The algorithm provides significant theoretical and empirical improvements. Theoretically, it guarantees finding a condition with probability $(1-\eta)\mu$, essentially matching the optimal subpopulation size $\mu$. It also improves the loss approximation factor from $O(n^k)$ to $\tilde{O}(\epsilon n^{k/2})$, or even $\tilde{O}(\epsilon g \log \log(n^k))$ if the underlying rule has $g$ terms.
Empirically, the algorithm was tested on standard real-world regression datasets, including Boston housing, Body fat, Cpusmall, and Space. As shown in Figure 1, the algorithm's performance on Risk-Coverage curves demonstrates its ability to maintain low error while identifying significant subpopulations. On the Boston housing dataset, at 25% coverage, it output a concrete, logical rule defining exactly which houses the model could accurately price (e.g., based on nitric oxide concentration and distance to employment centers).
Furthermore, synthetic tests showed that the new $\ell_2$-norm algorithm is robust to noise. Under 5% noise, it successfully recovered planted 2-DNF rules where baseline sup-norm ($\ell_\infty$) algorithms failed. The $\ell_\infty$ baselines were maximally sensitive to outliers, often failing to segment the data effectively by returning rules that included nearly the entire dataset.
Discussion and Future Work
A primary advantage of this method is that interpretability is a core feature; unlike "learning with rejection" models that output black-box confidence scores, this method outputs human-readable $k$-DNF rules. This allows practitioners to understand exactly for whom the model is accurate.
However, the algorithm faces limitations regarding computational weight, as the running time scales exponentially with the sparsity parameter $s$. Future work will focus on overcoming this exponential dependence and improving the loss bounds for reference class regression, which currently still suffers from an $O(n^k)$ blow-up. Additionally, the question of whether the current theoretical blow-up in loss is optimal remains open, as no computational lower bounds currently exist for this specific problem.
Summary updated