Modulus Bounds for Parameter Discretization

Why Parameter Discretization Needs a Quantitative Bound

A finite net replaces a potentially large parameter space with finitely many representative points. But solving the decision problem at those points only controls the full problem if risk cannot change too much between a parameter and its representative. The key is a bound that holds uniformly over the decision rules being considered. Such a bound converts the net’s radius into an explicit allowance for discretization error.

Let $(\Theta,d)$ be a nonempty parameter space with metric $d$, let $\mathcal D$ be a class of decision rules, and let $R(\theta,\delta)$ be the risk of rule $\delta\in\mathcal D$ at parameter $\theta$. Assume the risks in the discussion below are finite. For a nonempty subset $A\subseteq\Theta$, define its minimax value by

M(A)=\inf_{\delta\in\mathcal D}\sup_{\theta\in A}R(\theta,\delta).

The infimum need not be attained. A finite set $\Gamma\subseteq\Theta$ is an $\eta$-net for $\Theta$ if every $\theta\in\Theta$ is within distance $\eta$ of at least one $\gamma\in\Gamma$. The useful case here is a net whose points belong to $\Theta$, so that $\Gamma\subseteq\Theta$.

Definition: The uniform modulus of continuity of risk over $\mathcal D$ is $$ \omega(t)=\sup_{\delta\in\mathcal D}\ \sup_{\substack{\theta,\theta'\in\Theta\\d(\theta,\theta')\leq t}} \left|R(\theta,\delta)-R(\theta',\delta)\right|,\qquad t\geq 0. $$ It is a uniform modulus when $\omega(t)$ is finite for the radii used and $\omega(t)\to 0$ as $t\downarrow 0$. A Lipschitz risk bound with constant $L$ means $\omega(t)\leq Lt$.

The Discretization Bound

The central estimate compares, rule by rule, the worst risk on the full space with the largest risk at a net point. Its proof uses only the covering property and the definition of the modulus.

Theorem: Suppose $\Gamma\subseteq\Theta$ is a finite $\eta$-net and $\omega(\eta)<\infty$. For every $\delta\in\mathcal D$, $$ \max_{\gamma\in\Gamma}R(\gamma,\delta) \leq \sup_{\theta\in\Theta}R(\theta,\delta) \leq \max_{\gamma\in\Gamma}R(\gamma,\delta)+\omega(\eta). $$ Consequently, $$ M(\Gamma)\leq M(\Theta)\leq M(\Gamma)+\omega(\eta). $$

Proof. Since $\Gamma\subseteq\Theta$, the supremum over $\Theta$ is at least the maximum over $\Gamma$. For the other direction, fix $\delta\in\mathcal D$ and any $\theta\in\Theta$. The net property gives a $\gamma\in\Gamma$ with $d(\theta,\gamma)\leq\eta$. Thus $R(\theta,\delta)\leq R(\gamma,\delta)+\omega(\eta)\leq\max_{\gamma'\in\Gamma}R(\gamma',\delta)+\omega(\eta)$. Taking the supremum over $\theta$ proves the rule-by-rule upper bound.

For the minimax values, the lower bound follows because for every $\delta$, $\sup_{\Theta}R(\theta,\delta)\geq\max_{\Gamma}R(\gamma,\delta)$; taking infima preserves this inequality. For the upper bound, the rule-by-rule estimate gives $M(\Theta)\leq\inf_{\delta\in\mathcal D}\{\max_{\gamma\in\Gamma}R(\gamma,\delta)+\omega(\eta)\}=M(\Gamma)+\omega(\eta)$. No minimizer is needed. $\square$

This bound also transfers an approximately optimal finite-net rule to the full problem. If a rule $\delta_\alpha$ satisfies $\max_{\gamma\in\Gamma}R(\gamma,\delta_\alpha)\leq M(\Gamma)+\alpha$, then

\sup_{\theta\in\Theta}R(\theta,\delta_\alpha) \leq M(\Theta)+\alpha+\omega(\eta).

Indeed, apply the theorem’s rule-by-rule upper bound, then use $M(\Gamma)\leq M(\Theta)$. Thus, to obtain a global $\varepsilon$-minimax rule, it suffices to allocate the error so that $\alpha+\omega(\eta)\leq\varepsilon$. In the Lipschitz case, a mesh radius $\eta\leq(\varepsilon-\alpha)/L$ suffices when $L>0$ and $\alpha\leq\varepsilon$.

Worked Example: Bernoulli Mean and Squared-Error Risk

Suppose $X\sim\operatorname{Bernoulli}(\theta)$, where $\theta\in[0,1]$, and estimate $\theta$ by a rule $\delta$ with $\delta(0)=\delta_0\in[0,1]$ and $\delta(1)=\delta_1\in[0,1]$. Under squared-error loss, the risk is

R(\theta,\delta)=(1-\theta)(\delta_0-\theta)^2+\theta(\delta_1-\theta)^2.

To bound its change, write $q_\theta(x)=P_\theta(X=x)$ and $\ell_\theta(a)=(a-\theta)^2$. For $\theta,\theta'\in[0,1]$, split the risk difference into a change in the loss and a change in the distribution:

R(\theta,\delta)-R(\theta',\delta) =\sum_{x=0}^1 q_\theta(x)\{\ell_\theta(\delta_x)-\ell_{\theta'}(\delta_x)\} +\sum_{x=0}^1\{q_\theta(x)-q_{\theta'}(x)\}\ell_{\theta'}(\delta_x).

For $a,\theta,\theta'\in[0,1]$, $\left|(a-\theta)^2-(a-\theta')^2\right| =|\theta-\theta'||2a-\theta-\theta'|\leq2|\theta-\theta'|$. Therefore the absolute value of the first sum is at most $2|\theta-\theta'|$. Each squared loss in the second sum lies in $[0,1]$; since $q_\theta(1)-q_{\theta'}(1)=\theta-\theta'$ and $q_\theta(0)-q_{\theta'}(0)=-(\theta-\theta')$, that sum has absolute value at most $|\theta-\theta'|$. Hence \[ |R(\theta,\delta)-R(\theta',\delta)|\leq3|\theta-\theta'| \] uniformly over all the stated rules.

