一种减小方差求解非光滑问题的随机优化算法

来源：软件学报杂志2015年第11期北京时间：

作者：朱小辉,陶卿,邵言剑,储德军

单位：朱小辉，中国人民解放军陆军军官学院 十一系, 安徽 合肥 23003111,陶卿，中国人民解放军陆军军官学院 十一系, 安徽 合肥 23003102,邵言剑，中国人民解放军陆军军官学院 十一系, 安徽 合肥 23003103,储德军，中国人民解放军陆军军官学院 十一系, 安徽 合肥 23003104

摘要：随机优化算法是求解大规模机器学习问题的高效方法之一.随机学习算法使用随机抽取的单个样本梯度代替全梯度,有效节省了计算量,但却会导致较大的方差.近期的研究结果表明:在光滑损失优化问题中使用减小方差策略,能够有效提高随机梯度算法的收敛速率.考虑求解非光滑损失问题随机优化算法COMID(compositeobjective mirror descent)的方差减小问题.首先证明了COMID具有方差形式的O(1/√T+σ2/√T)收敛速率,其中,T是迭代步数,σ2是方差.该收敛速率保证了减小方差的有效性,进而在COMID中引入减小方差的策略,得到一种随机优化算法α-MDVR(mirror descent with variance reduction).不同于Prox-SVRG(proximal stochastic variance reduced gradient),α-MDVR收敛速率不依赖于样本数目,每次迭代只使用部分样本来修正梯度.对比实验验证了α-MDVR既减小了方差,又节省了计算时间.

关键词：机器学习;随机算法;非光滑;方差;composite objective mirror descent(COMID)

基金资助：国家自然科学基金(61273296); 安徽省自然科学基金(1308085QF121)