Jun, 2024

具有 $k$- 次模函数的 Stackelberg 博弈下的分配风险感知性和鲁棒性

PDF
TL;DR我们研究了在对抗环境中的子模规划优化问题，该问题适用于机器学习中使用容易受到不确定性和攻击的数据进行特征选择。我们关注攻击者和防御者之间的斯塔克尔伯格博弈，攻击者的目标是最小化防御者最大化的 k - 子模规函数。我们考虑攻击成功和数据噪声带来的不确定性，并解决了由于对随机参数的概率分布的不完全了解而引起的挑战。具体而言，我们引入了分布度风险厌恶 k - 子模规拦截问题（DRA k-SIP）和分布度风险接受 k - 子模规拦截问题（DRR k-SIP），并提出了针对它们的收敛精确算法。DRA k-SIP 解决方案允许风险规避的拦截者制定针对现实世界不确定性的稳健策略。相反，DRR k-SIP 解决方案提供了攻击者的进攻策略，他们愿意承担（分布）风险以造成最大的损害，并确定了关键易受攻击的组件，这可以用于防御者的防御策略。从 DRA k-SIP 和 DRR k-SIP 中得出的最优值为防御者的目标函数的期望值提供了一个类似置信区间的范围，用于捕捉分布的不确定性。我们使用特征选择和传感器放置问题的实例以及威斯康星乳腺癌数据和合成数据进行了计算实验。
submodular optimizationadversarial contextstackelberg gamesuncertaintiesfeature selection
发现论文，激发创造
  • 分布鲁棒子模最大化

    通过直接优化偏差和方差的组合，该研究通过展示如何进行具有理论保证的高效算法，从而在次模函数中进行分布式鲁棒优化（DRO），从而实现在未知随机次模函数的情况下实现更好的性能和更好的推广。

    Feb, 2018

  • 计算最优分布式鲁棒策略

    本文研究了基于分布鲁棒优化的 Stackelberg 游戏模型，特别是在不确定下属效用模型的情况下，寻找最优策略以保护某些资产。我们的研究表明，在广泛的不确定模型下，分布鲁棒 Stackelberg 均衡始终存在。当存在无限个下属效用函数且不确定性由支持有限名义分布周围的 Wasserstein 球表示时，我们提出了一种基于混合整数规划的增量算法来计算最优的分布鲁棒策略。实验结果显示，我们的方法可扩展到中等规模的 Stackelberg 游戏，从而验证了算法的可行性。

    Sep, 2022

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

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

    Nov, 2017

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

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

    Mar, 2024

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

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

    May, 2023

  • 针对呈递衰减收益的格子子模函数进行的优化减少

    该研究论文介绍了 DR-submodular 函数以及其最大化问题，给出了从 DR-submodular 方程到 submodular 方程的通用约简方式，并将前者的结果转化为后者，使其适用于许多类型的限制约束。

    Jun, 2016

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

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

    May, 2020

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

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

    Sep, 2019

  • 韧性单调子模函数最大化

    本研究关注机器学习、优化和控制中的鲁棒优化问题，在面临多种故障或攻击时，提出了首个可扩展的曲率相关算法，用于近似求解单调子模目标函数，保证了优秀的逼近性能，并使用实验证明了该算法的有效性。

    Mar, 2017

  • 满足背包约束的敌对鲁棒次模最大化

    该研究提出了针对单个和多个背包约束下的单调次模最大化的首个对抗鲁棒算法，具有可扩展的分布式和流式实现。性能评估结果表明，与现有非鲁棒算法的自然鲁棒化相比，该算法对于大型社交网络图等输入具有最佳的目标结果，并表现出极强的性能，即使与提前给出拆除集合的线下算法相比也是如此。

    May, 2019