动机
有限步数的界告诉我们:预先指定更新次数后,平均迭代点有多准确;但它本身没有说明一条无限长的运行轨迹是否会停靠在最小点。要回答后者,我们需要控制所有未来更新累积的噪声,而非只控制某一步的噪声。递减学习率提供一个折衷:步长之和必须无限,让算法有足够机会继续修正初始误差;步长平方之和则必须有限,以控制条件方差的累积。
以下结论是单一迭代序列以概率一收敛,与平均迭代点的期望界不同。我们在强凸及二阶矩有界的条件下证明一个实用版本;这些是充分条件,不代表随机梯度法只在此情况下才收敛。
定义
定义 23.1.1
(强凸性与投影随机梯度格式)
设 是 的非空闭凸集。可微函数 称为 -强凸,其中 ,若对所有 ,
令 是代表第 次更新前信息的 代数流,并令 关于 可测。给定确定的正步长 ,投影更新与随机梯度的条件为
其中 ,而 是 中离 最近的点。
这里 在下一时刻可测。上界要求的是完整条件二阶矩,而不只是 的方差。即使随机步越出可行集,投影仍保证更新点可行。假设 在 上于 取得最小值;下面的引理说明强凸性使这个点唯一。
定理/命题
第一个结果把强凸性化为收敛证明真正用到的不等式。最小点位于边界、梯度不为零时,它依然成立。
引理 23.1.2
(约束最小点处的强单调性)
设 在 上可微且 -强凸, 是 在 上的最小点。则 是唯一最小点,并且对每个 ,
主定理把这个不等式与步长序列的两个条件结合起来。
定理 23.1.3
(单个迭代点的收敛)
在上述条件下,设 是确定的,并且
则 几乎必然成立。例如,、 恰在 时同时满足两个条件。
在无界区域上,完整二阶矩有界并非自动成立:强凸二次函数的梯度就是无界的。可以在有界可行集上证明矩有界,或者改用带增长条件的定理。此外,几乎必然收敛并不提供有限样本置信区间,也不自动给出普适的收敛速度。
证明或证明思路
先证明引理,再证明定理。
证明
(最优性条件加上两条强凸不等式)
对 及 ,由 的凸性有 ,所以函数 在 处取最小值,其右导数非负:
把强凸不等式从 到 写一次、从 到 再写一次,然后相加。函数值相互抵消,剩下
再加上最优性不等式即得引理。至于唯一性,从 到 的强凸不等式连同最优性条件给出:当 时,。
定理的证明把一切归结为标量 。
证明
(一步不等式,再用上鞅预付未来噪声)
若 且 ,沿 到 的线段最小化到 的距离,得 ;展开 便有 。取 、,
关于 取条件期望。由于 关于 可测,无偏性把内积中的 换成 ,矩界则控制最后一项。再用引理,并记 ,得到
定义确定的尾和 (因为 ,它有限),以及
每个 非负且关于 可测;它也可积,因为 ,而 是常数。利用 ,
由非负上鞅收敛定理, 几乎必然收敛到有限极限。 中最后一项和式单调不减,又不超过 ,所以收敛;特别地,几乎必然有 。由于 , 也几乎必然有有限极限 。若在某个样本点上 ,则在该处对所有充分大的 有 ,而 会使 发散。故 几乎必然成立。
证明透视
一次为所有未来噪声留出预算
两个步长条件在不同位置起作用。平方可和只用来使 有限并趋于零; 发散只在最后一行用到,用以排除正的极限。仅凭一步不等式无法沿每条轨迹迭代,因为它只在条件期望下成立,而噪声项 每一步都会出现。
关键一步是预付这些噪声。把全部未来预算 加到 上,吸收每一步的 ;把累积进展 加进来,吸收 ,于是总和成为上鞅。这只在步长确定时才成立:此时 是已知数, 是适应过程。强凸性通过引理提供进展项,而投影需要 闭且凸,并且 。
这里使用的标准上鞅定理可由上穿不等式得到:非负上鞅的期望关于时间一致有界,因此无限次穿越任何固定有理端点区间的概率为零;它的上、下极限必然相同。我们把定理用于一维记账过程,并没有假设迭代点本身是上鞅。
例子
例题 23.1.4
(带噪声的二次函数化为样本平均)
令 、、、,其中相互独立的 以相同概率取 和 。取 ( 时为平凡 代数)及 。随机梯度条件无偏、,并且在 上 。未投影的递推式 经归纳给出
右边落在 内,所以投影从不改变它。其期望为零,且 :交叉项因独立性和中心化而消失。定理保证它几乎必然收敛到零;二阶矩公式描述的则是不同运行之间的有限时间平均。
例题 23.1.5
(选取幂次步长)
若 ,由 级数判别法, 而 。其他假设也成立时就可以使用定理。相反, 不满足平方可和条件, 不满足步长和无穷的条件。充分条件不满足,本身并不说明每个采用该步长的问题都发散。
例题 23.1.6
(经投影到达的边界最小点)
令 、,使用精确梯度 ,并取 、。此时 ,在 上 ,约束最小点是 ,而 。第一步给出 ;此后 ,所以对每个 都有 。若不投影,同一递推给出 ,之后 :它停在 之外的无约束最小点。在约束问题中,迭代点收敛,但梯度趋于 而不是 。
常见错误
反例模式
步长总和有限会使误差停滞
即使没有噪声,取 、、 及 ,便有 。迭代点收敛到严格为正的乘积 。事实上,对 有 ,所以其对数之和有限。每一步都降低目标值,但有限的总移动量不能保证到达最小点。
固定步长则有相反的困难。对上述带噪声、投影不起作用的二次例子,固定 时,,其极限为 。这个噪声下限说明固定步长的最后迭代点不一定均方收敛。但这并不表示所有固定步长问题都失败:没有噪声时结论可以不同。
常见错误
(以为极限处梯度必为零)
定理说的是 ,其中 是 上的最小点。若 位于边界, 未必为零;在边界例子中它等于 。“随机梯度足够小就停止”这类停止规则因而可能永远不触发;证明用到的是引理中的不等式,而不是 。
常见错误
(把条件不等式误读为逐条轨迹递减)
不等式 只在条件期望下成立。个别距离可以增大:在带噪声的二次例子中 ,但 给出 。因此证明需要上鞅论证,不能沿每条轨迹作确定性递推。
总结
无穷的步长总和提供持续修正;有限的平方和使累积误差项可求和。条件无偏、完整二阶矩有界和强凸性结合上鞅论证,得到各个投影迭代点的几乎必然收敛。
练习
快速检查
(对 ,求同时满足两个步长条件的所有 。乘以 会改变答案吗?)
解答 · 答案
级数判别法要求第一个和式发散,即 ;第二个和式收敛则要求 。因此 。乘以有限正数不改变这两项判断。
快速检查
(在带噪声的二次例子中,计算 和 。)
解答 · 答案
,故 。它等于一恰好在三个符号都是 时发生,概率为 。
快速检查
(令 且 。求其约束最小点,并取 对一般 验证引理的不等式。)
解答 · 答案
最小点是 ,尽管 。对 ,。边界最优性不等式提供了额外的非负项 。
快速检查
(对常见错误部分的固定步长二次递推,由一维递推式推导二阶矩的极限。)
解答 · 答案
令 ,中心化与独立性给出 。由 ,几何系数小于一,其不动点为 。