PaperlayerView exact revision on arXiv

Source-linked AI summary

Structured Credal Learning

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

arXiv:2603.14070v1stat.MEstat.ML

TL;DR

Robust learning often conflates covariate shift with label ambiguity, despite their distinct sources. We construct credal sets from environment–labeler combinations and show that their total-variation diameter decomposes across those sources, supporting finite min–max optimization without extrinsic radius tuning.

  • Problem

    Existing credal learning can compress covariate shift and label mechanism ambiguity into one diameter, obscuring which source contributes to the robustness penalty.

    Source: §3.1 · p. 2

  • Method

    The framework forms structured credal sets from plausible covariate distributions paired with plausible labeling mechanisms.

    Source: §1 · p. 2, §3.2 · p. 3

  • Results

    The TV diameter separates covariate-shift and label-ambiguity contributions, equals maximum pairwise annotator disagreement under fixed covariates, and supports finite extreme-point min–max optimization.

    Source: §1 · p. 2, §8 · p. 8

  • Takeaways & Limitations

    The robustness quantity can be intrinsic to the structured set rather than an extrinsically tuned radius.

    Source: §1 · p. 2, §8 · p. 8

    The framework assumes finite collections of environments and labelers and requires their explicit specification or estimation.

    Source: §9 · p. 8

Abstract

from arXiv · show

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

Reliable learning must contend with both covariate shift and ambiguity in labels, but existing approaches often address them separately or combine them without distinguishing their contributions. This paper proposes structured credal sets that preserve the distinction and characterizes their uncertainty geometrically.

1. Introduction

  • Existing methods often address the two sources in isolation, and prior credal learning does not formally attribute robustness errors to either source.Covariate-focused methods typically assume stable labeling mechanisms, while label-ambiguity research often assumes fixed inputs.Source: §1 · p. 1
  • The framework separates covariate shift from label mechanism ambiguity, two distinct sources of predictive uncertainty in critical learning tasks.The paper identifies medical diagnosis, drug discovery, and autonomous driving as examples of critical applications.Source: §1 · p. 1
  • Structured credal sets combine plausible covariate distributions with plausible labeling mechanisms, explicitly preserving both sources of uncertainty.The construction uses convex combinations of product measures formed by pairing the two kinds of plausible distributions.Source: §1 · pp. 1–2
  • The total-variation diameter decomposes into covariate-shift and expected label-ambiguity contributions, with an interaction between environmental variation and annotator ambiguity.In the fixed-covariate regime, the diameter equals maximum pairwise annotator disagreement and admits finite-sample concentration guarantees.Source: §1 · p. 2
  • Robust optimization over the structured set reduces to a finite min–max problem over extreme points and avoids extrinsic radius tuning.The adversary is restricted to semantically meaningful alternatives.Source: §1 · p. 2

2. Related work

Prior credal learning theory can conflate uncertainty in covariate distributions with uncertainty in labeling mechanisms, while common DRO sets use externally specified radii. This work factorizes those sources into coherent environment–labeler worlds and uses the resulting structure for interpretable robustness.

2. Related work

  • Existing credal learning formulations treat uncertainty over the joint distribution, conflating covariate-marginal heterogeneity with conditional labeling ambiguity.The structured construction instead factorizes uncertainty across covariate distributions and labeling mechanisms.Source: §2 · p. 2
  • The structured credal construction decomposes its diameter into interpretable covariate- and label-driven components and reduces the robust objective to finitely many extreme points.Its robustness quantity is intrinsic to the credal set rather than an externally tuned radius.Source: §2 · p. 2
  • Wasserstein and f-divergence DRO balls require an extrinsic radius and can yield worst-case distributions with limited semantic interpretability.The paper contrasts these balls with uncertainty sets built from coherent covariate–labeling worlds.Source: §2 · p. 2

3. Structured Credal Learning Framework

The framework replaces a single undifferentiated uncertainty set with a structured model that keeps covariate variation distinct from labeling uncertainty. It builds joint distributions from environment–labeler pairs and takes their convex hull as the structured credal set.

3.1. Preliminary: Credal Learning Theory

  • Credal learning replaces a single data-generating distribution with a set of plausible distributions and bounds target risk, but its diameter can obscure whether uncertainty comes from covariates or labels.The framework therefore preserves those sources as distinct components.Source: §3.1 · pp. 2–3

