一种具有O(1/T)收敛速率的稀疏随机算法

摘要：

随机梯度下降(stochastic gradient descent,SGD)是一种求解大规模优化问题的简单高效方法,近期的研究表明,在求解强凸优化问题时其收敛速率可通过α-suffix平均技巧得到有效的提升.但SGD属于黑箱方法,难以得到正则化优化问题所期望的实际结构效果.另一方面,COMID (composite objective mirror descent)是一种能保证L1正则化结构的稀疏随机算法,但对于强凸优化问题其收敛速率仅为O(logT/T).主要考虑“L1+Hinge”优化问题,首先引入L2强凸项将其转化为强凸优化问题,进而将COMID算法和α-suffix平均技巧结合得到L1MD-α算法.证明了L1MD-α具有O(1/T)的收敛速率,并且获得了比COMID更好的稀疏性.大规模数据库上的实验验证了理论分析的正确性和所提算法的有效性.

关键词：机器学习、随机优化、稀疏性、L1正则化、COMID

所属期刊栏目：51

分类号：TP301(计算技术、计算机技术)

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

在线出版日期：2014-11-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1901-1910