For a numerical guarantee, take a net of radius $\eta=0.02$. Then $\omega(\eta)\leq3(0.02)=0.06$. If a rule is within $\alpha=0.04$ of the finite-net minimax value, its maximum risk on $[0,1]$ is at most $0.04+0.06=0.10$ above the full minimax value. The displayed risk formula is important: squared-error estimation of $\theta$ requires subtracting $\theta$ from each possible action, including the action after observing $X=1$.

General Moduli Can Be More Informative

A Lipschitz condition is convenient but not essential. If the risk is uniformly Hölder continuous, for example, then $\omega(t)\leq Ct^\beta$ for constants $C>0$ and $0<\beta\leq1$. For an error allowance $\rho>0$, choosing $\eta\leq(\rho/C)^{1/\beta}$ guarantees $\omega(\eta)\leq\rho$. When $\beta<1$, the bound may decrease more slowly than a linear one, so the required mesh can be finer.

Worked Example: A Square-Root Modulus

Consider a decision problem with no informative observation, parameter space $\Theta=[0,1]$, action $a\in[0,1]$, and loss $L(\theta,a)=|a-\theta|^{1/2}$. Its risk is $R(\theta,a)=|a-\theta|^{1/2}$. For nonnegative $u,v$, $\sqrt{u+v}\leq\sqrt u+\sqrt v$, since squaring the right side gives $u+v+2\sqrt{uv}\geq u+v$. It follows that $|\sqrt u-\sqrt v|\leq\sqrt{|u-v|}$.

The reverse triangle inequality gives $\big||a-\theta|-|a-\theta'|\big|\leq|\theta-\theta'|$. Apply the square-root inequality with $u=|a-\theta|$ and $v=|a-\theta'|$ to obtain \[ |R(\theta,a)-R(\theta',a)|\leq|\theta-\theta'|^{1/2}. \] This holds uniformly over all actions, so $\omega(t)\leq\sqrt t$. A net of radius $\eta=0.0025$ has discretization error at most $\sqrt{0.0025}=0.05$. Therefore, if the finite-net rule is within $0.05$ of the finite-net minimax value, it is within $0.10$ of the full minimax value.

Deriving a Lipschitz Bound in a Normal Model

In some models the parameter changes both the loss and the distribution of the data. A useful proof separates these two effects, as in the Bernoulli example. The next calculation shows that a uniform bound can still be obtained when the observation has a continuous distribution.

Worked Example: Normal Location With Bounded Actions

Let $X\sim N(\theta,1)$ for $\theta\in[0,1]$, and consider measurable rules $\delta:\mathbb R\to[0,1]$ under squared-error loss. Write $\phi(x-\theta)$ for the normal density. The risk is \[ R(\theta,\delta)=\int_{\mathbb R}(\delta(x)-\theta)^2\phi(x-\theta)\,dx. \] For $h=|\theta-\theta'|$, split the difference as

