基于梯度的非凸优化的催化剂加速
介绍了一种名为 Catalyst 的通用方案,通过解决一系列适当选择的辅助问题来加速各种优化算法(包括梯度下降、块坐标下降和增量算法),从而加快收敛速度。
Dec, 2017
本研究引入了一种通用方案,利用对加速邻域点算法的新分析,加快一阶优化方法。通过近似解决一系列精心选择的辅助问题来最小化凸目标,从而实现更快的收敛速度,为包括梯度下降、块坐标下降、SAG、SAGA、SDCA、SVRG、Finito/MISO 及其邻域点变体在内的大类算法提供加速和明确的非强凸目标支持,加速在实践中证明对病态问题尤其有用。
Jun, 2015
本文提出了一个通用框架,允许加速几乎任意非加速确定性和随机算法用于光滑凸优化问题,其中通过使用加速的近端外梯度方法作为非加速内方法的包络来实现。该算法有两个关键不同之处:容易验证的内部算法停止标准和学习率的可调节性,使得此工作的主要贡献是适用于自适应内部算法 Steepset Descent、Adaptive Coordinate Descent 和 Alternating Minimization 的新框架。此外,在非自适应情况下,我们的方法允许获得没有对数因子的 Catalyst,这与标准 Catalyst 不同。
Nov, 2019
本文介绍了在目标函数为凸或强凸函数时获取加速一阶随机优化算法的各种机制,同时扩展了最初用于确定性目标的 Catalyst 方法到随机问题领域,并提供了一个新的关于处理不精确近端算子时的鲁棒性的泛化分析
Jun, 2019
该论文将 Nesterov 的加速梯度方法推广到非凸和可能的随机优化问题中,证明该方法可以最优地解决一般的非凸光滑优化问题,并可应用于重要类的复合优化问题和非凸随机优化问题,是文献中第一次确立了 AG 方法解决非凸非线性规划的收敛性。
Oct, 2013
本文介绍了一种新的非均匀光滑条件下的优化方法,并开发出一种简单但有效的分析技术来限制沿轨迹的梯度,从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了(随机)梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率,而不需要梯度剪裁,并允许在随机场景中的有界方差的重尾噪声。
Jun, 2023
我们提出了一种新的优化方法,通过类似于椭球体法的简单几何解释,实现了超平滑何强凸函数的无约束优化,并在数值实验中证明了其优于 Nesterov 加速梯度下降。
Jun, 2015
本文介绍了用于凸优化中的加速技术的两个关键方法族(动量和嵌套优化方案),动量方法结构收敛证明使用几个主模板(例如用于优化梯度方法的那个)和近端加速,探讨了重新启动方案和一些常见的加速的技术。
Jan, 2021
本文提出了 AdaACSA、AdaAGD + 等新的自适应一阶优化算法,以加速受限制的凸优化问题中的收敛速度,同时针对平滑和不平滑函数,实现几乎最优的收敛速率;同时,通过自动调整每个坐标学习率,这些算法不需要固定事先知道目标函数的参数化,是针对限制优化的真正加速 Adagrad 方法之一。此外,本文提出了适用于无限制优化和单调算子的自适应方法,并附有具体的算法实现。
Jul, 2020
本文分析了一种用于优化非凸问题的快速递增聚合梯度方法,在递增一阶预言框架中分析了 SAGA 算法,并表明它比梯度下降和随机梯度下降更快地收敛到稳定点。此外,我们还讨论了 Polyak 特殊类的问题,针对这类问题,SAGA 方法的收敛速度为线性收敛到全局最优解。最后,我们分析了实际有用的 SAGA 正则化和小批量变体。据我们所知,这篇论文提出了第一篇关于递增聚合梯度方法快速收敛的分析。
Mar, 2016