3.2. Covariate–Labeling Uncertainty

  • The model represents uncertainty in two stages: sample features from a plausible covariate distribution, then labels from a plausible conditional labeling mechanism.The feature distributions represent environments, while conditional distributions represent labelers.Source: §3.2 · p. 3

3.3. Structured Credal Set

  • Each environment–labeler pair defines a joint distribution, and the structured credal set is their convex hull.This construction represents uncertainty over which coherent generative world, or mixture of worlds, may occur at deployment.Source: §3.3 · p. 3
  • For the structured credal set, the supremum of the stated functions over the set or its pairs is attained at its extreme points.This property supports finite extreme-point optimization.Source: §3.3 · p. 3

4. Theoretical Analysis: Geometry of the Structured Credal Set

The analysis decomposes total-variation distances in structured credal sets into covariate and labeler contributions, with their interaction governed by how environments expose regions of disagreement. It then bounds the set’s diameter using these components.

4.1. Total Variation Decomposition

  • With a fixed environment, joint TV distance equals expected pointwise labeler disagreement; with a fixed labeler, it equals the distance between environment marginals.The latter equality holds because the invariant labeler redistributes probability across labels without diluting the feature-marginal discrepancy.Source: §4.1 · pp. 3–4
  • Theorem 4.3 bounds joint distance when both environment and labeler vary, with the environment gating how much labeler disagreement is visible.Disagreement affects the joint distance only when the environment places sufficient mass in the region where labelers disagree.Source: §4.1 · p. 4
  • Figure 1 illustrates that joint distance spikes when a sliding environment concentrates mass where two labelers disagree, despite covariate shift remaining approximately 0.38.The blue line is the theoretical upper bound from Theorem 4.3.Source: Figure 1 · p. 4

4.2. Diameter Bounds for Product Credal Sets

  • The diameter bounds include the dominant covariate or labeling uncertainty, while overlap-limited disagreement can contribute only on the feature mass shared by environments.When environments overlap broadly, disagreement can add its full expected magnitude; outside the overlap, covariate shift already saturates the uncertainty.Source: §4.2 · p. 5
  • The upper bound is tight when covariate supports are disjoint or label disagreement is constant across inputs, and the resulting generalization penalty separates covariate and effective-labeling components.The stable-environment case is treated as a separate pure-labeling regime.Source: §4.2 · p. 5

5. The Pure Labeling Uncertainty Regime

In the pure labeling uncertainty regime, inputs come from a fixed population and multiple labeling mechanisms may disagree. For deterministic hard labels, the credal diameter is characterized exactly by the maximum pairwise disagreement rate.

5. The Pure Labeling Uncertainty Regime

  • A fixed dataset labeled by multiple annotators is one motivating setting for pure labeling uncertainty, where the covariate-shift term vanishes.The stated estimation assumptions capture independent multi-annotator labeling without requiring a latent ground truth or parametric noise model.Source: §5 · p. 5
  • The geometric characterization holds independently of the multi-annotator assumptions used for estimation and concentration.Those assumptions are required only for estimation and concentration.Source: §5 · p. 5

5.1. Geometric Characterization: Diameter as Disagreement

  • For deterministic hard labels, the total-variation diameter equals the maximum pairwise disagreement rate among labelers.The fixed-covariate setting makes the diameter a directly measurable disagreement statistic.Source: §5.1 · p. 5

2. Soft Label Regime (Exact): If probability vectors p(j)

The section gives operational characterizations of uncertainty under different label-observation regimes, then treats the credal diameter as an estimable quantity and as an irreducible component of robust generalization. In stochastic hard-label settings, observed disagreement provides a conservative safety certificate.

2. Soft Label Regime (Exact): If probability vectors p(j)

  • With soft label probability vectors, the diameter is proportional to expected L1 distance, while observed stochastic hard-label disagreement provides a conservative upper bound.The stochastic hard-label diameter is nonidentifiable because the labelers’ conditional distributions are not observable; the independent coupling yields a valid upper bound.Source: §2 · p. 6

5.2. The Observable Radius: From Hyperparameter to Statistical Estimation

  • The diameter can be estimated at rate O(n^-1/2), with only logarithmic dependence on the number of labelers.For 10 annotators, the stated example requires about 375 samples for precision 0.1 at 95% confidence.Source: §5.2 · p. 6
  • The estimation procedure needs no specified error structure or ground-truth labels and assumes only conditional independence of annotators.The finite-sample guarantee applies to observed pairwise disagreement in the stochastic hard-label regime, where that rate upper-bounds the true diameter.Source: §5.2 · p. 6

