Failure Modes in Truncation and Discretization

Why Approximation Can Change a Minimax Problem

Approximation is useful in minimax theory because an infinite parameter space or an unbounded loss can be difficult to analyze directly. But several operations that look like “truncation” are mathematically different. Restricting the parameters removes cases from the maximization; truncating the loss caps the penalty while keeping those cases; discretizing the parameters replaces a continuum by selected points. Each operation can change the problem unless its error is controlled.

The most reliable diagnostic is to write down the risk after the proposed change and ask what is being held fixed. In particular, a good approximation at every fixed parameter need not be good uniformly over the parameter space, and a good solution on every finite subproblem need not yield a good rule for the full problem.

Definition: In a statistical decision problem, let \(P_\theta\) be the distribution of the observation \(X\) at parameter \(\theta\in\Theta\), let \(\delta\) be a measurable decision rule, and let \(L(\theta,a)\geq 0\) be a measurable loss. The risk is \(R(\theta,\delta)=E_\theta[L(\theta,\delta(X))]\). The minimax risk is \(V(\Theta,L)=\inf_\delta\sup_{\theta\in\Theta}R(\theta,\delta)\), where the infimum is over the stated class of rules. A parameter restriction replaces \(\Theta\) by a subset. Loss truncation at level \(c>0\) replaces \(L\) by \(L_c=\min(L,c)\) without changing \(\Theta\).

Parameter Restriction Is Not Loss Truncation

A parameter restriction changes which risks enter the supremum. Loss truncation changes the value assigned to an outcome, potentially at every parameter. Even when both operations make a problem bounded or simpler, they answer different decision questions.

Worked Example: Restricting the Parameter Versus Capping the Loss

Suppose there is no informative observation, so a rule chooses a fixed real action \(a\). Take \(\Theta=\mathbb{R}\) and squared-error loss \(L(\theta,a)=(a-\theta)^2\).

Full parameter space and original loss. For any fixed \(a\), parameters can be arbitrarily far from \(a\), so \(\sup_{\theta\in\mathbb{R}}(a-\theta)^2=\infty\). Thus the minimax risk is infinite.

Restrict the parameter space to \(\{0\}\). Choosing \(a=0\) gives risk \((0-0)^2=0\), so the restricted minimax risk is zero.

Keep \(\mathbb{R}\), but truncate the loss at \(1\). For every \(a\), choose any \(\theta\) with \(|a-\theta|\geq 1\). Then \(\min((a-\theta)^2,1)=1\), while truncated loss never exceeds \(1\). Consequently, \(\sup_{\theta\in\mathbb{R}}\min((a-\theta)^2,1)=1\) for every \(a\), and the truncated-loss minimax risk is \(1\).

The three minimax values are therefore infinite, zero, and one, respectively. The example makes the distinction explicit: removing parameters can remove hard cases, while capping the loss leaves those parameters in the supremum.

Pointwise Risk Control Does Not Control the Tail

A sequence of rules may have risks that converge at every fixed parameter while retaining a large worst-case risk. The problem is that the parameter where the risk is large can move as the rule changes. This is precisely why pointwise convergence alone cannot justify passing to a supremum over an unbounded or noncompact parameter space.

Worked Example: A Moving Risk Spike Under Squared Error

Let \(\Theta=\{1,2,\ldots\}\), let the observation be \(X=\theta\) with probability one, and use squared-error loss for estimating \(\theta\). The rule \(\delta_n\) reports \(x+1\) when \(x=n\), and reports \(x\) otherwise.

At a fixed parameter \(\theta\), the observation equals \(\theta\). If \(\theta=n\), then \(\delta_n(X)=n+1\), so \(R(\theta,\delta_n)=1\). If \(\theta\ne n\), then \(\delta_n(X)=\theta\), so \(R(\theta,\delta_n)=0\). Equivalently,

R(\theta,\delta_n)=\mathbf{1}\{\theta=n\}.

