软件学报  2014, Vol.25 Issue (9): 2160-2171   PDF    
一种求解强凸优化问题的最优随机算法
邵言剑, 陶卿, 姜纪远, 周柏    
中国人民解放军陆军军官学院 十一系, 安徽 合肥 230031
摘要:随机梯度下降(SGD)算法是处理大规模数据的有效方法之一.黑箱方法SGD在强凸条件下能达到最优的O(1/T)收敛速率,但对于求解L1+L2正则化学习问题的结构优化算法,如COMID(composite objective mirror descent)仅具有O(lnT/T)的收敛速率.提出一种能够保证稀疏性基于COMID的加权算法,证明了其不仅具有O(1/T)的收敛速率,还具有on-the-fly计算的优点,从而减少了计算代价.实验结果表明了理论分析的正确性和所提算法的有效性.
关键词机器学习     随机优化     强凸问题     混合正则化项     COMID (composite objective mirror descent)    
Stochastic Algorithm with Optimal Convergence Rate for Strongly Convex Optimization Problems
SHAO Yan-Jian, TAO Qing, JIANG Ji-Yuan, ZHOU Bai    
11st Department, Army Officer Academy of PLA, Hefei 230031, China
Corresponding author: SHAO Yan-Jian, E-mail: shy.jian@gmail.com
Abstract: Stochastic gradient descent (SGD) is one of the efficient methods for dealing with large-scale data. Recent research shows that the black-box SGD method can reach an O(1/T) convergence rate for strongly-convex problems. However, for solving the regularized problem with L1 plus L2 terms, the convergence rate of the structural optimization method such as COMID (composite objective mirror descent) can only attain O(lnT/T). In this paper, a weighted algorithm based on COMID is presented, to keep the sparsity imposed by the L1 regularization term. A prove is provided to show that it achieves an O(1/T) convergence rate. Furthermore, the proposed scheme takes the advantage of computation on-the-fly so that the computational costs are reduced. The experimental results demonstrate the correctness of theoretic analysis and effectiveness of the proposed algorithm.
Key words: machine learning     stochastic optimization     strongly-convex     hybrid regularization     COMID (composite objective mirror descent)    

机器学习面临的数据规模正变得越来越大,比如,一个普通文本数据库就会达到107样本个数或109样本维数的规模[1].在对大数据进行处理和分析中可以挖掘出有价值的信息,进而有效地解决或缓解各领域面临的问题.然而,大数据在带来机遇的同时,也面临着众多的困难和挑战,寻求一种高速、有效的计算技术,是目前亟需解决的科学问题.机器学习方法在该背景下得到广泛的应用,其核心问题之一是求解优化问题[2],与传统批处理算法不同的是,随机梯度下降(SGD)算法[3,4]在每次迭代计算时,仅仅优化单个样本点造成的损失,极大地减少了内存开销,但也正是每次仅仅优化单个样本点造成的损失,收敛速率不可避免地会受到影响.但机器学习问题有其特殊性,即样本集独立同分布,并且通常冗余度较大,仅需要很少一部分样本就能达到所需的泛化能力,因此,迭代部分样本点步骤后,优化问题解的学习精度就已经趋于稳定.特别是在2007年,Shalev-Shwarts等人[5]在投影次梯度方法的基础上得到了求解支持向量机问题的SGD,该方法又称为Pegasos.Pegasos在处理80万个样本的路透社文本RCV1数据库仅需几秒的时间,与当时主流的大规模算法相比,SGD在处理实际学习问题中具有明显的优势.因此,SGD算法无论是在理论还是在实用上成为求解大规模学习问题的有效方法.

