Dyadic Bounds for Small-Margin Probabilities

Why dyadic shells are useful

A small-margin condition controls how much probability lies close to the classification decision boundary. Its usefulness often depends on more than knowing that this probability is small: calculations may need to add contributions from regions at several distances from the boundary. Dividing those distances into dyadic scales makes the contributions explicit and exposes which exponent governs the sum.

Let $X$ denote the covariates, let $\eta(x)=P(Y=1\mid X=x)$ for a binary response $Y\in\{0,1\}$, and write $\Delta(X)=|2\eta(X)-1|$ for the classification margin variable. Thus $0\leq\Delta(X)\leq1$, and values near zero correspond to points near the decision boundary. We use the following convention for the Tsybakov small-margin condition.

Definition: The distribution satisfies the small-margin condition with exponent $\alpha\geq0$ and constant $C\geq1$ if $$ P\{\Delta(X)\leq t\}\leq C t^\alpha,\qquad 0<t\leq1. $$ The exponent and constant are fixed for the distribution under consideration. When $\alpha>0$, the condition implies $P\{\Delta(X)=0\}=0$, by taking $t$ down to zero.

The assumption $C\geq1$ is harmless and follows from the displayed condition at $t=1$. No density for $\Delta(X)$ is assumed. The bounds below therefore apply to discrete as well as continuous margin distributions, including distributions with atoms away from zero.

Dyadic shells near the boundary

Fix a threshold $t\in(0,1]$. The dyadic shells below that threshold are $(2^{-(j+1)}t,2^{-j}t]$, for integers $j\geq0$. Each shell is half as wide in its margin scale as the shell before it. The event $\{\Delta=0\}$ is kept separate, so the shells partition $\{0<\Delta\leq t\}$.

Theorem: Under the small-margin condition, for every $j\geq0$, $$ P\{2^{-(j+1)}t<\Delta(X)\leq2^{-j}t\} \leq C\,2^{-j\alpha}t^\alpha. $$

Proof. The $j$th shell is contained in $\{\Delta(X)\leq2^{-j}t\}$. Applying the small-margin condition at $2^{-j}t$, which lies in $(0,1]$, gives $$ P\{2^{-(j+1)}t<\Delta(X)\leq2^{-j}t\} \leq P\{\Delta(X)\leq2^{-j}t\} \leq C(2^{-j}t)^\alpha = C\,2^{-j\alpha}t^\alpha. $$ $\square$

This bound is deliberately an upper bound, not an estimate of the shell probability. It says that the mass available to a shell at scale $2^{-j}t$ decreases at least geometrically when $\alpha>0$. For $\alpha=0$, it only bounds each shell by $C$, and the number of shells cannot be ignored in a sum.

Worked Example: Checking the Shell Bound for a Discrete Margin

Suppose $\Delta$ takes values $1/8,1/2,1$ with probabilities $0.1,0.3,0.6$, respectively. Verify the small-margin condition with $\alpha=1$, $C=1$, and list the nonempty shells below $t=1$.

For $0<t<1/8$, $P(\Delta\leq t)=0$. For $1/8\leq t<1/2$, this probability is $0.1$, which is at most $t$, since $t\geq1/8=0.125$. For $1/2\leq t<1$, it is $0.4$, which is at most $t$. At $t=1$, it is $1$. Thus $P(\Delta\leq t)\leq t$ throughout $(0,1]$.

The shells for $t=1$ are $(1/2,1]$, $(1/4,1/2]$, and $(1/8,1/4]$, with masses $0.6,0.3,0.1$. The theorem bounds these by $1,1/2,1/4$, respectively. Each actual mass satisfies its bound; the inequalities need not be tight.

Positive truncated moments

A positive power of the margin gives greater weight to points farther from the boundary. On $\{\Delta\leq t\}$, the shell at scale $2^{-j}t$ contributes at most its probability multiplied by the largest possible value of $\Delta^q$ on that shell. Summing those contributions yields a direct bound for a truncated moment.

Theorem: If $q>0$, then $$ E\!\left[\Delta(X)^q\mathbf{1}\{\Delta(X)\leq t\}\right] \leq \frac{C}{1-2^{-(\alpha+q)}}\,t^{\alpha+q}, \qquad 0<t\leq1. $$ Here $\mathbf{1}\{A\}$ is one on event $A$ and zero otherwise.

Proof. The contribution from $\Delta=0$ is zero because $q>0$. On shell $j$, $\Delta^q\leq(2^{-j}t)^q$. By the shell bound, the expectation over that shell is therefore at most $$ (2^{-j}t)^q C\,2^{-j\alpha}t^\alpha =C\,t^{\alpha+q}2^{-j(\alpha+q)}. $$ The shells are disjoint and cover $\{0<\Delta\leq t\}$. Adding their nonnegative contributions gives a geometric series with ratio $2^{-(\alpha+q)}<1$. Its sum is $1/(1-2^{-(\alpha+q)})$, proving the claimed inequality. $\square$

The factor $t^{\alpha+q}$ separates two effects: the small-margin condition contributes $t^\alpha$, while the $q$th power contributes $t^q$. The geometric-series constant records the cost of including every smaller scale, rather than only the outermost shell.

Worked Example: A Continuous Margin Distribution

Let $\Delta$ have distribution function $P(\Delta\leq t)=t^2$ for $0\leq t\leq1$. This is a valid distribution on $[0,1]$, with density $2x$ for $0<x<1$. It satisfies the condition with $\alpha=2$ and $C=1$. Find the truncated first moment at $t=1/4$, then compare it with the dyadic bound.

