NeurIPS 2018 | 腾讯AI Lab参与提出机器学习模型的随机优化新方法

感谢阅读腾讯AI Lab微信号第62篇文章。AI领域顶会 NeurIPS 正在加拿大蒙特利尔举办，腾讯AI Lab实验室每日将深度解读一篇入选论文，今天是第6篇。Enjoy！

NeurIPS (Conference on Neural Information Processing Systems,神经信息处理系统进展大会)与ICML并称为神经计算和机器学习领域两大顶级学术会议。今年为第32届会议，将于 12月3日至8日在加拿大蒙特利尔举办。

腾讯AI Lab第三次参加NeurIPS，共20篇论文入选，位居国内企业前列。会议期间，我们选取7篇论文进行深度解读。今天解读论文为： 

Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexity。

论文链接：

http://papers.nips.cc/paper/8057-stochastic-primal-dual-method-for-empirical-risk-minimization-with-o1-per-iteration-complexity

在这篇论文中，作者提出了一种新的随机优化方法，用来优化基于广义线性模型的机器学习模型，即具有如下形式的问题：

其中x是模型的参数，即优化的变量。

这一类的函数包括很多常用的机器学习模型，例如logistic regression、SVM等。而这一类的优化问题的标准解法包括随机梯度下降（SGD）以及它的一些变种。在SGD等传统的随机方法中，算法每次会随机抽取一个样本的特征向量a_i，再根据抽取到的信息来更新模型参数，因此它们的迭代复杂度与问题的维度成正比。而在这篇论文中，作者提出了一种全新的随机更新方式：在每一轮迭代随机抽取一个特征向量a_i的基础上，只需要进一步地随机采样a_i的某一个维度上的信息即可进行迭代，因此这种方法具有常数的、与问题大小无关的迭代复杂度。

具体来说，论文中提出的算法如下：

这个算法称为SPD1算法。就像上述所说的一样，算法的每一轮迭代只需要用到一个随机采样的a_ij的信息，然后以此为基础做一个坐标下降。值得注意的是，除了优化变量x外，这个算法中需要用到一个额外的辅助变量y。从优化理论的角度来说，y是原问题的对偶变量，所以这个算法实际上是一个基本原问题-对偶问题的算法。但从直观上来理解，变量y_i实际上也是对问题的第i个样本的拟合情况的一个评估，在有了一个这样的y的辅助下，SPD1算法可以做到不需要完整的样本就可以对模型参数x做出更新。

在论文中，作者证明了SPD1方法的收敛性，而且在普通的非光滑的凸问题下它的复杂度为：

这跟SGD的总体复杂度是一致的。

更进一步的，在结合了方差减小的技巧之后，作者提出了上述算法的一个改进版本——SPD1-VR：

除了方差减小的技巧外，该方法与SPD1不同的是进一步引入了extragradient方法：在每轮迭代分别需要对两个变量做两次更新，这是为了保证算法的理论收敛性而设计的。在论文中作者证明了在强凸的条件下SPD1-VR算法具有线性的收敛性，优于原始的SPD1。

实验表明，在维度比较高的问题中，SPD1和SPD1-VR的收敛速度要优于对应的SGD、SVRG等算法，这主要是其双重的随机性带来的。另外，论文中也指出这种每一轮只需要样本的部分维度信息的更新方法也会在分布式计算的场景中带来好处。

精彩解读回顾