子模函数:从离散到连续领域
介绍了子模函数的理论,包括在计算机科学和应用数学(如机器学习,计算机视觉,运筹学或电力网络)中发挥重要作用的集合函数,类似于向量空间上的凸函数。假定掌握了凸分析的基础知识。
Oct, 2010
本文研究了一类新的子模函数优化问题,提出了一种基于平滑凸优化的算法SLG,可用于解决具有数万个变量的分解子模函数问题,而且在一些合成基准测试和联合分类和分割任务中优于现有的子模函数优化算法。
Oct, 2010
本研究扩展了Narasimhan和Bilmes的工作,提出了基于子模函数差别最小化的新算法,该算法能有效地解决多种组合约束的问题,并且能够用于许多机器学习问题中,它在性能上优于现有的算法。
Jul, 2012
本文介绍了一种弱DR属性,用于给出有关子模性的统一特征,证明了可以在近似保证的同时高效地最大化子模连续函数,为在一般下闭凸约束条件下最大化单调DR-子模连续函数和在盒约束条件下的非单调子模连续函数提供了算法,并探讨了其在不同实际应用中的应用性。
Jun, 2016
这篇论文研究了函数的最大化问题,其中由凸可解体$P$所定义的一类$F(x) = G(x)+C(x)$函数是凸函数和DR子模函数的一个严格扩展,提供了一些算法实现,并在实际应用中进行了验证。
Jun, 2021
介绍了一个新的概念:在格子上定义函数的超模秩,是把函数分解为超模函数之和所需的最小项数;并且通过对不同偏序关系下定义超模和的方式,描述了具有固定超模秩的函数,以及类似地定义亚模秩;使用亚模分解来优化集合函数用于解决单调集合函数最大化和集合函数比率最小化的问题,特别地使用亚模秩的一个上界将优化问题分解成亚模子问题,从而提高了近似比的保证。
May, 2023
该论文提出了一种统一的方法来最大化连续DR-submodular函数,包括了一系列设置和oracle访问类型,并且给出了新的结果和改进的结果,其中包括一些与随机函数值有关的访问,使得其能够实现首个带有绑架反馈的悔恨边界。
May, 2023
在非凸优化的领域中,DR-submodular函数的优化在最近越来越重要,一些最近的工作探讨了在一般(不一定是下闭的)凸集约束下非单调DR-submodular函数的最大化,但之前的方法使用最小的L∞范数作为参数,而Mualem和Feldman的研究结果表明这种方法无法在下闭和非下闭约束之间进行平滑插值。本文提出了基于凸体约束的自然分解方法,通过提供下闭凸体和一般凸体两个不同凸体的插值,我们还通过三个离线应用和两个在线应用实证了我们所提算法的优越性。
Jan, 2024