Apr, 2024

一个块坐标下降的多目标优化算法：理论和实证分析

PDF
TL;DR存在一种条件，使得块坐标下降在进化多目标优化中达到渐近效率，我们考虑了这个开放问题并提出了块坐标版本的 GSEMO 算法来与标准 GSEMO 算法的运行时间进行比较，理论和实证结果表明了块坐标下降更快的情况的存在，这一结果可能对此类算法产生更广泛的见解。
发现论文，激发创造
  • 分布式块坐标下降法用于最小化部分可分离函数

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

    Jun, 2014

  • 多目标问题（前导 1，尾随 0）的进化多样性优化的运行时分析

    本研究分析了进化多目标优化算法在多样性优化问题中的应用，并证明了一种算法能够在预期的迭代次数下计算出所有 Pareto 最优解。同时，还分析了该算法找到具有最佳多样性的种群所需的迭代次数，并通过实证研究验证了理论预测的准确性。

    Apr, 2024

  • $(1+(λ,λ))$ 全局 SEMO 算法

    本研究设计了一种遗传算法以及动态参数设置，针对多目标优化问题达到更快的运行时，并在算法证明过程中对其在运行时方面进行了验证。

    Oct, 2022

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

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

    Dec, 2012

  • 使用 GSEMO 在 OneMinMax 上进行多样性优化的严格运行时分析

    本论文研究了 GSEMO 算法在多目标优化中优化群体多样性的方法，阐述了该算法在解决 Pareto - 最优问题中的优势，并得到当问题规模为奇数时，预期时间内收敛到具有最优多样性的种群的证明，分析中涉及了种群的随机漫步等相关理论。

    Jul, 2023

  • 坐标下降算法

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

    Feb, 2015

  • 坐标下降算法入门

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

    Sep, 2016

  • 大规模高斯过程回归的贪婪块坐标下降

    通过提出变量分解算法 - greedy block coordinate descent（GBCD）-，我们将密集高斯过程回归变得实用，解决了现有方法的局限性，并将主动集选择转化为零规范约束优化问题，使用贪心方法求解，进而在实证比较中证明了 GBCD 具有全局收敛的能力并且比竞争算法更快、更准确。

    Jun, 2012

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

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

    Jul, 2011

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

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

    Nov, 2015