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

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