Apr, 2024

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

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

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

    Sep, 2019

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

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

    Nov, 2017

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

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

    Mar, 2024

  • 线性子模最大化与赌徒反馈

    在带有赌博反馈的子模函数优化中，考虑使用逼近算法来最大化线性结构的子模客观函数，通过模拟算法和实证研究检验了样本效率与线性结构的关系。

    Jul, 2024

  • 最大化连续 DR - 次模函数的统一方法

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

    May, 2023

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

  • 二次可分解次模函数最小化

    本文提出了一种新的凸优化问题 —— 二次可分解子模函数极小化问题，该问题与可分解子模函数极小化问题密切相关，并在许多基于图和超图的学习环境中产生，例如基于图的半监督学习和 PageRank。我们采用了一种新的解决策略，并描述了可以通过随机坐标下降（RCD）方法和锥体投影优化的目标。我们还确定了 RCD 算法的线性收敛率，并开发了具有可证明性能保证的高效投影算法。基于超图的半监督学习的数字实验证实了所提出算法的效率，并证明了与现有最先进方法相比，在预测精度方面取得了显着的改进。

    Jun, 2018

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

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

    May, 2020

  • 通过积分二次约束分析优化算法：非强凸问题

    本文提出了一个统一的框架，能够证明广泛使用的迭代一阶优化算法的指数收敛和次指数收敛速率，并展示了该框架对梯度法、近端算法及其加速变体的实用性，同时开发了连续时间对应物，能够分析梯度流和 Nesterov 加速法的连续时间极限。

    May, 2017

  • 将一般和闭凸集连接起来：子模最大化中的桥梁

    在非凸优化的领域中，DR-submodular 函数的优化在最近越来越重要，一些最近的工作探讨了在一般（不一定是下闭的）凸集约束下非单调 DR-submodular 函数的最大化，但之前的方法使用最小的 L∞范数作为参数，而 Mualem 和 Feldman 的研究结果表明这种方法无法在下闭和非下闭约束之间进行平滑插值。本文提出了基于凸体约束的自然分解方法，通过提供下闭凸体和一般凸体两个不同凸体的插值，我们还通过三个离线应用和两个在线应用实证了我们所提算法的优越性。

    Jan, 2024