Tsybakov Margin Exponents

Why Bound the Probability of Small Margins?

In binary classification, the most consequential observations for a decision rule are often those whose conditional class probabilities are close to one half. A small change in the estimated class probability can change the predicted label there. Tsybakov’s margin condition describes how much probability the feature distribution places near this decision boundary. It is a condition on the distribution of margins, not a claim that every observation is far from the boundary.

Let $X$ be a feature random variable and let $Y\in\{-1,+1\}$ be its binary label. Write $\eta(x)=P(Y=+1\mid X=x)$ for a measurable version of the conditional class probability, and define the margin variable

\Delta(X)=|2\eta(X)-1|.

The margin lies in $[0,1]$. It is zero when the two labels have equal conditional probability and is close to zero when they are nearly tied. The following convention uses the event $0<\Delta(X)\le t$: exact ties are excluded because a tie has no preferred class under the conditional distribution.

Definition: For constants $C>0$ and $\alpha\ge 0$, the distribution of $(X,Y)$ satisfies Tsybakov’s margin condition with exponent $\alpha$ and constant $C$ if, for every $t>0$, $$ P(0<\Delta(X)\le t)\le C t^\alpha. $$ The pair $(\alpha,C)$ is one set of valid condition parameters; it need not be unique.

The condition concerns the mass of the feature distribution in a narrow band of positive margins. It does not require a lower bound on every individual margin. When $\alpha>0$, the upper bound decreases as $t$ decreases: very small positive margins must have correspondingly little probability. A larger exponent gives a stronger small-$t$ restriction when the constant is held fixed. The constant matters as well, so exponents should not be compared without attending to their associated constants and the range of $t$.

Reading the Exponent and Constant

For $0<t\le1$, the right-hand side $Ct^\alpha$ is a power-law envelope for the probability of a positive margin no larger than $t$. The exponent controls the envelope’s rate of decrease toward zero; the constant controls its vertical scale. Because $\Delta(X)\le1$, the condition for $t\ge1$ usually adds no substantive restriction when $C\ge1$ and $\alpha\ge0$: the probability is at most one and $Ct^\alpha\ge1$. Stating the condition for every $t>0$ is convenient and unambiguous.

A positive exponent does not say that there are no observations arbitrarily close to the boundary. A continuous margin distribution can have positive probability in every interval $(0,t]$ while that probability tends to zero at a controlled rate. Conversely, a margin distribution with a positive gap above zero satisfies conditions with many different positive exponents. Thus $\alpha$ is an exponent for a valid bound, not automatically a unique parameter describing the distribution.

The zero-exponent case deserves separate attention. Since $t^0=1$, the condition becomes $P(0<\Delta(X)\le t)\le C$. For $t\ge1$, the event includes every positive margin, so this condition is equivalent to $P(\Delta(X)>0)\le C$. If the convention is $C\ge1$, it is automatic and expresses no decay near the boundary. If $C<1$, it does constrain the total probability of non-tied points. In particular, exponent zero alone does not mean that margins are bounded away from zero.

Worked Example: A Continuous Power-Law Margin

Suppose $\Delta(X)$ has density $f_\Delta(u)=2u$ for $0<u<1$, with no atoms at zero or one. For $0<t\le1$, integrate the density:

P(0<\Delta(X)\le t)=\int_0^t 2u\,du=t^2.

For $t\ge1$, this probability is one. Therefore $\alpha=2$ and $C=1$ satisfy the condition for all $t>0$: for $t\le1$ the bound is equality, and for $t\ge1$, $1\le t^2$.

In fact, every exponent $0\le\alpha\le2$ works with $C=1$. For $0<t\le1$, $t^2\le t^\alpha$; for $t\ge1$, $1\le t^\alpha$. No exponent $\alpha>2$ works with any finite constant $C$. Otherwise, for every $0<t\le1$, the condition would require $t^2\le Ct^\alpha$, or $t^{2-\alpha}\le C$. The left-hand side diverges as $t$ decreases to zero, contradicting finiteness of $C$. This example has a meaningful upper limiting exponent of two, even though smaller exponents are also valid.

How Valid Exponents Relate

A distribution may satisfy the condition for one exponent and thereby satisfy it for smaller exponents, after allowing an appropriate constant. The argument uses the fact that margins are at most one; it is not a claim that every exponent is interchangeable at the same constant.

Theorem: If the margin condition holds with exponent $\alpha\ge0$ and constant $C>0$, then it holds with every exponent $\beta$ such that $0\le\beta\le\alpha$, with constant $C'=\max(C,1)$.

Proof. Let $A_t=\{0<\Delta(X)\le t\}$. If $0<t\le1$, then $t^\alpha\le t^\beta$, so

P(A_t)\le Ct^\alpha\le Ct^\beta\le C't^\beta.

If $t\ge1$, the probability is at most one, and $C't^\beta\ge1$ because $C'\ge1$ and $t^\beta\ge1$. Thus $P(A_t)\le C't^\beta$ for these $t$ as well. The two ranges cover all $t>0$, proving the result. $\square$

The theorem explains why reporting an exponent without a constant or a convention for its range can be incomplete. It also clarifies the zero-exponent case: an exponent above zero implies that smaller exponents are available, but the converse does not provide a positive-exponent bound.

Worked Example: A Discrete Margin With a Gap

