论文部分内容阅读
存储能力的提升使得数据的规模和形式成指数形式增长,进而越来越多的领域都提出了对海量数据进行高速处理和分析的要求。一阶优化方法由于其每次迭代所需计算量低和收敛速度快等优势已成为处理这一棘手问题的主流方法。特别是近几年凸优化在信号处理和机器学习等领域需求的急速增长进一步使得一阶优化方法备受关注。而一阶随机优化方法由于其每步迭代所需计算量极小,速度更快和易拓展等优势已成为处理大规模学习问题的主要方法。然而,一阶随机优化方法的这些优势并不是免费获得的。其每次迭代过程中的随机采样策略导致了方差的产生,而方差对随机优化算法产生的最直接的影响就是降低随机优化方法的收敛速率。即使当目标函数具有强凸且光滑这种良好的性质时,传统的一阶随机优化方法也只能达到次线性收敛速率。为了降低方差对随机优化算法产生的影响及保证算法的收敛性,其在运行时通常采用一组递减的步长序列或者预先选定的常数步长。一阶随机优化算法中,不确定的梯度选择方式破坏了搜索空间进而不允许严格的决定序列生成,使得在确定性优化算法中使用的传统的线性搜索策略不能用于随机优化算法中。沿着降低方差这条主线,出现了一批数值效果稳定且具有线性收敛速率的一阶随机优化方法。在这些先进一阶随机优化方法中,最受关注的是引入mini-batching技术的一阶随机优化方法一mini-batch算法。mini-batch算法不仅继承了传统的一阶随机优化算法计算量低、速度快等优越性质,且更易于算法的并行,同时可以有效的降低随机优化算法中由于采样产生的方差。然而,现存的mini-batch算法通常采用与传统一阶随机优化方法相似的步长选择方式:一组递减的步长序列或者预先选定好的常数步长。在运行算法时,使用递减的步长序列会进一步降低算法的收敛速度;而预先选定的常数步长通常需要事先在若干个步长上进行测试择其表现最优的一个,在面对数据规模很大的问题时,这种做法是极其耗时且不可取的。最为重要的是,目前并没有明确的指导原则与理论来说明哪种选择步长的策略更好。本文围绕如何有效、快速的选取mini-batch算法的步长展开工作。主要工作和贡献如下:1.提出 mS2GD-BB 算法。本文提出在 mini-batch semi-stochastic gradient descent(mS2GD)算法中引入Barzilai-Borwein(BB)算法,BB算法可自动计算mS2GD算法的步长。证明了 mS2GD-BB算法的收敛性;分析了 mS2GD-BB算法的复杂度。数值实验证明了所提出算法的有效性。2.提出Random Barzilai-Borwein(RBB)算法,并将其引入到mS2GD算法中,得到mS2GD-RBB算法。mS2GD-RBB算法可获得动态自适应步长。证明了mS2GD-RBB算法的收敛性并分析了 mS2GD-RBB算法的复杂度。大量的数值实验充分证明了 RBB算法的有效性。3.提出基于超梯度的在线步长(Online Step Size,OSS)计算策略并将其应用到 Mini-Batch Nonconvex SVRG(MSVRG)算法中,得到 MSVRG-OSS 算法。证明了 MSVRG-OSS算法的收敛性并分析了该算法的复杂度。MSVRG-OSS算法避免了使用BB算法及RBB算法计算步长时,出现分母为零而导致两种方法失效的情况发生。数值实验证明了 MSVRG-OSS算法的有效性。4.将BB步长和RBB步长引入具有Nesterov加速结构的一阶确定性优化算法和一阶随机优化算法中。分别证明了所提出算法的收敛性并分析了提出算法的复杂度。性质实验和对比实验充分证明了所提出算法的有效性。