在线非单调 DR 子模最大化
本研究探讨了在一般的向下封闭凸约束下最大化非单调 DR-submodular 连续函数的问题,通过研究其几何属性提出了两种具有漂亮保证的优化算法,并扩展到更广泛的广义 DR-submodular 连续函数类以适用于更多应用场景。
Nov, 2017
该论文提出了一种统一的方法来最大化连续 DR-submodular 函数,包括了一系列设置和 oracle 访问类型,并且给出了新的结果和改进的结果,其中包括一些与随机函数值有关的访问,使得其能够实现首个带有绑架反馈的悔恨边界。
May, 2023
本文介绍了一种弱 DR 属性,用于给出有关子模性的统一特征,证明了可以在近似保证的同时高效地最大化子模连续函数,为在一般下闭凸约束条件下最大化单调 DR - 子模连续函数和在盒约束条件下的非单调子模连续函数提供了算法,并探讨了其在不同实际应用中的应用性。
Jun, 2016
在非凸优化的领域中,DR-submodular 函数的优化在最近越来越重要,一些最近的工作探讨了在一般(不一定是下闭的)凸集约束下非单调 DR-submodular 函数的最大化,但之前的方法使用最小的 L∞范数作为参数,而 Mualem 和 Feldman 的研究结果表明这种方法无法在下闭和非下闭约束之间进行平滑插值。本文提出了基于凸体约束的自然分解方法,通过提供下闭凸体和一般凸体两个不同凸体的插值,我们还通过三个离线应用和两个在线应用实证了我们所提算法的优越性。
Jan, 2024
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
这篇论文研究了函数的最大化问题,其中由凸可解体 $P$ 所定义的一类 $F (x) = G (x)+C (x)$ 函数是凸函数和 DR 子模函数的一个严格扩展,提供了一些算法实现,并在实际应用中进行了验证。
Jun, 2021
本研究提出了一种新的算法,用于在普遍限制条件下最大化非单调子模函数。该算法在下闭多面体上找到了一个函数的多线性扩展的近似分数解,其近似保证是 0.372,这是在 1/e 近似之上的首次改进,由连续贪心算法 [Feldman 等,FOCS2011] 实现。
Aug, 2016
研究在线赌徒学习中的单调多线性 DR - 子模函数设计算法 BanditMLSM,可以获得(1-1/e)遗憾的 O(T ^ {2/3} log T);将子模随机带入分割拟阵约束和赌徒顺序单调最大化,可以在两个问题中获得 O(T ^ {2/3} log T)的(1-1 /e)遗憾,这比现有结果更好。给出第一个关于具有分割拟阵约束的子模赌徒的次线性遗憾算法。
May, 2023
本文讨论了带有 $d$ 背包限制的任意模子模函数最大化问题,建立了离散问题和连续松弛之间的强联系,并利用这种联系提出了近似算法和确定性技术,得到了很好的解决方案。
Jan, 2011