Oracle Inequalities for Thresholded Series

Why Compare Thresholding With an Oracle?

A thresholded wavelet estimate makes a separate keep-or-delete decision for each empirical coefficient. An ideal decision-maker would know the underlying signal coefficients and could choose the more favorable action for each one. Comparing these procedures gives a way to assess thresholding without claiming that the threshold selects the ideal action every time. The comparison has two parts: a benchmark for the best ideal decisions, and a remainder accounting for noise large enough to affect thresholding.

We work with a finite, orthonormal series on a fixed design. The conclusions below are coefficientwise and do not require independent coefficient errors. In particular, although empirical wavelet coefficients may be dependent, the bound can still be summed across them.

Model and Ideal Keep-or-Delete Benchmark

Let $x_1,\ldots,x_n$ be fixed design points, and suppose $Y_i=f(x_i)+\varepsilon_i$. Let $\{\phi_j:j\in\mathcal J\}$ be a finite collection of basis functions that is orthonormal for the empirical inner product $ \langle g,h\rangle_n=n^{-1}\sum_{i=1}^n g(x_i)h(x_i) $. Write $\theta_j=\langle f,\phi_j\rangle_n$ for the coefficient of the projection of the signal onto $\phi_j$. The empirical coefficient and its noise are $ \widehat\theta_j=n^{-1}\sum_{i=1}^nY_i\phi_j(x_i) $ and $Z_j=\widehat\theta_j-\theta_j$.

Definition: For a fixed threshold $t>0$, the hard-thresholded coefficient is $ \widetilde\theta_j=\widehat\theta_j\mathbf 1\{|\widehat\theta_j|\geq t\} $. An ideal keep-or-delete action is a number $m_j\in\{0,1\}$, producing coefficient $m_j\theta_j$ if the signal coefficient were known. We use the ideal benchmark $ \min\{\theta_j^2,t^2\} $: deleting costs $\theta_j^2$, while keeping is assigned the threshold-scale cost $t^2$.

This benchmark is a deterministic approximation-versus-complexity comparison, not automatically the expected squared error of keeping the noisy coefficient. If one instead evaluates the realized action $m_j\widehat\theta_j$, its loss depends on the realized noise. Keeping these two comparisons distinct is essential in a pointwise proof.

Worked Example: Choosing the Ideal Actions

Take $t=1.2$ and signal coefficients $(\theta_1,\theta_2,\theta_3)=(0.2,1.5,0.5)$. For each coefficient, compare the cost of deleting, $\theta_j^2$, with the keep cost $t^2=1.44$.

For coefficient 1, deletion costs $0.2^2=0.04$, less than 1.44, so the ideal action is delete. For coefficient 2, deletion costs $1.5^2=2.25$, greater than 1.44, so the ideal action is keep. For coefficient 3, deletion costs $0.5^2=0.25$, less than 1.44, so the ideal action is delete. The summed ideal benchmark is $0.04+1.44+0.25=1.73$.

The action for coefficient 2 is keep because $2.25>1.44$; the comparison is between squared signal size and squared threshold, not between the signal and a noise realization.

A Pointwise Oracle Inequality

Theorem: For every real signal coefficient $\theta$, every real noise value $z$, and every threshold $t>0$, define $y=\theta+z$ and $\widetilde\theta=y\mathbf 1\{|y|\geq t\}$. Then $$ (\widetilde\theta-\theta)^2 \leq 4\min\{\theta^2,t^2\} + 4z^2\mathbf 1\{|z|>t/2\}. $$ Consequently, for any finite coefficient set $\mathcal J$, $$ \sum_{j\in\mathcal J}(\widetilde\theta_j-\theta_j)^2 \leq 4\sum_{j\in\mathcal J}\min\{\theta_j^2,t^2\} + 4\sum_{j\in\mathcal J}Z_j^2\mathbf 1\{|Z_j|>t/2\}. $$

The first term is exactly the sum of the best ideal keep-or-delete costs defined above. The second term is zero for coefficients whose noise magnitude is at most half the threshold. It records a stochastic remainder only for coefficients with larger noise.

Proof. First suppose $|z|\leq t/2$. If thresholding keeps $y$, then $|y|\geq t$, and the triangle inequality gives $|\theta|\geq |y|-|z|\geq t/2$. The squared error is $z^2\leq t^2/4$. If $|\theta|\leq t$, then $\theta^2\geq t^2/4$, so $z^2\leq\min\{\theta^2,t^2\}$. If $|\theta|>t$, then $z^2\leq t^2/4\leq\min\{\theta^2,t^2\}$. Thus the claimed bound holds when the coefficient is kept.

