坐标下降算法
最近,有人提出可以从最优控制理论中统一不同的优化算法。我们通过展示如何从这一新兴原理中导出坐标下降算法来进一步证明此命题。特别地,我们展示了基本的坐标下降算法可以通过使用最大原理和一组最大函数作为 “控制” Lyapunov 函数来导出。因此,由导致的控制系统的 Lyapunov 函数的耗散与相应的坐标下降算法的收敛性相关。所有情况下,搜索向量的运算度量均由凸目标函数的 Hessian 给出。
Sep, 2023
提出一种自适应选择坐标方法来提高坐标下降方法的收敛性,该方法通过多臂老虎机算法学习使用具有较大下降下限的坐标进行更新,从而解决了检查所有坐标的困难,提高了计算效率。
Dec, 2017
本文研究子模函数最小化问题,并采用随机坐标下降方法来获得具有更快线性收敛率和更低迭代成本的算法。与交替投影方法相比,我们的算法不依赖于完全维度的向量运算,并且收敛所需的迭代次数显著减少。
Feb, 2015
该论文介绍了一种 V~u-Condat 算法的坐标下降版本,该算法可以解决具有可微函数、约束以及非可分、非可导的正则化器的优化问题,并且在更广泛的参数范围内比之前的方法产生了更好的收敛性能。
Aug, 2015
提出了在矩阵流形上开发计算效率高的坐标下降(CD)算法的一般框架,从而允许在每次迭代中仅更新少数变量,并符合流形约束。通过一阶目标函数的近似实现了更高效的变体,分析了它们的收敛性和复杂性,并在多个应用中验证了它们的有效性。
Jun, 2024
本篇研究分析几种解决非凸优化问题的新方法,其中目标函数为由非凸光滑项和已知凸简单项组成的总和,提出了随机坐标下降算法,并研究了它们的收敛性质及一些最优性衡量指标。同时,还针对一般情况下的非凸复合优化问题,证明了算法所生成的序列渐近收敛到固定点,同时在某些最优性测度下期望具有亚线性收敛率,如果目标函数满足误差界限条件,则导出了目标函数期望值的局部线性收敛率,并进行了广泛的数值实验来评估算法性能和与现有方法的比较。
May, 2013
该论文介绍了如何加速随机坐标下降方法,提高收敛速度,同时又不用支付每次迭代的代价。它提出了一个新的通用方法,并证明它的收敛性,并在多个领域中获得更快的渐近运行时间。
May, 2013
通过在巨大规模优化问题的坐标下降方法中对坐标选择提出一种新的选择准则,其效率显著优于均匀随机选择,并可以达到最陡坐标下降(SCD)的效率,使加速达到最多 n 倍,并在许多实际应用中可以不花费任何额外成本且计算效率非常接近更快的均匀选择。数值实验表明,该方法具有很好的性能改进,并符合理论保证。
Jun, 2017
本文考虑使用随机块坐标下降方法来最小化一个凸函数,其中关键步骤是更新变量块。现有算法假定为计算更新需要完全解决一个特定子问题。作者在本研究中放宽了这个要求,允许子问题被部分解决,导致一种不完全的块坐标下降方法。本方法将精确更新的最佳结果作为特例,并使用迭代技术和预处理进行进一步的加速。
Apr, 2013