Let $\Delta(X)$ equal $0$ with probability $0.25$, $0.2$ with probability $0.45$, and $0.8$ with probability $0.30$. This is a valid margin distribution on $[0,1]$. For $0<t<0.2$, $P(0<\Delta(X)\le t)=0$. For $0.2\le t<0.8$, it is $0.45$; and for $t\ge0.8$, it is $0.75$.

Fix any $\alpha>0$ and take $C=5^\alpha$. For $t<0.2$, the condition holds because its left side is zero. For $t\ge0.2$, $Ct^\alpha=5^\alpha t^\alpha\ge1$, while the probability is at most $0.75$. Hence the condition holds for every positive exponent, with a constant that can depend on that exponent. The positive margins are bounded below by $0.2$, the feature of this example related to Massart’s bounded-noise condition.

For $\alpha=0$, $C=1$ also works, since the probability is never greater than one. The tie mass $0.25$ is not counted in the event. This example shows why a valid exponent does not have to be unique and why exponent comparisons need to include the constant.

Two Margin Scales

Some presentations measure distance from the conditional probability $1/2$ directly, using $\delta(X)=|\eta(X)-1/2|$. The margin used here is exactly twice that quantity: $\Delta(X)=2\delta(X)$. A change of scale changes the constant in the power bound, but not the exponent.

Result: If $P(0<\Delta(X)\le t)\le Ct^\alpha$ for all $t>0$, then $$ P(0<\delta(X)\le t)\le C2^\alpha t^\alpha $$ for all $t>0$. Conversely, if $P(0<\delta(X)\le t)\le Kt^\alpha$, then $P(0<\Delta(X)\le t)\le K2^{-\alpha}t^\alpha$.

Proof. Since $\Delta(X)=2\delta(X)$, the event $0<\delta(X)\le t$ is exactly $0<\Delta(X)\le2t$. Applying the assumed bound at $2t$ gives

P(0<\delta(X)\le t) =P(0<\Delta(X)\le2t) \le C(2t)^\alpha =C2^\alpha t^\alpha.

For the converse, $0<\Delta(X)\le t$ is equivalent to $0<\delta(X)\le t/2$. The bound in the $\delta$ scale therefore gives

P(0<\Delta(X)\le t) =P(0<\delta(X)\le t/2) \le K(t/2)^\alpha =K2^{-\alpha}t^\alpha.

Both implications hold for every $t>0$, including $\alpha=0$, when the scale factor is one. $\square$

Worked Example: Positive Margins and Exact Ties

Suppose $\Delta(X)=0$ with probability $0.4$, and with the remaining probability $0.6$, the margin is uniform on $(0,1)$. For $0<t\le1$, the probability of a positive margin at most $t$ is

P(0<\Delta(X)\le t)=0.6t.

For $t\ge1$, it is $0.6$. Thus the condition holds with $\alpha=1$ and $C=0.6$: equality holds for $0<t\le1$, and $0.6\le0.6t$ for $t\ge1$. It cannot hold with any $\alpha>1$ and finite $C$, because for $0<t\le1$ it would require $0.6t\le Ct^\alpha$, or $0.6t^{1-\alpha}\le C$, whose left side diverges as $t$ decreases to zero.

If the event instead included ties, then for every $t>0$, $P(\Delta(X)\le t)\ge0.4$. No positive exponent could bound this probability by $Ct^\alpha$ for all sufficiently small $t$ with finite $C$, since $Ct^\alpha$ tends to zero. Excluding exact ties is therefore consequential when ties have positive probability. The zero-margin points do not contribute positive or negative preference between the classes, whereas positive margins can be arbitrarily small in this example.

Common Mistakes and Practical Interpretation

Treating the exponent as a lower bound on every margin. The condition is a probability upper bound, not a pointwise separation requirement. Continuous distributions can satisfy it while placing positive probability arbitrarily close to zero.
Assuming exponent zero means a margin gap. It does not. With $C\ge1$, the zero-exponent inequality is automatic. A gap is a much stronger property; it makes the small-positive-margin probability zero below the gap.
Ignoring the constant when comparing exponents. A larger exponent gives a tighter power near zero only when constants and the relevant range are also considered. A condition with one exponent can hold with a very large constant, and the same distribution can admit several exponents.
Including ties without checking the convention. Under the strict-positive-margin convention, a tie atom is excluded. Under an inclusive event, a positive tie mass rules out every positive exponent with finite constant. State which event is being bounded.
Confusing a change of margin scale with a change of exponent. Replacing $|2\eta(X)-1|$ by $|\eta(X)-1/2|$ multiplies the constant by a scale factor raised to $\alpha$; it leaves the exponent unchanged.

The condition is useful because it summarizes how much probability can lie close to the classification boundary, a feature that affects how difficult it can be to distinguish competing labels. Its role is descriptive and quantitative: the condition alone does not specify a learning procedure, guarantee a particular rate, or identify a unique exponent. Those conclusions require additional assumptions and arguments.

Check Your Understanding

Try to answer each question using the event $0<\Delta(X)\le t$ and the stated range of $t$.

In your own words, what does a positive exponent restrict about the distribution of small positive margins?
If a condition holds with exponent $3$, which smaller nonnegative exponents also work according to the theorem, and why might their constants differ?
For a margin distribution with positive mass at zero and a continuous positive-margin component, explain why excluding ties can matter for a positive exponent.
What does the zero-exponent condition with $C=1$ say when $\Delta(X)\in[0,1]$? What changes if $C<1$?
If the margin is changed from $|2\eta(X)-1|$ to $|\eta(X)-1/2|$, what happens to the exponent and to the constant?

What You'll Learn