5.3. Robust Generalization and Optimality

  • The robust generalization bound separates source-distribution learning error from labeling uncertainty, which reflects genuine task ambiguity rather than necessarily a model failure.The source-distribution term vanishes as sample size grows, whereas the labeling-uncertainty term is not reduced by more data from the same ambiguous process.Source: §5.3 · p. 6
  • In the fixed-covariate regime, the diameter is both an observable disagreement statistic and the minimax price of ambiguity, an irreducible floor on robust generalization.The lack of labeler consensus cannot be reduced by collecting more data from the same ambiguous process.Source: §5.3 · pp. 6–7

6. Optimization

The optimization section contrasts classical distributional robustness with a structured alternative. The structured credal set reduces the infinite-dimensional problem to a discrete minimax game over plausible environment–labeler worlds.

6. Optimization

  • Classical DRO uses a distributional ball whose radius is difficult to specify and whose optimization ranges over an infinite-dimensional space.Worst-case perturbations may also drift off the data manifold into non-semantic noise.Source: §6 · p. 7

6.1. Reduction to Extreme Points

  • The infinite-dimensional DRO problem reduces exactly to discrete minimax optimization over the structured credal set’s extreme points.This permits a finite set of environment–labeler worlds in place of optimization over all probability measures.Source: §6.1 · p. 7
  • The structured formulation makes the robustness radius intrinsic rather than tuned, and Nature selects the worst-case combination of environment and labeler among semantically plausible worlds.In the pure labeling regime, the objective enforces robustness to the most challenging labeler under the current hypothesis.Source: §6.1 · p. 7
  • Finite-world optimization can use greedy worst-world descent or a Log-Sum-Exp surrogate that averages per-world gradients.As its temperature decreases, the surrogate approaches hard minimax training; larger temperature moves toward uniform averaging.Source: §6.1 · pp. 7–8

7. Synthetic Experiments

Synthetic experiments test the geometric bounds and estimators under controlled settings with known ground truth. The reported results cover bound tightness, disagreement-diameter estimation, and finite-sample estimation error.

7. Synthetic Experiments

  • The experiments were designed to verify the theoretical bounds and statistical behavior of the estimators on controlled synthetic families with analytically computable quantities.This known-ground-truth setup applies to the claims tested in Sections 4 and 5.Source: §7 · p. 8
  • Across 40,000 joint distribution pairs, the bounds had essentially zero slack in pure-shift regimes and moderate slack under simultaneous joint shift.The experiments used 20 Gaussian environments and 10 soft or deterministic hard labelers; the joint-shift results are summarized in Table 1.Source: §7 · p. 8, Table 1 · p. 8
  • In the fixed-covariate regime, the diameter estimator was nearly unbiased for hard labelers and remained accurate for soft labels and increasing noise budgets.The soft-label result uses the L1-based form; the noisy-annotator estimates tracked the closed-form prediction with low error.Source: §7 · p. 8
  • Absolute estimation error decayed at the predicted O(n^-1/2) rate across covariate distributions, with negligible empirical violation probability and stable tightness ratios.The experiments also found non-vacuous bounds and robustness when scaling the number of labeling mechanisms, including large NY.Source: §7 · p. 8

8. Conclusion

The conclusion presents structured credal learning as a way to separate covariate and labeling uncertainty. Its geometric results yield an intrinsic robustness quantity and a tractable discrete robust-optimization formulation.

8. Conclusion

  • The framework decomposes distributional uncertainty into covariate distributions and labeling mechanisms.It derives sharp geometric bounds on the induced credal-set diameter and an exact characterization in the pure label-uncertainty regime.Source: §8 · p. 8
  • The credal diameter is a directly measurable robustness statistic governed by annotator disagreement, rather than a hyperparameter-dependent quantity.The conclusion describes this as replacing an ad-hoc tuned robustness radius with an intrinsic quantity determined by the structured credal set.Source: §8 · p. 8
  • Robust optimization over structured credal sets admits a tractable discrete formulation with interpretable worst-case objectives.The conclusion frames the results as a theoretical foundation for robust learning under simultaneous covariate shift and label uncertainty.Source: §8 · p. 8