对于强凸优化问题,Pegasos的收敛速率只达到O(logT/T),与理论上的最优收敛速率O(1/T)存在着明显的差距.为解决这一问题,Hazan等人[6]在SGD方法中嵌入内循环,提出EPOCH-GD随机算法,获得了O(1/T)的最优收敛速率.但Rakhlin等人[7]认为,EPOCH-GD算法与标准的SGD在算法形式上存在较大差别,因此不能说明SGD算法能够得到最优的收敛速率.针对这一问题,Rakhlin等人在没有改变SGD算法迭代步骤的前提下,在解决强凸随机优化问题时,仅仅将算法的平均输出方式以后半部分平均的a-suffix技巧来代替,最终达到了O(1/T)的最优收敛速率.但是该平均技巧与标准的平均方式相比也带来了一个缺点,导致了不能按照on-the-fly的方式计算.2012年,Lacoste-Julien等人[8]提出一种加权平均方式,与a-suffix平均不同的是,该方法仅对SGD算法的每步的输出解乘以一个权重,从而在得到最优的收敛速率的同时,还保证了on-the-fly的计算方式.

众所周知,机器学习优化问题一般以“正则化项+损失函数”的形式存在[2],早期的学习算法将正则化项和损失函数组成的目标函数当做一个整体来考虑,并不区别看待,SGD就属于这种黑箱方法.然而,近些年的研究成果表明:正则化项和损失函数往往有着机器学习的特殊含义,如L1正则化保证了解的稀疏性[9];L2正则化具有比较明确支持向量的含义[10]等.著名优化领域专家Nesterov也曾指出:“黑箱方法在凸优化问题上的重要性将不可逆转地消失,彻底地取而代之的是巧妙运用问题结构的新算法[11]”.此后,广大的研究者们开始意识到那些能够充分发掘优化问题本身结构的算法将起到越来越重要的地位.

由于SGD方法无法充分挖掘优化问题的学习结构,在求解随机优化问题时,极大地掩盖了正则化项的作用.为此,众多学者都致力于搜寻可以突出机器学习结构含义的算法[12, 13, 14],其中,COMID(composite objective mirror descent)算法[13]以其简单高效而倍受学者们推崇.COMID是Duchi等人对经典的镜面下降算法MD[15,16]的突破性改进,与MD算法相比,COMID在优化过程中将正则化项和损失函数区分看待,只对损失函数进行近似线性展开,从而保证了正则化项的结构.此外,该算法可以直接使用软阈值方法[12]对优化子问题解析求解,减少了计算代价.COMID算法先以在线形式被提出,后又扩展为随机算法.但是,在求解强凸优化问题时,COMID仅能够得到O(lnT/T)的收敛速率.

综合以上分析,能否把加权平均技巧与COMID算法相结合,将COMID算法求解强凸优化问题的收敛速率加速到O(1/T)?从COMID算法的收敛性分析中不难发现:当正则化和损失函数分开考虑时,其证明过程中的主要困难而又复杂之处体现在如何界定正则化项交错问题导致的上界.本文在COMID算法中引入了类似文献[8]中的加权平均技巧,提出了一种HRMD-W(hybrid regularized mirror descent with weighted averaging)算法,在考虑L1+L2+Hinge的混合正则化项的随机优化问题时,我们首先使用软阈值方法给出交错项的上界;其次,通过巧妙的选取步长,在理论上证明HRMD-W具有O(1/T)的收敛速率,并且可以使用on-the-fly方法减少计算代价;最后,在大规模数据库上的实验结果表明:HRMD-W算法在保证与COMID算法具有相同稀疏性的同时,获得了较高的正确率.

1SGD,COMID算法及加速技巧

不失一般性,我们在此仅讨论最简单的二分类问题,假设训练样本集独立同分布,并且表示为S={(x1,y1),…,(xm,ym)},其中,(xi,yi)ÎRnx{-1,+1},m为样本个数,n为样本维数.S中的样本满足独立同分布,我们使用x=(x,y)表示随机抽取的样本.

1.1SGD算法

SGD以操作简单、计算便捷、理论分析完善,其主要执行流程见算法1,假设F为优化问题的目标函数,则SGD所要求解的优化问题如下:

(1)

其中,F(w)=Ex[F(w,x)],WRn上的闭凸集合.

