Diagonal Selection Across Finite Subproblems

From Finite Problems to One Global Rule

Suppose the parameter space is countable and can be listed as an increasing sequence of finite sets. For each finite set, it may be possible to find a rule with small maximum risk there. The difficulty is that the rule can change as the set grows: a sequence of rules that works on every fixed finite set eventually need not itself contain a rule that works everywhere. Diagonal selection addresses this by extracting a subsequence whose risk at each fixed parameter converges.

Convergence of the risk coordinates alone is not enough. The limit must be the risk vector of an available decision rule, and the coordinates must be bounded so that convergent subsequences can be extracted. We give precise assumptions that ensure both properties, including an explicit uniform bound on risks outside the finite restrictions.

Definition: Let $\Theta=\{\theta_1,\theta_2,\ldots\}$ be a countable parameter space and set $\Theta_m=\{\theta_1,\ldots,\theta_m\}$. For a decision rule $\delta$, write $R(\theta,\delta)$ for its risk at $\theta$, and define the finite minimax value $$ M_m=\inf_{\delta}\ \max_{\theta\in\Theta_m}R(\theta,\delta). $$ The global minimax value is $M_*=\inf_{\delta}\sup_{\theta\in\Theta}R(\theta,\delta)$. The rules in these infima belong to the same specified class $\mathcal D$.

The values $M_m$ are nondecreasing: enlarging the parameter set cannot decrease the maximum risk of any fixed rule, and therefore cannot decrease its infimum. We assume $0\le M_0:=\lim_{m\to\infty}M_m<\infty$. The construction below uses rules that are nearly optimal on $\Theta_m$, but also requires control of their risks beyond $\Theta_m$.

Conditions for Diagonal Selection

Here are sufficient conditions. They are deliberately explicit: a finite-subproblem approximation by itself does not supply the needed tail bound or guarantee that a limit risk vector is attainable.

Theorem: Suppose the following conditions hold.

$\Theta=\{\theta_1,\theta_2,\ldots\}$, with $\Theta_m=\{\theta_1,\ldots,\theta_m\}$, and $0\le M_0=\lim_m M_m<\infty$.
All risks in $\mathcal D$ are finite and nonnegative.
For every $\eta>0$, there are rules $\delta_m^{(\eta)}\in\mathcal D$, one for each $m$, such that $$ \max_{\theta\in\Theta_m}R(\theta,\delta_m^{(\eta)})\le M_m+\eta, \qquad \sup_{\theta\notin\Theta_m}R(\theta,\delta_m^{(\eta)})\le B_m^{(\eta)}, $$ where $B^{(\eta)}:=\sup_m B_m^{(\eta)}<\infty$. The supremum over an empty set is taken to be zero.
Risk-coordinate closedness holds on bounded sequences: if $\gamma_j\in\mathcal D$, $K<\infty$, and $R(\theta_i,\gamma_j)\in[0,K]$ for every $i,j$, then every coordinatewise limit $r_i=\lim_j R(\theta_i,\gamma_j)$ is the risk vector of some rule $\gamma\in\mathcal D$.

Then, for every $\eta>0$, there is a rule $\gamma^{(\eta)}\in\mathcal D$ such that $$ \sup_{\theta\in\Theta}R(\theta,\gamma^{(\eta)})\le M_0+\eta. $$ Consequently, $M_*=M_0$, and for every $\varepsilon>0$ there is a global $\varepsilon$-minimax rule.

The condition on the tail is uniform in $m$ for each fixed target $\eta$. It does not require the outside risks to tend to zero; it requires them not to grow without bound as the finite restrictions expand. Risk-coordinate closedness is a separate assumption: a sequence of risk vectors can converge coordinatewise to a vector that no rule in $\mathcal D$ attains.

Proof by Diagonal Extraction

