Class-Conditional Label Noise Versus Margin Noise

Two Different Meanings of “Noise”

In binary classification, “noise” can refer either to how recorded labels were generated or to how much probability mass lies near the decision boundary. These are different properties. Class-conditional label noise describes a corruption mechanism linking an unobserved clean label to an observed label. Massart and Tsybakov conditions instead describe the posterior probabilities of the labels being used for classification.

This distinction matters because one property does not generally determine the other. A class-conditional corruption mechanism can produce many different posterior-margin distributions, depending on the clean model and the distribution of covariates. Conversely, a distribution can have a strong margin gap even when its label-corruption probability varies with the covariates and is therefore not class-conditional.

Class-Conditional Label-Flips

Let \(X\) be a covariate, \(Y^*\in\{0,1\}\) a clean label, and \(\widetilde Y\in\{0,1\}\) the observed label. Write \(\eta^*(x)=P(Y^*=1\mid X=x)\). In a class-conditional flip model, the probability of changing the label depends on the clean class, but not further on \(X\).

Definition: The labels follow a class-conditional flip model if there are constants \(\rho_0,\rho_1\in[0,1]\) such that, almost surely, \(P(\widetilde Y=1\mid X,Y^*=0)=\rho_0\) and \(P(\widetilde Y=0\mid X,Y^*=1)=\rho_1\). The flip rate is \(\rho_0\) for clean class 0 and \(\rho_1\) for clean class 1. Unless stated otherwise, assume \(\rho_0+\rho_1<1\), so the corruption does not reverse the ordering of clean posterior probabilities.

The observed posterior is \(\widetilde\eta(x)=P(\widetilde Y=1\mid X=x)\). Conditioning on the clean class gives the following formula.

Result: Under the class-conditional flip model, \(\widetilde\eta(x)=\rho_0(1-\eta^*(x))+(1-\rho_1)\eta^*(x) =\rho_0+(1-\rho_0-\rho_1)\eta^*(x)\).

Indeed, given \(X=x\), an observed 1 occurs either when \(Y^*=0\) and it flips to 1, or when \(Y^*=1\) and it remains 1. Those disjoint cases have probabilities \((1-\eta^*(x))\rho_0\) and \(\eta^*(x)(1-\rho_1)\), respectively, which sum to the displayed expression. This calculation depends on the flip probabilities being constant within each clean class.

Worked Example: Symmetric Flips and a Uniform Margin Gap

Suppose \(X\) takes two values, \(a\) and \(b\), with positive probability, and the clean posterior probabilities are \(\eta^*(a)=0.2\) and \(\eta^*(b)=0.8\). Each clean label is independently flipped with probability \(\rho_0=\rho_1=0.1\).

The observed posterior is \(\widetilde\eta(x)=0.1+0.8\eta^*(x)\). Thus \(\widetilde\eta(a)=0.1+0.8(0.2)=0.26\), and \(\widetilde\eta(b)=0.1+0.8(0.8)=0.74\).

Define the observed posterior margin by \(\Delta(x)=|2\widetilde\eta(x)-1|\). At both covariate values, \(\Delta(x)=0.48\). Consequently this distribution satisfies a Massart margin gap with \(h=0.48\), as well as a Tsybakov margin condition for every exponent \(\alpha>0\). The flip mechanism and the margin property both hold here, but they are established by different calculations.

Massart and Tsybakov Margin Conditions

For a distribution of \((X,Y)\), let \(\eta(x)=P(Y=1\mid X=x)\) and define its posterior margin as \(\Delta(x)=|2\eta(x)-1|\). The Bayes classifier chooses class 1 when \(\eta(x)\geq 1/2\) and class 0 otherwise. The margin is the absolute difference between the two conditional class probabilities: it is small when the classification decision is locally uncertain.

Definition: A distribution satisfies the Massart margin condition with gap \(h>0\) if \(\Delta(X)\geq h\) almost surely. Equivalently, the conditional probability of error of the Bayes classifier, \(\min\{\eta(X),1-\eta(X)\}\), is at most \((1-h)/2\) almost surely.

The Massart condition rules out covariates with posterior probabilities arbitrarily close to one half. It is a uniform, pointwise separation from the decision boundary, not a statement that observed labels were corrupted at constant rates within each class.

Definition: For \(\alpha>0\), a distribution satisfies a Tsybakov margin condition with exponent \(\alpha\) and constant \(C<\infty\) if \(P(\Delta(X)\leq t)\leq Ct^\alpha\) for every \(0<t\leq1\).