从公式(1)可以看出:SGD的目标函数为期望形式,这正是随机算法的特点.由于样本独立同分布,关于单个样本的目标函数F(wt,x)的次梯度gt是整个目标函数F(wt)次梯度的无偏估计[6,17],即有E[gt]ÎF(wt),因此,SGD在算法形式上表现为每步迭代仅优化随机抽取的一个样本.此外,SGD算法的一个重要评价指标——收敛速率,是指在数学期望下,SGD输出解对应的目标函数值收敛于最优目标函数值的速率[6],数学表达式为

E[F(w)-F(w)],

其中,w*为优化问题的最优解.

算法1. SGD算法.

1. Initialize w1=0

2.     for t=1 to T

3.         Compute gtÎF(wt,xt),ht=1/st

4.         Compute wt+1=PW(wt-htgt)

5.     end for

6. Output:

其中,s为强凸参数,ht为步长,gt表示F(wt,x)的次梯度,PW表示在W上的投影算子.

1.2COMID算法

COMID算法是2010年由Duchi等人提出,该算法将优化目标函数中的正则化项和损失函数区分对待,仅对损失函数进行线性近似展开,而不对正则化项作处理.此时,子问题就具有解析解,算法既能够快速收敛又能够保证正则化项的各种性质.特别地,当r(w)为L1正则化项时,能够得到稀疏解.具体来说,在结构学习框架下,COMID算法的主要迭代形式如下:

(2)

其中,r(w)为正则化项,若用l(w,x)表示损失函数,则gt为损失函数l(wt,xt)的次梯度,Bj(w,wt)为Bregman[18]. COMID算法所要优化的目标函数为F(w)=Ex[r(w)+l(w,x)],其执行过程与SGD类似,区别在于COMID所要求解的子问题为公式(2).

在求解强凸优化问题时,当步长取O(1/t)时,SGD和COMID算法都只达到O(logT/T)的收敛速率,为此,Shalev-Shwartz和Duchi等人给出如下定理:

定理1[5,13]. 假设w*为优化问题(1)的最优解,取步长ht=O(1/t),则当SGD或COMID算法求解强凸优化问题并运行T次迭代后,其收敛速率满足:

其中,

1.3SGD的加速技巧

众所周知,强凸优化问题的最优收敛速率为O(1/T),但标准的SGD算法(算法1)仅能达到O(logT/T).为此,文献[7]通过对算法1的输出简单改动,使SGD算法得到最优的收敛速率,即对算法输出使用a-suffix平均技巧,将原来的标准平均方式改为

其中,aÎ(0,1),设aT为整数.

然而,该方法不能on-the-fly地进行计算.通过观察可知:标准平均方式可以写成(1+T)wT的形式,在这种形式下,算法不需要运行所有迭代步骤,在运行的过程中,仅需少量的计算代价,便可对进行更新,这种方式对算法的执行起着极其重要的作用.a-suffix平均方式需要存储算法每次迭代产生的wT,或者需要事先知道算法迭代次数,固不能on-the-fly地进行计算.

随后,文献[8]为了克服a-suffix平均的缺点,使用另外一种平均方式——加权平均,同样使SGD算法得到O(1/T)的收敛速率.加权平均不同于以往仅简单对wt取平均的做法,在算法第t步迭代产生wt的同时,为wt乘以一个权重t,其输出形式为

其中,rT=2/(T+1).

加权平均不仅能够on-the-fly地进行计算,而且通过巧妙地选取步长,使得其收敛速率的理论证明更加地简洁易懂.

使用a-suffix和加权平均技巧求解强凸优化问题时,都能使优化问题的收敛速率加速到最优,即得到O(1/T)的收敛速率.为此,文献[7,8]给出如下定理:

定理2[7,8]. 令w*为优化问题(1)的最优解,取步长ht=O(1/t),SGD算法使用a-suffix或加权平均技巧求解强凸优化问题,其收敛速率满足:

当使用a-suffix平均技巧时,;使用加权平均技巧时,有

