论文链接：

摘要：本篇论文旨在引见关于将最优化方法运行于机器学习的关键模型、算法、以及一些放开性疑问。这篇论文是写给有必定常识储藏的读者，尤其是那些相熟基础优化算法但是不了解机器学习的读者。首先，咱们推导出一个监视学习疑问的公式，并说明它是如何基于高低文和基本假定发生各种优化疑问。而后，咱们讨论这些优化疑问的一些清楚特色，重点讨论 logistic 回归和深层神经网络训练的案例。本文的后半部分重点引见几种优化算法，首先是凸 logistic 回归，而后讨论一阶方法，包括了随机梯度法（SGD）、方差缩减随机方法（variance reducing stochastic method）和二阶方法的经常使用。最后，咱们将讨论如何将这些方法运行于深层神经网络的训练，并着重形容这些模型的复杂非凸结构所带来的艰巨。

1 引言

在过去二十年里，机器学习这一诱人的算法畛域简直以前所未有的速度崛起。机器学习以统计学和计算机迷信为基础，以数学优化方法为外围。理想上，近来优化方法钻研畛域中的许多最新通常和实践停顿都遭到了机器学习和其它数据驱动的学科的影响。但是即使有这些咨询，统计学、计算机迷信和努力于机器学习相关疑问的优化方法钻研之间仍存在许多阻碍。因此本文试图概述机器学习学习算法而冲破这种阻碍。

本篇论文的目的是给出与机器学习畛域相关的一些关键疑问和钻研疑问的概述。思考到触及运筹学畛域的常识，咱们假定读者相熟基本的优化方法通常，但是仍将引入在狭义机器学习畛域经常使用的相关术语和概念，宿愿借此促成运筹学专家和其它奉献畛域的人员之间的沟通。为了成功这一目的，咱们在词汇表 1 中列出了本论文将引见和经常使用的最关键的术语。

1.1 说明动机1.2 学习疑问和优化疑问1.3 学习边界、过拟合和正则化

2 处置Logistic回归疑问的优化方法（浅层模型的优化方法）

当 L 和 r 是关于 w 的恣意凸函数时，可以运用在本节中讨论的方法来处置疑问（11）：

这一类中蕴含很多机器学习模型，包括允许向量机、Lasso（Least Absolute Shrinkage and Selection Operator）、稠密逆协方差选用等。无关这些模型的详细消息请参见 [86] 和其中的参考文献。为了每一步都能详细（展现进去），此处咱们指定以二分类的正则化logistic回归为例（启动解说）。为了简化例子中的符号，咱们作不失普通性的假定，令 。（此处省去了偏置项 b0），这一省略操作可以经过在输入向量上参与一维恒为 1 的特色值来补偿）。当 w 和 x 都是 d 维时就可以令其为特定的凸优化疑问。

值得一提的是，关于此类疑问，正则化项必无法少。想一想为什么说它必无法少，假定关于一切的 i ∈{1,...,n}，有参数向量 w，满足 yi(wT*xi) > 0 以及（存在）无界射线 {θw : θ > 0}。那疑问就很清朗了，在这个例子中，当 θ →∞时，

也就是说函数（式 12）无法取最小值。另一方面，经过参与（强迫）正则化函数 r，可以保证疑问（12）将具备最优解。

关于正则化函数 r，咱们将会参考罕用选用 和 r(w) = ||w||1。不过为了繁难起见，咱们通常会选用前者，由于它使得公式 12 关于每一个因子是延续可微的。相反，r(w) = ||w||1 会造成非平滑疑问，为此，（成功）函数最小化就须要更复杂的算法。

2.1 一阶方法

咱们首先讨论用一阶方法求解疑问（12），这里的」一阶」仅仅指对函数 F 中的参数启动一阶偏导的数学技巧。

2.1.1 梯度降低法

从概念上讲，最小化润滑凸指标的最繁难的方法是梯度降低法，详细剖析参见 [ 62 ]。在这种方法中，从初始化预计值 w0 开局，经过下述公式迭代地降级权重预计值。

