该研究分别设计了针对凸函数和非凸函数的优化算法 SGD3 和 SGD5,分别能够在近最优的速率下找到梯度范数为特定值的最小值点和近似局部极小值点,并且这些速率具有优越性和不劣性。
Jan, 2018
采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界,使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型,证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型,我们证明了 ε^ -3 个查询的下界,建立了最近提出的方差缩减技术的最优性。
Dec, 2019
本篇论文研究了关于随机逼近问题的现有算法,提出了两种新型随机梯度算法,并在回归和逻辑分类两种经典的监督学习问题上进行了测试,得到了较好的优化效果。
Jun, 2013
本文介绍了一种非凸二阶优化算法,其时间复杂度与样本维度和训练样本数量呈线性关系,在训练神经网络和其他非凸目标的机器学习问题上具有广泛应用,并可以保证返回近似局部最小值。
Nov, 2016
本篇论文使用类似于期望光滑性假设的新方法来研究随机梯度下降法在非凸优化中的收敛率,并在考虑多种采样策略和小批量大小的情况下,探讨有限和优化问题的影响。
Feb, 2020
本篇论文研究了非凸优化中高效到达稳定点的基本问题,并利用方差缩减技巧和适用于非凸优化的全新方差缩减分析提出一种首个非凸优化的一阶小批量随机算法,并在非凸损失函数和神经网络训练中表现出了有效性。
Mar, 2016
本文将通过对随机梯度下降进行深入分析,证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时,SGD 能够在 O(ε^ -3.5)次随机梯度计算中逃离鞍点并找到(ε,O(ε^ 0.5))- 近似二阶稳定点,从而推翻了 SGD 至少需要 O(ε^ - 4)的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配,如 Nesterov 的动量加速,负曲率搜索,以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解,并可潜在地推广到广泛的随机优化算法类。
Feb, 2019
本文提出了使用混合随机估算器设计的混合随机梯度算法来解决非凸期望问题,该算法可以获得更好的复杂度,同时考虑不同的扩展,如使用自适应步长和不同的迭代方式。在使用两个非凸模型进行了多个数据集上的比较。
May, 2019
本文提出了一种针对非凸优化的简化方法,通过该方法可将寻找稳态的算法转变为寻找局部极小值的算法,并将海森矩阵向量积计算替换为仅使用梯度计算,此方法在随机和确定性设置下均可应用且不会影响算法的性能表现。将此方法应用于现有算法,可以将 Natasha2 转变为一阶方法而不影响性能,亦可以将 SGD,GD,SCSG 和 SVRG 转换为寻找近似局部极小值的算法,表现优于已知的一些最佳结果。
Nov, 2017
本文提出了一种基于加速梯度下降的新随机逼近算法,该算法在非强凸情况下取得了最佳预测误差率,并在加速遗忘初始条件方面达到了最优效果,同时在算法的平均迭代次数和最终迭代次数上均提供了收敛结果,该算法还在无噪声环境下提供了一个匹配下界,展示了我们算法的最优性。
Mar, 2022