A Regularization Mirror Descent Algorithm with Optimal Convergence Rate

doi:10.3969/j.issn.1000-3428.2014.06.032

Abstract

Abstract: 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 structure 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 effective- ness of the proposed algorithm.

Key words: machine learning, online learning, stochastic optimization, sparsity, L1 and L2 regularization, convergence rate

摘要： Pegasos算法是求解大规模支持向量机问题的有效方法，在随机梯度下降过程中植入多阶段循环步骤，能使该算法得到最优的收敛速度O(1/T)。COMID算法是由镜面下降算法推广得到的正则化随机形式，可保证正则化项的结构，但对于强凸的优化问题，该算法的收敛速度仅为O(logT/T)。为此，在COMID算法中引入多阶段循环步骤，提出一种求解L1+L2混合正则化项问题的最优正则化镜面下降算法，证明其具有最优的收敛速度O(1/T)，以及与COMID算法相同的稀疏性。在大规模数据库上的实验结果验证了理论分析的正确性和所提算法的有效性。

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

CLC Number:

TP18

WANG Jing-xiao, GAO Qian-kun, WANG Qun-shan. A Regularization Mirror Descent Algorithm with Optimal Convergence Rate[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2014.06.032.

王惊晓，高乾坤，汪群山. 一种具有最优收敛速度的正则化境面下降算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2014.06.032.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2014.06.032

http://www.ecice06.com/EN/Y2014/V40/I6/148

References

参考文献 [1] Cortes C, Vapnik V. Support-vector Networks[J]. Machine Learning, 1995, 20(3): 273-297. [2] Vapnik V. The Nature of Statistical Learning Theory[M]. [S. l.]: Springer, 1999. [3] Zhang Tong. Statistical Behavior and Consistency of Classifi- cation Methods Based on Convex Risk Minimization[J]. Annals of Statistics, 2004, 32(1): 56-85. [4] Wang Jue, Tao Qing. Machine Learning: The State of the Art[J]. IEEE Transactions on Systems, 2008, 23(6): 49-55. [5] Bottou L. Stochastic Gradient Descent Tricks[M]//Neural Net- works: Tricks of the Trade. Berlin, Germany: Springer, 2012: 421-436. [6] Shalev-shwartz S, Singer Y, Srebro N. Pegasos: Primal Esti- mated Sub-gradient Solver for SVM[C]//Proceedings of the 24th International Conference on Machine Learning. [S. l.]: ACM Press, 2007: 3-30. [7] Langford J, Li Lihong, Zhang Tong. Sparse Online Learning via Truncated Gradient[J]. The Journal of Machine Learning Research, 2009, 10: 777-801. [8] 孔康, 汪群山, 梁万路. L1 正则化机器学习问题求解分析[J]. 计算机工程, 2011, 37(17): 175-177. [9] Nesterov Y. Primal-dual Subgradient Methods for Convex Problems[J]. Mathematical Programming, 2009, 120(1): 221- 259. [10] Hazan E, Agarwal A, Kale S. Logarithmic Regret Algorithms for Online Convex Optimization[J]. Machine Learning, 2007, 69(2/3): 169-192. [11] Nemirovsky A S, Yudin D B. Problem Complexity and Method Efficiency in Optimization[M]. New York, USA: Wiley, 1983. [12] Hazan E, Kale S. Beyond the Regret Minimization Barrier: An Optimal Algorithm for Stochastic Strongly-convex Optimi- zation[J]. Journal of Machine Learning Research, 2011, 19: 421-436. [13] Duchi J, Shalev-Shwartz S, Singer Y, et al. Composite Objective Mirror Descent[C]//Proceedings of the 23rd Annual Workshop on Computational Learning Theory. [S. l.]: ACM Press, 2010: 116-128. [14] Beck A, Teboulle M. Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization[J]. Operations Research Letters, 2003, 31(3): 167-175. [15] Banerjee A, Merugu S, Dhillon I S, et al. Clustering with Bregman Divergences[J]. The Journal of Machine Learning Research, 2005, 6: 1705-1749. 编辑金胡考

Please choose a citation manager

Content to export