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

ICMLAug, 2013

Fast Semidifferential-based Submodular Function Optimization

Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes

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

Abstract

We present a practical and powerful new framework for both unconstrained and constrained submodular function optimization based on discrete semidifferentials (sub- and super-differentials). The resulting algorithms, which repeatedly compute and then efficiently optimize submodular semi

submodular function optimization discrete semidifferentials machine learning optimization algorithms theoretical and empirical analyses

发现论文，激发创造

可微子模最大化

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

Mar, 2018

分布鲁棒子模最大化

通过直接优化偏差和方差的组合，该研究通过展示如何进行具有理论保证的高效算法，从而在次模函数中进行分布式鲁棒优化（DRO），从而实现在未知随机次模函数的情况下实现更好的性能和更好的推广。

Feb, 2018

次二次子模函数最小化

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

Oct, 2016

用户友好型次模优化的反射方法

该研究提出了一种基于离散子模规划问题的连续最佳逼近算法，提高了优化子模函数的效率和精度，并在图像分割任务中展示了该算法的优越性。

Nov, 2013

次模性、凸性和凹性的多面体方面

本文通过扩展 Edmonds 和 Lovasz 的研究，提供了关于子模性与凸性和凹性之间关系的更完整的画面，同时探讨了子模最大化的优化条件和一些近似条件的应用。

Jun, 2015

子模函数：扩展、分布和算法。一份调查

本文介绍了子模函数的连续松弛及其在优化问题中的应用，同时提出了一种基于对称子模函数的基数约束下，最小化函数的常系数逼近算法。

Dec, 2009

在线连续子模最大化

本文研究一种在线优化过程，其中目标函数不是凸函数（也不是凹函数），而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体，它可以访问目标函数的全梯度，并证明它对未来最佳可行解的（1-1/e）- 近似具有 O（T 的平方根）的遗憾界。对于只能获得梯度的无偏估计的情况，我们还提出了在线随机梯度上升算法，并证明它也具有 O（T 的平方根）的遗憾界，但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数，并证明相同的次线性遗憾界。最后，在几个问题实例上演示了算法的效率，包括非凸 / 非凹二次规划，子模集函数的多线性扩展和 D - 最佳设计。

Feb, 2018

次模最大化的梯度方法

本文研究了许多学习应用中天然存在的连续子模函数的最大化问题，证明了随机投影梯度方法在凸约束下可以提供强的逼近保证，然后将其应用于随机子模函数的最大化问题，最后通过实验证明了该方法的有效性和实用性。

Aug, 2017

近似最小化次模函数差的算法及应用

本研究扩展了 Narasimhan 和 Bilmes 的工作，提出了基于子模函数差别最小化的新算法，该算法能有效地解决多种组合约束的问题，并且能够用于许多机器学习问题中，它在性能上优于现有的算法。

Jul, 2012

子模函数：从离散到连续领域

本文研究了次模函数及其在凸优化和概率测度方面的应用，提出了连续化的概率测度拓展方式，利用多重边际最优传送理论对次模集函数情况下的推论进行了拓展，最终给出了离散域中通用次模函数的实际最小化算法及其收敛速率。

Nov, 2015