Epsilon-Complete Classes and Approximate Replacement

Why Approximate Replacement Is Useful

A class of decision rules may be simpler to work with than the full class: it might contain only rules with a particular structure, or a manageable collection of rules that approximate a larger family. Exact risk domination can be too demanding in such a setting. A more flexible question is whether a rule in the simpler class can have risk no more than a specified amount above the target rule's risk, at every parameter value.

The tolerance must be uniform over the parameter space. A replacement that is excellent at most parameter values but has a large risk increase at one value does not satisfy a small uniform tolerance. The definitions below make this requirement precise and show how a bound on risk approximation produces an approximate replacement.

Epsilon-Domination and Epsilon-Completeness

Definition: Consider a decision problem with parameter space $\Theta$, rule class $\mathcal{D}$, and finite risk $R(\theta,\delta)$ for every $\theta\in\Theta$ and $\delta\in\mathcal{D}$. For $\varepsilon\geq 0$, a rule $\delta'$ epsilon-dominates a rule $\delta$ if $$ R(\theta,\delta')\leq R(\theta,\delta)+\varepsilon \qquad\text{for every }\theta\in\Theta. $$ A subclass $\mathcal{C}\subseteq\mathcal{D}$ is epsilon-complete in $\mathcal{D}$ if, for every $\delta\in\mathcal{D}$, there is a $\delta'\in\mathcal{C}$ that epsilon-dominates $\delta$.

Equivalently, the largest positive risk increase of $\delta'$ over $\delta$ is at most $\varepsilon$: $$ \sup_{\theta\in\Theta}\bigl[R(\theta,\delta')-R(\theta,\delta)\bigr]_+\leq\varepsilon, \qquad [x]_+=\max(x,0). $$ This is a one-sided condition. The replacement may improve risk by any amount at some parameter values; only its risk increases are capped. In this tutorial, epsilon-domination does not require a strict improvement at any parameter value. At $\varepsilon=0$, it is weak pointwise risk domination. If a convention for exact completeness requires strict improvement for rules that are not risk-equivalent, that additional condition is separate from the epsilon bound.

The tolerance is measured on the same scale as the loss and risk. For example, multiplying every loss by a positive constant $a$ multiplies every risk excess and the corresponding tolerance by $a$. A numerical value of $\varepsilon$ is therefore meaningful only in relation to the chosen loss scale.

Worked Example: Checking an Epsilon-Replacement in a Finite Problem

Suppose a decision problem has three parameter values, $\theta_1,\theta_2,\theta_3$. A target rule $\delta$ has risk vector $(0.40,0.20,0.50)$, and a candidate rule $\delta'$ has risk vector $(0.43,0.17,0.54)$. Find the smallest tolerance for which $\delta'$ epsilon-dominates $\delta$.

Subtract the target risk from the candidate risk at each parameter: $$ \begin{aligned} R(\theta_1,\delta')-R(\theta_1,\delta)&=0.43-0.40=0.03,\\ R(\theta_2,\delta')-R(\theta_2,\delta)&=0.17-0.20=-0.03,\\ R(\theta_3,\delta')-R(\theta_3,\delta)&=0.54-0.50=0.04. \end{aligned} $$

The largest positive excess is $0.04$. Thus $\delta'$ epsilon-dominates $\delta$ for every $\varepsilon\geq0.04$, and $0.04$ is the smallest such tolerance. In particular, the risk decrease at $\theta_2$ does not offset the increase at $\theta_3$: the comparison is made separately at every parameter value.

Risk Approximation Gives a Replacement

One direct way to obtain an approximate replacement is to find a rule whose entire risk function is close to the target rule's risk function. Uniform closeness controls risk increases as well as decreases, so it is stronger than the one-sided requirement in epsilon-domination.

Theorem: Let $\delta\in\mathcal{D}$, and suppose $\delta'\in\mathcal{D}$ satisfies $$ \sup_{\theta\in\Theta} \left|R(\theta,\delta')-R(\theta,\delta)\right|\leq\varepsilon. $$ Then $\delta'$ epsilon-dominates $\delta$.

