加速、并行和近端坐标下降
本文针对最小化部分可分平滑凸函数和简单可分离凸函数之和的问题,展示了随机(块)坐标下降法在并行化时可以加速。 研究表明,与串行方法相比,在高概率下近似解决问题所需的迭代次数的理论加速比简单地依赖于并行处理器数量和目标函数平滑部分可分离的自然且易于计算的可分离度度量。 此外,当每次迭代更新的块数是随机的时,该算法的处理能力也非常出色,并可以解决涉及具有 200 亿个非零元素的矩阵的 LASSO 问题。
Dec, 2012
本文提出了一种异步并行随机坐标下降算法,它具有线性收敛速率和 $1/K$ 的次线性速率,可实现基于多核系统的近线性加速,并取得了在 40 核处理器上的实现结果。
Nov, 2013
介绍了一个基于 proximal 的对偶协调上升方法,该算法框架可以用于多种正则化损失最小化问题,包括 l1 正则化和结构化输出 SVM。我们取得的收敛速度与现有最先进结果匹配并有时超过。
Nov, 2012
本文介绍了一种基于近端随机对偶坐标上升方法的算法,并演示了如何使用内外迭代过程加速该方法。我们分析了该框架的运行时,并获得了改进各种关键机器学习优化问题(包括 SVM、逻辑回归、岭回归、套索以及多类别 SVM)的最新结果的速率。实验验证了我们的理论发现。
Sep, 2013
本文提出了一种分布式随机块坐标下降方法来最小化具有大量变量 / 坐标的凸函数,并分析了其复杂度,其中局部块可分的光滑部分直接影响了其复杂度,进一步扩展了已有研究成果,该方法在分布式环境下的实现还使用了集群计算和计算同步等技术。
Jun, 2014
本文提出了一种基于随机加速的坐标梯度下降法(APCG)来求解具有分块可分特征的凸组合优化问题的算法,并且应用此算法于正则化的经验风险最小化(ERM)问题,相较于现有算法其在强凸性和病态问题方面取得了更好的收敛速度。
Jul, 2014
我们扩展了 Approximate-Proximal Point 方法,在随机凸优化问题中应用包括随机次梯度、近端点和束方法,同时提出了更快的模型算法和加速方案,保持了 Approximate-Proximal Point 算法的鲁棒性,同时提供了更快的收敛速度和更低的界限。我们通过实证测试证实了理论结果的可行性。
Jan, 2021
研究并分析随机坐标下降方法的设计和复杂度,特别是每次迭代在一个随机子集(采样)中更新的变体,这取决于期望可分离过逼近(ESO)的概念。本文为一类函数和任意采样推导了这种不等式,该方法基于与采样和描述函数的数据相关的特征值的研究。
Dec, 2014
本文探讨了非凸优化中加速近端梯度法及其变体的收敛性,并提出了一种新的变体利用自适应动量和块坐标更新来进一步改进广泛类别的非凸问题中的性能,在稀疏线性回归和正则化中表现出可证明的局部线性收敛性。
Oct, 2017