样本平均近似

样本平均近似（sample average approximation，SAA）用一组随机样本的平均成本代替期望成本，再求解这个确定的优化问题。它先把样本固定下来，所有候选决策比较同一组情景；求得的样本最优值和所选决策的真实期望成本是两个不同对象。

一个能完全算出的抽样问题

设只能从 $X=\{0,1,2\}$ 中选x，随机需求ξ以相同概率取0、2，成本 $h(x,\xi )=(x-\xi {)}^2$。真实期望为 $$F(x)=\frac{1}{2}{x}^2+\frac{1}{2}(x-2{)}^2=(x-1{)}^2+1.$$ 三个真实成本依次为2、1、2，最优x=1，最优值一。

假设独立抽到四个样本 $(0,0,0,2)$。固定这组数据后，样本平均成本为 ${\hat{F}}_4(x)=[3x^2+(x-2{)}^2]/4=x^2-x+1$。在允许的三个决策上，成本依次是1、1、3。若平局选较小x，就选零：样本最优值仍为一，但所选决策的真实成本是二，真实最优性差距是一。样本目标值碰巧接近真实最优值，并不能证明所选方案好。

点仅在三个离散决策处有效，为区分重合点作微小水平偏移；样本把零与一判为并列最优。

有解变式抽到 $(0,0,2,2)$，则样本平均恰与F相同，最优x=1。两组样本大小相同而答案不同，故一次小样本结果不能作为无误差结论。若把可行集改成连续区间[0,2]，第一组样本的最优x会变成1/2；本条的有限候选证明有明确范围。

从逐点平均到优化保证

一般地，令X为含M个决策的非空有限集合，对每个x要求 $h(x,\xi )$ 可测且 $𝔼|h(x,\xi )|<\mathrm{\infty }$。从同一总体独立同分布抽样 ${\xi }_1,\dots ,{\xi }_N$，定义 $${\hat{F}}_N(x)=\frac{1}{N}\sum _{s=1}^{N}h(x,{\xi }_s),{\hat{x}}_N\in \arg \underset{x\in X}{min}{\hat{F}}_N(x).$$ 由强大数定律，每个固定x的样本平均几乎必然趋向F(x)。因为候选只有有限个，有限个概率一事件的交仍有概率一，所以 $${\Delta }_N=\underset{x\in X}{max}|{\hat{F}}_N(x)-F(x)|⟶0\text{几乎必然}.$$ 设 $x^{\ast }\in \arg \underset{X}{min}F$。在任一已经实现的样本上插入样本目标，得到 $$0\le F({\hat{x}}_N)-F(x^{\ast })\le |F({\hat{x}}_N)-{\hat{F}}_N({\hat{x}}_N)|+|{\hat{F}}_N(x^{\ast })-F(x^{\ast })|\le 2{\Delta }_N.$$ 中间省去的项 ${\hat{F}}_N({\hat{x}}_N)-{\hat{F}}_N(x^{\ast })\le 0$。这就把统一估计误差转换为优化误差，并证明真实差距几乎必然趋于零。若只把样本问题解到容差τ，则右侧再加τ。无限决策集不能直接用“有限个事件相交”的论证，须另证统一收敛。

有界损失下的有限样本数

若进一步知道对每个x，成本几乎必然落在同一有界区间 $[a,b]$，且 $a<b$，Hoeffding不等式给出固定x的双侧误差概率不超过 $2e^{-2N{ϵ}^2/(b-a{)}^2}$。将M个候选的坏事件取并集，无需各候选成本之间独立，就有 $$Pr({\Delta }_N>ϵ)\le 2M\exp (-\frac{2N{ϵ}^2}{(b-a{)}^2}).$$ 因此，对 $0<\delta <1$，只要 $$N\ge \frac{(b-a{)}^2}{2{ϵ}^2}\log \frac{2M}{\delta },$$ 便以至少 $1-\delta$ 的概率保证所选方案的真实成本差距不超过 $2ϵ$。这是抽样前的概率保证，不是对每个样本均成立的确定性界；成本无界或样本相关时不能直接套用。

仅显示N至少280的曲线段；ε为1/4时，上界在N为613首次低于0.05，真实决策差距界为1/2。

主例可用a=0、b=4、M=3。若要 $ϵ=1/4,\delta =0.05$，充分样本数为 $\lceil 128\log 120\rceil =613$，此时真实差距以至少九成五概率不超过二分之一。该分布上界较保守；它利用的是损失范围和候选数，并没有利用三个损失函数的全部结构。

样本最优值的乐观偏差与执行

对固定x，样本均值无偏；但先取最小再平均会产生向下偏差。因为对任意固定x都有 $\underset{y}{min}{\hat{F}}_N(y)\le {\hat{F}}_N(x)$，取期望并再对x取最小，得到 $𝔼[\underset{y}{min}{\hat{F}}_N(y)]\le \underset{x}{min}F(x)$。这是期望上的不等式，并非每次样本最优值都偏低。评价已经选出的决策时，可使用独立验证样本；给定训练样本和所选决策后，独立验证均值仍以该决策的真实成本为条件期望。置信区间还需相应的方差、范围或尾部条件。

代码使用 Python 3 标准库，输入候选列表和已抽取的样本，输出每个候选的样本成本、所选x、样本最优值，以及本例已知总体下的真实成本。函数复制输入，不修改列表；M个候选、N个样本的计算需 $O(MN)$ 时间，复制与结果表需 $O(M+N)$ 空间。这里明确枚举有限集合，求解误差为零，抽样误差仍存在。

Python 3

import math

def finite_saa(candidates,samples):
    choices,observations = tuple(candidates),tuple(samples)
    if not choices or not observations:
        raise ValueError("nonempty choices and observations required")
    if not all(math.isfinite(v) for v in choices+observations):
        raise ValueError("finite data required")
    table = [(x,sum((x-z)**2 for z in observations)/len(observations)) for x in choices]
    chosen,training = min(table,key=lambda row:(row[1],row[0]))
    population = ((chosen-0)**2+(chosen-2)**2)/2
    return chosen,training,population,table

def sufficient_n(M,width,epsilon,delta):
    if M < 1 or width <= 0 or epsilon <= 0 or not 0 < delta < 1:
        raise ValueError("positive size, width, accuracy and delta in (0,1) required")
    return math.ceil(width**2/(2*epsilon**2)*math.log(2*M/delta))

for observations in [(0,0,0,2),(0,0,2,2)]:
    print(observations,finite_saa([0,1,2],observations))
print("sufficient N",sufficient_n(3,4,.25,.05))
assert sufficient_n(3,4,.25,.05) == 613

输出第一组选择零、真实成本二，第二组选择一、真实成本一，充分样本数为613。SAA可使用复杂的确定性求解器处理样本目标；它本身不是每步更换新小批量的随机梯度算法，也不会单靠增加样本消除不恰当的分布假设。