Minimax Values on Increasing Parameter Subsets

Why Restrict the Parameter Space?

A large or infinite parameter space can be difficult to analyze directly. One approach is to study successively larger, simpler subsets and ask what their minimax values say about the full problem. Nested subsets give an immediate monotonicity result, but they do not necessarily recover the full minimax value. The distinction is between expanding the parameters for a fixed rule and choosing a new best rule on each restricted problem.

We use the standard decision-theoretic setup: for each parameter $\theta\in\Theta$, data have distribution $P_\theta$; a decision rule selects an action, and its risk is the expected loss. The results below need very little about the sampling distributions. They apply whenever the risks are defined and the same class of rules is used for every parameter subset.

Definition: Let $\Delta$ be a nonempty common class of decision rules, and let $R(\theta,\delta)\in[0,\infty]$ be the risk of rule $\delta\in\Delta$ at parameter $\theta$. For a nonempty subset $A\subseteq\Theta$, its restricted minimax value is $$ V(A)=\inf_{\delta\in\Delta}\ \sup_{\theta\in A}R(\theta,\delta). $$ The full minimax value is $V(\Theta)$. The rule class $\Delta$ is held fixed as $A$ varies; it may include randomized rules.

The nonemptiness condition in this definition is deliberate: the restricted value here is defined only for nonempty parameter sets. In the exhaustion considered below, every set must therefore be nonempty, not just their union. Values are allowed to be $+\infty$.

Monotonicity Along an Exhaustion

Theorem: Suppose $\Theta\ne\varnothing$, the sets are nonempty and nested, $$ \varnothing\ne\Theta_1\subseteq\Theta_2\subseteq\cdots\subseteq\Theta, $$ and $\bigcup_{n\ge1}\Theta_n=\Theta$. Set $V_n=V(\Theta_n)$ and $V=V(\Theta)$. Then $$ V_1\le V_2\le\cdots\le V, \qquad \lim_{n\to\infty}V_n=\sup_{n\ge1}V_n\le V. $$ The limit and inequalities are understood in the extended nonnegative reals.

Proof. For any fixed rule $\delta$, enlarging the set over which a supremum is taken cannot decrease that supremum. Thus, for every $n$, $$ \sup_{\theta\in\Theta_n}R(\theta,\delta) \le \sup_{\theta\in\Theta_{n+1}}R(\theta,\delta) \le \sup_{\theta\in\Theta}R(\theta,\delta). $$ Taking the infimum over the same class $\Delta$ preserves each inequality, giving $V_n\le V_{n+1}\le V$. Every nondecreasing sequence of extended nonnegative real numbers converges to its supremum. This proves the asserted limit and upper bound. $\square$

No existence of a minimax rule is required: the proof uses infima, not minima. Nor does the argument require compactness, continuity of risk, or a particular statistical model. The value of the full problem is an upper bound on each restricted value, but this order argument alone does not show that the bound is approached.

Worked Example: Finite-Label Prediction Approaches the Full Value

There is no informative observation. The parameter space and action space are both the positive integers, and the loss is $L(\theta,a)=1$ if $a\ne\theta$, and $0$ otherwise. Allow randomized rules, so a rule is a probability mass function $q$ on the positive integers. Take $\Theta_n=\{1,\ldots,n\}$.

For a parameter $\theta$, the risk is the probability of a wrong label: $$ R(\theta,q)=1-q_\theta. $$ For any rule, at least one of $q_1,\ldots,q_n$ is at most $1/n$, since their sum is at most $1$. Therefore $$ \sup_{\theta\in\Theta_n}R(\theta,q) =1-\min_{1\le\theta\le n}q_\theta \ge 1-\frac1n. $$ The rule assigning probability $1/n$ to each of the first $n$ labels and zero elsewhere attains this bound: its risk is $1-1/n$ at every parameter in $\Theta_n$. Hence $V_n=1-1/n$, including $V_1=0$, and $\lim_n V_n=1$.

On the full space, every probability mass function has $q_\theta\to0$ as $\theta\to\infty$. Otherwise infinitely many probabilities would be bounded below by some positive constant, contradicting $\sum_{\theta\ge1}q_\theta=1$. Thus $\sup_{\theta\ge1}(1-q_\theta)=1$ for every rule, and $V=1$. In this example the restricted values do recover the full value.

What Exhaustion Gives for a Fixed Rule

The union condition does yield an exact statement about each individual rule. It does not, by itself, permit exchanging the order of optimization and limit.

Result: Under the exhaustion assumptions of the theorem, for every fixed $\delta\in\Delta$, $$ \sup_{\theta\in\Theta}R(\theta,\delta) = \sup_{n\ge1}\ \sup_{\theta\in\Theta_n}R(\theta,\delta). $$ Consequently, $$ \lim_{n\to\infty}V_n = \sup_{n\ge1}\inf_{\delta\in\Delta}\sup_{\theta\in\Theta_n}R(\theta,\delta) \le \inf_{\delta\in\Delta}\sup_{n\ge1}\sup_{\theta\in\Theta_n}R(\theta,\delta) = V. $$

Proof. Write $s_n=\sup_{\theta\in\Theta_n}R(\theta,\delta)$. Since the sets are nested, $s_n$ is nondecreasing, and $s_n\le\sup_{\theta\in\Theta}R(\theta,\delta)$. Conversely, each $\theta\in\Theta$ belongs to some $\Theta_m$, so $R(\theta,\delta)\le s_m\le\sup_n s_n$. Taking the supremum over $\theta$ gives the reverse inequality and proves the fixed-rule identity.