If thresholding deletes $y$, the squared error is $\theta^2$, and $|y|<t$ implies $|\theta|\leq |y|+|z|<3t/2$. When $|\theta|\leq t$, the error equals $\min\{\theta^2,t^2\}$. When $t<|\theta|<3t/2$, it is less than $9t^2/4$, which is at most $4\min\{\theta^2,t^2\}=4t^2$. This proves the inequality for $|z|\leq t/2$.

Now suppose $|z|>t/2$. If thresholding keeps $y$, its squared error is $z^2$, which is at most the right-hand side because that side includes $4z^2$. If it deletes $y$, then $|y|<t$, so $\theta^2=(y-z)^2\leq2y^2+2z^2<2t^2+2z^2$. For $\theta^2\leq t^2$, the term $4\min\{\theta^2,t^2\}=4\theta^2$ alone bounds the error. For $\theta^2>t^2$, the right-hand side is $4t^2+4z^2$, which exceeds $2t^2+2z^2>\theta^2$. The scalar inequality holds in every case. Applying it separately to each $j$ and summing proves the finite-sum inequality. $\square$

Worked Example: Checking a Pointwise Comparison

Use $t=1.2$, signal coefficients $(0.2,1.5,0.5)$, and realized noises $(0.2,-0.2,0.8)$. The observed coefficients are $(0.4,1.3,1.3)$. Thresholding deletes the first and keeps the second and third. From the preceding example, the ideal actions are delete, keep, delete. Thus thresholding agrees with the ideal action on the first two coefficients and disagrees only on the third.

The thresholded squared errors are $(0.2)^2=0.04$, $(1.3-1.5)^2=0.04$, and $(1.3-0.5)^2=0.64$, totaling $0.72$. The ideal benchmark is $1.73$. Only the third noise exceeds $t/2=0.6$, so the stochastic remainder before its factor of 4 is $0.8^2=0.64$. The theorem's right-hand side is $4(1.73)+4(0.64)=9.48$, which bounds $0.72$.

A different pointwise comparison uses the realized losses of the ideal actions when applied to the observed coefficients: deleting the first incurs $0.04$, keeping the second incurs $0.04$, and deleting the third incurs $0.25$. Their sum is $0.33$, not the expected risk of those actions. It is also not the benchmark $1.73$. These are three distinct quantities, and they should not be substituted for one another.

Expected Risk and the Noise Remainder

Corollary: If $E[Z_j^2]<\infty$ for every $j\in\mathcal J$, then $$ \sum_{j\in\mathcal J}E[(\widetilde\theta_j-\theta_j)^2] \leq 4\sum_{j\in\mathcal J}\min\{\theta_j^2,t^2\} + 4\sum_{j\in\mathcal J}E\!\left[Z_j^2\mathbf 1\{|Z_j|>t/2\}\right]. $$

To prove this, take expectations in the pointwise inequality. The coefficient set is finite, so expectation distributes over the sum without any interchange of an infinite sum and a limit. The benchmark is deterministic because the signal coefficients and threshold are fixed. The assumed second moments ensure the remainder expectations are finite. No independence between the $Z_j$'s is needed. $\square$

The expected remainder retains the tail contribution at the actual cutoff $t/2$. A simple but less informative consequence is $ E[Z_j^2\mathbf 1\{|Z_j|>t/2\}]\leq E[Z_j^2] $. More detailed bounds require additional assumptions on the noise distribution. The inequality itself does not prescribe a way to calibrate $t$.

Worked Example: An Exact Stochastic Remainder

Let there be one coefficient with $\theta=0.4$, threshold $t=1$, and noise $Z$ equal to $0.7$ or $-0.7$, each with probability $1/2$. The observed coefficient is $1.1$ in the first case and $-0.3$ in the second. Hard thresholding keeps $1.1$, giving squared error $(1.1-0.4)^2=0.49$, and deletes $-0.3$, giving squared error $0.4^2=0.16$. Its expected risk is therefore $(0.49+0.16)/2=0.325$.

The ideal benchmark is $\min\{0.4^2,1^2\}=0.16$. Since $|Z|=0.7>t/2=0.5$ in both outcomes, the expected stochastic remainder before its factor of 4 is $E[Z^2\mathbf 1\{|Z|>0.5\}]=0.49$. The bound gives $0.325\leq4(0.16)+4(0.49)=2.6$. This bound is not tight here; its purpose is a valid comparison that isolates the large-noise contribution.

From Coefficient Error to Regression Risk