This condition allows small margins, but limits how much probability can accumulate near zero. We use the version that includes any observations with exactly zero margin in the event \(\{\Delta(X)\leq t\}\). Some references define the margin using \(|\eta(X)-1/2|\) instead; since \(\Delta(X)=2|\eta(X)-1/2|\), that convention changes constants by a factor involving \(2^\alpha\), not the substance of the condition.

What the Margin Conditions Imply

A Massart gap is stronger than a Tsybakov condition: if all margins are at least \(h\), then sufficiently small-margin events have probability zero. For larger thresholds, their probability is at most one. The following argument gives the constants explicitly.

Theorem: If \(\Delta(X)\geq h\) almost surely for some \(0<h\leq1\), then for every \(\alpha>0\), \(P(\Delta(X)\leq t)\leq h^{-\alpha}t^\alpha\) for all \(0<t\leq1\).

Proof. If \(0<t<h\), the event \(\{\Delta(X)\leq t\}\) is empty up to a probability-zero set, so its probability is zero and the claimed inequality holds. If \(h\leq t\leq1\), then \(P(\Delta(X)\leq t)\leq1\leq(t/h)^\alpha=h^{-\alpha}t^\alpha\). These cases cover every \(0<t\leq1\). \(\square\)

The converse does not hold. A Tsybakov bound allows margins to approach zero, provided the probability of very small margins decreases sufficiently quickly. It does not supply a positive lower bound on every margin.

Worked Example: Class-Conditional Flips Without Any Positive Tsybakov Exponent

Let \(X\) take values \(k=1,2,\ldots\), with \(P(X=k)=1/[k(k+1)]\). These probabilities sum to one because \(1/[k(k+1)]=1/k-1/(k+1)\). Set \(\eta^*(k)=(1+2^{-k})/2\), and independently flip each clean label with symmetric rate \(\rho_0=\rho_1=0.1\).

The observed posterior is \(\widetilde\eta(k)=0.1+0.8\eta^*(k)\). Its margin is therefore \(\Delta(k)=|2\widetilde\eta(k)-1|=0.8\,2^{-k}\). The margins are positive but tend to zero, so there is no Massart gap.

For any integer \(K\geq1\), take \(t_K=0.8\,2^{-K}\). Every \(k\geq K\) has \(\Delta(k)\leq t_K\), and the probability of this set is \(\sum_{k=K}^{\infty}1/[k(k+1)]=1/K\). If a Tsybakov bound held for some \(\alpha>0\) and finite \(C\), it would require \(1/K\leq C(0.8\,2^{-K})^\alpha\) for every \(K\). This is impossible: the ratio \((1/K)/(0.8\,2^{-K})^\alpha=2^{\alpha K}/[K\,0.8^\alpha]\) diverges as \(K\) increases. Thus class-conditional flips do not guarantee a Massart gap or a positive-exponent Tsybakov condition.

Symmetric and Asymmetric Flips Affect Margins Differently

The posterior transformation also clarifies how flip rates interact with the clean Bayes rule. Under symmetric flips, \(\rho_0=\rho_1=\rho<1/2\), subtracting one half from the observed posterior gives \(\widetilde\eta(x)-1/2=(1-2\rho)(\eta^*(x)-1/2)\). The multiplier is positive, so the clean and observed Bayes classifiers agree, and the observed margin is exactly \((1-2\rho)\) times the clean margin. Thus a clean Massart gap \(h\) becomes an observed gap \((1-2\rho)h\). The same scaling transfers a Tsybakov exponent, with a changed constant.

With unequal flip rates, the transformation remains increasing when \(\rho_0+\rho_1<1\), but its decision threshold need not remain at the clean threshold \(1/2\). Solving \(\widetilde\eta(x)=1/2\) gives the clean-posterior threshold \(\eta^*(x)=(1/2-\rho_0)/(1-\rho_0-\rho_1)\), when this value lies in \([0,1]\). This equals \(1/2\) precisely when \(\rho_0=\rho_1\). Class-conditional corruption is therefore not, by itself, a guarantee that classification decisions for the clean and observed labels coincide.

Worked Example: Asymmetric Class-Conditional Flips Change the Decision

Suppose at a covariate value \(x\), the clean posterior is \(\eta^*(x)=0.55\). The clean Bayes decision is class 1. Now let \(\rho_0=0.1\) and \(\rho_1=0.3\); both rates are below one half and their sum is \(0.4<1\).

The observed posterior is \(\widetilde\eta(x)=0.1+(1-0.1-0.3)(0.55)=0.1+0.6(0.55)=0.43\). It is below one half, so the observed-label Bayes decision is class 0. Its margin is \(|2(0.43)-1|=0.14\). The mechanism is class-conditional, but its unequal rates have shifted the decision threshold and changed this decision.

A Margin Condition Need Not Be Class-Conditional Noise

