半随机梯度下降方法
本文研究了随机梯度下降在随机情形下的最优性。结果表明,对于光滑问题,算法可以达到最优的O(1/T)收敛速率,但对于非光滑问题,平均收敛速率可能真的是Ω(log(T)/T),而这不仅仅是分析的产物。反过来,我们展示了一种简单的平均步骤修改方法,足以恢复到O(1/T)收敛速率,而无需对算法做出任何其他改变。此外,我们还给出了支持我们发现的实验结果,并指出了开放性问题。
Sep, 2011
本文提出了一种加速的非平滑随机梯度下降算法- ANSGD,该算法利用常见非平滑损失函数的结构来实现一类问题(包括SVM)的最优收敛速率,是第一个能够实现最优O(1/t)率的随机算法来最小化非平滑损失函数的算法,经实证比较表明,ANSGD明显优于以前的次梯度下降算法,包括SGD。
May, 2012
本文探讨了在没有光滑假设的情况下,以及通过运行平均方案将SGD迭代转换为具有最佳优化精度的解决方案的性能,并证明了对于凸非光滑目标函数,最后一个SGD迭代的次优性的程度随T的轮次按O(log(T)/ sqrt(T))缩放,对于非光滑强凸情况,次优性的程度随T按O(log(T)/ T)缩放。此外,本文提出了一种新的简单平均方案,并提供了一些实验说明。
Dec, 2012
本篇论文研究了关于随机逼近问题的现有算法,提出了两种新型随机梯度算法,并在回归和逻辑分类两种经典的监督学习问题上进行了测试,得到了较好的优化效果。
Jun, 2013
提出了一种利用小批量方案改进半随机梯度下降(S2GD)方法的 mS2GD,该方法主要用于最小化一个由很多光滑凸函数的平均值和一个简单的非光滑凸正则化器组成的强凸函数,分析表明,该方法在具有小批量效应和简单并行实现方案的情况下,可以加速算法的收敛过程。
Apr, 2015
本文提出了一种使用线性搜索技术自动设置步长的随机梯度下降算法,在数据插值设置中,使用 Armijo 线性搜索方法的 SGD 实现凸和强凸函数的确定性收敛率,同时提出了一种 Lipschitz 线性搜索策略的随机额外梯度的算法,该算法在满足嵌入条件的非凸问题和鞍点问题的情况下实现了线性收敛率,并在标准分类任务上表现出了良好的性能。
May, 2019
本文提出了一种统一分析的变体的近端随机梯度下降法,包括了未进行方差缩减、重要性抽样、小批量抽样、量化、坐标子采样等方法,同时获得了近端随机梯度下降法和随机化坐标下降法、方差缩减和非方差缩减的统一理论,提出了五种新变体的近端随机梯度下降法,并通过数值实验证明了其性质。
May, 2019
证明在L-平滑度条件下, 随机梯度下降的迭代收敛速度的数量级为O(LR2exp[-(mu/4L)T]+sigma2/muT),其中sigma2是随机噪声方差, 且收敛速度与最佳已知的GD和SGD迭代复杂度匹配.
Jul, 2019