Fix $\eta>0$ and use the sequence $\delta_m^{(\eta)}$ from the theorem. Since $M_m\le M_0$, each risk coordinate of each selected rule is bounded above by $K=\max\{M_0+\eta,B^{(\eta)}\}$. Nonnegativity bounds it below by zero. Thus the entire sequence of risk vectors lies in $[0,K]^{\mathbb N}$.

Extract convergence at the first parameter.
The real sequence $R(\theta_1,\delta_m^{(\eta)})$ lies in the compact interval $[0,K]$, so it has a convergent subsequence.

Repeat for each coordinate.
From that subsequence extract one along which the risk at $\theta_2$ converges, then extract for $\theta_3$, and continue.

Take the diagonal subsequence.
Choosing the $j$th index from the $j$th nested subsequence gives indices $m_j$ increasing to infinity. For every fixed $i$, $R(\theta_i,\delta_{m_j}^{(\eta)})$ converges as $j\to\infty$.

Represent the limit by a rule.
Risk-coordinate closedness supplies $\gamma^{(\eta)}\in\mathcal D$ whose risk at each $\theta_i$ equals the corresponding coordinate limit.

Write $r_i=\lim_j R(\theta_i,\delta_{m_j}^{(\eta)})$. Fix $i$. Eventually $m_j\ge i$, so $\theta_i\in\Theta_{m_j}$ and $$ R(\theta_i,\delta_{m_j}^{(\eta)})\le M_{m_j}+\eta. $$ Taking the limit along the subsequence, and using $M_{m_j}\to M_0$, gives $r_i\le M_0+\eta$. Since $R(\theta_i,\gamma^{(\eta)})=r_i$ for every $i$, taking the supremum over the enumerated parameter space proves the claimed bound.

For any rule $\delta$, its global maximum risk is at least its maximum risk on $\Theta_m$, which is at least $M_m$. Therefore $\sup_{\theta\in\Theta}R(\theta,\delta)\ge M_m$ for every $m$, and hence $M_*\ge M_0$. The constructed rules give $M_*\le M_0+\eta$ for every $\eta>0$, so $M_*\le M_0$. Thus $M_*=M_0$. Choosing, for example, $\eta=\varepsilon/2$ gives a rule with global risk at most $M_*+\varepsilon$. $\square$

Worked Examples

Worked Example: A Successful Diagonal Construction

Consider $\Theta=\{1,2,\ldots\}$ and a no-observation decision problem with rules $d_1,d_2,\ldots,d_\infty$. Specify their risks by $$ R(i,d_k)= \begin{cases} 1+1/k,&i\le k,\\ 3,&i>k, \end{cases} \qquad R(i,d_\infty)=1. $$ All risks are nonnegative. For every finite restriction $\Theta_m=\{1,\ldots,m\}$, rule $d_\infty$ has maximum risk $1$, and no rule has maximum risk below $1$, since every listed risk is at least $1$. Thus $M_m=1$ and $M_0=1$.

Fix $\eta>0$. Choose $d_m$ whenever $1/m\le\eta$, and choose $d_\infty$ for the remaining finitely many indices. On $\Theta_m$, the chosen $d_m$ has maximum risk $1+1/m\le1+\eta=M_m+\eta$; the alternative $d_\infty$ has maximum risk exactly $1$. For $d_m$, the risk outside $\Theta_m$ is $3$, while for $d_\infty$ it is $1$. Hence the tail bounds are uniform, with $B_m^{(\eta)}\le3$.

For each fixed $i$, once $m\ge i$ and $1/m\le\eta$, $R(i,d_m)=1+1/m\to1$. The coordinatewise limit is the risk vector of $d_\infty$. Its global maximum risk is $1=M_0$. This example shows how the selected finite rules may have outside risk larger than the limiting rule's risk, while a uniform tail bound still permits the diagonal argument.

Worked Example: Tail Control Does Not Replace Closedness

