Removing $$\delta $$-dependence in minimal interpretable model learning: distribution conditions and structural parameters

Abstract

Learning minimal interpretable models (e.g., decision trees, decision sets, and binary decision diagrams) is computationally challenging, yet increasingly important in high-stakes settings. We use decision trees as a canonical case study, but the proposed structural parameter is solver-agnostic. Recent parameterized-complexity results show fixed-parameter tractability when parameterized by model size
s
and a data-dependent conflict parameter


$$\delta $$

δ



, the maximum Hamming disagreement between oppositely labeled examples. We show that


$$\delta $$

δ



is highly noise-sensitive: under small relevant support and independent irrelevant features,


$$\delta $$

δ



typically scales with ambient dimension, making


$$\delta $$

δ



-based branching uninformative. We introduce a distribution-aware alternative, the
effective conflict width


$$\kappa _\tau $$


κ
τ




, obtained by restricting conflicts to features whose relevance exceeds a threshold. We instantiate this idea as structure-guided branching (SGB), which branches on relevance-filtered conflict features and safely falls back to full


$$\delta $$

δ



-branching. Using conflict-driven branching simulations to isolate search-tree effects, we find that


$$\kappa _\tau $$


κ
τ




can remain stable as dimension grows and yields substantial reductions in explored search nodes on synthetic data and multiple real datasets. These results suggest structural parameters can improve the noise robustness of exact interpretable learning and can serve as solver-agnostic pruning signals.