Why Epi-Convergence Enters Minimax Problems
A sequence of statistical problems may produce maximum-risk functions that converge poorly in the uniform sense. The approximating risks can behave very differently far from any fixed procedure, even when their behavior near each fixed procedure is stable. For minimization, the essential questions are more targeted: can a sequence of procedures with nearly minimal maximum risk escape to remote parts of the procedure space, and must its limits minimize the limiting objective?
Epi-convergence answers these questions through two requirements: a lower bound along every convergent sequence and the existence of a recovery sequence for each candidate limit. Neither requirement demands uniform convergence. To turn these conditions into conclusions about minimizers, however, one also needs compactness of bounded sublevel sets.
- For every \(x\in D\) and every sequence \(x_n\to x\), \(f(x)\leq\liminf_{n\to\infty} f_n(x_n)\).
- For every \(x\in D\), there is a sequence \(x_n\to x\) such that \(\limsup_{n\to\infty} f_n(x_n)\leq f(x)\). Such a sequence is called a recovery sequence for \(x\).
The first condition prevents objectives along convergent procedures from falling below the limiting objective. The second says the limiting objective can be approached from the approximating problems. When \(f(x)=+\infty\), the recovery inequality imposes no restriction beyond convergence to \(x\); the lower-bound condition still matters.
Maximum Risk as an Objective
For a statistical decision problem, write \(R(\theta,\delta)\) for the risk of procedure \(\delta\) at parameter value \(\theta\). On a procedure space \(D\), its maximum-risk function is
An approximation to the problem may have risks \(R_n(\theta,\delta)\) and maximum-risk function \(M_n(\delta)=\sup_{\theta\in\Theta}R_n(\theta,\delta)\). More generally, the approximations may use changing parameter sets. The results below concern the resulting functions \(M_n\) on a common metric space of procedures; for readability, they are stated for generic functions \(f_n\). The minimax value is \(\inf_{x\in D}f_n(x)\), and a procedure is an \(\varepsilon_n\)-near-minimizer when its objective is at most \(\varepsilon_n\) above that infimum.
Equicoercivity is a uniform compactness requirement across the approximating objectives. It is tailored to minimization: a sequence of near-minimizers whose objective values stay bounded above must have a convergent subsequence.
A Useful Sufficient Condition
Uniform convergence is one sufficient route to epi-convergence, but it is stronger than necessary. The following local version is enough and helps verify the epi conditions in examples.
Proof. Fix \(x\in D\) and any sequence \(x_n\to x\). The set consisting of \(x\) and all the \(x_n\) is compact: any open cover contains a set covering \(x\), which covers all but finitely many \(x_n\), and the remaining points can be covered finitely. Uniform convergence on this compact set gives \(f_n(x_n)-f(x_n)\to0\). Continuity gives \(f(x_n)\to f(x)\), and hence \(f_n(x_n)\to f(x)\). In particular, the epi lower-bound condition holds. Taking the constant sequence \(x_n=x\) gives \(f_n(x)\to f(x)\), so it is a recovery sequence. \(\square\)
Worked Example: A Maximum of Two Risks
Worked Example: A Maximum of Two Risks
Let the procedure space be \(D=\mathbb{R}\), and let the parameter set contain two values. Define the risks and their maximum by
For each fixed \(a\), the two risks converge to \(a^2\) and \(a^2/4\), respectively, so \(M_n(a)\to f(a)=a^2\). More generally, if \(a_n\to a\), then \(a_n-1/n\to a\) and \(a_n+1/n\to a\). Thus \(M_n(a_n)\to\max\{a^2,a^2/4\}=a^2=f(a)\). This verifies both epi-convergence conditions: the lower bound holds with equality in the limit, and the constant sequence \(a_n=a\) is a recovery sequence.
This convergence is not uniform on all of \(\mathbb{R}\). For any fixed \(n\), as \(a\to+\infty\), \(M_n(a)=(a-1/n)^2\) eventually, and \(M_n(a)-a^2=-2a/n+1/n^2\), which is unbounded in magnitude. Yet the minimum can be found exactly. At \(a=1/(3n)\), the two risks are both \(4/(9n^2)\). If \(a\leq1/(3n)\), the first risk is at least \(4/(9n^2)\); if \(a\geq1/(3n)\), the second is at least \(4/(9n^2)\). Therefore the minimum is \(4/(9n^2)\), attained at \(a=1/(3n)\). These minimizers converge to the minimizer \(0\) of \(f(a)=a^2\).
Near-Minimizers Under Epi-Convergence
The key result combines epi-convergence with equicoercivity. It gives convergence of the infima and identifies the limits of near-minimizers without requiring uniform convergence.
Proof. First fix any \(x\) with \(f(x)<+\infty\), and take a recovery sequence \(y_n\to x\). Since \(m_n\leq f_n(y_n)\), the recovery inequality gives \(\limsup_n m_n\leq\limsup_n f_n(y_n)\leq f(x)\). Taking the infimum over such \(x\) yields \(\limsup_n m_n\leq m\). In particular, \(m_n\) is bounded above for all sufficiently large \(n\).
To prove the lower bound, choose a subsequence \(m_{n_k}\) converging to \(\liminf_n m_n\). For each \(k\), the definition of the finite infimum permits a choice \(z_k\) such that \(m_{n_k}\leq f_{n_k}(z_k)\leq m_{n_k}+1/k\). The values \(f_{n_k}(z_k)\) are bounded above, so equicoercivity gives a further subsequence converging to some \(z\). The epi lower-bound condition then implies \(f(z)\leq\liminf_k f_{n_k}(z_k)=\liminf_n m_n\). Since \(m\leq f(z)\), it follows that \(m\leq\liminf_n m_n\). Together with the upper bound, this proves \(m_n\to m\).
Now consider any sequence of near-minimizers \(x_n\). Its objective values satisfy \(f_n(x_n)\leq m_n+\varepsilon_n\), which is bounded above. Equicoercivity therefore gives a convergent subsequence, say \(x_{n_k}\to x\). The epi lower bound and convergence of the infima imply \(f(x)\leq\liminf_k f_{n_k}(x_{n_k})=m\), where the equality follows from \(m_{n_k}\leq f_{n_k}(x_{n_k})\leq m_{n_k}+\varepsilon_{n_k}\). By definition of \(m\), \(f(x)\geq m\); hence \(f(x)=m\). The same argument applies to any cluster point. \(\square\)
Worked Example: Compactness Controls Near-Minimizers
Worked Example: Compactness Controls Near-Minimizers
Let \(D=\mathbb{R}\) and \(f_n(a)=(1+1/n)a^2\). For every \(a_n\to a\), \(f_n(a_n)\to a^2\), so the epi-limit is \(f(a)=a^2\). The values are \(m_n=m=0\). For any real \(C\geq0\), if \(f_n(a)\leq C\), then \(|a|\leq\sqrt{C/(1+1/n)}\leq\sqrt C\); if \(C<0\), the sublevel sets are empty. These uniform bounds show equicoercivity.
The convergence is not uniform on \(\mathbb{R}\), since \(f_n(a)-f(a)=a^2/n\) is unbounded as a function of \(a\) for each \(n\). Nevertheless, any sequence with \(f_n(a_n)\leq m_n+\varepsilon_n=\varepsilon_n\), where \(\varepsilon_n\to0\), satisfies \[ |a_n|^2\leq\frac{\varepsilon_n}{1+1/n}\leq\varepsilon_n. \] Thus \(a_n\to0\), the unique minimizer of the limit. Here the conclusion follows directly, and the theorem explains the general compactness principle behind it.
Worked Example: What Escape Looks Like
Worked Example: What Escape Looks Like
For each \(n\), consider a single-parameter problem with procedure \(a\in\mathbb{R}\) and risk \(R_n(a)=(a-n)^2\). Its maximum-risk function is just \(f_n(a)=(a-n)^2\), and its minimum is \(m_n=0\), attained at \(a_n=n\).
For any sequence \(a_n\to a\), the sequence \(a_n\) is bounded, so \(|a_n-n|\to+\infty\), and consequently \(f_n(a_n)\to+\infty\). The epi-limit is therefore the function \(f(a)=+\infty\) for every \(a\): the lower-bound condition holds, and the recovery inequality for this infinite-valued limit is automatic. But \(\inf_a f(a)=+\infty\), whereas every approximating infimum is zero. The minimizers \(a_n=n\) have no convergent subsequence. The sequence is not equicoercive: its zero sublevel sets contain \(n\) at index \(n\), and these points escape every compact subset of \(\mathbb{R}\).
Common Pitfall and Practical Interpretation
A tempting but incorrect argument is: “The objectives epi-converge, so their minimizers must converge to a minimizer of the limit.” Epi-convergence only controls sequences that converge to a point in the procedure space. It cannot by itself rule out minimizing procedures that move farther away as \(n\) increases. The escaping-risk example shows the gap: the minimizers have low risk, but no finite procedure is a limit of them.
The correction is to check two separate ingredients. Epi-convergence gives the appropriate local comparison of objective values, while equicoercivity prevents bounded-objective sequences from escaping. When both hold and the limiting infimum is finite, near-minimizers have cluster points, and each cluster point is a minimizer of the limiting maximum-risk function. If that minimizer is unique, relative compactness and the fact that every cluster point is the same imply that the entire near-minimizing sequence converges to it.
In applications, the topology on the procedure space is part of the claim: convergence of procedures must be meaningful for the intended conclusion. Equicoercivity must then be verified in that topology, often by proving that any procedure with maximum risk below a fixed bound lies in a relatively compact region. A pointwise comparison of risks at each parameter value does not, on its own, establish either epi-convergence of the maximum-risk functions or this compactness condition.
Check Your Understanding
Use the definitions and results above to answer these questions.
- State the two conditions in the definition of epi-convergence and explain the distinct role of each.
- Why does the maximum-risk example with two parameters fail to converge uniformly on \(\mathbb{R}\), even though its minimizers converge?
- In the near-minimizer theorem, where is equicoercivity used in proving convergence of the minimax values?
- For \(f_n(a)=(a-n)^2\), identify the epi-limit and explain why it does not have the same infimum as the approximating functions.
- If the limiting objective has a unique minimizer, what additional conclusion follows for a sequence of near-minimizers under the theorem’s assumptions?