本研究旨在介绍了坐标下降算法的基本原理、变体及其扩展,特别关注于在数据分析、机器学习等领域中的应用及并行执行的收敛性等。
Feb, 2015
本篇论文研究非同步并行块协调下降算法,证明了更实际的假设条件下算法的收敛性,并构建了直接模拟目标进展和延迟的李雅普诺夫函数。
May, 2017
该论文介绍了如何加速随机坐标下降方法,提高收敛速度,同时又不用支付每次迭代的代价。它提出了一个新的通用方法,并证明它的收敛性,并在多个领域中获得更快的渐近运行时间。
May, 2013
本文提出了一种高效的分布式随机坐标下降算法,用于最小化正则化的非强凸损失函数,并经过在英国最大的超级计算机 Archer 上的实现,表明该算法可以有效解决一个具有 500 亿个变量的 LASSO 优化问题,具有 O (1/k^2) 的收敛速度。
May, 2014
研究加速贪婪坐标下降算法,在理论和实践中分别探究 $O (1/k^2)$ 收敛及其在强凸函数方面加速线性收敛的性能,引入并研究了两种算法:加速半贪婪坐标下降(ASCD)和加速贪婪坐标下降(AGCD)算法,实验结果表明 AGCD 优于其他加速坐标下降方法。
Jun, 2018
本文提出了一种异步并行随机坐标下降算法,它具有线性收敛速率和 $1/K$ 的次线性速率,可实现基于多核系统的近线性加速,并取得了在 40 核处理器上的实现结果。
Nov, 2013
该专著介绍了坐标下降算法,主要研究优化问题的解决方法,适用于机器学习、数据科学、工程等领域。
Sep, 2016
最近,有人提出可以从最优控制理论中统一不同的优化算法。我们通过展示如何从这一新兴原理中导出坐标下降算法来进一步证明此命题。特别地,我们展示了基本的坐标下降算法可以通过使用最大原理和一组最大函数作为 “控制” Lyapunov 函数来导出。因此,由导致的控制系统的 Lyapunov 函数的耗散与相应的坐标下降算法的收敛性相关。所有情况下,搜索向量的运算度量均由凸目标函数的 Hessian 给出。
Sep, 2023
本篇研究分析几种解决非凸优化问题的新方法,其中目标函数为由非凸光滑项和已知凸简单项组成的总和,提出了随机坐标下降算法,并研究了它们的收敛性质及一些最优性衡量指标。同时,还针对一般情况下的非凸复合优化问题,证明了算法所生成的序列渐近收敛到固定点,同时在某些最优性测度下期望具有亚线性收敛率,如果目标函数满足误差界限条件,则导出了目标函数期望值的局部线性收敛率,并进行了广泛的数值实验来评估算法性能和与现有方法的比较。
本文提出并分析了一种新的并行坐标下降方法 ---'NSync',其中在每次迭代中更新随机坐标子集,同时允许非均匀选择子集,我们在强凸性假设下得到了收敛速率,同时说明了如何为集合分配概率以优化界限。该方法的复杂度和实际性能可以比其均匀变体快一个数量级。令人惊讶的是,每个迭代只更新一个随机选择的坐标系的策略 --- 以最优概率 --- 在理论和实践上都可能需要较少的迭代次数,而不是在每个迭代中更新所有坐标系的策略。
Oct, 2013