动机
许多计算问题都化为最小化大量记录的平均损失。参数向量描述模型或近似,每条记录贡献一项损失。完整梯度可能要扫描全部数据,但粗略方向往往已足以作一次有用更新。小批量方法正是在方向准确度与取得方向的成本之间取舍。
这个取舍同时涉及数学与计算机。平均更多独立抽取的梯度,可降低方差;但它也消耗更多记录求值、可能需要更大的缓冲,并减少固定预算内可更新参数的次数。硬件处理中等大小矩阵,也可能比逐项小运算有效率。因此,最小或最大批量都不自动是最佳选择。
必须先说清想改善什么。降低期望梯度平方、降低一步后目标值、每秒处理更多记录,以及符合内存限制,是不同的结论。数据管线较快,不能证明优化较快;驻点界也不能证明非凸目标已达全局最小值。
定义
定义 3.1.1
(有限和目标与有放回小批量梯度)
参数 ,考虑有限和目标:
每个 都可微。完整梯度在同一参数处求全部 项。大小为 的小批量梯度,从 中独立均匀地有放回抽取 ,并计算
此定义容许索引重复。无放回抽取子集是另一种设计,方差会有有限总体修正。把数据洗牌后依次使用又不同:给定前面抽到的记录,同一轮后续索引不再是独立均匀抽样。使用证明前,不能只因都叫“小批量”便忽略差异。
定义 3.1.2
(-光滑)
采用欧氏(Euclidean)范数与内积。设常数 。若可微目标 对所有 都有 ,称 为 -光滑。
沿线段积分梯度,并限制梯度变化,可得上二次模型:
光滑不等于凸。光滑函数仍可有多个局部极小值、鞍点,甚至没有有限下界。后面的定理因此另外假设 是有限下界,而不把它混入光滑的定义。
定义 3.1.3
(随机迭代与条件无偏)
随机迭代为 ,固定步长 。令 包含初始状态及第 步抽取批量之前的全部随机信息,因此给定 时当前参数 已知。若每个 都有 ,称梯度估计条件无偏。
这比含糊地说“整个过程平均方向正确”更精确,也正是下降论证所需的假设。
定理 / 命题
命题 3.1.4
(独立小批量降低条件方差)
在固定参数处定义
上述有放回小批量满足
若在固定 后重新独立抽取批量,同样恒等式在第 步条件成立。
此命题只用更新噪声衡量批量。实际上,同一个 还进入其他几笔账。
概念视角算法
同一批量大小,不同的比较分母
从统计看,增大 降低每次更新的独立梯度噪声。从算法预算看,每次参数移动耗用 次分量求值。从系统看,它改变缓冲区大小、矩阵运算效率及通信频率。比较方法前要选与问题相符的分母:更新次数、记录求值次数、实际耗时或内存。只报告每次更新的改善,会把取得该更新的成本隐藏起来。
第二个结果把方差恒等式变成关于多次更新的保证。
定理 3.1.5
(光滑随机迭代的驻点界)
设 全局 -光滑,且有下界 。取确定的 、、。假设每步条件无偏,并有条件噪声界 ,相关期望有有限矩。则
结论限制平均期望梯度平方,并不断言每次迭代改善、最后一次最好,或已到达全局极小值。
证明思路
证明
(独立中心化抽样的交叉项消失)
每个随机分量梯度的期望都是完整梯度。把 个向量中心化,展开总和的范数平方。独立且均值为零,令交叉内积的期望消失;剩下 项共贡献 ,再除以 ,即得第一个定理。此论证直接适用于向量,而不只是逐坐标的说法。
证明
(条件期望下的一步下降,再裂项相消)
对第二个定理,在光滑上界中代入 ,并给定 取期望。条件无偏处理线性项,中心二阶矩恒等式则给出
因 ,梯度平方前的下降系数至少是 。再取期望,从零加到 ,目标值项裂项相消。最后期望目标值不少于 ,移项便得所需界。参数依赖先前随机性,所以必须用条件期望:新批量要在当前参数处仍然无偏。
证明透视
驻点界中每个假设的用处
光滑性只用一次,就是在 、 处的二次上界;它把随机的一步化为含 的线性项与含 的二次项。关键一步是先对 取条件期望。在此条件下 固定,无偏性把线性项变成 ,噪声界则把二次项拆成 。步长限制 只用来使净系数 至少为 ;换成其他固定比例只改变常数,但系数必须保持为正。裂项求和消去所有中间目标值,下界 只用一次,用来控制最后一项。没有 ,右边会含 ,它可以无界增大。
固定正步长下,噪声项不会只因增加 而消失。减小步长可减噪声项,但在固定迭代预算下会放大暂态项。有正噪声时,平衡两项建议步长尺度为 ,仍须受 限制,比例常数也依赖目标差距与方差。当常数未知,这个理论建议并不是可以直接使用的全知参数选择。
若另行独立均匀地从 选一个迭代索引,其期望梯度平方正好等于左边。这给出平均界的明确输出解释。小梯度只是一次驻点判据;要换成函数值或全局最佳性保证,还需额外结构。
例题详解
例题 3.1.6
(看得见梯度噪声的一维损失)
取 、。平均是 ,极小点为 ,光滑常数 。两个分量梯度是 、,均值为 ,相对均值偏差为 ,故任何位置都有 。
在 ,以步长 作完整梯度更新,得到 ,目标由 降至 。若只均匀抽一项,更新值为 或 ,各占一半,目标分别为 、,期望为 。
批量大小 的更新噪声方差为 。因目标是二次函数,更新后期望恰为 ; 时为 。相同步长下,较大批量改善一步的期望,却花更多分量求值。在极小点,两个分量梯度仍是 :完整梯度为零,不代表随机梯度也消失。
例题 3.1.7
(比较预算,而非只比较更新次数)
同一目标从 出发,初始差距为 ,可取 。设 、、,驻点界为 。暂态与噪声项分别为 、;此上界不必精确贴近真实表现。
若分量求值预算固定为 , 可作四百次更新,相同步长下界为 。 只能作二十五次,界为 。这些特定选择中,中等批量的上界较小,但比较的是上界,不是精确结果或普遍最佳批量。
代入 ,暂态项成为 ,随 增大;噪声项却随 减少。改步长会改变比较。若硬件吞吐量依赖批量,固定时间预算又不同于固定分量求值预算。
例题 3.1.8
(内存与透明的时间模型)
一百万条稠密特征记录,各有一千维,以八字节数值存储。只保存特征矩阵便需 字节,即十进制八 GB。二百五十六条记录的批量缓冲需 字节;参数或累积梯度向量各需 。标签、优化器状态、临时数组及运行环境仍有额外开销,以上不能当成总内存承诺。
作为示意而非测量,设一步成本 毫秒,分别代表固定开销及逐条记录的工作。 与 的吞吐量约为每毫秒 与 条;模型中随批量增大,上限趋近每毫秒一百条。这不代表无限大批量最好:缓冲继续增大,同一记录预算内参数移动的次数则减少。
同步数据并行时,每个节点可先累积长度 的梯度再通信,而非传送全部原始记录。但拓扑、延迟及慢节点仍影响时间。所有节点的贡献要在同一参数版本处计算,才符合上述简单估计量;使用过时参数的梯度需要另一套分析。
常见错误
驻点定理的步长假设很容易被当成技术细节,其实不然。
反例模式
步长过大,即使没有噪声也破坏上界
断言:驻点界对任何固定步长都成立。取 、,则 、、,迭代是确定性的。取 、,更新为 ,故 。 时左边为 ,右边却是 。所断言的不等式不成立,迭代值还以 增长。修正后的表述保留假设 ,它保证下降系数为正。
常见错误
(改变抽样分布却不重新加权)
均匀抽样也是估计量的一部分。若第 项以正概率 被抽取,直接使用其梯度,期望便是概率加权目标的梯度。要对原来均匀目标无偏,单样本应改为 。但极小概率可带来很大方差;无偏不等于有效率。概率为零的记录更不能由此式恢复。
反例模式
互不相同的索引不会给出同一方差
错误说法:任意 个抽样索引都给出小批量方差 。在第一个例题中,、。有放回且 时,方差是 ;例如概率为 的批量 给出 ,偏差为 。无放回时,大小为二的批量只有 ,所以 恰好成立,方差为 。修正后,对均匀抽取的 个不同索引,应使用有限总体公式 (),这里正好给出 。
常见错误
(把定理套用到已修改的迭代)
梯度截断、动量、自适应缩放、无放回抽样及异步更新,都改变了被分析的迭代。它们可能有用,但此定理没有自动涵盖。检查一个例子的目标是否下降,也不能证明整个随机过程满足条件无偏与噪声假设。
总结
独立有放回小批量给出无偏梯度,其方差按 降低。光滑性、有限下界及条件噪声控制共同产生平均驻点界。较大批量以更多工作与内存换取每步较少噪声。有效的计算比较要先说明统计假设、输出判据与资源预算。
练习
练习 3.1.9
(在固定参数处,三个标量分量梯度为 。求完整梯度、均匀单分量梯度的方差,以及四次独立有放回小批量平均的方差。)
基础
解答 · 答案
完整梯度是 。偏差 的平方平均为 ,故单项方差为 。四个独立抽样的平均方差为 。这依赖有放回与独立;从三条记录中抽四个不同索引,并不是题设的过程。
练习 3.1.10
( 采用确定性完整梯度更新。找出对所有非零起点都严格减小目标的正步长范围,并与定理的充分限制比较。)
基础
解答 · 答案
更新为 ,非零起点的目标比为 。因此恰在 时严格下降; 时不变,更大则上升。定理采用较严格的充分范围 ,以确保证明所用的下降系数。
练习 3.1.11
(在驻点界中取 、、、、、。计算此界并指出暂态项与噪声项。结论是否保证全局最小值?)
核心
解答 · 答案
暂态项是 ,噪声项是 ,总界为 。步长满足 。若其他假设也成立,结论限制平均期望梯度平方;没有额外的适当凸性等结构,小梯度不能证明全局最优。
练习 3.1.12
(两个分量梯度为 与 ,抽样概率为 与 。求不加权梯度的期望与对均匀目标的两个重要性修正值,验证无偏,并解释为何两个概率都必须为正。)
核心
解答 · 答案
均匀目标的梯度为 ,但不加权期望是 。修正值为 与 ,期望为 。若某项概率为零,它永远不被观测,而且除以概率没有定义;无法用此方案对其任意贡献作无偏恢复。