非光滑凸问题投影型对偶平均优化方法的个体收敛性

对于一般凸问题,对偶平均方法的收敛性分析需要在对偶空间进行转换,难以得到个体收敛性结果.对此,文中首先给出对偶平均方法的简单收敛性分析,证明对偶平均方法具有与梯度下降法相同的最优个体收敛速率Ο(lnt/t).不同于梯度下降法,讨论2种典型的步长策略,验证对偶平均方法在个体收敛分析中具有步长策略灵活的特性.进一步,将个体收敛结果推广至随机形式,确保对偶平均方法可有效处理大规模机器学习问题.最后,在L1范数约束的hinge损失问题上验证理论分析的正确性.

Individual Convergence of Projected Dual Averaging Methods in Nonsmooth Convex Cases

For convex problems,since the convergence analysis of DA(dual averaging)needs to be transformed in dual space,it is difficult to gain individual convergence.In this paper,a simple convergence analysis of DA is presented,and then it is proved that DA can attain the same optimalΟ(ln t√t)individual convergence rate as gradient descent(GD).Different from GD,the individual convergence of DA is proved to be step-size flexible by analyzing two typical step-size strategies.Furthermore,the stochastic version of the derived convergence is extended to solve large-scale machine learning problems.Experiments on L1-norm constrained hinge loss problems verify the correctness of the theoretical analysis.