Cong Fang, Chris Junchi Li, Zhouchen Lin, Tong Zhang作者

腾讯AI Lab&北大提出基于随机路径积分的差分估计子非凸优化方法


最近北京大学 ZERO 实验室与腾讯 AI Lab 提出一种新的技术:基于随机路径积分的差分估计子(SPIDER),该技术能够以更低的计算复杂度追踪许多我们感兴趣的量。该研究工作被接收为NeurIPS 2018 SPOTLIGHT(4.08%) 论文。

本文利用 SPIDER 技术求解大规模的随机非凸优化问题,在理论上本文的算法上取得的更快并在一定程度上最优的收敛速度!

论文:Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator

论文地址:https://arxiv.org/pdf/1807.01695.pdf

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

 其中当 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.

理论NIPS2018NIPS非凸优化北大腾讯AI Lab
1
相关数据
随机优化技术

随机优化(SO)方法是生成和使用随机变量的优化方法。 对于随机问题,随机变量出现在优化问题本身的表述中,其涉及随机目标函数或随机约束。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

凸优化技术

凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单,譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用,如次导数等。 凸优化应用于很多学科领域,诸如自动控制系统,信号处理,通讯和网络,电子电路设计,数据分析和建模,统计学(最优化设计),以及金融。在近来运算能力提高和最优化理论发展的背景下,一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化(凸最小化)问题,例如求凹函数f最大值的问题就等同于求凸函数 -f最小值的问题。

随机梯度下降技术

梯度下降(Gradient Descent)是遵循成本函数的梯度来最小化一个函数的过程。这个过程涉及到对成本形式以及其衍生形式的认知,使得我们可以从已知的给定点朝既定方向移动。比如向下朝最小值移动。 在机器学习中,我们可以利用随机梯度下降的方法来最小化训练模型中的误差,即每次迭代时完成一次评估和更新。 这种优化算法的工作原理是模型每看到一个训练实例,就对其作出预测,并重复迭代该过程到一定的次数。这个流程可以用于找出能导致训练数据最小误差的模型的系数。

推荐文章
暂无评论
暂无评论~