Approximate Minimax Procedures · Tutorial 281 of 982

Finite Nets for Compact Parameter Spaces

Use finite nets and equicontinuity to turn finite-parameter risk guarantees into approximate guarantees over a compact parameter space.

Advanced 11 min read

What You'll Learn

Define finite nets in compact metric parameter spaces
State and prove a finite-net risk-transfer result
Use uniform equicontinuity to control worst-case risk
Relate finite-net and continuum minimax values
Calculate net bounds in squared-error and Bernoulli examples
Recognize why pointwise continuity alone is insufficient

Why Approximate a Compact Parameter Space?

A worst-case risk is a supremum over all parameter values. Even when the parameter space is compact, that supremum concerns a continuum and may be difficult to evaluate directly. A finite net replaces the continuum by finitely many representative parameter values. The key question is when a risk bound at those representatives also controls risk nearby.

The needed link is equicontinuity: nearby parameter values must have similar risks, uniformly over the candidate decision rules under consideration. Compactness supplies a finite set of representatives; equicontinuity makes the resulting approximation valid for risk, not just for the parameter space itself.

Finite Nets and Equicontinuous Risk Functions

Definition: Let $(\Theta,d)$ be a metric space. A finite set $N\subseteq\Theta$ is an $r$-net for $\Theta$ if for every $\theta\in\Theta$, there is a $\nu\in N$ such that $d(\theta,\nu)<r$. A family of real-valued functions $\mathcal{R}$ on $\Theta$ is equicontinuous if, for every $\varepsilon>0$, there is an $\eta>0$ such that $d(\theta,\phi)<\eta$ implies $|R(\theta)-R(\phi)|<\varepsilon$ for every $R\in\mathcal{R}$.

For a decision rule $\delta$, its risk at parameter $\theta$ is $R(\theta,\delta)=E_\theta[L(\theta,\delta(X))]$, when this expectation is well-defined. In what follows, risks are real and finite. A class of rules $\mathcal{D}_0$ has equicontinuous risks if the family $\{R(\cdot,\delta):\delta\in\mathcal{D}_0\}$ is equicontinuous. The uniformity over $\delta$ is important: it lets one choose a single net that works for the whole class.

Every compact metric space has a finite $r$-net for each $r>0$. Indeed, the open balls $B(\theta,r)=\{\phi:d(\phi,\theta)<r\}$, with centers $\theta\in\Theta$, cover $\Theta$. Compactness gives a finite subcover $B(\nu_1,r),\ldots,B(\nu_m,r)$; their centers form the required net.

Transferring a Risk Bound from the Net

Theorem: Suppose $\Theta$ is a compact metric space and $\mathcal{D}_0$ is a class of decision rules whose risk functions are equicontinuous on $\Theta$. For every $\varepsilon>0$, there is a finite net $N\subseteq\Theta$ such that, for every $\delta\in\mathcal{D}_0$, $$ \sup_{\theta\in\Theta}R(\theta,\delta) \leq \max_{\nu\in N}R(\nu,\delta)+\varepsilon. $$

Proof. By equicontinuity, for the given $\varepsilon>0$ there is an $\eta>0$ such that $d(\theta,\phi)<\eta$ implies $|R(\theta,\delta)-R(\phi,\delta)|<\varepsilon$ for every $\delta\in\mathcal{D}_0$. Compactness gives a finite $\eta$-net $N$. Fix any $\delta\in\mathcal{D}_0$ and any $\theta\in\Theta$. Choose $\nu\in N$ with $d(\theta,\nu)<\eta$. Then $$ R(\theta,\delta) < R(\nu,\delta)+\varepsilon \leq \max_{\phi\in N}R(\phi,\delta)+\varepsilon. $$ This holds for every $\theta$. Taking the supremum over $\theta$ gives the stated weak inequality. $\square$

The net is chosen using the common equicontinuity condition, not separately for each rule. The theorem does not say that the finite maximum equals the continuum supremum. It says the difference is at most a chosen tolerance, uniformly across the class.

Worked Example: A Squared-Error Decision Problem on an Interval

Let $\Theta=[0,1]$, let there be no informative observation, and let the action be a constant $a\in[0,1]$. Use squared-error loss $L(\theta,a)=(a-\theta)^2$. The risk is $R(\theta,a)=(a-\theta)^2$.

Take $N=\{0,0.25,0.5,0.75,1\}$. Every point in $[0,1]$ is within $0.125$ of a point in $N$. For the action $a=0.4$, the risks at the net points are $$ 0.16,\quad 0.0225,\quad 0.01,\quad 0.1225,\quad 0.36. $$ Hence the maximum net risk is $0.36$. The theorem’s transfer bound is $0.36+2(0.125)=0.61$. In this particular example, direct calculation gives the exact continuum maximum: the largest squared distance from $0.4$ to a point in $[0,1]$ is $(1-0.4)^2=0.36$. The net bound is valid but conservative.

Finite-Net Minimax Values

