ASVRG：一个更好的加速近端SVRG

ASVRG是由西安电子科技大学一科研团队于近期新提出来的一个加速的近端随机变量减小的梯度方法，通过设计一个简单高效的动量加速技巧，只添加一个额外的变量和一个动量参数，使得其拥有了一个更简单且所需的训练迭代数更少的加速效果。并且，ASVRG被证明可以实现强凸和非强凸目标的最著名的oracle复杂性，此外，还可以扩展到小批量和非平滑设置。作者在论文中，还凭经验验证了理论结果，并表明ASVRG的性能与最先进的随机方法相当，有时甚至更好。

论文下载地址：https://arxiv.org/abs/1810.03105

近期研究

其中f(x)是一个凸函数，他是n个凸分量函数的有限平均值，而g(x)是一个“简单”可能非平滑函数。随机梯度估计器的方差可能很大，这导致收敛慢。最近，通过许多方差减少的SGD方法以及它们的加速变体如SVRG和Katyusha，SGD的收敛速度得到了提高。

论文的贡献

• 更简单

不同于大多数加速算法，例如需要两个动量的Katyusha，ASVRG的参数更新规则只需要一个动量来加速。

• 低复杂度

作者证明了ASVRG收敛到ε-最小化，对于SC问题，有着O（（n + pnL /μ）log（1 /ε））的Oracle复杂度，这与（Defazio，2016; Allenn-zhu, 2018）中所述相同，并符合（Woodworth和Srebro，2016）中所提到的上限。

• 最优收敛速度

作者还证明了ASVRG对于非SC问题实现了O（1 / t2）的最优收敛速度和O（nlog（1 /ε）+ pnL /ε）的oracle复杂度，这符合（Hien等，2018; Allen-zhu，2018）中最知名的结果。

• 更多应用

作者在算法中引入了小批量，自适应正则化和平滑技术，并进一步分析了它们的收敛性。

收敛性分析

ASVRG用于强凸目标

ASVRG用于非强凸目标

实验一

实验二

从实验结果中可以看出，ASVRG优化的加速效果显著。其中，ASVRG理论上跟目前最快的算法Katyusha一样，有最快的收敛速度，不过由于Katyusha使用了两个动量参数，所以ASVRG的时间开销是Katyusha的一半，使得它比Katyusha的速度更快。

论文下载地址：https://arxiv.org/abs/1810.03105

版权声明 本博客的文章除特别说明外均为原创，本人版权所有。欢迎转载，转载请注明作者及来源链接，谢谢。 本文地址: https://blog.ailemon.net/2019/01/03/asvrg-a-better-accelerated-proximal-svrg/ All articles are under Attribution-NonCommercial-ShareAlike 4.0