9. Limitations and Future Work

The framework assumes finite collections of environments and labelers and relies on specifying or estimating them. The accompanying proof material establishes extreme-point optimization and derives distance bounds through density manipulations and alternative decomposition paths.

9. Limitations and Future Work

  • The framework assumes finite collections of environments and labelers, which may limit scalability to continuous or high-dimensional uncertainty families.Explicitly specifying or estimating candidate environments and labelers may also be challenging in fully unsupervised or highly dynamic deployment scenarios.Source: §9 · p. 8
  • Future work could extend the framework to continuous environment and annotator families, integrate it with representation learning, or model hierarchical labels and structured outputs.The paper suggests these directions as ways to broaden applicability and potentially yield finer-grained robustness guarantees.Source: §9 · p. 8

A.1. Lemma 3.5

  • Lemma 3.5 reduces maximization of continuous convex functions over the credal polytope, including separately convex functions of two arguments, to its extreme points.The proof uses the Bauer Maximum Principle and the finite extreme-point set.Source: §A.1 · p. 11

A.2.1. PROOF FOR PROPOSITION 4.1

  • The Proposition 4.1 proof uses a product-measure density representation and factors the nonnegative feature density out of the absolute value.The supplied proof passage identifies this as a step in the density-based derivation.Source: §A.2.1 · p. 11

A.2.2. PROOF FOR PROPOSITION 4.2

  • The Proposition 4.2 proof factors the joint densities into feature and conditional-label terms, then uses nonnegativity and conditional-density normalization.The derivation substitutes the integral of the conditional density, which equals one.Source: §A.2.2 · pp. 11–12

A.2.3. PROOF FOR THEOREM 4.3

  • Theorem 4.3 derives its distance bounds along two paths that change the labeler and environment in opposite orders.The proof combines triangle-inequality bounds with exact intermediate distances, then takes the minimum over the paths.Source: §A.2.3 · pp. 12–13

A.2.4. PROOF FOR THEOREM 4.5

Theorem 4.5 bounds the credal-set diameter by relating covariate shift and label disagreement, and its figure passage describes covariate mass as gating disagreement’s contribution. In the fixed-covariate regime, joint TV distance reduces to expected pointwise label disagreement.

A.2.4. PROOF FOR THEOREM 4.5

  • The proof also establishes the lower bound diamTV(P) ≥ ηX.This bound isolates the covariate-shift contribution as a lower bound on the diameter.Source: §A.2.4 · p. 13
  • Theorem 4.5 gives the upper bound diamTV(P) ≤ ηX + (1 − ηX)η̄Y|X.This is the displayed upper-bound statement in the supplied proof passage.Source: §A.2.4 · p. 14
  • In the density argument, the excess feature densities for two environments cannot both be positive at the same input, allowing the absolute-value expression to split into two terms.The proof states that the excess densities never exist simultaneously at a point x, and uses this to drop the absolute value before splitting the integral.Source: §A.2.4 · pp. 14–15
  • The proof obtains an upper bound on the diameter by decomposing joint distance into covariate and labeling contributions.The figure passage explains that the two interpolation paths reflect the interaction between feature and label changes, with covariate mass gating the effect of label disagreement.Source: §A.2.4 · p. 14, Figure 2 · p. 16

B. Proofs for NX = 1 Regime

  • With the environment fixed, the TV distance between two joint distributions reduces to expected pointwise disagreement between their labelers.The pure label-uncertainty proof sets NX = 1, so the covariate distribution is fixed and unique.Source: B. Proofs for NX = 1 Regime · p. 17, §B.1 · p. 17

B.1. Proposition 5.1: Geometric Exactness

  • In the pure label-uncertainty regime, the proof characterizes the credal-set diameter through distances between joint distributions that share the same feature marginal.The proof identifies the diameter as a maximum over the credal set’s extreme points.Source: §B.1 · p. 17

B.2. Theorem 5.2: Finite Sample Concentration

This section develops finite-sample bounds and estimation for structured credal ambiguity in the fixed-covariate regime, including results for bounded-noise annotators and independently noisy binary annotators. It also connects these bounds to robustness guarantees and discrete min-max optimization of expected risk.

