Tsybakov Conditions with Ties and Discrete Covariates

Why ties change the meaning of a margin condition

In binary classification, the conditional class probability can equal one half at some covariate values. At such a value, neither class is more likely than the other, so either prediction has the same conditional error. This matters when a margin condition counts covariates whose conditional probability is close to one half: does it count the exact ties as well as nearby values?

For continuous covariates, an exact tie may have probability zero even when the decision boundary is nonempty. With discrete covariates, a single tied covariate value can have positive probability. The distinction between counting and excluding ties is therefore essential, not merely notational.

Definition: In binary classification, let $Y\in\{0,1\}$, let $X$ denote the covariates, and define the regression function $\eta(x)=P(Y=1\mid X=x)$. The classification margin at $x$ is $\delta(x)=|2\eta(x)-1|$, which lies in $[0,1]$. A boundary tie occurs when $\eta(X)=1/2$, or equivalently when $\delta(X)=0$. Its probability is $\tau=P(\delta(X)=0)$.

A Bayes classifier predicts class 1 where $\eta(x)>1/2$ and class 0 where $\eta(x)<1/2$; at a tie it may choose either class. The margin measures how much the conditional error increases if the prediction at a non-tied point is reversed. A Tsybakov margin condition restricts the probability of seeing small margins.

Two conventions for the Tsybakov condition

Fix constants $C>0$ and $\alpha>0$. The inclusive version counts ties:

P\bigl(\delta(X)\le t\bigr)\le C t^\alpha,\qquad 0<t\le 1.

The tie-excluded version counts only positive margins:

P\bigl(0<\delta(X)\le t\bigr)\le C t^\alpha,\qquad 0<t\le 1.

Both conditions describe how quickly probability mass can accumulate near the decision boundary, but they make different claims at the boundary itself. The inclusive condition requires the boundary to have probability zero. The tie-excluded condition places no restriction on $\tau$. If a convention instead uses $|\eta(X)-1/2|$, the margin is rescaled by a factor of two, which changes the constant $C$ but not the exponent $\alpha$.

The exponent is informative about the probability of small positive margins: a larger exponent imposes a thinner near-boundary region. In a discrete distribution with positive margins separated from zero, however, there may be no positive margins in a sufficiently small interval at all. That situation satisfies the tie-excluded condition for every positive exponent, whether or not the distribution has ties.

Worked Example: A Discrete Covariate With a Boundary Tie

Suppose $X$ takes values $a,b,c$ with probabilities $0.2,0.5,0.3$, respectively, and $\eta(a)=0.1$, $\eta(b)=0.5$, and $\eta(c)=0.8$. The margins are $\delta(a)=|0.2-1|=0.8$, $\delta(b)=0$, and $\delta(c)=|1.6-1|=0.6$. Thus the tie mass is $\tau=0.5$.

For every $t>0$, the inclusive probability $P(\delta(X)\le t)$ is at least $0.5$, because the event always contains $X=b$. If an inclusive condition held with $\alpha>0$, then $0.5\le Ct^\alpha$ for every $t>0$, which fails for sufficiently small $t$. So no finite $C$ works.

For the tie-excluded condition, the smallest positive margin is $0.6$. If $0<t<0.6$, the probability in the condition is zero. If $0.6\le t\le 1$, it is at most the total positive-margin mass, $0.2+0.3=0.5$. For any $\alpha>0$, choosing $C=0.5/0.6^\alpha$ works: when $t\ge0.6$, $Ct^\alpha\ge0.5$. Thus the tie-excluded condition holds for every positive exponent.

What the inclusive condition implies

The relationship between the two formulations follows directly from the probability of the tie event.

Theorem: For any $C>0$ and $\alpha>0$, the inclusive condition implies $\tau=0$. If $\tau=0$, the inclusive and tie-excluded conditions are identical.

Proof. Take $t_m=1/m$. The events $\{\delta(X)\le t_m\}$ decrease as $m$ increases, and their intersection is $\{\delta(X)=0\}$. Since probability is continuous for a decreasing sequence of events, $P(\delta(X)\le t_m)$ tends to $\tau$. The inclusive condition gives $P(\delta(X)\le t_m)\le C m^{-\alpha}$, whose right-hand side tends to zero. Therefore $\tau=0$. Conversely, when $\tau=0$, the events $\{\delta(X)\le t\}$ and $\{0<\delta(X)\le t\}$ differ only on a probability-zero event. Their probabilities are equal for every $t>0$, so the two conditions coincide. $\square$

The theorem explains why citing “the Tsybakov condition” without specifying the event can be ambiguous in a discrete setting. An inclusive positive-exponent condition rules out ties; a tie-excluded condition permits them.

Worked Example: Positive Margins Approaching Zero Without Ties

Let $X$ take values $k=1,2,\ldots$ with $P(X=k)=2^{-k}$. These probabilities sum to one. Set $\eta(k)=(1+2^{-k})/2$, so $\delta(k)=2^{-k}$ and there are no ties.

For $0<t<1/2$, let $m=\lceil\log_2(1/t)\rceil$. Then $2^{-m}\le t$, and $\delta(k)\le t$ holds exactly when $k\ge m$. Hence $P(\delta(X)\le t)=\sum_{k=m}^{\infty}2^{-k}=2^{1-m}\le2t$. For $1/2\le t\le1$, the probability is at most $1\le2t$. Thus the inclusive condition holds with $\alpha=1$ and $C=2$, and so does the tie-excluded condition. For example, at $t=1/8$, the event is $k\ge3$, with probability $\sum_{k=3}^{\infty}2^{-k}=1/4=2t$.