For the inequality between the optimized quantities, fix any $\delta$. For every $n$, $$ \inf_{\eta\in\Delta}\sup_{\theta\in\Theta_n}R(\theta,\eta) \le \sup_{\theta\in\Theta_n}R(\theta,\delta) \le \sup_{m\ge1}\sup_{\theta\in\Theta_m}R(\theta,\delta). $$ Taking the supremum over $n$ on the left and then the infimum over $\delta$ on the right proves the inequality. The fixed-rule identity identifies its right-hand side with $V$. $\square$

The potential gap comes from the order of operations. On every restricted set one can choose a rule suited to that set; the rule can change with $n$. The full value instead requires one rule to control risk over all of $\Theta$. The fixed-rule identity does not ensure that the sequence of restricted rules can be replaced by a single rule with the same bound.

Worked Example: Restricted Values Stay Strictly Below the Full Value

Let $\Theta=\{1,2,\ldots\}$, let the observation be constant and uninformative, and let the action be a positive integer $a$. Define the loss by $$ L(\theta,a)= \begin{cases} 1,&\theta\le a,\\ 2,&\theta>a. \end{cases} $$ Use $\Theta_n=\{1,\ldots,n\}$, and allow a rule to randomize over positive-integer actions. Write $A$ for its random action. Its risk is $$ R(\theta,\delta)=1+P(A<\theta). $$

Every risk is at least $1$. The deterministic choice $A=n$ has risk $1$ for every $\theta\in\Theta_n$, so $V_n=1$ for every $n$ and $\lim_n V_n=1$.

For any randomized rule, the events $\{A<\theta\}$ increase to the whole sample space as the integer $\theta$ tends to infinity: every realized action $A$ is a finite positive integer. By continuity of probability for increasing events, $P(A<\theta)\to1$. Therefore the supremum of the risks over the full parameter space is $2$ for every rule. The risks never exceed $2$, so this supremum is exactly $2$, and $V=2$. Thus $\lim_n V_n=1<2=V$, despite nonempty nested subsets exhausting $\Theta$.

The full value is a supremum: a particular finite $\theta$ need not give risk exactly $2$. Confusing a supremum with a maximum would not change this example’s value, but would misstate why it is $2$.

Worked Example: Increasing Values Can Diverge Along an Exhaustion

Let $\Theta=\{0,1,2,\ldots\}$, let the observation again be constant, let actions be real numbers, and use squared-error loss $L(\theta,a)=(a-\theta)^2$. Take $\Theta_n=\{0,1,\ldots,n\}$; randomized rules are allowed. For a rule with random action $A$, the average of its endpoint risks is $$ \frac{R(0,\delta)+R(n,\delta)}2 = E\!\left[\frac{A^2+(A-n)^2}{2}\right] = E\!\left[(A-n/2)^2\right]+\frac{n^2}{4} \ge\frac{n^2}{4}. $$ The maximum risk on $\Theta_n$ is at least this average. Choosing the deterministic action $a=n/2$ gives risk $(\theta-n/2)^2\le n^2/4$ for every integer $0\le\theta\le n$. Consequently $V_n=n^2/4$.

For the full space, if $E[A^2]=\infty$, then $E[(A-\theta)^2]=\infty$ for every fixed $\theta$, since $A^2\le2(A-\theta)^2+2\theta^2$. If $E[A^2]<\infty$, then $E[A]$ is finite and $$ R(\theta,\delta)=E[A^2]-2\theta E[A]+\theta^2\longrightarrow\infty \quad\text{as }\theta\to\infty. $$ Either way, every rule has infinite supremum risk over $\Theta$, so $V=\infty$. Here the restricted values increase without bound and their limit equals the full value in the extended sense.

Common Pitfalls and Interpretation

Leaving out nonemptiness. The definition used here applies only to nonempty parameter subsets. Require every $\Theta_n$ to be nonempty, as well as $\Theta$, or explicitly adopt a convention for empty-set values.
Changing the rule class across subsets. The comparison of infima requires the same $\Delta$ throughout. If restrictions change which rules are allowed, the monotonicity argument need not apply as stated.
Assuming exhaustion forces equality. Exhaustion makes the worst risk of each fixed rule converge to its full-space worst risk. It does not show that the infimum over rules commutes with that limit. The threshold example gives a strict gap.
Assuming a minimizing rule exists. The theorem remains valid when all infima are unattained. Replacing an infimum with a claimed minimum requires a separate attainment argument.

Key takeaway: For nonempty nested subsets exhausting $\Theta$, restricted minimax values increase and are bounded above by $V(\Theta)$. Their limit may equal the full value, as in finite-label prediction, or be strictly smaller, as in the threshold-loss example.

Check Your Understanding

Use the definitions and arguments above to answer these questions.

Why must every $\Theta_n$ be nonempty under the definition of $V(A)$ used here?
Which part of the monotonicity proof requires the decision-rule class to remain fixed?
In the finite-label example, why does some label among the first $n$ have probability at most $1/n$?
In the threshold-loss example, why does $P(A<\theta)$ tend to $1$ for a randomized rule?
Explain in words why the fixed-rule identity does not imply $\lim_n V_n=V$.

Minimax Values on Increasing Parameter Subsets

What You'll Learn