A margin condition concerns the distribution of \(\eta(X)\); class-conditional noise concerns whether flip probabilities remain constant as \(X\) varies within each clean class. The distinction can be seen by constructing labels whose corruption probability changes with \(X\), while keeping the posterior uniformly far from one half.

Worked Example: A Massart Gap Without Class-Conditional Flips

Let \(X\) be uniform on \([0,1]\), and let the clean label be deterministic: \(Y^*=1\) when \(X<1/2\), and \(Y^*=0\) when \(X\geq1/2\). Given \(X=x\), flip the clean label with probability \(q(x)=0.1+0.1x\).

For \(x<1/2\), the observed posterior is \(\eta(x)=1-q(x)=0.9-0.1x\), so its margin is \(2\eta(x)-1=0.8-0.2x\), which is greater than \(0.7\). For \(x\geq1/2\), \(\eta(x)=q(x)=0.1+0.1x\), so its margin is \(1-2\eta(x)=0.8-0.2x\), which is at least \(0.6\). Hence \(\Delta(X)\geq0.6\) almost surely: the observed distribution satisfies the Massart condition.

However, the flip probability is not constant within either clean class. For clean class 1, \(q(x)\) varies over \(0.1\leq q(x)<0.15\); for clean class 0, it varies over \(0.15\leq q(x)\leq0.2\). No pair of class-specific constants \(\rho_0,\rho_1\) describes these probabilities. The Massart margin property therefore holds without a class-conditional flip mechanism.

Why Margin Conditions Matter for Classification Risk

Margin assumptions are useful because classification excess risk weights mistakes according to how far the posterior is from one half. They do not specify a corruption mechanism. To see their role, let \(g:\mathcal X\to\{0,1\}\) be any measurable classifier, let \(g^*(x)=\mathbf 1\{\eta(x)\geq1/2\}\) be a Bayes classifier, and define \(R(g)=P(g(X)\ne Y)\).

Result: For binary classification, \(R(g)-R(g^*)=E[\Delta(X)\mathbf 1\{g(X)\ne g^*(X)\}]\).

Proof. Conditional on \(X=x\), predicting 0 has error probability \(\eta(x)\), and predicting 1 has error probability \(1-\eta(x)\). If \(g(x)=g^*(x)\), their conditional-risk difference is zero. If they disagree and \(\eta(x)>1/2\), the Bayes decision is 1, so the difference is \(\eta(x)-(1-\eta(x))=2\eta(x)-1=\Delta(x)\). If they disagree and \(\eta(x)<1/2\), the Bayes decision is 0, so the difference is \((1-\eta(x))-\eta(x)=1-2\eta(x)=\Delta(x)\). At a tie, \(\Delta(x)=0\) and the conditional risks are equal. Taking expectations of these conditional differences proves the identity. \(\square\)

The identity shows why a small-margin region matters: mistakes there contribute little excess risk individually, while mistakes at large margins contribute more. A Tsybakov condition limits the probability of the small-margin region; a Massart condition removes that region below a fixed threshold. Neither statement alone tells us whether labels were generated by constant class-specific flip rates.

Common Mistake: Treating the Assumptions as Synonyms

Incorrect reasoning: “The labels have Massart noise, so their flips must occur with a constant probability within each class; therefore the model is class-conditional.” This confuses a posterior-margin restriction with a statement about the label-generation mechanism.

Correction: Check the definitions separately. For class-conditional noise, examine whether \(P(\widetilde Y\ne Y^*\mid X,Y^*)\) is constant in \(X\) within each clean class. For a Massart or Tsybakov condition, examine the posterior margin \(|2\eta(X)-1|\) and how much probability it assigns near zero. One can hold without the other, as the examples demonstrate. Also specify whether \(\eta\) refers to clean labels or observed labels: asymmetric flips can change the posterior threshold and the Bayes decision.

Key takeaway: Class-conditional flips describe a corruption mechanism; Massart and Tsybakov describe posterior-margin behavior. Symmetric flips rescale the clean margin, while asymmetric flips can shift the decision threshold. Always identify the label distribution and the property being assumed.

Check Your Understanding

Use the definitions and calculations above to answer these questions.

Under class-conditional flips, derive the observed posterior \(\widetilde\eta(x)\) by conditioning on the clean label.
Why does a Massart margin gap imply a Tsybakov condition for every positive exponent? Give a valid constant in terms of the gap.
In the asymmetric-flip example, what is the clean-posterior threshold at which the observed posterior equals one half?
Can a distribution satisfy a Massart margin condition when its flip probability varies with \(X\) within each clean class? Explain using the relevant distinction.
What does a Tsybakov condition restrict, and what does it leave unspecified about the label-generation mechanism?