Jun, 2016

针对呈递衰减收益的格子子模函数进行的优化减少

PDF
TL;DR该研究论文介绍了 DR-submodular 函数以及其最大化问题，给出了从 DR-submodular 方程到 submodular 方程的通用约简方式，并将前者的结果转化为后者，使其适用于许多类型的限制约束。
dr-submodularmaximizationbudget constraintsubmodularconstraints
发现论文，激发创造
  • 在线非单调 DR 子模最大化

    本文研究了 DR - 次模连续函数在最大化过程中的基本问题，并在凸集合的不同类型下提出了一系列在线算法，用于最小化在线非单调 DR - 次模函数。在实验中表现良好并为机器学习领域中有关问题提供了新的解决方案。

    Sep, 2019

  • 连续 DR - 次模最大化：结构和算法

    本研究探讨了在一般的向下封闭凸约束下最大化非单调 DR-submodular 连续函数的问题，通过研究其几何属性提出了两种具有漂亮保证的优化算法，并扩展到更广泛的广义 DR-submodular 连续函数类以适用于更多应用场景。

    Nov, 2017

  • 分布鲁棒子模最大化

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

    Feb, 2018

  • 将一般和闭凸集连接起来：子模最大化中的桥梁

    在非凸优化的领域中，DR-submodular 函数的优化在最近越来越重要，一些最近的工作探讨了在一般（不一定是下闭的）凸集约束下非单调 DR-submodular 函数的最大化，但之前的方法使用最小的 L∞范数作为参数，而 Mualem 和 Feldman 的研究结果表明这种方法无法在下闭和非下闭约束之间进行平滑插值。本文提出了基于凸体约束的自然分解方法，通过提供下闭凸体和一般凸体两个不同凸体的插值，我们还通过三个离线应用和两个在线应用实证了我们所提算法的优越性。

    Jan, 2024

  • 子模 + 凹函数

    这篇论文研究了函数的最大化问题，其中由凸可解体 $P$ 所定义的一类 $F (x) = G (x)+C (x)$ 函数是凸函数和 DR 子模函数的一个严格扩展，提供了一些算法实现，并在实际应用中进行了验证。

    Jun, 2021

  • 基于随机累积约束的在线 DR 子模最大化

    本研究考虑了在线连续 DR-submodular 最大化问题，采用了随机线性长期约束，并提出了在线 Lagrangian Frank-Wolfe（OLFW）算法来解决这类问题，得到了期望和高概率下的次线性后悔上限和次线性约束违规上限。

    May, 2020

  • 最大化连续 DR - 次模函数的统一方法

    该论文提出了一种统一的方法来最大化连续 DR-submodular 函数，包括了一系列设置和 oracle 访问类型，并且给出了新的结果和改进的结果，其中包括一些与随机函数值有关的访问，使得其能够实现首个带有绑架反馈的悔恨边界。

    May, 2023

  • 保证的非凸优化：连续域上的子模最大化

    本文介绍了一种弱 DR 属性，用于给出有关子模性的统一特征，证明了可以在近似保证的同时高效地最大化子模连续函数，为在一般下闭凸约束条件下最大化单调 DR - 子模连续函数和在盒约束条件下的非单调子模连续函数提供了算法，并探讨了其在不同实际应用中的应用性。

    Jun, 2016

  • 超模极大化 —— 非非负性保证、快速算法和应用

    本文研究次模函数的优化和算法问题，提出了一种在 $k$-cardinality 约束下最大化 $g-c$ 的算法，并通过实验设计对其进行了验证。

    Apr, 2019

  • 约束子模最大化问题：超越 1/e

    本研究提出了一种新的算法，用于在普遍限制条件下最大化非单调子模函数。该算法在下闭多面体上找到了一个函数的多线性扩展的近似分数解，其近似保证是 0.372，这是在 1/e 近似之上的首次改进，由连续贪心算法 [Feldman 等，FOCS2011] 实现。

    Aug, 2016