May, 2014

非强凸损失的快速分布式坐标下降

PDF
TL;DR本文提出了一种高效的分布式随机坐标下降算法，用于最小化正则化的非强凸损失函数，并经过在英国最大的超级计算机 Archer 上的实现，表明该算法可以有效解决一个具有 500 亿个变量的 LASSO 优化问题，具有 O (1/k^2) 的收敛速度。
distributedcoordinate descentregularizationoptimizationsupercomputer
发现论文，激发创造
  • 异步并行随机坐标下降算法

    本文提出了一种异步并行随机坐标下降算法，它具有线性收敛速率和 $1/K$ 的次线性速率，可实现基于多核系统的近线性加速，并取得了在 40 核处理器上的实现结果。

    Nov, 2013

  • 大数据优化的并行坐标下降方法

    本文针对最小化部分可分平滑凸函数和简单可分离凸函数之和的问题，展示了随机（块）坐标下降法在并行化时可以加速。 研究表明，与串行方法相比，在高概率下近似解决问题所需的迭代次数的理论加速比简单地依赖于并行处理器数量和目标函数平滑部分可分离的自然且易于计算的可分离度度量。 此外，当每次迭代更新的块数是随机的时，该算法的处理能力也非常出色，并可以解决涉及具有 200 亿个非零元素的矩阵的 LASSO 问题。

    Dec, 2012

  • 用于大规模结构化非凸优化的高效随机坐标下降算法

    本篇研究分析几种解决非凸优化问题的新方法，其中目标函数为由非凸光滑项和已知凸简单项组成的总和，提出了随机坐标下降算法，并研究了它们的收敛性质及一些最优性衡量指标。同时，还针对一般情况下的非凸复合优化问题，证明了算法所生成的序列渐近收敛到固定点，同时在某些最优性测度下期望具有亚线性收敛率，如果目标函数满足误差界限条件，则导出了目标函数期望值的局部线性收敛率，并进行了广泛的数值实验来评估算法性能和与现有方法的比较。

    May, 2013

  • 强凸优化的最优分布式随机镜像下降

    本文研究在多智能体网络中，基于 Bregman 散度作为距离测度函数，提出了两种高效的非欧几里德随机次梯度下降算法，用于求解非平滑和强凸函数的最小值，并在模拟实验中验证其收敛速度。

    Oct, 2016

  • 使用非均匀采样加速坐标下降更快速

    本文针对大规模问题，提出了一种采用非均匀采样、每个坐标加权的加速坐标下降方法，实现了加速梯度下降和经验风险最小化的优化，使得运行时间显著减少。

    Dec, 2015

  • 异步随机坐标下降：并行与收敛性质

    本文提出一种异步并行随机近端坐标下降算法，用于最小化由光滑凸函数和可分离凸函数组成的复合目标函数，并给出在多核处理器上的实现结果。

    Mar, 2014

  • 用于正则化损失最小化的加速近端随机双坐标上升

    本文介绍了一种基于近端随机对偶坐标上升方法的算法，并演示了如何使用内外迭代过程加速该方法。我们分析了该框架的运行时，并获得了改进各种关键机器学习优化问题（包括 SVM、逻辑回归、岭回归、套索以及多类别 SVM）的最新结果的速率。实验验证了我们的理论发现。

    Sep, 2013

  • 近似最陡坐标下降

    通过在巨大规模优化问题的坐标下降方法中对坐标选择提出一种新的选择准则，其效率显著优于均匀随机选择，并可以达到最陡坐标下降（SCD）的效率，使加速达到最多 n 倍，并在许多实际应用中可以不花费任何额外成本且计算效率非常接近更快的均匀选择。数值实验表明，该方法具有很好的性能改进，并符合理论保证。

    Jun, 2017

  • 大数据学习的分布式坐标下降方法

    本文介绍了一种名为 Hydra 的解决大数据损失最小化问题的混合坐标下降方法，该方法将坐标进行初始分区并在每次迭代时在不同的节点上处理，并对所需迭代次数给出了较高概率下的界限。

    Oct, 2013

  • 解线性系统的高效加速坐标下降方法和更快的算法

    该论文介绍了如何加速随机坐标下降方法，提高收敛速度，同时又不用支付每次迭代的代价。它提出了一个新的通用方法，并证明它的收敛性，并在多个领域中获得更快的渐近运行时间。

    May, 2013