本文结合COMID和加权平均技巧,提出HRMD-W算法.在求解L1和L2混合正则化项导致的强凸优化问题时,通过克服HRMD-W算法收敛性分析中的关键性问题,从理论方面将该算法的收敛速率提升至最优,即,达到O(1/T).

2HRMD-W算法及收敛性分析

本文主要考虑特殊的具有L1和L2混合正则化项的随机优化问题:

(3)

其中,l(w;x)=max{0,1-ytáw;xtñ}为样本(xt,yt)的Hinge损失.不难看出:L2正则化项的引入,使整个目标函数具备了强凸性质.同时,为了保证目标函数的结构,将此强凸项并入原正则化项中,此时,正则化项为

.

易知,r(w)为强凸函数,满足s-强凸[19].

算法2. HRMD-W算法.

1: Input parameters l,s. Initialize w1=0

2:     for t=1 to T

3:         Compute gtÎl(wt,ξt),ht=2/st

4:         Compute wt+1 via Eq.(4)

5:     end for

6: Output:

算法2为HRMD-W算法的主要执行过程,在算法中,我们取与文献[8]不同的是,算法2在第t步迭代产生wt的同时,为wt乘以一个权重t+1,其输出可以写为

其中,由此可见,可通过on-the-fly方式进行计算.HRMD-W算法主要迭代步骤为

(4)

本文的收敛速率证明与文献[8]基本类似,但SGD和COMID算法存在着本质的区别.为此,我们给出了正则化交错项需满足的关系式,见引理1.

引理1. 假设E[||gt||]≤G,"t,对公式(4)采用软阈值方法进行求解,则正则化交错项有

如下关系式成立:

其中,

根据以上引理,并使用加权平均特有的证明技巧,我们很容易得出如下两个定理,附录2给出了详细的证明:

定理3. 令w*为优化问题(3)的最优解,则HRMD-W算法运行T次迭代后,其收敛速率满足如下关系:

其中,AB同引理1.

定理4. 令w*为优化问题(3)的最优解,则HRMD-W算法输出的任意瞬时解与最优解之间满足如下关系:

其中,AB同引理1.

从定理3不难看出:不等式右边的形式为O(1/T)+O(lnT/T2)+O(1/T2),其中起主导作用的项为O(1/T).所以,当HRMD-W算法运行T步后的收敛速率为最优的O(1/T).类似地,定理4描述了算法迭代过程的解与最优解之间欧式距离的界小于O(1/T).

3 数值实验

本节通过4个大规模数据库验证HRMD-W算法的实际效果.实验环境为Sun Ultra45工作站(1.6GHz UltraSPARC IIIi处理器,4GB内存,Sorlaris10操作系统),实验所采用的比较算法均在LIBLINEAR[20]平台上实现.

3.1 实验数据库和比较算法

实验所采用的4个大规模数据库分别为CCAT,astro-physic,a9a和covtype,表 1给出了这4个数据库的详细描述.

Table 1 Description of datasets 1 实验数据库描述

实验对3种算法进行比较,分别为HRMD-W算法、SGD-W算法[8]和采用L1+L2混合正则化的COMID算法,记为HRCOMID算法.对于使用L2正则化项的强凸优化问题,SGD-W算法得到了O(1/T)的最优收敛速率;根据文献[13]易知,HRCOMID算法的收敛速率为O(logT/T).

3.2 实验方法及结论

实验过程中,我们对每个数据库的样本采取随机抽取的方式,算法进行10 000次迭代后终止.为公平起见,算法中的参数采用网格搜索方式取最优参数,并且算法在每个数据库上运行10次,最终结果为10次结果的平均值及均方差.

图 1为3种算法的收敛速率比较图,其中,横坐标表示迭代次数;纵坐标表示当前目标函数值与最优目标函

Fig. 1 Comparisons of convergence rate图 1 目标函数收敛速率比较图

数值之差,在此用表示,具体计算时,最优目标函数值取迭代中最小的目标函数值.

