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

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

腾讯AI Lab第三次参加NeurIPS，共20篇论文入选，位居国内企业前列。会议期间，我们选取7篇论文进行深度解读。今天解读论文为： SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator。

论文链接：https://arxiv.org/pdf/1807.01695.pdf

本文由北京大学ZERO实验室与腾讯 AI Lab 合作完成，是本届NeurIPS的Spotlight论文之一。

本文提出一种新的技术：基于随机路径积分的差分估计子（SPIDER）。该技术能够以更低的计算复杂度追踪许多我们感兴趣的量。本文利用SPIDER技术求解大规模的随机非凸优化问题，在理论上，该算法取得了更快，并在一定程度上最优的收敛速度。

具体地，我们研究如下的随机优化问题：

其中当n有限时，我们把该问题称为有限和问题，当n趋于无穷时，我们把该问题称为在线问题。

由于上述问题可以是一个非凸问题，一般情况下人们很难求出该问题的全局最优解，所以往往会考虑寻求一个松弛解，例如寻求一个ɛ精度的一阶稳定点，即满足：

对于传统的随机梯度下降法 (SGD)，理论上对于上述问题，只能获得ɛ负4次幂的收敛速度。 当使用方差缩减技巧 (variance reduction)[1]之后，速度可以提升到ɛ的负3分之10次幂。而本文提出的SPIDER技术，可以进一步将收敛速度在理论上提升到ɛ的负3次幂！ 我们将算法展示在下图算法1中。可以看出算法的核心在于使用随机梯度的差分的累和估计真实梯度，与使用了归一化的步长。

当得到了上述算法之后，我们进一步考虑是否存在理论上比该算法更快的算法。本文给出很好的回答：对于广义的该问题，在一定情况下(n有限)不存在在数量级上比SPIDER更快的算法。具体地，本文扩展了文献[2]中的反例，说明了存在某个函数理论上至少需要ɛ负3次幂随机梯度访问才可能获得一个一阶稳定点。这即证明了SPIDER在一定条件下的最优性！

本文还有许多的重要扩展，读者可以在长文（https://arxiv.org/pdf/1807.01695.pdf）中看到， 例如：

1、对于一个更难的收敛准则，即要求算法能够逃离较明显的鞍点，找到一个二阶稳定点，本文提出了SPIDER-SFO算法，其收敛速度仍为ɛ的负3次幂。而目前所有非凸方法对于寻求二阶稳定点只能达到ɛ的负3.5次幂的收敛速度！ 下图为给算法之间的收敛速度比较：

2、本文提出的SPIDER技巧非常灵活，不仅可以用于更好的追踪梯度，也可以帮助我们更好的追踪许多其他感兴趣的量，例如对于0阶算法，使用SPIDER技术，可以得到满足d乘以ɛ负3次幂收敛速度的算法 （SPIDER-SZO）。 而目前最快的方法收敛速度为d乘以ɛ负4次幂！

3、本文的证明方法相对简单且易懂。证明技巧很容易被推广，例如很容易使用该文的证明技巧证明SVRG [1]在该问题的收敛速度。

[1] Johnson, Rie & Zhang, Tong (2013). Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems (pp. 315–323).

[2] Carmon, Yair, Duchi, John C., Hinder, Oliver, & Sidford, Aaron (2017b). Lower bounds for finding stationary points i. arXiv preprint arXiv:1710.11606.