ICLRMar, 2024

统一的无投影算法用于对抗性 DR-Submodular 优化

PDF
TL;DR该论文介绍了统一的无投影 Frank-Wolfe 类型算法，用于对抗性连续 DR - 次模优化，跨越了全信息和（半）助手反馈、单调和非单调函数、不同约束和类型的随机查询等情景。在非单调设置中，所提出的算法要么是第一个经过证明具有亚线性 α- 遗憾界的算法，要么具有优于现有技术的 α- 遗憾界，其中 α 是离线设置中的相应逼近界。在单调设置中，所提出的方法在 8 个考虑的情况中，在 7 个情况中给出了投影免费算法的最新亚线性 α- 遗憾界，同时与其余情况的结果相匹配。此外，本文还研究了对抗性 DR - 次模优化中的半助手反馈和助手反馈，推动了对这一优化领域的理解。
发现论文，激发创造
  • 最大化连续 DR - 次模函数的统一方法

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

    May, 2023

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

    该论文提出了一种新颖的元 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

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

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

    May, 2023

  • 在线连续子模最大化

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

    Feb, 2018

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

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

    Sep, 2019

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

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

    Nov, 2017

  • 基于多线性 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

  • 面向无梯度和无投影的随机优化

    本文介绍了一种零阶 Frank-Wolfe 算法，用于解决约束随机优化问题，该算法与基本 Frank-Wolfe 算法同样无需投影，且不需要计算梯度，可收敛于凸平滑约束下的优化目标函数。同时，本算法在具有每次迭代一个方向导数的所有零阶优化算法中具有最优维度依赖性。对于非凸函数，本算法的 Frank-Wolfe gap 为 O (d^{1/3} T^{-1/4})，并在黑盒优化设置上进行实验，证明了其效果。

    Oct, 2018

  • 从线性到线性化优化：一种新的框架及其在静态和非静态 DR - 子模块优化中的应用

    本文介绍了上线性可编码 / 可平方化函数的概念，该类函数扩展了凹性和 DR - 次模性，适用于不同凸集的单调和非单调情况。提出了一种通用的元算法，将线性 / 二次最大化的算法转化为优化上可平方化函数的算法，为处理凹和 DR - 次模优化问题提供了统一方法。将这些结果扩展到多反馈设置，促进了半强盗 / 一阶反馈与盗贼 / 零阶反馈之间，以及一阶 / 零阶反馈与半强盗 / 盗贼反馈之间的转换。利用这个框架，使用跟随扰动领袖（FTPL）算法和其他算法作为线性 / 凸优化的基础算法，得到了新的无投影算法，改善了各种情况下的现有最新结果。在 DR - 次模最大化中获得了动态和自适应的遗憾保证，这是在这些设置中首次实现此类保证的算法。值得注意的是，与现有最新结果相比，本文在较少的假设下实现了这些进展，突显了其对非凸优化的广泛适用性和理论贡献。

    Apr, 2024