其中 αk > 0 是一个步长参数。步长序列 {αk} 的选用间接选择此算法的性能。在优化钻研畛域，人们普遍以为，在每次迭代中驳回线性搜查来确定 {αk }，可以为处置各种类型的疑问找到一共性能优越的算法。但是，关于机器学习运行程序来说，这种运算老本高昂，由于每次函数 F 的计算都须要传递整个数据集，假设 n 过大，很或许带来高昂的（训练）老本。

好在当每个αk 都设置为一个正的常数α且它是一个足够小的固定值时，从通常上剖析，该算法的收敛性仍可以获取保证。（固定的步长常数在机器学习畛域叫做学习率。但即使不是常数，也有人把αK 或整个序列 {αK } 叫做学习率）。该算法的收敛速度取决于函数 f 是强凸函数还是弱凸函数。

用于处置 L1 范数正则化的logistic回归疑问的梯度降低和减速梯度降低拓展算法区分被称作 ISTA 和 FISTA。咱们观察到，在这种状况下，即使λ> 0，指标函数也不会是强凸函数。只要指标函数为凸时 [5]，ISTA 和 FISTA 具备与其对应的平滑函数相反的次线性收敛速度。

梯度降低在 ML 训练环节中的一个关键特性就是计算出每次迭代中求解函数 F 的梯度的运算老本。在 ML 的训练环节中，单个梯度计算的老本通常是 O（ND），这个确实可以看到，例如，在正则化项为 的状况中，函数 F 关于每一个特定的 w 的梯度是

2.1.2 随机梯度法

随机梯度法由于其用于最小化随机指标函数而在运筹学畛域广为人知，同时也是 ML 社区中的一种特色优化算法。该算法最后由 Robbins 和 Monro [ 67 ] 在处置随机方程组疑问时提出，值得留意的是，它可以用于最小化具备良好收敛性的随机指标，而且每次迭代的计算复杂度仅为 O（d）而不是 O（nd）（梯度降低中的计算复杂度）。

在每一次性迭代中，随机梯度法都会计算梯度 F（Wk）的无偏预计 GK。该预计可以以及低的代价计算获取；例如，关于公式（12），某次迭代的随机梯度可被求解为

其中 Sk 被称作小批量，它的一切元素都是从总数据集 {1,...,n} 中按平均散布选进去的。接上去的运算相似于梯度降低：

毫无不懂，该算法的关键在于选用步长序列 {αk}。不同于梯度降低，固定的步长（即学习率）不能保证算法会收敛到强凸函数 F 的最小值，而只保证收敛到最小值的邻域。

SGD 的收敛速度比梯度降低慢。尤其当函数 F 是强凸函数时，该算法只保证当 k ≥ O(1/ε) 时可以获取预期精度的解（即满足 E[F(wk)]-F(w) ≤ ε的解），而当函数 F 仅仅是凸函数时，只要在 k ≥ O(1/ε^2) [11] 时才干保证得出上述解。

另一方面，正如前文提及的，假设 Sk 的大小由一个常数限定（独立于 n 或 k 的常数），那么 SGD 的每次的迭代老本都比梯度降低法小 0（n）倍。

但是，在实践运用中，规范的 SGD 并不必定是处置机器学习中优化疑问的最有效方法。理想上，机器学习和优化算法畛域在开发改良或代替 SGD 方面启动了少量的踊跃钻研。在随后的两部分中，咱们将讨论两类方法：方差缩减法和二阶方法。但是在这两类方法以外，还有多种方法。例如，加有动量的 SGD 就是一个通常中被发现的性能好于好于规范 SGD 的拓展版 SGD。见下图算法 1

2.1.3 方差缩减法（Variance reducing method）

思考到疑问（11），人们发现经过应用指标 F 的结构作为 n 个函数的有限和再加上繁难的凸函数项，可以改善 SGD 方法。目前曾经钻研出几种方法，如 SAG [74]，SAGA [22]，SDCA [76] 和 SVRG [44]。

