加权随机算法是深度学习中的常见算法，一般应用在以下场景：有一个集合S，里面比如有A,B,C,D这四项。这时我们想随机从中抽取一项，但是抽取的概率不同，比如我们希望抽到A的概率是50%,抽到B和C的概率是20%,D的概率是10%。一般来说，我们可以给各项附一个权重，抽取的概率正比于这个权重。

研究现状随着大数据的逐渐普及，机器学习处理的数据规模也呈现爆炸式增长． 批处理方法是经典的优化算法之一，由于每次梯度的计算都要穷举一次全部样本，不得不多次遍历所有样本，导致其已经不能满足快速高效处理数据的需求．为了解决这一问题，研究者们提出随机优化方法，每步迭代仅对单个样本进行优化，有效节省迭代过程中的计算时间和内存开销． 尤其是Shalev-Shwarts 等提出随机梯度下降算法(Stochastic Gradient Descent，SGD)，又被称为Pegasos． 该算法在求解支持向量机问题时具有绝对优势，可以在几秒钟内处理完文本数据库RCV1 的80 万个样本． 但是，SGD 在求解强凸优化问题时仅能获得O(logT /T) 的收敛速率，并未达到理论分析上的最优收敛速率O(1 /T)． 另一方面，SGD在强凸条件下的瞬时收敛速率也一直未获得令人满意的理论结果。1

实际应用在实际操作中，SGD 每次迭代仅需要优化单个样本，与批处理方法相比，虽然减小计算量，但是却存在方差，随着迭代次数的增加，方差也逐渐累加，收敛速率不可避免地受到影响。研究表明，越来越多的研究者在已有优化算法中加入减小方差策略，提出新的算法，并获得更好的收敛速率。因此，减小方差策略成为提升已有优化算法收敛速率的主要手段。Johnson 等提出SVRG(StochasticVariance Reduced Gradient)，求解光滑损失强凸优化问题时，在减小方差的同时获得指数阶的最优收敛速率，但SVRG 将目标函数看成一个整体，仍然属于黑箱方法。因此，Xiao 等将SVRG 中的减小方差技巧推广到Proximal 形式，得到随机算法Prox-SVRG(Proximal SVRG)。 与SVRG 一样，Prox-SVRG 在减小方差的同时获得最优收敛速率，而且还保证优化问题的结构性。但是，上述2 种算法在修正梯度的过程中需要计算全梯度，从而不得不多次穷举全部样本。求解光滑问题的减小方差策略推广到非光滑一般凸优化问题中，在每次迭代过程中仅使用部分样本代替全部样本，用于修正梯度，并获得该类优化问题关于方差的最优收敛速率。

加速策略在优化领域中，强凸问题的收敛速率的阶不会优于O(1 /T)，但标准SGD 目前仅具有O(logT /T)收敛速率，并未达到理论上的最优收敛速率。为此，Rakhlin 等提出α-suffix 平均的技巧，仅使用α-suffix 平均代替算法1 平均输出的后半部分。在未改变SGD 迭代步骤的前提下，达到最优收敛速率O(1 /T)。为了克服这一缺点，Lacoste-Julien 等提出一种加权平均技巧，仅对算法的输出使用加权平均，就使SGD 达到O(1 /T) 的最优收敛速率。2

本词条内容贡献者为:

杜强 - 高级工程师 - 中国科学院工程热物理研究所