The transfer result also explains how a finite-parameter optimization can produce an approximate worst-case guarantee. Fix a finite net $N$, and define the worst risks and minimax values over a class $\mathcal{D}_0$ by $$ M(\delta)=\sup_{\theta\in\Theta}R(\theta,\delta), \qquad M_N(\delta)=\max_{\nu\in N}R(\nu,\delta), $$ $$ V=\inf_{\delta\in\mathcal{D}_0}M(\delta), \qquad V_N=\inf_{\delta\in\mathcal{D}_0}M_N(\delta). $$

The finite-net value cannot exceed the continuum value: $M_N(\delta)\leq M(\delta)$ for every rule, and therefore $V_N\leq V$. If the risks are equicontinuous, the reverse comparison holds up to a tolerance once the net is fine enough.

Corollary: Suppose $V$ and $V_N$ are finite and the hypotheses of the theorem hold. For any $\varepsilon>0$, choose a finite net so that the transfer error is less than $\varepsilon/2$. If a rule $\delta\in\mathcal{D}_0$ satisfies $M_N(\delta)\leq V_N+\varepsilon/2$, then $M(\delta)\leq V+\varepsilon$.

To verify the claim, apply the theorem to obtain $$ M(\delta) \leq M_N(\delta)+\frac{\varepsilon}{2} \leq V_N+\varepsilon \leq V+\varepsilon. $$ If the finite-net infimum is not attained, a rule within $\varepsilon/2$ of it exists by the definition of infimum, provided $V_N$ is finite and the class is nonempty. Thus attainment is not needed for the approximate guarantee.

Worked Example: A Bernoulli Mean Risk Bound

Let $X_1,\ldots,X_n$ be independent Bernoulli observations with success probability $\theta\in[0,1]$, and estimate $\theta$ by $\hat{\theta}=\bar X$ under squared-error loss. Since $E_\theta[\bar X]=\theta$ and $\operatorname{Var}_\theta(\bar X)=\theta(1-\theta)/n$, its risk is $$ R(\theta,\bar X)=E_\theta[(\bar X-\theta)^2] =\frac{\theta(1-\theta)}{n}. $$

For $\theta,\phi\in[0,1]$, $$ |R(\theta,\bar X)-R(\phi,\bar X)| = \frac{|\theta-\phi|\,|1-\theta-\phi|}{n} \leq \frac{|\theta-\phi|}{n}, $$ because $|1-\theta-\phi|\leq1$. Take the grid $N=\{0,0.2,0.4,0.6,0.8,1\}$. Every point of $[0,1]$ is within $0.1$ of a grid point. The largest risk on the grid occurs at $0.4$ or $0.6$, and equals $0.4(0.6)/n=0.24/n$. Therefore $$ \sup_{\theta\in[0,1]}R(\theta,\bar X) \leq \frac{0.24}{n}+\frac{0.1}{n} =\frac{0.34}{n}. $$ Directly, $\theta(1-\theta)\leq1/4$, with equality at $\theta=1/2$, so the exact supremum is $1/(4n)=0.25/n$. The net argument gives a correct, though looser, bound.

Why Uniformity Matters

Continuity of each risk function separately is not enough to choose one finite net that controls an entire class of rules. Compactness makes each individual continuous function uniformly continuous, but the required net may depend on the function. A sequence of risks can develop increasingly narrow peaks between fixed net points.

Worked Example: Continuous Risks That a Fixed Net Misses

On $[0,1]$, fix $N=\{0,0.5,1\}$ and consider the continuous functions $$ R_k(\theta)=\exp\{-k^2(\theta-0.25)^2\}, \qquad k=1,2,\ldots. $$ At the net points, the largest value is at $0.5$, so $$ \max_{\nu\in N}R_k(\nu)=\exp(-k^2/16). $$ For $k=10$, this is $\exp(-6.25)$, approximately $0.00193$. But $R_k(0.25)=1$, and no value exceeds $1$, so $\sup_{\theta\in[0,1]}R_k(\theta)=1$. The net maximum becomes arbitrarily small as $k$ grows while the continuum maximum remains $1$. These functions are individually continuous, but the family is not equicontinuous. Thus a small risk on a fixed net does not, by itself, imply a small worst-case risk.

Common Mistake

Wrong reasoning: “The parameter space is compact, and every risk is continuous, so a single finite net must control the risks of all candidate rules.” Compactness gives a finite net at any specified radius, but does not make a collection of continuous functions equicontinuous.
Correction: Establish a common continuity bound for the candidate rules’ risk functions, then choose the net radius from that common bound. If only one fixed rule is being considered, its own continuity can be enough, but a sequence or class of rules requires uniform control to use one net for all of them.

Key takeaway: Compactness makes finite parameter nets available; equicontinuity makes their risk guarantees transferable. Together they turn a finite-net near-minimax rule into an approximately minimax rule over the full compact parameter space.

Check Your Understanding

Try these questions before moving on.

State the definition of an $r$-net and explain where compactness is used to obtain a finite one.
Why must equicontinuity be uniform over the rule class for one net to work for every rule?
In the squared-error example, verify the bound $|R(\theta,a)-R(\phi,a)|\leq2|\theta-\phi|$.
For the Bernoulli sample mean, what is the exact worst-case squared-error risk, and at which parameter value is it attained?
What feature of the functions $R_k$ in the fixed-net example prevents a finite-net maximum from controlling their continuum maxima?

Back to Tutorials