Metraipolis › archive › dc_c7bc4b96fec7

Optimal Subgroup Discovery at Every Support Threshold — arXiv:2611.03053

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.03053
License (as archived)
CC0-1.0
Archived
2026-11-03T11:23:04.564Z
SHA-256 of the archived text
79c078ca6dd4e66c810cad50f64a283832eb4aac932d9c298fc623211f3fd094
Stable URL of this page
https://metraipolis.com/documento/dc_c7bc4b96fec7

How to cite

Optimal Subgroup Discovery at Every Support Threshold — arXiv:2611.03053 — arXiv (en), https://arxiv.org/abs/2611.03053 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c7bc4b96fec7 (Metraipolis archive dc_c7bc4b96fec7, sha256 79c078ca6dd4e66c810cad50f64a283832eb4aac932d9c298fc623211f3fd094)
BibTeX
@misc{dcc7bc4b96fec7,
  title = {Optimal Subgroup Discovery at Every Support Threshold — arXiv:2611.03053},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03053},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c7bc4b96fec7; sha256 79c078ca6dd4e66c810cad50f64a283832eb4aac932d9c298fc623211f3fd094},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03053. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.03053 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:02:37.668Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).