子模 + 凹函数
本文介绍了一种弱 DR 属性,用于给出有关子模性的统一特征,证明了可以在近似保证的同时高效地最大化子模连续函数,为在一般下闭凸约束条件下最大化单调 DR - 子模连续函数和在盒约束条件下的非单调子模连续函数提供了算法,并探讨了其在不同实际应用中的应用性。
Jun, 2016
本研究探讨了在一般的向下封闭凸约束下最大化非单调 DR-submodular 连续函数的问题,通过研究其几何属性提出了两种具有漂亮保证的优化算法,并扩展到更广泛的广义 DR-submodular 连续函数类以适用于更多应用场景。
Nov, 2017
本文研究了 DR - 次模连续函数在最大化过程中的基本问题,并在凸集合的不同类型下提出了一系列在线算法,用于最小化在线非单调 DR - 次模函数。在实验中表现良好并为机器学习领域中有关问题提供了新的解决方案。
Sep, 2019
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
本文研究了次模函数及其在凸优化和概率测度方面的应用,提出了连续化的概率测度拓展方式,利用多重边际最优传送理论对次模集函数情况下的推论进行了拓展,最终给出了离散域中通用次模函数的实际最小化算法及其收敛速率。
Nov, 2015
该论文提出了一种统一的方法来最大化连续 DR-submodular 函数,包括了一系列设置和 oracle 访问类型,并且给出了新的结果和改进的结果,其中包括一些与随机函数值有关的访问,使得其能够实现首个带有绑架反馈的悔恨边界。
May, 2023
论文设计了一种新的逼近算法来解决在单一拟阵约束下优化子模和超模函数的问题,特别地,当目标函数有闭合总曲率时,获得了一个 (1-c/e)- 近似的结果;该算法基于连续贪心算法和非随机局部搜索的修改,并进行了扩展以包括在一些特定场景下的应用,例如最大熵抽样和列子集选择问题。
Nov, 2013
在非凸优化的领域中,DR-submodular 函数的优化在最近越来越重要,一些最近的工作探讨了在一般(不一定是下闭的)凸集约束下非单调 DR-submodular 函数的最大化,但之前的方法使用最小的 L∞范数作为参数,而 Mualem 和 Feldman 的研究结果表明这种方法无法在下闭和非下闭约束之间进行平滑插值。本文提出了基于凸体约束的自然分解方法,通过提供下闭凸体和一般凸体两个不同凸体的插值,我们还通过三个离线应用和两个在线应用实证了我们所提算法的优越性。
Jan, 2024
本文研究了许多学习应用中天然存在的连续子模函数的最大化问题,证明了随机投影梯度方法在凸约束下可以提供强的逼近保证,然后将其应用于随机子模函数的最大化问题,最后通过实验证明了该方法的有效性和实用性。
Aug, 2017