高效的随机优化mini-batch训练

Mu Li, Tong Zhang, Yuqiang Chen, Alexander J. Smola, 2014.

本文提出了一种mini-batchSGD算法，该算法的收敛速度随批量的增大而增大。

它解决了每个迭代中的保守子问题，以最大限度地利用小批处理，同时通过保守约束控制方差。

结果表明，该算法具有最优的收敛速度，并提出了实用的分布式实现。

在大规模数据集的串行和分布式实验中，验证了该方法的有效性。

1 介绍

传统的SGD每次迭代处理一个示例，这种连续的特性使得SGD很难处理分布式推理。

一个常见的实际解决方案是使用mini-batch训练，它在每个迭代中聚合多个示例。然而，对于大规模的应用程序来说，mini-batch training同步成本可能仍然太大。在实际应用中，虽然可以采用mini-batch的方法来降低通信成本，但可能会降低收敛速度。

$\bullet$ 对于一般的凸目标函数，SGD的收敛性为

$\bullet$ 对于小批量规模b的SGD，收敛性为

为了解决这个问题，提出了一个替代的mini-batch更新策略，该策略不会随着mini-batch大小的增加而降低收敛速度。

具体地说，在每次迭代中，我们都求解一个保守的风险最小化子问题。它由两部分组成：mini-batch的原始目标函数和保守惩罚(conservative penalty)。为了达到目标，我们需要两个要素：一个更复杂的更新策略；第二，一个解决保守子问题的有效方法。

作者的方法不同于以往的工作，除了简单的梯度计算外，还增加了一个保守的惩罚，并以非平凡(nontrivial)的方式使用每个数据分区:

$\bullet$ 提出了一种新的和通用的方式来执行mini-batch更新超越简单的参数平均。

$\bullet$ 结果表明，该算法具有最优的收敛速度,

提高了批量（batch size）b较大时的收敛速度。此外，进一步证明了对于一个λ-强凸目标函数，它可以改进为

$\bullet$ 提出了两种策略来解决保守子问题，并演示了如何在一个通信高效的分布式实现（distributed implementation）中扩展它们。

$\bullet$ 在大型数据集上验证了该算法的有效性。

2 算法

推理问题的通用形式：

其中 $\phi _{i} :\Omega →R$

为凸损失函数，w为共享参数。

这种通用形式解决了大量的机器学习问题。

2.1 有效的mini-batch training

在实践中，当我们使用大型的迷你批处理大小时，在处理的示例数量方面，收敛速度会显著降低。

给定一个随机的mini-batch $I\subset \left\{ 1,....,n \right\}$ ，大小为b，我们可以将I上的目标函数定义为

在 $\Omega =R^d$ 的简单情况下，迷你批处理SGD采用以下随机更新规则:在每个迭代t，我们选择迷你批处理 $It\subset \left\{ 1,....,n \right\}$ ，大小b随机取，令

只要 $\Omega$ 有一个非平凡的形状，我们就需要添加一个投影步骤，它会找到Wt在可行集 $\Omega$ 中的最近邻居。

对于一般域 $\Omega$ ，可以将更新（5）重写为小批量的优化问题：

在本文中，我们提出通过在迭代t处求解以下子问题来更新参数:

它由两个部分组成:第一部分最小化了对mini-batch It的目标函数，旨在实现对mini-batch的充分利用。第二个组件是一个保守约束，它限制参数的剧烈变化，以避免过度使用。

下图给出该算法：

2.2 理论分析

解决保守子问题(6)的优点是当mini-batch大小增加时，收敛速度不会显著降低。

这反映在主要结果中。

在说明定理之前，需要引入凸函数f的Bregman散度的概念如下:

定理需要以下假设:

假设1 假设对于所有t:

只要我们选择 $\gamma$ t大于或等于 $\phi$ 的平滑度参数，假设成立：

换句话说，强凸性的对应项，即变化量存在一个二次上界，就足以保证这个条件。事实上，可以证明 $\gamma t=O(1/b)$ 是充分的。

基本上，假设1限定了当用子集上的一个和一个保守惩罚替换全部Bregman散度时我们可以预期的‘surprise’的数量。

定理1 考虑随机更新规则(6)，假设对于所有i都λ-强凸。

在假设1下，当选择更新参数 $\gamma t=\gamma +λ(t-1)$ 时，对于所有的 $w*\in Ω$ ：

由于增加小批量尺寸时，方差随着 O(1/b)的减小而减小，因此γ=O(1/ $\sqrt{b}$ )的缩放是合适的。这将产生以下总计regret bound：

这意味着如果小批量大小为b，在T步之后，我们的收敛边界为。因此，增加小批量大小并不影响算法处理的训练实例数量的收敛性。

3 实际考虑

两种求解保守问题（6）的优化近似方法及其分布式实现。

3.1 早期停止近似

3.1.1 EMSO-GD

EMSO-GD是SGD的直接扩展。它通过梯度下降法求解(6)。标准停止标准可用于实现早期停止。在实践中，使用最简单的策略是最方便的:限制最大的迭代次数L。这种策略的一个主要好处是简化了将在下一节中介绍的分布式实现的同步。

算法如下：

3.1.2 EMSO-CD

利用坐标下降法求解mini-batch线性SVM的对偶形式，在每一个时间EMSO-CD随机选取一个坐标j∈[1,p]，其中p为坐标的总数，然后求解一维问题：

与EMSO-GD类似，使用最大迭代次数作为早期停止条件。

算法如下：

