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

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

基于随机步长具有最优瞬时收敛速率的稀疏随机优化算法

几乎所有的稀疏随机算法都来源于在线形式,只能获得平均输出方式的收敛速率,对于强凸优化问题无法达到最优的瞬时收敛速率.文中避开在线形式转到随机模式,直接研究随机优化算法.首先在含有L1正则化项的稀疏优化问题中加入L2正则化项,使之具有强凸特性.然后将黑箱优化方法中的随机步长策略引入到当前通用的结构优化算法COMID中,得到基于随机步长的混合正则化镜面下降稀疏随机优化算法.最后通过分析L1正则化问题中软阈值方法的求解特点,证明算法具有最优的瞬时收敛速率.实验表明,文中算法的稀疏性优于COMID.