超越凸性:随机拟凸优化
本文提出了一种加速的非平滑随机梯度下降算法- ANSGD,该算法利用常见非平滑损失函数的结构来实现一类问题(包括SVM)的最优收敛速率,是第一个能够实现最优O(1/t)率的随机算法来最小化非平滑损失函数的算法,经实证比较表明,ANSGD明显优于以前的次梯度下降算法,包括SGD。
May, 2012
本文探讨了在没有光滑假设的情况下,以及通过运行平均方案将SGD迭代转换为具有最佳优化精度的解决方案的性能,并证明了对于凸非光滑目标函数,最后一个SGD迭代的次优性的程度随T的轮次按O(log(T)/ sqrt(T))缩放,对于非光滑强凸情况,次优性的程度随T按O(log(T)/ T)缩放。此外,本文提出了一种新的简单平均方案,并提供了一些实验说明。
Dec, 2012
该研究提出了一种算法,它结合了随机梯度下降的计算效率和拟牛顿法利用的二阶曲率信息,通过维护和操作每个贡献函数的独立 Hessian 近似值实现不同的方法的统一。该算法适用于高维度优化问题,通过将这些二次近似值存储和操作在一个共享的、时变的、低维度子空间中,保持了计算可行性和限制了内存需求,且需要很少或不需要调整超参数。该算法与早期的随机二阶技术相反,早期技术将每个贡献函数的 Hessian 视为完整 Hessian 的噪声近似,而不是直接估计的目标。在七个不同的优化问题上进行了实验性的改进收敛表现,算法已发布为开源 Python 和 MATLAB 软件包。
Nov, 2013
提出了一种利用小批量方案改进半随机梯度下降(S2GD)方法的 mS2GD,该方法主要用于最小化一个由很多光滑凸函数的平均值和一个简单的非光滑凸正则化器组成的强凸函数,分析表明,该方法在具有小批量效应和简单并行实现方案的情况下,可以加速算法的收敛过程。
Apr, 2015
本文研究证明了随机梯度下降在非凸学习中,无需统一梯度有界性假设也能达到最优收敛率的情况,并在一定程度上对于一般非凸目标函数和梯度主导的目标函数实现了几乎必然收敛。特别地,在方差为零的情况下可以得到线性收敛。
Feb, 2019
证明在L-平滑度条件下, 随机梯度下降的迭代收敛速度的数量级为O(LR2exp[-(mu/4L)T]+sigma2/muT),其中sigma2是随机噪声方差, 且收敛速度与最佳已知的GD和SGD迭代复杂度匹配.
Jul, 2019
研究了随机梯度下降(SGD)算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度,结果表明,Ghadimi和Lan的上限不能得到改进,除非做出额外的假设,即使对于凸二次函数,也是如此;此外还表明,对于非凸函数,SGD最小化梯度的可行性需要根据所选择的最优性标准而定。
Oct, 2019