TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Target risk bound by source risk, H-delta-H divergence, and joint error

Statement

Let $(X, Σ_{X})$ be a measurable space, equip ${0, 1}$ with its discrete sigma-algebra, and let $P_{S}, P_{T}$ be joint probability laws on $X \times {0, 1}$ with input marginals $μ_{S}, μ_{T}$ . Let $H$ be a nonempty class of measurable classifiers $h : X \to {0, 1}$ . Define the source and target risks by $ϵ_{D} (h) : = P_{D} {(x, y) : h (x) \neq y}$ for $D \in {S, T}$ and define the joint-labeling error $λ : = \inf_{g \in H} (ϵ_{S} (g) + ϵ_{T} (g))$ . Then every $h \in H$ satisfies $ϵ_{T} (h) \leq ϵ_{S} (h) + \frac{1}{2} d_{H Δ H} (μ_{S}, μ_{T}) + λ .$

Statement references

Ben-David et al., Definitions 2–3, Lemma 3, and complete Theorem 2 proof, printed pp. 156–158: the ideal joint error, symmetric-difference divergence, and the source/target triangle argument.

Mansour, Mohri, and Rostamizadeh, §3 and §4.1, arXiv version 3, pp. 3–5: the disagreement distance and the separate finite-sample complexity bounds.

Facts & Assumptions

Given: Source and target joint probability laws on $X \times {0, 1}$ , their input marginals, a nonempty class of measurable binary classifiers, and the definitions of $ϵ_{D}$ and $λ$ in the Statement.

[F1]

Source and target joint laws, risks, and covariate shift: $P_{S}, P_{T}$ are probability laws on the common input-label product, and $μ_{S}, μ_{T}$ are their input marginals.

[F2]

H-delta-H divergence: for every $h, g \in H$ , $∣ μ_{S} (A_{h, g}) - μ_{T} (A_{h, g}) ∣ \leq \frac{1}{2} d_{H Δ H} (μ_{S}, μ_{T})$ .

[F3]

Supervised prediction problems: each classifier is measurable, so its binary disagreement and error events are measurable in the product sigma-algebra.

[F4]

Additivity of the nonnegative Lebesgue integral: the nonnegative integral is additive for sums of nonnegative measurable functions.

[F5]

Monotonicity and nonnegative homogeneity of the nonnegative integral: the nonnegative integral is monotone.

[F6]

The nonnegative integral agrees with the simple integral on simple functions: the integral of each indicator function equals the measure of its set, since an indicator is a nonnegative simple function.

Proof

1.1F1F2F3F4F5F6given

Fix $h, g \in H$ . Their disagreement set is measurable since $A_{h, g} = (h^{- 1} ({0}) \cap g^{- 1} ({1})) \cup (h^{- 1} ({1}) \cap g^{- 1} ({0}))$ . The error event for $h$ is measurable since it is $(h^{- 1} ({0}) \times {1}) \cup (h^{- 1} ({1}) \times {0})$ , and likewise for $g$ . Pointwise, if $h (x) \neq y$ then either $g (x) \neq y$ or $h (x) \neq g (x)$ ; hence $1_{{h (x) \neq y}} \leq 1_{{g (x) \neq y}} + 1_{A_{h, g}} (x)$ . Monotonicity and additivity of the nonnegative integral, the indicator-integral identity [F6], and the marginal identity in [F1] give $ϵ_{T} (h) \leq ϵ_{T} (g) + μ_{T} (A_{h, g})$ .

2.1F1F2F3F4F5F6step 1.1algebra

If $h (x) \neq g (x)$ , then at least one of $h (x)$ and $g (x)$ differs from $y$ , so $1_{A_{h, g}} (x) \leq 1_{{h (x) \neq y}} + 1_{{g (x) \neq y}}$ . Integrating this inequality under $P_{S}$ using [F4]–[F6] and the marginal identity in [F1] gives $μ_{S} (A_{h, g}) \leq ϵ_{S} (h) + ϵ_{S} (g)$ . By [F2], $μ_{T} (A_{h, g}) \leq μ_{S} (A_{h, g}) + \frac{1}{2} d_{H Δ H} (μ_{S}, μ_{T})$ , so step 1.1 yields $ϵ_{T} (h) \leq ϵ_{S} (h) + ϵ_{S} (g) + ϵ_{T} (g) + \frac{1}{2} d_{H Δ H} (μ_{S}, μ_{T})$ .

3.1step 2.1givenchoose

Let $η > 0$ . Since $H$ is nonempty and $λ$ is the infimum of its finite joint-error values, there exists $g_{η} \in H$ with $ϵ_{S} (g_{η}) + ϵ_{T} (g_{η}) < λ + η$ . Substituting this choice into step 2.1 gives $ϵ_{T} (h) \leq ϵ_{S} (h) + λ + η + \frac{1}{2} d_{H Δ H} (μ_{S}, μ_{T})$ .

4.1step 3.1algebra∎

The inequality in step 3.1 holds for every $η > 0$ ; letting $η$ decrease to zero gives the stated bound. The proof requires no attained joint-risk minimizer.

Remarks

This is a population inequality. It does not bound empirical source risk or an empirical estimate of the divergence; finite-sample substitution requires a separate bounded-loss and complexity theorem. Even when the input divergence is small, a large joint-labeling error $λ$ can leave the target-risk bound large.

Remarks references

Ben-David et al., Theorem 2 and its complete proof, printed pp. 157–158: the finite-sample target bound adds VC-complexity terms to the population inequality.

Mansour, Mohri, and Rostamizadeh, §3 and Theorem 9, arXiv version 3, pp. 4–7: empirical discrepancy bounds require Rademacher-complexity controls and bounded-loss assumptions.

Depends on

Used by

Identical input laws can hide a large joint-labeling error Example

Dependency tree · two levels

24 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan, A Theory of Learning from Different Domains, Machine Learning 79 (2010), Definitions 2–3, Lemma 3, and Theorem 2 proof (standard reference, not scraped)
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh, Domain Adaptation: Learning Bounds and Algorithms, arXiv:0902.3430v3, §3 and §4.1 (standard reference, not scraped)