从理论到实践的一阶凸优化的催化剂加速
本研究引入了一种通用方案,利用对加速邻域点算法的新分析,加快一阶优化方法。通过近似解决一系列精心选择的辅助问题来最小化凸目标,从而实现更快的收敛速度,为包括梯度下降、块坐标下降、SAG、SAGA、SDCA、SVRG、Finito/MISO 及其邻域点变体在内的大类算法提供加速和明确的非强凸目标支持,加速在实践中证明对病态问题尤其有用。
Jun, 2015
该论文介绍了一种通用的方案,使用最初设计用于最小化凸函数的梯度下降算法来解决非凸优化问题,该方案允许我们将这些方法用于弱凸性目标,这涵盖了机器学习和信号处理中通常出现的大类非凸函数。该方案无需假定目标函数具有凸性,而是通过自适应于未知的弱凸性常数来实现其保证。最后,本文还展示了将该方案应用于增量算法的几个实验结果。
Mar, 2017
本文提出了一个通用框架,允许加速几乎任意非加速确定性和随机算法用于光滑凸优化问题,其中通过使用加速的近端外梯度方法作为非加速内方法的包络来实现。该算法有两个关键不同之处:容易验证的内部算法停止标准和学习率的可调节性,使得此工作的主要贡献是适用于自适应内部算法 Steepset Descent、Adaptive Coordinate Descent 和 Alternating Minimization 的新框架。此外,在非自适应情况下,我们的方法允许获得没有对数因子的 Catalyst,这与标准 Catalyst 不同。
Nov, 2019
本文介绍了在目标函数为凸或强凸函数时获取加速一阶随机优化算法的各种机制,同时扩展了最初用于确定性目标的 Catalyst 方法到随机问题领域,并提供了一个新的关于处理不精确近端算子时的鲁棒性的泛化分析
Jun, 2019
本文介绍了用于凸优化中的加速技术的两个关键方法族(动量和嵌套优化方案),动量方法结构收敛证明使用几个主模板(例如用于优化梯度方法的那个)和近端加速,探讨了重新启动方案和一些常见的加速的技术。
Jan, 2021
本文回顾了近端点法在大规模优化中的作用,并重点介绍了三个最新的例子:用于弱凸随机逼近的近端指导次梯度法,用于最小化凸函数和平滑映射组合的近端线性算法以及用于正则化经验风险最小化的 Catalyst 通用加速。
Dec, 2017
本文提出了一种名为 RECAPP 的新型加速近端点法,通过放宽误差标准来避免高精度算法,该方法在有限和问题中能够获得最好的已知复杂度,并且在凸优化中也表现出良好的性能。
Jun, 2022
本文提出了一种加速的一阶优化算法 —— 鲁棒动量法,可用于优化平滑强凸函数。该算法有一种参数可以调节对梯度噪声的稳健性与最差情况下的收敛速度之间的平衡。算法具有简单的解析形式,并通过在干净和梯度噪声情况下的一系列数值模拟进行了验证。
Oct, 2017
本文探讨了非凸优化中加速近端梯度法及其变体的收敛性,并提出了一种新的变体利用自适应动量和块坐标更新来进一步改进广泛类别的非凸问题中的性能,在稀疏线性回归和正则化中表现出可证明的局部线性收敛性。
Oct, 2017