机器学习中的随机优化算法计算机专业

1、摘要对于机器学习中的数值优化问题，考虑到其规模和维数都比较大，传统的方法难以高效的解决这一问题。近些年来，针对大规模的机器学习问题做了很多研究，比较重要的一类方法是 随机算法。优化方法主要分为一阶梯度方法和二阶牛顿方法两大类，针对一阶方法的改进和研究比较成熟和完善，一阶方法又可以分为两类，原始方法和对偶方法，原始方法比较有代表性的有SAG、SAGA、SVRG，对偶方法有SDCA和SPDC两种。此外，加速方法如Catalyst、Katyusha，其收敛速度为一阶方法所能达到的最好结果。二阶方法目前是机器学习领域研究的重要方向，其收敛速度要优于一阶方法，但是其实践中会有一些难度，比较实用的是L-B

2、FGS方法及其随机算法的改进。本文将详细全面的叙述机器学习中各种随机算法，介绍随机算法的发展历程，研究方向及研究热点，最后通过数值试验比较了几种常见随机算法，以给读者直观的数值效果。 关键词：大规模机器学习，随机算法，优化方法1 I Stochastic Optimization Algorithm in Machine LearningAbstractFor the optimization problem in machine learning field, traditional method have difficulties in solving the high dimension

3、 and big data problem . In recent years, there are many researches in large scale machine learning problems, especially stochastic algorithms. Generally, stochastic method can divided into two parts. One is first-order gradient method and the other is second- order Newton method. There is more impro

4、vement and research in first order method , and the first order method is more mature and perfect. There is two classes for first order method. For the primal class, SVRG,SAG,SAGA is the representation , and SDCA ,SPDC for dual class. Otherwise , the acceleration method such as catalyst and katyusha

5、, which has the optimal con- vergence speed for first order method, is put forward in last two years. Second order method is one important research area , and it has better convergence but not better performance because it has to compute the hessian matrix , one useful method is L-BFGS and its varia

6、nts.In this paper, the author will introduce stochastic algorithms in machine learning area in detail. In the end , numerical experiments compare some common algorithm and give a direct view to readers. Key Words:Large-scale machine learning problem,Stochastic algorithm,Optimization method2 II 目录摘要.

7、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .IAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8、. . . . . . . . . . .II引言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11 基础知识 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9、. . . . . . . . . . . . . . . . . . .52 一阶方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62.1 梯度下降法（Gradient Descent） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10、 . . . . . . .62.2 随机梯度方法（Stochastic Gradient Method） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.3 方差减小方法（Variance Reduction Method) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102.3.1随机平均梯度方法(StochasticAverage Gradient). . . . . . . . . . . . . . .

11、. . . . . . . . . . .112.3.2 随机方差减小梯度方法(Stochastic Variance Reduction Gradient). . . . . . . . . .122.3.3 SAGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .132.4 随机对偶坐标上升法（Stochastic Dual Coordinate Ascent） . . .

12、 . . . . . . . . . . . . . . . .142.5 随机原始对偶坐标法（Stochastic Primal Dual Coordinate）. . . . . . . . . . . . . . . . . . . .162.6 加速方法Catalyst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192.7 Katyusha . . . . . . . . . . .

13、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203 二阶方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .223.1 牛顿法与拟牛顿法 . . . . .

14、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .223.1.1 SR1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .233.1.2 BFGS、DFP . . . . . . . . . . . .

15、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .233.2 Limited-memory-BFGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .243.3 随机牛顿方法 . . . . . . . . . . . . . . . . . . . . . . . . . . .

16、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .254 数值实验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27参考文献. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29致谢. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .314 III 引言近些年来，随着科学技术不断地进步发展，尤其是在计算机、通信等领域的进步以