Unlike a finite set of positive margins, this support has margins arbitrarily close to zero. The condition therefore places a genuine restriction on how much probability lies near the boundary.

Finite positive-margin support

Discrete covariates often have only finitely many possible values. If the positive margins on that support are bounded away from zero, the tie-excluded condition follows regardless of how large the tie mass is.

Proposition: Suppose $P(\delta(X)>0)>0$ and there is a $\Delta>0$ such that $\delta(X)\ge\Delta$ whenever $\delta(X)>0$, almost surely. Then, for every $\alpha>0$, the tie-excluded condition holds with $C=P(\delta(X)>0)/\Delta^\alpha$.

Proof. If $0<t<\Delta$, there is no positive margin at most $t$, so $P(0<\delta(X)\le t)=0$. If $\Delta\le t\le1$, then $P(0<\delta(X)\le t)\le P(\delta(X)>0)$. The proposed constant gives $Ct^\alpha=P(\delta(X)>0)(t/\Delta)^\alpha\ge P(\delta(X)>0)$. The required inequality holds in both ranges of $t$. $\square$

In particular, on a finite covariate support, the minimum among the finitely many positive margins is positive whenever there is at least one positive margin. A finite support can therefore satisfy every tie-excluded exponent, even if it places substantial probability on ties. If all margins are zero, the left side of the tie-excluded condition is identically zero, so that condition also holds for every $\alpha>0$.

Worked Example: A Large Tie Mass and a Positive-Margin Gap

Suppose $X$ has probability $0.9$ on a tied point with margin $0$, and probability $0.1$ on a point with margin $0.5$. For $0<t<0.5$, the tie-excluded probability is zero. For $0.5\le t\le1$, it is $0.1$. For any $\alpha>0$, take $C=0.1/0.5^\alpha$; then $Ct^\alpha\ge0.1$ in the second range, so the tie-excluded condition holds.

The inclusive probability is at least $0.9$ for every $t>0$, so it cannot be bounded by $Ct^\alpha$ as $t$ tends to zero. The distinction is not a small adjustment to the constant: the two conditions make incompatible claims about the boundary mass.

Ties and excess classification risk

A tie can matter to a probability condition without contributing any excess classification risk. To see this precisely, let $g$ be any measurable classifier, let $g^*$ be a measurable Bayes classifier, and define the classification risk $R(g)=P(g(X)\ne Y)$. The excess risk is $R(g)-R(g^*)$.

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

Derivation. Conditional on $X=x$, predicting 0 has error probability $\eta(x)$, and predicting 1 has error probability $1-\eta(x)$. If $\eta(x)>1/2$, the Bayes prediction is 1, and predicting 0 instead increases conditional error by $\eta(x)-(1-\eta(x))=2\eta(x)-1=\delta(x)$. If $\eta(x)<1/2$, the Bayes prediction is 0, and predicting 1 instead increases conditional error by $(1-\eta(x))-\eta(x)=1-2\eta(x)=\delta(x)$. If $\eta(x)=1/2$, both predictions have error $1/2$, so the increase is zero. Thus the conditional excess risk is $\delta(x)\mathbf{1}\{g(x)\ne g^*(x)\}$ in all cases. Taking expectation over $X$ proves the identity. $\square$

This identity also shows why arbitrary tie-breaking does not change the Bayes risk. A classifier that differs from the chosen $g^*$ only at tied covariate values has excess risk zero. Nevertheless, the same ties may prevent an inclusive margin condition with positive exponent from holding. Risk equivalence at ties and a probability assumption about near-boundary mass are different issues.

Common mistake

Wrong reasoning: “There is a tie at a discrete covariate value, but either label is Bayes-optimal there, so the usual positive-exponent margin condition still holds.”
Correction: That conclusion depends on the condition’s event. If it is inclusive, $P(\delta(X)\le t)$ is at least the tie mass for every $t>0$, so no finite $C$ can satisfy the bound for $\alpha>0$. If it excludes ties, the tie mass is absent from the bound and the condition may hold. State explicitly which formulation is being used.

When assessing a discrete design, first compute $\tau=P(\delta(X)=0)$. Then inspect the positive margins: do they have a positive gap above zero, or can they accumulate arbitrarily close to zero? The first question determines whether the inclusive condition is immediately ruled out; the second determines whether the tie-excluded bound imposes a nontrivial restriction.

Check Your Understanding

Use the definitions and results above to answer the following.

If $P(\delta(X)=0)=0.2$, can an inclusive condition hold with finite $C$ and $\alpha>0$? Explain.
Suppose every positive margin is at least $0.1$, but $P(\delta(X)=0)=0.7$. Which version of the condition can hold for every positive exponent?
Why does a classifier that differs from a Bayes classifier only at tied points have zero excess risk?
For a distribution with no ties, what relationship holds between the inclusive and tie-excluded conditions?
Can a finite discrete support with a positive-margin gap satisfy the tie-excluded condition for $\alpha=3$ and $\alpha=1$? What feature of the support determines the answer?