动机
随机梯度的计算可以比完整梯度便宜,但随机性也改变了收敛保证的内容。某一步可能令目标值上升;最后迭代仍可能波动,而适当平均却已有小期望差距。要理解定理,必须说明每步之前知道什么、最后平均什么,以及假设控制的是噪声方差,还是整个梯度的二阶矩。
基本凸证明观察至最优点的平方距离。投影维持可行性,并改善比较距离;凸性再把梯度内积连到目标差距。强凸性额外提供一个距离项,让证明不必沿用普通凸情况的粗界。恰当的递减步长与递增权重会令这些额外项精确相消。
以下把相消完整推导出来,而非只列出更快速率。这解释了后期点为何有较大权重,以及初始距离项为何可以消失。结论控制固定目标的期望优化误差,不自行处理泛化、有偏抽样或某一条实现轨迹的误差。
定义
定义 18.1.1
(历史、无偏与两种矩界)
设 非空、闭且凸, 在包含它的开邻域可微且凸,并在 上于 取得最小值。选确定的 。-代数流 表示第 步前的历史, 对它可测;估计器 对 可测,并满足
另假设沿迭代有完整条件二阶矩界 。若 上梯度范数不超过 ,则 足够。
中心化噪声 的条件均值为零,所以展开平方时交叉项消失。但方差界本身未控制均值梯度,不能直接当作完整二阶矩。整个欧几里得(Euclid)空间上的全局强凸函数不可能同时有全局有界梯度;有界可行集常令假设相容。更一般地,定理只需完整矩界沿实际迭代成立。
更新为 ,其中步长确定且正,投影指欧几里得最近点。非负确定权重 的加权平均是 ,总权重须正。因 凸,此平均仍可行。
下面较快的速率还需要一个假设:可行集上一致的曲率下界。
定义 18.1.2
( 上的强凸性)
设 。若
则称 在 上为 -强凸。
最优点可以在边界,普通梯度未必要零;以下没有把它当作无约束驻点。
定理/命题
定理 18.1.3
(完整二阶矩下的凸平均界)
在上述条件下,记 ,用固定步长 及 ,则
若 ,取 得 。确定的变步长则给
定理 18.1.4
(没有无故对数项的强凸速率)
若再有 -强凸性,取 ,使用另一个平均
则
强凸平均使用递增指标权重,不是递减步长权重。不能把它代入第一个定理便宣称已证第二个。证明须先用强凸距离项,再选相匹配的加权求和。本节未要求光滑常数,也未断言几乎必然收敛。
证明思路
证明
(投影距离递推与凸平均)
令 。从 指向任意 的线段可行,在最近点对平方距离求导便得 。展开 即有 。取 ,每次实现都满足
取条件期望。给定 后当前位移已知,无偏性可把内积中的 换成 。凸性使内积不小于 。再取全期望,令 、,得到
先不要除以变步长,直接求和,距离便精确消去。舍去非负的终点项,再用凸性得 ,即得变步长公式。步长相同时便是普通平均公式,最小化两项上界给出所述步长。若 或 为零,须直接处理退化情形,不能把零代入要求为正的步长。
证明中有三个不同层次:先对每次实现的投影建立确定性不等式,再给定当前历史对新噪声取平均,最后对整段历史取全期望。若一开始就把当前点当成固定的非随机数,会漏掉它与以往抽样的依赖;若只取无条件平均,又不足以消去内积中的相关项。明确的-代数流正是使每一步成立的依据。
证明
(强凸下的加权相消)
把强凸不等式用于 、。整理后,梯度内积的下界增加 ;与前面相同的条件期望步骤给出
代入 ,再除以 :
乘以 。 的正系数为 ,恰好等于前一指标留下的负系数; 时初始正系数为零。求和后剩下
除以权重总和 ,再对相应平均用凸性,便得所述速率。
证明透视
加权相消中每个假设在哪里起作用
关于 可测只用了一次:它让位移移出条件期望,无偏性才能从内积中消去噪声。噪声并没有从 中消失;正是这一项需要完整矩 ,而不是方差 。投影在取期望之前逐条实现地使用,所以无须投影与估计器独立。
不明显的一步是步长与权重的配对。强凸性使除法后 的系数变成 ,权重 再使它等于前一指标以负号留下的 。求和能够收尾,是因为首个系数 ,所以 从不出现(但矩常数 仍取决于迭代能到达的位置);最后一项 非正,可以舍去。
权重也决定噪声总量。若用相等权重,距离系数的符号仍然正确,但噪声贡献 ,它像 那样增长;除以 后得到 阶的界。权重 把每个噪声项变成 ,对数便消失了。
输出规则与速率的意思
具体实现时必须真的计算定理指定的平均。递增权重只需存储加权和与总权重,不必保留整条轨迹;若改用最后一点,数学对象已改变。别的假设可能支持最后迭代定理,但本证明未给出它。
同一优化结果可用于经验目标,也可用于能抽取无偏梯度的总体期望。前者若逐条循环遍历数据,下一分量梯度未必在给定历史下等于完整经验梯度;后者则须新样本相对当前历史保持适当独立。两种用法不能只因公式相似便省略抽样检查。
矩常数是证明沿途统一使用的上界,未必等于解附近的二阶矩。递减噪声或局部估计可以支持更佳分析,但尚未分析前,不能用某次观察到的小梯度取代统一常数。
由目标差距控制距离
概念视角几何
目标准确度与位置
在受约束最小点,沿可行线段微分给 。把强凸性用在该点,便得差距至少 。所以强凸加权输出的期望平方距离至多 。这仍只适用指定输出,不是靠声称边界梯度为零而得。
步长需要有效的正曲率下界。若只有较小的已认证下界,可在步长与证明一起代入,得到较弱但有效保证。单点曲率、尤其有噪声的 Hessian 估计,不会自行证明整个可行集强凸。这些常数反映已知的目标信息,并非算法自动知道的量。二次增长也证唯一性:另一最小点若差距零,距离亦零;存在性则仍是独立假设。
反例模式
步长安排需要真实的曲率常数
断言:对任何凸函数 ,只要取某个 并用步长 ,就有强凸速率。取 上的 ,精确梯度 (故 ),,。步长为 ,故 ,。当 时,加权输出为 ,这也就是它的差距;断言的界却是 。线性函数对任何 都不是 -强凸的;修正是使用有效的下界 ,否则只有凸情形的定理适用。
例题详解
例题 18.1.5
(投影与边界最优点)
令 、、、、步长 ,此处 。有 ;两项平均使用 ,所以为 。界为 。最优点零的导数是一,不应用无约束零梯度测试。第二步原候选点为负,投影把它修正为可行点。
例题 18.1.6
(强凸而有噪声的均值问题)
等概率取负一及三,令 、。最优点一、强凸参数一,差距为 。新样本梯度 的噪声方差四,均值梯度范数至多二,故 足够。从负一出发,抽到三及负一,步长一及 ,给 。两项加权输出为 ,此实现的差距是 ;定理控制所有抽样的期望,不是每条实现。若 ,保证期望差距至多 。
例题 18.1.7
(方差不是完整矩)
对实线上的 ,估计器为 ,独立中心化噪声方差一。在 ,条件方差是一,完整二阶矩却是 。把 写成一便丢掉均值梯度。若可行集为 ,可用 。解附近收集的小噪声估计不能自动认证之前全部更新的矩界。
常见错误
反例模式
无条件中心化不足以控制历史内积
当前点 等概率为正一或负一,目标恒为零,估计器却返回 。无条件均值零,与真梯度期望一样;但给定当前历史,其均值是 ,且 。距离证明所需的是实际当前点的条件无偏,而非整体平均巧合为零。
强凸并不使每次有噪声的更新都下降;凸性本身也没有给出可用的统一矩常数,各条件都有不同作用。最后,以估计器调用次数计的速率不等于实际运行时间的速率,尤其当不同方法的单次调用成本不同时。
常见错误
(报告最后一点或错误的平均)
强凸定理控制的是 ,其权重像 那样增长。改报 、普通平均 或步长加权平均 (权重像 那样递减)都改变了所讨论的对象,本证明对它们都不适用。步长加权平均只是凸定理的正确输出。
常见错误
(把噪声方差当作矩常数)
递推的平方项是 。以 代替 便丢掉 ,而它在远离最优点时很大,正如方差例子所示。应使用 ,其中梯度界 须在迭代能到达的范围内成立。
总结
投影控制实现距离,条件无偏处理一次噪声项,完整二阶矩控制平方余项。普通凸性给步长加权界;强凸性则支持另一种精确相消,得到递增权重输出的 期望差距。
练习
快速检查
(变步长证明为什么应先求和再除以步长?用 及 写出以 加权的界。)
解答 · 答案
未除步长时,距离项是 ,精确相消;若先除以不同步长,相邻系数便不同,须另作分析。直接得到 ,输出按步长加权。
快速检查
(取 、,列出步长及归一化的强凸平均权重,并指出在 处相消的系数。)
解答 · 答案
步长为 ,即 ;归一化输出权重为 ,即 。在 处, 的加权负系数为 , 的正系数为 ,恰好消去。输出含 ,不含 。
快速检查
(条件噪声方差至多为九,均值梯度范数至多为四。求足够的 ,以及 、 时的最优凸界。)
解答 · 答案
条件中心化给出 ,即 。步长为 ,最优期望界为 。这个界可能偏保守,并不表示实际误差就是一。
快速检查
(在 上最小化 ,验证边界最优点与证明使用的强凸内积不等式相容。)
解答 · 答案
最优点为零,导数为一。可行 的差距为 ,而 。因 ,这正好等于差距加 ,即证明所用的强不等式,完全不要求受约束最优点的梯度为零。