动机
一致收敛问整个假设类的每个成员是否都有可靠经验平均。算法稳定性问的是另一件事:只换一个观察,指定训练规则的输出改变多少?假设类可以很大,而强正则化程序对一个观察仍反应很小。此时直接分析程序,可能比为全部可表示函数计费更合适。
稳定证明有两部分。概率恒等式把期望泛化化为相邻训练样本的比较;优化论证再界住输出差异。两者都不能由“正则化防止过拟合”的口号代替。前者需要独立同分布抽样,后者需要确切曲率、梯度及算法条件。
以下固定一个完整模型:紧致凸参数集上的凸光滑损失、正二次惩罚,以及由共同确定初始点开始的投影完整梯度下降。精确正则化 ERM 与其有限迭代近似便可共用同一组常数。最后的总体比较会保留优化误差及正则化偏差,并清楚只控制期望。
定义
设 C⊂Rd 非空、紧致且凸,包含于半径 R 的球,直径不超过 D。每个观察 z 的损失在包含 C 的开凸邻域为 C2,并有
0≤ℓ(w,z)≤Bℓ,∥∇ℓ(w,z)∥≤G,0⪯∇2ℓ(w,z)⪯βI(w∈C).假设对 z 可测。样本 S=(Z1,…,Zn) 独立同分布;只相差一个坐标称为相邻。若确定算法 A 对每个相邻对及测试点均有 ∣ℓ(A(S),z)−ℓ(A(S′),z)∣≤ϵ,便称为 ϵ-一致稳定。
令 RP(w)=Eℓ(w,Z)、RS(w)=n−1i∑ℓ(w,Zi)。固定 λ>0,设 FS=RS+λ∥w∥2/2、F=RP+λ∥w∥2/2。紧致性给存在,强凸性给唯一;另假设所得映射可测,使期望有意义。
迭代用确定初始点 w0∈C、固定步长 0<η≤1/(β+λ),更新 wt+1=ΠC(wt−η∇FS(wt))。相邻样本采用同一初始点、步长及步数。记 q=1−ηλ∈[0,1)、At(S)=wt。
定理/命题
定理 10.1.2
(替换一项恒等式与正则化稳定性)
每个 ϵ-一致稳定算法都满足
ES[RP(A(S))−RS(A(S))]≤ϵ.FS 的精确最小点稳定性至多 2G2/(λn)。投影梯度作 t 次更新后,稳定性至多
ϵt=λn2G2(1−qt).
令 δt=(G+λR)Dqt,则每份样本都有 FS(At(S))−CminFS≤δt。若 wλ 在 C 最小化 F,则
E[F(At(S))]−F(wλ)≤ϵt+δt.对每个固定比较点 u∈C,
E[RP(At(S))]−RP(u)≤ϵt+δt+2λ∥u∥2.
常数可以保守。损失有界保证可积分,梯度及曲率界则负责敏感度与收缩。结论是期望的绝对值,不是绝对偏差的期望,也不是某份样本的高概率保证。
证明思路
取独立替换 Zi′,以 S(i) 代替第 i 项。输出 A(S(i)) 与原 Zi 独立,替换样本又与 S 同分布,所以
ESRP(A(S))=ES,Zi′ℓ(A(S(i)),Zi).减经验风险并对指标平均,得到完整恒等式
E[RP(A(S))−RS(A(S))]=n1i∑E[ℓ(A(S(i)),Zi)−ℓ(A(S),Zi)].每个被积项绝对值由一致稳定性控制,第一个结论便成立。独立性用在确切位置:替换算法不能通过未替换的数据初始化或调参规则,暗中保留已移除观察。
一致稳定性要求对所有测试观察及所有相邻样本成立,并非只在一个已抽到的测试点看到小变化。这个强量词让我们直接把界移进期望,无须知道输出与原训练项的复杂依赖。若只有平均意义的敏感度,仍可能有别的泛化定理,但不能未作相应积分控制就沿用这个证明。
精确 ERM 令 x=argCminFS、y=argCminFS′。强凸性与受约束一阶最优性给 FS(y)−FS(x)≥λ∥x−y∥2/2,反向样本同理。相加消去共同损失及惩罚,得
λ∥x−y∥2≤n1[ℓ(y,zi)−ℓ(x,zi)+ℓ(x,zi′)−ℓ(y,zi′)]≤n2G∥x−y∥.距离为零时直接成立,否则除去距离,得至多 2G/(λn)。梯度界令每个损失沿可行线段为 G-Lipschitz,乘上 G 即得所述稳定性,不需要边界最优点的梯度为零。
证明透视
把两个最优性不等式相加
每个最小点都通过自己的目标函数证明自身:FS 的强凸性与 x 处的约束一阶条件给出二次增长 FS(y)−FS(x)≥λ∥x−y∥2/2,FS′ 在 y 处亦然。关键一步是把两个不等式相加。两个目标共有 n−1 个损失和惩罚项,它们全部抵消,只剩下两个改变了的损失,权重为 1/n。梯度界使这个余项关于 ∥x−y∥ 是线性的,而左边是二次的,于是迫使 ∥x−y∥≤2G/(λn)。这里只用到损失的凸性和 λ;曲率上界 β 并未使用。
迭代先比较同一样本的两个参数。沿可行线段积分 Hessian,梯度差为 Hxy(x−y),对称矩阵特征值在 [λ,β+λ]。合法步长令 I−ηHxy 的特征值在 [0,q]。投影非扩张,故完整更新收缩距离至少因子 q。非扩张可由两个投影的变分不等式相加证明:∥p−p′∥2≤⟨p−p′,a−a′⟩≤∥p−p′∥∥a−a′∥。
现在从共同初始点耦合相邻样本。相同参数处只有一项梯度不同,惩罚消去,所以梯度差至多 2G/n。插入另一样本在第一条轨迹目前点的中间更新,再分别用非扩张与收缩,得到
dt+1≤qdt+n2ηG,d0=0,dt≤λn2G(1−qt).最后一步是几何和。再乘损失 Lipschitz 常数,接替换恒等式,便得到有限步期望保证。
证明透视
先耦合算法,再对样本取期望
距离比较对每个相邻样本对确定成立。共同初始化令初距离零;收缩处理已累积的差异;更换观察每步注入至多 2ηG/n 的新扰动。只有建立这个统一比较后,才经替换恒等式取期望。不能把两个拟合参数当成独立随机量处理。
第二个定理不再需要概率论证:一个确定性的优化界,加上插入一次经验目标,便已足够。
经验最小点是投影更新的不动点,因受约束方向最优条件等价于相应投影恒等式。所以 ∥wt−wS⋆∥≤Dqt。目标梯度在 C 范数至多 G+λR,沿线段积分便给 δt。这个线性距离界在边界仍正确;依赖最优点梯度消失的二次上界则需要额外内点假设。
最后对固定 u 插入经验目标,有
E[F(At)]−F(u)=E[RP(At)−RS(At)]+E[FS(At)−FS(u)]≤ϵt+δt.等式用的是固定比较点经验评估无偏,不是错误声称训练输出也无偏。取 u=wλ 得正则化比较;若比较原风险,把两个惩罚移项,再舍去非正的输出平方范数项,就得第二个不等式。
三种误差各指什么
运行更久降低优化界,却可提高有限步敏感度至其极限。较大惩罚降低稳定界,却增加比较点惩罚。若比较点范数至多 R,暂不计优化项,便有 2G2/(λn)+λR2/2。取 λ=2G/(Rn) 可使此和为 2GR/n,但同时改了目标与合法步长,并非固定训练问题的免费改善。
归一化方式也重要。这里损失平均,惩罚只加一次,因此换一项的梯度差是 1/n 量级,强凸下界仍为 λ。若把惩罚也除以样本数,便是不同程序,敏感度与曲率均须重算。
若相邻初始化已知距离至多 a,同一递推会多出 qta,损失敏感度还须再乘 G。这精确显示共同初始化省去了什么,但未容许任意预处理被忽略:须先控制其相邻敏感度,而且套用概率恒等式时要在替换样本上重新运行整个算法。
Bousquet 与 Elisseeff及Hardt、Recht 与 Singer提供相关稳定性及耦合更新研究。本节自行证明指定投影完整梯度程序的常数,不能自动转移到任意随机优化器或数据调参规则。
例题详解
在 [−1,1] 取平方损失 (w−z)2/2、标签正负一、惩罚参数一。最小点为标签平均的一半。四个平衡标签给零,换一个负标签为正,输出变成 1/4。测试标签一的损失由 1/2 变 9/32,相差 7/32。一般界用 G=2 得二,比实际差大得多,但仍正确;保守上界不是误差的精确预测。
同一族取 n=100,R=1,D=2,β=1,λ=1,η=1/2,则 q=1/2。十步后稳定界为 0.08(1−2−10)≈0.079922,优化界为 6⋅2−10≈0.005859,和约 0.085781,控制正则化总体差距。原风险比较还有已声明的比较点惩罚,删掉便是在混用不同目标。
若 G=R=1,n=10000,极限统计加惩罚界是 2/(10000λ)+λ/2。选 λ=0.02 得 0.01+0.01=0.02。若选一,稳定项降至 0.0002,惩罚项却为 0.5。稳定性更强未必给更佳原风险比较。这是充分界的权衡,不是声称观察测试误差必沿此曲线变化。
常见错误
反例模式
没有曲率的凸 ERM 可以突变
令 C=[−1,1],损失 ℓ(w,z)=1+wz,标签正负一。损失非负、凸且一-Lipschitz。奇数样本量可有相邻标签和一及负一,无正则化 ERM 分别选负一及正一。测试标签一的损失差为二,不随样本量消失。凸性本身未给正二次惩罚所提供的 1/n 稳定性。
替换一项定理控制的是 ∣E[RP(A(S))−RS(A(S))]∣,即期望的绝对值。某一份训练样本的差距可以大得多,而正负相反的差距可以在平均中相互抵消。这个界也没有比较部署分布改变后的表现。要对实际抽到的样本下结论,须另加集中不等式的论证。
依赖数据的初始化,或在同一批观测上调出的惩罚,都必须算作被分析算法的一部分:恒等式会在 S(i) 上重新运行整个流程。若替换 Zi 时仍保留由 S 算出的初始化,证明所依赖的“A(S(i)) 与 Zi 独立”便不再成立。
收缩证明也需要 Hessian 界及所述步长;改用别的算法却沿用常数,需要新的耦合证明。优化与统计可靠性由误差分解联系起来,但仍是不同项。
总结
替换一项恒等式把训练敏感度连到期望泛化。正曲率控制精确最小点变化,也令相邻投影梯度轨迹收缩。再接独立证明的优化界,便得保留正则化偏差及期望范围的总体比较。
练习
快速检查
(替换恒等式中为何输出与原第 i 项独立?若隐藏初始化由未替换完整样本计算,会有什么问题?)
问 A(S(i)) 是哪些随机变量的函数。
解答 · 答案
替换样本只含其余独立原坐标及新的独立替换,全部与原第 i 项独立。只输入此样本的确定算法仍独立;若另收到原样本计出的初始化,就可能保留该观察信息,独立评估失效。须在替换样本重新计算初始化,或另行分析。
快速检查
(解 dt+1≤qdt+c,d0=0,再代入 c=2ηG/n 及 q=1−ηλ。)
解答 · 答案
递推给 dt≤cj=0∑t−1qj=c(1−qt)/(1−q)。用 1−q=ηλ 得 2G(1−qt)/(λn)。在零步两边均零,约定 q0=1。
快速检查
(平方损失、惩罚一、n=8,换一个负标签为正,精确最小点移多远?用 G=2 界住测试损失差。)
解答 · 答案
标签平均改变 2/8=1/4,最小点再除以二,所以移动 1/8。测试损失差至多 G/8=1/4。这使用精确解公式,因此比一般最坏稳定常数更锐利。
快速检查
(为何不能在受约束边界直接用 (β+λ)∥w−wS⋆∥2/2 当作目标差距上界?)
解答 · 答案
光滑性给二次余项之外,还有最优点梯度与位移的一次内积。受约束最优点只保证此项非负,不保证零,不能从上界删去。安全做法是用 (G+λR)∥w−wS⋆∥,在边界亦成立。