May, 2024

一种快速且可扩展的路径求解器：基于分块坐标下降法的组套索和弹性网络惩罚回归

PDF
TL;DR基于块坐标下降的快速可扩展算法用于解决广义线性模型中的群组套索和群组弹性网络问题，特别关注普通最小二乘损失（高斯损失），展示了每个块坐标更新可以通过牛顿方法高效解决，进一步利用自适应二分法进行改进，具有二次收敛速度。我们的基准测试显示，我们的 adelie 软件包在广泛的模拟和真实数据集上比下一个最快的软件包快 3 到 10 倍。此外，我们证明我们的软件包也是一个竞争的 lasso 求解器，与流行的 lasso 软件包 glmnet 的性能相当。
发现论文，激发创造
  • Lasso 惩罚回归的坐标下降算法

    本文研究了基于 lasso 惩罚的回归问题，并提出了两个非常快的算法来估计回归系数，其中一个算法基于循环坐标下降，而另一个基于贪心坐标下降和 Edgeworth 的算法。此外，如果对参数进行分组并对每个组进行惩罚，则可以将现有算法扩展到新领域。

    Mar, 2008

  • 路径坐标优化

    本文介绍了 “逐一” 坐标下降算法及其在 $ L_1 $- 惩罚回归（套索）、garotte 和弹性网络等相关方法中的应用，证明了该算法可以与广泛应用的 LARS（或同伦）过程竞争，在大规模 lasso 问题中引起了不少关注。但注意到它并不适用于 “融合 Lasso”，所以论文提出了一个广义算法，在比标准的凸优化器运行时间更短的时间内得出了解决方案。最后，将该过程推广到二维融合 Lasso，并展示了其在一些图像平滑问题上的性能。

    Aug, 2007

  • 基于块降算法的分组惩罚多响应和多项式回归

    本文提出了一种基于分组惩罚的多响应回归的分块下降算法，用拟牛顿框架将其扩展至分组惩罚的多项式回归，并给出了在 R 中使用的公开实现，比较其速度与一种竞争算法，结果表明我们的算法比其竞争对手快一个数量级，并可实时解决基因表达规模的问题。

    Nov, 2013

  • 关于群 Lasso 和稀疏群 Lasso 的说明

    该论文探讨了基于群回归的线性模型问题，提出了一种更加通用的罚函数，该罚函数将 L1 范数和群 L2 范数相融合，可以同时稀疏化群和个体特征。此外，为了解决该问题，提出了一种基于坐标下降的高效算法，该算法也适用于处理非正交模型矩阵的群回归的一般形式。

    Jan, 2010

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

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

    Dec, 2012

  • 组别下降算法用于具有组别预测变量的非凸罚线性和逻辑回归模型

    该论文研究使用一些非凸罚项方法解决群体选择问题并进行变量选择的统计性能比较。

    Sep, 2012

  • 大规模鞍点问题的随机并行块坐标下降

    本文提出一种新的针对分离结构和非强凸函数的凸凹鞍点问题的高效随机块坐标下降方法，采用自适应原始 - 对偶更新方法，可灵活地并行优化大规模问题。该方法在多个机器学习应用中均有显著提高，包括鲁棒主成分分析、Lasso 和通过组 Lasso 进行特征选择等。在理论和实际上，我们证明了该方法在所有这些应用中都具有明显优势。

    Nov, 2015

  • 网络套索：大型图中的聚类和优化

    本文介绍了基于交替方向乘子法的分布式可扩展解决网络套索问题的算法，在图形数据上进行聚类和优化，比对了基准方法并表明其是在解决大型优化问题中既快速又准确的方法。

    Jul, 2015

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

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

    May, 2014

  • 拟合受限 Lasso 的算法

    本研究比较了在求解有约束的 Lasso 问题中的几种不同的计算策略（包括二次规划、交替方向乘子法、以及一种高效的求解路径算法）。在通过模拟和真实数据示例的比较之后，提出了适用于不同数据规模下的实际建议，同时也发现一般化 Lasso 可以转化为有约束的 Lasso 问题，但反之则不成立。因此，该研究的方法也可以用于估计具有广泛应用的一般化 Lasso。

    Oct, 2016