非光滑强凸情形Adam型算法的最优收敛速率

摘要

对于非光滑强凸问题,在线梯度下降(Online Gradient Decent,OGD)取适当步长参数可以得到对数阶后悔界.然而,这并不能使一阶随机优化算法达到最优收敛速率.为解决这一问题,研究者通常采取两种方案:其一是改进算法本身,另一种是修改算法输出方式.典型的Adam(Adaptive moment estimation)型算法SAdam(Strongly convex Adaptive moment esti⁃mation)采用了改进算法的方式,并添加了自适应步长策略和动量技巧,虽然得到更好的数据依赖的后悔界,但在随机情形仍然达不到最优.针对这个问题,本文改用加权平均的算法输出方式,并且重新设计与以往算法同阶的步长超参数,提出了一种名为WSAdam(Weighted average Strongly convex Adaptive moment estimation)的Adam型算法.证明了WSAdam达到了非光滑强凸问题的最优收敛速率.经过Reddi问题的测试和在非光滑强凸函数优化中的实验,验证了所提方法的有效性.