一种简化的方法获得投影随机子梯度方法的 O (1/t) 收敛速率
本文探讨随机次梯度镜像下降方法在解决受限凸规划问题中的应用及其收敛性分析,特别研究了带有加权迭代平均的随机次梯度镜像下降方法,并分析了其迭代收敛速度和优化效果。通过合适的步长取值,实现了具有强凸性和一般凸性的函数的最优平均速率,并且通过加权平均的方式,优于已有的算法。
Jul, 2013
本文研究了基于随机子梯度优化的非光滑函数的优化问题,提出一种具有 O(1/T)收敛率的算法,并且证明在去除局部 polyhedral 假设时具有一般的收敛性,最后,在确定性问题的特殊情况下,在局部 polyhedral 假设上的收敛性得到了改善。
Jul, 2016
通过对 Shor 子梯度分析的推广,我们将子梯度方法的经典收敛速度理论扩展到可适用于非 Lipschitz 函数。我们证明了在任何具有局部 Lipschitz 性的凸函数中,确定性投影子梯度算法的全局 O(1/√T)收敛速度。我们还表明,对于具有最多二次增长的凸函数,随机投影子梯度方法的收敛速度为 O(1/√T),在强凸性或较弱的二次下限条件下,该速度可进一步提高至 O (1/T)。
Dec, 2017
本文证明了具有广义可微性质、约束非光滑非凸目标函数的单时标随机次梯度法和子梯度平均方法的收敛性,同时,我们也证明了这类函数路径上的链式规则。
Dec, 2019
探讨使用随机梯度下降的加权迭代平均算法,对确定的不可知参数进行最小二乘回归,分析了其收敛速度和误差,并提出了一种新的算法,取得了更好的性能表现。
Jun, 2016
本文研究具有一般凸目标函数和 Lipschitz 连续凸不等式约束函数的凸规划问题,并提出了一种简单的算法,用于实现 O (1/t) 的收敛速度。此外,该算法还可用于处理非线性约束条件。最终将该算法应用于多路径网络效用最大化问题,并产生具有快速 O (1/t) 收敛速度的分散式流量控制算法。
Dec, 2015
本文探讨了在没有光滑假设的情况下,以及通过运行平均方案将 SGD 迭代转换为具有最佳优化精度的解决方案的性能,并证明了对于凸非光滑目标函数,最后一个 SGD 迭代的次优性的程度随 T 的轮次按 O(log(T)/sqrt(T))缩放,对于非光滑强凸情况,次优性的程度随 T 按 O(log(T)/ T)缩放。此外,本文提出了一种新的简单平均方案,并提供了一些实验说明。
Dec, 2012
本文研究了随机梯度下降在随机情形下的最优性。结果表明,对于光滑问题,算法可以达到最优的 O (1/T) 收敛速率,但对于非光滑问题,平均收敛速率可能真的是 Ω(log (T)/T),而这不仅仅是分析的产物。反过来,我们展示了一种简单的平均步骤修改方法,足以恢复到 O (1/T) 收敛速率,而无需对算法做出任何其他改变。此外,我们还给出了支持我们发现的实验结果,并指出了开放性问题。
Sep, 2011
考虑由二次函数的期望值和任意凸函数组合成的复合目标函数的最小化问题,我们研究了随机双均值算法在恒定步长下的特性,证明其无需强凸假设即可获得 O (1/n) 的收敛速度,从而将欧几里得几何中关于最小二乘回归的较早结果扩展到了 (a) 所有凸正则化器以及约束条件,以及(b)由 Bregman 距离表示的所有几何形状。通过一种新的证明技巧来实现这一点,该技巧将随机和确定性递归联系起来。
Feb, 2017
本文提出了基于随机平均梯度方法的优化算法,它克服了黑匣子随机梯度方法的缺点,具有更快的收敛速度和更少的梯度评估数量。实验表明,该算法在许多情况下都优于现有的随机梯度方法和确定性梯度方法,并且可以通过非均匀采样策略进一步提高表现。
Sep, 2013