18、及互联网不断的普及。人们产生数据速率大大提高的同时又能够容易廉价地获取和存储数据。数据中蕴含是大量信息，但是如何在大量数据中发掘出有效的信息是一个很困难的问题。为了解决该问题，人们尝试采用各种方式。其中，比较好的处理方式是使用机器学习、数理统计的方法。机器学习利用数据建立模型来进行预测，其中常见的方法是将问题转化成一个优化模型，进而求解一个目标函数来。然而在大数据时代，数据的数量和数据的维数都比较高，如何更有效的处理和挖掘大数据，不仅要不断的改进和发展计算机硬件，也要不断的去改进机器学习算法的效率。提高机器学习算方法的效率更多的依赖于对数值优化算法的改进，因此有必要对大规模机器学习中的优化算法

19、进行总结。本文力求详细全面地对现有的机器学习中的优化方法做一概述，也是对自己最近学习的一个总结。给定一个训练数据集T = (x1, y1), (x2, y2), . . . , (xN, yN)，机器学习的策略是求经验风险最小损失的模型，常见的经验风险损失模型为65=min F(x) + g(x)1 nfi(x)xdn i=1其中， fi(x) : d 是一个凸的光滑损失函数, fi与样本密切相关，n代表着样本的个数。然而，当样本容量很小时，容易产生“过拟合”现象，为了防止过拟合。常在经验风险上加上表示模型复杂度的正则化项或惩罚项，称为结构风险损失函数。=min F(x) + g(x)1 nf

20、i(x) + g(x)xdn i=1其中， fi(x) : d 是一个凸的光滑损失函数, fi与样本密切相关，n代表着样本的个数。g(x) : d 是正则化函数，通常也是一个凸函数。这种形式的问题在机器学习中有着很广的应用，许多机器学习方法可以归结成求如上形式的优化问题：线性支持向量机可以转化成求一些的优化问题123:=min P(x)1 n1 bi(aT x) +x2xn i=1i+2其中，a+ = max0, a 逻辑回归是归结为解决下述的优化问题23：min P(x)1 n log(1 + ebiaT x) + x2x= ni=1i22LASSO可以转化成求解以下优化问题23：min P

21、(x) = 1 n(ai x bi)2 + 1 x2x2ni=121解决这一问题的难点在于，当优化变量的维数d和样本的个数n比较大时，求解这 一问题需要非常大的计算量和存储内存。对于这种大规模的优化问题，比较常见的方 法可以分为批处理方法和随机算法。批处理方法主要包括全梯度下降方法和拟牛顿L-BFGS方法，随机方法主要有随机梯度下降法（SGD）以及这种算法的改进，比如随机方差下降梯度方法(SVRG)、随机平均梯度方法(SAG);随机对偶坐标上升法（SDCA），随机原始对偶坐标方法（SPDC）。梯度下降法是一种线搜索方法4，每一次迭代选择该点的负梯度方向作为搜索方 向，因为负梯度方向是最快的下降