Proof. For each $\theta$, the absolute-value bound implies $$ R(\theta,\delta')-R(\theta,\delta) \leq \left|R(\theta,\delta')-R(\theta,\delta)\right| \leq\varepsilon. $$ Adding $R(\theta,\delta)$ to both sides gives the required risk inequality for every $\theta$. Therefore $\delta'$ epsilon-dominates $\delta$. $\square$

This theorem also gives a useful construction from a sequence. Suppose $\delta_m\in\mathcal{C}$ and $$ \sup_{\theta\in\Theta} \left|R(\theta,\delta_m)-R(\theta,\delta)\right|\longrightarrow 0. $$ For any prescribed $\varepsilon>0$, the definition of convergence supplies an index $m$ for which the displayed supremum is less than $\varepsilon$. The theorem then shows that this particular $\delta_m$ epsilon-dominates $\delta$. The point is not merely that the risks can be approximated in the limit: a finite-index rule provides the replacement for each positive tolerance.

Worked Example: Replacing a Rule by a Nearby Risk Function

Let the parameter be $\theta\in\{0,1\}$, let $X\sim\operatorname{Bernoulli}(\theta)$, and use squared-error loss $L(\theta,a)=(a-\theta)^2$. Consider constant-action rules that report $a$, regardless of $X$. The target rule reports $0.40$, while the candidate class contains the rule reporting $0.45$. Determine the smallest tolerance for which the candidate replaces the target.

