极小极大风险

定义 ​

给定模型族 $\{P_{\theta }:\theta \in \mathrm{\Theta }\}$、样本 $S\sim P_{\theta }^m$ 与决策损失 $L$，算法 $A$ 的最坏风险为

$$\underset{\theta \in \mathrm{\Theta }}{sup}{\mathbb{E}}_{\theta }L(A(S),\theta ),$$

极小极大风险为

$${\mathfrak{R}}_m(\mathrm{\Theta })=\underset{A}{inf}\underset{\theta \in \mathrm{\Theta }}{sup}{\mathbb{E}}_{\theta }L(A(S),\theta ).$$

先由自然选择算法，再由对手挑最坏参数；一般不能交换 inf 与 sup。是否允许随机化算法、可测性和输出空间都属于定义的一部分。

统计决策论中的估计量、决策规则与风险公理库估计量、决策规则与风险Estimator and decision rule · Statistical risk将观测映为行动的规则，以及在每个参数下对抽样随机性平均后的损失。把 ${\mathbb{E}}_{\theta }L(A(S),\theta )$ 识别为固定参数下的频率风险：先对样本与规则自身的随机性平均损失，再在参数类上取最坏情形，并在允许的规则中取下确界。学习理论的预测风险可以复用这套量词骨架，但必须逐项说明随机对象、行动空间与损失，不能另建一个同名的 minimax 概念。

以 Bernoulli 均值估计为例，取 $P_p=\mathrm{Bernoulli}(p)$、$p\in [0,1]$ 和平方损失 $(\hat{p}-p{)}^2$。样本均值 $\hat{p}$ 无偏，因此它的风险可以直接计算：

$${\mathbb{E}}_p(\hat{p}-p{)}^2={\mathrm{Var}}_p(\hat{p})=\frac{p(1-p)}{m}\le \frac{1}{4m}.$$

这只说明 ${\mathfrak{R}}_m([0,1])\le 1/(4m)$，因为 minimax 还允许其他估计器；要证明同阶下界，可选两个距离约 $1/\sqrt{m}$ 的参数，使其样本分布仍难区分，但错误动作产生约 $1/m$ 平方损失。

Bayes 风险对先验平均，minimax 对最坏参数。选择任何先验后，所有算法的最坏风险至少为其先验平均风险，因此 Bayes 问题可给 minimax 下界，但两者不相等。还应区分绝对风险、超额风险、错误概率和局部 minimax，它们使用不同损失与参数邻域。

若先固定一个估计器再报告其最坏风险，得到的是该算法的风险上界，不是 minimax 值；若交换成 $\underset{\theta }{sup}\underset{A}{inf}$，算法仿佛知道真实 $\theta$ 后才选择，值常退化为零。Inf–sup 的顺序正是“先设计统一程序，再面对未知世界”的数学表达。

参考资料

• Alexandre Tsybakov, Introduction to Nonparametric Estimation, 2009.
• Bin Yu, “Assouad, Fano, and Le Cam,” 1997.