Structured Credal Learning

Varun Venkatesh, Eyke Hüllermeier, Bernd Bischl, Mina Rezaei · 2026

Read Structured Credal Learning by Varun Venkatesh, Eyke Hüllermeier, Bernd Bischl, Mina Rezaei (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14070.txt.

Introduction

Venkatesh and co-authors split two sources of uncertainty that robust learning often lumps together. One source is covariate shift, and the other is noisy labels. Their structured credal learning framework keeps them apart. Total uncertainty splits into parts from each source, with a gating effect between them. Benign-looking covariate shifts can sharply raise the joint uncertainty. Robust training over these sets becomes a tractable min-max problem, with finite-sample bounds to back it.

Catalog record

CREATORVarun Venkatesh, Eyke Hüllermeier, Bernd Bischl, Mina Rezaei
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106014
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14070

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Structured Credal Learning Varun Venkatesh, Eyke Hüllermeier, Bernd Bischl, Mina Rezaei Abstract Real-world learning tasks often encounter uncertainty due to covariate shift and noisy or inconsistent labels. However, existing robust learning methods merge these effects into a single distributional uncertainty set. In this work, we introduce a novel structured credal learning framework that explicitly separates these two sources. Specifically, we derive geometric bounds on the total variation diameter of structured credal sets and demonstrate how this quantity decomposes into contributions from covariate shift and expected label disagreement. This decomposition reveals a gating effect : covariate modulates how much label disagreement contributes to the joint uncertainty such that seemingly benign covariate shifts can substantially increase the effective uncertainty. We also establish finite-sample concentration bounds in a fixed covariate regime and demonstrate that this quantity can be efficiently estimated. Lastly, we show that robust optimization over these structured credal sets reduces to a tractable discrete min–max problem, avoiding ad-hoc robustness parameters. Overall, our approach provides a principled and practical foundation for robust learning under combined covariate and label mechanism ambiguity. 1 Introduction Predictive uncertainty is crucial for developing reliable and trustworthy machine learning algorithms used to make critical decisions, such as medical diagnosis ( Bordes et al. 2010 ; Shalit et al. 2017 ; Wang et al. 2025b ) , drug discovery ( Svensson et al. 2025 ) , and autonomous driving ( Chytas et al. 2024 ) . This uncertainty arises from multiple, fundamentally distinct sources: distributional mismatch and inherent target ambiguity ( Hüllermeier & Beringer 2005 ; Gal & Ghahramani 2016 ) . Specifically, covariate shift occurs when the input distribution differs between training and test time while the conditional labeling mechanism distribution remains unchanged. We refer to label mechanism ambiguity for uncertainty in the conditional label distribution arising from measurement noise, annotator variability, or intrinsic class overlap, and it imposes a limit on achievable prediction accuracy ( Bordes et al. 2010 ; Natarajan et al. 2013 ; Gruber et al. 2025 ; Huang & Chong 2023 ) . Crucially, these sources demand different operational remedies—distributional adaptation for the former, improved supervision or label reconciliation for the latter. Most existing methods primarily address these challenges in isolation and typically do not decouple marginal and conditional uncertainty in robustness certificates. Domain adaptation ( Chen et al. 2025 ; Tamang et al. 2025 ) , importance weighting ( Li et al. 2020 ; Sugiyama et al. 2007 ) , invariant learning methods ( Li et al. 2024 ; Nguyen et al. 2025a ) , and distributionally robust optimization (DRO) ( Nguyen et al. 2025c ; Jeong et al. ; Zhu et al. 2025 ; Nguyen et al. 2025b ) have shown strong performance in mitigating covariate shift by aligning feature distributions across environments, typically under the assumption of stable labeling mechanisms. In contrast, research on label mechanism ambiguity focuses on robust training or uncertainty-aware prediction under fixed input distributions ( Hüllermeier & Beringer 2005 ; Hüllermeier 2014 ; Cai et al. 2025b ; Zhou et al. 2022 ) . Recent works ( Li & Zhu 2024 ; Caprio et al. 2024 ) attempt to diagnostically decompose prediction error into marginal and conditional components. For example, the credal learning framework of Caprio et al. 2024 , grounded in imprecise probability theory ( Augustin et al. 2014 ) , replaces single distributions with convex sets of distributions (credal sets) to more faithfully represent uncertainty, limited knowledge, and data variability. However, it does not provide formal predictive robustness guarantees that can explicitly attribute observed errors to covariate shift versus label mechanism ambiguity. In this paper, we propose a structured credal learning framework that explicitly distinguishes the sources of uncertainty into covariate shift and label mechanism ambiguity. Instead of modeling distributional uncertainty as an unstructured set of joint distributions, we construct credal sets as convex combinations of product measures formed by pairing plausible covariate distributions with plausible labeling mechanisms. Our main theoretical contribution is a geometric characterization of the resulting credal set under total variation (TV) distance. We show that its diameter decomposes into interpretable contributions from covariate shift and expected label mechanism ambiguity , revealing a precise interaction between environmental variation and annotator ambiguity. We further establish concentration bounds in a fixed covariate regime with uncertain labeling mechanisms and prove that the credal diameter equals the maximum pairwise annotator disagreement rate . This transforms an abstract robustness parameter into a directly measurable statistic that admits tight finite-sample concentration guarantees. Finally, we show that robust learning over a structured credal set admits a tractable DRO formulation where the worst-case risk is attained at an extreme point, reducing learning to a finite min–max selection. This avoids extrinsic radius tuning while restricting the adversary to semantically meaningful alternatives. Taken together, our contributions are: (i) We introduce a structured credal learning framework that explicitly decomposes distributional uncertainty into covariate shift and label mechanism ambiguity. (ii) We derive explicit bounds on the total-variation diameter of structured credal sets and show that it decomposes along the same two sources of uncertainty linked by a gating interaction. This yields interpretable robust generalization bounds directly attributable to each source. (iii) In the fixed-covariate regime, we prove the credal diameter equals the maximum pairwise disagreement rate — a directly measurable statistic estimable at parametric rate — and establish a minimax lower bound. (iv) We show that robust optimization over structured credal sets reduces to a finite min–max problem over extreme-points, with an intrinsic, observable robustness radius that requires no extrinsic tuning. 2 Related work Our work bridges credal learning theory and DRO. Credal learning Theory (CLT) ( Caprio et al. 2024 ) extends statistical learning theory grounded on imprecise probability ( Augustin et al. 2014 ) . Recent work leverages this perspective to derive finite-sample generalization guarantees whose tightness is controlled by the total variation diameter \mathrm{diam}_{\mathrm{TV}}(\mathcal{P}) of the credal set ( Löhr et al. 2025 ; Javanmardi et al. 2024 ) . Existing CLT formulations ( Shariatmadar et al. 2025 ; Wang et al. 2025a ; Mubashar et al. 2025 ; Caprio et al. 2025 ) , however, treat uncertainty at the level of the joint distribution over (X,Y) , thereby conflating heterogeneity in the covariate marginal P_{X} with ambiguity in the conditional labeling mechanism P_{Y|X} . In contrast, we introduce a structured credal construction that factorizes uncertainty across covariate distributions and labeling mechanisms enabling a geometric decomposition of the induced diameter into interpretable covariate-driven and label-driven components. Distributionally robust optimization defines uncertainty sets as Wasserstein or f -divergence balls around the empirical distribution ( Ben-Tal et al. 2013 ; Ai & Ren 2024 ; Cai et al. 2025a ; Zhu et al. 2021 ; Ehyaei et al. 2024 ) , requiring specification of an extrinsic radius parameter and often producing worst-case distributions with limited semantic interpretability. In contrast, our uncertainty set is the convex hull of coherent generative “worlds” (covariate \times labeling mechanism), leading to an intrinsic, data-driven robustness quantity via the credal diameter decomposition, This yields robustness certificates that are directly attributable to distinct sources of distributional variability and a finite extreme-point reduction of the robust objective. 3 Structured Credal Learning Framework 3.1 Preliminary: Credal Learning Theory Notation. Let \mathcal{X} and

Read the complete text