一种具有最优收敛速度的正则化境面下降算法  

A Regularization Mirror Descent Algorithm with Optimal Convergence Rate

作　　者：王惊晓 高乾坤[1] 汪群山[1] 

机构地区：[1]解放军陆军军官学院十一系,合肥230031

出　　处：《计算机工程》2014年第6期148-153,共6页Computer Engineering

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

摘　　要：Pegasos算法是求解大规模支持向量机问题的有效方法,在随机梯度下降过程中植入多阶段循环步骤,能使该算法得到最优的收敛速度O(1/T)。COMID算法是由镜面下降算法推广得到的正则化随机形式,可保证正则化项的结构,但对于强凸的优化问题,该算法的收敛速度仅为O(logT/T)。为此,在COMID算法中引入多阶段循环步骤,提出一种求解L1+L2混合正则化项问题的最优正则化镜面下降算法,证明其具有最优的收敛速度O(1/T),以及与COMID算法相同的稀疏性。在大规模数据库上的实验结果验证了理论分析的正确性和所提算法的有效性。Pegasos algorithm is an efficient method to solve large-scale Support Vector Machine（SVM） problems. The recent study shows that Pegasos can achieve the optimal O（1/T） convergence rate by adding epoches to the procedure of stochastic gradient descent. COMID（Composite Objective Mirror Descent） algorithm is a stochastic regularized case extended by mirror descent method, which can ensure the structm＇e of regularization. However, for strongly-convex problems, the convergence rate of COMID is only O（logT/T）. Aiming at this problem, this paper introduces the epoches to COMID and presents an optimal regularization mirror descent algorithm for solving hybrid L1 and L2 regularization problem. It proves that this algorithm achieves the optimal O（1/T） convergence rate and obtains the same sparsity as COMID algorithm. Experimental results on large-scale datasets demonstrate the correctness of theoretic analysis and effectiveness of the proposed algoifithm.

关 键 词：机器学习 在线学习 随机优化 稀疏性 L1+L2正则化 收敛速度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]