动机
经验风险最小化指出目标,却未说明如何到达。即使假设类的统计性质良好,计算问题仍可能十分庞大。对有限项损失的平均,可以每次遍历全部观察以计算完整梯度,也可以随机选一个观察来估计梯度。前者每步工作较多;后者引入需要长期控制的波动。比较算法时,必须问在什么条件及计算成本下,能得到什么保证。
目的地亦有不同含义。对可微凸函数,零梯度识别全局最小点;对非凸函数,小梯度可能只表示接近驻点,甚至位于极大点附近。另一方面,把训练损失降至很低,不等于证明总体风险很小。优化与泛化相关,但回答不同问题,以下会保持这个区分。
证明的核心是一个至比较点的平方距离。展开其变化会出现内积,而凸性把内积连到目标差距。光滑性则直接控制函数值的变化。这些恒等式说明了为何随机方法需要平均,也说明无偏梯度的单步更新为何未必令损失下降。
定义
定义 2.1.1
(凸性与光滑性)
可微函数 为凸,若
若 且梯度满足
便称梯度为 -Lipschitz,或称 为 -光滑。
凸性说明切平面在全局的位置;光滑性限制梯度变化速度,并不蕴涵凸性。若函数二次连续可微,一致的 Hessian 算子范数界足以保证光滑。对称半正定矩阵 所定义的凸二次函数,可取正的 ;若全部曲率为零,任意正上界亦可。
确定性梯度下降是 ,其中 固定。对非空闭凸集 上的随机方法,初始点 选为确定值。以 表示第 步前已知的全部随机信息, 对它可测。梯度估计器 须满足
第二项界控制完整二阶矩,并非只控制方差。投影更新为 ,其中 是 中与 欧几里得(Euclid)距离最近的点。非空、闭及凸在有限维保证投影存在且唯一。若 且二阶矩界沿迭代仍成立,便可省略投影。
若 ,每步重新均匀抽取指标 ,则 无偏。“随机”一词本身并不保证均匀或条件独立。若抽样概率是 ,正确无偏估计须改为 。
概念视角分析
投影步是线性模型加邻近惩罚的最小点
配方可得
每一步只在由 控制的距离内信任抽样梯度给出的线性模型,并保持可行。这样写时,步长是对靠近当前点的权重,这正是两个证明都追踪平方距离 的原因。
定理/命题
定理 2.1.2
(光滑下降与凸目标的速率)
设 在 可微且 -光滑。若 ,则
若 亦凸、在 取得最小值,且 ,则对 有
定理 2.1.3
(无偏且二阶矩有界的投影 SGD)
设 在 可微且凸, 是它在 上的最小点,并满足上述估计器条件。令 、。固定 时,
若 ,取 ,上界便是 。
第二个定理不需要光滑性,但其估计器假设比无偏更强,应在实际问题中核对。指定总步数 后,这个步长在同一次运行中保持不变;不能把它当作递减步长的定理,也没有因此证明每个迭代几乎必然收敛。
证明思路
确定性证明用光滑性得到下降,用凸性得到差距。
证明
(下降不等式,再加裂项相消的距离)
令 ,积分 的导数,并减去一次项:
代入 即得下降不等式。在非驻点, 保证严格下降。较窄的范围 令距离证明更简单。
凸性给 。与下降界合并,得
展开新的平方距离,右边正是上述内积减去 。把 至 相加,距离项裂项相消。函数值单调下降,所以最后差距乘 不超过全部差距之和;再舍去非负的终点距离,便得确定性速率。
随机证明不能依赖单调下降,所以只保留距离论证。
证明
(投影、条件化与平均)
投影亦保留所需的距离不等式。若 ,沿 至任意 的线段作最小化,得到 。展开距离便有 。令 ,得
给定 后,目前点及比较点已固定;条件无偏性把内积中的 换成真梯度。凸性提供目标差距,二阶矩条件控制最后一项。取总期望并相加,得到
最后由凸性,。因此定理控制的平均明确包括 至 ,不能无声改成最后迭代。
证明透视
每个估计器假设只进入一项
随机证明完全没有用到光滑性;唯一追踪的量是 。投影一步需要 非空、闭且凸,并需要 :这样 不会使任何点离 更远,所以展开时可以忽略投影。展开平方得到两个随机项。交叉项 由条件无偏性处理,这要求给定 时 已知;二次项 由二阶矩界处理,这就是单有方差界不够的原因。
凸性用了两次:一次把 化为差距 ,另一次通过 Jensen 不等式从差距的平均过渡到平均点处的差距。关键一步是距离项可以裂项相消,而不需要 单调——噪声步本来就没有单调性。代价是结论关于 ,而不是 。
没有凸性时仍能说什么
若光滑函数有下界 ,在 下,下降不等式仍可相加为
这个结论没有用凸性,只控制驻定程度,未控制全局最优差距。 在零点梯度为零,却比全局最小值高一;它虽非整条实线上光滑有界曲率的例子,已显示逻辑问题。全局光滑的例子是 :由零点开始便停在值为二的全局极大点。小梯度定理不能排除这种初始化。
反例模式
没有凸性,差距速率便失效
断言:对有最小点 的 -光滑函数及 ,梯度下降满足 。取 ,它满足 ,故为 -光滑;取 、。由于 ,对每个 都有 ,且 。所断言的界是 ,当 时已小于 。下降不等式与梯度范数界在这里仍然成立;只有差距速率需要凸性假设。
如何理解随机界的两项
固定步长时,距离项随运行时间减少,二阶矩项则随步长增加。小步长减弱单次噪声的作用,却需要更多步才能离开初始点。指定总步数的选择,是平衡这个上界的两项,并非声称实际轨迹每步恰好遵从上界。
凸集亦保证平均点可行。若可行集是非凸离散集合,平均可行点可能不再可行;非凸投影也可能不唯一,且不满足证明用的比较距离界。若不知道 ,可以用已知上界代替,例如有界可行集的直径。所得保证可能保守,但常数的来历清楚。
所有期望均同时涵盖此前抽到的指标及目前的新噪声。先给定历史,再取总期望,并非形式上的多写一步:它确保目前位置虽然随机,对当步分析仍是已知量。若某抽样规则使用历史而改变各指标概率,就必须按真正的条件概率重新检查无偏性及二阶矩;不能继续沿用均匀抽样的计算。
例题详解
例题 2.1.4
(曲率决定安全步长)
考虑 ,、。最小值为零,。取 ,误差递推矩阵是 ,故 、,函数值依次为 。第一坐标改善较慢。若改取 ,第二误差乘数变成 ,便会交替放大。负梯度方向正确,不代表任意位移长度都合适。
例题 2.1.5
(无偏不代表噪声轨迹单调)
令 、,其中每步新噪声独立且等概率取 。记 、。固定 时,
展开平方后,交叉项的条件期望为零,便得递推。在精确最小点,只要 ,下一步必定离开。取 ,极限均方误差为 ,期望损失为 。这描述固定步长的最后迭代,并不违反随总步数调小步长的平均迭代保证。
例题 2.1.6
(有限和的抽样计算)
在某点,两个分量梯度为 ,平均梯度为 。均匀抽样的均值是 、方差是九。若第一项以概率 被抽中,仍直接用原分量梯度,均值却变成 ,方向错误。重要性加权后,两个可能值是 ,均值回到 ,方差则为 ,比九更大。恢复无偏不等于改善效率。在同一目前点平均 个独立无偏梯度,噪声方差除以 ;共同均值的平方范数并不因此除以 。
常见错误
常见错误
(把无偏随机步当作下降步)
无偏只控制条件均值,单次估计未必接近真梯度,负估计方向也未必下降;噪声标量例子在精确最小点以概率一离开。条件化不可省略,因为当前参数依赖以往的随机指标。只在第一步无条件均值正确,并不保证后续无偏。
常见错误
(用方差界代替二阶矩界)
SGD 定理要求完整的二阶矩界 。单有方差界仍允许非常大的确定性梯度,不能直接替代。若梯度范数不超过 、噪声条件方差不超过 ,则 ,所以 足够。紧致可行集上连续且有界的分量梯度常能提供所需条件。
常见错误
(只按迭代次数比较两种速率)
完整有限和梯度约需 次分量计算,单次 SGD 只需一次。只比较迭代次数可能误导;反过来,每步较便宜也不证明一定更快达到精度。几何、方差、实现及所需精度都会影响结果。
总结
光滑性控制函数值变化,凸性把内积连到全局差距,条件无偏性则让距离证明在期望下成立。平均及步长平衡处理随机波动。这些都是优化保证;所得预测器的泛化仍须另行分析。
练习
快速检查
(求第一个二次例子对所有初始点收敛的精确固定步长区间,并说明最大边界处的情况。)
解答 · 答案
误差乘数为 、,两者绝对值均小于一等价于 。在 时,第二个乘数为 ,非零误差交替而不缩小。定理所用的 足以证明简单速率,却不是这个二次函数的精确稳定区间。
快速检查
(在 SGD 定理中取 、、,求建议步长及界。若期望差距须不超过 ,这个界要求多少步?)
解答 · 答案
步长为 ,上界 也是这个值。由 得 。这里使用的是初始距离及完整二阶矩的界,不能把方差估计直接当作 。
快速检查
(在噪声标量例子中取 、、、。求 、 及期望目标值的极限。)
解答 · 答案
递推是 ,且 ,故 、。极限为 ,期望目标值趋于 。初始期望损失是 ;在这个噪声水平下,它上升到固定步长的噪声下限。
快速检查
(同一点的两个独立估计噪声均值为零、方差为 ,求它们平均的方差。为什么不能直接把这个计算套用到相邻两步 SGD?)
解答 · 答案
独立性使交叉协方差为零,故平均的方差是 。相邻步的梯度在不同的随机点计算,后一点依赖前一步的噪声,并非同一固定点的两个独立估计,所以需要重新作条件分析。