为了繁难援用，咱们把 SVRG 叫做算法 2。该算法在每个外部迭代中口头一次性完整的梯度计算，而后沿着随机方向再迭代 L 步，这是整个梯度的随机修正环节。内环步长 L（inner loop size）必需满足必定的条件以保证收敛 [ 44 ]。

SVRG，全称为随机方差减小梯度，其称号源自于该算法可以被视为 SGD 的方差减小变体（尤其是有限和最小化/finite-sum minimization）。

钻研员经过联合 SVRG 和 SAGA 的一些思维，提出一个新的方法，叫做 SARAH。仅是内层迭代步长不同于 SVRG，SARAH 的公式如下

该变动造成 ，使得 SARAH 中的步长不基于无偏梯度预计。不过，相关于 SVRG，它取得了改良的收敛特性。

表 2 ： 最小化强凸函数的一阶方法计算复杂度

表 3 ： 最小化普通凸函数的一阶方法计算复杂度

2.2 二阶方法和拟牛顿法

受确定性优化钻研畛域几十年钻研成绩的处罚，ML 优化中最生动的钻研畛域之一就是关于如何经常使用二阶导数（即曲率）消息来减速训练。

可怜的是，当 n 或 d 很大时，在机器学习运行程序中，海塞矩阵（Hessian matrix）的计算和存储变得十分低廉。

另一类基于形如（21）模型的算法是拟牛顿方法：

幽默的是，这些方法没有计算出显式二阶导数，而是经过在每次迭代中运行低秩降级结构齐全由一阶导数的海塞近似矩阵。例如，让咱们简明引见最盛行的拟牛顿算法，全称为 Broyden-Fletcher-Goldfarb-Shanno（BFGS）方法。在这种方法中，咱们首先可以看到（21）的最小值为、 进一步发现它实践上可以繁难地计算出逆 Hessian 近似。由于 随着步长 sk = w_k+1 − wk 和位移 yk = ∇F(wk+1) − ∇F(wk) 的移动，有人选用 以最小化 以满足割线方程 sk = (B^-1)yk。经常使用精心挑选的规范表白，这个疑问的解析式可以显示的写成

其中 之间的差异可以仅示意为二阶矩阵。

为繁难援用，完整的经典 BFGS 算法被称为算法 3。

即使驳回二阶消息，随机优化方法（无差异缩小）也无法到达比次线性更快的收敛速度。不过，经常使用二阶消息是一个不错的想法，由于假设海塞近似矩阵收敛于海塞矩阵的实在解，则可以缩小收敛速度中的常数，同时还可以缩小病态（ill-conditioning）的影响。

可怜的是，虽然曾经观察到了实践的效率优化，但无通常上还没有一个真正的二阶方法，可以成功这样的优化。到目前为止，只需海塞（近似）矩阵坚持良好特性，大少数实践的方法只能保证明现 SGD 的收敛（速率）特性。例如，假设序列 {Bk}（不必定由 BFGS 更重生成）对一切 k 满足：

此时 具备与 SGD 相反的收敛速度属性。咱们就 可以正当地假定这些限定实用于上述讨论的方法，这些假定有适当的保证。但是，在拟牛顿方法的背景下应该小心，其中随机梯度预计或许与海塞近似相关。

3 深度学习

沿着这些方向启动的关键停顿包括深层神经网络（DNN）的运用。机器学习的一个相应的分支称为深度学习（或分层学习），它代表了一类试图经过经常使用蕴含延续线性和非线性变换的多档次深层图来结构数据中上档次笼统的算法 [6, 51, 73, 37, 38, 23]。近年来迷信家们曾经钻研了各种神经网络类型，包括全衔接神经网络（FNN）[84,28]，卷积神经网络（CNN）[50] 和循环神经网络（RNN）[41,57,52]。关于咱们来说，将关键关注前两类神经网络，同时留意其它网络。

