Oct, 2019

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

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

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

    Feb, 2018

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

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

    Feb, 2018

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

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

    Sep, 2019

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

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

    May, 2020

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

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

    Jan, 2022

  • 基于多线性DR-次模极大化的Bandit算法及其在对抗性次模Bandit中的应用

    研究在线赌徒学习中的单调多线性DR-子模函数设计算法BanditMLSM，可以获得（1-1/e）遗憾的O（T ^ {2/3} log T）；将子模随机带入分割拟阵约束和赌徒顺序单调最大化，可以在两个问题中获得O（T ^ {2/3} log T）的（1-1 / e）遗憾，这比现有结果更好。给出第一个关于具有分割拟阵约束的子模赌徒的次线性遗憾算法。

    May, 2023

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

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

    May, 2023

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

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

    Sep, 2023

  • 带有赌徒反馈的最小化最大化子模优化

    利用随机bandit反馈在无序集合函数最大化问题中建立了首个极小极大下界，并提出了一个能够匹配下界的算法。

    Oct, 2023

  • 求和最大子模函数博弈

    在线决策问题、子模函数、求和-最大函数、强化学习以及后悔上界是该研究论文的主要关键词和内容。

    Nov, 2023