Using the density, the exact moment is $$ E[\Delta\mathbf{1}\{\Delta\leq1/4\}] =\int_0^{1/4}x(2x)\,dx =2\left[\frac{x^3}{3}\right]_0^{1/4} =\frac{1}{96}. $$

For the bound, set $q=1$, $\alpha=2$, $C=1$, and $t=1/4$. The theorem gives $$ E[\Delta\mathbf{1}\{\Delta\leq1/4\}] \leq\frac{(1/4)^3}{1-2^{-3}} =\frac{1/64}{7/8} =\frac{1}{56}. $$ Indeed, $1/96\leq1/56$. The bound has the correct $t^3$ scaling, but its geometric constant is not intended to match the exact integral.

Truncated inverse moments and exponent regimes

Some arguments weight small margins by a negative power. These weights grow as the boundary is approached, so a lower cutoff $\tau>0$ is essential. Partition $(\tau,1]$ into outward dyadic shells $(2^j\tau,2^{j+1}\tau]$, truncating the last shell at 1. Set $N=\lceil\log_2(1/\tau)\rceil$; the $N$ shells indexed from $j=0$ to $N-1$ cover $(\tau,1]$.

Theorem: For $s>0$ and $0<\tau<1$, the small-margin condition implies $$ E[\Delta(X)^{-s}\mathbf{1}\{\Delta(X)>\tau\}] \leq C\,2^\alpha\tau^{\alpha-s} \sum_{j=0}^{N-1}2^{j(\alpha-s)}, \qquad N=\lceil\log_2(1/\tau)\rceil. $$ Consequently, the bound is of order $C\tau^{\alpha-s}$ if $\alpha<s$, of order $C\log(1/\tau)$ if $\alpha=s$, and bounded uniformly in $\tau$ if $\alpha>s$. Constants in these order statements may depend on $\alpha$ and $s$.

Proof. On shell $j$, $\Delta^{-s}\leq(2^j\tau)^{-s}$. Its probability is at most the probability that $\Delta\leq2^{j+1}\tau$. If this endpoint exceeds 1, the probability is at most 1, which is also at most $C(2^{j+1}\tau)^\alpha$, since $C\geq1$. Otherwise the small-margin condition gives the same upper bound. Thus the contribution from shell $j$ is at most $$ (2^j\tau)^{-s}C(2^{j+1}\tau)^\alpha =C\,2^\alpha\tau^{\alpha-s}2^{j(\alpha-s)}. $$ Summing over the $N$ shells proves the displayed inequality. If $\alpha<s$, the sum is bounded by the infinite geometric sum with ratio $2^{\alpha-s}<1$. If $\alpha=s$, all $N$ summands equal one, and $N$ is of order $\log(1/\tau)$. If $\alpha>s$, the sum is at most a constant times $2^{N(\alpha-s)}$; since $2^N\tau<2$, multiplication by $\tau^{\alpha-s}$ leaves a constant bound. $\square$

The three regimes arise from the direction of the geometric series. When $\alpha<s$, the smallest retained margins dominate. When $\alpha=s$, each scale contributes comparably, so the number of scales appears. When $\alpha>s$, the outer scales dominate, and the bound stays finite as the cutoff decreases.

Worked Example: The Critical Inverse-Moment Case

Let $\Delta$ be uniform on $[0,1]$. Then $P(\Delta\leq t)=t$, so the condition holds with $\alpha=1,C=1$. Take $s=1$ and $\tau=1/16$, and compare the exact truncated inverse moment with the dyadic bound.

Direct integration gives $$ E[\Delta^{-1}\mathbf{1}\{\Delta>1/16\}] =\int_{1/16}^1\frac{1}{x}\,dx =\log(16) =4\log(2). $$ Here $N=\lceil\log_2(16)\rceil=4$ and $\alpha=s=1$. The theorem gives $$ E[\Delta^{-1}\mathbf{1}\{\Delta>1/16\}] \leq 2\sum_{j=0}^{3}1 =8. $$ Since $4\log(2)$ is approximately $2.77$, the inequality holds. The four equal terms in the bound display the critical feature: each dyadic scale receives the same upper allowance, producing logarithmic growth in the number of scales.

Common mistake and practical use

A common mistake is to bound every shell by the small-margin probability at the original threshold and then add that same bound over infinitely many shells. That loses the scale dependence and may give a divergent or uninformative sum. The correction is to apply the condition at the shell's own endpoint: the $j$th inward shell uses $2^{-j}t$, producing the factor $2^{-j\alpha}$. For positive moments there is an additional factor $2^{-jq}$; for inverse moments the outward shells instead carry $2^{j(\alpha-s)}$.

These calculations are useful whenever a proof divides errors or weights according to distance from the classification boundary. They make explicit which scales control a bound and whether a sum is finite, logarithmic, or dominated by its smallest retained margin. They do not by themselves assert a learning rate: that requires the other assumptions and arguments of the particular learning problem.

Key takeaway: Apply the margin condition at each shell's own endpoint, then include the weight contributed by the quantity being summed. The resulting geometric ratio determines whether the aggregate is bounded, logarithmic, or power-sized.

Check Your Understanding

Use the shell endpoint in each calculation, and distinguish bounds on probabilities from bounds on weighted moments.

Under the small-margin condition, what upper bound applies to the probability of the shell $(t/8,t/4]$?
Why does the positive-moment theorem require $q>0$ when the margin distribution may have an atom at zero?
For $\alpha=2$, $q=1$, and threshold $t$, what power of $t$ appears in the truncated positive-moment bound?
For a truncated inverse moment with $\alpha=s$, why does the dyadic sum grow with the number of shells?
In the discrete example, why is the shell bound valid even though the actual shell masses are smaller than the bounds?