\begin{aligned} R(\theta,\delta)-R(\theta',\delta) ={}&\int_{\mathbb R}\big[(\delta(x)-\theta)^2-(\delta(x)-\theta')^2\big]\phi(x-\theta)\,dx\\ &+\int_{\mathbb R}(\delta(x)-\theta')^2\big[\phi(x-\theta)-\phi(x-\theta')\big]\,dx. \end{aligned}

Because all three of $\delta(x),\theta,\theta'$ lie in $[0,1]$, the absolute difference of squared losses in the first integral is at most $2h$. Since the density integrates to one, the absolute value of that integral is at most $2h$. Also $0\leq(\delta(x)-\theta')^2\leq1$, so the second integral in absolute value is at most $\int_{\mathbb R}|\phi(x-\theta)-\phi(x-\theta')|\,dx$.

The fundamental theorem of calculus along the shift in the density, followed by the triangle inequality and integration, gives \[ \int_{\mathbb R}|\phi(x-\theta)-\phi(x-\theta')|\,dx \leq h\int_{\mathbb R}|\phi'(u)|\,du. \] The interchange is justified by integrating the nonnegative absolute derivative over the shift interval and over $x$ (Tonelli’s theorem); the resulting integral is finite. Since $\phi'(u)=-u\phi(u)$, the last integral is $E|Z|=\sqrt{2/\pi}$ for $Z\sim N(0,1)$. Thus \[ |R(\theta,\delta)-R(\theta',\delta)| \leq \left(2+\sqrt{2/\pi}\right)|\theta-\theta'|. \] For $\eta=0.01$, the discretization allowance is at most $0.01(2+\sqrt{2/\pi})$, approximately $0.02798$. A rule within $0.02$ of the net minimax value is therefore within approximately $0.04798$, and hence within $0.05$, of the full minimax value.

Choosing the Mesh and Avoiding a Common Pitfall

The practical calculation is to reserve part of the desired tolerance for solving the finite problem and the rest for discretization. If $\varepsilon$ is the desired global tolerance, choose $\alpha\geq0$ for the finite-net optimization error, then choose $\eta$ so that $\omega(\eta)\leq\varepsilon-\alpha$. For a Hölder bound $Ct^\beta$, for instance, it is enough to take $\eta\leq((\varepsilon-\alpha)/C)^{1/\beta}$, provided $\alpha<\varepsilon$.

Establish uniform regularity.
Bound $|R(\theta,\delta)-R(\theta',\delta)|$ for every rule in the class, not just for a selected rule.

Set the discretization allowance.
Choose $\rho$ so that the finite optimization error $\alpha$ plus $\rho$ is no greater than the target $\varepsilon$.

Choose the net radius.
Select $\eta$ with $\omega(\eta)\leq\rho$; for a Lipschitz bound $L\eta$, take $\eta\leq\rho/L$ when $L>0$.

Transfer the finite-net guarantee.
Apply the theorem to conclude that the selected rule is globally within $\alpha+\omega(\eta)$ of the full minimax value.

A common mistake is to prove that $R(\theta,\delta)$ is continuous in $\theta$ for each fixed $\delta$, then assume one mesh works for every rule. Pointwise continuity does not provide a common radius across an unrestricted class of rules. The correction is to prove a uniform modulus, as in the examples where the bound holds for every admissible action or rule. A second error is to use a risk expression that does not match the stated loss: in squared-error estimation, the loss at every possible observation is $(\delta(x)-\theta)^2$. A discretization guarantee derived from a different expression does not apply to the stated problem.

Key takeaway: A finite parameter net controls the full maximum risk when the risk has a modulus of continuity uniform over the decision rules. The minimax-value error is at most $\omega(\eta)$, and an $\alpha$-accurate finite-net solution is globally $\alpha+\omega(\eta)$-minimax.

Check Your Understanding

Use the uniform-modulus bound to answer the following.

If $\omega(t)\leq 4t$ and the finite-net optimization error is $0.02$, what net radius guarantees a global error no larger than $0.10$?
Why does the inequality $M(\Gamma)\leq M(\Theta)$ require $\Gamma\subseteq\Theta$?
For a bound $\omega(t)\leq 3t^{1/2}$, what radius is sufficient to make the discretization allowance at most $0.12$?
Explain why continuity of risk for each fixed rule is not, by itself, enough to choose one mesh that works uniformly over a class of rules.
In the Bernoulli squared-error example, identify the part of the risk-difference argument that accounts for the changing distribution of $X$.