深度学习的最小牛顿解算器

1小步与大步：深度学习的最小牛顿解算器João F.Henriques Ehrhardt Samuel Albanie Andrea Vedaldi视觉几何组，牛津{joao,hyenal,albanie,vedaldi}@robots.ox.ac.uk摘要我们提出了一种快速的二阶方法，可以用作当前深度学习求解器的替代品。与随机梯度下降算法相比，该算法每次迭代只需要两个额外的前向模式自动微分运算，计算量相当于两个标准前向通道，易于实现。我们的方法解决了长期存在的问题，目前的二阶求解器，反演近似海森矩阵每次迭代准确或共轭梯度法，程序比SGD步骤慢得多。相反，我们建议保留由逆Hessian矩阵投影的梯度的单个估计，并且每次迭代更新一次，只需通过网络两次。 这一估计具有相同的大小， 到通常用于SGD的动量变量。没有保留对黑森人的估计。我们首先验证我们的方法，称为C URVE BALL ， 在 具 有 已 知 解 决 方 案 的 小 问 题 上 （ 噪 声Rosenbrock函数和退化的2层线性网络），当前的深度学 习 解 决 方案 正 在 努 力 。 然 后， 我 们 在 CI-FAR 和ImageNet上训练了几个大型模型，包括ResNet和VGG-f网络，在那里我们展示了更快的收敛速度，无需超参数调整。我们还展示了我们的优化器1. 介绍随机梯度下降（SGD）和反向传播（17）是当前深度网络训练的算法支柱。深度学习的成功证明了这种组合的强大功能，它已成功应用于大型数据集和深度网络的各种任务。然而，虽然SGD有许多优点，但收敛速度（就迭代次数而言）并不一定是其中之虽然单个SGD迭代计算速度非常快，并在优化开始时导致快速进展，但它很快就会进入一个较慢的阶段，改进是缓慢实现的这可以归因于进入参数空间的目标函数缩放不良的区域在这种情况下，快速进展将需要参数空间中不同方向的巨大不同步长，而SGD无法提供。二阶方法，如牛顿方法及其变体，通过根据目标函数的局部曲率重新缩放梯度来消除这个问题。对于R中的标量损失，这种重标度采用H−1J的形式，其中H是Hessian矩阵（二阶导数）或目标空间中局部曲率的近似，J是目标的梯度。事实上，它们可以实现局部尺度不变性（37，p。27），并在梯度下降停滞的地区取得可证明的更好进展。虽然它们在其他领域是无与伦比的，但它们在深度模型中的应用存在一些障碍。首先，反转甚至存储Hessian是不切实际的第二，由于随机采样，任何Hesian估计必然是噪声和病态的，经典的反演方法，如共轭梯度法是不稳健的。在本文中，我们提出了一种新的算法，可以克服这些困难，并使二阶优化适用于深度学习。我们特别展示了如何避免存储任何估计的海森矩阵或其逆。相反，我们将牛顿更新H−1J的计算视为求解一个本身可以通过梯度下降求解的线性系统。解决该系统的成本通过将其步骤与参数更新步骤交错来随时间摊销。我们所提出的方法增加了很少的开销，因为海森矢量积可以实现现代网络，只有两个步骤的自动差分。有趣的是，我们表明，我们的方法是等效的动量SGD（也称为重球方法）与一个单一的附加项，占曲率。因此，我们将方法命名为CURVE BALL。与其他提案不同，总内存占用量与momentum SGD一样小。本文的结构如下。介绍了相关的技术背景。2，并提出我们的方法，47634764秒3.我们评估我们的方法，并显示实验结果在秒。4.第一章相关工作在sec中讨论五、最后，我们总结了我们的研究结果在sec。六、2. 背景为了使我们的方法的描述是独立的，我们简要地总结了优化中的一些标准我们的目标是找到一个模型的最优参数（例如一个神经网络）φ：R p → R o，其中ppa-参数w ∈ R p和o输出（符号未显示对训练数据的依赖性，包含在φ为 了 紧 凑 性 ） 。 输 出 的 质 量 由 损 失 函 数 L 评 估 ：Ro→R，因此找到w被简化为优化问题：1w= arg min L（φ（w））= arg min f（w）。（一）用参数λ>0正则化，得到所谓的Levenberg（24）方法：z=− （ H + λI ） −1J ，（4）W←w+z，（ 5）其中H∈Rp×p，J∈Rp，I∈Rp×p是单位矩阵.注意，与动量GD（eq.2），新的步骤z独立于前一步骤。为了避免负担-我们省略了H（w）和J（w）中的w参数，但它们必须在每次迭代时重新计算。直觉上，情商的影响。4是针对不同的方向适当地重新缩放步长-具有高曲率的方向需要小的步长，而具有低曲率的方向需要大的步长来取得进展。还要注意，Levenbergw w重新缩放函数f会改变梯度的比例也许最简单的算法找到一个最佳的（或至少是一个稳定点）的方程。1是梯度下降（GD）。GD使用迭代w←w-更新参数βJ（w），其中β>0是学习率，J（w）∈Rp是目标函数f的梯度（或雅可比矩阵）关于参数w。一个有用的变体是用动量变量z（30）来增加GD，其可以被解释为过去梯度的衰减平均值：z←ρz−βJ（w）（2）w←（3）第一章动量参数为ρ。动量GD，由方程给出2-3，对于凸函数，可以显示出比GD具有更快的收敛，在更高的学习速率下保持稳定，并且对目标函数的不良缩放表现出稍微更好的抵抗力（25;第11段）。一个重要的方面是，这些优点几乎不需要额外的计算，只需要少量的额外内存，这就解释了为什么它在实践中被广泛使用。在神经网络中，GD通常被其随机版本（SGD）所取代，其中在每次迭代中，不是计算模型f = L（φ（ w ） ） 的 梯 度 ， 而 是 计 算 模 型 f t= L t （ φ t（w））的梯度，该模型是在从训练集随机抽取的一小批样本上评估的。2.1. 二阶优化如第1节所述，牛顿法类似于GD，但通过逆Hessian矩阵控制梯度，计算H−1J作为下降方向。然而，反演海森函数在数值上可能是不稳定的，或者反演函数甚至可能不存在。为了解决这个问题，黑森通常并因此确定由该方法选择的正则化下降方向。另一种解释这个问题的方法是Levenberg- Marquardt，它取代了等式中的I4个，诊断（H）。对于深度网络等非凸函数，这些方法仅在Hessian为半正定（PSD）时收敛到局部最小值。3. 方法3.1.自动微分和反向传播为了介绍涉及Hessian的快速计算，我们必须简短地讨论如何计算雅可比。L（φ（w））的雅可比矩阵（等式1）是通常计算为J=Jφ JL，其中Jφ∈Rp×o和JL∈Ro×1分别是模型和损失的雅可比行列式。在实践中，雅可比矩阵从来没有明确地形成，但是雅可比向量积Jv是用反向传播算法实现的。我们定义←−AD（v）=Jv（6）作为反向模式自动微分（RMAD）操作，通常称为反向传播。注意，因为损失是标量函数，所以通常在梯度下降中使用的起始投影向量v是标量，并且我们设置v= 1。然而，对于中间计算，它通常是梯度的（矢量化）张量（参见等式10）。第9段）。一种可能不太为人所知的替代方案是前向模式微分（FMAD），它从另一个方向计算矢量-雅可比积：−→′ ′[1]为了简洁，我们省略了可选的正则化项，但这并没有实质性地改变我们的推导。[2]有些资料使用了另一种形式，其中β在方程式中。3代替（等效于z的重新参数化），4765AD（v）=v J（7）这种变体在深度学习中不太常见，因为RMAD适合计算标量值函数的导数，例如学习目标，而4766φ2φL1：z0=0算法1. CURVEBALL（建议）。算法2.简化的无Hessian方法。1：对于t = 0，...， T − 1 do2：对于t = 0，...， T − 1do第 三 章 ：∆z=H（ wt ）zt+J（wt）第 四 章 ：z t+1=ρzt−β<$z5：wt+1=wt+zt+16：结束2：z0=−J（wt）3：对于r = 0，…，R − 1（或收敛）4：zr+1=CG（zr，H（wt）zr，J（wt））5：结束6：wt+1=wt+zR第七章： 端FMAD更适合于标量参数的向量值函数然而，我们稍后将证明FMAD在涉及黑森的计算中是相关的。RMAD和FMAD之间的唯一区别是乘法的结合性方向：FMAD在向前方向上传播梯度，而RMAD（或反向传播）在反向方向上进行。例如，对于函数aoboc的复合，−→ADabc（v）=（（vJ a）J b）J c （8）来自softmax层的预测向量和预测向量是逐元素乘积。因此，这些产品只需要元素方面的操作。我们注意到这是建立在一个经典的结果（29）上的，然而有两个主要的区别.首先，他们的方法是用精确的Hessian矩阵H来计算乘积，而我们用Gauss-Newton矩阵H来计算乘积，以便对鞍点具有鲁棒性。其次，我们利用现代自动微分工具，而他们依赖于一个符号操作技术，需要新的方程推导出每个模型的变化。←−′ ′ADabc（v）=J a（J b（J c v））（9）因此，这两个操作具有类似的计算开销，并且可以类似地实现。3.2. 快速Hessian矢量积由于涉及深度网络的学习目标的Hessian不一定是半正定的（PSD），因此通常使用具有此属性的代理矩阵，这可以防止二阶方法被吸引到鞍点（（8）讨论了这个问题）。其中最广泛使用的是高斯-牛顿矩阵（3;^P. 254）：H=JφHLJ T，（10）其中，HL是损失函数的Hessian。当HL是PSD时，这是所有凸损耗（例如， 逻辑损失，Lp距离），通过构造得到的H_p是PSD。 对于我们提出的方法，实际上对于任何隐式反转Hessian（或其近似）的方法，只需要计算Hessian-向量乘积H v。因此，eq.10采用非常方便的形式：3.3. 快速二阶优化本节介绍了我们的主要贡献：一种最小化目标的二阶泰勒展开的方法从起始点w离开一步z的结果可以用目标f的二阶泰勒展开来建模：f（w+z）<$f<$（w，z）=f（w）+zT J（w）+1zTH（w）z（13）大多数二阶方法寻求使最小化的更新zf，忽略高阶项：z=argminf（z′）=argmin1z′TH z′+z′TJ（14）z′z′2一般来说，通过最小化等式来找到步长z14，通过显式迭代H-1J（22;3）或共轭梯度（CG）方法（20）。后一种方法，称为无海森方法（也称为截断牛顿或牛顿-CG（37，p. 168））在内存方面是最经济的，因为..ΣΣHv=JφHJ Tv（11）它只需要访问Hessian-vector产品（3.2节）。高级视图在算法2中示出，其中←−= ADφ.. −→ΣΣHLADφ（ v） .（十二）CG代表共轭梯度的一步（停止条件，线搜索和一些中间变量，EQ的成本因此，12等于两个反向传播操作的结果。中间矩阵-向量乘积Hlu具有可忽略的成本：例如，对于平方距离损耗，H L = 2I ⇒HL u= 2u。模拟类似地，对于多项式逻辑损失，我们有HL=diag（p）−pp T H L u=p4767为清楚起见省略）。注意，对于w（外循环）的每次更新，算法2必须执行CG（内循环）的若干步骤以找到单个搜索方向z。我们提出了一些改变，以消除这种昂贵的内部循环。第一种是重新使用先前的搜索方向z来热启动内部迭代，4768zφφφφφ每次重置z（算法2，第2行）。如果z没有突然改变，那么这应该有助于减少给定步长，最优ρ和β可以通过求解a2×2线性系统（22秒）7）：CG迭代，从更接近解决方案开始第二改变是利用这一事实，以显着减少内部Σ ΣΣβ=THΣ−1ΣΣJ·T·帕兹不（十八）循环迭代到一次（R= 1）。不同的解释我们现在交错搜索方向z和参数w的更新（算法1，第4行和第5行），而不是嵌套它们（算法2，第4行和第6行）。不幸的是，这种变化失去了所有的理论保证，这些保证是在假设CG迭代的起点总是z0= −J（w t）的情况下证明的（37，p. 124）。这种担保的丧失在实践中得到了证实，因为我们发现，导致算法非常不稳定。我们的第三个变化是用梯度下降代替CG，它没有这种依赖性。微分方程14 w.r.t. z产生：△z=Jf（z）=Hz+J（15）将这些改变应用于无Hessian方法（A1-租m 2）得到算法1。我们还引入了一个可选的因子ρ，它每一步都会衰减z（算法1，第4行）。包含它的实际原因是为了逐渐获得过时的更新，这是由f的非线性所必需的。更正式地说，这种变化完全等价于增加一个正则化项（1−ρ）<$z <$2，当ρ<$1时，该正则化项消失（通常推荐用于动量参数（12））。令人惊讶的是，尽管是从二阶方法导出的，我们可以将算法1与动量GD（eq. 2-3)他们几乎是平等的，除了一个额外的曲率项H（w）z。由于增加了曲率的动量GD，这也被称为重球方法，我们将我们的算法命名为CURVE BALL。实施. 使用第3.2节中的快速海森矢量积，可以很容易地实现等式。15，包括正则化项λI（第2.1节）。 我们可以进一步提高EQ。通过对操作进行分组以最小化自动微分（反向传播）步骤的数量−ρzTH∆ zzTHzJz请注意，在计算建议的更新（eq.16），量JZ，J TZ和J L已经被计算并且不能被重新使用。 与H=J φ H LJ T的事实一起，这意味着上述2 × 2矩阵的元素可以仅用一个额外的前向传递来计算。详细证明见附录A.1。自动λ超参数缩放。正则化项λI（eq.4）可以被解释为信任区域（37，p. 68）。 当二阶近似保持良好时，λ可以很小，对应于未正则化的Hessian和大的信赖域。相反，较差的拟合需要相应的较大λ。我们可以测量由二次拟合预测的客观变化（f）与真实客观变化（f）之间的差异（或比率），通过com-fit-fit设γ =（f（w + z）− f（w））/f（z）。 这需要一个f（w+z）的目标的附加评估，但其他erwise仅依赖于先前计算的量。这使得它成为信赖域的一个非常有吸引力的估计，γ= 1对应于完美近似。（37页）69），我们每5次迭代计算γ，当γ>3/2时，λ减小0.999倍，当γ1/2时，λ增大倒数。我们注意到，我们的算法对初始λ不是很敏感。在使用批量归一化的实验中（第4节），我们简单地将其初始化为1，否则将其设置为10。我们在附录B.2中展示了自动调整超参数收敛性证明除了在我们的设置（深度神经网络）中适用的非凸问题通常缺乏强保证之外，还有一个附加的.△z=ΣJφ HL JT+λI z+Jφ JL（十六）由于我们的算法的递归性质（交错的w和z步骤）而导致的困难。我们的方法是=Jφ.HL JT z+JLΣ +λz（17）重球法（18; 10）（通过增加一个曲率项），直到最近，它一直抵制建立全球性的通过这种方式，模型上的总通过次数为两次：我们计算Jφ v和JT v′乘积，分别作为一个RMAD（反向传播）和一个FMAD运算实现（3.1节）。自动ρ和β超参数关闭form. 我们提出的方法引入了一些超参数，就像SGD一样，需要针对不同的设置进行调整理想情况下，我们希望根本不进行调优对于-tunately，方程中的二次最小化解释14允许我们在优化中利用标准结果在任何4769在没有动量的情况下（（19），表1），甚至只有在强凸或二次函数的情况下，收敛速度才有所提高出于这个原因，我们提出了两个更容易处理的情况下的证明（附录A）。第一个是我们的方法的凸二次函数的全局线性收敛性，它允许直接检查的区域的收敛以及其速度（定理A.1）。第二个建立，对于凸非二次函数，CURVE BALL18（定理A.2）。我们注意到4770图1. 已知解的退化优化问题。上图：不同求解器的随机Rosenbrock函数的轨迹（函数值越高，阴影越深）。Bot-tom：相同轨迹的每次迭代损失的演变。表1. 小退化数据集上的优化比较。 对于每个优化器，我们报告到达解的迭代次数的平均值±标准差。在随机Rosenbrock函数中使用的均匀分布的极限（等式2）。19)其中U[λ1，λ2]。年龄：13七百九十九±一百六十。51290± 4762750± 25795± 5列弗马夸特（24）16±414± 317± 49± 4BFGS（37，p.136）19±444± 2163± 2943± 21精确黑森14±110± 317± 49± 0。5C曲线B ALL（我们的）13± 0。512± 113± 135± 11由于高斯-牛顿近似和信赖域（eq. 4)这在实践中总是得到验证的。4. 实验已知解的退化问题。 虽然我们的优化器的主要目的是将其应用于大规模深度学习架构，但我们首先将其应用于有限复杂性的问题，目的是探索我们的方法在可解释领域中的优势和劣势。我们与两种流行的一阶求解器进行了比较-带有动量的SGD和Adam（13）3，以及 更 传 统 的 方 法 ， 如 Levenberg-Marquardt ， BFGS（37，p. 136）（与立方线搜索）和牛顿的方法与确切的海森。我们考虑的第一个问题是搜索二维Rosenbrock检验函数的最小值，它具有使我们能够可视化轨迹每一个优化者的发现具体地说，我们使用这个函数的随机R（u，v）=（1−u）2+100i（v−u2）2，（19）其中，在函数的每次求值时，从具有λ 1，λ 2 ∈ R的均匀分布U[λ1，λ2]中提取噪声样本i（我们可以恢复具有λ1= λ2= 1的确定性Rosenbrock函数）。 为了评估对噪声的鲁棒性，我们比较了确定性公式上的每个优化器和两个随机变量（具有不同的噪声状态）。我们还考虑第二个感兴趣的问题，最近由（31）介绍它包括将仅具有两个线性层的深度网络拟合到数据集，其中样本输入x通过关系y=Ax与样本输出y相关，其中A是病态矩阵（条件数= 105）。结果示于表1中。我们使用网格搜索来确定SGD和Adam的最佳超参数（见附录B.1）。我们报告了到达解所需的迭代次数，公差为τ= 10−4。每个优化器运行100次以上计算统计数据我们观察到，一阶方法在所有情况下都表现不佳具有精确Hessian4的Newton方法通常表现最好，紧随其后的是Levenberg-Marquardt（LM），然而它们对于大规模问题是不切实际的。我们的方法提供了可比的（有时更好）perfor-曼斯，尽管避免了昂贵的海森反演。另一方面，BFGS的性能，它近似于具有参数更新缓冲区的Hessian，似乎与噪音水平呈负相关图1示出了示例轨迹。一阶方法的缓慢振荡行为是显而易见的，以及噪声对BFGS步骤的影响。另一方面，CURVE BALL、Newton和LM在几次迭代中收敛。与动量新加坡元类似，我们的主要主张是基于第4节中的大量实验，该方法3 我 们 还 试 验 了RMSProp （ 35 ） 、 AdaGrad （9 ） 和 AdaDelta（41），但发现这些方法在这些“玩具”问题上的表现始终不如Adam和SGD。4当Hessian包含负特征值时，使用它们的绝对值（8）。确定性RosenbrockU[0，1]U[0，3]拉伊希米·雷希特SGD+动量370±40846± 2174069± 56595± 24771MNIST MLP10.80.60.40.200 0.5 1 1.5 2迭代×104图2.比较不同数据集和网络的不同优化器。显示训练误差，因为它是正在优化的量。C URVE B ALL在各种现实环境下表现良好，包括大规模数据集（ImageNet），批量归一化和严重过参数化模型（ResNet）。其超参数是相同的，除了顶部中心面板（无批次范数）。CIFAR。我 们 现在转向在更现实的数据集上训练深度网络的任务。经典的二阶方法不用于这种情况下，由于大量的参数和随机采样。我们从一个基本的5层卷积神经网络（CNN）开始。5我们在CIFAR-10上训练这个网络20个时期，有和没有批量归一化（已知可以改善条件（15）），每个实验使用128的小批量。为了评估更大模型的优化性能，我们还训练了一个更大的ResNet-18模型。作为基准，我们选择SGD（有动量）和Adam，我们发现来超越竞争对手的一阶优化器。它们的学习率是从集合10−k，k∈N中选择的，对于基本CNN使用网格搜索 ， 而 对 于 ResNet SGD 使 用 作 者 推 荐 的 时 间 表（12）。我们关注训练误差，因为它是EQ优化的量。1（验证错误在下面讨论结果可以在图中看到。2（顶行）。我们观察到，在每个设置中，CURVE BALL都以一种对标准化和模型类型鲁棒的方式优于其竞争对手。ImageNet. 为了评估我们的方法在更大规模上的实用性，我们将其应用于大规模ImageNet数据集上的分类任务。我们报告培训5基本的CNN有5×5个过滤器和ReLU激活，以及前3个卷积后的3×3个最大池化层（步幅为2）输出通道的数量分别为（32，32，64，64，10）。在使用从100个随机采样类的图像形成的子集的中等规模设置以及通过在完整数据集上训练的大规模设置两者上。两个实验都使用VGG-f架构，小批量大小为256，并遵循（6）所述的设置。结果如图1所示二、我们看到，我们的方法在这两种情况下都提供了与流行的一阶求解器相比的compelling性能，并且有趣的是，其改进幅度随着数据集的规模而增长。随机架构结果。 可以说，标准架构偏向于SGD，因为它被用于架构搜索，而它未能优化的架构评估优化器在架构上的泛化能力，测试它们在不考虑网络模型的情况下的表现，这将是有用的。我们通过比较随机生成的50个深度CNN架构上的优化器来在这个方向上进行尝试（详见附录B.3）。除了与架构无关之外，这使得任何手动调整超参数都不可行，我们认为这是可靠优化器的合理要求。CIFAR 10的结果显示在图3（左）中，作为所有运行的中值（粗线）和第25 - 75百分位数（阴影区域）。CURVE BALL始终优于一阶方法，大部分误差低于SGD和Adam的误差。CurveBall（我们的）SGD亚当KFAC误差（%）4772表2.最佳误差百分比（列车/ val.）用于不同的模型和优化方法。CURVE BALLλ使用自动λ重新缩放（秒3.3）。括号中的数字显示了脱落正则化的验证误差（比率0.3）。前三列在CIFAR-10上训练，而第四列在ImageNet-100上训练。模型基本基本+BNResNet-18VGG-fC曲线 BALLλ14.1/19.97.6/16.30.7/ 15.3（13.5）10.3/33.5C曲线 BALL15.3/19.39.4/15.81.3/16.112.7/33.8SGD18.9/21.110.0/16.12.1/12.819.2/39.8亚当15.7/19.79.6/16.11.4/14.013.2/35.9与其他二阶方法的比较。我们使用了二阶KFAC（22）方法的公共实现，并测试了他们提出的4层MLP（输出大小为128-64-32-10）的场景我们在图中示出了结果。2（右下一行），每种方法的学习率最高在这个问题上，我们的方法执行比较一阶求解器，而KFAC取得较少的进展，直到它已经稳定其Fisher矩阵估计。我们的方法的一个主要优势是它基于标准深度学习工具的最小实现，使我们能够轻松使用批量归一化等改进为了突出这一事实，在图。3（右）我们再次展示了基本的CIFAR设置，这次将C URVE B ALL与KFAC进行比较，其中有和没有批量范数，对于KFAC，这样的添加相对来说是不容易实现的。这表明我们的方法和batch-norm的组合比单独使用更强大，类似于一阶方法的情况（图2）。2）的情况。挂钟时间为了提供对每个模型的相对效率的估计，图1.3显示了基本CIFAR-10模型上的挂钟时间重要的是，我们观察到，我们的方法是有竞争力的一阶求解器，而不需要任何调整。此外，我们的pro-totype实现包括FMAD操作没有收到相同程度的优化，因为RMAD（反向传播），并可以进一步受益于精心设计。我们还试验了无Hessian优化器（基于共轭梯度）（20）。我们在附录B.4中给出了对数时间由于CG操作成本高，需要多次通过网络，因此它比一阶方法和我们自己的二阶方法慢一个数量级。这验证了我们设计没有内部CG循环的无Hessian方法的最初动机（第3.3节）。过度拟合和验证误差虽然这项工作的重点是优化，但比较训练模型获得的验证误差也很有趣报告见表2。我们观察到，使用所提出的方法训练的模型在大多数模型上表现出更好的训练和验证错误，但ResNet除外，其中过拟合起着更重要的作用。然而，我们注意到，这可以通过更好的正则化来解决，我们展示了一个这样的例子，通过在括号中报告5. 相关工作虽然二阶方法已被证明是优化确定性函数的高效工具（24; 37，p. 164）它们在随机优化中的应用，特别是在深度神经网络中的应用仍然是一个活跃的研究领域。已经开发了许多方法来改进具有曲率信息的随机优化，以避免在病态区域（8）中的缓慢进展，同时避免存储和反转Hessian矩阵的成本。一种流行的方法是从参数梯度的缓冲区及其在先前迭代中的一阶和二阶矩（例如，AdaGrad（9）、AdaDelta（41）、RMSProp（35）或Adam（13））。这些求解器受益于不需要额外的函数评估，除了传统的小批量随机梯度下降。通常，他们通过利用曲率的经验估计来设置自适应学习率，该曲率具有对Hessian的对角近似（例如，（41））或重新缩放的对角高斯-牛顿近似（例如，（9））。虽然对角结构减少了计算，但它们的总体效率仍然有限，并且在许多情况下可以通过良好调整的SGD求解器（36）来匹配二阶求解器采用不同的方法，每次迭代投入更多的计算，希望实现更高质量的更新。信赖域方法（7）和立方正则化（26;（5）典型的例子。为了达到更高的质量，他们将Hessian矩阵H或易于处理的近似值（如Gauss-Newton近似值（20; 23; 3）（在第2节中描述），或Hessian（16; 38）。属于信赖域族（7）的另一工作线（其已被证明对于诸如分类的任务是有效的）介绍了具有自然梯度的二阶信息（2）。虽然它在黎曼流形上实现了一个由Kullback-Leibler（KL）发散导出的轨迹，但实际上它相当于用Fisher矩阵F代替了修正梯度公式H−1J中的HessianH。以来（2）几位作者的开创性工作研究了各种各样的-这个想法的答案。TONGA（32）依赖于经验Fisher矩阵，其中模型预测分布上的先前期望（28）和（21）的工作建立了高斯-牛顿方法和自然梯度之间的联系。最近（22）介绍了KFAC优化器，它使用Fisher矩阵的块对角近似。这被证明是一个有效的随机解算器，在sev-tv中，4773图3.（左）CIFAR10上50个随机生成架构的结果。示出了中值（粗线）和第25 - 75位数（阴影区域）。图例中的数字表示学习率（CURVE BALL固定）。（中）训练错误与 挂钟时间（基本CIFAR-10型号）。（右）批量归一化很容易与我们的方法结合，而KFAC和其他方法则不是这样通常的设置，但仍然具有计算挑战性。特别地，它需要比参数本身多一个数量级的存储器，这在某些情况下可能是不可行相比之下，我们的要求与momentum-SGD相同。上面讨论的许多方法都执行了显式系统反演，这通常证明是非常昂贵的（39）。因此，许多工作（20; 23;42）已经试图利用通过自动微分（29; 33），执行系统反演与共轭梯度（海森自由的方法）。其他方法（4;1）为了效率而诉诸于Hessian的秩-1近似。虽然这些方法取得了一些成功，但与深度学习中的最新技术相比，它们仅在中等规模的单层模型上进行了我们推测，它们没有被广泛采用的主要原因是它们每次参数更新（34; 14）需要几个步骤（网络通道），这将使它们处于类似的缺点。一阶方法作为我们测试的无Hessian-free方法（附录B.4）。也许与我们的方法更密切相关，（27）使用自动微分来计算Hessian向量乘积以构建自适应的每个参数的学习率。最接近的方法是LiSSA（1），它是围绕用泰勒级数展开近似Hessian逆的思想构建的。这个系列可以实现为递归动量SGD是我们算法性能的一个重要因素，因为我们每个小批只需要执行一次相比之下，（1）报告内环更新的典型数量（Alg中的R2)等于样本的数量（例如，对于MNIST的测试子集，R = 10，000）。虽然这对于线性支持向量机的测试案例来说不是问题，因为每次更新只需要一个内积，但这并不适用于深度神经网络。其次，它们独立地为每个小批次反转Hessian，而我们的方法聚合了所有过去的小批次的隐式Hessian（遗忘因子为ρ）。由于批量大小的数量级小于参数（例如，256个样本与对于VGG-f的6000万个参数），在这些问题中，用于小批量的Hessian矩阵是完整数据集的Hessian的较差替代，并且严重病态。最后，虽然他们在线性模型的凸问题上表现出了更好的性能，但我们专注于在大型数据集（数百万个样本和参数）上训练深度网络的需求，在这些数据集上，以前的牛顿方法无法超越深度学习社区常用的一阶方法。6. 结论和今后的工作在这项工作中，我们提出了一个实用的二阶求解器，专门为深度学习规模的随机优化问题量身定制。我们证明我们的H−1=I+（I−H）H−1，从H−1=I开始。以来（r）（r−1）（0）优化器可以应用于一系列数据集，并达到更好的效果。LiSSA方法是一种无Hessian方法，其核心是租m类似于算法2：它也迭代地细化牛顿步长的通过一些简单的代数操作，我们可以使用泰勒递归将此更新写入形式与我们的类似：zr+1=zr−H<$ zr−J。这看起来类似于我们的基于梯度下降的更新，学习率β= 1（Alg. 1，第3-4行），有一些关键的区别。首先，他们重置每个小批量的步长估计的状态（Alg.2，第2行）。重复使用过去的解决方案，例如与具有相同迭代次数的一阶方法相比，训练误差更小，基本上没有超参数调整。在未来的工作中，我们打算通过将FMAD操作工程化到与反向传播相同的标准来对我们的方法的挂钟时间进行更多的改进，并研究最佳信任域策略以获得封闭形式的λ。致谢。我们感谢ERC StG IDIU-638009、IDIU-677195、EP/R03298 X/1、DFR 05420和EP-SRC AIMS CDT提供支持。4774引用[1] Naman Agarwal、Brian Bullins和Elad Hazan。线性时间机器学习的二阶随机优化机器学习研究杂志，18（1）：4148[2] 甘利俊一自然梯度在学习中起着有效的神经计算，10（2）：251[3] Aleksandar Botev ， Julian Hippolyt Ritter ， andDavid Barber.深度学习的实用高斯-牛顿优化。第28届机器学习国际会议（ICML-17），2017年。[4] Yair Carmon，John C Duchi，Oliver Hinder，andAaron Sidford.非凸优化的加速方法SIAM Journalon Optimization，28（2）：1751[5] Coralia Cartis，Nicholas IM Gould，and Philippe LToint. 非约束优化的自适应立方正则化方法第一部分 ： 动 机 、 收 敛 性 和 数 值 结 果 。 MathematicalProgramming，127（2）：245[6] Ken Chatfield，Karen Simonyan，Andrea Vedaldi和Andrew Zisserman。魔鬼的回归细节：深入研究卷 积 网 络 。 arXiv 预 印 本 arXiv ： 1405.3531 ，2014。[7] Andrew R Conn，Nicholas IM Gould，and Ph LToint.信赖域方法，第1卷。暹罗，2000年。[8] Yann N Dauphin ， Razvan Pascanu ， CaglarGulcehre，Kyunghyun Cho ，Surya Ganguli ，andYoshua Bengio.鞍点问题的识别与求解在高维非凸优化中。神经信息处理系统的进展，第2933-2941页，2014年[9] John Duchi，Elad Hazan，and Yoram Singer.在线学习和随机优化的自适应次梯度方法Journal ofMachine Learning Research，12（Jul）：2121[10] 尼古拉斯·弗拉马里恩和弗朗西斯·巴赫。从平均到加速，只有一个步长。在学习理论会议上，第658-695页[11] 加布里埃尔·高。为什么动量真的有效蒸馏，2017。[12] Kaiming He，Xiangyu Zhang，Shaoying Ren，andJian Sun. 用于图像识别的深度残差学习。在IEEE计算机视觉和模式识别会议论文集，第770-778页[13] Diederik P Kingma和Jimmy Ba。 Adam：随机最佳化的方法。arXiv预印本arXiv：1412.6980，2014。[14] Pang Wei Koh和Percy Liang。通过影响函数理解国际机器学习会议，第1885- 1894页[15] JonasKohler ， HadiDaneshmand ， AurelienLucchi，Ming Zhou，Klaus Neymeyr，and ThomasHofmann.从理论上理解批处理规范化。arXiv预印本arXiv：1805.10694，2018。[16] Jonas Moritz Kohler和Aurelien Lucchi。非凸优化的 子 采 样 三 次 正 则 化 arXiv 预 印 本 arXiv ：1705.05933，2017。[17] Yann LeCun，Léon Bottou，Yoshua Bengio，andPatrick Haffner.基于梯度的学习应用于文档识别。Proceedings of the IEEE，86（11）：2278[18] Laurent Lessard ， Benjamin Recht ， and AndrewPackard.积分二次约束优化算法的分析与设计SIAM Journal on Optimization，26（1）：57[19] Nicolas Loizou和Peter Richtárik。随机梯度法、牛顿法、邻近点法和子空间下降法的动量和随机动量。arXiv预印本arXiv：1712.09677，2017。[20] 詹姆斯·马滕斯通过无海森优化的深度学习。在ICML，第27卷，第735-742页[21] 詹姆斯·马滕斯关于自然梯度法的新见解和观点。2014年[22] 詹姆斯·马滕斯和罗杰·格罗斯用Kronecker因子近似曲线优化神经网络。在机器学习国际会议上，第2408-2417页https://github.com/tensorflow/kfac/.[23] James Martens和Ilya Sutskever。学习递归神经网络与无hessian优化。第28届国际机器学习会议（ICML-11）论文集，第1033-1040页。Citeseer，2011.[24] 豪尔赫·J·莫雷。Levenberg-Marquardt算法：实施和 理 论 。 在 数 值 分 析 中 ， 第 105-116 页 。Springer，1978年。[25] 尤里·内斯特罗夫凸优化导论：基础教程，第87卷。Springer Science Business Media，2013.4775[26] Yurii Nesterov和Boris T Polyak。Newton方法的三次 正 则 化 及 其 全 局 性 能 。 MathematicalProgramming，108（1）：177[27] 吉纳维芙·奥尔随机学习的动力学和算法。博士论文，计算机科学与工程系，俄勒冈研究生院，比弗顿，OR，1995。[28] Razvan Pascanu和Yooney Bengio。重新审视深层网络的自然梯度。在2013年学习表征国际会议（研讨会轨道），2013年。[29] 巴拉克·珀尔马特。快速精确乘法的黑森。神经计算，6（1