Worked Minimax Rate Comparisons Across Regimes

Introduction

A minimax rate is a concise summary of how difficult a learning problem remains as the sample size grows. In binary classification, that difficulty depends not only on how smoothly the conditional class probability varies, but also on how much probability mass lies near the decision boundary. The purpose here is to turn those ingredients into a rate and compare the results across regimes.

The central calculation is simple once the rate is stated: combine the input dimension, the smoothness exponent, and the margin (or noise) exponent. The important judgment is recognizing whether the resulting exponent is below, equal to, or above one. That comparison separates slower polynomial rates from the parametric \(n^{-1}\) regime.

Rate Ingredients and the Comparison Rule

Let \(X\in[0,1]^d\) be the feature vector and \(Y\in\{0,1\}\) the class label. Write \(\eta(x)=P(Y=1\mid X=x)\). A Bayes classifier predicts the more probable class at each \(x\); for example, it predicts class 1 when \(\eta(x)\geq 1/2\). For a classifier \(\hat g\), its excess risk is its misclassification risk minus the risk of a Bayes classifier. The minimax excess risk is the smallest worst-case expected excess risk achievable over a specified class of data-generating distributions using \(n\) observations.

Definition: A margin condition with exponent \(\alpha\geq 0\) and constant \(C\) is a bound of the form \(P_X(0<|\eta(X)-1/2|\leq t)\leq Ct^\alpha\) for \(0<t\leq 1/2\). Larger \(\alpha\) means less probability mass near the decision boundary. The case \(\alpha=0\) is the weak-noise case: this inequality imposes no polynomial decay of boundary-near mass as \(t\) decreases.

Assume the regression function \(\eta\) belongs to a Hölder-smoothness class of order \(\beta>0\), and that the feature distribution and the classes of regression functions are regular and rich enough for the standard upper and lower minimax bounds to apply. The exact constants, and sometimes logarithmic factors in particular formulations, depend on the class. The polynomial-rate comparison used here is the standard smoothness–margin rate.

Rate rule: Under the usual nondegeneracy conditions for the smoothness–margin classification problem, the minimax excess-risk rate is, up to constant factors, \(n^{-\rho}\), where \(\rho=\min\left\{1,\frac{\beta(1+\alpha)}{2\beta+d}\right\}\). The uncapped exponent is \(\rho_{\mathrm{raw}}=\frac{\beta(1+\alpha)}{2\beta+d}\). When \(\rho_{\mathrm{raw}}\geq 1\), the polynomial rate is the parametric rate \(n^{-1}\).

This is a minimax rate statement, not a claim that every estimator automatically attains the rate. It also presumes the model class and assumptions behind the standard result; a rate formula cannot replace checking whether a particular problem belongs to that class.

Worked Comparisons

Worked Example: Weak Noise Versus a Positive Margin Exponent

Compare weak noise and a low-noise condition with \(\alpha=1\), keeping dimension \(d=4\) and smoothness \(\beta=1\) fixed.

With weak noise, \(\alpha=0\). The uncapped exponent is \(\rho_{\mathrm{raw}}=\frac{1(1+0)}{2(1)+4}=\frac{1}{6}\). Since \(1/6<1\), there is no saturation, and the rate is \(n^{-1/6}\).

With \(\alpha=1\), the exponent becomes \(\rho_{\mathrm{raw}}=\frac{1(1+1)}{2(1)+4}=\frac{2}{6}=\frac{1}{3}\). This is also below one, so the rate is \(n^{-1/3}\). The low-noise condition improves the polynomial rate: \(n^{-1/3}\) decreases faster than \(n^{-1/6}\) as \(n\) grows. Neither case is saturated.

Worked Example: Finding the Saturation Threshold

Let \(d=3\) and \(\beta=1\). Find the margin exponent at which the raw rate first reaches \(n^{-1}\).

The threshold is obtained by setting the raw exponent equal to one: \(\frac{\beta(1+\alpha)}{2\beta+d}=1\). Multiplying both sides by the positive denominator gives \(\beta(1+\alpha)=2\beta+d\), hence \(\alpha\beta=\beta+d\). For the specified values, \(\alpha=1+3=4\).

At \(\alpha=4\), the raw exponent is \(\frac{1(1+4)}{2+3}=1\), so the rate is \(n^{-1}\). At \(\alpha=5\), it is \(\frac{1(1+5)}{5}=\frac{6}{5}\). The exponent is capped at one, so the rate remains \(n^{-1}\), not \(n^{-6/5}\).

Worked Example: Saturation with Greater Smoothness

Take \(d=2\), \(\beta=2\), and \(\alpha=2\). Calculate the rate and verify that it is exactly at the saturation boundary.

The raw exponent is \(\rho_{\mathrm{raw}}=\frac{2(1+2)}{2(2)+2}=\frac{6}{6}=1\). Equivalently, the threshold condition is \(\alpha\beta\geq\beta+d\). Here \(\alpha\beta=2\cdot2=4\) and \(\beta+d=2+2=4\), so equality holds. The rate is \(n^{-1}\).

