H-delta-H divergence

Let $(\mathsf{X},{\mathrm{\Sigma }}_X)$ be a measurable space, equip $\{0,1\}$ with its discrete sigma-algebra, let ${\mu }_S$ and ${\mu }_T$ be probability measures on $\mathsf{X}$, and let $\mathcal{H}$ be a nonempty class of measurable classifiers $h:\mathsf{X}\to \{0,1\}$. For $h,h^{\mathrm{\prime }}\in \mathcal{H}$, define their measurable disagreement set by $A_{h,h^{\mathrm{\prime }}}:=(h^{-1}(\{0\})\cap h^{\mathrm{\prime }-1}(\{1\}))\cup (h^{-1}(\{1\})\cap h^{\mathrm{\prime }-1}(\{0\}))\mathrm{.}$ The $\mathcal{H}\mathrm{\Delta }\mathcal{H}$ divergence of the two input laws is $d_{\mathcal{H}\mathrm{\Delta }\mathcal{H}}({\mu }_S,{\mu }_T):=2{\sup }_{h,h^{\mathrm{\prime }}\in \mathcal{H}}\mid {\mu }_S(A_{h,h^{\mathrm{\prime }}})-{\mu }_T(A_{h,h^{\mathrm{\prime }}})\mid \in [0,2]\mathrm{.}$

Source and target joint laws, risks, and covariate shift: supplies the source and target input marginals ${\mu }_S$ and ${\mu }_T$.

A measurable function between measurable spaces: measurability means measurable preimages, so the displayed finite union of intersections is measurable.

Ben-David et al., Definition 3, Lemma 3, printed pp. 156–157: the symmetric-difference hypothesis class and the disagreement-probability bound.

Mansour, Mohri, and Rostamizadeh, Definition 3 and §3, arXiv version 3, pp. 3–4: the $d_A$ distance with $A=\mathcal{H}\mathrm{\Delta }\mathcal{H}$ for binary classification.