B.2. Theorem 5.2: Finite Sample Concentration

  • Under the stated assumptions, annotated sample tuples are i.i.d., enabling a high-probability concentration bound for the maximum empirical pairwise TV disagreement.The proof uses Hoeffding’s inequality for pairwise disagreement estimates and a union bound across annotator pairs; the bound’s explicit formula is not included in the supplied passage.Source: §B.2 · pp. 19–20

B.3. Corollary 5.4: Robust Generalization

  • In the pure label uncertainty regime (NX = 1), the robust generalization guarantee uses the credal-set diameter, which is characterized by maximum expected pairwise label disagreement.The general bound also includes a statistical estimation error depending on confidence, sample size, and hypothesis class.Source: §B.2 · p. 20, §B.3 · p. 21

B.3.1. THEOREM 5.5: MINIMAX OPTIMALITY

  • The minimax proof constructs an NX = 1 credal set from two deterministic labeling mechanisms that disagree on a feature subset of mass η, then uses a two-point testing argument.The supplied proof concludes that this construction establishes the theorem, but does not include the lower-bound formula.Source: §B.3.1 · pp. 21–22, Step 3: A two-point testing lower bound · pp. 22–23

B.4. Noisy Annotator Model (Aleatoric Uncertainty)

  • With binary symmetric annotators that are conditionally independent given the ground truth, a pair disagrees exactly when one annotator flips, and the credal diameter is their maximum pairwise disagreement.This specialization gives a direct interpretation of the robustness radius through annotator error behavior.Source: §B.4 · p. 23
  • When every annotator has εj ≤ εmax ≤ 1/2, the ambiguity-radius upper bound is strictly below 1, so it is non-vacuous despite noisy supervision.Source: §B.4 · p. 23

C. Proof for Proposition 6.1

  • For bounded loss, linear expected risk reaches its supremum at an extreme point; finite generators make robust optimization a discrete min-max problem.Source: C. Proof for Proposition 6.1 · p. 24

D.1. Empirical Analysis and Ablation Studies

The experiments test whether the structured credal bounds are tight and whether the diameter can be estimated and concentrated reliably across labeling regimes. Results show strong empirical coverage, accurate disagreement-based estimates, and sample-size behavior consistent with the theory, with finite-sample performance varying by labeling mechanism and data distribution.

D.1. Empirical Analysis and Ablation Studies

  • 3.65 × 10−5 mean estimation gap in the soft-label regime; deviations stayed within 0.05 for 99.9% of trials, and noisy-label bias was ≈0.02 up to ε = 0.5.The hard-label estimator was unbiased; the soft-label characterization uses mean L1 distance, while the noisy-label test allowed mechanisms to flip the ground truth.Source: §D.1 · p. 24, §D.2 · p. 25
  • In the fixed-covariate regime, diameter estimates were unbiased and tightly concentrated for hard and soft labelers; soft-label estimates tracked the population value even at small n.The soft-label result is attributed to the lower-variance signal from observing probabilities directly.Source: §D.1 · pp. 24–25
  • 100% empirical coverage: all evaluated distribution pairs satisfy the general distance bounds, with essentially zero slack in pure shifts and moderate slack in joint shifts.The evaluation covers 20 Gaussian covariate distributions and 10 labeling mechanisms.Source: §D.1 · p. 24, Table 2 · p. 25
  • At NY = 1000 labeling mechanisms, bounds remained non-vacuous and tightness ratios stayed between 1.4 and 3.3, while estimation error scaled logarithmically in NY.The evaluation considered both a fixed-diameter construction and a setting where the diameter could expand with the number of mechanisms.Source: §D.1 · p. 25

D.2. Discussion

  • O(n−1/2) error scaling held across deterministic hard-label covariate settings, with effectively zero violation probability and tightness ratios around 1.7–2.5.For soft labels, the Probit-link concentration results also showed predicted scaling and zero observed violations.Source: §D.2 · pp. 25, 27
  • For soft labels under Probit covariates N(0, 1), median and 95th-percentile errors decreased monotonically with sample size, with zero observed bound violations.The reported Hoeffding-based bound remained conservative, while its tightness ratio stayed stable.Source: §D.2 · p. 27
  • Across labeling regimes, Figure 3 reports O(n−1/2) error scaling, while finite-sample errors differ: sigmoid labels are lower-error and block labelers converge more slowly with a higher error floor than interval labelers.The Hoeffding union bound is a conservative upper envelope in the depicted settings.Source: §D.2 · pp. 27, 29
Loading 2603.14070v1…