图 1可以看出:HRMD-W算法在astro-physic和covtype数据库上与SGD-W算法收敛速率相当;在a9a数据库的收敛速率快于SGD-W;但在CCAT数据库慢于SGD-W算法.总的来说,HRMD-W基本达到与SGD-W算法相同的收敛速率,且均快于HRCOMID算法.图中代表Bound的双划线表示定理2所给出的算法收敛速率的界.可以看出,HRMD-W算法的实际收敛速率曲线均在其相应界的下方,进而说明本文理论分析的正确性.

表 2给出算法在4个数据库上的测试错误率及方差.比较表中3种算法很容易看出:算法HRMD-W的测试错误率最小,准确率最高.众所周知:方差在一定程度上反映算法的稳定性,方差越小,表示算法的稳定性越好.从表 2可以看出:HRMD-W和SGD-W算法的稳定性优于HRCOMID算法,这是因为在算法输出解中使用加权技巧,从而使得算法的稳定性增加.

Table 2 Comparisons of test error and variance 2 测试错误率和方差比较

图 2为3种算法的稀疏度比较图.稀疏度是指算法输出解向量中零维所占的比例,解的稀疏度越高,表示算法稀疏性越好.比较HRMD-W和SGD-W算法容易发现:在a9a和astro-physic数据库上,两者的稀疏性相差不大;在CCAT和covtype上,HRMD-W算法的稀疏性较好.比较HRMD-W和HRCOMID,从图中可以看出:对于covtype数据库,HRCOMID算法的稀疏性稍好一些;在a9a,两种算法稀疏性相当;但在astro-physic和CCAT数据库上,HRMD-W的稀疏性明显好于HRCOMID算法.

Fig. 2 Comparisons sparsity图 2 稀疏度比较图
4 总结与展望

本文在混合正则化项的镜面下降算法中引入加权技巧,提出了HRMD-W算法.该算法在保证正确率的前提下,以on-the-fly的计算方式减少计算代价,并且在理论上证明算法达到O(1/T)的最优收敛速率.最后,通过实验对算法的性能进行验证,说明理论分析的正确性和所提算法的有效性.

对强凸优化问题,通过使用加权平均技巧,不仅能得到最优的收敛速率,而且在一定程度上也能减少算法的计算代价和提高算法的稳定性.这仅仅是将该技巧用于算法的最终输出上,近年也出现了将该技巧用于梯度上[21].能否将加权平均用于算法的迭代过程中,是我们下一步努力的方向.

附录1. 引理1的证明

证明:公式(4)所要解决的优化问题为

.

由于向量w的每一维不相关,因此可以将其转换为如下单维优化问题:

.

满足二次项+一次项+正则化项条件,使用软阈值方法解得:

.

分两种情况讨论:

(1) 当|wt,j-htgt,j|≤lht,即|wt,j|-|htgt,j|≤lht时,有wt+1,j=0.此时,单维的正则化交错项为

所以,该情况正则化项满足:

为方便整理,我们定义两个参数来简化证明,表示如下:

得到:

(2) 当|wt,j-htgt,j|>lht时,有:

.

为方便证明,用sgn表示sgn(wt,j-htgt,j).此时:

所以,该情况正则化项满足:

同样地,定义两个参数来简化证明,表示如下:

令:

所以有:.

综上两种情况,我们令:

可得:.

附录2. 定理3定理4的证明

证明:根据MRMD-W算法的主要迭代步骤:

其中,gt=f(wt,xt).

r¢(wt+1)Îr(wt+1),由约束优化问题的一阶最优性条件得:

áw-wt+1,wt+1-wt+htgt+htr¢(wt+1)ñ≥0.

特别地,当w=w时:

áw*-wt+1,wt+1-wt+htgt+htr¢(wt+1)ñ≥0.

进一步化简得:

áw*-wt+1,wt+1-wtñhtáwt+1-w*,gt+r¢(wt+1)ñ.

