Research map / Learning theory and algorithms / Prediction and decision losses
Learning With Multi-Group Guarantees For Clusterable Subpopulations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes endogenous subgroups model where subpopulations are mixture components, defines discriminant and likelihood calibration errors, and uses a multi-objective online multicalibration algorithm achieving O(T^{1/2}) without separation, beating cluster-then-predict's O(T^{2/3}).
Problem
Online calibration guarantees for subpopulations that are defined endogenously as clusters (mixture components) of the feature distribution, when group membership is uncertain and must be learned.
Approach
Defines per-subgroup calibration errors via mixture components using either hard (argmax) or soft (posterior-weighted) attribution, and handles all plausible clusterings at once by covering the distinguisher class with bounded pseudodimension and running online multicalibration, rather than explicitly learning clusters first.
Key results
- Multi-objective online multicalibration achieves O(T^{1/2}) discriminant and likelihood calibration error without cluster separation, versus O(T^{2/3}) for cluster-then-predict under separation.
- Pseudodimension of group membership distinguishers for exponential-family mixtures is bounded by O(dim T(x)) times k log factors, giving Gaussian mixture bounds of O(sqrt(T(d^2 k log T log k))) for DCE.
- Per-subgroup calibration guarantees are provable without separation, whereas learning Gaussian mixture cluster assignments requires sample complexity Omega(d/(eps^2 gamma^6)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace cluster-then-predict with simultaneous multi-objective calibration | Online discriminant calibration for clusterable subpopulations · Two isotropic Gaussian components with separation \(\|\mu_1-\mu_2\| \geq \gamma\) | discriminant calibration error: O(d^{1/3} T^{2/3} \gamma^{-4/3} + \sqrt{T \log(1/\delta)}) -> O(\sqrt{T}) | Helped |
| Replace cluster-then-predict with simultaneous multi-objective calibration | Online likelihood calibration for clusterable subpopulations · Gaussian mixtures | likelihood calibration error: \widetilde O(T^{2/3}) -> \widetilde O(\sqrt T) | Helped |
| Use cluster-then-predict without separation | Online likelihood calibration · Two Gaussian components, without separation | likelihood calibration error: \widetilde O(T^{2/3}\sqrt{d}\log^{1/2}(d/\delta)) -> \widetilde O(T^{12/13}\sqrt{d}\log^{1/2}(d/\delta)) | Hurt |
| Use likelihood-based rather than most-likely-component attribution | Per-subgroup error measurement · Subgroups with uncertain membership | per-subgroup guarantee for smaller subgroups | Helped |
| Require separation between component means | Learning cluster assignments for two isotropic Gaussian components · Cluster assignment learning | sample complexity: \Omega( \tfrac d{\varepsilon^2 \gamma^6}) | Hurt |
Surprising findings
- Providing per-cluster calibration guarantees can be easier than learning the clusters: separation is needed for clustering but not for per-subgroup guarantees.
Limitations
- Results are theoretical with no empirical experiments on real data.
- Analysis restricted to i.i.d. data and mixtures of exponential families; general k-component non-isotropic cases are harder.
- Assumes subgroup mixture model is correctly specified within the class of densities.
Experimental setup
Metrics: discriminant calibration error likelihood calibration error
Baselines: cluster-then-predict
Builds on: multicalibration Blackwell approachability online calibration (Foster-Vohra style)
Closest papers by meaning
- Boosting Test Performance with Importance Sampling--a Subpopulation Perspective (AAAI 2025 · similarity 0.87)
- Diverse Prototypical Ensembles Improve Robustness to Subpopulation Shift (ICML 2025 · similarity 0.86)
- Multigroup Robustness (ICML 2024 · similarity 0.86)
- Stochastic Grouping Conformal Prediction for Effective Subgroup Reliability (NeurIPS 2026 · similarity 0.85)
- Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage (ICML 2025 · similarity 0.84)
- Self-Organized Conformal Prediction: Reducing Regional Coverage Gaps with Unsupervised Group Discovery (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.