22、方向，因此亦被称为最速下降法，它仅利用了函数的梯度信息，因此也被称为一阶方法。梯度方法每次迭代的方向为其负梯度方向，xk 1 = xk kgk = xk k n fi(xk)+ni=1它的收敛速度为O(1/n),是一种次线性的迭代算法。一种加速的梯度算法AGD45形如：xk+1 = xk + (xk xk1) k f (xk + (xk xk1)它的收敛速度为O(1/n2),但当目标函数是强凸函数时，其收敛速度为线性收敛速度。梯度下降方法需要需要计算n个梯度，这一计算量为O(nd),当n和d很大时，这一计算 量和存储空间是很大的。一个更实用的改进是每一次迭代时，随机选择一个点计算梯度来进行更新

23、,SGD形式如67：xk+1 = xk k fik (xk)ni=1并且需要满足E fik (xk)|xk1 = 1 n fi(xk)。这一改进的好处是，每一个次迭代其计算n量是标准梯度下降法的1 。对于随机梯度下降法(SGD),其随机向量g(xk, k)是函数全梯度的无偏估计，因此其满足 EF(x) g(x , ) f (x ) (2L 222 * L/2) F(x ) +Eg(x , ) F(x )k+1kkkkkkk22kkk上式不等号右边的第二项是我们预期的误差，第三项我们称之为方差，因为方差的存在，所以SGD也需要采用变步长的方式才能保证算法的收敛。方差的存在导致了算法性能上的不足，

24、因此如果我们能够改进算法使得方差不断的减小直至零。比较有代表性的方差减小方法有三种，分别称为SVRG8，SAG910，SAGA11，这三种方法的更 新方式如下：f (xk) f (k)1jxk 1 = xk jj +n f (k)(S AG)+nni=1 iixk 1 = xk f (xk) f (k)1 n f (k)(S AGA)+jjj + n i=1 iixk 1 = xk f (xk) f (x) +1 nf (x)(S VRG)+jj n i=1 i SAG9是最早提出的具有线性收敛速度的随机梯度方法，其每次更新不依赖于n。SAGA可以看成是结合SAG和SVRG两种方法的技巧提出的

25、新的算法，它与SVRG的收敛速度相近，并适用于非强凸的问题。SVRG有着良好的性质，并且适用于非凸函数。另外一类比较实用的方法是随机对偶方法，主要有SDCA12和SPDC13，SDCA是 将原始问题转化为其对偶形式，采用随机坐标的思想，随机选择对偶坐标不断求极大直到最优值，SPDC 是将其原问题转化为鞍点问题，通过交替最小化原始变量和最大化对偶变量来求鞍点，在正文中将继续介绍着两种方法。牛顿方法14是利用函数二阶信息的一种优化方法，现实中我们常常使用一种近似 的牛顿方法，拟牛顿法，在机器学习领域中，比较常用的是L-BFGS拟牛顿方法，这一 方法在最优值附近可以达到次线性的收敛速度。其迭代格式为

26、：xk+1 = xk kHkFk其中，k是步长，Hk是Hessian阵的逆的一种近似。更新的方式为：Hk+1 = VT HkVk + kyk sTkkkyT skk其中k = 1 , Vk = I kyk sT .sk = xk+1 xk, yk = fk+1 fk。因为二阶方法在计算中复杂度比较高，对二阶方法的改进存在一定的难度，因此关于二阶的随机方法的工作还比较有限，我们将在正文介绍几种改进的算法。 接下来第一章我将介绍相关的数学知识背景，第二章我将分别对一阶算法进行介绍，第三章我将对二阶算法的做一介绍，第四章我将通过一些实验来对比不同的优化算法。1基础知识定义 1 L-Lipshistz

27、连续 称函数f : d 为L-Lipschitz连续函数， L > 0 ， 如果对于a, b d，均有| f (a) f (b)| L|a b|定义 2 光滑称函数f : d 为光滑函数， > 0，如果对于任意a, b d，均有2f (b) f (a) + f (a), T (b a) + b a2定义 3 凸函数 称函数f : d 为凸函数，如果对于任意a, b d，均有f (b) f (a) + f (a), T (b a)定义 4 µ强凸函数 称连续可微的函数f : d 为µ强凸函数，µ > 0，如果对于任意a, b d，均有2f (b)

28、f (a) + f (a), T (b a) + µb a2定义 5 条件数 如果连续可微的函数f : d 为光滑函数，µ强凸函数，记 =µ称为原函数的条件数。定义 6 最小值点 点x*称之为局部最小值点，如果存在x*的领域N，使得对任意x N均有f (x) f (x*) 点x*称之为严格最小值点（强最小值点），如果存在x*的领域N，使得对任意x N且x Ç x*，均有f (x) > f (x*)定理 1 一阶必要性条件如果x*是最小值点，并且函数f 在x*的一个开领域是连续可微的，那么有 f (x*) = 0。定理 2 如果函数f 是凸函数，那么

29、任意局部最小值点均为全局最小值点。此外，当函数是可微时，任何x满足 f (x) = 0的点均为全局最小值点。2一阶方法2.1 梯度下降法（Gradient Descent）梯度下降法是一种线搜索方法，每一次迭代选择该点的负梯度方向作为搜索方向， 因为负梯度方向是最快的下降方向，因此亦被称为最速下降法，它仅利用了函数的梯度信息，因此也被称为一阶方法。它的形式非常的直观简单，在每一次迭代选择负梯度方向作为其下降方向，其更新形式如下：xk 1 = xk kgk = xk k n fi(xk)+ni=1其中，k是步长或学习率，它可由一些准则确定，比如Wolfe准则、Armijo准则等。L当函数F是凸函

30、数，并且其梯度是L Lipshitz函数时，取 = 1 时，它的收敛速度可以达到O(1/k)5，f (xk) f (x*) 2L x0 x* 22k + 4进一步，当F是µ强凸，并且其梯度是L lipshitz函数时，其收敛速度为线性收敛5：f (xk) f (x*) L ( L µ)2k x0 x* 22 L + µNesterov证明了一阶方法的理论最优下界45，并且采用了一种加速的方法对梯度下降算法进行了改进，称之为Nesterov加速，称这一算法为加速梯度下降算法（AGD）。一种常用的AGD 迭代方式如下：xk+1 = yk k f (yk)yk+1 =

31、xk+1 + (xk+1 xk)L当函数F是凸函数，并且其梯度是L Lipshitz函数时,如果k =22µ)速度为1 、 =L µL+ µ 其收敛L(2zzzzzzzf (xk) f (x*) min(1 µ)k,4L L + k * f (x0) f (x*) + µ x0 x* 2上述收敛速度对于非强凸函数和强凸函数都是适合的，当函数为非强凸时，取µ=0。通 过迭代格式，可以看出，在其迭代时，仅涉及到向量的加减以及数乘运算，因此其每一次迭代的计算复杂度为O(nd)。然而，在每一步，梯度下降方法需要需要计算n个梯度，其计算量为O(

32、nd),当n和d很 大时，这一计算量和存储空间是很大的。因此，如何改进梯度算法，使得其适用于大规模的机器学习优化问题，特别是在数据爆炸的今天，成为一个很有意义的问题。然而，在每一步，梯度下降方法需要需要计算n个梯度，其计算量为O(nd),当n和d很 大时，这一计算量和存储空间是很大的。因此，如何改进梯度算法，使得其适用于大规模的机器学习优化问题，特别是在数据爆炸的今天，成为一个很有意义的问题。一种比较常见的方法是确定性提升梯度方法(deterministic incremental gradient0method)15，称之为IG。IG方法和标准的梯度下降方法非常相似，对于n个函数和的形式的目

33、标函数，其主要区别是IG方法使变量沿着其中一个函数的梯度方向循环更新。 具体的可以看成是一个有着两层循环的算法，每一次外层迭代可以看成是一个m次内层迭代的循环。令初始点为x0 n，对于任意k > 0，更新方式为x(k) = x(k) k fi(x)(k)ii1其中k > 0，代表着步长，x(k+1) = xk 。i10nIG方法的性能取决于内循环中迭代顺序，如果对于某些具体问题，如果存在一些已 知的信息，并能确定出一个迭代顺序(1, . . . , n 的一个排列)，那么IG方法则有很好的性能。x(k) = x(k) k f(x(k) )ii1(i)i1然而，在现实当中先验信息是很

34、难获得的，我们更倾向于采用随机采样的方法来更新。这一方法被称为随机梯度方法(stochastic gradient method)，或者称为Robbins-Monro7 算法。2.2 随机梯度方法（Stochastic Gradient Method）随机梯度方法(SG)迭代的过程并不由目标函数，初始点，步长等因素唯一决定，其过程也是随机的，这不同于标准的梯度方法，每一次迭代，其根据某分布随机选择 一个样本点来更新目标变量。其中一种SG方法为随机梯度下降算法(stochastic gradientdescent)，SGD并不能保证目标函数在每相邻两次迭代都一定下降，只是期望意义上的下降算法67

35、：x(k+1) = x(k) k fik (x(k)ni=1且满足E fik (x(k) = 1 n fi(x(k) = F(x(k)。n每一轮迭代的计算量是标准梯度法的1 ，仅为O(d)，但是其步长要不断的减小才能保证目标函数能收敛到最优值点。我们将从理论对SG做进一步认识，这是一些已知的 结论16,我们考虑更一般的形式(SG)，如算法1。Algorithm 1 SG选择初始点x1for t=1,2,. . . ,m do生成一个随机变量k 计算随机向量g(xk, k) 确定步长k更新： xK+1 = xKkg(xk, k) end for引理 1 如果函数F(x)是L-光滑函数，那么算法1

36、满足如下的不等式，对于任意的k N：Ek F(xk+1) F(xk) kF(xk)T Eg(xk, k) + 1 2LE g(xk, k) 2k2 kk2假设 1 目标函数和SG(算法1)满足如下条件:(1) 函数F是下有界的，并且序列xk在一个开集中(2) 存在µG µ > 0，使得对于任意k NF(xk)T E g(xk, k) µ F(xk) 2k2 Ek g(xk, k) 2 µG F(xk) 2(3) 存在M 0和Mv 0，使得对于任意k Nk2V g(xk, sk) M + Mv F(xk) 2引理 2 如果函数F(x)是L-Lipsc

37、hitz函数并且满足假设1，那么对任意k N满足如下不等式:E F(x1+) F(x ) F(x )T E g(x , )2 LE g(x , ) 2kk+1kkkkkk2 kkkk2 (µ 1 kLMG)k F(xk) 21 2 LM22 + 2 k定理 3 如果函数F是L-Lipschitz连续函数，µ强凸函数，假设算法1中步长固定，即对任意k N均有k = 且 µG0 < < LM则对任意k N有如下的不等式：EF(xk) F(x*) LM + (1 cµ)k1(F(x1) F(x*) LM )2Cµ kLM 2Cµ

38、2cµ由上述定理可以得知，如果步长是固定时，那么算法最终仅能收敛到最优值点的邻域附近的次优点，因此可以通过不断减小步长来保证算法收敛到最优值点，这可有以下定理在理论上得以保证。定理 4 如果函数F是L-Lipschitz连续函数，µ强凸函数，假设算法1中步长采用如下序列更新： k = + k其中 > 1 并且 > 0使得1 µ cµ则对任意k N有：LMG v EF(xk) F(x*) + k其中v :2LM*= max 2cµ 1), ( + 1)(F(x1) f (x )对于随机梯度下降法(SGD),其随机向量g(xk, k)是

39、函数全梯度的无偏估计， 也即满足F(xk) = Eg(xk, k)。因此其满足EF(x) g(x , ) f (x ) (2L * L/2) F(x ) +Eg(x , ) F(x )k+1kkkkkkk22kkk 222上式不等号右边的第二项是我们预期的误差，第三项我们称之为方差，因为方差的存在，所以SGD也需要采用变步长的方式才能保证算法的收敛。方差的存在导致了算法性能上的欠缺，如果我们能够改进算法使得方差不断的减小直至零，便能够提升算法的性能，在下一节中我们将介绍三种这样的方法。随机梯度方法相比于标准梯度方法更加有效地利用了数据，标准梯度方法每一次更新目标变量需要用到所有的样本，但是在实

40、际问题中，数据会存在这一定的冗余，因此，每次用到全体数据的一部分也能产生很好的效果，并且其效率会更高。通过实验可以得知，随机梯度方法在刚开始下降的比较剧烈，会很快达到一定精度的次优解。再 者，如果忽略通信时间，标准梯度方法的收敛速度为O(nlog(1/s)(因为每次迭代需要计 算n个梯度)，而虽然SGD 的收敛速度为O(1/T )，但是其每次只计算一个梯度，因此其收敛速度为1/s，当n很大时，并且在实际中计算时间和精度要求有限时，SGD并不比标准梯度的效果差。2.3 方差减小方法（Variance Reduction Method)方差的存在是使得随机梯度方法性能欠缺的一个主要原因，通过减小方

41、差来提升算法的性能是一个很好的想法。首先给出一种方差减小的观点11，假设用蒙特卡洛采样 的方法去更新EX，如果能够高效的计算出EY，并且Y与X 有着密切的关系，那么可以不断用 来不断逼近Y。其中 = (X Y) + EY，那么E 是EX 和EY 的凸组合， 的方差为Var() = 2Var(X) + Var(Y) 2Cov(X, Y)。如果取 = 1，那么 是X 的无偏估计。有三种比较经典的方法可以看成是采用这一思想来改进SGD，分别是SAG(随机平 均梯度方法),SVRG(随机方差减小方法)和SAGA。j对于SAGA11和SAG910， X是随机梯度方法(SGD)的方向采样f (xk),Y可

42、以看做是f (k)。在SAGA中， = 1，而在SAG 中 = 1 ，SAG的方差是SAGA的 1 ，但jjnn2是SAGA的估计是无偏估计。SVRG8采用的是Y = f (x)，并且它分为了内外两层循环。这三种方法的更新方式如下：j f (xk) f (k)1jxk 1 = xk jj +n f (k)(S AG)+nni=1 iixk 1 = xk f (xk) f (k)1 n f (k)(S AGA)+jjj + n i=1 iixk 1 = xk f (xk) f (x) +1 nf (x)(S VRG)+jj n i=1 i SAG9是最早提出的具有线性收敛速度的随机梯度方法，其每

43、次更新不依赖于n。SAGA 可以看成是结合SAG和SVRG两种方法的技巧提出的新的算法，它与SVRG的收敛速度相近，并适用于非强凸的问题。SVRG 有着良好的性质，并且适用于非凸函数，近几年来，关于SVRG的研究不断进行，得到不断发展。接下来将分别介绍三种方法。2.3.1 随机平均梯度方法(Stochastic Average Gradient)SAG910可以看成是IAG17的一种随机版本，类似于是随机梯度方法，每一次迭代仅需要一个样本点来计算方向向量，并且每次迭代的向量方向是全梯度的有偏估计， 但是它的收敛速度是线性的。SAG的迭代格式如下：xk 1 = xk k n yk+ni=1 i其

44、中yk = f (xk)如果i = ik，ik是随机选取的指标，否则yk保持不变。iiiikSAG方法相比于SGD有着很明显的优点，它可以采用固定步长进行更新，并且有 着更快的收敛性质，线性收敛速度。但是它需要存储n个梯度，当n和d 很大时，其存储量为O(nd)，其存储量是十分巨大的，但是对于某些特殊的函数，比如带有线性预测形式的函数fi(aT x)，其存储量大大减小，只需要O(d)。如果初始梯度选择的是零向量，也即yi = 0，那么在算法迭代的初始可以将步长调为1 直至更新此处k = n，这样的调整可以提高收敛的速度。SAG的算法如下10：当取合适的步长时，SAG是一种线性收敛的算法，其收敛

45、速度为O(n + )log(1/s)，Algorithm 2 SAGd = 0, yi = 0i = 1, 2, . . . , nfor t=1,2,. . . ,m do均匀采样 i 1, 2, . . . , n d = d yi + f (x)iiyi = f (x)x = x dn end for有如下定理9：nL定理 5 如果函数f 是L-Lipschitz连续，µ强凸函数，如果固定步长k = 21，这有如下的)k32ix x +o关系式：Exk x*2 (1 µ8Ln*9 i f (x*)2 4nL2µ进一步，如果n 8L ，步长为k = f rac

46、12nµ，SAG迭代满足对于k n：8nE f (xk) f (x*) (1 1 )kC其中C = 16L x x*2 + 4i f (x*)2 (8log(1 + µn ) + 1)i3n#03n2µ4L上式的结果是当k n时，在前n步使用SG方法，然后以前n步迭代的均值作为SAG的初始值，同时yi = 0，虽然SAG有着同样的收敛速度，但是更加难分析，在实验中可以直接使用SAG方法，这里仅仅为了给出一个理论上更好的界。LSAG方法是一种线性收敛的随机梯度算法，其收敛速度为O(n + )log(1/s)。SAG方法可以使用采用定步长，在实际中可取k = 1 ，由

47、于L通常未知，常采用线搜索的方式确定9。但是每次迭代其存储量为O(nd)，计算量为O(d)，当n 和d 都比较大时，这会影响到算法的实际使用效率。2.3.2 随机方差减小梯度方法 SAG是第一个取得线性收敛效果的随机梯度方法，此后，对随机算法的研究不断深入，随机方差下降梯度方法(SVRG)是其中最重要的算法之一。这是由8等人在2013年 提出的方法，是一种具有线性收敛的算法。它适用的范围极其广泛，不仅适用于强凸的函数，非强凸，非凸的情况也同样有着很好的收敛性质。这种方法不需要有存储整个梯度并且在迭代过程中并不需要改变每一步的步长，在实际操作中更加的方便。这一方法分为两层循环，每m次在一个点x计

48、算一次全梯度吗，然后在该点计算一个 方向向量，并且这一向量是全梯度的一个无偏估计，然后做一次梯度”下降“。算法的主要思想如下：µ = F(x) =1 n fi(x)n i=1xt = xt1 t( fi (xt1) fi (x) + µ)tt 其中it 是随机的从1, ., n选择，因此我们有Ext|xt1 = xt1 tF(xt1)SVRG是一种方差不断下降的方法。根据梯度的迭代格式， fit (xt1) fit (x) + µ。t 1(t 1)当x 和 x(t)都收敛到同一个x*时，µ 0。因此，当 fi(x) fi(x*)时fi (x ) fi (

49、x) + µ fi(x ) fi(x*) 0 tt 通过这一格式，方差能够得到有效的控制，这提高了收敛的速度。SVRG算法是=+线性收敛的，如果F是L-Lipschitz光滑连续且µ 强凸时，当m足够大使得 1µ(12L)m 2L 12L< 1可以得到EF(xs) F(x*) sF(x0) F(x*)其中x*是最优值点。SVRG是一种线性收敛的随机算法，其每一个内循环需要计算2m + n次梯度，这和Algorithm 3 SVRG给定初始向量x0，步长，正整数m。for k=1,2,. . . do计算方向向量µ = F(x0) = n i=1 f

50、i(x0)令x0= xk1 nfor j=1,2,. . . ,m do随机选取ij 1, 2, . . . , nx j = x j1 ( fij (xj1) fij (x0) + µ)end for选择(1):令x= x k+1选择(2):令xm= 1 m x选择(3):随机选取j 1, 2, . . . , m，令xk+1 = x jk+1m j=1jend for全梯度方法的计算复杂度很相近，但它仅需要O(log(1/s)次外循环，其复杂度为O(n +)log(1/s)。可以看出，每次内循环时，在计算方向向量时，会用到全梯度这一信息，这与SG有 着很明显的差别，这在其他收敛性

51、质比较好的算法中也会得到体现，全梯度的使用控制了优化过程的一个总体方向，使得优化过程不会偏离整体方向太远。SVRG方法的收敛速度为O(n + )log(1/s)，每轮内循环的其计算量为O(nd + md)，通常m取为n的倍数，实际中取m = 2n即可。SVRG同样适用于非强凸或者非凸的目标函数， 有着极好的性质，可参见1819202.3.3 SAGA另 一 个 比 较 重 要 的 方 差 下 降 的 方 法 是SAGA11方 法， SAGA可 以 看 成是SAG和SVRG两种方法思想的融合。SAGA中每次迭代的方向向量可以看成是之前 数次迭代方向的平均值， j 1, . . . , n是随机选取的，具体的方式为：gk = f (xk) f (k)1 n f (k)jjj + n i=1 iin可以看出SAGA中方向的选取方式与SAG很类似，仅仅是将1 替换成了1，这一改变使得每次选取的方向向量是全梯度的无偏估计。它可以看成是SVRG与SAG两种思想结 合形成的一种新的随机算法1611。除了初始化时需要计算n个梯度，需要O(nd)的