For each fixed \(\theta\), \(R(\theta,\delta_n)\) is eventually zero as \(n\) increases. Yet for every \(n\), \(\sup_{\theta\in\Theta}R(\theta,\delta_n)=1\), because the supremum includes \(\theta=n\). Thus pointwise convergence of these risks to zero does not imply convergence of their suprema to zero.

The same calculation diagnoses a finite-set approximation. On \(\Theta_m=\{1,\ldots,m\}\), the rule \(\delta_n\) has zero risk whenever \(n>m\). That says nothing about its risk at the omitted parameter \(n\). A finite calculation is informative about the full problem only when omitted parameters are controlled as well.

Theorem: Suppose \(\Theta_m\) are increasing subsets with union \(\Theta\), and all minimax values use the same class of decision rules and the same loss. Write \(V_m=\inf_\delta\sup_{\theta\in\Theta_m}R(\theta,\delta)\) and \(V=\inf_\delta\sup_{\theta\in\Theta}R(\theta,\delta)\). Then \(V_m\) is nondecreasing and \(V_m\leq V\) for every \(m\). Equality of \(\lim_m V_m\) and \(V\) does not follow from these facts alone.

For every fixed rule, enlarging \(\Theta_m\) cannot decrease its maximum risk. Taking the infimum over the same rule class preserves this ordering, so \(V_m\leq V_{m+1}\). Also \(\sup_{\theta\in\Theta_m}R(\theta,\delta)\leq\sup_{\theta\in\Theta}R(\theta,\delta)\) for every \(\delta\); taking infima gives \(V_m\leq V\). The last sentence is essential: the rule that performs well on \(\Theta_m\) may depend on \(m\) and may perform poorly outside \(\Theta_m\). \(\square\)

Worked Example: Finite Minimax Values Can Miss the Global Value

Let there be no informative observation, \(\Theta=\{1,2,\ldots\}\), and let the action space also be the positive integers. Define the loss by \(L(\theta,k)=\mathbf{1}\{\theta\geq k\}\). A rule is simply a choice of action \(k\).

On \(\Theta_m=\{1,\ldots,m\}\), choose \(k=m+1\). For every \(\theta\in\Theta_m\), \(\theta<m+1\), so \(L(\theta,m+1)=0\). Hence \(V_m=0\), since risks are nonnegative.

On the full space, every finite action \(k\) has risk \(1\) at \(\theta=k\). Therefore \(\sup_{\theta\in\Theta}L(\theta,k)=1\) for every action, and \(V=1\). In this example \(\lim_m V_m=0<1=V\). The finite-problem actions escape to larger and larger values; no one of them gives low worst-case risk on the full space.

What Makes Truncation and Discretization Safe?

A useful safeguard for loss truncation is a uniform bound on the part of the loss that was removed. For nonnegative \(L\), the difference between the original and truncated losses is \((L-c)_+=\max(L-c,0)\). A bound on its expectation, uniform over both parameters and rules, controls the corresponding risks and minimax values.

Theorem: Let \(L_c=\min(L,c)\). Suppose that, for some finite \(\varepsilon\geq0\), \(\sup_{\theta\in\Theta,\,\delta}E_\theta[(L(\theta,\delta(X))-c)_+]\leq\varepsilon\), where the supremum is over the same rule class used for both losses. Then the minimax values \(V\) for \(L\) and \(V_c\) for \(L_c\) satisfy \(V_c\leq V\leq V_c+\varepsilon\).

For each rule and parameter, \(0\leq L-L_c=(L-c)_+\). Taking expectations gives \(0\leq R(\theta,\delta)-R_c(\theta,\delta)\leq\varepsilon\). Taking the supremum over \(\theta\) preserves these inequalities:

\sup_\theta R_c(\theta,\delta) \leq \sup_\theta R(\theta,\delta) \leq \sup_\theta R_c(\theta,\delta)+\varepsilon.

Taking infima over the same rules gives \(V_c\leq V\leq V_c+\varepsilon\). The uniformity over rules matters: a tail bound for only one selected rule cannot, by itself, bound the minimax value, whose infimum ranges over the entire rule class. \(\square\)