Orthonormality makes the coefficientwise result relevant to the fitted function. Define the empirical projection $f_{\mathcal J}=\sum_{j\in\mathcal J}\theta_j\phi_j$ and the thresholded fit $\widetilde f=\sum_{j\in\mathcal J}\widetilde\theta_j\phi_j$. Since $f-f_{\mathcal J}$ is orthogonal, under the empirical inner product, to every basis function in the collection, it is orthogonal to $\widetilde f-f_{\mathcal J}$. Hence

\begin{aligned} \|\widetilde f-f\|_n^2 &=\|(\widetilde f-f_{\mathcal J})-(f-f_{\mathcal J})\|_n^2\\ &=\|\widetilde f-f_{\mathcal J}\|_n^2+\|f-f_{\mathcal J}\|_n^2\\ &=\sum_{j\in\mathcal J}(\widetilde\theta_j-\theta_j)^2+\|f-f_{\mathcal J}\|_n^2 . \end{aligned}

The second equality follows by expanding the squared norm: its cross term is zero by orthogonality. For the last equality, expand $\widetilde f-f_{\mathcal J}=\sum_j(\widetilde\theta_j-\theta_j)\phi_j$; the cross-products vanish and each basis function has empirical squared norm one. Combining this identity with the coefficientwise inequality bounds the fitted risk by the projection error plus four times the ideal benchmark and four times the stochastic remainder. This is an exact finite-dimensional decomposition; it does not bound error outside the span by thresholding.

Worked Example: Verifying the Empirical Risk Decomposition

Take $n=2$, basis vectors $\phi_1=(1,1)$ and $\phi_2=(1,-1)$, and empirical norm $\|g\|_n^2=(g_1^2+g_2^2)/2$. Their empirical squared norms are both 1 and their empirical inner product is 0. Let the signal be $f=(2,0)=1\phi_1+1\phi_2$, and let the observed response be $Y=(2.4,-0.4)$. The empirical coefficients are $\widehat\theta_1=(2.4-0.4)/2=1$ and $\widehat\theta_2=(2.4+0.4)/2=1.4$.

With $t=1.2$, thresholding deletes the first coefficient and keeps the second, so $\widetilde f=1.4\phi_2=(1.4,-1.4)$. Directly, its empirical squared error from $f$ is $\{(1.4-2)^2+(-1.4-0)^2\}/2=(0.36+1.96)/2=1.16$. In coefficient form the error is $(0-1)^2+(1.4-1)^2=1+0.16=1.16$, agreeing exactly. The noise coefficients are $0$ and $0.4$; neither exceeds $t/2=0.6$. The ideal benchmark is $\min\{1,1.44\}+\min\{1,1.44\}=2$, so the pointwise bound gives $1.16\leq4(2)+0$.

Interpretation and a Common Pitfall

The inequality says that thresholding has controlled error relative to a coefficientwise ideal choice, up to a remainder for unusually large coefficient noise. It does not say that the threshold agrees with the oracle, that the bound is sharp, or that the oracle benchmark equals the expected risk. In a wavelet basis, $\mathcal J$ may index locations and scales; the same proof applies to any finite orthonormal collection, including a boundary-corrected one.

Pitfall: replacing realized loss by expected risk inside a pointwise argument. A pointwise inequality is evaluated at the realized noise values. For example, keeping a coefficient has realized loss $Z_j^2$, whereas its expected loss is $E[Z_j^2]$. They are not interchangeable before taking expectations.
Pitfall: charging disagreement without checking which action differs. If thresholding keeps a coefficient that the ideal rule deletes, that is one disagreement. If both rules keep it, there is no disagreement, even if the coefficient is near the threshold.
Pitfall: treating the benchmark as the exact oracle risk. Here $\min\{\theta_j^2,t^2\}$ compares deletion with a threshold-scale keep cost. It is a useful deterministic benchmark, but the risk of keeping the noisy coefficient is governed by the noise distribution.

The explicit remainder also clarifies why noise behavior matters: coefficients with $|Z_j|\leq t/2$ are handled by the ideal benchmark alone in the pointwise proof, while larger noise values are charged separately. Turning that remainder into a sharper numerical guarantee requires distributional information beyond the deterministic inequality.

Check Your Understanding

Use the stated threshold convention and distinguish pointwise losses from expectations.

For $t=2$ and $\theta=0.6$, which ideal action minimizes the benchmark, and what is its cost?
Why does the pointwise inequality's stochastic remainder vanish when $|z|\leq t/2$?
For a kept coefficient, express its realized squared error in terms of $z$. What is its expected squared error?
What assumptions on dependence among the coefficient noises are needed to sum the expected oracle inequality over a finite set?
In the empirical risk decomposition, which orthogonality makes the cross term vanish?