Because each rule reports a constant, its risk is the squared error of that constant. At $\theta=0$, the risks are $$ R(0,\delta)= (0.40-0)^2=0.16, \qquad R(0,\delta')=(0.45-0)^2=0.2025. $$ The candidate's excess risk at $\theta=0$ is $0.2025-0.16=0.0425$.

At $\theta=1$, the risks are $$ R(1,\delta)=(0.40-1)^2=0.36, \qquad R(1,\delta')=(0.45-1)^2=0.3025. $$ Here the candidate reduces risk by $0.36-0.3025=0.0575$, so its risk excess is $-0.0575$. The largest positive excess across the two parameter values is $0.0425$. Thus the candidate epsilon-dominates the target for every $\varepsilon\geq0.0425$, and no smaller tolerance works.

Weighted Risk Bounds

Sometimes a risk approximation is expressed in a weighted metric rather than the ordinary uniform metric. Suppose $w:\Theta\to(0,\infty)$ is a weight function and define $$ d_w(R_1,R_2)=\sup_{\theta\in\Theta}w(\theta) \left|R_1(\theta)-R_2(\theta)\right|. $$ To turn a bound in this metric into a uniform risk tolerance, the weights must be bounded away from zero. A small weighted distance alone may allow a large unweighted difference where the weight is very small.

Theorem: Suppose $w(\theta)\geq c>0$ for every $\theta\in\Theta$. If $$ d_w\bigl(R(\cdot,\delta'),R(\cdot,\delta)\bigr)\leq\eta, $$ then $\delta'$ epsilon-dominates $\delta$ with $\varepsilon=\eta/c$.

Proof. For each $\theta$, the metric bound gives $$ w(\theta)\left|R(\theta,\delta')-R(\theta,\delta)\right|\leq\eta. $$ Since $w(\theta)\geq c>0$, division by $w(\theta)$ yields $$ \left|R(\theta,\delta')-R(\theta,\delta)\right| \leq\frac{\eta}{w(\theta)} \leq\frac{\eta}{c}. $$ In particular, $R(\theta,\delta')-R(\theta,\delta)\leq\eta/c$ for every $\theta$, which is the epsilon-domination condition with $\varepsilon=\eta/c$. $\square$

Worked Example: Converting a Weighted Bound

Let $\Theta=\{\theta_1,\theta_2,\theta_3\}$, with weights $w=(2,1,0.5)$. A target rule has risk vector $(0.30,0.50,0.20)$, and a candidate has risk vector $(0.31,0.49,0.24)$. Calculate the weighted distance and the resulting uniform tolerance.

The absolute risk differences are $0.01,0.01,0.04$. After multiplying by the weights, the three weighted differences are $$ 2(0.01)=0.02,\qquad 1(0.01)=0.01,\qquad 0.5(0.04)=0.02. $$ Hence the weighted distance is $d_w=0.02$. The smallest weight is $c=0.5$, so the theorem guarantees epsilon-domination with $$ \varepsilon=\frac{0.02}{0.5}=0.04. $$ This bound is attained: the candidate's risk at $\theta_3$ exceeds the target's by $0.24-0.20=0.04$. Thus $0.04$ is also the smallest actual tolerance in this example.

Combining Approximate Replacements

Approximate replacements can be applied in sequence, but their tolerances accumulate. The following elementary result is useful when a target rule is first replaced by an intermediate rule and that intermediate rule is then replaced by a member of a desired class.

Theorem: If $\delta_1$ epsilon-dominates $\delta_0$, and $\delta_2$ eta-dominates $\delta_1$, then $\delta_2$ $(\varepsilon+\eta)$-dominates $\delta_0$.

Proof. For every $\theta$, the two hypotheses give $$ R(\theta,\delta_2)\leq R(\theta,\delta_1)+\eta \leq R(\theta,\delta_0)+\varepsilon+\eta. $$ This is precisely the definition of $(\varepsilon+\eta)$-domination of $\delta_0$ by $\delta_2$. $\square$

It follows that if $\mathcal{C}$ is $\varepsilon$-complete in $\mathcal{D}$, every target rule has a replacement in $\mathcal{C}$ whose risk is bounded above by the target risk plus $\varepsilon$ at every parameter value. If a construction instead uses several stages with tolerances $\varepsilon_1,\ldots,\varepsilon_k$, the final bound is their sum. A small error at each stage need not remain small after many stages.

Common Pitfall: Averaging Away a Risk Increase

A frequent mistake is to average risk differences across parameter values and declare a replacement acceptable because the average is small or negative. Epsilon-domination is a pointwise comparison, not an average-risk comparison. In the finite example above, the candidate improves risk by $0.03$ at one parameter value but increases it by $0.04$ at another. The improvement does not cancel the increase: the smallest valid tolerance remains $0.04$.

A second mistake is to use a weighted-distance bound without checking whether the weights are bounded below. If $w(\theta)$ can approach zero, a small value of $w(\theta)|R_1(\theta)-R_2(\theta)|$ does not necessarily imply a small risk difference at that parameter value. The conversion theorem depends on the explicit condition $w(\theta)\geq c>0$.

Key takeaway: To establish epsilon-completeness, produce for each target rule a member of the proposed class and verify, uniformly in $\theta$, that its risk is at most the target risk plus $\varepsilon$. Uniform risk approximation is one sufficient construction; weighted approximation requires a positive lower bound on the weights.

Check Your Understanding

For each question, focus on the risk bound at every parameter value.

A candidate rule has risk excesses $-0.02, 0.01,$ and $0.06$ at three parameter values. What is the smallest tolerance for which it epsilon-dominates the target?
Why does uniform absolute risk distance at most $\varepsilon$ imply epsilon-domination, even though the definition only limits risk increases?
A weighted risk metric has weights that are all at least $0.4$, and the weighted distance between two risks is at most $0.03$. What uniform tolerance is guaranteed?
If one replacement has tolerance $0.02$ and a second replacement has tolerance $0.05$ relative to the first, what tolerance is guaranteed for the final rule relative to the original target?
Explain why a small average risk excess over parameter values does not by itself establish epsilon-domination.