一种基于Comid的非光滑损失随机坐标下降方法

坐标下降方法以简洁的操作流程、低廉的计算代价和快速的实际收敛效果,成为处理大规模优化最有效的方法之一.但目前几乎所有的坐标下降方法都由于子问题解析求解的需要而假设损失函数的光滑性.本文在结构学习的框架下,在采用Comid方法求解随机挑选单变量子问题的基础上,提出了一种新的关于非光滑损失的随机坐标下降方法.理论分析表明本文所提出的算法在一般凸条件下可以得到Ο(√t/t)的收敛速度,在强凸条件下可以得到Ο(lnt/t)的收敛速度.实验结果表明本文所提出的算法对正则化Hinge损失问题实现了坐标优化预期的效果.     

随机COMID的瞬时收敛速率分析

COMID(Composite Objective MIrror Descent)是一种能够保证L1正则化结构的在线算法,其随机收敛速率可由在线算法的regret界直接得到,但其最终解是T次迭代平均的形式,稀疏性很差.瞬时解具有很好的稀疏性,因此分析算法的瞬时收敛速率在随机学习中变得越来越重要.本文讨论正则化非光滑损失的随机优化问题,当正则化项为L1和L1+L2时,分别证明了COMID的瞬时收敛速率.大规模数据库上的实验表明,在保证几乎相同正确率的同时,瞬时解一致地提高了稀疏性,尤其是对稀疏性较差的数据库,稀疏度甚至能够提升4倍以上.     

一种求解强凸优化问题的最优随机算法

随机梯度下降(SGD)算法是处理大规模数据的有效方法之一.黑箱方法SGD在强凸条件下能达到最优的O(1/T)收敛速率,但对于求解L1+L2正则化学习问题的结构优化算法,如COMID(composite objective mirror descent)仅具有O(lnT/T)的收敛速率.提出一种能够保证稀疏性基于COMID的加权算法,证明了其不仅具有O(1/T)的收敛速率,还具有on-the-fly计算的优点,从而减少了计算代价.实验结果表明了理论分析的正确性和所提算法的有效性.     

一种减小方差求解非光滑问题的随机优化算法

随机优化算法是求解大规模机器学习问题的高效方法之一.随机学习算法使用随机抽取的单个样本梯度代替全梯度,有效节省了计算量,但却会导致较大的方差.近期的研究结果表明:在光滑损失优化问题中使用减小方差策略,能够有效提高随机梯度算法的收敛速率.考虑求解非光滑损失问题随机优化算法COMID(compositeobjective mirror descent)的方差减小问题.首先证明了COMID具有方差形式的O(1/√T+σ²/√T)收敛速率,其中,T是迭代步数,σ²是方差.该收敛速率保证了减小方差的有效性,进而在COMID中引入减小方差的策略,得到一种随机优化算法α-MDVR(mirror descent with variance reduction).不同于Prox-SVRG(proximal stochastic variance reduced gradient),α-MDVR收敛速率不依赖于样本数目,每次迭代只使用部分样本来修正梯度.对比实验验证了α-MDVR既减小了方差,又节省了计算时间.     

一种具有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更好的稀疏性.大规模数据库上的实验验证了理论分析的正确性和所提算法的有效性.