本文研究了一类新的子模函数优化问题,提出了一种基于平滑凸优化的算法 SLG,可用于解决具有数万个变量的分解子模函数问题,而且在一些合成基准测试和联合分类和分割任务中优于现有的子模函数优化算法。
Oct, 2010
本文提出了一种新的凸优化问题 —— 二次可分解子模函数极小化问题,该问题与可分解子模函数极小化问题密切相关,并在许多基于图和超图的学习环境中产生,例如基于图的半监督学习和 PageRank。我们采用了一种新的解决策略,并描述了可以通过随机坐标下降(RCD)方法和锥体投影优化的目标。我们还确定了 RCD 算法的线性收敛率,并开发了具有可证明性能保证的高效投影算法。基于超图的半监督学习的数字实验证实了所提出算法的效率,并证明了与现有最先进方法相比,在预测精度方面取得了显着的改进。
Jun, 2018
本文研究子模函数最小化问题,并采用随机坐标下降方法来获得具有更快线性收敛率和更低迭代成本的算法。与交替投影方法相比,我们的算法不依赖于完全维度的向量运算,并且收敛所需的迭代次数显著减少。
Feb, 2015
研究离散和连续方法在可分解子模函数最小化中的联系,提出了基于组合论的优化算法的改进时间估计,并通过明确级别 - 0 和级别 - 1 算法之间的明显区别,对两种方法进行了系统的实验性比较。
Mar, 2017
该研究提出了一种基于离散子模规划问题的连续最佳逼近算法,提高了优化子模函数的效率和精度,并在图像分割任务中展示了该算法的优越性。
Nov, 2013
本文介绍了通过使用广义子模函数代替较简单的目标函数获得的几个传统计算机科学问题的推广,包括子模型负载平衡,子模型最稀疏切割和子模型平衡切割等,并建立了这些问题的近似界限。
May, 2008
本文介绍了子模函数的连续松弛及其在优化问题中的应用,同时提出了一种基于对称子模函数的基数约束下,最小化函数的常系数逼近算法。
Dec, 2009
本文探究了三个相关且重要的机器学习问题。我们展示了这三个问题的复杂度都依赖于子模函数的 ' 曲率 ',并提供了改进旧有结果的上下界。我们证明了曲率对于子模函数的近似、最小化和学习有影响,并通过实验结果支持了我们的理论结论。
文章提出了一种基于离散半微分的无约束和有约束子模函数优化的实用强大新框架,旨在为子模最小化和最大化问题提供统一的范例,并为解决这些问题提供了新的算法,该算法能够多次计算和高效率优化子模半梯度。作者还分析了该算法的理论性质,并进行了支撑的经验实验,证明其在最大化问题上的优秀表现。
Aug, 2013
本文从凸分析的角度介绍了子模函数,论述了子模函数最小化与各类凸优化问题的关系,提出了新的高效算法以及多种子模函数在机器学习中的应用。
Nov, 2011