Let the only available rules be $d_1,d_2,\ldots$, with risks $$ R(i,d_k)= \begin{cases} 0,&i\le k,\\ 1,&i>k. \end{cases} $$ On $\Theta_m$, the rule $d_m$ has maximum risk $0$, so $M_m=0$. Its risk at every parameter outside $\Theta_m$ is exactly $1$, giving the uniform tail bound $B_m=1$. All risks are nonnegative and the finite-subproblem rules are exact minimizers.

For any fixed $i$, $R(i,d_m)=0$ for every $m\ge i$, so the risk vectors of $d_m$ converge coordinatewise to the all-zero vector. But no available rule has that vector: for each $d_k$, its risk at $i=k+1$ is $1$. In fact every available rule has global maximum risk $1$, so $M_*=1$, not $M_0=0$.

The sequence therefore satisfies the finite risk bounds and the uniform tail bound, but not the required risk-coordinate closedness. The coordinatewise limit exists as a vector, yet it does not correspond to a rule in the specified class.

Worked Example: Why an Upper Bound Alone Is Insufficient

Take a no-observation problem with $\Theta=\{1,2,\ldots\}$ and actions $a=1,2,\ldots$. Define $$ R(1,a)=0,\qquad R(i,a)= \begin{cases} -a,&2\le i\le a,\\ 1,&i>a. \end{cases} $$ For $\Theta_m$, action $m$ has maximum risk $0$: its risk at parameter $1$ is $0$, and its risks at parameters $2,\ldots,m$ are $-m$. No action can have maximum risk below $0$, because risk at parameter $1$ is always $0$. Thus $M_m=0$. For the selected rule $a=m$, every parameter outside $\Theta_m$ has risk $1$, so the outside risks are uniformly bounded above.

Nevertheless, every fixed action $a$ has risk $1$ at $i=a+1$, and therefore has global maximum risk $1$. The selected risk at any fixed $i\ge2$ eventually equals $-m$, which tends to negative infinity rather than having a convergent subsequence in a bounded interval. The failure is the absence of a uniform lower bound: an upper bound does not make the risk coordinates bounded. Nonnegative risks rule out precisely this escape to negative infinity.

Common Mistake and Practical Use

A tempting but invalid argument is: “For each fixed parameter, the risks are bounded above, so Bolzano–Weierstrass gives a convergent subsequence.” Bolzano–Weierstrass requires boundedness on both sides. The preceding example shows that finite-subproblem and outside upper bounds do not provide it. In the theorem, nonnegative risks plus a uniform upper bound place every coordinate in $[0,K]$; if losses are not nonnegative, an explicit uniform lower bound on the selected risks can serve the same purpose.

There are three distinct tasks in applying this method. First, verify that the chosen finite-subproblem rules satisfy an upper bound on the risks outside each restriction, uniformly across the sequence for the target tolerance being used. Second, establish boundedness of all risk coordinates so the diagonal extraction is legitimate. Third, justify that a coordinatewise limit is attained by a rule in the allowed class. None of these tasks follows merely from pointwise convergence, and omitting any one can invalidate the conclusion.

The method is especially useful when finite parameter restrictions are tractable but the full parameter space is infinite. It separates the finite optimization from the global limiting argument: finite minimax values identify the candidate value, tail bounds keep the selected rules controlled, and risk-coordinate closedness ensures that the coordinatewise limit is statistically available.

Check Your Understanding

Use the assumptions and proof above to answer the following questions.

Why is $M_m$ nondecreasing when the finite restrictions $\Theta_m$ are nested?
Which bound places every selected risk coordinate in a compact interval, and where is nonnegativity used?
In the diagonal subsequence proof, why must the subsequence indices tend to infinity?
What does risk-coordinate closedness add beyond coordinatewise convergence of the extracted risk vectors?
In the second worked example, which theorem condition fails, and why does a uniform tail bound not repair it?
Why does an upper bound on risks alone fail to justify Bolzano–Weierstrass extraction?