ICMLJan, 2022

随机连续次模最大化：通过非遗忘函数增强

PDF
TL;DR本文研究了随机连续子模最大化问题，在离线和在线两种场景下提出了一种基于 boosting 方法的算法，有效地解决了 DR-submodular 目标函数的最大化问题，并在对抗性环境下讨论了梯度反馈的在线情况。数值实验验证了算法的有效性。
stochastic continuous submodular maximizationboosting frameworkonline gradient ascentdr-submodular objective functionadversarial delays
发现论文，激发创造
  • 在线连续子模最大化

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

    Feb, 2018

  • 次模最大化的梯度方法

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

    Aug, 2017

  • 基于条件梯度方法的随机次模最大化：弥合差距

    研究连续子模最大化问题，通过提供新颖的算法并使用随机持续优化作为接口，在满足约束条件的情况下获得了紧密的逼近保证。

    Nov, 2017

  • 随机条件梯度方法：从凸优化到子模最大化

    该论文提出了基于随机条件梯度方法的优化问题求解算法，用于解决大规模维度下的凸函数、连续子模型等多种问题，并证明了当问题维度高时，该方法较与传统的随机梯度下降法更加稳定，同时计算时间复杂度也得到了有效降低。

    Apr, 2018

  • 基于随机梯度的无需投影的在线优化：从凸性到次模性

    该论文提出了一种新颖的元 Frank-Wolfe 算法及其简化版 One-Shot-Frank-Wolfe，用于对在线优化进行全局和子模最优解的快速求解。其方法基于梯度下降实现，通过随机梯度估算和孪生逼近算法来降低收敛难度。

    Feb, 2018

  • 随机子模极大化：覆盖函数的情形

    该论文研究了如何将随机梯度下降等连续优化算法应用到离散问题中的子模优化，通过将扩展线性化处理并通过向上投影处理，得到离散解，针对加权覆盖函数进行研究，实验表明，该方法在保证最优近似率的同时，大幅降低了计算成本。

    Nov, 2017

  • 随机条件梯度 ++

    本文提出了一种用于非显式随机优化问题的算法 SFW ++，使用该算法可以快速收敛于全局最优解，并通过一些简单的结构扩展，可以优化跨不同优化问题的条件梯度方法。

    Feb, 2019

  • 连续 DR - 次模函数最大化的梯度上升增强

    通过引入提升技术，我们改进了标准 PGA 方法的逼近性能，并在四个问题上验证了其有效性。

    Jan, 2024

  • 通过多项式估计进行随机子模最大化

    本研究以连续贪心算法为基础，研究了具有一般性骨架约束的随机子模最大化问题，主要应用于在线学习，团队形成，设施位置，影响最大化，主动学习和感知目标函数。实验表明，使用多项式梯度估计代替样本估计，可有效减少随机性并缩短执行时间。

    Mar, 2023

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

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

    May, 2020