论文链接：https://arxiv.org/abs/1706.10207摘要：本文旨在介绍将优化方法应用于机器学习的关键模型、算法、和一些未解决的问题。本文面向有一定知识储备的读者，尤其是熟悉基本优化算法但不了解机器学习的读者。首先，我们推导出一个监督学习问题的公式，并展示它如何根据上下文和基本假设产生各种优化问题。然后我们讨论这些优化问题的一些显着特征，重点关注逻辑回归和深度神经网络训练的情况。本文的后半部分重点介绍几种优化算法，从凸逻辑回归开始，然后讨论一阶方法，包括使用随机梯度法(SGD)、减少方差的随机方法和二阶方法。最后，我们讨论了如何将这些方法应用于深度神经网络的训练，重点是描述这些模型的复杂非凸结构所带来的困难。1简介在过去的二十年里，引人入胜的机器学习算法领域以几乎前所未有的速度发展。机器学习以统计学和计算机科学为基础，以数学优化方法为核心。事实上，优化方法研究领域的许多最新理论和实践进展都受到了机器学习和其他数据驱动学科的影响。然而，即使有这些联系，统计学、计算机科学和专门针对机器学习相关问题的优化方法研究之间仍然存在许多障碍。因此，本文试图通过概述机器学习算法来打破这一障碍。本文的目的是概述与机器学习领域相关的一些关键问题和研究问题。考虑到运筹学领域涉及的知识，我们假设读者熟悉优化方法的基本理论，但仍会介绍广义上机器学习领域中使用的相关术语和概念。沟通。为实现这一点，我们在词汇表1中列出了本文将介绍和使用的最重要的术语。1.1明确动机1.2学习问题和优化问题1.3学习边界、过拟合和正则化2解决Logistic回归问题的优化方法（浅层模型的优化方法）当L和r是关于w的任意凸函数时，可以使用本节讨论的方法解决问题（11）：这一类包括很多机器学习模型，包括支持向量机、Lasso（LeastAbsoluteShrinkageandSelectionOperator）、稀疏逆协方差选择等。有关这些模型的详细信息，请参见[86]及其中的参考资料。为了在每个步骤中具体（展示），这里我们指定两个分类的正则化逻辑回归作为例子（解释）。为了简化示例中的符号，我们做出不失一般性的假设，令。（这里省略了偏置项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范数正则化逻辑回归问题的梯度下降和加速梯度下降扩展算法分别称为ISTA和FISTA。我们观察到，在这种情况下，即使λ>0，目标函数也不会是强凸的。ISTA和FISTA仅在目标函数为凸函数时才具有与其光滑对应物相同的次线性收敛速度[5]。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。见下图算法12.1.3方差缩减法（Variancereducingmethod）考虑问题（11），发现可以通过将目标F的结构作为n个函数加a的有限和来改进SGD方法简单的凸函数项。已经研究了几种方法，例如SAG[74]、SAGA[22]、SDCA[76]和SVRG[44]。为了便于参考，我们将SVRG称为算法2。该算法在每次外层迭代中进行一次全梯度计算，然后在随机方向上迭代L步，这是对整个梯度的随机修正。内环步长L（innerloopsize）必须满足一定的条件才能保证收敛[44]。SVRG是StochasticVarianceReducingGradient的缩写，它的名字来源于这样一个事实，即该算法可以被视为SGD（特别是有限和最小化）的方差减少变体。研究人员结合了SVRG和SAGA的一些思想，提出了一种称为SARAH的新方法。仅内层迭代步长与SVRG不同，SARAH公式如下。这种变化导致SARAH中的步长不是基于无偏梯度估计。然而，相对于SVRG，它??获得了改进的收敛特性。表2：最小化强凸函数的一阶方法的计算复杂度表3：最小化一般凸函数的一阶方法的计算复杂度动机，ML优化中最活跃的研究领域之一是关于如何使用二阶导数（即曲率）信息以加速训练。不幸的是，当n或d很大时，Hessian矩阵在机器学习应用程序中的计算和存储变得非常昂贵。另一类基于形式(21)模型的算法是拟牛顿法：有趣的是，这些方法不计算显式二阶导数，而是通过在每次迭代中应用低秩更新来构建一整套一阶导数的Hessian近似矩阵。作为一个例子，让我们简单介绍一下最流行的拟牛顿算法，即Broyden-Fletcher-Goldfarb-Shanno(BFGS)方法。在这种方法中，我们首先可以看到（21）有一个最小值，并进一步发现它实际上可以方便地计算逆Hessian近似值。由于以步长sk=w_k+1?wk和位移yk=?F(wk+1)??F(wk)移动，因此选择最小化以满足割线方程sk=(B^-1)yk。使用精心选择的规范表达式，可以明确地写出这个问题的解析公式，其中之间的差异只能表示为二阶矩阵。为便于参考，完整的经典BFGS算法称为算法3。即使具有二阶信息，随机优化方法（无差异缩减）也无法实现比次线性更快的收敛。然而，使用二阶信息是个好主意，因为如果Hessian近似收敛到Hessian的真解，它会降低收敛速度中的常数，同时也会降低病态条件的影响。不幸的是，虽然已经观察到实际的效率增益，但理论上没有真正的二阶方法可以实现这种增益。到目前为止，只要Hessian（近似）矩阵保持良好行为，大多数实用方法只能保证实现SGD的收敛（速率）特性。例如，如果序列{Bk}（不一定由BFGS更新生成）满足所有k：这与SGD具有相同的收敛率属性。然后我们可以合理地假设这些限制适用于上面讨论的方法，并为这些假设提供适当的保障。然而，在拟牛顿方法的背景下应该小心，其中随机梯度估计可能与Hessian近似有关。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.3Hessian-free优化方法（Hessian-freemethod）一些研究人员发现我们可以修改DNN的反向传播算法来计算这种Hessian-vector乘积，因为它们可以被视为方向导数[65]。计算这种产品的复杂性只是比计算梯度更多的常数因素。结果类的方法通常被称为Hessian-free优化方法，因为在访问和使用Hessian信息时没有显式存储Hessian矩阵。由于目标函数的非凸性质，在DNN的情况下会出现其他问题，并且真正的Hessian矩阵可能不是正定的。通常，在确定性优化中，两种可能的方法来处理这个问题是修改Hessian矩阵和使用信赖域方法。这两种方法都在训练DNN的背景下进行了探索，例如在[54,55]中，提出了一种高斯-牛顿方法，该方法近似于函数F的Hessian公式中的第一项(11)在Hessian矩阵中（省略正则化项）其中是损失的Hessian矩阵函数l(,)相对于第一个参数，?p(w,xi)是dy维函数p(w,x)forTheJacobianofweightsw,?^2[pj(w,xi)]for所有j∈{1,...,dy}是关于w的逐元素Hessian矩阵。3.4SubsampledHessian方法（SubsampledHessianmethod）最近，在一系列论文（3,15,34）中，研究人员对使用非常通用的随机建模搜索和自适应三次正则化方法进行了分析。在这项工作中，表明只要梯度和Hessian估计足够准确且具有一定的正概率，使用随机不精确梯度和Hessian信息的标准优化方法就会保持其收敛速度。在机器学习和采样Hessians和梯度的情况下，事实证明|SK|相对于算法所采用的步长，必须选择足够大的值。例如，在[3,34]中，|SK|大小与置信区域的半径有关。需要注意的是，对于采样的Hessian矩阵，样本集的大小远大于采样梯度的大小，所以用精确梯度支持Hessian估计的想法催生了一个强大的算法，它有强大的理论支撑和良好的实践效率。
