Why Penalize a Minimax Problem?
A minimax value is the infimum of maximum risk over all decision rules. On a noncompact rule space, rules with nearly minimal risk may range over regions that are difficult to control, and the infimum need not be attained. A coercive penalty offers a way to confine a penalized search to a compact region. The tradeoff is that the selected rule minimizes risk plus penalty, not risk alone. To use this method responsibly, we need both a compactness argument and an explicit bound on the risk cost of penalization.
The key bound compares a penalized minimizer with a rule that is already approximately minimax and has finite penalty. Its size depends on that comparator’s penalty. Coercivity by itself guarantees compact sublevel sets; it does not guarantee that the penalty has little effect on maximum risk.
Setup and Definitions
Let \(\mathcal{D}\) be a nonempty metric space of decision rules. For \(\delta\in\mathcal{D}\), let \(M(\delta)=\sup_{\theta\in\Theta}R(\theta,\delta)\) be its maximum risk, where \(R(\theta,\delta)\) is the risk at parameter \(\theta\). Assume \(M:\mathcal{D}\to[0,\infty]\), and define the minimax value \(V=\inf_{\delta\in\mathcal{D}}M(\delta)\). Throughout, assume \(V<\infty\). Let \(J:\mathcal{D}\to[0,\infty]\) be a penalty, and for \(\lambda>0\) define the penalized objective \(H_\lambda(\delta)=M(\delta)+\lambda J(\delta)\).
We assume lower semicontinuity of \(M\) and \(J\) when proving existence. Lower semicontinuity means, in particular, that if \(\delta_k\to\delta\), then \(M(\delta)\le\liminf_k M(\delta_k)\), and likewise for \(J\). For \(\lambda>0\), these assumptions imply that \(H_\lambda\) is lower semicontinuous. Importantly, a finite penalized objective somewhere is a separate requirement for a useful existence result: lower semicontinuity and coercivity alone do not supply such a rule.
Compact Confinement and Existence
The first fact explains the role of coercivity. Any rule whose penalized objective is bounded above must have bounded penalty. Since bounded penalty places a rule in a compact sublevel set, penalized near-minimizers cannot escape arbitrarily far in the rule space.
To prove the containment, take a rule with \(H_\lambda(\delta)\le C\). Nonnegativity of \(M\) gives \(\lambda J(\delta)\le M(\delta)+\lambda J(\delta)=H_\lambda(\delta)\le C\), so \(J(\delta)\le C/\lambda\). Coercivity makes that penalty sublevel set compact. If \(h_\lambda<\infty\), use \(C=h_\lambda+\rho\), which is finite. This proves the proposition.
The next theorem gives a sufficient condition for the penalized infimum to be attained. The condition that a rule have both finite risk and finite penalty ensures that the infimum is finite, so a minimizing sequence can be placed in a compact sublevel set.
Proof. Write \(h_\lambda=\inf_{\delta\in\mathcal{D}}H_\lambda(\delta)\). Nonnegativity gives \(h_\lambda\ge0\), and the assumed rule satisfies \(H_\lambda(\delta_0)<\infty\), so \(h_\lambda\le H_\lambda(\delta_0)<\infty\). By the definition of infimum, choose a sequence \((\delta_k)\) such that \(H_\lambda(\delta_k)\to h_\lambda\). For all sufficiently large \(k\), \(H_\lambda(\delta_k)\le h_\lambda+1\). The proposition places this tail of the sequence in the compact set \(\{\delta:J(\delta)\le(h_\lambda+1)/\lambda\}\). In a metric space, compactness gives a convergent subsequence, say \(\delta_{k_j}\to\delta_\lambda\). Lower semicontinuity yields \(H_\lambda(\delta_\lambda)\le\liminf_j H_\lambda(\delta_{k_j})=h_\lambda\). Since \(h_\lambda\) is the infimum, \(H_\lambda(\delta_\lambda)\ge h_\lambda\). Thus equality holds, and \(\delta_\lambda\) attains the infimum. \(\square\)
If no rule has finite penalized objective, then \(H_\lambda(\delta)=\infty\) for every \(\delta\), and \(h_\lambda=\infty\). Under the extended-real convention for attainment, every rule then attains this value, but this is not a useful finite optimization result. The compactness proof above applies in the finite-infimum case, not by asserting that an infinite-valued objective has a finite minimizing sequence.
Bounding the Risk Cost of Penalization
The following inequality translates optimality for the penalized objective into a maximum-risk bound. It requires a comparator with both near-minimax risk and finite penalty. If a penalized minimizer exists, compare its objective value with that comparator’s objective value.
Proof. By optimality, \(H_\lambda(\delta_\lambda)\le H_\lambda(\delta_\eta)\). Since \(J\ge0\), the risk of the penalized minimizer is at most its penalized objective. Therefore \[ M(\delta_\lambda)\le H_\lambda(\delta_\lambda)\le H_\lambda(\delta_\eta) =M(\delta_\eta)+\lambda J(\delta_\eta) \le V+\eta+\lambda J(\delta_\eta). \] All terms on the right are finite under the stated assumptions. \(\square\)
Consequently, to obtain maximum risk at most \(V+\varepsilon\), it is sufficient to find a finite-penalty comparator \(\delta_\eta\) and choose \(\lambda>0\) so that \(\eta+\lambda J(\delta_\eta)\le\varepsilon\). This separates the two sources of error: the comparator’s minimax gap \(\eta\) and the penalty contribution \(\lambda J(\delta_\eta)\). The conclusion is a bound, not a claim that the penalized minimizer has risk at most \(V+\lambda\) independently of the comparator.
Worked Examples
Worked Example: Two-Point Parameter Space
Let the parameter space be \(\Theta=\{0,2\}\), let the action space be \(\mathbb{R}\), and suppose the observation is deterministic and carries no additional information. Use squared-error loss \(L(\theta,a)=(a-\theta)^2\). Then the maximum risk at action \(a\) is \(M(a)=\max\{a^2,(a-2)^2\}\). Take \(J(a)=a^2\) and \(\lambda=2\).
The minimax value is \(V=1\). Indeed, at \(a=1\), both risks equal \(1\), while for any \(a\), the two distances from \(a\) to \(0\) and \(2\) cannot both be less than \(1\). More explicitly, if both squared risks were less than \(1\), then \(|a|<1\) and \(|a-2|<1\), which require \(a<1\) and \(a>1\), a contradiction.
For \(a\le1\), \((a-2)^2\ge a^2\), so \(H_2(a)=(a-2)^2+2a^2=3a^2-4a+4\). Completing the square gives \(H_2(a)=3(a-\tfrac23)^2+\tfrac83\), whose minimum on \(a\le1\) is attained at \(a=\tfrac23\), with value \(\tfrac83\). For \(a\ge1\), \(H_2(a)=3a^2\), whose minimum on that region is \(3\) at \(a=1\). Hence the global penalized minimizer is \(a_\lambda=\tfrac23\). Its maximum risk is \(M(\tfrac23)=\max\{\tfrac49,\tfrac{16}{9}\}=\tfrac{16}{9}\).
Using the minimax action \(a=1\) as comparator, the theorem gives \(M(a_\lambda)\le V+\lambda J(1)=1+2=3\). The actual risk, \(\tfrac{16}{9}\), satisfies this bound. The penalty has shifted the action toward zero and increased maximum risk above \(V\); the comparator’s penalty determines the stated guarantee.
Worked Example: A Numerical Compactness Bound
Let \(\mathcal{D}=\mathbb{R}\), \(M(a)=|a-3|\), \(J(a)=a^2\), and \(\lambda=\tfrac12\). This risk can be realized with a single parameter, deterministic observation, and absolute-error loss for estimating the parameter value \(3\). The minimax value is \(V=0\), attained at \(a=3\).
The penalized objective is \(H_{1/2}(a)=|a-3|+\tfrac12a^2\). For \(a\le3\), it is \(3-a+\tfrac12a^2=\tfrac12(a-1)^2+\tfrac52\), minimized at \(a=1\) with value \(\tfrac52\). For \(a\ge3\), it is \(a-3+\tfrac12a^2\), which is increasing there because its derivative \(1+a\) is positive; its minimum on that region is \(H_{1/2}(3)=\tfrac92\). Thus \(a_\lambda=1\), and \(M(a_\lambda)=2\).
Every rule with \(H_{1/2}(a)\le3\) satisfies \(\tfrac12a^2\le H_{1/2}(a)\le3\), so \(a^2\le6\). The entire sublevel set is contained in the compact interval \([-\sqrt6,\sqrt6]\). Comparing instead with \(a=3\), whose risk is \(0\) and penalty is \(9\), gives the theorem’s bound \(M(a_\lambda)\le0+\tfrac12(9)=\tfrac92\), which is valid though not sharp.
Worked Example: Approximation When the Minimax Infimum Is Not Attained
Let \(\mathcal{D}=\mathbb{R}\), with a single parameter and deterministic observation, and define the loss and risk by \(M(a)=e^{-a}\). Then \(V=0\), because \(e^{-a}>0\) for every finite \(a\) and \(e^{-a}\to0\) as \(a\to\infty\); the infimum is not attained. Choose \(J(a)=a^2\), which is coercive, and \(\lambda=0.01\).
The penalized objective is \(H_\lambda(a)=e^{-a}+0.01a^2\). Its derivative is \(-e^{-a}+0.02a\). For \(a\le0\), this derivative is negative. For \(a>0\), its derivative as a function of \(a\) is \(e^{-a}+0.02>0\); hence it increases strictly from a negative value at zero to positive values for sufficiently large \(a\). It has exactly one zero, and the objective decreases before that zero and increases after it. Thus a finite penalized minimizer exists.
For any \(\eta>0\), choose the comparator \(a_\eta=\log(1/\eta)\), for which \(M(a_\eta)=\eta\) and \(J(a_\eta)=\{\log(1/\eta)\}^2\). The risk bound is therefore \(M(a_\lambda)\le\eta+0.01\{\log(1/\eta)\}^2\). For \(\eta=0.1\), \(\log(10)\approx2.3026\), so the bound is \(M(a_\lambda)\le0.1+0.01(2.3026)^2\approx0.1530\).
This example shows how a finite-penalty approximate minimax comparator can give a useful guarantee even when no minimax rule exists. The bound depends on how large the comparator’s penalty is at the chosen accuracy.
Common Pitfalls and Practical Use
A frequent error is to infer that coercivity and lower semicontinuity alone imply a finite-valued penalized minimizer. They do not. For example, take a nonempty discrete rule space, let \(M\equiv1\), and let \(J\equiv\infty\). The finite sublevel sets of \(J\) are empty and thus compact, and \(M\) and \(J\) are lower semicontinuous. Yet \(H_\lambda\equiv\infty\). Every rule attains the extended-real infimum \(\infty\), but there is no finite objective value and no useful minimizing-sequence argument. The correction is to require a rule with finite risk and finite penalty for the finite-attainment theorem, or to handle an infinite infimum separately.
A second error is to claim that making \(\lambda\) small automatically makes the risk bias small. The proved bound contains \(\lambda J(\delta_\eta)\), and the penalty of an increasingly accurate comparator may itself grow. A valid approximation argument must check that the chosen \(\eta\) and \(\lambda\) make the sum \(\eta+\lambda J(\delta_\eta)\) small. Coercivity supplies confinement; the comparator supplies the risk guarantee.
Verify that its finite sublevel sets are compact and that the relevant objectives are lower semicontinuous.
Find a rule with both finite maximum risk and finite penalty before applying the finite-attainment result.
Use a finite-penalty \(\eta\)-minimax comparator and verify that \(\eta+\lambda J(\delta_\eta)\) meets the desired tolerance.
Check Your Understanding
Try these questions using the definitions and bounds above.
- Why does \(H_\lambda(\delta)\le C<\infty\) imply \(J(\delta)\le C/\lambda\) when \(M\ge0\)?
- Which additional condition in the existence theorem ensures that the penalized infimum is finite?
- If \(M(\delta_\eta)\le V+\eta\), what maximum-risk bound follows for a minimizer of \(H_\lambda\)?
- In the two-point example, why is the maximum risk at \(a=\tfrac23\) equal to \(\tfrac{16}{9}\), rather than \(\tfrac49\)?
- Why does coercivity alone not imply that a small \(\lambda\) produces a small risk increase?