For discretization, the corresponding safeguard is a common modulus of continuity in the parameter. If risks of all candidate rules vary slowly between nearby parameters, a finite net can approximate the supremum. If the modulus depends on the rule or deteriorates without bound, a net may miss a narrow region of high risk.

Theorem: Let \(\Theta\) be a compact metric space and \(D_\eta\subset\Theta\) a finite \(\eta\)-net: every \(\theta\in\Theta\) is within distance \(\eta\) of some \(d\in D_\eta\). Suppose a nondecreasing function \(\omega\) satisfies \(\omega(\eta)\to0\) as \(\eta\to0\) and \(|R(\theta,\delta)-R(d,\delta)|\leq\omega(\eta)\) whenever the distance between \(\theta\) and \(d\) is at most \(\eta\), uniformly over all rules \(\delta\). If \(V_{D_\eta}=\inf_\delta\max_{d\in D_\eta}R(d,\delta)\), then \(V_{D_\eta}\leq V\leq V_{D_\eta}+\omega(\eta)\).

For each rule \(\delta\), the net property gives, for every \(\theta\), a point \(d\in D_\eta\) with \(R(\theta,\delta)\leq R(d,\delta)+\omega(\eta)\). Thus \(\max_{d\in D_\eta}R(d,\delta)\leq\sup_{\theta\in\Theta}R(\theta,\delta)\leq\max_{d\in D_\eta}R(d,\delta)+\omega(\eta)\). Taking infima over \(\delta\) yields the claimed bounds. Uniformity over the rule class allows the same error bound to survive the infimum. \(\square\)

Worked Example: A Grid Misses a Discontinuous Risk

Consider a no-observation problem with \(\Theta=[0,1]\), actions \(a\in[0,1]\), and measurable loss \(L(\theta,a)=\mathbf{1}\{\theta=a\}\). The full-space minimax risk is \(1\): for every action \(a\), the parameter value \(\theta=a\) gives loss \(1\), and the loss is never larger than \(1\).

Now use the grid \(D=\{0,\tfrac14,\tfrac12,\tfrac34,1\}\). Choose \(a=\tfrac18\), which is not in \(D\). At each grid point \(d\), \(d\ne a\), so \(L(d,a)=0\); the grid minimax risk is therefore zero. The grid misses the parameter \(\theta=\tfrac18\), where the risk is \(1\). Here the loss is discontinuous in \(\theta\), so no modulus tending to zero can provide the uniform control required by the theorem.

Common Mistakes and a Practical Check

Treating restriction as truncation. Restriction drops parameters from the supremum; truncation caps losses at the parameters that remain. Check which object changed.
Inferring uniform control from pointwise convergence. A moving risk spike can vanish at every fixed parameter while the maximum risk stays large. Check a supremum or a uniform tail bound.
Assuming finite minimax values converge to the global value. The optimizing rules can vary with the finite set and escape the class of rules that work globally. Verify a condition that controls risks outside each finite set.
Discretizing without a common modulus. A net only controls nearby parameter values when the risks of all relevant rules change by a controlled amount. Verify the modulus uniformly over those rules.

Before accepting an approximation, identify its exact operation, state the quantity being approximated, and establish an error bound that survives both the supremum over parameters and the infimum over rules. Without that control, agreement on a sequence of finite or truncated problems is evidence about those problems, not a proof about the original minimax problem.

Check Your Understanding

Use the definitions and safeguards in this tutorial to answer the following questions.

In the squared-error example, why does restricting the parameter to \(\{0\}\) differ from truncating the loss at \(1\) while retaining all real parameters?
How can risks converge to zero at every fixed parameter while their suprema remain equal to one?
For an increasing sequence of parameter sets, why must the finite minimax values be nondecreasing and bounded above by the full minimax value?
What uniform tail condition guarantees that truncating a nonnegative loss changes the minimax value by at most a specified amount?
Why does a parameter net provide a minimax approximation only when risk variation is controlled uniformly over the decision rules?