NIPSJun, 2018

二次可分解次模函数最小化

PDF
TL;DR本文提出了一种新的凸优化问题 —— 二次可分解子模函数极小化问题，该问题与可分解子模函数极小化问题密切相关，并在许多基于图和超图的学习环境中产生，例如基于图的半监督学习和 PageRank。我们采用了一种新的解决策略，并描述了可以通过随机坐标下降（RCD）方法和锥体投影优化的目标。我们还确定了 RCD 算法的线性收敛率，并开发了具有可证明性能保证的高效投影算法。基于超图的半监督学习的数字实验证实了所提出算法的效率，并证明了与现有最先进方法相比，在预测精度方面取得了显着的改进。
发现论文，激发创造
  • 随机坐标下降方法在最小化可分解子模函数中的应用

    本文研究子模函数最小化问题，并采用随机坐标下降方法来获得具有更快线性收敛率和更低迭代成本的算法。与交替投影方法相比，我们的算法不依赖于完全维度的向量运算，并且收敛所需的迭代次数显著减少。

    Feb, 2015

  • 可分解次模函数的高效最小化

    本文研究了一类新的子模函数优化问题，提出了一种基于平滑凸优化的算法 SLG，可用于解决具有数万个变量的分解子模函数问题，而且在一些合成基准测试和联合分类和分割任务中优于现有的子模函数优化算法。

    Oct, 2010

  • 可分解子模函数最小化的收敛速度

    本文介绍一种易用且可并行的用于最小化由 “简单” 子模函数组成的子模函数的算法，并在几何子模多面体的基础上，利用谱图理论结果证明该算法线性收敛，并给出了收敛速率的上下界。

    Jun, 2014

  • 学习和最小化子模函数的曲率和最优算法

    本文探究了三个相关且重要的机器学习问题。我们展示了这三个问题的复杂度都依赖于子模函数的 ' 曲率 '，并提供了改进旧有结果的上下界。我们证明了曲率对于子模函数的近似、最小化和学习有影响，并通过实验结果支持了我们的理论结论。

    Nov, 2013

  • 子模函数学习：凸优化观点

    本文从凸分析的角度介绍了子模函数，论述了子模函数最小化与各类凸优化问题的关系，提出了新的高效算法以及多种子模函数在机器学习中的应用。

    Nov, 2011

  • 分布式子模最大化

    本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi，该方法可在 MapReduce 框架下实现，初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题，如稀疏高斯过程推断和样例聚类等问题，且在一定的自然条件下，可以达到接近于传统集中式计算模式下的性能表现。

    Nov, 2014

  • 可分解次模函数的最小化问题：离散和连续

    研究离散和连续方法在可分解子模函数最小化中的联系，提出了基于组合论的优化算法的改进时间估计，并通过明确级别 - 0 和级别 - 1 算法之间的明显区别，对两种方法进行了系统的实验性比较。

    Mar, 2017

  • 可微子模最大化

    本文提出一种针对子模函数的数据学习算法，可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布，本文提出一种可微的方式对模型进行优化。实证研究表明，该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。

    Mar, 2018

  • 基于快速半微分的次模函数优化

    文章提出了一种基于离散半微分的无约束和有约束子模函数优化的实用强大新框架，旨在为子模最小化和最大化问题提供统一的范例，并为解决这些问题提供了新的算法，该算法能够多次计算和高效率优化子模半梯度。作者还分析了该算法的理论性质，并进行了支撑的经验实验，证明其在最大化问题上的优秀表现。

    Aug, 2013

  • 次二次子模函数最小化

    本文通过在 submodular 函数的 Lovasz 扩展上使用投影随机次梯度下降法，利用子模性和数据结构来获得快速的坐标轴下降算法，实现了针对整数值子模函数的超线性 SFM 算法和针对实值子模函数的几乎线性 SFM 算法。

    Oct, 2016