3.1 疑问公式化3.2 随机梯度降低法

咱们援用以下内容来强调将优化算法运行于训练 DNN 的令人困惑的反响。首先，例如在 [11] 中，有一个论断标明，经过运行 SGD 来最小化非凸指标函数（不时从输入×输入空间绘制），可以保证预期梯度危险将隐没，至少在一个子序列上是这样，即： 。这一论断令人欣喜，这标明 SGD 可以成功与其他最先进的基于梯度的优化算法相似的收敛保证。但是，虽然文献中的种种保证是有局限性的; 毕竟，虽然许多基于梯度的优化算法确保指标函数干燥缩小，但 SG 并不以这种方式计算。因此，假设一个子序列收敛到一个固定点，那么咱们怎样能确定该点不是鞍点，或许是有误差部分最小值，亦或是一些指标值比初始点差的最大值？理想上，咱们并不能必需。也就是说，SGD 方法通常长于找到部分极小值，而不是全局最小值。另一方面，SGD 往往会在固定值左近减缓收敛速度，这或许会阻碍它在深度神经网络中开展。

普通来说，关于非凸疑问，SGD 的收敛速度记载在 [29,30]，但是它们十分有限，特意是它们不实用于§1.3 中的讨论。因此，咱们不能以雷同的方式争执 SGD 是机器学习中非凸优化疑问的最佳方法。此外，下式

中的学习界限是没有用的，由于关于许多 DNN 和 CNN，由神经网络发生的分类的复杂度 C 比训练样本数 n 大得多。理想上，在 [90] 中，阅历标明，只要这些汇合中的数据随机扰动，神经网络才干随便地超越典型的数据集类型。

3.3 海塞-自在优化方法（Hessian-free method）

有钻研者发现咱们可以修正 DNN 的反向流传算法来计算这样的海塞-矢量乘积，由于它们可以被看作是方导游数 [65]。计算这种乘积的复杂度只是比计算梯度多一个常数因子。所获取的类的方法通常被称为海塞-自在优化方法，由于当访问和经常使用 Hessian 消息时，没有显式地存储 Hessian 矩阵。

由于指标函数的非凸性，在 DNN 的状况中发生了其它的疑问，真正的海塞矩阵或许不是正定矩阵。普通来说，在确定性优化中，处置这个疑问的两种或许的方法是修正海森矩阵和运用置信域（trust region）方法。这两种方法都在训练 DNN 的状况中讨论过，例如，在 [54,55] 中，提出了一种高斯牛顿法，其在（11）中函数 F 的 Hessian 的公式中的第一项近似于 Hessian 矩阵（省略了正则化项）

其中 是关于第一个参数的损失函数 l(·, ·) 的海塞矩阵，∇p(w, xi) 是 dy-维函数 p(w, x) 关于权重 w 的雅可比式，∇^2 [pj (w, xi)] for all j ∈ {1, . . . , dy} 是关于 w 的按元素运算的海塞矩阵。

3.4 子采样海森方法（Subsampled Hessian method）

最近，在一系列论文（3, 15, 34）中，钻研员们应用一个很普通的随机模型框架，对凸区域和非凸情景下的置信域、线搜查和自顺应三次正则化方法启动了剖析。在这项上班中，它标明，只需梯度和 Hessian 预计是足够准确的一些正概率，经常使用随机不准确梯度和 Hessian 消息的规范优化方法就可以保管其收敛速度。

在机器学习和采样 Hessian 和梯度的状况下，结果只需求| SK |必需选用足够大的相关于该算法采取的步骤的长度。例如，在 [ 3, 34 ]，| SK |大小与置信域半径的相关。须要留意的是，关于采样的海塞矩阵，其对样本集的大小要求比采样的梯度要高得多，因此允许经常使用准确梯度的海塞预计的思维催生了弱小的算法，它领有弱小通常撑持和良好的通常高效性。