Oct, 2018

高效贪心坐标下降求解组合问题

PDF
TL;DR本文提出一种针对一类非光滑复合问题的贪心更新规则，其中包括 $L1$- 正则化问题，SVM 等应用程序。我们提供了独立于 $n$ 的首个线性收敛速度，并且证明了我们的贪心更新规则提供了类似于光滑情况下所获得的速度提升。此外，我们还展示了我们的新选择规则可以映射到最大内积搜索实例中，从而利用标准最近邻算法来加速实现。通过广泛的数值实验证明了该方法的有效性。
coordinate descentgreedy updatesnon-smooth composite problemslinear rates of convergencemaximum inner product search
发现论文，激发创造
  • 近似最陡坐标下降

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

    Jun, 2017

  • 用一范数的最速下降法分析和改善对等约束优化的贪心 2 - 坐标更新

    通过在 L1 范数下的等式约束最速下降方法，考虑了考虑最小化一个带有一种约束并且有界约束的平滑函数的问题，提出了一种比随机选择更快的产生收敛的贪婪选择的收敛率，同时给出了支持向量机双重问题的规则。

    Jul, 2023

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

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

    May, 2013

  • 随机分块坐标下降算法优化复合函数的迭代复杂度

    通过开发随机块坐标下降法，我们证明该方法能够以概率至少为 1-rho 获得 Epsilon - 准确解，其迭代次数不超过 O (n / Epsilon*log (1/rho))，并且将前人研究的复杂度缩小 4 倍，消除了对数项中的 Epsilon，并成功地解决了 l1 正则化最小二乘和支持向量机等问题。

    Jul, 2011

  • 用于加速并行坐标下降的特征聚类

    本文介绍一种新的算法集合，叫做块贪心坐标下降法，用于解决大规模的 L1 正则化问题，此算法家族的收敛性分析表明用于此问题的算法可以更好的利用并行计算，此理论收敛性分析得到实际数据实验的支持。

    Dec, 2012

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

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

    Dec, 2015

  • 非光滑凸优化平滑原始 - 对偶坐标下降算法

    提出一种新的随机坐标下降方法，应用广泛，采用四种新颖的思想，包括平滑、加速、同伦、坐标下降和非均匀采样，具有迭代收敛保证，数值实验表明其优于现有算法。

    Nov, 2017

  • 自适应重要性采样加速坐标下降

    本文提出了一种新的自适应规则来随机选择决策变量的部分更新，以解决大规模的凸优化问题，并通过数学理论推导和数值实验加以验证。

    Mar, 2017

  • 大步长坐标下降原始 - 对偶算法与可能非可分函数

    该论文介绍了一种 V~u-Condat 算法的坐标下降版本，该算法可以解决具有可微函数、约束以及非可分、非可导的正则化器的优化问题，并且在更广泛的参数范围内比之前的方法产生了更好的收敛性能。

    Aug, 2015

  • 随机坐标下降法中的最优概率

    本文提出并分析了一种新的并行坐标下降方法 ---'NSync'，其中在每次迭代中更新随机坐标子集，同时允许非均匀选择子集，我们在强凸性假设下得到了收敛速率，同时说明了如何为集合分配概率以优化界限。该方法的复杂度和实际性能可以比其均匀变体快一个数量级。令人惊讶的是，每个迭代只更新一个随机选择的坐标系的策略 --- 以最优概率 --- 在理论和实践上都可能需要较少的迭代次数，而不是在每个迭代中更新所有坐标系的策略。

    Oct, 2013