Apr, 2013

不精确坐标下降法：复杂性与预调节

PDF
TL;DR本文考虑使用随机块坐标下降方法来最小化一个凸函数，其中关键步骤是更新变量块。现有算法假定为计算更新需要完全解决一个特定子问题。作者在本研究中放宽了这个要求，允许子问题被部分解决，导致一种不完全的块坐标下降方法。本方法将精确更新的最佳结果作为特例，并使用迭代技术和预处理进行进一步的加速。
convex functionrandomized block coordinate descentinexact updateiterative techniquespreconditioning
发现论文，激发创造
  • 更加现实的假设下的异步坐标下降

    本篇论文研究非同步并行块协调下降算法，证明了更实际的假设条件下算法的收敛性，并构建了直接模拟目标进展和延迟的李雅普诺夫函数。

    May, 2017

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

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

    Jul, 2011

  • 坐标下降算法

    本研究旨在介绍了坐标下降算法的基本原理、变体及其扩展，特别关注于在数据分析、机器学习等领域中的应用及并行执行的收敛性等。

    Feb, 2015

  • 随机块坐标下降方法解决网络线性约束最优化问题

    本文介绍了基于随机块坐标梯度下降的并行优化算法，能够快速高效地解决大规模线性可分凸问题在网络结构上的应用，收敛速率与更新组件 $ au$ 线性相关，并探讨了稀疏半定规划解法和具体应用。

    Apr, 2015

  • 坐标下降算法入门

    该专著介绍了坐标下降算法，主要研究优化问题的解决方法，适用于机器学习、数据科学、工程等领域。

    Sep, 2016

  • 分布式块坐标下降法用于最小化部分可分离函数

    本文提出了一种分布式随机块坐标下降方法来最小化具有大量变量 / 坐标的凸函数，并分析了其复杂度，其中局部块可分的光滑部分直接影响了其复杂度，进一步扩展了已有研究成果，该方法在分布式环境下的实现还使用了集群计算和计算同步等技术。

    Jun, 2014

  • 基于块坐标更新的非凸优化全局收敛算法

    提出了一种基于 prox-linear surrogate 的原则的优化算法，证明了其全迭代序列收敛于关键点并具有较快的收敛速度，并将其应用于非凸正则化线性回归和非负矩阵分解等问题。

    Oct, 2014

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

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

    May, 2013

  • 坐标下降与赌博抽样

    提出一种自适应选择坐标方法来提高坐标下降方法的收敛性，该方法通过多臂老虎机算法学习使用具有较大下降下限的坐标进行更新，从而解决了检查所有坐标的困难，提高了计算效率。

    Dec, 2017

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

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

    Dec, 2012