Feb, 2018

在线连续子模最大化

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

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

    Feb, 2018

  • 在线连续子模最大化：从完全信息到 Bandit 反馈

    本文提出了三种在线算法，分别用于子模最大化问题中的函数渐变计算优化、带赌博的子模最大化问题和响应式带乘积集约束的带乘积子模问题。三个算法在达到 $(1-1/e)$ -regret bound 的前提下，分别取得了复杂度为 $O (T^{4/5})$、$O (T^{8/9})$ 以及 $O (T^{8/9})$ 的折损。

    Oct, 2019

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

    本文研究了随机连续子模最大化问题，在离线和在线两种场景下提出了一种基于 boosting 方法的算法，有效地解决了 DR-submodular 目标函数的最大化问题，并在对抗性环境下讨论了梯度反馈的在线情况。数值实验验证了算法的有效性。

    Jan, 2022

  • 在线凸优化下的在线次模最大化

    研究了在线环境下的通用拟阵约束下的单调子模最大化问题，证明了一大类子模函数在在线凸优化问题中的优化等价性，通过合适的舍入方案，实现了在组合优化中达到次线性后悔的 OCO 算法。同时，该规约也适用于多种不同版本的在线学习问题，包括动态后悔、游走和乐观学习等。

    Sep, 2023

  • 改进的无投影在线连续子模最大化

    本文提出了一种投影 - 无关算法 POBGA，通过在线提升梯度上升算法、不可行的投影技术和阻塞技术的新颖组合，以及分散设置的变体，有效地缩短了由先前算法 Mono-FW 降低的后悔下限，并将通信复杂度从 O（T）降低到 O（√T）。

    May, 2023

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

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

    May, 2020

  • 次模最大化的梯度方法

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

    Aug, 2017

  • 在线非单调 DR 子模最大化

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

    Sep, 2019

  • 关于凸优化和非凸优化的在线 Frank-Wolfe 算法

    探讨在线变体的 Frank-Wolfe 算法，包括简单迭代更新和非自适应步长规则，研究凸和非凸损失的多个新结果，并基于对随机 Frank-Wolfe 算法的改进分析得出在强凸随机成本时的遗憾界和任何时刻的最优性为 O (log^3T/T) 和 O (log^2T/T) ; 此外，该在线算法即使在损失非凸的情况下也能收敛，以速率 O (1/T 的平方根) 找到时变 / 随机损失的稳态点。

    Oct, 2015

  • 在线动态次模优化

    该研究提出了用于在线二元优化的一种新算法，基于子模函数实现，并在动态环境下添加普适约束，最后通过测试发现算法在快速响应能力和网络再配置等方面具有广泛的应用价值。

    Jun, 2023