---
title: "Optimal Subgroup Discovery at Every Support Threshold"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.03053v1"
permalink: "https://feed.astralor.com/items/itm_d778416cc4393bab2e201da4"
published: "2026-11-02T12:48:04.000Z"
score: 58
channel: "ai"
tags: ["Optimal Subgroup Discovery","Every Support Threshold","Subgroup","Existing","Kullback-Leibler","Under","Pareto"]
---

# Optimal Subgroup Discovery at Every Support Threshold

## 速览

Subgroup discovery aims to identify regions of the feature space where a target variable deviates from its marginal distribution. A fundamental challenge in this problem is the trade-off between a subgroup's deviation a…

## 关键点

- Subgroup discovery aims to identify regions of the feature space where a target variable deviates from its marginal distribution.
- A fundamental challenge in this problem is the trade-off between a subgroup's deviation and its support: small subgroups can be highly deviating but statistically meaningless, while large ones cannot deviate much by con…
- Existing methods tackle this challenge by collapsing the two into a single scalar quality measure, implicitly committing to one particular trade-off and making it difficult to recover the most deviating subgroup under a…

## 全文

Subgroup discovery aims to identify regions of the feature space where a target variable deviates from its marginal distribution. A fundamental challenge in this problem is the trade-off between a subgroup's deviation and its support: small subgroups can be highly deviating but statistically meaningless, while large ones cannot deviate much by construction. Existing methods tackle this challenge by collapsing the two into a single scalar quality measure, implicitly committing to one particular trade-off and making it difficult to recover the most deviating subgroup under a user-specified support constraint. We instead provide the first theoretical and structural characterization of optimal subgroups with maximum Kullback-Leibler (KL) divergence under arbitrary support constraints. Under a partition-based generative model, where the feature space decomposes into regions of homogeneous conditional distributions of the target variable called atoms, we prove that every point on the deviation-support Pareto front is a union of whole atoms together with at most one fractional atom. This reduces an uncountable search to a finite combinatorial problem. Guided by this theory, we propose a simple two-step recipe: learn a homogeneous partition, then select atoms greedily. Across 19 benchmark datasets, it finds the most deviating subgroups at a range of support thresholds, and reliably improves subgroups returned by existing methods when applied as a post-processing step. These results empirically validate the sufficiency and necessity of our theoretical contributions.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_d778416cc4393bab2e201da4