Mar, 2014

Matroid Bandits: 快速组合优化与学习

PDF
TL;DR通过结合 bandit 和 matroid 的思想，本篇论文提出了一种新型组合赌博算法 ——matroid bandits，它的目标是在 matroid 中最大化一个随机的初始未知的模块化函数，并提供了一种切实可行的算法 —— 乐观 matroid 最大化（OMM），证明了两个上界，gap-dependent 和 gap-free，时间复杂度均为亚线性，与其他相关量最多线性相关。同时在三个实际问题上测试，证明了该方法是有效的。
发现论文，激发创造
  • 利用不确定性的结构实现高效 Matroid 半 Bandits

    本研究通过将实现优化为特定的子模最大化，并设计适应的近似程序，提供了首个可以依赖奖励结构来改善遗憾界限的有效算法。这一改进将状态 - of-the-art 的无间隙遗憾界限显著提高了 sqrt (m)/log m 倍。最后，我们证明了我们的改进如何转化为更普遍的预算组合半强盗。

    Feb, 2019

  • 子模最大化问题的紧凑组合算法在矩阵约束条件下的应用

    提出了一种基于组合数学的算法，用于求解在一个制约性匹配中的单调子模优化问题，算法具有很高的精度和时间效率。

    Apr, 2012

  • 基于矩阵约束的多臂赌博纯探索

    研究了在随机多臂赌博游戏中受拟阵约束（Best-Basis）的纯勘探问题，提供了几乎最优样本复杂度的算法，以确定拟阵的基并达到最大总权重。

    May, 2016

  • 次线性时间下的拟阵半赌博问题

    研究了 matroid semi-bandits 问题，提出了一个计算更便宜的算法 FasterCUCB，基于对内积权重的近似最大重量基的动态维护，能够保证与 CUCB 相匹配的遗憾上限，用来最大化期望累积线性回报。

    May, 2024

  • 基于拟阵的全动态次模最大化

    研究单调子模函数下的最大值问题以及约束条件下的问题，提出了一个随机的动态算法，并给出了一个高效的数据结构来处理发生了添加和删除变化的值，该算法能够提供一个 4 近似解。

    May, 2023

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

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

    Mar, 2023

  • 在线玄学最大化下的基合约束与学习分配应用

    本文提出了一种能够动态地为信息源进行排序，同时又能保证重复信息的减少不会影响子模函数的最优化问题算法，并在真实的 Web 数据集中分别实验了广告分配和动态排名两个在线优化问题。

    Jul, 2014

  • 并行下考虑拟阵约束和装箱限制的子模块最大化

    本文提出了一种在单个 matroid 约束或多个 packing 约束下，通过小量自适应查询轮次来最大化 submodular 函数的多线性扩展的算法，该算法在 submodular maximization with a matroid constraint 和 non-monotone submodular maximization subject to packing constraints 两个问题上均获得了近乎最佳的拟合比例，并且在自适应轮次和并行运行时间上提出了指数级别的加速。

    Aug, 2018

  • 求和最大子模函数博弈

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

    Nov, 2023

  • 子模集约束下的公平性最大化

    在机器学习中，基于 matroid 约束的子模最大化是一个具有各种应用的基本问题。最近，已经在有限制条件下的流式和离线设置下考虑了基于基数约束的子模最大化中的公平性，但对于更一般的 matroid 约束问题，只有在流式设置下且只考虑单调目标。本文通过提出各种算法和不可能性结果，在质量、公平性和广泛性之间提供了不同的权衡。

    Dec, 2023