又因为f(w,x)为一般凸函数,r(w)函数满足s-强凸,所以:

所以有:

即:

对上式两边取期望得:

ht=2/st,上式得:

对上式两边同乘以(t+1),并从t=1到T求和得:

因为,

所以有:.

,所以有:

.

参考文献
[1] 孙正雅,陶卿.统计机器学习综述:损失函数与优化求解.中国计算机学会通讯,2009,5(8):7-14.
[2] Tao Q, Gao QK, Jiang JY, Chu DJ. Survey of solving the optimization problems for sparse learning. Ruan Jian Xue Bao/Journal of Software, 2013,24(11):2498-2507 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4479.htm
[3] Robbins H, Monro S. A stochastic approximation method. The Annuals of Mathematical Statistics, 1951,22:400-407 .
[4] Kiefer J, Wolfowitz J. Stochastic estimation of the maximum of a regression function. The Annuals of Mathematical Statistics, 1952,23:462-466.
[5] Shalev-Shwartz S, Singer Y, Srebro N. Pegasos: Primal estimated sub-gradient solver for SVM. In: Proc. of the 24th Int’l Conf. on Machine Learning. ACM Press, 2007. 807-814.
[6] Hazan E, Kale S. Beyond the regret minimization barrier: An optimal algorithm for stochastic strongly-convex optimization. Journal of Machine Learning Research-Proceedings Track, 2011,19:421-436.
[7] Rakhlin A, Shamir O, Sridharan K. Making gradient descent optimal for strongly convex stochastic optimization. In: Proc. of the 29th Int’l Conf. on Machine Learning. 2012. 449-456. http://arxiv.org/abs/1109.5647
[8] Lacoste-Julien S, Schmidt M, Bach F. A simpler approach to obtaining an o(1/t) convergence rate for projected stochastic subgradient descent. arXiv preprint arXiv:1212.2002, 2012.
[9] Tibshirani R. Regression shrinkage and selection via the lasso. Journal of Royal Statistical Society, Series B, 1996,58(1):267-288.
[10] Shalev-Shwartz S, Zhang T. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 2013,14:567-599.
[11] Nesterov Y. How to advance in structural convex optimization. OPTIMA: Mathematical Programming Society Newsletter, 2008,78: 2-5.
[12] Xiao L. Dual averaging methods for regularized stochastic learning and online optimization. The Journal of Machine Learning Research, 2010,11:2543-2596.
[13] Duchi J, Shalev-Shwartz S, Singer Y, Tewari A. Composite objective mirror descent. In: Proc.of the 23rd Annual Workshop on Computational Learning Theory. ACM Press, 2010. 116-128.
[14] Ouyang H, He N, Tran L, Gray A. Stochastic alternating direction method of multipliers. In: Proc. of the 30th Int’l Conf. on Machine Learning. 2013. 80-88.http://jmlr.org/proceedings/papers/v28/ouyang13.html
[15] Nemirovski A, Yudin D. Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics, John Wiley-Interscience Publication, 1983.
[16] Beck A, Teboulle M. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 2003,31(3):167-175 .
[17] Nemirovski A, Juditsky A, Lan G, Shapiro A. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 2009,19(4):1574-1609 .
[18] Bregman LM. The relaxation method of finding the common point convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 1967,7:200-217 .
[19] Bertsekas D. Convex Analysis and Optimization. Athena: Scientific, 2003.
[20] Fan RE, Chang KW, Hsieh CJ, Wang XR, Lin CJ. LIBLINEAR: A library for large linear classification. The Journal of Machine Learning Research, 2008,9:1871-1874.
[21] Chen X, Lin Q, Pena J. Optimal regularized dual averaging methods for stochastic optimization. In: Proc.of the Advances in Neural Information Processing Systems. 2012. 404-412.
[2] 陶卿,高乾坤,姜纪远,储德军.稀疏学习优化问题的求解综述.软件学报,2013,24(11):2498-2507. http://www.jos.org.cn/1000-9825/4479.htm