3.2 分布式模型平均

在分布式计算中，我们假设有d台机器。通过网络连接。其中每台机器独立地解决保守的子问题，然后所有机器平均其结果。

算法如算法4所示。前面部分介绍的算法适用。

4 实验

4.1 数据集

使用三个不同尺度的二分类数据集，如表1所示。

KDD04来自于2004年KDD杯的粒子物理任务，其目标是对高能对撞机实验中产生的两种粒子进行分类。

URL数据集的目的是检测恶意的URLs。

CTR是一个包含显示广告的私人数据集，随机采样时间为三个月。目标是预测一个广告是否会被点击。

KDD04是一个密集的数据集，而其他两个数据非常稀疏。最大的数据集CTR有超过1亿个示例，原始文本文件大小约为300 GB。

4.2 设置

用逻辑回归的方法来研究分类问题。通过令

目标函数可以写成(1)的形式。这里令(yi, xi)为第i个样本对。

评估五种算法，如表2所示。

L-BFGS 这是经典内存受限BFGS方法的一个并行版本，如[18]中所述。也就是说，根机器从每个客户机获得次梯度来聚合成一个全局次梯度。随后更新参数并传播其新值。按构造方法是一个批量优化解决方案。

LibLinear 这是由林志仁的网站获得的单机实现。我们将它包括进来，为现有的和著名的“解决方案”提供一个参考点。这是一个对于凸问题复杂的批量求解。

Mini-Batch SGD 这可以有效地为每台机器上的小批量SGD计算次梯度。这些次梯度然后聚合，以获得一个完整的小批量超梯度。之后，我们使用(5)更新服务器并重新广播参数。我们使用O(1/ $\sqrt{t}$ )衰减学习率的小批量算法。具体来说,我们设定

对于迭代t，其中常数和a分别指定初始规模和衰减速度。通过对收敛过程的分析，进行网格搜索，选择最优解。我们搜索范围

EMSO-GD 使用算法4中引入的参数平均方法，同时通过(10)对每个客户机执行参数更新。它不同于以前的方法，在处理一个小批处理时考虑到损失函数的高阶信息。

EMSO-CD 与EMSO-GD的关键区别在于，它使用坐标下降来更新一个minibatch中的参数。除此之外，结构基本上是相同的。对于两个EMSO变量，我们设置λ=0。内部迭代的数量分别为5和2，并从{ $10^0，...，10^5$ }搜索λ。

4.3 小批量和收敛性

第一个完整性检查是确定关于单个节点hold上的微型批处理方法的收敛结果。为此，将批量大小从103增加到105.处理107个实例后的目标值如图1所示。

图1:在单个节点中处理107个示例后的目标值与小批量大小。从上到下，数据集分别是KDD04、URL和CTR，由于单个节点的容量有限，CTR被向下采样到400万个示例。

EMSO-GD缓解了小批量SGD的目标值会增加（也就是说处理的例子的收敛速度变慢）的问题。EMSO-CD求解保守子问题时，收敛性更稳定。

总之，与单纯的梯度计算相比，在mini-batch上求解保守优化问题是有益的。

4.4 与其他算法的比较

根据目标值对比表2中列出的算法和运行时，但只报告最佳批处理大小的结果。图2显示了结果，可以看出，这两批处理算法的收敛性。

图2：单个节点的目标值与运行时间。数据集与图1相同，从上到下依次是KDD04、URL和CTR。

对于mini-batch处理算法。EMSO-GD与SGD相当。同时，即使使用更小的批处理大小，EMSO-CD也比其他两种方法快10倍。

4.5 小批量生产和同步成本

图3显示了使用12台机器时同步成本对算法整体运行时间的贡献。

图3：当在12个和12个节点之间通信时，同步成本的一部分作为小批量大小的函数。

由于EMSO-GD和EMSO-CD在每个mini-batch中都比SGD解决了更复杂的优化问题，因此它们的同步成本也相应地比SGD小。它比梯度下降占用更多的CPU时间，即使后者处理最少的批处理5次，因此同步性进一步降低成本。

各种小批量条件下的收敛结果如图4所示。

图4:使用12个节点改变迷你批处理大小时的目标值。顶部:对于固定总数的例子设置为5x106。底部:对于固定运行时间设置为1000秒。

EMSO-GD稍微改进了SGD，而EMSO-CD有弹性地增加了mini-batch处理的大小。尽管在单节点实验中SGD与EMSO-GD具有可比性，但由于分布式环境中的通信成本，后者的性能优于前者。

此外，EMSO-CD使用大批大小有明显的优势，因为它在mini-batch大小增加时收敛得更快。

4.6 可伸缩性

图5比较了以下两种算法:EMSO-CD和LBFGS，评估不同节点数量的运行时结果。

这两种算法都受益于节点数量的增加。但L-BFGS比EMSO-CD获益更多。然而, 由于更快的对流速率，EMSO-CD仍然比L-BFGS快10倍。

表3显示了EMSO-CD达到特定目标值的定量加速。

当节点数量从5个增加到10个时，两个目标值的平均加速倍数都是1.75倍，如果节点数量增加4倍，则加速倍数增加到2.5倍。

5 结论

作者提出了一种新的mini-batch算法，在每一步中以原始形式解决一个正则化优化问题。结果表明，该方法在理论上也能达到最优收敛速度，并给出了该方法的实际实现。在各种情况下，所得到的方法的实际性能都优于mini-batch SGD。

【心理学与AI】Efficient Mini-batch Training for Stochastic Optimization