For comparison, if \(\alpha=1\) with the same \(d\) and \(\beta\), the raw exponent is \(\frac{2(2)}{6}=\frac{2}{3}\), giving \(n^{-2/3}\). Increasing \(\alpha\) from 1 to 2 moves this setting from an unsaturated rate to the parametric boundary.

Why the Regimes Have These Boundaries

The saturation condition follows directly from the rate formula. Since \(2\beta+d>0\), multiplying an inequality by this denominator preserves its direction:

\rho_{\mathrm{raw}}\geq 1 \quad\Longleftrightarrow\quad \frac{\beta(1+\alpha)}{2\beta+d}\geq 1 \quad\Longleftrightarrow\quad \beta+\alpha\beta\geq 2\beta+d \quad\Longleftrightarrow\quad \alpha\beta\geq\beta+d.

Thus the saturation threshold for the margin exponent is \(\alpha_{\mathrm{sat}}=1+d/\beta\). Below it, the rate exponent is \(\beta(1+\alpha)/(2\beta+d)\); at or above it, the polynomial exponent is one. This algebra also guards against a tempting but incorrect shortcut: the criterion is not merely \(\alpha\beta\geq d\).

Derived comparison: Fix \(d\) and \(\beta\), and compare two unsaturated margin exponents \(0\leq\alpha_1<\alpha_2<1+d/\beta\). Their rate exponents differ by \(\rho(\alpha_2)-\rho(\alpha_1)=\frac{\beta(\alpha_2-\alpha_1)}{2\beta+d}>0\). Therefore the larger margin exponent gives the faster polynomial rate, as long as both settings remain unsaturated.

To verify this comparison, substitute the uncapped formula for each exponent and subtract:

\rho(\alpha_2)-\rho(\alpha_1) = \frac{\beta(1+\alpha_2)}{2\beta+d} - \frac{\beta(1+\alpha_1)}{2\beta+d} = \frac{\beta(\alpha_2-\alpha_1)}{2\beta+d}.

The numerator and denominator on the right are positive, so the difference is positive. The corresponding rate \(n^{-\rho}\) decreases more quickly when \(\rho\) is larger, for \(n>1\). Once the exponent reaches one, further increases in \(\alpha\) do not improve the polynomial minimax rate under this rule. \(\square\)

Interpreting the Three Regimes

Regime	Condition	Rate exponent
Weak noise	\(\alpha=0\)	\(\beta/(2\beta+d)\)
Low noise, unsaturated	\(0<\alpha<1+d/\beta\)	\(\beta(1+\alpha)/(2\beta+d)\)
Saturated	\(\alpha\geq 1+d/\beta\)	1

In the weak-noise case, the margin assumption provides no improvement over the base smoothness-dependent exponent. A positive but sub-threshold \(\alpha\) improves the exponent, and the amount of improvement is \(\beta\alpha/(2\beta+d)\). Saturation means that the raw exponent has reached or passed one, so the stated polynomial rate has reached \(n^{-1}\). These are comparisons of asymptotic orders; they do not say that one rate is numerically smaller at every finite sample size once unknown constants are included.

Dimension and smoothness matter in complementary ways. Increasing \(d\) enlarges the denominator and lowers the raw exponent. Increasing \(\beta\) raises the numerator and also changes the denominator, so its effect should be calculated rather than described from the numerator alone. The threshold \(\alpha_{\mathrm{sat}}=1+d/\beta\) makes the interaction explicit: for fixed \(d\), greater smoothness lowers the margin exponent needed to reach saturation.

Common Pitfall

A common error is to compute \(\rho_{\mathrm{raw}}>1\) and report \(n^{-\rho_{\mathrm{raw}}}\) as the minimax rate. For instance, with \(d=3,\beta=1,\alpha=5\), the raw exponent is \(6/5\), but the rate rule gives \(\rho=\min\{1,6/5\}=1\), hence \(n^{-1}\). The correction is to apply the cap after calculating the raw exponent.

A second error is to use \(\alpha\beta\geq d\) as the saturation test. Substitution into the rate formula shows that the correct condition is \(\alpha\beta\geq\beta+d\). The extra \(\beta\) comes from the \(1+\alpha\) in the numerator, which contributes both the baseline smoothness term and the margin contribution.

Key takeaway: Calculate \(\rho_{\mathrm{raw}}=\beta(1+\alpha)/(2\beta+d)\), then report \(\rho=\min\{1,\rho_{\mathrm{raw}}\}\). Weak noise has \(\alpha=0\); positive sub-threshold \(\alpha\) improves the rate; saturation begins at \(\alpha\beta=\beta+d\).

Check Your Understanding

For each question, show the exponent calculation before naming the regime.

For \(d=5,\beta=2,\alpha=0\), what is the rate exponent, and is the setting saturated?
For \(d=2,\beta=1\), calculate the raw exponent at \(\alpha=1\). How does it compare with the weak-noise exponent?
Derive the saturation threshold for \(\alpha\) from the condition \(\rho_{\mathrm{raw}}\geq1\).
For \(d=4,\beta=2,\alpha=4\), calculate the raw exponent and the capped rate exponent.
Why can a larger margin exponent improve an unsaturated rate but fail to improve the polynomial rate after saturation?