Why an Oracle Bound Needs Conditions
Lepski’s method chooses among estimators computed at several smoothing scales by comparing them pairwise. The goal is to retain a relatively fine scale when its estimate remains compatible with coarser estimates, without knowing the unknown bias at any scale. A finite-sample oracle inequality makes this goal precise: it compares the selected estimator with a suitable candidate’s bias-variance trade-off.
There is an important qualification. Pairwise comparisons do not guarantee that every candidate with small bias plus variance will pass the selector. Its deterministic means must also be sufficiently compatible with the comparison thresholds. Likewise, bounds on noise at each scale do not automatically give a bound at the finest scale that is uniform over all estimators. We state these conditions explicitly rather than claiming an unrestricted oracle bound.
Setup and Selector
\(\hat j=\max\{j:\|\hat\theta_j-\hat\theta_k\|\le A r_k\ \text{for every }k<j\}\).
The condition is vacuous for \(j=1\), so the set is nonempty.
For a fine candidate \(j\), the selector compares it with every coarser candidate \(k<j\), using the coarser scale \(r_k\) as the threshold. The pairwise difference decomposes exactly as
The first term is deterministic and reflects compatibility of the means. The second is stochastic. The triangle inequality gives \(\|\xi_j-\xi_k\|\le\|\xi_j\|+\|\xi_k\|\), so scale-specific noise bounds control the comparison at scale \(k\), since \(r_j\le r_k\).
A Finite-Sample Oracle Inequality
Fix \(\beta\ge0\). Call candidate \(j\) \(\beta\)-compatible if its deterministic means satisfy all the relevant comparison bounds:
For \(j=1\), the maximum is over an empty set, and the condition is taken to hold. This definition is sufficient, not necessary: it ensures that every pairwise mean difference involving candidate \(j\) is small enough for the selector’s tests.
\(\mathcal E=\{\|\xi_j\|\le u r_j\text{ for all }j\}\cap\{\|\xi_j\|\le u r_M\text{ for all }j\}\).
On \(\mathcal E\), the selector satisfies
\(\|\hat\theta_{\hat j}-\theta\|\le\min_{j\in\mathcal J_\beta}\{B_j+(A+u)r_j\}\),
where \(\mathcal J_\beta\) is the set of \(\beta\)-compatible indices. In addition, \(\|\hat\theta_{\hat j}-\theta\|\le B_{\hat j}+u r_M\). If \(P(\mathcal E)\ge1-\delta\), both inequalities hold with probability at least \(1-\delta\).
The first bound is an oracle inequality over compatible candidates. The second uses the uniform finest-scale noise bound and is a direct bound for the selected index. The uniform condition is included in the theorem’s event; it does not follow merely from the scale-specific inequalities.
Proof. Fix any \(j\in\mathcal J_\beta\). For each \(k<j\), the bias part of the comparison satisfies
On \(\mathcal E\), the stochastic part satisfies
because \(j>k\) implies \(r_j\le r_k\). Therefore
Thus \(j\) passes every comparison and is an eligible index in the selector’s defining set. Since \(\hat j\) is its largest eligible index, \(\hat j\ge j\). If \(\hat j>j\), the selector’s test at index \(\hat j\), with coarser index \(j\), gives \(\|\hat\theta_{\hat j}-\hat\theta_j\|\le A r_j\). If \(\hat j=j\), this difference is zero, so the same bound holds. Consequently,
This holds for every \(j\in\mathcal J_\beta\), giving the minimum in the theorem. Separately, the uniform part of \(\mathcal E\) implies \(\|\xi_{\hat j}\|\le u r_M\), regardless of the selected index. Hence
The event is an intersection of finitely many measurable inequalities, and the selector is measurable because it is defined from finitely many comparisons. The probability statement follows directly from \(P(\mathcal E)\ge1-\delta\). \(\square\)
Reading the Bound as a Bias-Variance Trade-Off
The oracle score \(B_j+(A+u)r_j\) has the usual form: deterministic approximation error plus a stochastic scale penalty. But the minimum in the theorem is taken over \(\mathcal J_\beta\), not automatically over every index. If an index minimizing \(B_j+(A+u)r_j\) over the full grid is \(\beta\)-compatible, then the theorem gives the ordinary grid oracle bound at that index. Without compatibility, that conclusion does not follow from this argument.
This distinction is useful in applications. A structural bias calculation may establish compatibility for the scales around the bias-variance balance, or a more detailed model-specific argument may yield a different oracle comparison. The finite-sample theorem should match the conditions actually verified for the estimator and grid.
Worked Example: Checking Compatibility and the Bound
Let \(\mathcal H=\mathbb R\), \(\theta=0\), \(M=3\), and \((r_1,r_2,r_3)=(1,0.5,0.25)\). Take deterministic means \((\mu_1,\mu_2,\mu_3)=(0.20,0.08,0.02)\), so \((B_1,B_2,B_3)=(0.20,0.08,0.02)\). Choose \(\beta=0.30\).
For \(j=2\), the compatibility ratio is \((B_1+B_2)/r_1=(0.20+0.08)/1=0.28\). For \(j=3\), the ratios are \((B_1+B_3)/r_1=0.22\) and \((B_2+B_3)/r_2=0.20\). Thus all three indices are \(\beta\)-compatible.
Suppose \(u=0.20\), \(A=1\), and the observed stochastic errors are \((0.03,0.02,0.01)\). The required threshold condition holds because \(1\ge0.30+2(0.20)=0.70\). The errors satisfy \(|\xi_j|\le u r_j\): the three upper bounds are \(0.20,0.10,0.05\). They also satisfy the finest-scale uniform condition \(|\xi_j|\le u r_3=0.05\).
The estimates are \((0.23,0.10,0.03)\). Their differences are \(0.13\le1\) for indices 1 and 2, \(0.20\le1\) for indices 1 and 3, and \(0.07\le0.5\) for indices 2 and 3. Hence index 3 passes and \(\hat j=3\). The oracle scores \(B_j+(A+u)r_j\) are \(1.40\), \(0.68\), and \(0.32\), respectively. The theorem bounds the selected error by \(0.32\); the actual error is \(|0.03-0|=0.03\).
Worked Example: Why the Uniform Finest-Scale Condition Is Separate
Consider the two-scale construction \(M=2\), \(A=u=1\), \(r_1=1\), \(r_2=0.1\), and \(\theta=\mu_1=\mu_2=0\). Let \(Z\) equal \(1\) or \(-1\) with equal probability, and set \(\xi_1=Z\), \(\xi_2=-0.1Z\). Both biases are zero, so both indices are compatible for any \(\beta\ge0\).
The scale-specific bounds hold: \(|\xi_1|=1=u r_1\) and \(|\xi_2|=0.1=u r_2\). The pairwise stochastic difference is \(|\xi_1-\xi_2|=1.1\). Thus a pairwise deviation allowance \(v r_1\) with \(v=1.1\) holds, but the selector with threshold \(A r_1=1\) rejects index 2 and selects index 1. Its error is \(1\), whereas the unrestricted bias-plus-scale minimum is \(\min(1,0.1)=0.1\).
This does not contradict the theorem: the finest-scale uniform condition would require \(|\xi_1|\le u r_2=0.1\), which fails. In this example, even the compatible-candidate bound on the event cannot be invoked. Pairwise control at a coarse threshold is not a substitute for a uniform bound at the finest scale.
Worked Example: A Simple Probability Check for the Event
Suppose \(M=4\), \(r_4=0.1\), and the errors are independent \(N(0,0.01^2)\) random variables. Set \(u=1\). Since \(r_j\ge r_4\), the single condition \(\max_j|\xi_j|\le0.1\) implies both parts of \(\mathcal E\): it gives \(|\xi_j|\le u r_4\le u r_j\), as well as the uniform finest-scale bound.
For a centered normal variable with standard deviation \(0.01\), the Gaussian tail bound gives \(P(|\xi_j|>0.1)\le2\exp[-0.1^2/(2(0.01)^2)]=2e^{-50}\). By the union bound, \(P(\mathcal E)\ge1-8e^{-50}\). Therefore the theorem’s inequalities hold with probability at least \(1-8e^{-50}\), provided \(A\ge\beta+2\). This calculation is conservative, but it verifies the event probability directly.
Common Pitfall
A tempting but invalid shortcut is to prove the oracle inequality using only \(\|\xi_j\|\le u r_j\) for each index and then claim that a selected estimate finer than an oracle candidate is controlled by that candidate. The selector’s comparison can control the difference between those estimates only when the relevant candidate passes; if it fails, a scale-specific noise bound alone does not turn the failure into the claimed oracle bound. The two-scale example shows the problem numerically.
The correction is to state the event and oracle class that the proof actually supports. Here, compatibility ensures that every candidate in \(\mathcal J_\beta\) passes, while the finest-scale uniform condition separately controls the selected noise by \(u r_M\). Neither condition should be silently inferred from the other.
Check Your Understanding
Use the definitions and inequalities above to answer the following questions.
- Why does the proof use \(r_j\le r_k\) when bounding the stochastic part of a comparison with \(k<j\)?
- For given biases and scales, how would you check whether an index \(j\) is \(\beta\)-compatible?
- What additional condition is needed to conclude \(\|\xi_{\hat j}\|\le u r_M\), and why does it not follow from \(\|\xi_j\|\le u r_j\) alone?
- If the full-grid minimizer of \(B_j+(A+u)r_j\) is not compatible, what does the theorem guarantee instead?
- In the two-scale example, which part of the theorem’s event fails, and what is the selected estimator’s error?